点到点信道的数据链路层

计算机网络技术第三章点到点信道的数据链路层本章主要内容停止等待协议连续ARQ协议因特网的点对点协议PPP计算机网络技术3.1数据链路层的基本概念局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动3.1.1数据链路层的简单模型计算机网络技术(a)数据链路层结点A结点B帧(b)发送帧接收链路IP数据报1010……0110帧取出数据链路层网络层链路结点A结点B物理层IP数据报1010……0110帧装入数据链路层传送的是帧计算机网络技术3.1.2链路和数据链路链路(link)即物理链路，是从一个结点到相邻结点的一段物理线路，中间没有任何其他的交换结点。一条链路只是一条路径的一个组成部分。数据链路(datalink)即逻辑链路，除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。计算机网络技术3.2三个基本问题(1)帧定界(2)透明传输(3)差错控制计算机网络技术3.2.1帧定界帧定界(framing)就是确定帧的界限。帧结束帧首部IP数据报帧的数据部分帧尾部MTU数据链路层的帧长从这里开始发送帧开始计算机网络技术用控制字符进行帧定界的方法举例SOH装在帧中的数据部分帧帧开始符帧结束符发送在前EOT计算机网络技术3.2.2透明传输SOHEOT出现了“EOT”被接收端当作无效帧而丢弃被接收端误认为是一个帧数据部分EOT完整的帧发送在前计算机网络技术SOHSOHESCSOHEOTESCESCzESCyESCzESCx原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符用字节填充法解决透明传输的问题计算机网络技术3.2.3差错检测检错奇偶校验循环冗余校验（CRC）计算机网络技术奇/偶校验的规则是在原数据位后附加一个校验位，将其值置为“0”或“1”，使附加该位后的整个数据码中“1”的个数成为奇数或偶数。使用奇数个“1”进行校验的方案被称为奇校验；对应于偶数个“1”的校验方案被称为偶校验。奇/偶校验计算机网络技术循环冗余检验在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。在发送端，先把数据划分为组。假定每组k位。假设待传送的一组数据M=101001（现在k=6）。我们在M的后面再添加供差错检测用的r位冗余码一起发送。计算机网络技术①设f（x）为k阶信息码多项式，G（x）为r阶生成码多项式；②用模2除法进行xrf（x）/G（x），得到余式R（x），R（x）为r阶冗余码多项式；③用模2减法进行xrf（x）-R（x），得到待传送的CRC码多项式。CRC码的计算过程：计算机网络技术例如，已知要传送的信息为1010001101，G(X)=X5+X4+X2+1，计算冗余码的过程和结果如下：∴传送序列T(x)=101000110101110计算机网络技术接收端对收到的每一帧进行CRC检验接收方收到后，用G(x)除多项式，若余数R0，则传输有错,就丢弃。若得出的余数R=0，则判定这个帧没有差错，就接受(accept)。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。计算机网络技术思考：习题3-17计算机网络技术注意仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。计算机网络技术3.3停止等待协议两台计算机通过一条数据链路进行通信的简化模型假定１：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定２：不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机。计算机网络技术具有最简单流量控制的数据链路层协议B计算机网络技术算法发送结点：(1)从主机取一个数据帧；(2)将数据帧送到数据链路层的发送缓存；(3)将发送缓存中的数据发送出去；(4)等待；(5)若收到由接收结点发过来的信息，则从主机取一个新的数据帧，然后转到(2)计算机网络技术算法接收结点：(1)等待；(2)若收到由发送结点发过来的数据帧,则将其放入数据链路层的接收缓存；(3)将接收缓存中的数据帧上交主机；(4)向发送结点发一信息,表示数据帧已上交主机；(5)转到(1)计算机网络技术3.3.1停止等待协议的工作原理数据帧出错确认帧出错ACKn表示“第n–1号帧已经收到，现在期望接收第n号帧”。正常情况ACK1ACK0计算机网络技术发送结点：(1)从主机取一个数据帧，送交发送缓存。(2)V(S)←0。(发送状态变量的初始化)(3)N(S)←V(S)。(发送序号N(S))(4)将发送缓存中的数据帧发送出去。(5)设置超时计时器。(6)等待。{等待以下(7)和(8)中最先出现的一个}(7)收到确认帧ACKn，若n=1–V(s)，则：从主机取一个新的数据帧，放入发送缓存；V(S)←[1V(S)]，转到(3)。否则，丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到(4)。3.3.2停止等待协议的算法ACK1ACK0计算机网络技术接收结点：(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)。ACK1ACK0计算机网络技术思考：习题3-4计算机网络技术(1)在发送端,在发送数据之前,都必须将发送状态变量V(S)的值写到数据帧的发送序号N(S)上。(2)发送端在发送完数据帧时,必须在其发送缓中暂时保留这个数据帧的副本。(3)在接收端只接受序号正确的数据帧,并发送确认。计算机网络技术在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。如果收到接收端发来的确认帧，那么还可以继续发送数据帧。要点：3.4发送窗口大于1的ARQ协议计算机网络技术01234523456DATAtftout重传送主机丢弃送主机出错时间AB3.4.1连续ARQ协议的工作原理计算机网络技术发送端和接收端分别设定发送窗口和接收窗口。发送窗口用来对发送端进行流量控制。发送窗口的大小WT代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。3.4.2滑动窗口的概念计算机网络技术(1)发送窗口内的帧是允许发送的帧,而不考虑有没有收到确认.(2)每发送完一个帧,允许发送的帧数就减1.(3)如果所允许发送的帧都发送完了,但还没有收到任何确认,那就不能再发送任何帧了.(4)每收到一个帧的确认,发送窗口就向前(向右)滑动一个帧的位置.计算机网络技术发送窗口01234567012WT不允许发送这些帧允许发送5个帧(a)01234567012不允许发送这些帧还允许发送4个帧WT已发送(b)01234567012不允许发送这些帧WT已发送(c)01234567012不允许发送这些帧还允许发送3个帧WT已发送已发送并已收到确认(d)计算机网络技术在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续ARQ协议中，接收窗口的大小WR=1。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。计算机网络技术不允许接收这些帧01234567012WR准备接收0号帧(a)不允许接收这些帧01234567012WR准备接收1号帧已收到(b)不允许接收这些帧01234567012WR准备接收4号帧已收到(c)发ACK1计算机网络技术发送方接收方帧1234567869ACKACKNAK10出错只重传帧6选择重传ARQ协议的工作原理3.4.4选择重传ARQ协议计算机网络技术思考：习题3-11计算机网络技术a.无确认的无连接服务b.有确认的无连接服务c.有确认的面向连接服务3.4.5数据链路层所提供的基本服务计算机网络技术3.5点对点协议PPP3.5.1点对点协议的特点现在全世界使用得最多的数据链路层协议是点对点协议PPP(Point-to-PointProtocol)。用户使用拨号电话线接入因特网时，一般都是使用PPP协议。计算机网络技术用户到ISP的链路使用PPP协议用户至因特网已向因特网管理机构申请到一批IP地址ISP接入网PPP协议计算机网络技术PPP协议应满足的需求简单封装成帧透明性多种网络层协议多种类型链路差错检测检测活跃度（即检测连接状态）最大传送单元（MTU）网络层地址协商数据压缩协商计算机网络技术PPP协议不需要的功能纠错流量控制序号多点线路半双工或单工链路计算机网络技术PPP协议的组成1992年制订了PPP协议。经过1993年和1994年的修订，现在的PPP协议已成为因特网的正式标准[RFC1661]。PPP协议有三个组成部分一个将IP数据报封装到串行链路的方法。链路控制协议LCP(LinkControlProtocol)。网络控制协议NCP(NetworkControlProtocol)。计算机网络技术3.5.2PPP协议的帧格式标志字段F=0x7E（符号“0x”表示后面的字符是用十六进制表示。十六进制的7E的二进制表示是01111110）。地址字段A只置为0xFF。地址字段实际上并不起作用。控制字段C通常置为0x03。先发送IP数据报1211字节12不超过1500字节PPP帧7EFF03FACFCSF7E协议信息部分首部尾部计算机网络技术PPP有一个2个字节的协议字段。当协议字段为0x0021时，PPP帧的信息字段就是IP数据报。若为0xC021,则信息字段是PPP链路控制数据。若为0x8021，则表示这是网络控制数据。先发送IP数据报1211字节12不超过1500字节PPP帧7EFF03FACFCSF7E协议信息部分首部尾部计算机网络技术透明传输问题当PPP用在异步传输时，就使用一种特殊的字符填充法。当PPP用在同步传输时，协议规定采用硬件来完成比特填充。计算机网络技术字符填充将信息字段中出现的每一个0x7E字节转变成为2字节序列(0x7D,0x5E)。若信息字段中出现一个0x7D的字节,则将其转变成为2字节序列(0x7D,0x5D)。若信息字段中出现ASCII码的控制字符（即数值小于0x20的字符），则在该字符前面要加入一个0x7D字节，同时将该字符的编码加以改变。计算机网络技术零比特填充在发送端，只要发现有5个连续1，则立即填入一个0。接收端对帧中的比特流进行扫描。每当发现5个连续1时，就把这5个连续1后的一个0删除。计算机网络技术01001111101000101001001111110001010010011111010001010信息字段中出现了和标志字段F完全一样的8比特组合发送端在5个连1之后填入0比特再发送出去在接收端把5个连1之后的0比特删除会被误认为是标志字段F发送端填入0比特接收端删除填入的0比特计算机网络技术思考：习题3-18、3-19计算机网络技术