【正文】 ? 由于概率發(fā)送，有些時(shí)隙被閑置 ? 需要時(shí)鐘同步 5: DataLink Layer 530 時(shí)隙 Aloha的效率 ? 假設(shè) : 有 N個(gè)活躍節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)在每個(gè)時(shí)隙開(kāi)始時(shí)以概率 P發(fā)送 ? 給定節(jié)點(diǎn)在一個(gè)時(shí)隙中發(fā)送成功的概率 = p(1p)N1 ? 給定時(shí)隙中有節(jié)點(diǎn)發(fā)送成功的概率 = Np(1p)N1 ? 最大效率 : ? 找到令 Np(1p)N1最大的概率 p* ? 代入 Np*(1p*)N1， 并令N趨向于無(wú)窮，得到： ? 最大效率 = 1/e = 效率： 當(dāng)網(wǎng)絡(luò)中存在大量活躍節(jié)點(diǎn)時(shí)，長(zhǎng)期運(yùn)行過(guò)程中成功時(shí)隙所占的比例 最佳情況 : 信道用于有效傳輸?shù)臅r(shí)間僅為 37%！ 5: DataLink Layer 531 Pure ALOHA ? 基本思想： ? 任何節(jié)點(diǎn)有數(shù)據(jù)發(fā)送就可以立即發(fā)送 ? 節(jié)點(diǎn)通過(guò)監(jiān)聽(tīng)信道判斷本次傳輸是否成功 ? 若不成功，立即以概率 P重傳，以概率（ 1P）推遲至下一個(gè)幀時(shí) ? 發(fā)生沖突的情形： ? 在時(shí)刻 t0發(fā)送的幀與在 [t01,t0+1] 時(shí)段內(nèi)發(fā)送的其它幀沖突 5: DataLink Layer 532 純 Aloha的效率 P(給定節(jié)點(diǎn)發(fā)送成功 ) = P(節(jié)點(diǎn)發(fā)送 ) . P(無(wú)其它節(jié)點(diǎn)在 [t01,t0]內(nèi)發(fā)送 ) . P(無(wú)其它節(jié)點(diǎn)在 [t0, t0+1]內(nèi)發(fā)送 ) = p . (1p)N1 . (1p)N1 = p . (1p)2(N1) 求出令節(jié)點(diǎn)發(fā)送成功概率 Np . (1p)2(N1)最大的 p*，并令 N infty: 最大效率 = 1/(2e) = 5: DataLink Layer 533 載波偵聽(tīng)多址接入（ CSMA） ?發(fā)送前監(jiān)聽(tīng)信道： ?信道空閑 : 發(fā)送整個(gè)幀 ?信道忙：推遲發(fā)送 ?沖突仍可能發(fā)生 : ?由于存在傳輸延遲，節(jié)點(diǎn)可能沒(méi)有監(jiān)聽(tīng)到其它節(jié)點(diǎn)正在發(fā)送 ?一旦發(fā)生沖突，整個(gè)幀傳輸時(shí)間被浪費(fèi) 5: DataLink Layer 534 CSMA/CD (Collision Detection) ?帶沖突檢測(cè)的 CSMA ?通過(guò)測(cè)量收到的信號(hào)強(qiáng)度檢測(cè)沖突（ 沖突信號(hào)的強(qiáng)度較大 ） ?檢測(cè)到?jīng)_突后 立即停止傳輸損壞的幀 （ 減少信道浪費(fèi) ） 以太網(wǎng) MAC協(xié)議 ?以太網(wǎng)采用 CSMA/CD協(xié)議 : 1. NIC從網(wǎng)絡(luò)層接收數(shù)據(jù)報(bào)，構(gòu)造以太幀 2. 若 NIC監(jiān)聽(tīng)到信道空閑，立即發(fā)送幀；若信道忙，堅(jiān)持監(jiān)聽(tīng)直至發(fā)現(xiàn)信道空閑，然后發(fā)送幀 3. 若 NIC發(fā)送完整個(gè)幀而沒(méi)有檢測(cè)到?jīng)_突，認(rèn)為發(fā)送成功！ 4. 若 NIC在傳輸過(guò)程中檢測(cè)到?jīng)_突，立即停止發(fā)送幀，并發(fā)送一個(gè)阻塞信號(hào) 5: DataLink Layer 535 以太網(wǎng) MA協(xié)議（續(xù)） 5. NIC進(jìn)入 指數(shù)回退 階段 : ? 第一次沖突 : 從 {0,1}中選擇 K，延遲 K? 512比特時(shí)間 ? 第二次沖突后 : 從 {0,1,2,3}中選擇 K， …… ? 第三次沖突后 : 從 {0,1,2,3,4,5,6,7}中選擇 K， …… ?…… ? 第 10次沖突后，從 {0,1,2,3,4,…,1023}中選擇 K， …… 6. 返回 Step 2 ?指數(shù)回退的目的是根據(jù)網(wǎng)絡(luò)負(fù)載調(diào)整重傳時(shí)間： ?負(fù)載越重（沖突次數(shù)越多）：隨機(jī)等待時(shí)間越長(zhǎng) 5: DataLink Layer 536 5: DataLink Layer 537 CSMA/CD的效率 ? Tprop = 以太網(wǎng)中任意兩個(gè)節(jié)點(diǎn)之間傳播延遲的 最大值 ? ttrans = 最長(zhǎng)幀的傳輸時(shí)間 ?在以下情況下，以太網(wǎng)的效率趨近于 1： ?tprop 趨近于 0，或 ?ttrans 趨向于無(wú)窮 t r an sp r op /tte f f i c i e nc y 51 1??5: DataLink Layer 538 輪流 MAC協(xié)議 —輪詢 ?主節(jié)點(diǎn)輪流 ―邀請(qǐng) ‖從節(jié)點(diǎn)發(fā)送 ?缺點(diǎn) : ?引入 輪詢 延遲 ?單點(diǎn)失效 （主節(jié)點(diǎn)） 主節(jié)點(diǎn) 從節(jié)點(diǎn) poll data data 5: DataLink Layer 539 輪流 MAC協(xié)議 —令牌傳遞 ?網(wǎng)絡(luò)中有一個(gè) 令牌 ，按照預(yù)定的順序在節(jié)點(diǎn)間傳遞 ?獲得令牌的節(jié)點(diǎn)可以發(fā)送 ?缺點(diǎn)： ?令牌傳遞延遲 ?單點(diǎn)失效（令牌） T data (nothing to send) T 5: DataLink Layer 540 MAC協(xié)議比較 信道劃分 MAC協(xié)議 : ? 重負(fù)載下高效： 沒(méi)有沖突 ，節(jié)點(diǎn)公平使用信道 ? 輕負(fù)載下 低效：即使只有一個(gè)活躍節(jié)點(diǎn)也只能使用1/N的帶寬 隨機(jī)接入 MAC協(xié)議 ? 輕 負(fù)載時(shí)高效 ： 單個(gè)活躍節(jié)點(diǎn)可以使用整個(gè)信道 ? 重 負(fù)載時(shí)低效 ： 頻繁發(fā)生 沖突，信道使用效率低 輪流協(xié)議 （ 試圖權(quán)衡以上兩者 ） ? 按需使用信道（避免輕負(fù)載下固定分配信道的低效） ? 消除競(jìng)爭(zhēng)（避免重負(fù)載下的發(fā)送沖突） 5: DataLink Layer 541 MAC協(xié)議小結(jié) ?按照時(shí)間、頻率、編碼 劃分 信道： ? 時(shí)分 多址 ，頻分 多址 ，碼分 多址 ?隨機(jī)接入： ? ALOHA, SALOHA（ ALOHA網(wǎng)絡(luò)） ? CSMA/CD（早期以太網(wǎng)） ? CSMA/CA（ ） ?輪流 ? 中心節(jié)點(diǎn)輪詢（藍(lán)牙） ? 令牌傳遞（ FDDI， IBM令牌環(huán)，令牌總線 ） 5: DataLink Layer 542 Data link layer so far: ? 服務(wù) ? 差錯(cuò)檢測(cè) /糾正 ? 多址接入 Next: LAN technologies ? 鏈路層編址 ? 以太網(wǎng) ? 交換機(jī) ? VLAN 局域網(wǎng)、城域網(wǎng)和廣域網(wǎng) ?局域網(wǎng) LAN（ Local Area Network） ? 將小范圍內(nèi)的計(jì)算機(jī)及外設(shè)連接起來(lái)的網(wǎng)絡(luò)，范圍在幾公里以內(nèi) ?城域網(wǎng) MAN（ Metropolitan Area Network ） ? 通常覆蓋一個(gè)城市的范圍（幾十公里），如有線電視網(wǎng)、寬帶無(wú)線網(wǎng)等 ? 城域網(wǎng)要能支持?jǐn)?shù)據(jù)、音頻和視頻在內(nèi)的綜合業(yè)務(wù)，服務(wù)質(zhì)量好，支持用戶數(shù)量多 ?廣域網(wǎng) WAN（ Wide Area Network） ? 通常覆蓋一個(gè)國(guó)家或一個(gè)洲（一百公里以上），規(guī)模和容量可任意擴(kuò)大 5: DataLink Layer 543 Link Layer 544 Link layer, LANs: outline introduction, services error detection, correction multiple access protocols LANs ? addressing, ARP ? Ether ? switches ? VLANS link virtualization: MPLS data center working a day in the life of a web request 鏈路層編址 ? 每一塊網(wǎng)絡(luò)適配器（網(wǎng)卡）固定分配一個(gè)地址，稱為MAC地址，也稱物理地址、硬件地址、鏈路層地址等 ? MAC地址長(zhǎng) 6個(gè)字節(jié)，一般用由“ : ”或“ ”分隔的 6個(gè)十六進(jìn)制數(shù)表示 ? MAC地址由 IEEE負(fù)責(zé)分配，每塊適配器的地址是全球唯一的： ? 網(wǎng)卡生產(chǎn)商向 IEEE購(gòu)買一塊 MAC地址空間（前 3字節(jié)） ? 生產(chǎn)商確保生產(chǎn)的每一塊網(wǎng)卡有不同的 MAC地址 ? MAC地址固化在網(wǎng)卡的 ROM中 ? 現(xiàn)在用軟件改變網(wǎng)卡的 MAC地址也是可能的 5: DataLink Layer 546 每個(gè)適配器有一個(gè) MAC地址 Broadcast address = FFFFFFFFFFFF = adapter 1A2FBB7609AD 5823D7FA20B0 0CC4116FE398 7165F72B0853 LAN (wired or wireless) MAC地址類型 ?目的 MAC地址有三種類型： ?單播地址：適配器的 MAC地址，地址最高比特為 0 ?多播地址：標(biāo)識(shí)一個(gè)多播組的邏輯地址，地址最高比特為 1 ?廣播地址： ff:ff:ff:ff:ff:ff ?網(wǎng)絡(luò)適配器僅將發(fā)送給本節(jié)點(diǎn)的幀（單播，廣播，多播）交給主機(jī) ?若將適配器設(shè)置成混收模式，適配器將收到的所有幀交給主機(jī) 向同一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)發(fā)送 ? 在同一個(gè)物理網(wǎng)絡(luò)上，數(shù)據(jù)報(bào)如何從一個(gè)節(jié)點(diǎn)到達(dá)另一個(gè)節(jié)點(diǎn)？ ? 發(fā)送節(jié)點(diǎn)的網(wǎng)絡(luò)層將數(shù)據(jù)報(bào)和接收節(jié)點(diǎn)的物理地址交給數(shù)據(jù)鏈路層 ? 數(shù)據(jù)鏈路層將數(shù)據(jù)報(bào)封裝在一個(gè)鏈路層幀中，在物理網(wǎng)絡(luò)上發(fā)送 ? 接收主機(jī)的適配器收到幀，判斷是發(fā)給本機(jī)的，取出數(shù)據(jù)報(bào)交給網(wǎng)絡(luò)層 ? 問(wèn)題： ? 發(fā)送節(jié)點(diǎn)如何獲得接收節(jié)點(diǎn)的物理地址？ ? 幀如何到達(dá)接收節(jié)點(diǎn)？ 地址解析（ Address Resolution） ?發(fā)送節(jié)點(diǎn)的網(wǎng)絡(luò)層知道接收節(jié)點(diǎn)的 IP地址 ，如： ? 源主機(jī)知道源路由器的 IP地址（缺省路由） ? 中間 路由器知道下一跳的 IP地址 （查找轉(zhuǎn)發(fā)表） ? 目的路由器知道目的主機(jī)的 IP地址 ?問(wèn)題： ? 發(fā)送節(jié)點(diǎn) 已知 接收節(jié)點(diǎn)的 IP地址 ，想 獲得接收節(jié)點(diǎn)的MAC地址 ?地址解析： ? 獲得與 IP地址 對(duì)應(yīng)的 MAC地址 地址解析的方法 ?靜態(tài)映射 IP地址 MAC地 址的缺點(diǎn)： ?主機(jī)