第二講+鏈路層A

第2講數(shù)據(jù)鏈路層之一2a-1第2講:數(shù)據(jù)鏈路層本講目標(biāo):

了解數(shù)據(jù)鏈路層服務(wù)原理:可靠數(shù)據(jù)傳輸,流量控制錯誤檢測,校正共享廣播信道鏈路層編址各類鏈路層技術(shù)的實現(xiàn)和實例教科書參考第4、5、6章概述:鏈路層的服務(wù)可靠數(shù)據(jù)傳輸,流量控制錯誤檢測,校正多點訪問技術(shù)和LAN鏈路層尋址,ARP特定的鏈路層技術(shù):以太網(wǎng)集線器,網(wǎng)橋,交換機(jī)第2講數(shù)據(jù)鏈路層之一2a-2數(shù)據(jù)鏈路層的基本概念鏈路(link)是一條無源的點到點的物理線路段，中間沒有任何其他的交換結(jié)點。一條鏈路只是一條通路的一個組成部分。數(shù)據(jù)鏈路(datalink)

除了物理線路外，還必須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路。第2講數(shù)據(jù)鏈路層之一2a-3鏈路層:工作環(huán)境兩個物理上連接的設(shè)備:主機(jī)-路由器,路由器-路由器,主機(jī)-主機(jī)第2講數(shù)據(jù)鏈路層之一2a-4鏈路層:工作環(huán)境常常在兩個對等的數(shù)據(jù)鏈路層之間畫出一個數(shù)字管道，在這條數(shù)字管道上傳輸?shù)臄?shù)據(jù)單位是frame（幀）applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframe物理鏈路數(shù)據(jù)鏈路協(xié)議接口卡結(jié)點結(jié)點幀幀第2講數(shù)據(jù)鏈路層之一2a-5鏈路層的服務(wù)成幀,鏈路訪問:

將分組封裝入幀,加上幀頭,幀尾如果是共享介質(zhì)，則需實現(xiàn)信道的訪問,‘物理地址’放在幀首用來確定信源、信宿

不同于IP地址喔!在兩臺物理上連接的設(shè)備之間實現(xiàn)可靠傳遞:

可靠傳遞是什么概念，回顧一下學(xué)過的知識!不太用在誤碼率低的場合(光纖,某些雙絞線)無線鏈路:誤碼率相當(dāng)高第2講數(shù)據(jù)鏈路層之一2a-6鏈路層的服務(wù)(續(xù))流量控制:

保持收發(fā)雙方的同步錯誤檢測:

信號衰減和噪聲會導(dǎo)致出錯.接收端檢測到錯誤時:給發(fā)送端信號要求重發(fā)或丟棄出錯幀

錯誤校正:

接受端檢測多個位錯并加以校正而無需要求發(fā)送端重發(fā)第2講數(shù)據(jù)鏈路層之一2a-7鏈路層:實現(xiàn)通過“adapter（網(wǎng)卡或適配器）”實現(xiàn)e.g.,PCMCIA卡,以太網(wǎng)卡一般適配器都含有:RAM,DSP芯片,主機(jī)的總線接口,和鏈路接口applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframephys.linkdatalinkprotocoladaptercard第2講數(shù)據(jù)鏈路層之一2a-8停止等待協(xié)議數(shù)據(jù)鏈路層主機(jī)

A緩存主機(jī)

B數(shù)據(jù)鏈路AP2AP1緩存發(fā)送方接收方幀高層幀完全理想化的數(shù)據(jù)傳輸假定1：鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會出差錯也不會丟失。假定2：不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來得及收下，并及時上交主機(jī)。這個假定就相當(dāng)于認(rèn)為：接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不會低于發(fā)送端發(fā)送數(shù)據(jù)的速率。第2講數(shù)據(jù)鏈路層之一2a-9voidsender1(void){frames;/*bufferforanoutboundframe*/packetbuffer;/*bufferforanoutboundpacket*/while(true){from_network_layer(&buffer);/*gogetsomethingtosend*/=buffer;/*copyitintosfortransmission*/to_physical_layer(&s);/*senditonitsway*/}/*Tomorrow,andtomorrow,andtomorrow,Creepsinthispettypacefromdaytoday}Tothelastsyllableofrecordedtime*/voidreceiver1(void){framer;event_typeevent;/*filledinbywait,butnotusedhere*/while(true){wait_for_event(&event);/*onlypossibilityisframe_arrival*/from_physical_layer(&r);/*gogettheinboundframe*/to_network_layer(&);/*passthedatatothenetworklayer*/}}完全理想化的數(shù)據(jù)傳輸?shù)?講數(shù)據(jù)鏈路層之一2a-102.具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議現(xiàn)在去掉上述的第二個假定。但是，仍然保留第一個假定，即主機(jī)A向主機(jī)B傳輸數(shù)據(jù)的信道仍然是無差錯的理想信道。然而現(xiàn)在不能保證接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不低于發(fā)送端發(fā)送數(shù)據(jù)的速率。流量控制策略：處理發(fā)送方的傳送能力比接收方接收能力大的問題?；诜答仚C(jī)制/交由傳輸層實現(xiàn)由收方控制發(fā)方的數(shù)據(jù)流，乃是計算機(jī)網(wǎng)絡(luò)中流量控制的一個基本方法。第2講數(shù)據(jù)鏈路層之一2a-112.具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議算法在發(fā)送結(jié)點：

(1)從主機(jī)取一個數(shù)據(jù)幀。

(2)將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。

(3)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。

(4)等待。

(5)若收到由接收結(jié)點發(fā)過來的信息(此信息的格式與內(nèi)容可由雙方事先商定好)，則從主機(jī)取一個新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)。第2講數(shù)據(jù)鏈路層之一2a-122.具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議算法（續(xù)）在接收結(jié)點：

(1)等待。

(2)若收到由發(fā)送結(jié)點發(fā)過來的數(shù)據(jù)幀，則將其放入數(shù)據(jù)鏈路層的接收緩存。

(3)將接收緩存中的數(shù)據(jù)幀上交主機(jī)。

(4)向發(fā)送結(jié)點發(fā)一信息，表示數(shù)據(jù)幀已經(jīng)上交給主機(jī)。

(5)轉(zhuǎn)到(1)。第2講數(shù)據(jù)鏈路層之一2a-13流程分析在發(fā)送結(jié)點：

(1)從主機(jī)取一個數(shù)據(jù)幀。

(2)將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。

(3)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。

(4)等待。

(5)若收到由接收結(jié)點發(fā)過來的信息(此信息的格式與內(nèi)容可由雙方事先商定好)，則從主機(jī)取一個新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)在接收結(jié)點：

(1)等待。

(2)若收到由發(fā)送結(jié)點發(fā)過來的數(shù)據(jù)幀，則將其放入數(shù)據(jù)鏈路層的接收緩存。

(3)將接收緩存中的數(shù)據(jù)幀上交主機(jī)。

(4)向發(fā)送結(jié)點發(fā)一信息，表示數(shù)據(jù)幀已經(jīng)上交給主機(jī)。

(5)轉(zhuǎn)到(1)。第2講數(shù)據(jù)鏈路層之一2a-142.具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議voidsender2(void){frames;/*bufferforanoutboundframe*/packetbuffer;/*bufferforanoutboundpacket*/event_typeevent;/*frame_arrivalistheonlypossibility*/while(true){from_network_layer(&buffer);/*gogetsomethingtosend*/=buffer;/*copyitintosfortransmission*/to_physical_layer(&s);/*byebyelittleframe*/wait_forevent(&event);/*donotproceeduntilgiventhegoahead*/}}voidreceiver2(void){framer,s;/*buffersforframes*/event_typeevent;/*frame_arrivalistheonlypossibility*/while(true){wait_for_event(&event);/*onlypossibilityisframe_arrival*/from_physical_layer(&r);/*gogettheinboundframe*/to_network_layer(&);/*passthedatatothenetworklayer*/

to_physical_layer(&s);/*sendadummyframetoawakensender*/}}第2講數(shù)據(jù)鏈路層之一2a-15兩種情況的對比（傳輸均無差錯）ABDATADATADATADATA送主機(jī)B送主機(jī)B送主機(jī)B送主機(jī)BABDATA送主機(jī)BDATA送主機(jī)B時間不需要流量控制需要流量控制第2講數(shù)據(jù)鏈路層之一2a-163.實用的停止等待協(xié)議時間ABDATA0送主機(jī)DATA1送主機(jī)ACKACK(a)正常情況送主機(jī)ACKDATA0重傳DATA0tout丟失!AB(c)數(shù)據(jù)幀丟失送主機(jī)ACKtoutACKAB(d)確認(rèn)幀丟失DATA0重傳丟棄DATA0丟失!DATA0送主機(jī)NAKACKDATA0重傳出錯AB(b)數(shù)據(jù)幀出錯四種情況

第2講數(shù)據(jù)鏈路層之一2a-17超時計時器的作用結(jié)點A發(fā)送完一個數(shù)據(jù)幀時，就啟動一個超時計時器(timeouttimer)。計時器又稱為定時器。若到了超時計時器所設(shè)置的重傳時間tout而仍收不到結(jié)點B的任何確認(rèn)幀，則結(jié)點A就重傳前面所發(fā)送的這一數(shù)據(jù)幀。一般可將重傳時間選為略大于“從發(fā)完數(shù)據(jù)幀到收到確認(rèn)幀所需的平均時間”。第2講數(shù)據(jù)鏈路層之一2a-18解決重復(fù)幀的問題

使每一個數(shù)據(jù)幀帶上不同的發(fā)送序號。每發(fā)送一個新的數(shù)據(jù)幀就把它的發(fā)送序號加1。若結(jié)點B收到發(fā)送序號相同的數(shù)據(jù)幀，就表明出現(xiàn)了重復(fù)幀。這時應(yīng)丟棄重復(fù)幀，因為已經(jīng)收到過同樣的數(shù)據(jù)幀并且也交給了主機(jī)B。但此時結(jié)點B還必須向A發(fā)送確認(rèn)幀ACK，因為B已經(jīng)知道A還沒有收到上一次發(fā)過去的確認(rèn)幀ACK。第2講數(shù)據(jù)鏈路層之一2a-19幀的編號問題

任何一個編號系統(tǒng)的序號所占用的比特數(shù)一定是有限的。因此，經(jīng)過一段時間后，發(fā)送序號就會重復(fù)。序號占用的比特數(shù)越少，數(shù)據(jù)傳輸?shù)念~外開銷就越小。對于停止等待協(xié)議，由于每發(fā)送一個數(shù)據(jù)幀就停止等待，因此用一個比特來編號就夠了。一個比特可表示0和1兩種不同的序號。

第2講數(shù)據(jù)鏈路層之一2a-20幀的發(fā)送序號

數(shù)據(jù)幀中的發(fā)送序號N(S)以0和1交替的方式出現(xiàn)在數(shù)據(jù)幀中。每發(fā)一個新的數(shù)據(jù)幀，發(fā)送序號就和上次發(fā)送的不一樣。用這樣的方法就可以使收方能夠區(qū)分開新的數(shù)據(jù)幀和重傳的數(shù)據(jù)幀了。第2講數(shù)據(jù)鏈路層之一2a-21第2講數(shù)據(jù)鏈路層之一2a-22第2講數(shù)據(jù)鏈路層之一2a-23停等ARQ協(xié)議描述voidsender3(void){seq_nrnext_frame_to_send;/*seqnumberofnextoutgoingframe*/frames;/*scratchvariable*/packetbuffer;/*bufferforanoutboundpacket*/event_typeevent;next_frame_to_send=0;/*initializeoutboundsequencenumbers*/from_network_layer(&buffer);/*fetchfirstpacket*/while(true){=buffer;/*constructaframefortransmission*/

s.seq=next_frame_to_send;/*insertsequencenumberinframe*/to_physical_layer(&s);/*senditonitsway*/

start_timer(s.seq);/*ifanswertakestoolong,timeout*/wait_forevent(&event);/*frame_arrival,cksum_err,timeout*/

if(event==frame_arrival){from_physical_layer(&s);/*gettheacknowledgement*/if(s.ack==next_frame_to_send){from_network_layer(&buffer);/*getthenextonetosend*/inc(next_frame_to_send);/*invertnext_frame_to_send*/}}}}voidreceiver3(void){seq_nrframe_expected;framer,s;event_typeevent;frame_expected=0;while(true){wait_for_event(&event);/*possibilities:frame_arrival,cksum_err*/if(event==frame_arrival){/*avalidframehasarrived*/from_physical_layer(&r);/*gogetthenewlyarrivedframe*/if(r.seq==frame_expected){/*thisiswhatwehavebeenwaitingfor.*/to_network_layer(&);/*passthedatatothenetworklayer*/inc(frame_expected);/*nexttimeexpecttheothersequencenr*/}s.ack=1-frame_expected;/*tellwhichframeisbeingacked*/

to_physical_layer(&s);/*noneofthefieldsareused*/}}}第2講數(shù)據(jù)鏈路層之一2a-24停止等待協(xié)議的算法幀錯誤與幀丟失同等對待（實用的數(shù)據(jù)鏈路層協(xié)議大都是這樣的）因此，使用帶有序號n的確認(rèn)幀。按照習(xí)慣的表示法，ACKn

表示“第n–1

號幀已經(jīng)收到，現(xiàn)在期望接收第n號幀”。ACK1表示“0號幀已收到，現(xiàn)在期望接收的下一幀是1號幀”；ACK0表示“1號幀已收到，現(xiàn)在期望接收的下一幀是0號幀”。

第2講數(shù)據(jù)鏈路層之一2a-25在發(fā)送結(jié)點：(1)從主機(jī)取一個數(shù)據(jù)幀，送交發(fā)送緩存。(2)V(S)←0。(3)N(S)←V(S)。(4)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。(5)設(shè)置超時計時器。(6)等待。{等待以下(7)和(8)這兩個事件中最先出現(xiàn)的一個}(7)收到確認(rèn)幀ACKn，若n=1–V(s)，則：從主機(jī)取一個新的數(shù)據(jù)幀，放入發(fā)送緩存；

V(S)←[1

V(S)]，轉(zhuǎn)到(3)。否則，丟棄這個確認(rèn)幀，轉(zhuǎn)到(6)。(8)若超時計時器時間到，則轉(zhuǎn)到(4)。第2講數(shù)據(jù)鏈路層之一2a-26在接收結(jié)點：(1)V(R)←0。(2)等待。(3)收到一個數(shù)據(jù)幀；若N(S)=V(R)，則執(zhí)行(4)；否則丟棄此數(shù)據(jù)幀，然后轉(zhuǎn)到(6)。(4)將收到的數(shù)據(jù)幀中的數(shù)據(jù)部分送交上層軟件（也就是數(shù)據(jù)鏈路層模型中的主機(jī)）。(5)V(R)←[1

V(R)]。(6)n←V(R)；發(fā)送確認(rèn)幀ACKn，轉(zhuǎn)到(2)。第2講數(shù)據(jù)鏈路層之一2a-27停止等待協(xié)議的要點只有收到序號正確的確認(rèn)幀ACKn后，才更新發(fā)送狀態(tài)變量V(S)一次，并發(fā)送新的數(shù)據(jù)幀。接收端接收到數(shù)據(jù)幀時，就要將發(fā)送序號N(S)與本地的接收狀態(tài)變量V(R)相比較。若二者相等就表明是新的數(shù)據(jù)幀，就收下，并發(fā)送確認(rèn)。否則為重復(fù)幀，就必須丟棄。但這時仍須向發(fā)送端發(fā)送確認(rèn)幀ACKn，而接收狀態(tài)變量V(R)和確認(rèn)序號n都不變。

第2講數(shù)據(jù)鏈路層之一2a-28停止等待協(xié)議的要點（續(xù)）連續(xù)出現(xiàn)相同發(fā)送序號的數(shù)據(jù)幀，表明發(fā)送端進(jìn)行了超時重傳。連續(xù)出現(xiàn)相同序號的確認(rèn)幀，表明接收端收到了重復(fù)幀（接收端超時導(dǎo)致的）。發(fā)送端在發(fā)送完數(shù)據(jù)幀時，必須在其發(fā)送緩存中暫時保留這個數(shù)據(jù)幀的副本。這樣才能在出差錯時進(jìn)行重傳。只有確認(rèn)對方已經(jīng)收到這個數(shù)據(jù)幀時，才可以清除這個副本。第2講數(shù)據(jù)鏈路層之一2a-29停止等待協(xié)議的要點（續(xù)）實用的

CRC

檢驗器都是用硬件完成的。CRC檢驗器能夠自動丟棄檢測到的出錯幀。因此所謂的“丟棄出錯幀”，對上層軟件或用戶來說都是感覺不到的。發(fā)送端對出錯的數(shù)據(jù)幀進(jìn)行重傳是自動進(jìn)行的，因而這種差錯控制體制常簡稱為ARQ(AutomaticRepeatreQuest)，直譯是自動重傳請求，但意思是自動請求重傳。第2講數(shù)據(jù)鏈路層之一2a-30可靠傳輸雖然物理層在傳輸比特時會出現(xiàn)差錯，但由于數(shù)據(jù)鏈路層的停止等待協(xié)議采用了有效的檢錯重傳機(jī)制，數(shù)據(jù)鏈路層對上面的網(wǎng)絡(luò)層就可以提供可靠傳輸?shù)姆?wù)。糾錯/檢錯常用的檢錯方法校驗和（checksum）CRC第2講數(shù)據(jù)鏈路層之一2a-31錯誤檢測EDC=錯誤檢測校正（ErrorDetectionandCorrection(冗余數(shù)據(jù))）位D=由檢驗位保護(hù)的數(shù)據(jù),可包括首部字段

錯誤檢測不可能達(dá)到100%可靠!

協(xié)議算法可能會忽略了某些錯誤,但比例極小

較大的EDC字段可以產(chǎn)生較好的檢錯和糾錯效果第2講數(shù)據(jù)鏈路層之一2a-32奇偶校驗單比特校驗:檢測奇數(shù)位錯誤兩維單比特校驗:檢測和校正單比特錯誤00第2講數(shù)據(jù)鏈路層之一2a-33因特網(wǎng)校驗和發(fā)送端:把數(shù)據(jù)段的內(nèi)容看成一系列16-bit的整數(shù)校驗和:對內(nèi)容進(jìn)行累加(1’scomplementsum)發(fā)送端將校驗和放入UDP的checksum字段接收端:對接收到的數(shù)據(jù)段進(jìn)行校驗和計算檢查計算所得的校驗和與接收到值的是否相等:NO–出錯了YES–沒查出錯誤.但有可能存在錯誤?….目的:

檢測數(shù)據(jù)段在傳輸過程中出現(xiàn)的錯誤(注意:僅用在傳輸層)第2講數(shù)據(jù)鏈路層之一2a-34循環(huán)冗余檢驗的原理在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗CRC的檢錯技術(shù)。假設(shè)待傳送的數(shù)據(jù)D=1010001101（共dbit）。我們在D的后面再添加供差錯檢測用的rbit冗余碼R一起發(fā)送。第2講數(shù)據(jù)鏈路層之一2a-35冗余碼的計算用二進(jìn)制的模2運(yùn)算進(jìn)行2r乘D的運(yùn)算，這相當(dāng)于在D后面添加r個0，得到(d+r)bit長的數(shù)。用得到的(d+r)bit的數(shù)D*2r除以事先選定好的長度為(r+1)bit的生成多項式P，得出的商是Q，而余數(shù)是R，除數(shù)P比余數(shù)R至少要多1個比特。余數(shù)R＝冗余碼R第2講數(shù)據(jù)鏈路層之一2a-36冗余碼的計算舉例設(shè)待傳送的數(shù)據(jù)：D=1010001101，

r=5，生成多項式P=110101，運(yùn)算的結(jié)果是：余數(shù)R=01110將余數(shù)R作為冗余碼添加在數(shù)據(jù)D的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或2rD+R

1101010110

←

Q

商110101101000110100000

←

2rD被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余數(shù)除數(shù)

P

第2講數(shù)據(jù)鏈路層之一2a-37循環(huán)冗余檢驗的原理說明接收方將接收到的數(shù)據(jù)，用生成多項式P去除它，只要得出的余數(shù)R不為0，就表示檢測到了差錯。但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現(xiàn)了差錯。一旦檢測出差錯，就丟棄這個出現(xiàn)差錯的幀。只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)P，那么出現(xiàn)檢測不到的差錯的概率就很小很小。第2講數(shù)據(jù)鏈路層之一2a-38幀檢驗序列FCS在數(shù)據(jù)后面添加上的冗余碼稱為幀檢驗序列

FCS(FrameCheckSequence)。循環(huán)冗余檢驗CRC和幀檢驗序列FCS并不等同。CRC是一種常用的檢錯方法，而FCS是添加在數(shù)據(jù)后面的冗余碼。FCS可以用CRC這種方法得出，但CRC并非用來獲得FCS的惟一方法。

第2講數(shù)據(jù)鏈路層之一2a-39應(yīng)當(dāng)注意僅用循環(huán)冗余檢驗CRC差錯檢測技術(shù)只能做到無差錯接受(accept)?！盁o差錯接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們都能以非常接近于1的概率認(rèn)為這些幀在傳輸過程中沒有產(chǎn)生差錯”。但是，永遠(yuǎn)都不可能保證收到的數(shù)據(jù)是絕對正確的。要對付出錯和丟失的情況，就必須再加上確認(rèn)和重傳機(jī)制。第2講數(shù)據(jù)鏈路層之一2a-40停止等待協(xié)議ARQ的優(yōu)缺點優(yōu)點：比較簡單。缺點：通信信道的利用率不高，也就是說，信道還遠(yuǎn)遠(yuǎn)沒有被數(shù)據(jù)比特填滿。為了克服這一缺點，就產(chǎn)生了另外兩種協(xié)議，即連續(xù)ARQ和選擇重傳ARQ。時間ABDATA0送主機(jī)DATA1送主機(jī)ACKACK第2講數(shù)據(jù)鏈路層之一2a-41連續(xù)ARQ協(xié)議在發(fā)送完一個數(shù)據(jù)幀后，不是停下來等待確認(rèn)幀，而是可以連續(xù)再發(fā)送若干個數(shù)據(jù)幀，同時等待確認(rèn)。接收方只按序號逐個地接收和確認(rèn)數(shù)據(jù)幀。如果某一幀沒有及時收到確認(rèn)，則需要重發(fā)該幀及以后的所有幀。第2講數(shù)據(jù)鏈路層之一2a-42連續(xù)ARQ協(xié)議的工作原理DATA0DATA1DATA2DATA3DATA4DATA5重傳DATA2重傳DATA3ACK1ACK2ACK1確認(rèn)DATA0ACK2確認(rèn)DATA1DATA2出錯，丟棄DATA3不按序，丟棄，重傳ACK2DATA4不按序，丟棄，重傳ACK2DATA5不按序，丟棄，重傳ACK2ACK3ACK3確認(rèn)DATA2ACK4確認(rèn)DATA3ACK4重傳DATA5重傳DATA4超時重傳時間ABtout送交主機(jī)送交主機(jī)…

ACK2ACK2ACK2第2講數(shù)據(jù)鏈路層之一2a-43需要注意(1)接收端只按序接收數(shù)據(jù)幀。雖然在有差錯的2號幀之后接著又收到了正確的3個數(shù)據(jù)幀，但接收端都必須將這些幀丟棄，因為在這些幀前面有一個2號幀還沒有收到。雖然丟棄了這些不按序的無差錯幀，但應(yīng)重復(fù)發(fā)送已發(fā)送過的最后一個確認(rèn)幀（防止確認(rèn)幀丟失）。DATA0DATA1DATA2DATA3DATA4DATA5重傳DATA2重傳DATA3ACK1ACK2ACK3ACK4重傳DATA5重傳DATA4ABtout

ACK2ACK2ACK2第2講數(shù)據(jù)鏈路層之一2a-44需要注意(2)ACK1表示確認(rèn)0號幀DATA0，并期望下次收到1號幀；ACK2表示確認(rèn)1號幀DATA1，并期望下次收到2號幀。依此類推。。。DATA0DATA1DATA2DATA3DATA4DATA5重傳DATA2重傳DATA3ACK1ACK2ACK3ACK4重傳DATA5重傳DATA4ABtout

ACK2ACK2ACK2第2講數(shù)據(jù)鏈路層之一2a-45需要注意(3)結(jié)點A在每發(fā)送完一個數(shù)據(jù)幀時都要設(shè)置該幀的超時計時器。如果在所設(shè)置的超時時間內(nèi)收到確認(rèn)幀，就立即將超時計時器清零。但若在所設(shè)置的超時時間到了而未收到確認(rèn)幀，就要重傳相應(yīng)的數(shù)據(jù)幀（仍需重新設(shè)置超時計時器）。在等不到2號幀的確認(rèn)而重傳2號數(shù)據(jù)幀時，雖然結(jié)點A已經(jīng)發(fā)完了5號幀，但仍必須向回走，將2號幀及其以后的各幀全部進(jìn)行重傳。連續(xù)ARQ又稱為Go-back-NARQ，意思是當(dāng)出現(xiàn)差錯必須重傳時，要向回走N個幀，然后再開始重傳。DATA0DATA1DATA2DATA3DATA4DATA5重傳DATA2重傳DATA3ACK1ACK2ACK3ACK4重傳DATA5重傳DATA4ABtout

ACK2ACK2ACK2第2講數(shù)據(jù)鏈路層之一2a-46滑動窗口的概念如果連續(xù)發(fā)送的幀過多，一旦出錯，則需重傳的幀也會增多，使效率降低；序號用幀頭中的字段表示，比特數(shù)是有限的。因此，必須限制連續(xù)發(fā)送的幀數(shù)。此時協(xié)議的運(yùn)轉(zhuǎn)表現(xiàn)為“滑動窗口”的形式，可認(rèn)為發(fā)送端和接收端分別設(shè)定了發(fā)送窗口和接收窗口。第2講數(shù)據(jù)鏈路層之一2a-47發(fā)送窗口發(fā)送窗口的大小WT

代表在還沒有收到對方確認(rèn)信息的情況下發(fā)送端最多可以發(fā)送多少個數(shù)據(jù)幀。發(fā)送窗口內(nèi)的幀包括已發(fā)送但尚未收到確認(rèn)的幀可以立即發(fā)送的幀另一種定義是發(fā)送窗口僅包含后一種幀，但WT

的意義不變兩者數(shù)目之和為WT

第2講數(shù)據(jù)鏈路層之一2a-4801234567012發(fā)送窗口WT不允許發(fā)送這些幀允許發(fā)送5個幀(a)01234567012不允許發(fā)送這些幀還允許發(fā)送4個幀WT已發(fā)送(b)01234567012不允許發(fā)送這些幀WT已發(fā)送(c)01234567012不允許發(fā)送這些幀還允許發(fā)送

3個幀WT已發(fā)送已發(fā)送并已收到確認(rèn)(d)第2講數(shù)據(jù)鏈路層之一2a-49接收窗口接收窗口代表了期望收到的數(shù)據(jù)幀的范圍若接收到的數(shù)據(jù)幀落在接收窗口之外，則一律將其丟棄。在連續(xù)ARQ協(xié)議中，接收窗口的大小WR=1。只有當(dāng)收到的幀的序號與接收窗口一致時才能接收該幀。否則，就丟棄它。每收到一個序號正確的幀，接收窗口就向前（即向右方）滑動一個幀的位置。同時發(fā)送對該幀的確認(rèn)。

第2講數(shù)據(jù)鏈路層之一2a-50不允許接收這些幀01234567012WR準(zhǔn)備接收0號幀(a)不允許接收這些幀01234567012WR準(zhǔn)備接收

1號幀已收到(b)不允許接收這些幀01234567012WR準(zhǔn)備接收4號幀已收到(c)第2講數(shù)據(jù)鏈路層之一2a-51滑動窗口的重要特性只有在接收窗口向前滑動時（與此同時也發(fā)送了確認(rèn)），發(fā)送窗口才有可能向前滑動。收發(fā)兩端的窗口按照以上規(guī)律不斷地向前滑動，因此這種協(xié)議又稱為滑動窗口協(xié)議。當(dāng)發(fā)送窗口和接收窗口的大小都等于1時，就是停止等待協(xié)議。第2講數(shù)據(jù)鏈路層之一2a-52滑動窗口的流量控制功能發(fā)送窗口越大，則可以連續(xù)發(fā)送的幀數(shù)也越多，意味著發(fā)送速率越高。接收方可以通過調(diào)整發(fā)送方的窗口大小來對發(fā)送端進(jìn)行流量控制。如果發(fā)送窗口縮小為1，則成為停止等待協(xié)議，此時只能靠調(diào)整返回ACK的時間間隔來進(jìn)行流量控制。問題：如何區(qū)分?jǐn)?shù)據(jù)/ACK丟失和對發(fā)送端的抑制？第2講數(shù)據(jù)鏈路層之一2a-53發(fā)送窗口的最大值當(dāng)用n個比特進(jìn)行編號時，若接收窗口的大小為1，則只有在發(fā)送窗口的大小WT

2n1時，連續(xù)ARQ協(xié)議才能正確運(yùn)行。例如，當(dāng)采用3bit編碼時，發(fā)送窗口的最大值是7而不是8。01234567012第2講數(shù)據(jù)鏈路層之一2a-54最佳幀長若數(shù)據(jù)幀的幀長取得很短，那么控制信息在每一幀中所占的比例就增大，因而額外開銷增大，這就導(dǎo)致信道利用率的下降。若幀長取得太長，則數(shù)據(jù)幀在傳輸過程中出錯的概率就增大，于是重傳次數(shù)將增大，這也會使信道利用率下降。由此可見，存在一個最佳幀長，在此幀長下信道的利用率最高。第2講數(shù)據(jù)鏈路層之一2a-55選擇重傳ARQ協(xié)議可加大接收窗口，先收下發(fā)送序號不連續(xù)但仍處在接收窗口中的那些數(shù)據(jù)幀。等到所缺序號的數(shù)據(jù)幀收到后再一并送交主機(jī)。選擇重傳ARQ協(xié)議可避免重復(fù)傳送那些本來已經(jīng)正確到達(dá)接收端的數(shù)據(jù)幀。但我們付出的代價是在接收端要設(shè)置具有相當(dāng)容量的緩存空間。第2講數(shù)據(jù)鏈路層之一2a-56協(xié)議的選擇

如果鏈路傳播延遲較小，可以采用停止等待協(xié)議否則，如果鏈路錯誤率較低，可以采用連續(xù)ARQ協(xié)議反之，則應(yīng)采用選擇重傳ARQ協(xié)議第2講數(shù)據(jù)鏈路層之一2a-57多點訪問鏈路和協(xié)議有三種類型的“鏈路”:點對點(e.g.PPP,SLIP)廣播式

(共享線路或介質(zhì);e.g,以太網(wǎng),無線網(wǎng),etc.)交換式(e.g.,交換式以太網(wǎng),ATMetc.)第2講數(shù)據(jù)鏈路層之一2a-58多點訪問協(xié)議一條共享的通信信道兩個或多個結(jié)點可同時發(fā)送信號:相互干擾在某一時刻只有一個結(jié)點可以成功地發(fā)送信號

多點訪問協(xié)議:分布式的算法來決定如何共享信道,i.e.,決定工作站何時可以發(fā)送注意：有關(guān)共享通道的通信（協(xié)商）也必須在該通道自身上解決!我們希望多點訪問協(xié)議能夠解決什么問題:同步還是異步

了解其他站點的信息健壯性(e.g.如何對待信道錯誤)性能第2講數(shù)據(jù)鏈路層之一2a-59MAC協(xié)議:類型通道分割將信道分割成較小的“片”(時隙,頻率)將小片分給各站點使用隨機(jī)訪問允許沖突從沖突中“恢復(fù)”“排隊”嚴(yán)格協(xié)調(diào)訪問來避免沖突目標(biāo):

高效,公平,簡單,分散控制第2講數(shù)據(jù)鏈路層之一2a-60隨機(jī)訪問協(xié)議當(dāng)結(jié)點有數(shù)據(jù)要發(fā)送時：使用信道全部的傳輸