第3章《数据链路层》

第三章数据链路层§3.1数据链路层的基本概念§3.5局域网中的数据链路层§3.4Internet中的数据链路层§3.3流量控制§3.2差错控制第3章数据链路层第一页，共61页。第一页，共61页。3.1数据链路层的基本概念3.1.1链路与数据链路数据链路层的最基本功能是将物理层提供的原始传送比特流可能出错的物理连接改造成为逻辑上无差错的数据链路。链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。链路只是通信路径的一部分，又称为物理链路。数据链路(datalink)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。第二页，共61页。第二页，共61页。数据链路层的基本功能数据链路层的信息传送机制是利用物理层提供的物理通路，首先在相邻节点之间建立数据链路，然后把将要传送的数据封装成帧，并加入应答、差错控制、流量控制信息，使有差错的物理线路变成无差错的数据链路，从而为网络层提供可靠的信息。第三页，共61页。第三页，共61页。3.1.2封装成帧封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。首部和尾部的一个重要作用就是进行帧定界。帧结束帧首部IP数据报帧的数据部分帧尾部MTU数据链路层的帧长开始发送帧开始第四页，共61页。第四页，共61页。用控制字符进行帧定界的方法举例SOH装在帧中的数据部分帧帧开始符帧结束符发送在前EOT注意：帧定界符SOH(StartOfHeader)和EOT(EndOfTransmission)只是控制字符的名称，并非是说SOH(或EOT)是由S,O,H(或E,O,T)三个字符组成！5第五页，共61页。第五页，共61页。IP数据报1010……0110帧取出数据链路层网络层链路结点A结点B物理层IP数据报1010……0110帧装入结点A结点B帧帧3.1.3数据链路层的通信模型6第六页，共61页。第六页，共61页。3.1.4透明传输由于帧的开始和结束的标记使用了专门的控制字符，因此，在传输的数据中就应尽量避免出现与帧定界控制字符一样的编码，否则就会发生帧定界错误识别。SOHEOT出现了“EOT”被接收端当作无效帧而丢弃被接收端误认为是一个帧数据部分EOT完整的帧发送在前第七页，共61页。第七页，共61页。解决透明传输问题：发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是1B)。字节填充(bytestuffing)或字符填充(characterstuffing)——接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。第八页，共61页。第八页，共61页。SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符用字节填充法解决透明传输的问题SOH9第九页，共61页。第九页，共61页。3.2差错控制3.2.1差错产生的原因与差错类型差错是指接收端收到的数据与发送端实际发出的数据出现不一致的现象。差错的产生是因为在通信线路上有噪声干扰。通信信道的噪声分为两类：热噪声和冲击噪声。热噪声是由线路本身的电子热运动产生的；冲击噪声是由外界电磁干扰引起的。第十页，共61页。第十页，共61页。3.2.2误码率的定义误码率：是指二进制比特在数据传输系统中被传错的概率。对差错的处理有两种处理策略：差错检测(errordetecting)

前向纠错或简称为纠错(forwarderrorcorrection)差错控制编码：信息位(k)＋冗余位(r)检错码和纠错码检错码：自动发现差错，然后通知对方重传，双向信道，发送方缓存发送的数据纠错码：不仅能发现差错而且能够自动纠正11第十一页，共61页。第十一页，共61页。3.2.3差错控制编码差错控制最常用的方法是采用差错控制编码：先按照某种编码方式为其生成冗余位，再将信息位加上冗余位构成一个码字再发送。接收端收到码字后查看信息位和冗余位，并检验冗余位以发现传输过程中是否有差错发生。差错控制编码又可分为检错码和纠错码。检错码：自动发现在传输过程中是否出现传输差错的编码技术；纠错码：不仅能发现传输差错而且能自动纠正差错的编码技术。12第十二页，共61页。第十二页，共61页。3.2.4循环冗余编码在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。循环冗余码(CRC)的工作原理：收发双方预先约定一个特征值G(x)；发送方将待发数据F(x)与特征值进行运算，获得一段冗余码R，将其组合一起发送出去。接收方在收到带冗余码的数据串[F(x)+R]后，将其与特征值G(x)进行运算，若运算结果为0则认为传输过程未产生差错，接收并处理；反之则认为传输过程有差错，直接丢弃。13第十三页，共61页。第十三页，共61页。循环冗余码的计算步骤（发送方）：由生产多项式G(x)计算出特征值作为除数，并确定冗余码长度n；将待发数据F(x)左移n位作为被除数；二者做二进制除运算，直到除不尽为止，得余数R(注意保持n位长度)R即循环冗余码FCS。第十四页，共61页。第十四页，共61页。CRC校验的实例待发送的数据比特序列对应的多项式为：f(x)=x5+x4+x+1；生成多项式G(x)=x4+x3+1。第十五页，共61页。第十五页，共61页。标准CRC生成多项式G（x）CRC-12G（x）=x12+x11+x3+x2+x+1CRC-16G（x）=x16+x15+x2+1CRC-CCITTG（x）=x16+x12+x5+1CRC-32G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+

x2+x+1第十六页，共61页。第十六页，共61页。练习(1)已知：信息码:110011信息多项式:F(X)=X5+X4+X+1

生成码:11001

生成多项式:G(X)=X4+X3+1(r=4)

求：循环冗余码和码字。(2)已知：接收码字:1100111001多项式:T(X)=X9+X8+X5+X4+X3+1

生成码:11001

生成多项式:G(X)=X4+X3+1(r=4)

求：码字的正确性。若正确，则指出冗余码和信息码。

第十七页，共61页。第十七页，共61页。检测出差错只要得出的余数R不为0，就表示检测到了差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。第十八页，共61页。第十八页，共61页。应当注意仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。

第十九页，共61页。第十九页，共61页。3.2.5反馈重传机制接收端通过检错码检查数据帧是否出错，一旦发现错误，通常采用反馈重发（automaticrequestforrepeat，ARQ）方法来纠正。20第二十页，共61页。第二十页，共61页。3.3流量控制3.3.1流量控制概述所谓流量控制就是调整发送方发送信息的速率，使接收方能够及时接收并处理信息。流量控制主要是为了防止网络拥塞、数据淹没与死锁等问题所采取的一种措施。流量控制的常用思路有两种：基于反馈和基于速率。基于反馈的流量控制（feedback-basedflowcontrol：接收方给发送方返回信息，通知它可以发送更多的数据，或告诉它本方的情况怎样，最多能够发送多少数据过来。基于速率的流量控制（rate-basedflowcontrol：限制发送方传输数据的速率而无须利用接收方的反馈信息。基于速率的方案仅在传输层中实现，在数据链路层中通常使用的机制是基于反馈的流量控制。第二十一页，共61页。第二十一页，共61页。3.3.2滑动窗口机制在任意时刻，发送方都维持了一个连续的允许发送的帧的序号，称为发送窗口；同时，接收方也维持了一个连续的允许接收的帧的序号，称为接收窗口。22第二十二页，共61页。第二十二页，共61页。1位滑动窗口协议停等协议（stop-and-wait）：规定发送方每发送一帧后就要停下来，等待接收方已正确接收的确认（acknowledgement）返回后才能继续发送下一帧。

23第二十三页，共61页。第二十三页，共61页。注意：可能出现的错误错误1：数据帧出错——校验与确认错误2：数据帧丢失——超时错误3：解决重复帧的问题——序号24第二十四页，共61页。第二十四页，共61页。后退N帧协议25第二十五页，共61页。第二十五页，共61页。选择重传协议26第二十六页，共61页。第二十六页，共61页。3.4Internet中的数据链路层大多数广域网的基础设施都是以点到点方式建设的。针对点对点链路，早期广泛使用能实现可靠传输的高级链路控制HDLC(High-levelDatalinkControl)协议，但随着通信线路质量的大大改善，现今使用最广泛的数据链路层协议是PPP(Point-to-PointProtocol)协议。用户至因特网已向因特网管理机构申请到一批

IP地址ISP接入网PPP

协议第二十七页，共61页。第二十七页，共61页。

3.4.1PPP协议的组成PPP协议的最大特点就是—简单PPP协议有三个组成部分一个将IP数据报封装到串行链路的方法。链路控制协议LCP(LinkControlProtocol)。网络控制协议NCP(NetworkControlProtocol)。第二十八页，共61页。第二十八页，共61页。3.4.2PPP的帧格式第二十九页，共61页。第二十九页，共61页。3.4.2PPP的帧格式标志字段

F

为0x7E（符号“0x”表示后面的字符是用十六进制表示。十六进制的

7E

的二进制表示是）。地址字段

A

只置为0xFF。地址字段实际上并不起作用。控制字段

C

通常置为0x03。PPP是面向字节的，所有的PPP

帧的长度都是整数字节。MTU—最大传输单元第三十页，共61页。第三十页，共61页。

透明传输问题当PPP用在同步传输链路时，协议规定采用硬件来完成比特填充法（和HDLC的做法一样）。当PPP用在异步传输链路时，就使用一种特殊的字符填充法。第三十一页，共61页。第三十一页，共61页。①字符填充法将信息字段中出现的每一个0x7E字节转变成为2字节序列(0x7D,0x5E)。若信息字段中出现一个0x7D的字节,则将其转变成为2字节序列(0x7D,0x5D)。若信息字段中出现ASCII码的控制字符（即数值小于0x20的字符），则在该字符前面要加入一个0x7D字节，同时将该字符的编码加以改变。第三十二页，共61页。第三十二页，共61页。②零比特填充法在发送端，先扫描整个信息字段，只要发现有5个连续1，则在其后立即填充一个0位。显而易见经过这种零比特填充后的数据，就可以保证在信息字段中不会出现6个连续的1。在接收端收到一个帧时，先找到标志字段F以确定一个帧的边界，接着对其中的比特流进行扫描：每当发现5个连续1时，若其后为0位，就把这5个连续1后的0删除，以还原成原来的信息比特流，直到另一个标志字段F（6个连续的1）出现则完成一个帧的接收。第三十三页，共61页。第三十三页，共61页。3.4.3PPP协议工作过程链路的建立和配置协调：当用户拨号接入ISP时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。PC机向路由器发送一系列的LCP分组（封装成多个PPP帧）。这些分组及其响应选择一些PPP参数，如：认证方式；最大数据传输单元等；链路质量检测：可选，确定其能否为上层所选定的网络协议提供足够的支持；网络协议配置与协调：进行网络层配置，NCP帧给新接入的PC机分配一个临时的IP地址，使PC机成为因特网上的一个主机。建立一条完整的链路；关闭链路：通信完毕时，NCP释放网络层连接，收回原来分配出去的IP地址。接着，LCP释放数据链路层连接。最后释放的是物理层的连接。第三十四页，共61页。第三十四页，共61页。设备之间无链路链路静止链路建立鉴别网络层协议链路打开链路终止物理链路LCP链路已鉴别的LCP链路已鉴别的LCP链路和NCP链路物理层连接建立LCP配置协商鉴别成功或无需鉴别NCP配置协商链路故障或关闭请求LCP链路终止鉴别失败LCP配置协商失败图3-15PPP协议状态图第三十五页，共61页。第三十五页，共61页。3.5局域网中的数据链路层3.5.1以太网的发展数据链路层使用的信道主要有两种类型：一种是使用一对一通信方式的点对点信道；另一种则是使用一对多通信方式的广播信道。在广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送。局域网是使用广播信道的典型代表。以太网技术已经成为了目前最流行的局域网技术第三十六页，共61页。第三十六页，共61页。最初设计的以太网

共享式以太网（同轴电缆）第三十七页，共61页。第三十七页，共61页。集线器的出现

共享式以太网（HUB）第三十八页，共61页。第三十八页，共61页。交换机的出现

交换式以太网以太网第三十九页，共61页。第三十九页，共61页。3.5.2CSMA/CD协议最初的以太网是将许多计算机都连接到一根总线上。当初认为这样的连接方法既简单又可靠，因为总线上没有有源器件。B向

D发送数据CDAE匹配电阻（用来吸收总线上传播的信号）匹配电阻不接受不接受不接受接受B只有D接受B发送的数据第四十页，共61页。第四十页，共61页。

CSMA/CD---载波监听多点接入/碰撞检测CSMA/CD表示CarrierSenseMultipleAccesswithCollisionDetection。CSMA/CD的基本思想可以归纳为以下3点先听后发边发边听，碰撞停止退避重传，碰撞过多放弃发送第四十一页，共61页。第四十一页，共61页。①先听后发当以太网中的一台主机需要利用共享的总线发送数据时，首先要监听总线是否空闲：信道空闲，开始发送数据；信道上有其他主机在发送数据，忙则等待；第四十二页，共61页。第四十二页，共61页。②边发边听，碰撞停止先听后发并不能完全消除冲突(或称为碰撞)---时延。1kmABt碰撞t=2

A检测到发生碰撞t=

B发送数据B检测到发生碰撞t=t=0单程端到端传播时延记为

第四十三页，共61页。第四十三页，共61页。t=

B检测到信道空闲发送数据t=

/2发生碰撞ABABABt=0A检测到信道空闲发送数据ABt=B检测到发生碰撞停止发送STOPt=2

A检测到发生碰撞STOPAB44第四十四页，共61页。第四十四页，共61页。争用期最先发送数据帧的站，在发送数据帧后至多经过时间2

（端到端往返时延）就可知道发送的数据帧是否遭受了碰撞。以太网的端到端往返时延2称为争用期，或碰撞窗口。经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。第四十五页，共61页。第四十五页，共61页。强化碰撞：人为干扰信号当发送数据的站一旦发现发生了碰撞时，除立即停止发送数据外，还要再继续发送若干比特的人为干扰信号(jammingsignal)，以便让所有用户都知道现在已经发生了碰撞。第四十六页，共61页。第四十六页，共61页。数据帧干扰信号TJABTBtB发送数据A检测到冲突开始冲突信道占用时间A发送数据第四十七页，共61页。第四十七页，共61页。③退避重传，碰撞过多放弃发送截断二进制指数退避(truncatedbinaryexponentialbackoff)算法：发生碰撞的站在停止发送数据后，要推迟（退避）一个随机时间才能再发送数据。确定基本退避时间(基数)，一般定为2τ定义一个参数K，K为重传次数，K＝Min[重传次数，10]，可见当重传不超过10次则K等于重传次数，当重传次数超过10次，K就始终等于10。然后从离散型整数集合{0，1，2，……，(2K－1)}中，随机取出一个数记做R。那么重传所需要的退避时间T就等于R倍的基本退避时间。即：T＝R×2τ。当重传16次都不成功就丢弃该帧，放弃发送并报告给上层协议。第四十八页，共61页。第四十八页，共61页。CSMA/CD发送方的工作原理第四十九页，共61页。第四十九页，共61页。

3.5.3以太网的MAC层以太网MAC层地址

在广播信道上也经常希望进行一对一的通信，因此需要给广播信道上的每台计算机分配至少一个互异的数据链路层地址。数据链路层地址又称为MAC地址或物理地址。MAC地址是一个48比特的二进制数，它被固化在每一个网络适配器的ROM中。MAC地址有三种形式：单播地址组播地址广播地址第五十页，共61页。第五十