第二讲+链路层A

第2讲数据链路层之一2a-1第2讲:数据链路层本讲目标:

了解数据链路层服务原理:可靠数据传输,流量控制错误检测,校正共享广播信道链路层编址各类链路层技术的实现和实例教科书参考第4、5、6章概述:链路层的服务可靠数据传输,流量控制错误检测,校正多点访问技术和LAN链路层寻址,ARP特定的链路层技术:以太网集线器,网桥,交换机第2讲数据链路层之一2a-2数据链路层的基本概念链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。数据链路(datalink)

除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。第2讲数据链路层之一2a-3链路层:工作环境两个物理上连接的设备:主机-路由器,路由器-路由器,主机-主机第2讲数据链路层之一2a-4链路层:工作环境常常在两个对等的数据链路层之间画出一个数字管道，在这条数字管道上传输的数据单位是frame（帧）applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframe物理链路数据链路协议接口卡结点结点帧帧第2讲数据链路层之一2a-5链路层的服务成帧,链路访问:

将分组封装入帧,加上帧头,帧尾如果是共享介质，则需实现信道的访问,‘物理地址’放在帧首用来确定信源、信宿

不同于IP地址喔!在两台物理上连接的设备之间实现可靠传递:

可靠传递是什么概念，回顾一下学过的知识!不太用在误码率低的场合(光纤,某些双绞线)无线链路:误码率相当高第2讲数据链路层之一2a-6链路层的服务(续)流量控制:

保持收发双方的同步错误检测:

信号衰减和噪声会导致出错.接收端检测到错误时:给发送端信号要求重发或丢弃出错帧

错误校正:

接受端检测多个位错并加以校正而无需要求发送端重发第2讲数据链路层之一2a-7链路层:实现通过“adapter（网卡或适配器）”实现e.g.,PCMCIA卡,以太网卡一般适配器都含有:RAM,DSP芯片,主机的总线接口,和链路接口applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframephys.linkdatalinkprotocoladaptercard第2讲数据链路层之一2a-8停止等待协议数据链路层主机

A缓存主机

B数据链路AP2AP1缓存发送方接收方帧高层帧完全理想化的数据传输假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。第2讲数据链路层之一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*/}}完全理想化的数据传输第2讲数据链路层之一2a-102.具有最简单流量控制的数据链路层协议现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机A向主机B传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。流量控制策略：处理发送方的传送能力比接收方接收能力大的问题。基于反馈机制/交由传输层实现由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。第2讲数据链路层之一2a-112.具有最简单流量控制的数据链路层协议算法在发送结点：

(1)从主机取一个数据帧。

(2)将数据帧送到数据链路层的发送缓存。

(3)将发送缓存中的数据帧发送出去。

(4)等待。

(5)若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)。第2讲数据链路层之一2a-122.具有最简单流量控制的数据链路层协议算法（续）在接收结点：

(1)等待。

(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。

(3)将接收缓存中的数据帧上交主机。

(4)向发送结点发一信息，表示数据帧已经上交给主机。

(5)转到(1)。第2讲数据链路层之一2a-13流程分析在发送结点：

(1)从主机取一个数据帧。

(2)将数据帧送到数据链路层的发送缓存。

(3)将发送缓存中的数据帧发送出去。

(4)等待。

(5)若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)在接收结点：

(1)等待。

(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。

(3)将接收缓存中的数据帧上交主机。

(4)向发送结点发一信息，表示数据帧已经上交给主机。

(5)转到(1)。第2讲数据链路层之一2a-142.具有最简单流量控制的数据链路层协议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讲数据链路层之一2a-15两种情况的对比（传输均无差错）ABDATADATADATADATA送主机B送主机B送主机B送主机BABDATA送主机BDATA送主机B时间不需要流量控制需要流量控制第2讲数据链路层之一2a-163.实用的停止等待协议时间ABDATA0送主机DATA1送主机ACKACK(a)正常情况送主机ACKDATA0重传DATA0tout丢失!AB(c)数据帧丢失送主机ACKtoutACKAB(d)确认帧丢失DATA0重传丢弃DATA0丢失!DATA0送主机NAKACKDATA0重传出错AB(b)数据帧出错四种情况

第2讲数据链路层之一2a-17超时计时器的作用结点A发送完一个数据帧时，就启动一个超时计时器(timeouttimer)。计时器又称为定时器。若到了超时计时器所设置的重传时间tout而仍收不到结点B的任何确认帧，则结点A就重传前面所发送的这一数据帧。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。第2讲数据链路层之一2a-18解决重复帧的问题

使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1。若结点B收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机B。但此时结点B还必须向A发送确认帧ACK，因为B已经知道A还没有收到上一次发过去的确认帧ACK。第2讲数据链路层之一2a-19帧的编号问题

任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。序号占用的比特数越少，数据传输的额外开销就越小。对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。一个比特可表示0和1两种不同的序号。

第2讲数据链路层之一2a-20帧的发送序号

数据帧中的发送序号N(S)以0和1交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。第2讲数据链路层之一2a-21第2讲数据链路层之一2a-22第2讲数据链路层之一2a-23停等ARQ协议描述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讲数据链路层之一2a-24停止等待协议的算法帧错误与帧丢失同等对待（实用的数据链路层协议大都是这样的）因此，使用带有序号n的确认帧。按照习惯的表示法，ACKn

表示“第n–1

号帧已经收到，现在期望接收第n号帧”。ACK1表示“0号帧已收到，现在期望接收的下一帧是1号帧”；ACK0表示“1号帧已收到，现在期望接收的下一帧是0号帧”。

第2讲数据链路层之一2a-25在发送结点：(1)从主机取一个数据帧，送交发送缓存。(2)V(S)←0。(3)N(S)←V(S)。(4)将发送缓存中的数据帧发送出去。(5)设置超时计时器。(6)等待。{等待以下(7)和(8)这两个事件中最先出现的一个}(7)收到确认帧ACKn，若n=1–V(s)，则：从主机取一个新的数据帧，放入发送缓存；

V(S)←[1

V(S)]，转到(3)。否则，丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到(4)。第2讲数据链路层之一2a-26在接收结点：(1)V(R)←0。(2)等待。(3)收到一个数据帧；若N(S)=V(R)，则执行(4)；否则丢弃此数据帧，然后转到(6)。(4)将收到的数据帧中的数据部分送交上层软件（也就是数据链路层模型中的主机）。(5)V(R)←[1

V(R)]。(6)n←V(R)；发送确认帧ACKn，转到(2)。第2讲数据链路层之一2a-27停止等待协议的要点只有收到序号正确的确认帧ACKn后，才更新发送状态变量V(S)一次，并发送新的数据帧。接收端接收到数据帧时，就要将发送序号N(S)与本地的接收状态变量V(R)相比较。若二者相等就表明是新的数据帧，就收下，并发送确认。否则为重复帧，就必须丢弃。但这时仍须向发送端发送确认帧ACKn，而接收状态变量V(R)和确认序号n都不变。

第2讲数据链路层之一2a-28停止等待协议的要点（续）连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧，表明接收端收到了重复帧（接收端超时导致的）。发送端在发送完数据帧时，必须在其发送缓存中暂时保留这个数据帧的副本。这样才能在出差错时进行重传。只有确认对方已经收到这个数据帧时，才可以清除这个副本。第2讲数据链路层之一2a-29停止等待协议的要点（续）实用的

CRC

检验器都是用硬件完成的。CRC检验器能够自动丢弃检测到的出错帧。因此所谓的“丢弃出错帧”，对上层软件或用户来说都是感觉不到的。发送端对出错的数据帧进行重传是自动进行的，因而这种差错控制体制常简称为ARQ(AutomaticRepeatreQuest)，直译是自动重传请求，但意思是自动请求重传。第2讲数据链路层之一2a-30可靠传输虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。纠错/检错常用的检错方法校验和（checksum）CRC第2讲数据链路层之一2a-31错误检测EDC=错误检测校正（ErrorDetectionandCorrection(冗余数据)）位D=由检验位保护的数据,可包括首部字段

错误检测不可能达到100%可靠!

协议算法可能会忽略了某些错误,但比例极小

较大的EDC字段可以产生较好的检错和纠错效果第2讲数据链路层之一2a-32奇偶校验单比特校验:检测奇数位错误两维单比特校验:检测和校正单比特错误00第2讲数据链路层之一2a-33因特网校验和发送端:把数据段的内容看成一系列16-bit的整数校验和:对内容进行累加(1’scomplementsum)发送端将校验和放入UDP的checksum字段接收端:对接收到的数据段进行校验和计算检查计算所得的校验和与接收到值的是否相等:NO–出错了YES–没查出错误.但有可能存在错误?….目的:

检测数据段在传输过程中出现的错误(注意:仅用在传输层)第2讲数据链路层之一2a-34循环冗余检验的原理在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。假设待传送的数据D=1010001101（共dbit）。我们在D的后面再添加供差错检测用的rbit冗余码R一起发送。第2讲数据链路层之一2a-35冗余码的计算用二进制的模2运算进行2r乘D的运算，这相当于在D后面添加r个0，得到(d+r)bit长的数。用得到的(d+r)bit的数D*2r除以事先选定好的长度为(r+1)bit的生成多项式P，得出的商是Q，而余数是R，除数P比余数R至少要多1个比特。余数R＝冗余码R第2讲数据链路层之一2a-36冗余码的计算举例设待传送的数据：D=1010001101，

r=5，生成多项式P=110101，运算的结果是：余数R=01110将余数R作为冗余码添加在数据D的后面发送出去，即发送的数据是101000110101110，或2rD+R

1101010110

←

Q

商110101101000110100000

←

2rD被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数除数

P

第2讲数据链路层之一2a-37循环冗余检验的原理说明接收方将接收到的数据，用生成多项式P去除它，只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。第2讲数据链路层之一2a-38帧检验序列FCS在数据后面添加上的冗余码称为帧检验序列

FCS(FrameCheckSequence)。循环冗余检验CRC和帧检验序列FCS并不等同。CRC是一种常用的检错方法，而FCS是添加在数据后面的冗余码。FCS可以用CRC这种方法得出，但CRC并非用来获得FCS的惟一方法。

第2讲数据链路层之一2a-39应当注意仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。但是，永远都不可能保证收到的数据是绝对正确的。要对付出错和丢失的情况，就必须再加上确认和重传机制。第2讲数据链路层之一2a-40停止等待协议ARQ的优缺点优点：比较简单。缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。为了克服这一缺点，就产生了另外两种协议，即连续ARQ和选择重传ARQ。时间ABDATA0送主机DATA1送主机ACKACK第2讲数据链路层之一2a-41连续ARQ协议在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧，同时等待确认。接收方只按序号逐个地接收和确认数据帧。如果某一帧没有及时收到确认，则需要重发该帧及以后的所有帧。第2讲数据链路层之一2a-42连续ARQ协议的工作原理DATA0DATA1DATA2DATA3DATA4DATA5重传DATA2重传DATA3ACK1ACK2ACK1确认DATA0ACK2确认DATA1DATA2出错，丢弃DATA3不按序，丢弃，重传ACK2DATA4不按序，丢弃，重传ACK2DATA5不按序，丢弃，重传ACK2ACK3ACK3确认DATA2ACK4确认DATA3ACK4重传DATA5重传DATA4超时重传时间ABtout送交主机送交主机…

ACK2ACK2ACK2第2讲数据链路层之一2a-43需要注意(1)接收端只按序接收数据帧。虽然在有差错的2号帧之后接着又收到了正确的3个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个2号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。DATA0DATA1DATA2DATA3DATA4DATA5重传DATA2重传DATA3ACK1ACK2ACK3ACK4重传DATA5重传DATA4ABtout

ACK2ACK2ACK2第2讲数据链路层之一2a-44需要注意(2)ACK1表示确认0号帧DATA0，并期望下次收到1号帧；ACK2表示确认1号帧DATA1，并期望下次收到2号帧。依此类推。。。DATA0DATA1DATA2DATA3DATA4DATA5重传DATA2重传DATA3ACK1ACK2ACK3ACK4重传DATA5重传DATA4ABtout

ACK2ACK2ACK2第2讲数据链路层之一2a-45需要注意(3)结点A在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。在等不到2号帧的确认而重传2号数据帧时，虽然结点A已经发完了5号帧，但仍必须向回走，将2号帧及其以后的各帧全部进行重传。连续ARQ又称为Go-back-NARQ，意思是当出现差错必须重传时，要向回走N个帧，然后再开始重传。DATA0DATA1DATA2DATA3DATA4DATA5重传DATA2重传DATA3ACK1ACK2ACK3ACK4重传DATA5重传DATA4ABtout

ACK2ACK2ACK2第2讲数据链路层之一2a-46滑动窗口的概念如果连续发送的帧过多，一旦出错，则需重传的帧也会增多，使效率降低；序号用帧头中的字段表示，比特数是有限的。因此，必须限制连续发送的帧数。此时协议的运转表现为“滑动窗口”的形式，可认为发送端和接收端分别设定了发送窗口和接收窗口。第2讲数据链路层之一2a-47发送窗口发送窗口的大小WT

代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。发送窗口内的帧包括已发送但尚未收到确认的帧可以立即发送的帧另一种定义是发送窗口仅包含后一种帧，但WT

的意义不变两者数目之和为WT

第2讲数据链路层之一2a-4801234567012发送窗口WT不允许发送这些帧允许发送5个帧(a)01234567012不允许发送这些帧还允许发送4个帧WT已发送(b)01234567012不允许发送这些帧WT已发送(c)01234567012不允许发送这些帧还允许发送

3个帧WT已发送已发送并已收到确认(d)第2讲数据链路层之一2a-49接收窗口接收窗口代表了期望收到的数据帧的范围若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续ARQ协议中，接收窗口的大小WR=1。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。

第2讲数据链路层之一2a-50不允许接收这些帧01234567012WR准备接收0号帧(a)不允许接收这些帧01234567012WR准备接收

1号帧已收到(b)不允许接收这些帧01234567012WR准备接收4号帧已收到(c)第2讲数据链路层之一2a-51滑动窗口的重要特性只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于1时，就是停止等待协议。第2讲数据链路层之一2a-52滑动窗口的流量控制功能发送窗口越大，则可以连续发送的帧数也越多，意味着发送速率越高。接收方可以通过调整发送方的窗口大小来对发送端进行流量控制。如果发送窗口缩小为1，则成为停止等待协议，此时只能靠调整返回ACK的时间间隔来进行流量控制。问题：如何区分数据/ACK丢失和对发送端的抑制？第2讲数据链路层之一2a-53发送窗口的最大值当用n个比特进行编号时，若接收窗口的大小为1，则只有在发送窗口的大小WT

2n1时，连续ARQ协议才能正确运行。例如，当采用3bit编码时，发送窗口的最大值是7而不是8。01234567012第2讲数据链路层之一2a-54最佳帧长若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。由此可见，存在一个最佳帧长，在此帧长下信道的利用率最高。第2讲数据链路层之一2a-55选择重传ARQ协议可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。选择重传ARQ协议可避免重复传送那些本来已经正确到达接收端的数据帧。但我们付出的代价是在接收端要设置具有相当容量的缓存空间。第2讲数据链路层之一2a-56协议的选择

如果链路传播延迟较小，可以采用停止等待协议否则，如果链路错误率较低，可以采用连续ARQ协议反之，则应采用选择重传ARQ协议第2讲数据链路层之一2a-57多点访问链路和协议有三种类型的“链路”:点对点(e.g.PPP,SLIP)广播式

(共享线路或介质;e.g,以太网,无线网,etc.)交换式(e.g.,交换式以太网,ATMetc.)第2讲数据链路层之一2a-58多点访问协议一条共享的通信信道两个或多个结点可同时发送信号:相互干扰在某一时刻只有一个结点可以成功地发送信号

多点访问协议:分布式的算法来决定如何共享信道,i.e.,决定工作站何时可以发送注意：有关共享通道的通信（协商）也必须在该通道自身上解决!我们希望多点访问协议能够解决什么问题:同步还是异步

了解其他站点的信息健壮性(e.g.如何对待信道错误)性能第2讲数据链路层之一2a-59MAC协议:类型通道分割将信道分割成较小的“片”(时隙,频率)将小片分给各站点使用随机访问允许冲突从冲突中“恢复”“排队”严格协调访问来避免冲突目标:

高效,公平,简单,分散控制第2讲数据链路层之一2a-60随机访问协议当结点有数据要发送时：使用信道全部的传输