计算机网络-数据链路层

1、2021-11-25CN-Chapter11第三章 数据链路层Data Link LayerCOURSE2021-11-25CN-Chapter123 数据链路层 向网络层提供什么样的服务接口？ 如何将物理层的比特组成帧？ 如何处理传输差错？ 如何调整帧的流速，不至于使慢速接收方被快速发送方淹没？2021-11-25CN-Chapter133 数据链路层3.1 数据链路层的基本概念3.2 设计问题3.3 基本的数据链路协议3.4 滑窗协议3.5 Internet中的数据链路层协议3.6 协议规范和验证2021-11-25CN-Chapter143.1 数据链路层的基本概念 链路(物理链路）一条

2、无源的点到点的物理线路段，中间没有任何交换结点。 数据链路（逻辑链路）除了必须具有的一条物理线路外，还必须有一些必要的规程(procedure)来控制这些数据的传输，把实现这些规程的硬件和软件加到链路上，就构成了数据链路。2021-11-25CN-Chapter153.1 数据链路层的基本概念 数据链路层的作用：通过一些数据链路层协议（规程），在不太可靠的物理链路上，实现可靠的数据传输。 主要功能： 链路管理：链路建立、维持和释放。 帧同步：帧的开始和结束。 流量控制：发和收方速率的一致。 差错控制：前向纠错；检错重发。2021-11-25CN-Chapter163.1 数据链路层的基本概念

3、主要功能： 将数据和控制信息区分开 透明传输 寻址：多点情况下。 本章不包括LAN的数据链路层介绍。本章介绍基本的数据链路层协议。2021-11-25CN-Chapter173.2 设计问题 服务类型 成帧 差错控制 流量控制2021-11-25CN-Chapter183.2.1 向网络层提供的服务 数据链路层的功能是向网络层提供服务。一般提供三种服务： 无确认的无连接服务 有确认的无连接服务 有确认的面向连接服务 在本章使用如下模型：2021-11-25CN-Chapter193.2.1 向网络层提供的服务虚拟通信过程实际通信过程2021-11-25CN-Chapter1103.2.1 向网

4、络层提供的服务一、无确认的无连接服务 源机器向目的机器发送独立的帧，而目的机器对送到的帧不作确认。 没有连接过程。 数据链路层不恢复丢失的帧。恢复工作由上层完成。 这类服务适合误码率很低的情况。也适合多媒体实时传输。2021-11-25CN-Chapter1113.2.1 向网络层提供的服务二、有确认的无连接服务 不建立连接。 为发送帧提供确认，使发送方知道帧是否安全到达。 注意：在数据链路层上提供确认只是一种选项，而不是要求。 适合不可靠的信道，e.g.无线信道。2021-11-25CN-Chapter1123.2.1 向网络层提供的服务三、有确认的面向连接的服务 数据传输之前，要建立连接。

5、传送分为三个阶段：建立连接、帧传输、断开连接。 每一发送的帧要编号，以保证每一帧确实收到，而且保证每一帧确实收一次，所有帧都按正确顺序收到。2021-11-25CN-Chapter1133.2.2 成帧 把比特流分成离散的帧，构造一个帧结构。 标定每一帧的起始和结束。 帧结构 面向字符、面向比特。 透明传输 字符填充、位填充。2021-11-25CN-Chapter1143.2.3 差错控制 如何保证可靠的传输？即如何处理帧差错和帧丢失？如何分辨重复帧？ 方法： 检错和纠错：在帧中加入校验和；重发； 帧丢失：发送计时；超时重发； 重复帧：帧编号。2021-11-25CN-Chapter1153

6、.2.4 流量控制 如何处理发方的传送能力比收方接收能力大的问题？ 高层也有这个问题 解决方法：流量控制。 限制发送方的数据流量，使发送速率不要超过接收方处理的速率。2021-11-25CN-Chapter1163.3 基本的数据链路协议数据结构与基本变量定义#define MAX_PKT / determines packet size in bytestypedef enum false, true boolean;/ boolean typetypedef unsigned int seq_nr; / sequence or ack numberstypedef struct unsig

7、ned char dataMAX_PKT; packet; /packet definition typedef enum data, ack, nak frame_kind; / frame_kind definitiontypedef struct / frames are transported in this layer frame_kind kind; / what kind of a frame is it? seq_nr seq; / sequence number seq_nr ack; / acknowledgement number packet info; / the n

8、etwork layer packet frame;2021-11-25CN-Chapter1173.3 基本的数据链路协议/ wait for an event to happen; return its type in event.void wait_for_event(event_type *event);/ fetch a packet from the network layer for transmission on the channel.Void from_network_layer(packet *p);/ deliver information from an inboun

9、d frame to the network layer.Void to_network_layer(packet *p);/ go get an inbound frame from the physical layer and copy it to r.Void from_physical_layer(frame *r);/ pass the frame to the physical layer for transmission.Void to_physical_layer(frame *s); / start the clock running and enable the timeo

10、ut event.Void start_timer(seq_nr k);2021-11-25CN-Chapter1183.3 基本的数据链路协议/ stop the clock and disable the timeout event.void stop_timer(seq_nr k);/ start an auxiliary timer and enable the ack_timeout event.void start_ack_timer(void);/ stop an auxiliary time and disable the ack_timeout event.void stop

11、_ack_timer(void);/ allow the network layer to cause a network_layer_ready eventvoid enable_network_layer(void);/ forbid the network layer from cause a network_layer_ready event.void disable_network_layer(void);/ macro inc is expanded in-line: increment k circularly.#define inc(k) if (k1：可能不按顺序接收。 网络

12、层总是按照适当的次序从数据链路层接收数据，而不考虑数据链路层窗口的大小。 两种ARQ策略：处理连续发送中的差错： 回退n（见连续ARQ） =回退n滑窗协议 选择重传 =选择重发滑窗协议2021-11-25CN-Chapter1513.4.4 回退n滑窗协议 发送窗口WT 2n 1。 接收窗口WR =1 抛弃出错帧以及后续帧。对于丢弃的帧，不发送确认。 缺点：差错率高的情况下，浪费大量的带宽。2021-11-25CN-Chapter1523.4.4 回退n滑窗协议2021-11-25CN-Chapter1533.4.5 选择重发滑窗协议 接收方的数据链路层存储坏帧以后的所有正确帧。 只重传此坏帧

13、，而不是所有的后续帧。 若第二次重传成功，接收方的数据链路层就把缓冲的正确帧交付给网络层，且对最高序号的帧进行确认。 接收窗口大于1。2021-11-25CN-Chapter1543.4.5 选择重发滑窗协议2021-11-25CN-Chapter1553.4.5 选择重发滑窗协议 问题是：接收窗口为多大？ 关键：接收窗口前移后，有效序列号的新范围和旧范围不能重叠！ =最大窗口的大小至多是序列号范围的一半，即： 最大值：WT= WR =2n/2 =2n-1 WR 2n-1 WT WR2021-11-25CN-Chapter1563.4.6 流量控制 问题：发送方发送信息比接收方处理信息快，因接

14、收方缓冲区不够，造成信息丢失。 方法：流量控制。一、基本流量控制原理 当接收方的缓冲区快满的时候，通知发送方停止发送。 例如简单的X-ON/X-OFF协议。2021-11-25CN-Chapter1573.4.6 流量控制ONONOFFAB发送tX-ON/X-OFF流量控制2021-11-25CN-Chapter1583.4.6 流量控制二、滑窗流量控制 发送窗口的尺寸=接收方的缓冲区数量 确认应答：允许发送方继续发送下一个帧。2021-11-25CN-Chapter1593.4.6 信道利用率 问题： 数据帧短，则帧头比例相对就大，因为额外开销大，信道利用率下降。 数据帧长，传输的帧出错概率

15、就大，重传次数多，信道利用率也下降。 因此什么是信道利用率？最佳帧长是多少？2021-11-25CN-Chapter1603.4.6 信道利用率 设误比特率为pb；数据帧长lf（包括ld位数据和lh位头信息）。 对于卫星链路，比特出错可以视为独立的。数据帧的差错率可以表达为（1帧中至少有1位出错的概率）： 对于很小的pb ：p 1 (1 lf pb ） lf pb 当差错率很低时，陆地链路也可用以上公式。flbpp)1(12021-11-25CN-Chapter1613.4.6 信道利用率 平均有效数据率：D = 每秒发送的帧数 每帧包含的数据 = max ld = (1 p) ld / tf

16、 1 + ( 1)p 信道利用率：U = 实际的有效数据率 / 链路容量 = D / C = ) 1(11)(pplllhdd2021-11-25CN-Chapter1623.4.6 信道利用率 上式表明帧长与信道利用率的关系。 从简化起见，在 1的条件下，对上式的ld求导，并令其为零，解出最佳数据长度为： 用 代入，得 用p lf pb代入，得) 1)1ln(41(2bhhdoptplllflbpp)1(1hbhdoptlpll/2021-11-25CN-Chapter1633.5 Internet中的数据链路层 用户可以通过： LAN与Internet连接；PC (Router-Route

17、r) Modem拨号连接。PC ISP(Router) Internet通信子网：Router的点到点连接。 在这一章，将学习Internet中的点到点线路中的数据链路层协议。 用于路由器-路由器、拨号主机（PC）与路由器之间的点到点链路。2021-11-25CN-Chapter1643.5 Internet中的数据链路层2021-11-25CN-Chapter1653.5.1 串行线路网际协议SLIP 1984年提出。当时用于把Sun工作站通过Modem连接到互连网上去。 协议规则： 用特殊标志0 xC0封装IP，构成SLIP帧。 字符填充：0 xC0 - 0 xDB, 0 xDC； 0 x

18、DB - 0 xDB, 0 xDD。 0 xDB称为SLIP的转义字符（与ASCII的转义字符：ESC-0 x1B不同）2021-11-25CN-Chapter1663.5.1 串行线路网际协议SLIPC0 DB DC DB DD C0ENDENDC0DBIP数据包2021-11-25CN-Chapter1673.5.1 串行线路网际协议SLIP SLIP缺点： 没有差错检测功能。出错时交高层处理。 必须知道双方的IP地址。对拨号用户不方便。 仅支持IP。 未成为Internet的标准协议。版本多，不兼容。 没有任何形式的身份验证，任何一方不知道真正在与谁通信。尤其是对拨号线路。2021-11

19、-25CN-Chapter1683.5.2 点对点协议PPP 为此，IETF推出了点到点线路的数据链路协议PPP，以解决以上问题。 PPP的三个组成部分： 一种成帧方式； 一个用于建立、配置和测试数据链路连接的协议LCP(Link Control Protocol)； 一套NCP(Network Control Protocol)，支持不同的网络层协议。2021-11-25CN-Chapter1693.5.2 点对点协议PPP 成帧 帧结构：与HDLC相似。但不是面向比特的。 标志F(0 x7E)、地址A(0 xFF)、控制C(0 x03) 多一个协议字段表示信息字段中是哪类分组： 例如LCP

20、, NCP, IP, OSI CLNP, IPX 信息字段是变长的，但是其长度为整数字节。缺省长度为1500字节。2021-11-25CN-Chapter1703.5.2 点对点协议PPP 成帧 用字符填充解决透明传输问题。 0 x7E - 0 x7D+0 x5E 0 x7D-0 x7D+0 x5D ASCII控制字符（小于0 x20）- 0 x7D+控制字符。FACProtocolPayloadFCSFvariable2021-11-25CN-Chapter1713.5.2 点对点协议PPP LCP和NCP用一个例子来说明它们的作用。 用户拨号，ISP的路由器作出应答，并与之建立一条物理连接

21、； PC向路由器发送一系列LCP分组（以PPP帧结构封装）。通过这些分组及其响应，确定使用的PPP参数。2021-11-25CN-Chapter1723.5.2 点对点协议PPP 用一系列NCP分组来配置网络层。典型地，PC要运行TCP/IP协议组，所用需要一个IP地址。NCP给新接入的PC一个临时IP地址。这样PC就成为Internet上的一个主机了。 通信完毕，NCP释放网络连接，收回原来分配出去的IP地址。 LCP释放数据链路层连接。 释放物理连接。2021-11-25CN-Chapter1733.6 协议规范和验证 问题：网络协议非常复杂，显得杂乱，难以验证。 解决：需要用形式描述的方

22、法进行准确描述，并由此进行协议验证。 本节学习两种形式描述方法： 有限状态机模型 Petri-net模型2021-11-25CN-Chapter1743.6.1 有限状态机模型 有限状态机组成：状态和变迁。 状态State： 每个协议机（发送方和接收方）在每个时刻总是处于一个特定的状态。 整个系统的状态是两个协议机(protocol machine)和信道的所有状态的组合。 一帧正在信道含义：一帧已部分发出，部分接收，还未在目的机上进行处理。2021-11-25CN-Chapter1753.6.1 有限状态机模型 变迁Transition： 当某些事件发生时，状态发生转移。从每个状态，有0个或

23、多个可能的迁移到其它状态。 状态图：所有状态为节点，所有变迁为有向弧，构成状态变迁图。 初始状态：系统开始状态。2021-11-25CN-Chapter1763.6.1 有限状态机模型 以停等协议为示例： XYZ表示系统的状态； X0，1。表示发送方发送的帧0或1。 Y0，1。表示接收方期望接收到帧0或1。 Z0，1，A，。信道状态。表示信道上传送帧0，1，ACK或出现差错（包括丢失）。 弧线或直线旁数字表示变迁的标号。2021-11-25CN-Chapter1773.6.1 有限状态机模型2021-11-25CN-Chapter1783.6.1 有限状态机模型 状态图分析：(1)会不会接受重

24、复的帧？ 对于帧0情况分析。即从初始状态出发，会不会存在这样一条路径：两次出现变迁1，而在二者之间没有出现变迁3？ 同样可以分析帧1情况。(2)会不会出现帧丢失，接收过程毫无发觉？例如，丢失两个连续的帧。2021-11-25CN-Chapter1793.6.1 有限状态机模型 分析：会不会存在发送过程改变2次状态（从0到1，然后从1到0），而接收过程的状态保持不变的任何路径？（3）死锁分析 死锁是一种特殊状态。无论发生什么事件，协议都不能前行（不能向网络层提交分组）。 死锁特征：存在从初始状态可达的状态子集： 没有能跳出该子集的变迁； 在该子集内没有引起前行的变迁。2021-11-25CN-C

25、hapter1803.6.2 PetriNet模型 PetriNet的四个基本元素： 位置place：系统可能处的状态。用圆圈表示。 迁移transition：状态的转移。用水平或垂直短线表示。 弧arc：每个变迁有0或多个输入弧和0个或多个输出弧。 标记token：系统目前处于的状态。用位置中的黑点表示。2021-11-25CN-Chapter1813.6.2 PetriNet模型 状态变迁的条件： 变迁就绪(enabled)：如果在某个变迁的每个输入位置上至少有一个输入标记。 点火(fire)：任何就绪的变迁可能随时点火，发生迁移。即从每个输入位置上移走一个标记，并在每个输出位置上填上一个标记。2021-11-25CN-Chapter1823.6.2 PetriNet模型可以模拟婴儿行为的Petrinet：吃、睡、吃、.2021-11-25CN-Chapter1833.6.2 PetriNet