第二講+鏈路層A

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

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

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

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

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

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

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

信號(hào)衰減和噪聲會(huì)導(dǎo)致出錯(cuò).接收端檢測(cè)到錯(cuò)誤時(shí):給發(fā)送端信號(hào)要求重發(fā)或丟棄出錯(cuò)幀

錯(cuò)誤校正:

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

A緩存主機(jī)

B數(shù)據(jù)鏈路AP2AP1緩存發(fā)送方接收方幀高層幀完全理想化的數(shù)據(jù)傳輸假定1：鏈路是理想的傳輸信道，所傳送的任何數(shù)據(jù)既不會(huì)出差錯(cuò)也不會(huì)丟失。假定2：不管發(fā)方以多快的速率發(fā)送數(shù)據(jù)，收方總是來(lái)得及收下，并及時(shí)上交主機(jī)。這個(gè)假定就相當(dāng)于認(rèn)為：接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不會(huì)低于發(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.具有最簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議現(xiàn)在去掉上述的第二個(gè)假定。但是，仍然保留第一個(gè)假定，即主機(jī)A向主機(jī)B傳輸數(shù)據(jù)的信道仍然是無(wú)差錯(cuò)的理想信道。然而現(xiàn)在不能保證接收端向主機(jī)交付數(shù)據(jù)的速率永遠(yuǎn)不低于發(fā)送端發(fā)送數(shù)據(jù)的速率。流量控制策略：處理發(fā)送方的傳送能力比接收方接收能力大的問(wèn)題?；诜答仚C(jī)制/交由傳輸層實(shí)現(xiàn)由收方控制發(fā)方的數(shù)據(jù)流，乃是計(jì)算機(jī)網(wǎng)絡(luò)中流量控制的一個(gè)基本方法。第2講數(shù)據(jù)鏈路層之一2a-112.具有最簡(jiǎn)單流量控制的數(shù)據(jù)鏈路層協(xié)議算法在發(fā)送結(jié)點(diǎn)：

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

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

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

(4)等待。

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

(1)等待。

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

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

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

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

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

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

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

(4)等待。

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

(1)等待。

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

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

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

(5)轉(zhuǎn)到(1)。第2講數(shù)據(jù)鏈路層之一2a-142.具有最簡(jiǎn)單流量控制的數(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兩種情況的對(duì)比（傳輸均無(wú)差錯(cuò)）ABDATADATADATADATA送主機(jī)B送主機(jī)B送主機(jī)B送主機(jī)BABDATA送主機(jī)BDATA送主機(jī)B時(shí)間不需要流量控制需要流量控制第2講數(shù)據(jù)鏈路層之一2a-163.實(shí)用的停止等待協(xié)議時(shí)間ABDATA0送主機(jī)DATA1送主機(jī)ACKACK(a)正常情況送主機(jī)ACKDATA0重傳DATA0tout丟失!AB(c)數(shù)據(jù)幀丟失送主機(jī)ACKtoutACKAB(d)確認(rèn)幀丟失DATA0重傳丟棄DATA0丟失!DATA0送主機(jī)NAKACKDATA0重傳出錯(cuò)AB(b)數(shù)據(jù)幀出錯(cuò)四種情況

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

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

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

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

數(shù)據(jù)幀中的發(fā)送序號(hào)N(S)以0和1交替的方式出現(xiàn)在數(shù)據(jù)幀中。每發(fā)一個(gè)新的數(shù)據(jù)幀，發(fā)送序號(hào)就和上次發(fā)送的不一樣。用這樣的方法就可以使收方能夠區(qū)分開(kāi)新的數(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é)議的算法幀錯(cuò)誤與幀丟失同等對(duì)待（實(shí)用的數(shù)據(jù)鏈路層協(xié)議大都是這樣的）因此，使用帶有序號(hào)n的確認(rèn)幀。按照習(xí)慣的表示法，ACKn

表示“第n–1

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

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

V(S)←[1

V(S)]，轉(zhuǎn)到(3)。否則，丟棄這個(gè)確認(rèn)幀，轉(zhuǎn)到(6)。(8)若超時(shí)計(jì)時(shí)器時(shí)間到，則轉(zhuǎn)到(4)。第2講數(shù)據(jù)鏈路層之一2a-26在接收結(jié)點(diǎn)：(1)V(R)←0。(2)等待。(3)收到一個(gè)數(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é)議的要點(diǎn)只有收到序號(hào)正確的確認(rèn)幀ACKn后，才更新發(fā)送狀態(tài)變量V(S)一次，并發(fā)送新的數(shù)據(jù)幀。接收端接收到數(shù)據(jù)幀時(shí)，就要將發(fā)送序號(hào)N(S)與本地的接收狀態(tài)變量V(R)相比較。若二者相等就表明是新的數(shù)據(jù)幀，就收下，并發(fā)送確認(rèn)。否則為重復(fù)幀，就必須丟棄。但這時(shí)仍須向發(fā)送端發(fā)送確認(rèn)幀ACKn，而接收狀態(tài)變量V(R)和確認(rèn)序號(hào)n都不變。

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

CRC

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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