第三章数据链路层.docx
《第三章数据链路层.docx》由会员分享，可在线阅读，更多相关《第三章数据链路层.docx（15页珍藏版）》请在冰点文库上搜索。
第三章数据链路层
第三章数据链路层
数据链路层要紧解决相邻两个节点间的通信问题，它负责将源节点网络层上的数据传输到目的节点的网络层上。
所谓相邻是指两个节点通过一条物理信道直接相连。
1．数据链路层的设计问题
依照网络的分层模型，每一层都是要利用其基层提供的效劳来为其上层提供效劳。
数据链路层从物理层取得的效劳是原始的比特流传输效劳，而比特流在传输的进程中是会犯错的，因此检测和纠正这些错误使得网络层能够不用关切传输错误，成为数据链路层的一项重要工作。
第二较高的发送速度和较低的接收能力的不匹配，也是造成传输犯错的一个缘故，因此流量操纵也是数据链路层的一项重要工作。
另外，不同的应用或传输环境可能要求不同的链路层效劳，因此链路层应该有多种效劳供上层选择，且每种效劳有概念良好的接供词上层挪用。
综上所述，数据链路层的要紧功能（或说要紧设计问题）包括以下三个方面：
为网络层提供良概念的效劳接口；
处置传输错误；
流量操纵。
效劳类型
能够让数据链路层提供多种不同的效劳，但大多提供以下三种效劳：
无确认的无连接效劳：
源节点向目的节点发送独立的帧，传输前不需要成立逻辑连接，传输后也不要求目的节点进行确认，也确实是说不保证每一个帧能被正确接收。
目的节点可能会将犯错的帧抛弃，但可不能通知源节点，也可不能试图发觉是不是有帧丢失，传输错误的恢复依托高层协议去完成。
这种效劳适用于误码率超级低的传输环境及一些实时业务，大多数局域网利用这一类效劳。
有确认的无连接效劳：
传输前不需要成立逻辑连接，但目的节点关于收到的每一个帧都必需单独进行确认（确信或否定），犯错或丢失的帧需要重发，直到正确接收为止。
这种效劳适用于误码率较高的传输环境，如无线传输环境。
（事实上，要求确认在这儿是一种优化传输效劳的选项，而不是必需的。
）
有确认的面向连接的效劳：
传输前需要成立逻辑连接，为每一个发送的帧成立帧编号并按序发送，目的节点对收到的帧进行检错和确认，犯错或丢失的帧需要重发直至正确接收为止，目的节点的链路层保证向其网络层递交正确有序的数据流。
通过图3-3看一下数据链路层协议在路由器中的位置。
组帧
咱们考察四种方式
字符计数法：
在帧的第一个字段携带帧的长度。
这种方式在帧传输犯错后无法恢复同步，因此不能单独利用。
带有字节填充的标志字节法：
利用特殊的字节（标志字节）来表示帧的开始与终止，当失去同步后，只需要搜索特定的标志字节就能够够了，如图3-5（a）。
为幸免在帧的其它部份显现与标志字节相同的比特模式，采纳了字节填充的方式，即在与特殊字符具有相同比特模式的字符前插入转义字符ESC，如图3-5（b）。
这种方式要依托于特定的字符编码集，灵活性差，处置开销大。
带有比特填充的起止标志法：
利用一个特殊的比特模式（01111110）作为帧的起始与终止标志。
为幸免在帧的其它部份显现与此标志相同的比特模式，采纳了比特填充的方式，即在5个持续的1后插入一个0，如图3-6。
这种方式不依托于特定的字符编码集，灵活性强，处置简单（利用硬件完成）。
物理层编码违例法：
这种方式只适用于那些在物理层编码中利用冗余技术的网络，例如以太网的物理层采纳曼彻斯特编码，它将比特“1”表示成高-低电平对，将比特“0”表示成低-高电平对，而高-高电平对和低-低电平对在编码中没有利用，如此能够用这两种无效的编码标识帧的边界。
过失操纵
过失操纵的要紧内容包括：
过失编码、反馈重传、超时重传、重复帧抛弃、按时器治理等。
流量操纵
基于反馈的流量操纵机制。
2.过失检测与纠正
犯错的类型：
单个错（singleerror）与突发错（bursterror）。
单个错通常由随机的信道热噪声引发，一次只阻碍1位，错误之间没有关联。
突发错通常由刹时的脉冲噪声引发，一次阻碍许多位，用突发长度表示突发错阻碍的最大数据位数。
在实际的通信中，常常发生的错误是突发错。
突发错有利于数据传输，但无益于检测和纠正。
过失编码的类型：
检错码（error-detectingcode）与纠错码（error-correctingcode）。
检错码只能检测到数据传输发生了错误，但不明白错在哪一名上，因此无法自行纠正错误，需要与反馈重传结合起来利用。
纠错码能够明白错误发生在哪一名上，因此能够自行纠正错误。
当信道条件许诺时，通常采纳检错码与反馈重传来检测和纠正错误。
如何检测和纠正错误？
长度为m比特的数据（或称消息）加上r比特的冗余（或称校验位）形成长度为n=m+r比特的码字（codeword）。
两个码字的不同位的个数称为这两个码字之间的海明距离d（HammingDistance），它意味着需要d个位的错误才有可能使一个码字变成另一个码字。
在大多数传输应用中，所有2m个可能的数据信息都是有效的，当计算校验位的方式确信后，就能够够构造出完整的有效码字表（共2m个有效码字）。
但长度为n的码字集中共有2n个码字，显然其中2n-2m个码字是无效的，它们只可能在传输发生错误时显现。
因此，判定是不是显现传输错误的方式确实是判定收到的码字是不是是无效码字，而纠错码纠正错误的方式确实是将收到的无效码字恢复到距其最近的有效码字，显然任何检错和纠错的方式都有必然的漏检概率。
编码集的检错与纠错能力
编码集的海明距离：
编码集中任意两个有效码字间的海明距离的最小值。
编码集的检错和纠错能力与编码集的海明距离有关。
为检测出d比特错误，编码集的海明距离至少应为d+1，奇偶校验是能够检测出1比特错误的检错码。
为纠正d比特错误，编码集的海明距离至少应为2d+1，海明码是能够纠正1比特错误的纠错码。
循环冗余码（CRC码）
这是一种多项式编码，它将位串看成是系数为0或1的多项式。
信息多项式M（x）：
由m个信息比特为系数组成的多项式。
冗余多项式R（x）：
由r个冗余比特为系数组成的多项式。
码多项式T（x）：
在m个信息比特后加上r个冗余比特组成的码字所对应的多项式，表达式为：
T（x）=xr·M（x）+R（x）。
生成多项式G（x）：
两边预先确信誉来计算R（x）的一个多项式。
编码方式：
用对应于G（x）的位串去除对应于xr·M（x）的位串，所得的余数附加到信息比特串的后面一路发送。
检错方式：
用对应于G（x）的位串去除对应于T（x）的位串，假设余数为0那么以为传输正确，不然以为传输错误。
CRC码检错能力强，实现简单快捷，是应用最普遍的检错码。
3.大体数据链路协议
通过三个由简单到复杂的数据链路协议来介绍该层协议的大体设计思想。
在那个地址假设源主机A与目的主机B通过一条单工信道进行通信，且A利用靠得住的面向连接的效劳向B传输数据。
当A的数据链路层收到网络层的一个分组后，将其嵌入到一个数据帧中，即加上帧头（操纵信息）和帧尾（校验），然后传给B的数据链路层。
假设数据链路层能够通过库例程to_physical_layer和from_physical_layer向/从物理层发送/接收帧，且校验部份（帧尾）由发送硬件自动加上和校验，链路层软件可不用关切。
数据链路层还能够通过库例程to_network_layer和from_network_layer向/从网络层发送/接收分组。
数据链路层挪用库例程wait_for_event（&event）等待某个事件的发生，事件的类型从变量event中取得。
假设帧头包括类型、发送序号、确认序号三个域（仅为例如用）。
协议1
这是一个最简单的单工协议，假设数据只在一个方向上传输，信道可不能犯错，且网络层和物理层始终处于预备好状态，因此既不需要过失操纵也不需要流量操纵。
进程如下：
发送方接收方
1）从网络层接收一个分组；1）等待帧到达事件；
2）将分组装入帧的信息域；2）从物理层接收一个帧；
3）将帧传给物理层；3）将分组（帧的信息域）传给网络层；
4）返回1）4）返回1）
由于不需要确认，也就不需要帧序号。
协议2
仍然假定是单工通信，且信道可不能犯错，可是接收端的处置能力有限，需要操纵发送方的速度，即流量操纵。
在那个地址需要引入反馈，要求接收端在预备好接收下一帧时，向发送方发还一个响应帧；而发送方在收到响应帧后，才能发送下一帧，这称为停-等。
进程如下：
发送方接收方
1）从网络层接收一个分组；1）等待帧到达事件；
2）将分组装入帧的信息域；2）从物理层接收一个帧；
3）将帧传给物理层；3）将分组（帧的信息域）传给网络层；
4）等待响应帧；4）发送响应帧；
5）响应帧抵达，返回1）5）返回1）
由于每次只发送一个帧，取得响应后再发下一帧，且可不能犯错，因此可不能有重发的需要，也就不需要帧序号。
协议3
仍然假定是单工通信，可是信道可能会犯错，接收端处置能力也有限。
链路层必需保证每一个帧正确抵达接收端，且发送端不能以太快的速度发送，因此，在那个地址既需要过失操纵也需要流量操纵。
采纳协议2中的停-等方式，发送方每次只发送一个帧，当那个帧被正确接收后才能发送下一帧，假设该帧未在规定的时刻内取得确认（超时），那么重发该帧；接收端对每一个收到的帧进行校验，对正确收到的帧发还确认，错误的帧抛弃。
由于需要区分新、旧两个帧，利用1比特的帧序号。
进程如下：
发送方
1）初始化发送序号（next_frame_to_send=0）；
2）从网络层接收一个分组，放入缓冲区；
3）从缓冲区中掏出分组构造一个帧：
将缓冲区中的分组拷入帧的信息域；
将next_frame_to_send拷入序号域；
4）将帧传给物理层；
5）启动相关的计时器；
6）等待事件发生（帧抵达，收到坏帧，超时）；
7）事件发生：
1事件为帧抵达：
从物理层接收一个帧，检查帧的确认序号域，
假设是对所发帧的确认（ack=next_frame_to_send），终止相关的计时器，从网络层接收下一个分组，放入缓冲区，发送序号加1，返回3）；
假设不是对所发帧的确认，直接返回3）；（缓冲区内容和发送序号均不变）
2事件为其它（收到坏帧，超时）：
返回3）；（缓冲区内容和发送序号均不变）
接收方
1）初始化期待接收的帧序号（frame_expected=0）；
2）等待帧的抵达；
3）从物理层接收一个帧，检查帧的发送序号域（seq），
若是是期待接收的帧（seq=frame_expected），将帧中携带的分组交给网络层，frame_expected加1，执行4）；
假设不是期待接收的帧（一个重复帧），执行4）；
4）发还对收到帧的确认（确认帧的ack等于收到帧的seq）；
5）返回2）。
4.滑动窗口协议
前面的协议都假定数据帧沿着一个方向传输，但事实上大多数的通信都是双向的。
当两边都有数据发送时，将确认序号携带在数据帧中传输能够减少开销，这称为捎带应答（piggybacking）。
捎带应答带来的一个问题是，当需要发送确认时没有要发送的数据帧如何办？
这能够让确认信息推延一点时刻再发送，若是仍然没有数据帧要发送，再用一个单独的帧进行确认。
以下三个协议都是用于双向数据传输的协议，且都属于滑动窗口协议，但它们的效率、复杂度及对内存的需求都不同。
在滑动窗口协议中，每一个要发送的帧都包括一个序号，范围是从0到某个最大值，最大值一般是2n-1，n为帧序号的长度。
滑动窗口协议的要点是，任何时刻发送进程要保护一组帧序号，对应于一组已经发送但尚未被确认的帧，这些帧称为落在发送窗口内；类似地，接收进程也要保护一组帧序号，对应于一组许诺接收的帧，这些帧称为落在接收窗口内。
发送窗口中的序号代表已发送但尚未确认的帧，其中窗口下沿代表最先发送但至今尚未确认的帧。
当发送窗口尚未达到最大值时，能够从网络层接收一个新的分组，然后将窗口上沿加1，并将新的上沿序号分派给新的帧；当收到对窗口下沿帧的确认时，窗口下沿加1。
由于每一个帧都有可能传输犯错，因此发送窗口中的帧都必需保留在缓冲区里以备重传，直至收到确以为止。
当发送窗口达到最大值时，停止从网络层接收数据，直到有一个缓冲区空出来为止。
接收窗口中的序号代表许诺接收的帧，任何落在窗口外的帧都被抛弃，落在窗口内的帧寄存到缓冲区里。
当收到窗口下沿帧时，将其交给网络层，并产生一个确认，然后窗口整体向前移动一个位置。
和发送窗口不同，接收窗口的大小是不变的，老是维持初始时的大小。
接收窗口大小为1，意味着数据链路层只能顺序接收数据，当接收窗口大于1时不是如此，但不管如何，数据链路层必需按顺序将数据递交给网络层。
图3-13。
1位滑动窗口协议
该协议利用停-等方式，因此只需要1比特长的帧序号。
帧头中至少包括seq和ack两个域，ack用于对正确收到的帧的序号进行确认。
由于支持双向传输，因此每一个协议实体需要同时完成发送和接收两个功能。
进程如下：
1）初始化发送序号和期待接收的帧序号：
next_frame_to_send=0，frame_expected=0；
2）从网络层接收一个分组，放入缓冲区；
3）从缓冲区中掏出分组构造一个帧：
将缓冲区中的分组拷入帧的信息域；
将next_frame_to_send拷入发送序号（seq）域；
将1-frame_expected拷入确认序号（ack）域；（初始化后两边发送的第一个帧的序号均为0，而该实体在发送第一个帧时尚未收到另一方发来的帧0，因此ack域必需为1）
4）将帧传给物理层；
5）启动相关的计时器；
6）等待事件发生（帧抵达，收到坏帧，超时）；
7）事件发生：
1事件为帧抵达：
从物理层接收一个帧，
a）检查帧的seq域，假设正是期待接收的帧（seq=frame_expected），将帧中携带的分组交给网络层，frame_expected加1，继续b）；（作为接收实体的处置，假设不是期待接收的帧，frame_expected不变）
b）检查帧的ack域，假设是等待确认的帧（ack=next_frame_to_send），终止相关的计时器，从网络层接收一个新的分组放入缓冲区，next_frame_to_send加1，到8）；（作为发送实体的处置，假设不是等待确认的帧，缓冲区内容及next_frame_to_send均不变）
2其它事件（收到坏帧，超时）：
到8）；（缓冲区内容及两个序号变量均没变）
8）用缓冲区中的分组、next_frame_to_send和1-frame_expected构造一个帧；
9）传给物理层；
10）启动计时器；
11）回到6）。
在正常情形下，发送方和接收方交替发送；但当发送方和接收方同时向对方发送，或超时设置得太短时，会造成没必要要的重发，但协议也能够正常运行，见图3-15。
GoBackN
直到此刻，咱们一直假定信号的传播延迟能够忽略不计，但事实上有些时候是不能忽略的，比如在卫星信道上（例）。
若是信道的数据速度为bbit/s，帧的长度为Lbits，信号的来回延迟为R秒，那么线路的效率为Lb/（L+bR）。
若是咱们在等待确认的时候多发送一些帧，就能够够提高线路的效率，这事实上许诺发送窗口包括多个未被确认的帧，这种技术称为管道化（pipelining）。
当信号传播延迟远大于帧的传输时刻时，适合采纳那个技术。
当管道化技术成立在不靠得住的信道上时会有一些问题。
比如，若是位于帧流中的某个帧丢失或损坏了，会发生什么情形？
在发送进程发觉犯错前，大量的后继帧会抵达接收方；当一个坏帧抵达接收方时，显然会被接收方抛弃，那么后面到来的帧如何处置？
有两种大体的方式来处置以上问题，一种方式称为gobackn，接收进程抛弃所有的后继帧，而且不通知发送进程。
该策略对应接收窗口为1的情形，即只能按顺序接收帧，当发送进程超时后，必需按顺序重传所有未被确认的帧，如图3-16（a）。
若是错误率高的话，这种方式会浪费很多带宽，但对内存需求不大。
另一种方式称为选择重传（对应接收窗口大于1的情形），只若是落入接收窗口且校验正确的帧，都要接收下来放到缓冲区里，如此当发送进程意识到某个帧犯错时，只是重传此帧而不是所有的后继帧，如图3-16（b）。
选择重传通常利用NAK对校验犯错或疑为丢失的帧进行确认，以便发送进程尽快重传该帧。
若是第二次重传成功，接收方的数据链路层中会有许多按顺序排列的正确帧，这些帧能够一路交给网络层，并只对最高序号的帧进行确认。
当窗口专门大时，这种方式需要大量的数据链路层内存，但它不浪费带宽。
Gobackn的进程如下：
1）初始化：
开网络层许诺；
ack_expected=0；（发送窗口下沿）
next_frame_to_send=0，frame_expected=0；
nbuffered=0；（发送窗口大小）
2）等待事件发生（网络层预备好，帧抵达，收到坏帧，超时）；
3）事件发生：
1事件为网络层预备好：
从网络层接收一个分组，放入相应的缓冲区；
发送窗口大小加1；
利用缓冲区中的分组、next_frame_to_send和frame_expected构造帧，发送；（ack中的值表示该序号及该序号之前所有的帧已全数正确收到）
next_frame_to_send加1；
跳转4）；
2事件为帧抵达：
从物理层接收一个帧，
a）检查帧的seq域，假设正是期待接收的帧（seq=frame_expected），将帧中携带的分组交给网络层，frame_expected加1（修改接收窗口），继续b）；
b）检查帧的ack域，假设ack落于发送窗口内，说明该序号及其之前所有序号的帧均已正确收到，因此终止这些帧的计时器，修改发送窗口大小及发送窗口下沿值，将这些帧去掉；（用一个while循环来完成）
c）跳转4）；
3事件是收到坏帧：
跳转4）；
4事件是超时：
next_frame_to_send=ack_expected，从发生超时的帧开始重发发送窗口内的所有帧，然后执行4）；
4）假设发送窗口大小小于所许诺的最大值（MAX-SEQ），开网络层许诺，不然关网络层许诺；（判定发送窗口是不是达到最大值）
5）返回2）。
那个协议有一个问题，没有考虑到当某个方向上没有数据要发送时，要对收到的帧进行单独确认。
在收到期待的帧后应该启动一个ACK超时计时器，当发生超时事件时，判定哪个计时器超时，假设是ACK计时器超时，应该单独发送一个确认帧。
而当发送了一个数据包时，应将被捎带确认的帧的ACK计时器终止。
利用gobackn协议，发送窗口的大小不能超过2n-1。
用书上的例子说明。
选择性重传
在该协议中，发送方的窗口大小从0开始增加到某个预定的最大值，而接收方的窗口老是维持固定大小并等于该最大值。
接收窗口内的每一个序号都有一个缓冲区，并有一名指示缓冲区是空仍是满。
当一个帧抵达时，只要其序号落在接收窗口内且此前并未收到过（相应缓冲区为空），就同意此帧并存于相应的缓冲区中；仅当序号比它小的所有帧都已递交给了网络层，此帧才会被提交给网络层。
选择重传的进程如下：
1）初始化：
类似gobackn的初始化，但增加了与接收窗口相关的内容，如设定接收窗口的大小、清空缓冲区满标志等；
2）等待事件发生（帧抵达，收到坏帧，数据帧超时，网络层预备好，ACK超时）；
3）事件发生：
1事件为网络层预备好：
从网络层接收一个分组，组帧发送，修改相关参数，与gobackn的处置同；跳转到4）；
2事件为帧抵达：
从物理层接收一个帧，
a）假设为数据帧，
i）假设不是期待接收的帧且未发送过NAK，那么发送一个NAK帧，要求重发指定序号的帧（frame_expected）；不然启动ACK计时器；继续ii）；
ii）假设收到的帧落在接收窗口内且此前未收到过，那么放入相应缓冲区并设置缓冲区满标志；继续iii）；
iii）假设接收窗口下沿帧已经抵达，那么从该帧开始将持续的假设干个帧交给网络层，并修改相应参数（缓冲区满标志，接收窗口范围），启动ACK计时器；跳转到c）；
b）假设为NAK帧，且请求重发的帧落在当前的发送窗口内，那么重发那个帧；
c）假设从发送窗口下沿开始持续的假设干个帧已被确认，那么终止这些帧的计时器，修改发送窗口大小及发送窗口下沿值将这些帧去掉；跳转到4）；
3事件为收到坏帧：
若是尚未发送过NAK，那么发送一个NAK；跳转到4）；
4事件为超时（数据帧超时）：
重发超时的帧；跳转到4）；
5事件为ACK超时：
为指定的帧发送单独的确认帧；跳转到4）；
4）假设发送窗口大小小于所许诺的最大值（NR_BUFS），开网络层许诺，不然关网络层许诺；
5）返回2）。
利用选择重发协议，发送窗口不能大于2n-1。
用书上的例子说明。
5.数据链路协议举例
HDLC
这是ISO公布的一个面向比特的全双工数据链路协议。
帧格式如图3-24所示，除标志外包括地址、操纵、信息和校验和几个部份，其中信息部份能够没有，因此有效帧长度至少为32比特。
帧标志：
01111110，用于表示帧的边界，也用于帧间填充。
利用比特填充保证数据的透明传输。
地址：
在点-多点线路（多终端）顶用于区分各个终端，而在点-点线路顶用于区分命令和响应。
操纵：
用于组成各类命令与响应，是HDLC的关键。
信息：
能够包括任何信息，原那么上没有长度限制。
校验和：
CRC编码。
帧的类型：
信息帧、监控帧和无编号帧。
信息帧：
用于携带数据；
监控帧：
用于过失操纵和流量操纵；
无编号帧：
用于链路治理。
这三种帧的操纵字段如图3-25。
协议采纳滑动窗口机制，利用3比特帧序号。
seq：
帧序号；
next：
下一个期待接收的帧序号；
P/F：
打听/终止位，有多种用途，在点-多点线路中可用于选择一个终端，在有些协议中可由发送站用来要求接收站当即发送一个监控帧，还有其它一些用途。
type：
决定监控帧的类型：
类型0（RECEIVEREADY）：
确信性确认帧，用来指示下一个希望收到的帧，当没有效于捎带的反向传输时利用此帧。
类型1（REJECT）：
否定性确认帧，要求从next域所指示的序号开始重发尔后所有的帧。
类型2（RECEIVENOTREADY）：
确认直到（不包括）next的所有帧，但要求发送方暂停发送。
类型3（SELECTIVEREJECT）：
要求重传next域指定的帧。
有些协议没有这种帧。
modifier：
5个修正位能够组成最多32种链路命令和响应（无编号帧），事实上没有效到这么多。
常见的命令或响应有：
断开连接、置链路模式、帧拒绝、无编号响应、无编号数据等。
Internet中的点-点数据链路层协议
在Internet中有很多地址需要用到点-点线路，如大量家庭用户利用拨号线路上网、集团用户利用租用线路将局域网连到因特网上，而通信子网中的路由器与路由器之间几乎都采纳专线（专门是光纤）进行互连。
在这些点-点线路上，需要某种数据链路层协议完成成帧、过失操纵和流量操纵等功能。
PPP
PPP是因特网中普遍利用的一种点-点数据链路协议，它有检错能力、支持多种网络层协议、支持IP地址的动态分派、支持身份认证等多种功能。
PPP有以下三个要紧特色：
提供一种组帧的方式用于区分帧的边界，并可支持过失检测；
提供一种链路操纵协议，用于链路的成立、测试、协商及拆除；
提供一组网络操纵协议，用于支持多种网络层协议；专门是支持IP的NCP支持IP地址的动态分派。
利用PPP通信的进程（图3-28）：
第一在两个modem之间成立物理连接；
升级会员 