计算机网络与通信(3 网络体系结构)

1、,第3章 网络体系结构,School of Computer,所要讲述的问题如下： 1.应用层的功能及实现模式 2.传输层的功能及实现策略 3.网络层的功能及实现模式、路由算法、 拥塞控制算法 4.数据链路层的差错控制方法、协议 5.物理层的功能、协议,3.1.1 应用层功能 为网络应用访问网络环境提供各种应用服务。 网络应用：满足用户需要的各种具体应用，通常是各种应用程序（AP） 应用服务：为支持各种网络应用而实现的公共服务，通常体现为各种应用协议。 具体功能： 1.应用管理 参数初始化 应用进程创建、维护 资源分配、回收 安全控制 2. 系统管理【监督、报告、统计等】,3.1.2 应用对服

2、务的要求,(1)可靠的数据传输 (2)足够的带宽 (3)定时,3.1.3 应用层抽象模型,应用层由应用实体（AE）组成 AE 由UE(用户元素)、 ASE（应用服务元素）组成 UE：AP与AE之间的接口,体现为一组服务调度 ASE：可重复使用的功能模块，提供应用网络的能力（API形式提供） 公共应用服务元素CASE：所有实体的共用部分 特定应用服务元素SASE：与具体应用相关的部分 应用特定服务元素A-SASE：通信功能 用户特定服务元素U-SASE：与具体应用相关的功能,3.1.4 应用层的服务模式：C/S vs P2P,1. C/S 模式 组成：服务器+客户机 (1)服务器处于接收请求的状

3、态。 (2)客户机发出服务请求，并等待接收结果。 (3)服务器接收、分析请求，进行必要的处理，得到结果并发送给客户机；继续处于接收请求的状态。 (4)客户机接收到结果后显示结果或作其它处理。 服务器需要较高的性能，客户机可以比较简单。-瘦客户，NC,3.1.4 应用层的服务模式：C/S vs P2P,2. P2P应用模型 没有一个固定的服务器 所有主机的地位是对等的，都从其它主机获取服务，又可以向其它主机提供服务 典型：BT,3.2.0传输层的目的 在两个应用实体之间实现可靠的、透明的、有 效的数据传输，使高层用户在相互通信时不必关 心通信子网的细节。 可靠：传输层处理并隔离低层的错误 透明：

4、高层用户不涉及点对点间通信的任何细节 有效：全双工、尽量高效,3.2.1 主要功能,(1)连接管理：端到端连接的建立、维持和释放。 (2)优化网络层提供的服务质量：检查低层未发现的错误，纠正低层检测出来的错误，对接收到的数据包重新排序。 (3)提供端到端的透明数据传输：屏蔽低层网络的细节操作。 (4)多路复用和分流：将多个传输连接映射到一个网络连接上。,3.2.1 主要功能（cont),(5)状态报告：连接的性能特征（如吞吐量、平均延迟等）、地址、使用的协议类别、当前计时器值、所请求的服务质量等。 (6)安全性：接入控制（发送方的本地证实，接收方的远程证实）；数据加密/解密。 (7)加速交付：

5、接收端收到紧急数据，不需要等待后继数据到达就立即提交。,3.2.2 服务质量（QoS）, 连接建立延迟 连接建立失败概率 吞吐率 ： 单位时间传送的用户数据的总量 传输延迟：从发送报文开始到收到报文为止所经历时间 残余误码率：丢失或错、乱报文数占发送的全部报文数的百分比。 安全保护 ： 保护数据不被窃取或修改的方法 优先级 恢复功能： 出现问题或拥塞时，自动终止连接的可能性,3.2.3 传输层基本策略,1. 寻址 传输地址：用传输服务访问点（TSAP）描述 (1)层次地址 由一系列域组合而成。 例如：地址=国家网络主机端口 优点：路由选择方便 缺点：进程移动不方便 例子：Internet：表示

6、TSAP。 (2)平面地址空间 用一个号码表示地址，每个地址都是唯一的。,3.2.3 传输层基本策略,2. 建立连接 传输层的两类传输服务：面向连接和无连接 二次握手 三次握手： (1)发送方发送一个连接请求报文到接收方 (2)接收方回送一个接受请求报文到发送方 (3)发送方再回送一个确认报文到接收方,3.2.3 传输层基本策略,3. 传输数据 使用发送（SEND）和接收（RECIVE）原语交换数据 分段：用户数据超过最大报文尺寸时，发送方对数据分段，每一个分段都有一个序列号，接收方按照正确的顺序还原数据。,3.2.3 传输层基本策略,4. 释放连接 正常释放和非正常释放（突发性终止） 对称释

7、放和非对称释放 对称释放：在两个方向上分别释放连接，一方释放连接后，不能发送数据，可以继续接收数据 非对称释放：单方面终止连接,3.2.3 传输层基本策略,5. 流量控制与缓冲策略 流量控制：控制发送端的发送速度 （1）拒绝接收 （2）滑动窗口协议 （3）信用滑动窗口协议 ：发送方每发送一个报文，就把窗口推进一格，窗口大小减少1；每当收到一个信用值，就把窗口增加该值 缓存：发送方缓存,主 机 A,缓存,主 机 B,数据链路,AP2,AP1,发送方,接收方,发送速率快,接收速率慢,缓存,流量控制,应用层,运输层,应用层,运输层,主 机 A,缓存,主 机 B,数据链路,AP2,AP1,发送方,接收

8、方,发送速率快,接收速率慢,缓存,流量控制,应用层,运输层,应用层,运输层,主 机 A,缓存,主 机 B,数据链路,AP2,AP1,发送方,接收方,发送速率快,接收速率慢,缓存,流量控制,应用层,运输层,应用层,运输层,主 机 A,缓存,主 机 B,数据链路,AP2,AP1,发送方,接收方,发送速率快,接收速率慢,缓存,流量控制,应用层,运输层,应用层,运输层,缓存溢出,3.2.4传输服务原语,1.ISO定义的抽象原语 T-CONNECT.request T-CONNECT.indication T-CONNECT.response T-CONNECT.confirm T-DATA.reque

9、st T-DATA.indication T-EXPEDITED-DATA.request T-EXPEDITED-DATA.indication T-DISCONNECT.request T-DISCONNECT.indication,建立连接,传输数据,释放连接,3.2.4传输服务原语,2. 概念传输原语 LISTEN 监听连接请求，直到某个连接请求到达。 CONNECT 请求建立连接。 SEND 发送数据。 RECEIVE 接收数据。 DISCONNECT 释放连接。,3.2.4传输服务原语,3. 实际传输原语 API函数 Windows操作系统：在winsock.h文件中有定义，共10

10、0多个 SOCKET（创建一个新的套接字) BIND（往套接字中附加本地地址） LISTEN（进入接收连接请求状态） CONNECT（试图建立连接） ACCEPT（接受连接请求） SEND（发送数据） RECEIVE（接收数据） CLOSE（释放连接）,3.3.1 主要功能 （1）网络连接管理：连接的建立、维护和拆除 （2）路由选择 （3）流量与拥塞控制 （4）数据传输：面向连接的虚电路方式和无连接的数据报方式 （5）差错检测和恢复 （6）计费 （7）协议转换 （8）网络连接复用：多个传输连接复用到一个网络连接上。,3.3.2 网络层的实现方法-数据报与虚电路,虚电路：面向连接的服务 数据报：

11、无连接 一、数据报 1. 原理 从传输层接收报文，分成较小的数据块，填上源地址、目的地址、长度等信息，组成一个分组 发送前不需要与接收者建立连接 每个分组作为一个独立的信息单元传送，不考虑与前面已发出的分组，以及与后面将要发出的分组之间的顺序关系 中继节点根据当时当地情况并按照一定的算法为分组选择一条最佳的传输路由,2.数据报的实现,节点收到分组，根据分组中的目的地址，查找本节点的输出线选择表，找出一条输出线将分组转发出去。 输出线选择表由路由选择算法来建立和维护,应用层 运输层 网络层 数据链路层 物理层,应用层 运输层 网络层 数据链路层 物理层,数据报服务,H1,H2,IP 数据报,丢失

12、,H1 发送给 H2 的分组可能沿着不同路径传送,二、虚电路,1.原理 在源主机与目标主机之间，建立一个网络连接，即为虚电路（简称VC） 所有发往该目的主机的数据都将沿着所建立的虚电路按顺序传送 当通信结束时，拆除虚电路 虚电路与电路交换的区别：虚电路非独占电路，在一条物理电路上可以建立许多虚电路 永久虚电路PVC与交换虚电路SVC（临时虚电路）,应用层 运输层 网络层 数据链路层 物理层,应用层 运输层 网络层 数据链路层 物理层,虚电路服务,H1,H2,虚电路,H1 发送给 H2 的所有分组都沿着同一条虚电路传送,2. 虚电路的实现,发 送 节 点,接 收 节 点,呼叫请求包,呼叫接受包,

13、数据包,呼叫清除包,清除确认包,中 间 节 点,2. 虚电路的实现, 发送节点发送呼叫请求包（VC号、源节点、目的节点等），根据输出线选择表发送出去。 呼叫请求包经过的每个节点，登记该虚电路 目的节点收到后发送呼叫接受包给源节点，源节点收到后即认为虚电路已经建立，可开始传送数据 源节点装配数据包时，在每个数据包上填上VC号，并从VC入口、出口表发送 每个中间节点根据数据包来自哪条输入线及其中的VC号查找VC入口、出口表，修改数据包中的VC号，并转发至下一节点 数据发送完后，源节点发送呼叫清除包给目的节点，目的节点回送一个确认包，释放连接,2. 虚电路的实现,选择当前未用的最小号码作为输出VC号

14、 P74（黄）,虚电路是逻辑连接,虚电路表示这只是一条逻辑上的连接，分组都沿着这条逻辑连接按照存储转发方式传送，而并不是真正建立了一条物理连接。 请注意，电路交换的电话通信是先建立了一条真正的连接。因此分组交换的虚连接和电路交换的连接只是类似，但并不完全一样。,三、 虚电路与数据报的比较,3.3.3 路由选择算法,Routing 功能：在通信子网内选择从源节点到目的节点的路径。 要求：正确、简单、健壮、可靠、公平 优劣标准：最短（时间、成本、链路数) 最优化原则：如果节点X是从节点I到节点J 的最优路径上的一个节点，那么该路径上从X到J的那段路径也必然是从X到J的最优路径。 分类：静态与动态（

15、自适应）,一、静态路由选择算法 条件：不考虑网络的状态 (1)随机路由选择算法（随机走动法） 算法思想：当数据包到达一个节点后，该节点随机选择一条输出线转发该数据包。 完全随机法，假定与该节点相连的链路有N条，则产生一个从1到N之间的随机数i，把数据包从第i条输出线上转发； 轮选法，即对所有输出线排序，每来一个数据包，依次选一输出线转发表。 缺点：可能将所收到的数据包又从输入线上转发出去，即将数据包原路返回。 解决办法：采用计程法，即在数据包中增加一个字段，记录包经过的节点的数目。,(2)扩散路径选择算法 (洪泛法) 算法思想：当某个节点收到一个不是发给它的分组时，就向所有与此节点相连的链路转

16、发出去。当然，不能再把这个分组发到它刚刚离开的那个节点。 缺点：会产生大量的重复包，包的数目可能会呈指数规律增加。结果导致网络出现拥塞。,(2)扩散路径选择算法 (洪泛法) 解决办法： 采用站计数法，每个包中增加一个站点计数字段，初值设为从源节点到目的节点的路径长度(最多节点数)。数据包每经过一个节点，站计数器减1。当该值变为0时，若还未到达目的节点，就丢弃该数据包。 首次登录法，每个包中增加一个序号字段，在每个节点设置一张表记录首次到达本节点的包的次序。当收到一个包时，检查相应源节点发送的该包是否首次到达节点。若是，则登录序号，并扩散转发；否则，丢弃该包。,用途： 广播； 高可靠性环境、拓扑

17、不稳定； 分布式数据库并行更新； 评价其它路由算法； 无线网； 辅助路由信息的传送，如传输链路状态信息。 洪泛法在军用网中很有用，因为它有很好的稳健性。,(3) 固定路由法 算法思想：当节点收到数据包后，检查目的地，然后在输出线选择表中查找到该目的节点的主路径输出线并从该输出线上转发数据包。表中可以规定多条输出线。算法速度快、开销小。 可以根据链路度量值进行选择。 缺点：固定路径由网管人员指定，一旦网络本身出现故障或其它原因导致拓扑结构发生变化，则原来指定的路径就可能走不通，数据包无法到达目的地，必须重新指定路径。 用途：永久虚电路（PVC）。,(4) 分散通信量法 算法思想：是事先在每个节点

18、的内存中设置一个路由表，但此路由表中给出几个可供采用的输出链路，并且对每条链路赋予一个概率。当一个分组到达该节点时，此节点即产生一个从0.00到0.99的随机数，然后按此随机数的大小，查表找出相应的输出链路。 例如：分组到K站，目的站为B。 目的站经过概率经过概率经过概率 A M0.50 L0.40 N0.10 B M0.35 N0.35 L0.30 C N0.65 M0.25 P0.10 E N0.55 P0.30 M0.15 D P0.45 N0.30 M0.25 这种方法与固定路由相比，可使网内的通信量更加平衡和得到较小的平均分组时延。,二、动态路由选择算法（自适应）,条件：需要考虑网络

19、当前的状态 要求： 测量：测量并感知网络状态，主要包括拓扑结构、流量及通信延迟。 报告：向有关进程或节点报告测量结果。 更新：根据测量结果更新路由表。 决策：根据新路由表重选合适路径转发数据包。,I. 孤立自适应路由选择算法,(1) 热土豆算法 每收到一个数据包，总是选择队列最短的输出线转发数据包，以求最快输出。 问题：没有考虑网络的带宽及全网的负载状况，当网络每部分的带宽不一样时，该算法不能保证转发的路径是最优路径。 (2) 反向探知算法 根据反向路由推测正向路由 问题：路由信息是间接的，不可靠的； 当没有反向路由信息时，正常的路由选择就难以完成。,II.分布式自适应路由选择算法,(1)距离

20、向量算法【分布式BellmanFord算法】 原理 每个节点保存一张距离向量表 表中每行表示一个目的节点，代表从本节点到该节点的最短距离及其对应的下一跳节点 通过与相邻节点交换距离信息更新距离向量表 转发数据包时根据包中的目的地址查找到该节点的输出节点并转发,距离信息传播,每个节点定时测量到相邻节点的距离，并把结果广播到相邻节点（Internet：30秒，超过180秒为不可达）。 每个节点收到距离信息包后更新距离向量表 更新方法 节点J经相邻节点到达目的节点Y J的邻节点为X1，X2，Xn J需要选择输出线(X1，X2，Xn )之一进行转发 计算延迟TJYmin = mintJX1+TX1Y，

21、tJX2+TX2Y，tJXn+TXnY tJX1，tJX2，tJXn是当前已知数值；TX1Y，TX2Y，TXnY是各邻节点到目的节点的延迟，通过交换信息后得到的值。找出TJY 最小的一条路径。,距离向量法举例1(cont),A,B,A,H,D,E,C,B,G,D,F,C,E,F,H,G,距离向量法举例1,A,B,距离向量法举例1(cont),A,B,距离向量法举例1(cont),A,B,A,H,D,E,C,B,G,D,H,G,E,C,F,F,距离向量法举例2,J估计到邻居A、I、H的延迟分别为8、10、12毫秒，收到来自A、I、H的列表如下,A,J,I,H,问题,.爱听好消息 对好消息反应快，

22、对坏消息反应慢 。 如BA在某时刻接通后断开,R2,R1,正 常 情 况,1 1 ,1 2 R1,R1 说：“我到网 1 的距离是 1，是直接交付。”,“1”表示“从本路由器到网 1”,“1”表示“距离是 1”,“”表示“直接交付”,R2,R1,正 常 情 况,1 1 ,1 2 R1,R2 说：“我到网 1 的距离是 2，是经过 R1。”,“1”表示“从本路由器到网 1”,“2”表示“距离是 2”,“R1”表示 经过 R1,R2,R1,正 常 情 况,1 1 ,1 2 R1,R1 说：“我到网 1 的距离是 16 （表示无法到达）， 是直接交付。”,但 R2 在收到 R1 的更新报文之前，还发

23、送原来的报文， 因为这时 R2 并不知道 R1 出了故障。,R2,R1,正 常 情 况,1 1 ,1 2 R1,R1 收到 R2 的更新报文后，误认为可经过 R2 到达网1，于是更新自己的路由表，说：“我到网 1 的距离是 3，下一跳经过 R2”。然后将此更新信息发送给 R2。,R2,R1,正 常 情 况,1 1 ,1 2 R1,R2 以后又更新自己的路由表为“1, 4, R1”，表明 “我到网 1 距离是 4，下一跳经过 R1”。,R2,R1,R2,R1,网 1出了故障,正 常 情 况,1 1 ,1 16 ,1 5 R2,1 2 R1,1 2 R1,这样不断更新下去，直到 R1 和 R2 到

24、网 1 的距离都增大到 16 时，R1 和 R2 才知道网1是不可达的。,这就是好消息传播得快，而坏消息传播得慢。网络出故障的传播时间往往需要较长的时间(例如数分钟)。这是 RIP 的一个主要缺点。,问题 . 无穷计算 【对策？】 . 开销大 （存储、通信） .可能造成阻塞 .未考虑各链路带宽,(2)链路状态路由算法,1）原理 每个节点保存一张链路状态表(矩阵） 节点 1 2 3 1 2 矩阵表中每个元素(i,j)表示节点i与节点j之间的状态（距离、成本、带宽) 链路状态表通过接收其余节点广播的链路信息更新 转发数据包时利用Dijkstra算法计算到目的节点的最短路径并转发,工作过程：P81-

25、（黄）,发现邻居 测量到相邻节点的延迟（距离） 发回声消息到相邻节点（Internet：10秒） 传送链路状态 包的格式：源节点顺序号+n 基本方法：扩散（广播） 收到链路状态包后，查看该序号的包是否收到 新包：转发、更新本地链路状态表； 旧包：丢弃 重新计算路由：用Dijkstra算法计算到目的节点的最短路径并转发,2）问题,序号重复问题 路由器重启问题 序号出错问题 3）改进 缓存一段时间后转发,三、层次路由选择算法,分级 网络分成区域，将区域分成簇，再将簇分成区，区分为组，直到最后每个单位内节点数较少为止。 N个节点：最优层数为lnN，每个节点需要的表项总数为elnN,四、广播路由选择算

26、法, 独立发送方法 扩散方法 多目的路由选择：每个包都包含目的地址清单。中间节点根据地址清单确定输出链路集合，并复制包，制作新的目的地址清单。 生成树方法 逆向转发方法,五、组播路由选择算法,建立组播树-Steiner树 (1)最短路径树方法（SPT） (2)核心树方法（CBT）,复制,复制,R1,R3,R4,R5,R6,R2,X,B,3.3.4 拥塞控制算法,一、概念 含义：指在通信子网中有太多的包存在，使得网络的性能降低，甚至不能工作的状况 现象：包丢失（是拥塞的征兆，是判断拥塞的标准之一）,拥塞的原因, 处理器速度太慢 线路容量限制 节点输出包的能力小于输入包的能力 网络流量分布不均衡

27、对资源需求的总和 可用资源 资源不足【CPU、缓冲区、线路等】 有时，正是拥塞控制本身成为引起网络性能恶化甚至发生死锁的原因,拥塞控制与流量控制,流量控制：一条路径 抑制发送端发送数据的速率，以便使接收端来得及接收 拥塞控制：通信子网 假定网络能够承受现有的网络负荷,拥塞控制的目标,防止由于过载而使吞吐量下降，损失效率 合理分配网络资源 匹配通信子网各部分的传输速度 避免死锁,拥塞控制所起的作用,提供的负载,吞吐量,0,二、拥塞控制原理开环与闭环原理,开环原理：通过良好的设计，避免拥塞问题的出现，确保拥塞问题在开始时就不会发生。 包括： 接受新的通信的时机(Admission Control)

28、 丢弃包的时机 丢弃哪些包等 特点：在作出决定时，不考虑网络当前的状况,闭环原理,通过反馈控制，在工作过程中动态控制拥塞 。 监测：监测网络系统以便检测到拥塞在何时、何处发生 报告：将拥塞发生的信息传送到可采取行动的地方 决策：调整网络系统的运行以解决出现的问题 效果：没有拥塞时，对网络的运行几乎没有影响，只有在拥塞出现后，才起作用，且负面影响尽量小,三、拥塞控制一般方法,拥塞预防方法 (2) 拥塞抑制方法,(1)拥塞预防方法,【开环方法，主要用于虚电路子网】 预定缓冲区法 ：建立虚电路时，同时预定缓冲区。 优点：基本可避免拥塞 缺点：缓冲区和通信线路利用率低, 合理分配缓冲区法,K个缓冲区、

29、N条输出线，缓冲区的分配方法： 平分法（固定法）。每根输出线分配的缓冲区数是m=K/N，每个输出队列的长度nim 最大分配法。设输出队列最大长度为bmax,则有0nibmax，niK。 经验表明bmax =K/SQRT(N)时有较好的性能 最小分配法。设每根输出线的最小缓冲区数为bminK/N,则有max(0,nibmin)KN bmin 最大最小分配法。ni须同时满足 nibmax 与 max(0,ni bmin)KN bmin, 通信量整形法,许可证算法 基本思想：通过限制网内包的总数来避免拥塞。 办法：发放许可证，只有得到许可证的节点才能发送包（汽车驾驶证） 经验数据：对于N个节点的网络

30、，许可证数为3N时性能最好。 问题：不能消除局部拥塞 p86-（黄）,原理：保证包流往通信子网的速率是恒定的 对于输入来的包，当队列没有空位置时，丢弃。,b. 漏桶算法,c. 令牌桶算法,当突发通信量到来时，相应增大输出速率，以保证输入数据不会丢失。,令牌桶算法与漏桶算法的区别,令牌算法允许空闲主机保留发送权，而漏桶算法却不允许。令牌算法允许最多n个包的突发通信量同时传送，对输入的突然增长提供更快的反应。 令牌桶算法在桶满时丢失的是令牌，而漏桶算法在桶满时丢失的是数据包。,(2) 拥塞抑制方法,【闭环方法，在拥塞出现或即将出现时进行】 1) 阻塞包算法 每条输出线有两个变量和f，为近期利用率，

31、01，f为瞬时利用率，值为0或1。定义：新=旧+(1)f 取01之间的常数值，反映输出线利用率修改的周期(不计近期历史的速度)。为定义一个阈值，当大于此值时，进入报警状态，否则算法不起作用。,阻塞包算法,接收包，计算值,是否报警态？,转发包,触发过阻塞包？,发阻塞包，并记录,Y,Y,N,N,中间节点,测量,判断,报警,阻塞包算法,源节点,收到阻塞包，发送速度降低X%,间隔内没有收到新的阻塞包，将发送速度提高Y%(YX),抑制,X:50, Y:25,阻塞包算法, （测量）节点收到包时，计算值。 （判断）根据值判断是否为报警状态? 若不是，则转发包，转 处理下一个包。 若是，则转。 （报警）判断该

32、包在其它节点上是否触发发送过阻塞包？ 若没有，则向源节点发送一个阻塞包，同时在收到的数据包上填入已发阻塞包标志。转发包，转。 （抑制）源节点在收到阻塞包后，将发送包的速度降低X%。当在规定的时间间隔内如果没有收到新的阻塞包，就将发送速度提高Y%(YX)。,缺点,阻塞包可能不起作用 改进：沿途每个节点降低发送速度 可能不公平 改进：每个节点的每条输出线为每个源端设置一个队列，在输出时轮流选择各队列中的包转发 。,2) 负载丢弃法,问题：丢弃策略 丢弃包的时机 无条件丢弃？ 负载大于一定值（=？）时丢弃？ 丢弃哪些包 接受新的通信的时机,为什么需要数据链路层: 存在传输差错的可能性，并且数据接收方

33、可能要调整数据到达的速率，因此完全靠同步和接口技术本身还是不够的。有必要在每个通信设备中再增加一个控制层，由它提供如流量控制、差错检测以及差错控制等功能。 数据链路层的主要任务是要保证物理上相邻的两个节点之间进行可靠的数据传输。, 链路(link)：是一条无源的点到点的物理线路段，中间没有任何其他的交换节点。 一条链路只是一条通路的一个组成部分。, 数据链路(data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。 一般的适配器都包括了数据链路层和物

34、理层这两层的功能。 当采用复用技术时，一条链路上可以有多条数据链路。,数据链路层像个数字管道, 常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。 早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。, 数据链路层最重要的作用（目的）就是：通过一些数据链路层协议（即链路控制规程），把不可靠的传输线变为可靠的传输线。 或者：将物理层为传输原始比特流而提供的可能出差错的链路改造成为逻辑上无差错的数据链路。 信道类型：点点信道、广播信道 方法：成帧传送,数据链路层的简单模型,局域网,广域网,主机 H1,主机 H2,路由器

35、R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 H2 发送数据,从层次上来看数据的流动,数据链路层的简单模型( 续）,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 H2 发送数据,链路层,应用层,运输层,网络层,物理层,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,R1,R2,R3,H1,H2,仅从数据链路层观察帧的流动,IP 数据报,1010 0110,帧,取出,数据 链路层,网络层,链路,节点 A,节点 B,物理层,数据 链路层,节点 A,

36、节点 B,(a),(b),发送,接收,链路,IP 数据报,1010 0110,帧,装入,数据链路层传送的是帧,数据链路层的主要功能： P89（黄） （1）链路管理 （2）帧同步 （3）流量控制 （4）差错控制 （5）透明传输 （6）寻址,3.4.1数据链路层功能1.成帧（封装成帧、帧同步）,封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。 首部和尾部的一个重要作用就是进行帧定界。,帧结束,帧首部,IP 数据报,帧的数据部分,帧尾部, MTU,数据链路层的帧长,开始 发送,帧开始,保证帧同步的方法： 字符界定法：特定标志字符 字符计数法：开始字

37、符、长度字段 位串界定法： 01111110，位填充 帧长度： LdoptSQRT（Lh/pb)-Lh 例： Lh=48b, pb=410-5, Ldopt1000b,2.透明传输 所谓透明传输就是无论所传数据是什么样的比特组合，都不会影响数据传输的正常进行。,透明传输举例,SOH,EOT,出现了“EOT”,被接收端当作无效帧而丢弃,被接收端 误认为是一个帧,数据部分,EOT,完整的帧,发送 在前,解决透明传输问题,发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。 字节填充(byte stuffing)或字符填充(char

38、acter stuffing)接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。 如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。,SOH,SOH,EOT,SOH,ESC,ESC,EOT,ESC,SOH,ESC,ESC,ESC,SOH,原始数据,EOT,EOT,经过字节填充后发送的数据,字节填充,字节填充,字节填充,字节填充,发送 在前,帧开始符,帧结束符,用字节填充法解决透明传输的问题,SOH,3. 流量控制 限制发送方的数据流量，使其发送的速率必须使接收方来得及接收。高层也有流量控制。如运输层是端到端的流量

39、控制，而本层是相邻两节点之间的流量控制。,4. 差错控制 错误类型 位错 帧错：丢失、重复、顺序错 控制方法 CRC检错，ARQ纠错 5.数据链路管理 建立、维持、释放数据链路（连接）,6. 寻址 在多点连接的情况下，必须保证每一幀都能送到正确的目的站。接收方也应当知道发送方是哪一个站。（用网卡地址）,3.4.3 数据链路层差错控制方法,错误类型： 位错 帧错：丢失，重复，顺序错 方法： 前向纠错：纠错码 检错重发：检错码 同时实现流量控制和差错控制,3.4.4 基本链路控制规程 当两个主机进行通信时，发方和收方的数据链路层分别设有一个发送缓冲区和一个接收缓冲区。 在全双工通信，则在每一方都要

40、同时设有发送缓冲区和接收缓冲区。 因为通信线路上数据是以比特流的形式串行传输的，在计算机内部数据的传输则是以字节（或多字节）为单位传输的。所以必须在计算机的内存中设置一定容量的缓冲区，以便解决数据传输速率不一致的矛盾。,不需要数据链路层协议的数据传输（完全理想化的数据传输） 在这种条件下不需要数据链路层协议 假定1：链路是理想的传输信道，所传输的任何数据既不会出差错也不会丢失。 假定2：不管发方以多快的速率发送数据，收方总是来得及接收，并及时上交主机。 满足上述第二个条件的代价是：接收缓冲区的容量为无限大，或者是接收速率与发送速率绝对精确相等。实际情况很难做到。,一、停等机制 1.单工停等协议

41、（具有最简单流量控制的数据链路层协议） 保留第一个假定，去掉第二个假设。为了使接收方的接收缓冲区在任何情况下都不会产生溢出，就是发方每发送一幀就暂停下来，等待接收方发来的确认信号，然后才发下一幀。 这种方法的流量控制是由收方控制的，也是计算机网络中流量控制的一个基本方法。 优点：简单； 缺点：效率低。,2.具有最简单流量控制的算法,在发送节点： (1) 从主机取一个数据帧。 (2) 将数据帧送到数据链路层的发送缓存。 (3) 将发送缓存中的数据帧发送出去。 (4) 等待。 (5) 若收到由接收节点发过来的信息(此信息 的格式与内容可由双方事先商定好)，则 从主机取一个新的数据帧，然后转到(2)

42、。,具有最简单流量控制的算法（续）,在接收节点： (1) 等待。 (2) 若收到由发送节点发过来的数据帧， 则将其放入数据链路层的接收缓存。 (3) 将接收缓存中的数据帧上交主机。 (4) 向发送节点发一信息，表示数据帧已 经上交给主机。 (5) 转到(1)。,两种情况的对比（传输均无差错）,A,B,DATA,DATA,DATA,DATA,送主机 B,送主机 B,送主机 B,送主机 B,A,B,DATA,送主机 B,DATA,送主机 B,时 间,不需要流量控制,需要流量控制,3. 有噪声信道的停等协议（实用的停止等待协议） 这种情况是去掉上述两个假定来考虑传输问题。 既然信道是不可靠的，在传输

43、中就会出现错误。,数据,出错,(1)数据帧出错,发送方A,接收方B,接收方收到一帧后，向发送方发送一个否定应答(NACK),否定应答,接收方B,发送方A,(1)数据帧出错,发送方收到否定应答(NCK)后，重传该帧,副本,接收方B,发送方A,(1)数据帧出错,应答,接收方B,发送方A,(1)数据帧出错,数据,丢失,(2)数据帧丢失,发送完一个数据帧时，就启动一个超时计时器,接收方B,发送方A,若到了超时计时器所设置的重传时间而仍收不到接收方的任何确认帧，则发送方就重传前面所发送的数据帧。,副本,接收方B,发送方A,(2)数据帧丢失,应答,接收方B,发送方A,(2)数据帧丢失,数据,(3)确认帧丢

44、失,发送完一个数据帧时，就启动一个超时计时器,接收方B,发送方A,丢失,超时重传,应答,接收方B,发送方A,(3)确认帧丢失,副本,使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。 若接收方收到发送序号相同的数据帧，就表明出现了重复帧，这时应丢弃重复帧。,接收方B,发送方A,(3)确认帧丢失,接收方还必须向发送方发送确认帧 ACK，因为接收方已经知道发送方还没有收到上一次发过去的确认帧 ACK,应答,接收方B,发送方A,(3)确认帧丢失,(1) 数据幀出现差错 在数据帧中加上了循环冗余校验(CRC)，接收端很容易校验出收到的数据帧是否有差错。 (2) 数据幀丢失

45、数据幀丢失造成接收方接收不到信息，所以它不会向发送方发确认信号，这样发送方就不能发送下一幀。于是出现了死等现象，也就是死锁。 解决这一问题的办法是加设置超时定时器。,(3) 确认幀丢失 数据幀正确接收，返回的确认幀丢失，造成发方在规定的超时时间片内收不到确认信息。发方就会重发这一幀，因此接收方收到了相同的两个幀，造成上一层收到重复的数据(重复帧)。 解决的办法是在发送方对每一数据幀进行编号。,时 间,A,B,送 主 机,ACK,送 主 机,ACK,(a) 正常情况,四种情况,停止等待协议的算法, 可不使用否认帧（实用的数据链路层协议大都是这样的），而且确认帧带有序号 n。 按照习惯的表示法，A

46、CKn 表示“第 n 1 号帧已经收到，现在期望接收第 n 号帧”。 ACK1 表示“0 号帧已收到，现在期望接收的下一帧是 1 号帧”； ACK0 表示“1 号帧已收到，现在期望接收的下一帧是 0 号帧”。,在发送节点：,(1) 从主机取一个数据帧，送交发送缓存。 (2) V(S)0。 发送状态变量初始化 (3) N(S)V(S)。 将发送状态变量的数值写入发送序号 (4) 将发送缓存中的数据帧发送出去。 (5) 设置超时计时器。 (6) 等待。 等待以下(7)和(9)这三个事件中最先出现的一个 (7) 收到确认帧 ACKn， 若 n = 1 V(s)，则： 从主机取一个新的数据帧，放入发送

47、缓存； V(S)1 V(S)，更新发送状态变量，变为下一个序号 转到 (3)。 (8) 若收到否认帧NAK，则转到(4) 。 重传数据帧 (9) 若超时计时器时间到，则转到(4)。 重传数据帧,在接收节点：,(1) V(R)0。接收状态变量初始化，其数字等于欲接收的数据帧的发送序号 等待。 当收到一个数据帧，就检查有无产生传输差错(CRC) 若结果正确，则执行后续算法； 否则转到(8) (4) 收到一个数据帧； 若 N(S) = V(R)，则执行(5)；收到发送序号正确的数据帧 否则丢弃此数据帧，然后转到(7)。 (5) 将收到的数据帧中的数据部分送交上层软件 （也就是数据链路层模型中的主机）

48、。 (6) V(R)1 V(R)更新接收状态变量，准备接收下一个数据帧 (7) nV(R)； 发送确认帧 ACKn，转到(2)。 (8) 发送否认帧 NAKn，转到(2)。,停止等待机制时间关系,A,B,DATA,DATA,ACK,传播时延 tp,处理时间 tpr,应答帧发送时间 ta,传播时延 tp,处理时间 tpr,时间,两个成功发送的 数据帧之间的 最小时间间隔,数据帧的 发送时间,tf,设置的 重传时间,tout,tout = tp + tpr+ ta + tp + tpr,重传时间,超时重传：数据帧发送完毕后若经过了一段时间还没有收到应答帧，就重传这个数据帧。 超时时间为 tout

49、= tp + tpr+ ta + tp + tpr 假定 tpr 和 ta 都远小于 tp，则 tout 2tp 两个发送成功的数据帧之间的最小时间间隔是 tT = tf + tout = tf + 2tp,信道利用率,没有传输错误，传输N帧所需要的时间为TD= N tT= N（tf+2tp） 信道的利用率： = N tf / TD = N tf / (N tf + 2 N tp ) = tf / (tf+2tp) =1/(1+2) , = tp / tf,吞吐量,数据帧出错的概率为p，应答帧不出现错误，重传次数不受限制 正确传送一帧所需的平均时间tav为 tav=tT（1+一个帧的平均重传次

50、数） 一帧的平均重传次数= 1P重传次数为1+2P重传次数为2 +3P重传次数为3+ =1P第1次发送出错P第2次发送成功 +2P第1，2次发送出错P第3次发送成功 =p(1-p)+2p2(1-p)+3p3(1-p)+ tav=tT+(1-p)ipitT=tT/(1-p) i=1,2,3, 最大吞吐量max= 1/ tav =（1-p）/ tT,停止等待机制特点： 优点：简单 缺点：效率低 停止等待机制小结： 发送一帧后，启动计时器，等待应答： 肯定应答：发新帧 否定应答或超时：重传 如何进行编号？ P7273 谢（4） 同步卫星： 传播延迟是约为270ms=0.27s， 假定数据率为64Kb

51、ps，帧长4000位。=64K0.27/4000=4.32， 卫星链路的利用率为： = 1/（1+2）=1/（1+24.32）=1/9.64=0.104。,二、连续 ARQ 机制（Go Back n）,在发送完一个数据帧后，不是停下来等待应答帧，而是可以连续再发送若干个数据帧。 接收端每次接收一个帧，且按顺序接收，收到正确帧后发送应答帧。 如果此时收到了接收端发来的应答帧，还可以接着发送数据帧。 发送端对出错的数据幀进行重发是自动进行的，所以这种差错控制体制简称为ARQ（Automatic Repeat reQuest），意思是自动请求重发。,连续 ARQ 协议的工作原理,ACK1 确认 DA

52、TA0,ACK2 确认 DATA1,DATA2 出错，丢弃,DATA3 不按序，丢弃，重传 ACK2,DATA4 不按序，丢弃，重传 ACK2,DATA5 不按序，丢弃，重传 ACK2,ACK3 确认 DATA2,ACK4 确认 DATA3,超 时 重 传 时 间,A,B,tout,送交主机,送交主机,?,连续ARQ：,(1) 接收端只按序接收数据帧。收到错帧后丢弃，重复发送已发送过的最后一个确认帧（防止确认帧丢失）。 (2) 发送节点在每发送完一个数据帧时都要设置该帧的超时计时器。如果收到确认帧，就将计时器清零。若超时而未收到确认帧，就重传相应的数据帧及其后续帧。 问题：连续发送多少帧（数据

53、帧编号占开销）？ 重发哪些帧？,三、滑动窗口的概念 发送窗口的概念：发送窗口中的序列号代表已发送了的但尚未确认的幀。如果发送窗口大小为N，则需要有N个缓冲区来保存尚未确认的幀。 接收窗口的概念：接收窗口的序列号是期望接收的幀。任何不在窗口内序号的幀都要丢弃。,全双工信道数据流分析 在全双工通信中，数据是双向通信。从A机器到B机器的数据帧和从A到B的确认帧混在一起，接收方通过查看到达的帧头部的kind字段，区别是数据帧还是确认帧。 捎带技术：将确认帧附加到发送的数据帧上。 捎带技术优点：开销少，减少“帧到达”中断次数，占接收方的缓冲区少。 捎带技术缺点：捎带技术比单独确认复杂（链路层无法预知下一

54、个分组何时到来），等待时间不能超过发送方的时间间隔，否则，帧会重发。采用折衷方法，设置一个时间片，如果分组很快到来，就采用捎带技术，否则就单独发确认帧。,0,1,2,3,4,5,6,7,0,1,2,发送窗口,WT,不允许发送这些帧,允许发送 5 个帧,(a),接收端设置接收窗口, 在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。 若接收到的数据帧落在接收窗口之外，则一律将其丢弃。 在连续 ARQ 协议中，接收窗口的大小 WR = 1。 只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。 每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。

55、同时发送对该帧的确认。,不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,准备接收 0 号帧,(a),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,准备接收 1 号帧,已收到,(b),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,准备接收 4 号帧,已收到,(c),WR,WR,滑动窗口的重要特性, 只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。 收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。 当发送窗口和接收窗口的大小都等于 1时，就是停止等待协议。,发送窗口的最大值, 当用 n 个比特

56、进行编号时，若接收窗口的大小为 1，则只有在发送窗口的大小 WT 2n 1时，连续 ARQ 协议才能正确运行。 例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。,1.一位滑动窗口,发送窗口、接收窗口大小都为1 2. 全部重传（返回N）协议 发送方：一次发送N帧，启动计时器，等待应答。若收到ACK，则窗口推进N，继续发送N个新帧，否则重新发送窗口中的N帧。 接收方：对收到的帧进行检错、排序，对重复或不在窗口内的帧，丢弃；对错误帧，发NAK；若收到N个正确帧，发ACK，修改窗口。 接收窗口：N 肯定应答采用累计确认，发送一次；否定应答对每帧确认，一帧出错全部重传。,3.选择重

57、传（Selective Repeat）协议 为提高信道的利用率，可只重传出现差错的数据帧或者是计时器超时的数据帧。一旦重传帧收到，就可与原先已收到的暂时存放在缓冲区中的帧一起，按正确的顺序送网络层，且只对最高序号的帧进行确认。,选择重传 ARQ 协议, 可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。 选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。 付出的代价是在接收端要设置具有相当容量的缓存空间。接收窗口的大小应大于1。即：发、收窗口为N。 发送方：一次发送N帧，等待应答。对NAK帧和超时帧重传，待N个帧

58、都收到ACK后，窗口推进N。 接收方：对收到的帧进行检错、排序，对每个帧给出应答（ACK/NAK)；N帧都应答ACK后窗口推进N。 对于选择重传 ARQ 协议，若用 n 比特进行编号，则接收窗口的最大值受下式的约束： WR+ WT 2n ，WR最大值： WT= WR=2n/2,4. 部分重传（Go-Back N，GBN ）,发送窗口为N，接收窗口为1 发送方： 每发送一帧，都启动超时计时器，连续发送后续的帧，即使在发送过程中收到肯定应答也不停止发送； 若收到ACK(i)，则登记； 若收到NAK(i)，或超时未收到应答，则将发送指针调整为i，从帧i开始，按的方式开始发送。,4. 部分重传（Go-

59、Back N，GBN ）,接收方： 对收到的帧进行检错、排序； 帧编号不在接收窗口中或重复，丢弃； 收到错误帧（位错），发送NAK(i)； 收到正确帧，保存到相应编号的缓冲区中（同时实现了排序），发送ACK(i)。 对每个错帧都单独发送否定应答，对每个正确帧都单独发送肯定应答。,部分重传,窗口的变化时机 重传时只发送已发送的部分？,四、滑动窗口对效率的影响,四、滑动窗口对效率的影响,信道利用率, 由于每个数据帧都必须包括一定的控制信息(如帧的序号、地址、同步信息以及其他的一些控制信息)，即使连续不停地发送数据帧，信道利用率(扣除全部的控制信息后的数据率与信道容量之比)也不可能达到 100 %。

60、 当出现差错时(这是不可避免的)，数据帧的不断重传将进一步使信道利用率降低。,最佳帧长, 若数据帧的帧长取得很短，控制信息在每一帧中所占的比例增大，因而额外开销增大，导致信道利用率的下降。 若帧长取得太长，数据帧在传输过程中出错的概率增大，重传次数增大，这也会使信道利用率下降。 由此可见，存在一个最佳帧长，在此帧长下信道的利用率最高。, 信道利用率与帧长有关 最佳帧长在1000 2000bit之间,小结： 1.流量控制：是用于确保发送实体发送的数据不会超出接收实体接收数据能力的一种技术。 (1) 没有差错的流量控制：所有的帧都能成功地接收，而且这些帧在到达时也没有差错。 (2) 停止等待流量控