第5章數據結構

我們的目標:

理解支撐鏈路層服務的原則:差錯檢測,糾正共享廣播信道:多路訪問鏈路層編址可靠數據傳輸,流量控制:前面已分析過各種鏈路層技術實例與實現第5章鏈路層和局域網1數據鏈路層與局域網第5章鏈路層5.1概述與服務5.2差錯檢測和糾錯5.3多路訪問協(xié)議5.4鏈路層編址5.5以太網5.6集線器和交換機5.7PPP5.8鏈路虛擬化:ATM和MPLS2數據鏈路層與局域網鏈路層:主要分析的內容分組如何通過各段鏈路？網絡層的數據報如何被封裝成鏈路層的幀？

鏈路層協(xié)議是否能夠提供路由器之間的可靠數據傳輸？

通信路徑上不同的鏈路是否采用不同的鏈路層協(xié)議？3數據鏈路層與局域網鏈路層:概述某些術語:主機和路由器是節(jié)點連接沿通信路徑的相鄰節(jié)點的路徑是鏈路有線鏈路無線鏈路局域網第二層的分組叫幀,

封裝數據報“l(fā)ink”數據鏈路層具有經一條鏈路從一個節(jié)點傳輸數據到相鄰節(jié)點的能力

4數據鏈路層與局域網5.1.1鏈路層提供的服務鏈路層功能：將分組通過一個鏈路，從一個節(jié)點傳輸到鄰近的另一個節(jié)點。鏈路層協(xié)議：用來在單段鏈路上傳輸分組。定義了在鏈路兩端的節(jié)點之間交互的分組格式，以及當發(fā)送和接收分組時節(jié)點采取的動作。交換的數據單元稱為幀(frame)，封裝了一個網絡層的數據報。所采取的動作：包括差錯檢測、重傳、流量控制和隨機訪問。典型協(xié)議：以太網、802.11無線LAN、令牌環(huán)和PPP，以及ATM。5數據鏈路層與局域網網絡層與鏈路層關系網絡層：將運輸層報文段從源主機傳送到目的主機。能夠在各段鏈路層提供異構服務的情況下，完成端到端的工作。鏈路層：將網絡層數據報從一個節(jié)點傳送到下一個節(jié)點（單段鏈路）。

不同的鏈路采用不同的鏈路層協(xié)議，提供的服務不同。6數據鏈路層與局域網類比例旅行社組織游客從?？诘焦鹆株査?。經過3段旅程，如圖。游客：數據報；運輸區(qū)段：通信鏈路；運輸方式：鏈路層協(xié)議，如汽車、飛機和船。旅行社：選路協(xié)議。飛機汽車船?？陉査?數據鏈路層與局域網鏈路層提供的服務鏈路層的基本服務是將數據報通過單一通信鏈路從一個節(jié)點移動到相鄰節(jié)點，所提供的服務的服務細節(jié)將隨鏈路層協(xié)議從一種進入下一種而改變；鏈路層可能提供的服務包括：

成幀：把網絡層數據報封裝成鏈路層幀，再傳送到鏈路上。首部包括若干字段：如編號、物理地址等。不同的鏈路層協(xié)議，幀格式可能不同。首部數據報8數據鏈路層與局域網鏈路層提供的服務鏈路接入：由媒體訪問控制(MediumAccessControl,MAC)協(xié)議定義幀在鏈路上傳輸的規(guī)則。點對點鏈路：一個發(fā)送方和一個接收方，MAC協(xié)議比較簡單(或不存在)，即任何時候只要鏈路空閑，發(fā)送方都能夠發(fā)送幀。廣播鏈路：多個節(jié)點共享一個鏈路（多路訪問），使用MAC協(xié)議協(xié)調多個節(jié)點的幀傳輸9數據鏈路層與局域網鏈路層提供的服務可靠交付：保證網絡層的數據報無差錯地通過鏈路層。與運輸層類似，可通過確認和重傳獲得。高差錯率的鏈路：如無線鏈路，在本地(發(fā)生差錯的鏈路)糾正差錯，不通過運輸層或應用層協(xié)議進行端到端的數據重傳；低差錯率的鏈路：如光纖、同軸電纜、雙絞線鏈路，不需提供可靠的傳輸服務。10數據鏈路層與局域網流量控制：防止發(fā)送節(jié)點的發(fā)送速率過高，避免接收節(jié)點來不及處理。鏈路節(jié)點的幀緩存容量有限。

當幀到達接收節(jié)點的速率大于其處理速率，接收方緩沖區(qū)產生溢出，幀會丟失。

鏈路層提供的服務11數據鏈路層與局域網鏈路層提供的服務差錯檢測：幀在傳輸時有可能出現比特差錯（10、01）。差錯檢測用來檢測是否存在一個或多個差錯。

發(fā)送節(jié)點：在幀中設置差錯檢測比特；接收節(jié)點：對收到的幀進行差錯檢測。通過硬件實現。差錯糾正：與差錯檢測類似。接收方不僅能檢測幀中是否出現差錯，還能判斷差錯的位置，并進行糾正。12數據鏈路層與局域網鏈路層提供的服務半雙工和全雙工：全雙工傳輸：鏈路兩端的節(jié)點可以同時傳輸分組。半雙工傳輸：鏈路兩端的節(jié)點不能同時傳輸和接收，只能交替。13數據鏈路層與局域網鏈路層服務和運輸層服務比較運輸層協(xié)議：在端到端的基礎上為兩個進程之間提供可靠傳輸；流量控制是在端到端的基礎上提供。鏈路層協(xié)議：在一條鏈路相連的兩個節(jié)點之間提供可靠傳輸。流量控制是在相鄰節(jié)點之間的基礎上提供。14數據鏈路層與局域網5.1.2鏈路層在何處實現在路由器中鏈路層怎樣實現在線路卡中？主機的鏈路層是用硬件還是軟件實現？它是實現一塊單獨的卡上還是在一個芯片上呢？它是怎樣與主機的硬件和操作系統(tǒng)組件接口的呢？15數據鏈路層與局域網在主機中鏈路層的主體部分是網絡適配器中實現適配器(adapter)：網絡接口卡（NIC，networkinterfacecard），其內核為鏈路層控制器。NIC是一個電路板（或PCMCIA板），包括RAM、DSP芯片、主機總線接口和鏈路接口。實現物理層及鏈路層的主要功能。因此鏈路層控制器的許多功能是用硬件實現的，例如Intel的8254x控制器實現以太網協(xié)議，AtherosAR5006實現802.11WiFi協(xié)議，目前網絡適配器已被綜合進主板------即“LAN在主板”發(fā)送節(jié)點幀接收節(jié)點數據報幀適配器適配器鏈路層協(xié)議將數據報封裝在幀中增加差錯檢測比特，可靠數據傳輸，流量控制,等查找差錯，可靠數據傳輸，流量控制,等提取數據報，傳遞到接收節(jié)點16數據鏈路層與局域網EDC=差錯檢測和糾錯比特(冗余)數據由差錯校驗保護，可能包括首部字段

差錯檢測不是100%可靠!

協(xié)議可能漏掉某些差錯，但是非常少

較大的EDC字段產生更好的檢測和糾正5.2差錯檢測技術17數據鏈路層與局域網奇偶校驗單比特奇偶校驗:檢測單個比特差錯二維比特奇偶校驗:檢測和糾正單個比特差錯00奇偶比特奇偶差錯奇偶差錯可糾正的單比特差錯無差錯18數據鏈路層與局域網互聯(lián)網檢查和發(fā)送方:將段內容作為16比特整數序列來處理檢查和:段內容相加(補碼和)發(fā)送方將檢查和的值放入UDP檢查和字段接收方:計算接收到段的檢查和檢查是否計算的檢查和等于

檢查和字段的值:NO–檢測到差錯YES–沒有檢測到差錯.盡管如此，還可能有錯。詳情見后….目標：檢測傳輸段中的“差錯”(如比特翻轉)(注意:僅用于運輸層)19數據鏈路層與局域網檢查和:循環(huán)冗余碼校驗將數據比特D看作一個二進制數選擇r+1比特模式(生成式),G

目標：選擇r個CRC比特R,使得<D,R>被G整除(以2為模)接收方知道G,用G除以<D,R>.如果有非零余數：檢測到差錯!能夠檢測所有小于r+1比特的突發(fā)差錯廣泛用于實踐中(ATM,HDCL)比特模式數學公式被發(fā)送的數據比特20數據鏈路層與局域網第5章鏈路層5.1概述與服務5.2差錯檢測和糾錯5.3多路訪問協(xié)議5.4鏈路層編址5.5以太網5.6集線器和交換機5.7PPP5.8鏈路虛擬化:ATM和MPLS21數據鏈路層與局域網兩類“鏈路”:點對點用于撥號接入的PPP在以太網交換機和主機之間的點對點鏈路廣播

(共享線路或媒體)傳統(tǒng)的以太網向上游的HFC802.11無線LAN5.2多路訪問協(xié)議22數據鏈路層與局域網廣播信道要解決問題傳統(tǒng)的廣播電視：是單向的廣播，一個固定的節(jié)點向許多接收節(jié)點發(fā)送。計算機網絡：廣播信道上的節(jié)點都能夠發(fā)送和接收。好比許多人聚集在一起交談（空氣是廣播媒體）。解決“誰在什么時候獲得說話權力”(向信道發(fā)送)。

多路訪問問題：如何協(xié)調多個發(fā)送和接收節(jié)點對共享廣播信道的訪問。相關技術是多路訪問協(xié)議。23數據鏈路層與局域網多路訪問協(xié)議目的：協(xié)調多個節(jié)點在共享廣播信道上的傳輸。避免多個節(jié)點同時使用信道，發(fā)生沖突（碰撞），產生互相干擾。沖突（collide）：兩個以上的節(jié)點同時傳輸幀，使接收方收不到正確的幀（所有沖突的幀都受損丟失）。造成廣播信道時間的浪費。

多路訪問協(xié)議可用于許多不同的網絡環(huán)境，如有線和無線局域網、衛(wèi)星網等。如圖5-9。24數據鏈路層與局域網25數據鏈路層與局域網多路訪問協(xié)議類型（三類）信道劃分協(xié)議把信道劃分為小“片”(時隙)給節(jié)點分配專用的小“片”隨機訪問協(xié)議不劃分信道，允許沖突能從沖突中“恢復”輪流協(xié)議通過輪流訪問信道避免沖突，要發(fā)送的節(jié)點越多輪流時間越長26數據鏈路層與局域網多路訪問協(xié)議的理想特性設廣播信道的速率為Rb/s只有一個節(jié)點發(fā)送數據時：該節(jié)點的吞吐量為R

b/s有M個節(jié)點發(fā)送數據時：每個節(jié)點吞吐量為R/M

b/s；協(xié)議是分散的：不會因為主節(jié)點故障而癱瘓協(xié)議是簡單的：實現方便、價格適中。27數據鏈路層與局域網5.3.1信道劃分協(xié)議主要有TDM、FDM、CDMA三種。設信道支持N個節(jié)點，傳輸速率是Rb/s。

時分多路復用(TDM)：將時間劃分為時間幀，每個時間幀再劃分為N個時隙（長度保證發(fā)送一個分組），分別分配給N個節(jié)點。每個節(jié)點只在固定分配的時隙中傳輸。例：6個站點的LAN,時隙1、3、4有分組,時隙2、5、6空閑28數據鏈路層與局域網TDM特點避免沖突、公平：每個節(jié)點專用速率R/N

b/s。節(jié)點速率有限：R/N

b/s；效率不高：節(jié)點必須等待它的傳輸時隙。29數據鏈路層與局域網

頻分多路復用(FDM)：將總信道帶寬Rb/s劃分為N個較小信道（頻段，帶寬為R/N），分別分配給N個節(jié)點。例：6個站點的LAN,頻帶1、3、4有分組,頻帶2、5、6空閑frequencybandstime

特點：與TDM類似。

避免沖突、公平：N個節(jié)點公平劃分帶寬；

節(jié)點帶寬有限、效率不高：節(jié)點帶寬為R/N。30數據鏈路層與局域網碼分多址CDMA(codedivisionmultipleaccess)基本思想：給每個節(jié)點分配一個不同的代碼（CDMA代碼，碼片序列）；每個節(jié)點用惟一的代碼對要發(fā)送的數據進行編碼；不同節(jié)點可以同時發(fā)送，并正確到達接收方（不會互相干擾）。最初：用于軍事通信，抗干擾能力強；目前：用于移動通信、無線多路訪問信道等。31數據鏈路層與局域網5.3.2隨機訪問協(xié)議基本思想：發(fā)送節(jié)點以信道全部速率（R

b/s）發(fā)送；發(fā)生沖突時，沖突的每個節(jié)點分別等待一個隨機時間，再重發(fā)，直到幀(分組)發(fā)送成功。典型隨機訪問協(xié)議：ALOHA協(xié)議載波監(jiān)聽多路訪問CSMA協(xié)議帶沖突檢測載波監(jiān)聽多路訪問CSMA/CD32數據鏈路層與局域網ALOHA

ALOHA：夏威夷大學研制的一個無線電廣播通信網（20世紀70年代初）。采用星型拓撲結構，使地理上分散的用戶通過無線電來使用中心主機。中心主機通過下行信道向二級主機廣播分組；二級主機通過上行信道向中心主機發(fā)送分組（可能會沖突，無線電信道是一個公用信道）。有若干種形式：

時隙ALOHA

純ALOHA中心33數據鏈路層與局域網1、時隙ALOHA假設：所有的幀長L

比特；時間被劃分為若干等長的時隙（長度為一幀的傳輸時間L/Rs）；節(jié)點只在時隙的開始點傳輸幀；所有節(jié)點同步傳輸，知道時隙什么時候開始；如果一個時隙有多個節(jié)點同時傳送，所有節(jié)點都能檢測到沖突34數據鏈路層與局域網時隙ALOHA操作過程：當節(jié)點有新的幀要發(fā)送，需等到下一個時隙開始，才傳輸整個幀。無沖突：節(jié)點成功傳輸幀。有沖突：節(jié)點檢測到沖突后，以概率p在后續(xù)的每一個時隙重傳該幀，直到成功。重傳35數據鏈路層與局域網特點：當只有一個活動節(jié)點（有幀要發(fā)送）時，以全速R連續(xù)傳輸。分散的：每個節(jié)點檢測沖突并獨立決定何時重傳；發(fā)送控制簡單；有多個活動節(jié)點時效率低。36數據鏈路層與局域網效率(efficiency)：當有許多活動節(jié)點時，在發(fā)送的許多幀中，成功時隙的份額。最低效率：沒有任何訪問控制，每個節(jié)點都在沖突之后立即重傳，效率為零。37數據鏈路層與局域網效率計算有三種可能時隙：沖突時隙C：出現幀沖突，被“浪費”?？臻e時隙E：所有活動節(jié)點停止傳輸，被“浪費”。成功時隙S：只有一個節(jié)點在傳輸的時隙。38數據鏈路層與局域網效率計算假設：有N個節(jié)點；每個節(jié)點都有一幀（新幀或重傳幀）要發(fā)送，試圖在每個時隙以概率p傳輸。成功時隙的概率：只有一個節(jié)點傳輸而其他N-1個節(jié)點不傳輸的概率。若一個節(jié)點傳輸的概率是p，剩余的節(jié)點不傳輸的概率是(1-p)N-1。一個給定的節(jié)點成功傳送的概率是p(1-p)N-139數據鏈路層與局域網時隙ALOHA的效率：N個節(jié)點中，任意節(jié)點成功傳送的概率：

N

p(1-p)N-1取極限后，最大效率為：1/e=0.37。即當許多節(jié)點都有很多幀要傳輸時，最多只有37%的時隙在成功傳輸，信道有效的傳輸速率是0.37Rb/s。40數據鏈路層與局域網2、純ALOHAALOHA的最初形式。是一個非時隙、完全分散的協(xié)議。工作過程：節(jié)點有幀要發(fā)，就立即傳輸。如果與其他幀產生沖突，在該沖突幀傳完之后以概率p立即重傳該幀；

或等待一個幀的傳輸時間，再以概率p傳輸該幀，或者以概率1-p等待另一個幀的時間。41數據鏈路層與局域網純ALOHA最大效率：假設：幀傳輸時間為一個時間單元。任何給定時間，一個節(jié)點傳輸一幀的概率是p。節(jié)點i在時間t0開始傳輸幀，如圖5-12所示。結果：在t0發(fā)送的幀會和在

[t0-1,t0+1]的發(fā)送的其它幀沖突與i幀開始部分重疊與i幀結束部分重疊42數據鏈路層與局域網保證幀成功傳輸：在時間間隔[t0

-1，t0]中，不能有其他節(jié)點開始傳輸。

其他節(jié)點沒有開始傳輸的概率是(1-p)N-1當節(jié)點i傳輸時，在時間間隔[t0

，t0+1]中，其他節(jié)點不能開始傳輸。

其他節(jié)點沒有開始傳輸的概率是(1-p)N-1。43數據鏈路層與局域網純ALOHA效率P(給定節(jié)點成功傳送)=P(節(jié)點傳送)·P(沒有其他節(jié)點在[t0-1,t0]內傳送)

·P(沒有其他節(jié)點在[t0,t0+1]內傳送)=p

.(1-p)N-1.(1-p)N-1

=p

.(1-p)2(N-1)

取極限為1/(2e)=0.18。

只有時隙ALOHA協(xié)議的一半。44數據鏈路層與局域網3、CSMA（載波偵聽多路訪問）增加兩個規(guī)則。載波偵聽CS：某個節(jié)點在發(fā)送之前，先監(jiān)聽信道。信道忙：有其他節(jié)點正往信道發(fā)送幀，該節(jié)點隨機等待（回退）一段時間，然后再偵聽信道。信道空：該節(jié)點開始傳輸幀。沖突檢測CD：邊發(fā)送邊監(jiān)聽，即節(jié)點在傳輸同時偵聽信道。如果檢測到有其他節(jié)點正在傳輸幀，發(fā)生沖突，立即停止傳輸，并用某種方法來決定何時再重新傳輸。人類類比:不要打斷他人說話!45數據鏈路層與局域網兩種相應的協(xié)議：載波偵聽多路訪問CSMA（carriersensemultipleaccess）帶沖突檢測的載波偵聽多路訪問CSMA/CD(CSMAwithcollisiondetection)46數據鏈路層與局域網CSMA：只增加“載波偵聽”規(guī)則。也叫“先聽后講”LBT（listenbeforetalk）。基本原理：

傳送前偵聽信道閑：傳送整個幀信道忙：延遲傳送特點：發(fā)前監(jiān)聽，可減少沖突。由于傳播時延的存在，仍有可能出現沖突，并造成信道浪費。47數據鏈路層與局域網例一個廣播總線連接4個節(jié)點(A、B、C、D)傳輸的時空圖。節(jié)點的空間分布

48數據鏈路層與局域網時間t0：節(jié)點B偵聽到信道空，開始傳輸幀，沿著媒體傳播比特。時間t1（t1t0）：節(jié)點D有幀要發(fā)送。B的傳輸信號未到D，D檢測到信道空，開始傳輸。很快，B的傳輸開始在D節(jié)點干擾D的傳輸（沖突）端到端信道傳播時延：信號從一個節(jié)點到另一個節(jié)點所花費的傳播時間。傳播時延越長，節(jié)點不能偵聽到另一個節(jié)點已經開始傳輸的可能性越大。49數據鏈路層與局域網帶來問題：信道浪費

節(jié)點沒有進行沖突檢測，既使發(fā)生了沖突，節(jié)點仍繼續(xù)傳輸它們的幀。但該幀已經被破壞、是無用的幀，信道傳輸時間被浪費。注意：距離與傳播時延對碰撞概率的影響。50數據鏈路層與局域網帶沖突檢測的CSMA(CSMA/CD)：增加“載波偵聽”和“沖突檢測”兩個規(guī)則?！斑呎f邊聽”LWT（listenwhiletalk）?；驹恚?/p>

傳送前偵聽信道忙：延遲傳送信道閑：傳送整個幀發(fā)送同時進行沖突檢測：一旦檢測到沖突就立即停止傳輸，盡快重發(fā)。目的：縮短無效傳送時間，提高信道的利用率。51數據鏈路層與局域網例兩個節(jié)點B、D在檢測到沖突之后很短的時間內都放棄傳輸。以太網即采用CSMA/CD協(xié)議。檢測到沖突放棄傳輸52數據鏈路層與局域網5.3.3輪流協(xié)議多路訪問協(xié)議理想特性：只有一個節(jié)點活動時，吞吐量R

b/s；有M個節(jié)點活動時，吞吐量R/M

b/s。ALOHA和CSMA協(xié)議有第一個特性，但沒有第二個特性。1、輪詢協(xié)議2、令牌傳遞協(xié)議53數據鏈路層與局域網1、輪詢協(xié)議(pollingprotocol)指定一個主節(jié)點，以循環(huán)的方式輪詢每個節(jié)點。并告訴節(jié)點能夠傳輸的最大幀數。輪詢順序：

12……

n

主節(jié)點通過觀察信道上是否有信號來判斷節(jié)點何時完成了幀的發(fā)送，再詢問下一節(jié)點。數據幀主節(jié)點1……2n輪詢幀54數據鏈路層與局域網特點：消除沖突和空時隙，效率高。有輪詢時延：活動節(jié)點不能立即傳輸幀，等待被輪詢；如果主節(jié)點失效，整個信道都不能用。55數據鏈路層與局域網2、令牌傳遞協(xié)議(token-passingprotocol)沒有主節(jié)點。設置一個令牌(token，小的專用幀)；令牌以固定順序循環(huán)傳遞，給節(jié)點傳輸機會。如：12……

n節(jié)點收到令牌：有幀要發(fā)送，傳輸，傳完后將令牌轉發(fā)到下一節(jié)點；否則，直接將令牌轉發(fā)到下一節(jié)點。56數據鏈路層與局域網特點：令牌傳遞是分散的，效率高。一個節(jié)點的失效會使整個信道崩潰。一個節(jié)點忘記釋放令牌，必須恢復令牌到環(huán)中。相應協(xié)議標準：IEEE802.5令牌環(huán)。57數據鏈路層與局域網5.3.4局域網(LAN)LAN：是一個地理范圍小的計算機網絡。計算機網絡的一個分支。特點：地理范圍?。簬坠?。如一棟樓，一所大學。使用多路訪問協(xié)議：如CSMA/CD。數據傳輸速率R高：10Mb/s、100Mb/s、1Gb/s、10Gb/s單位擁有。58數據鏈路層與局域網局域網拓撲結構：59數據鏈路層與局域網應用：范圍廣。典型應用：單位用戶通過LAN接入因特網。用戶主機先組成LAN，LAN通過路由器接入因特網。60數據鏈路層與局域網局域網協(xié)議標準：IEEE802標準系列。IEEE802委員會：美國電氣和電子工程師協(xié)會在1980年2月成立的一個分委員會，專門制訂局域網的相關標準典型標準：IEEE802.3：CSMA/CD以太網。IEEE802.4：令牌總線網。IEEE802.5：令牌環(huán)形網。IEEE802.11：無線局域網。IEEE802.12：新型高速局域網(100Mb/s)。61數據鏈路層與局域網兩種典型LAN技術：隨機訪問技術：以太網LAN（802.3LAN）。令牌傳遞技術：令牌環(huán)（tokenring，IEEE802.5）FDDI（光纖式分布數據接口）。62數據鏈路層與局域網令牌環(huán)N個節(jié)點(主機和路由器)通過直接鏈路連接成一個環(huán)。工作過程：令牌沿環(huán)路順序傳遞。一個節(jié)點有幀要發(fā)，等待“令牌”到達；得到令牌，發(fā)送一個幀，沿著整個環(huán)傳播；到達目的節(jié)點，將其接收（復制），作標記，繼續(xù)傳幀沿環(huán)路循環(huán)一周返回源點，檢查標記傳輸是否成功不成功：重發(fā)該幀；成功：將其從環(huán)中移走（刪除），并傳遞“令牌”。發(fā)送接收63數據鏈路層與局域網光線分布數據接口FDDI：用于地理范圍更大的LAN，如城域網MAN。由目的節(jié)點將收到的幀從環(huán)中移走。FDDI不是純粹的廣播信道，每個節(jié)點并不接收每個傳輸的幀。64數據鏈路層與局域網Q:為什么網絡層和鏈路層都需要地址呢？◆首先應該清楚并不是節(jié)點（主機或路由器）具有MAC地址，而是節(jié)點的適配器具有鏈路層地址，我們把LAN地址叫做物理地址或MAC地址◆以太網和802.11無線LAN的MAC地址長6字節(jié)，共有2^48個可能的LAN地址，通常用十六進制表示，每個字節(jié)表示為一對十六進制數；◆盡管MAC地址被設計為永久的，但現在用軟件是可以修改的；5.4鏈路層編址65數據鏈路層與局域網MAC地址的一個有趣性質是全球每家廠商生產的適配器都不會具有相同地址，原因是IEEE在管理MAC地址空間；廣播地址：FF-FF-FF-FF-FF-FF。5.4.1MAC地址1A-2F-BB-76-09-AD71-65-F7-2B-08-53字節(jié)向IEEE購買廠家自行分配12345666數據鏈路層與局域網MAC地址識別：廣播信道LAN中，一個節(jié)點發(fā)送的幀，在信道上廣播傳輸，其他節(jié)點都可能收到該幀。大多數情況，一個節(jié)點只向某個特定的節(jié)點發(fā)送。由“網卡”負責MAC地址的封裝和識別。發(fā)送適配器：將目的MAC地址封裝到幀中，并發(fā)送。所有其他適配器都會收到這個幀。

接收適配器：檢查幀的目的MAC地址是否與自己MAC地址相匹配：

匹配：接收該幀，取出數據報，并傳遞給上層。

不匹配：丟棄該幀。67數據鏈路層與局域網應用層有主機名、網絡層有IP地址和鏈路層有MAC地址，所以需要它們之間進行轉換，對于因特網而言，這是地址解析協(xié)議（ARP）；為了理解ARP之類的協(xié)議我們看下面的這個例子：5.4.2地址解析協(xié)議1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-98

LAN237.196.7.23237.196.7.78237.196.7.14237.196.7.8871-65-F7-2B-08-53AB那么源主機是怎么獲得目的主機的MAC地址？ARP68數據鏈路層與局域網地址之間的轉換通信時，需要進行地址轉換：

主機名

IP地址

MAC地址DNS域名系統(tǒng)：將主機名解析到IP地址。DNS為在因特網中任何地方的主機解析主機名。ARP地址解析協(xié)議：將IP地址解析到MAC地址。ARP只為在同一個LAN上的節(jié)點解析IP地址。69數據鏈路層與局域網地址轉換問題兩臺機器A和B,它們IP地址分別是IA、IB，物理地址分別是PA和PB高層程序僅希望與IP地址交往，而實際通信必須使用物理地址IP4IAPAHA4HA3HA2HA5PBIP5ABIP2R1R2以太網2以太網1FDDI網IP層上的互聯(lián)網IP數據報MAC幀IBIP3IP1IP6IP1IP6IP1IP6MAC幀MAC幀問題：A如何從B的IP地址得到它的物理地址PB？70數據鏈路層與局域網ARP:地址解析協(xié)議LAN上的每個IP節(jié)點(主機、路由器)都有ARP表ARP表:對LAN節(jié)點的IP/MAC地址映射

<IP地址;MAC地址;TTL>

TTL(壽命):地址映射將被忘記的時間長度(通常20分鐘)問題:已知B的IP地址怎樣決定B的MAC地址?1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53

LAN237.196.7.23237.196.7.78237.196.7.14237.196.7.8871數據鏈路層與局域網ARP協(xié)議:相同的LAN(網絡)A要向B發(fā)送數據報,并且B的MAC地址不在A的ARP表中.A廣播ARP請求分組,包含B的IP地址目的地MAC地址=FF-FF-FF-FF-FF-FF在LAN上的所有機器接收ARP請求B接收ARP分組，用它的MAC地址回答A幀發(fā)送到A的MAC地址(單播)A在它的ARP表中緩存(保存)IP到MAC的地址對，直到信息變得超時ARP是“即插即用”:節(jié)點創(chuàng)建它們的ARP表無需網絡管理員干預72數據鏈路層與局域網選路到另一個LAN目的:從A到B經R發(fā)送數據報

假定A知道B的IP地址在路由器R中有兩個ARP表,每張表對應一個IP網絡(LAN)ARB73數據鏈路層與局域網A生成具有源A、目的地B的數據報A使用ARP從111.111.111.110得到R的MAC地址A生成以R的MAC地址作為目的地的鏈路層幀,幀包含A-to-BIP數據報A的適配器發(fā)送幀B的適配器接收幀R從以太網幀取出IP數據報，看到它目的地是BR使用ARP得到B的MAC地址R生成包含A-to-BIP數據報的幀向B發(fā)送ARB74數據鏈路層與局域網◆以太網幾乎完全占領著現有的有線局域網市場。在20世紀80年代末和90年代早期，以太網面臨著來自其他LAN技術包括令牌環(huán)、FDDI和ATM的挑戰(zhàn)，這些技術也成功的抓住了部分LAN市場份額?！舻亲?0世紀70年代以來以太網不斷地更新技術，始終保持了LAN的支配地位，成為迄今為止最流行的有線局域網技術；◆以太網成功的因素很多，可以總結為：高速LAN、便捷（相對于令牌環(huán)、FDDI等）、設備便宜；◆21世紀前期以太網經歷了一次變革，位于網絡中心的集線器被交換機所取代；5.5以太網75數據鏈路層與局域網◆通過研究以太網的幀，我們能夠學習很多以太網的知識。為了將對以太網幀的討論放到切實可行的環(huán)境中，考慮從一臺主機向另外一臺主機發(fā)送一個IP數據報，且這兩臺主機在相同的以太網LAN上?！艏僭O發(fā)送適配器的MAC地址是AA-AA-AA-AA-AA-AA，接受適配器的MAC地址為BB-BB-BB-BB-BB-BB，發(fā)送適配器在一個以太網幀中封裝一個IP數據報，并把該幀傳遞到物理層。接受適配器從物理層接收到這個幀，提取IP數據報，并傳遞給網絡層；◆現在我們來看一下以太網幀的6個字段；5.5.1以太網幀結構76數據鏈路層與局域網1、以太網的幀結構CRC檢測范圍字節(jié)866246～15004前同步碼 目的地址 源地址類型數據CRC數據字段(46～1500字節(jié))：攜帶網絡層傳來的IP數據報。以太網的最大傳輸單元MTU是1500字節(jié)：若IP數據報超過1500字節(jié)，必須將該數據報分段。最小長度是46字節(jié)：如果IP數據報小于46字節(jié)，必須填充為46字節(jié)。接收方網絡層去除填充內容。77數據鏈路層與局域網目的地址(6字節(jié))：目的適配器的MAC地址。如主機B的地址：BB-BB-BB-BB-BB-BB。適配器B只接收目的地址與其MAC地址匹配或廣播地址的幀，并將數據字段的內容傳遞給網絡層。否則，丟棄該幀。字節(jié)866246～15004前同步碼 目的地址 源地址類型數據CRC78數據鏈路層與局域網源地址(6字節(jié))：發(fā)送適配器的MAC地址。如主機A的地址：AA-AA-AA-AA-AA-AA。字節(jié)866246～15004前同步碼 目的地址 源地址類型數據CRC79數據鏈路層與局域網類型字段(2字節(jié))：以太網可以“多路復用”（支持）多種網絡層協(xié)議。通過“類型”字段區(qū)分。發(fā)送方填入網絡層協(xié)議“類型”編號（復用）；接收適配器根據“類型”字段，將數據字段傳遞給相應的網絡層協(xié)議（分解）。字節(jié)866246～15004前同步碼 目的地址 源地址類型數據CRC80數據鏈路層與局域網循環(huán)冗余檢測CRC(4字節(jié))檢測幀中是否出現比特差錯（翻轉）。發(fā)送主機計算CRC：范圍包括目的地址、源地址、類型、數據字段的比特，結果放入幀CRC字段。接收主機進行CRC校驗：接收主機對收到的幀進行同樣計算，并校驗結果是否和CRC字段的內容相等。若計算結果不等于CRC字段的值(CRC校驗失敗)，該幀有差錯。字節(jié)866246～15004前同步碼 目的地址 源地址類型數據CRC81數據鏈路層與局域網前同步碼(8字節(jié))：前7字節(jié)是“10101010”，最后一個字節(jié)是“10101011”。使接收方和發(fā)送方的時鐘同步，接收方一旦收到連續(xù)的8字節(jié)前同步碼，可確定有幀傳過來。前同步碼是“無效信號”，接收方收到后刪除，不向上層傳。CRC的校驗范圍不包括前同步碼。82數據鏈路層與局域網2、基帶傳輸和曼徹斯特編碼基帶傳輸：適配器直接給廣播信道發(fā)送數字信號。寬帶傳輸：將信號調制到特定頻帶傳輸。數字信號編碼類型：不歸零編碼曼徹斯特編碼差分曼徹斯特編碼83數據鏈路層與局域網不歸零編碼直接用原始基帶數字信號傳。采用兩種不同電平，如：“1”--高電平；“0”--低電平

問題：出現一連串“1”或“0”時，接收方無法確定一位的開始和結束。即收發(fā)不能同步。一般不直接用。84數據鏈路層與局域網曼徹斯特編碼每位信號的中間都有一個跳變，兩個作用：表示數據：根據跳變方向判斷數據“1”或“0”，如：“1”--高電平跳到低電平；“0”--低電平變到高電平做同步時鐘：接收方根據跳變來同步接收。85數據鏈路層與局域網差分曼徹斯特編碼每位信號的中間都有一個跳變，只做時鐘，不表示數據數據表示：根據每位開始處是否有跳變，來判斷數據“1”或“0”。如：

“1”--無跳變；“0”--有跳變較好的抗干擾性能，復雜。信號編碼屬于物理層86數據鏈路層與局域網3、不可靠的無連接服務以太網向網絡層提供的服務。無連接服務：通信時，發(fā)送方適配器不需要先和接收方適配器“握手”。不可靠的服務：接收到的幀可能包含比特差錯。收到正確幀，不發(fā)確認幀；收到出錯幀，丟棄該幀，不發(fā)否定幀。發(fā)送適配器不會重發(fā)出錯幀，傳遞到接收方網絡層的數據報流可能有間隙。需要高層做相應處理。87數據鏈路層與局域網◆當一個節(jié)點通過某集線器互聯(lián)時，該以太LAN是一個真正的廣播LAN，即當某適配器傳輸一幀時，LAN上的所有適配器都會收到該幀，由于這種廣播特性，以太網需要多路訪問協(xié)議-----CSMA/CD?！粼谠搮f(xié)議下適配器可以任意的時刻傳輸---沒有時隙；◆適配器監(jiān)聽到鏈路再被其他適配器使用時，絕不會傳輸幀---載波監(jiān)聽；◆如果在傳輸過程中檢測到另一適配器正在傳輸，立刻終止---碰撞檢測；◆嘗試重傳前，等待一個隨機時間；◆適配器通過檢測電壓水平，實現監(jiān)聽和碰撞檢測；5.5.2以太網使用CSMA/CD88數據鏈路層與局域網以太網CSMA/CD算法1.適配器從網絡層接收數據報并生成幀2.如果適配器感知信道空閑，它開始傳輸幀.如果它感知信道忙，等待信道空閑再傳輸3.如果適配器傳輸整個幀而不檢測另一個傳輸，該適配器已經處理完幀!4.如果適配器傳輸過程中檢測到另一次傳輸,中止并發(fā)送強化沖突信號5.中止后,適配器進入指數回退:在第m次碰撞后,適配器隨機地從{0,1,2,…,2m-1}選擇一個K值。適配器等待K?512比特時間并返回到第二步89數據鏈路層與局域網以太網的CSMA/CD(續(xù))強化沖突信號:

確保所有的其他傳輸方都知道碰撞;48bit比特時間:

對10Mbps以太網是0.1μs;對K=1023,等待時間約為50msec

指數回退:

目標：估計當前負載，適應重傳嘗試重負載:隨機等待將更長首次碰撞:從{0,1}中選擇K；時延是K?512bit傳輸時間第二次碰撞后:從{0,1,2,3選擇K10次碰撞后,從{0,1,2,3,4,…,1023}選擇K為什么不采用一個小集合來選擇k值？例如{0,1,2,3,4,5,6,7}90數據鏈路層與局域網CSMA/CD效率Tprop=LAN中的2站點之間的最大傳播時間ttrans=傳輸最長幀的時間隨著tprop

趨于0,效率趨于1隨著ttrans

趨于無窮大，效率趨于1比ALOHA好得多,而且簡單

效率↑隨著a=tprop/ttrans↓asttrans↑91數據鏈路層與局域網◆以太網是一個單一的的協(xié)議標準，但以太網協(xié)議有很多類型和眼花繚亂的首字母縮寫，例如10BASE-T、100BASE-2、100BASE-T、10GBASE-T等，目前已被802.3標準化。◆首字母縮寫的第一個部分指該標準的速率，“BASE”指基帶以太網，幾乎所有的以太網都是基帶網，字母的最后一部分指物理媒體，例如“T”指雙絞線；5.5.3以太網技術twistedpair集線器92數據鏈路層與局域網集線器集線器基本上是物理層中繼器:來自一條鏈路的比特從其他所有鏈路出去以相同的速率無幀緩存在集線器中無CSMA/CD:適配器檢測碰撞提供網絡管理功能雙絞線集線器93數據鏈路層與局域網Gbit以太網吉比特以太網的標準稱為802.3z使用標準以太網幀格式允許點對點鏈路和共享的廣播信道在共享模式中,使用CSMA/CD;在需要高效率的節(jié)點之間采用近距離使用集線器,這里稱為“緩存分配器”1Gbps全雙工技術用于點對點鏈路現在已達10Gbps!

a=tprop/ttrans↑asttrans

↓94數據鏈路層與局域網◆現代以太網使用了一種星型拓撲，每個節(jié)點與中心交換機相連?！艚粨Q機的任務是接收鏈路層幀并將它們轉發(fā)到出鏈路；◆我們不是已經擁有集線器了嗎，為什么要用交換機？5.5.4鏈路層交換機集線器集線器集線器集線器95數據鏈路層與局域網5.5.4鏈路層交換機鏈路層設備存儲并轉發(fā)以太網幀檢查幀首部并基于MAC目的地址選擇性地轉發(fā)幀當幀在網段上轉發(fā)時，使用CSMA/CD訪問網段透明主機不知道交換機的存在即插即用,自學習交換機不必配置96數據鏈路層與局域網交換機兩層設備存儲并轉發(fā)以太網幀檢查幀首部并基于MAC目的地址選擇性地轉發(fā)幀當幀在網段上轉發(fā)時，使用CSMA/CD訪問網段透明主機不知道交換機的存在即插即用,自學習交換機不必配置下面我們學習交換機的工作原理97數據鏈路層與局域網轉發(fā)

怎樣決定向哪個LAN段上轉發(fā)幀呢?

看起來像選路問題...集線器集線器集線器交換機12398數據鏈路層與局域網假設節(jié)點向DD-DD-DD-DD-DD-DD地址發(fā)送，首先交換機會索引MAC地址表項，出現三種情況表中沒有該地址，廣播該幀；表中該項，但該地址屬于該LAN，所以過濾表中該項，但該地址步不屬于該LAN，轉發(fā)但是一開始這個交換機的表是如何配置起來的？鏈路層有與網絡層選路協(xié)議等價的協(xié)議嗎？或者必須通過管理員來配置該交換表？99數據鏈路層與局域網過濾/轉發(fā)當交換機收到1幀:

使用MAC目的地址索引交換機表if找到目的地項

then{if目的地位于幀到達的段

then

丟棄幀

else在指示的接口轉發(fā)該幀

}

else

洪泛

向所有接口(除了該幀到達的)轉發(fā)該幀100數據鏈路層與局域網自學習交換機具有令人驚奇的特性，那就是他的表是自動的、動態(tài)的、自治的建立，沒有任何人員干預，換句話說交換機具有自學習的能力，這種能力通過如下方式實現：一個交換機具有一個交換機表，初始為空對于某接口接收到的每個幀，該交換機在其表中儲存:該幀的MAC地址,到達的接口,時戳)知道了該發(fā)送節(jié)點的網段；表中的陳舊項丟棄

；交換機知道通過哪個接口能夠到達哪臺主機當幀收到,交換機“得知”發(fā)送方的位置:入LAN段在交換機中記錄了發(fā)送方/位置對101數據鏈路層與局域網交換機例子假定C向D發(fā)送幀交換機從C接收幀注意到C位于接口1因為D不在表中,交換機將向接口2和3轉發(fā)幀D接收幀集線器集線器集線器交換機ABCDEFGHI地址接口ABEG1123123102數據鏈路層與局域網交換機例子假定D回答C的幀交換機從D接收幀注意到在交換機表中D位于接口2因為C在表中,交換機僅向接口1轉發(fā)幀C接收幀集線器集線器集線器交換機ABCDEFGHI地址接口ABEGC11231103數據鏈路層與局域網交換機:流量隔離交換機安裝將子網分割成LAN段交換機過濾分組:

相同LAN段的幀通常不在其他LAN段上轉發(fā)段成為分離的碰撞域集線器集線器集線器交換機碰撞域碰撞域碰撞域104數據鏈路層與局域網交換機:專門的訪問交換機具有許多接口主機到交換機有直接的連接無碰撞;全雙工交換機:A到A’同時和B到B’，無碰撞交換機AA’BB’CC’105數據鏈路層與局域網交換機的其他信息直通交換:幀從輸入端口到輸出端口無需先收集整個幀少量地減少了時延共享/專用的結合,10/100/1000Mbps接口106數據鏈路層與局域網機構網絡集線器集線器集線器交換機到外部網絡路由器IP子網相同的廣播域郵件服務器Web服務器107數據鏈路層與局域網交換機vs.路由器兩者都是存儲轉發(fā)設備路由器:網絡層設備(檢查網絡層首部)交換機是鏈路層設備路由器維護選路表，實現選路算法交換機維護交換機表,實現過濾、學習算法108數據鏈路層與局域網對比小結集線器 路由器交換機流量隔離noyesyes即插即用yesnoyes優(yōu)化選路noyesno直通nonoyes隔離廣播noyesno109數據鏈路層與局域網第5章鏈路層5.1概述與服務5.2差錯檢測和糾錯5.3多路訪問協(xié)議5.4鏈路層編址5.5以太網5.6集線器和交換機5.7PPP5.8鏈路虛擬化:ATM和MPLS110數據鏈路層與局域網點對點鏈路層控制一個發(fā)送方、一個接收方、一段鏈路：比廣播鏈路容易處理:無媒體訪問控制不需要明確的MAC編制如撥號鏈路、ISDN鏈路流行的點對點DLC協(xié)議:PPP(point-to-point協(xié)議)HDLC:高級數據鏈路控制(數據鏈路過去被認為位于協(xié)議棧的“高層”!111數據鏈路層與局域網PPP設計要求[RFC1557]分組成幀:

在數據鏈路幀中封裝網絡層數據報在相同時間承載任何網絡層協(xié)議(不止是IP)的網絡層數據向上分解的能力比特透明性:

在數據字段必須承載任何比特模式差錯檢測

(不糾正)連接活躍性:

對網絡層檢測、通知鏈路故障網絡層地址協(xié)商:

端點能學習/配置每個其他網絡地址112數據鏈路層與局域網PPP不要求無糾錯/恢復無流量控制允許失序交付不必支持多點鏈路(如輪詢)差錯恢復,流量控制,數據重排序所有都移交到較高層!113數據鏈路層與局域網PPP數據幀標志:

定界符(成幀)地址:

不起作用(僅是一個選項)控制:不起作用;以后可能多控制字段協(xié)議:

該幀交付的高層協(xié)議(如PPP-LCP,IP,IPCP等)可變長度標志標志控制地址協(xié)議信息校驗114數據鏈路層與局域網PPP數據幀信息:

高層承載的數據校驗:

對差錯檢測的冗余循環(huán)校驗可變長度標志標志控制地址協(xié)議信息校驗115數據鏈路層與局域網比特填充

“數據透明性”要求:數據字段必須允許包括標志模式<01111110>問題:

收到的<01111110>是數據還是標志？發(fā)送方:

增加(“填充”)額外的<01111101>字節(jié)在每個<01111110>數據字節(jié)接收方:

在一排中出現0111110101111110:丟棄第一個字節(jié),繼續(xù)數據接收單個01111110:標志字節(jié)116數據鏈路層與局域網比特填充flagbytepatternindatatosend在傳輸數據中標志字節(jié)模式加上填充字節(jié)117數據鏈路層與局域網PPP數據控制協(xié)議在交換網絡層數據前，數據鏈路對等方必須配置PPP鏈路(最大的幀長度，鑒別)得知/配置網絡

層信息對IP:承載IP控制協(xié)議(IPCP)報文(協(xié)議字段:8021)以配置/得知IP地址118數據鏈路層與局域網第5章鏈路層5.1概述與服務5.2差錯檢測和糾錯5.3多路訪問協(xié)議5.4鏈路層編址5.5以太網5.6集線器和交換機5.7PPP5.8鏈路虛擬化:ATM和MPLS119數據鏈路層與局域網網絡的虛擬化資源的虛擬化:在系統(tǒng)工程中一種強有力的抽象:計算例子：虛擬內存，虛擬設備虛擬機器:如java1960’s/70’s的IBMVM操作系統(tǒng)層次抽象：不必關心較低層的細節(jié)，僅抽象地處理較低層120數據鏈路層與局域網因特網:虛擬化的網絡1974:多個不連接的網絡ARPAnet電纜上傳數據的網絡分組衛(wèi)星網絡(Aloha)分組無線電網絡…不同的方面:編制規(guī)則分組格式差錯恢復選路ARPAnet衛(wèi)星網絡“對分組網絡互聯(lián)的協(xié)議",V.Cerf,R.Kahn,IEEETransactionsonCommunications,May,1974,pp.637-648.121數據鏈路層與局域網因特網:虛擬化的網絡ARPAnet衛(wèi)星網絡網關網際層(IP):編址:互聯(lián)網絡看起來像單個、統(tǒng)一的實體，盡管下面的本地網絡是異構的網絡的網絡網關:“在本地的分組格式中嵌入互聯(lián)網分組或提取分組”(在互聯(lián)網級)選路到下一個網關122數據鏈路層與局域網Cerf和Kahn的因特網體系結構什么是虛擬化?兩層編址:互聯(lián)網和本地網絡網絡層(IP)使得互聯(lián)網層的一切都是同類的下面的本地網絡技術電纜衛(wèi)星56K電話調制解調器今天:ATM,MPLS…在互聯(lián)網層“不可見”.對IP看起來像鏈路層技術!123數據鏈路層與局域網ATM和MPLSATM,MPLS憑本身的頭銜分割了網絡不同于因特網的服務模型，編址和選路因特網視為連接IP路由器的邏輯鏈路就像撥號鏈路實際上是分離網絡(電話網)的部分ATM,MPSL:憑本身的頭銜的技術特性124數據鏈路層與局域網異步傳遞方式:ATM1990’s/00高速的標準(155Mbpsto622Mbps及更高)寬帶綜合業(yè)務數字網體系結構目標：

綜合的、承載話音、視頻和數據的端到端傳輸滿足話音、視頻的定時/QoS要求(對比因特網盡力而為模型)“下一代”電話：扎根在電話界的技術使用虛電路分組交換機(固定長度分組，稱為“信元”)125數據鏈路層與局域網ATM體系結構適配層:

僅在ATM網絡的邊緣數據分段/重裝大致類比于因特網運輸層ATM層:“網絡層”信元交換機,選路物理層126數據鏈路層與局域網ATM:網絡或鏈路層?印象:

端到端傳輸:“ATM從桌面到桌面”ATM是一種網絡技術事實:

用于連接IP主干路由器“在ATM上傳IP”ATM作為交換的

鏈路層,連接IP路由器ATM網絡IP網絡127數據鏈路層與局域網ATM適配層(AAL)ATM適配層(AAL):“適配”較高層(IP或純粹的ATM應用程序)到下面的ATM層AAL僅存在端系統(tǒng)中，不在交換機中AAL層段(首部/尾部字段,數據)根據多個ATM單元分段類比:在多個IP分組中的TCP段128數據鏈路層與局域網ATM適配層(AAL)(續(xù))AAL層的不同版本，取決于ATM服務類型:AAL1:

對CBR(恒定比特率)服務,如電路仿真AAL2:

對VBR(可變比特率)服務,如MPEG視頻AAL5:

對數據(如IP數據報)AALP