9 L09. 网络互连原理 -II [1] [1] [2] 6

Transcription

1 计算机网络作业答案 (2016) 刘威华中科技大学电子信息与通信学院 Contents 1 L01. 网络原理概述 [1] [2] L02. 网络体系架构 [3] L03. 网络性能评估 [1] [2] L04. 直连网络 [1] [1] L05 可靠传输 [1] [1] L06 媒体接入控制 [1] [2] L07. 网桥与交换机 [2] [1] L08. 网络互连原理 [1] [2]

2 9 L09. 网络互连原理 -II [1] [1] [2] L10. 路由协议实现 [1] [1] L11. 路由 -BGP [1] [2] L12.IPv6 与移动 IP 协议 [1] [1] L13.TCP-I [1] [2] L14.TCP-II [1] [2]

3 1 L01. 网络原理概述 1.1 [1] 1-23 题目 假设你想要在一条由信源 信宿 6 条 1 点对点链路和 5 个交换机组成的网路上传输 n 字节的文 件 假设每条链路传播延迟为 2ms, 带宽为 4Mbps, 而且交换机支持电路交换和分组交换 你可以把 文件分割成 1KB 的分组或在交换机之间建立起一个电路并把文件作为一个连续的比特流发送 假设 每个分组有 24 字节的分组首部信息和 1000 字节的有效载荷, 而且每个交换机在完全收到一个分组后对 分组进行存储转发的过程会引起 1ms 的延迟, 分组可以被链路发送而不需要等待确认 建立电路需要 发送 1KB 的消息 在路径上往返一次在每个交换机产生 1ms 的延迟 假设交换机不会给通过电路的数 据带来延迟 也可以假设文件大小是 1000 字节的整数倍 (a) 文件大小为多少个字节时, 电路交换在网络上发送的总字节数少于分组交换 (b) 文件大小为多少个字节时, 电路交换使整个文件到达目的地时产生的总延迟小于分组交换 (c) 以上结果是如何与路径上的交换机的数目相关的? 如何与链路的带宽相关的? 又是如何与分 组首部大小和分组大小之比相关的? (d) 本题给出的网络模型能否准确反映电路交换和分组交换的优缺点? 是否忽略了使这两种交换 方式受到质疑的重要因素? 如果有, 这些因素是什么? 解答 该试题的网络拓扑示意图如图 1 所示 : (a) 关于电路交换与分组交换的传输效率 图 1: 拓扑示意图 在电路交换 (Circuit Switching, CS) 中, 数据量 (Traffic, F CS ) 包括双向信令开销 (Signaling, F sig ) 和传送的数据 (Data, F data ), 即 : F CS = F sig + F data = (1K + 1K) + n (byte) = n (byte) 在分组交换 (Packet Switching, PS) 中, 数据量 (Traffic, F P S ) 包括发送分组头部的开销 (Header, F head ) 和传送的数据 (Data,F data ), 前者等于分组的头部的大小 (HeaderSize, h) 乘以分组的数 量 (Number of Packet, N pkt ), 即 : n F P S = F head + F data = 24 [ 1000 ] + n (byte) = 1.024n (byte) 如果希望电路交换发送的总字节数少于分组交换, 则需要满足 : F P S F CS, 即 1.024n n 求解结果为 n 又由于文件大小是 1000 字节的整数倍, 所以 : n (byte). (b) 关于电路交换 (CS) 与分组交换 (PS) 的时延性能 首先考虑分组交换, 列出分组交换的时序示意图如图 2 所示 : 1 原题为 7 条链路有误, 应为 6 条 3

4 T p T pkt T s T SW T p T pkt T LH 图 2: 分组交换的时序示意图 如图 2 所示, 观测数据传送起点的时延情况, 分组交换 (PS) 的总时延 (Delay, D) 可以简化为在交 换机上 (Switch, T SW ) 的处理时延和最后一跳 (LastHop, T LH ) 的时延之和, 设交换机数量为 k 个, 即 有 : D P S = T SW k + T LH 在每个交换机上的处理时延 (T SW ) 包括在这一跳处理一个数据包所需要的传播时延 (Propagation Delay, T p ) 传输时延 (Transmission Delay, T pkt ) 和处理时延 (Switch Processing Delay, T s ), 即 : T SW = T p + T pkt + T s 在最后一跳的时延包括传输一个数据包所需要的传播时延 (T p ) 和传输所有 N pkt 个数据包所需要的 传输时延 (T total ), 即 : T LH = T p + T total = T p + T pkt N pkt 于是, 分组交换的总时延为 : 有 T pkt = D P S = T SW k + T LH = (T p + T pkt + T s ) k + (T p + T pkt N pkt ) = T p (k + 1) + T pkt (k + N pkt ) + T s k 其中, 已知 T p = 2 (ms), T s = 1 (ms), k = 5, 设目标文件大小为 n 字节, N pkt = 因此 : S BW = 1KB 4Mbps = = (ms) n 1000, 又 D P S = (5+1) ( n) = n (s) 其次, 我们考虑的电路交换的时序图如图 3 所示 : 如图 3 所示, 电路交换 (CS) 的总时延 (D CS ) 包括两个部分, 即建立连接的信令部分 (Signaling, T sig ) 和数据批量传输的部分 (T data ) 2 D CS = T sig + T data 对信令传输部分, 观测信令数据前向传输的情况, 其时延可以简化为在交换机上 (T SW ) 的处理时 延和最后一跳 (T LH ) 的时延之和, 即 : T sig = 2 (T SW k + T LH ) = 2k T SW + 2 T LH 2 在此未考虑释放连接的时延过程, 有兴趣的同学可以自行加上重新测算 4

5 T p T pkt T s T SW T p T pkt T LH T pro T total 图 3: 电路交换的时序示意图 在每个交换机上的处理时延 (T SW ) 包括在这一跳处理一个信令包所需要的传播时延 (T p ) 传输时 延 (T pkt ) 和处理时延 (T s ); 在最后一跳的时延包括传输一个信令包所需要的传播时延 (T p ) 和传输该信 令包所需要的传输时延 (T pkt ), 于是 : T sig = 2k (T p + T pkt + T s ) + 2 (T p + T pkt ) = T p (2k + 2) + T pkt (2k + 2) + T s 2k 在数据批量传输部分, 其时延可以简化为一个分组经历所有链路的传播时延 (T pro ) 和传输所有数 据的传输时延 (T total ), 即 : T data = T pro + T total = T p (k + 1) + n/bw 于是, 电路交换的总延迟为 : D CS = T sig + T data = T p (3k + 3) + T pkt (2k + 2) + T s 2k + n/bw = T p 18 + T pkt 12 + T s 10 + n/bw 其中,T p = 2 (ms), T s = 1 (ms),t pkt = (ms), BW = 4 (Mbps), 因此 : D CS = ( ) n = n (s) 要使得电路交换产生的总延迟少于分组交换, 即 D CS D P S, 则 n n 解得 n , 由于文件大小是 1000 的整数倍, 取 n (byte) (c) 考察分组交换 电路交换的各项性能与传输文件大小 n 的关系 将分组的大小记为 s, 分组首部跟分组大小之比为 α, 则分组首部大小为 s α, 分组数据部分的大 小为 s (1 α) 将交换机的个数记为 k, 各链路的带宽记为 B, 则链路数为 k + 1 分组交换的总流量 F P S = F head + F data = h N pkt + n = (s α) [ s (1 α) ] + n = 电路交换的总流量 F CS = F sig + F data = 2 s + n 分组交换的总时延 D P S = T SW k + T LH = (T p + T pkt + T s ) k + (T p + T total ) = T p (k + 1) + T s k + s B (k + [ n s (1 α) ]) 电路交换的总时延 D CS = T sig + T data = 2 (T SW k + T LH ) + (T prop + T total ) n n 1 α 5

6 = 2k (T p + T pkt + T s ) + 2 (T p + T pkt ) + T p (k + 1) + T pkt [ n s (1 α) ] = T p (3k + 3) + T s 2k + s B (2k [ n s (1 α) ]) 因此, 我们可以得到下表的结论 表 1: 不同参数对分组交换和电路交换的性能影响 参数 F P S F CS D P S D CS 交换机数目 (k) 无影响 无影响 随着 k 数目增加而增大 随着 k 数目增加而增大 链路带宽 (B) 无影响 无影响 随着 B 增大而减小 随着 B 增大而减小 分组首部之比 (α) 随着 α 增大而增大 无影响 随着 α 增大而增大 无影响 (d) 此模型可以反映分组交换和电路交换的主要优缺点, 但也忽略了一些实际因素, 例如 : 网络设备 的处理能力有限, 当流量负载超过一定程度时会拥塞, 比如电路交换中可以支持的虚电路数量是有限 的, 分组交换的存储转发队列也是有限的 实际网络中的链路情况也比这个题目复杂, 该题目的结论 不一定成立, 比如不同跳的带宽一致, 分组交换中分组可能从多个路径传输, 分组传输时可能出错 等 1.2 [2] 1-9 题目 在如图所示的网络结构中, 主机 A 要向主机 B 发送一个长度为 300KB 的报文, 发送速率为 10Mb/s, 传输路径上要经过 8 个路由器 连接路由器的链路长度为 100km, 信号在链路上的传播速度为 m/s 每个路由器的排队等待延时为 1ms 路由器发送速率也为 10Mb/s 忽略: 主机接入到路由器的链路长度, 路由器排队等待延时与数据长度无关, 并假设信号在链路上传输没有出现差错和拥塞 计算 : (1) 采用报文交换, 报文头长度为 60B, 报文从主机 A 到主机 B 需要多长时间? (2) 采用报文分组交换, 分组头长度为 20B 时, 分组数据长度为 2KB 报文分组从主机 A 到主机 B 需要多长时间? 图 4: 拓扑示意图 解答 在系统方法教材 [1] 中只讨论了 电路交换 (Circuit Switching) 和 分组交换 (Packet Switching), 而在中文教材 [2] 和 [3] 中还提到了一种交换方式 报文交换 (Message Switching) 在下图 5 中给出了这三种交换方式的对比 具体说来 : 电路交换 整个报文的比特流连续地从源点直达终点, 好像在一个管道中传送 这种方式也被称为 线路交换 [2] 报文交换 整个报文先传送到相邻节点, 全部存储下后根据转发表转发到下一个节点 6

7 图 5: 三种交换方式的对比 ( 来源于图 1-13 [3]) 分组交换 单个分组 ( 整个报文的一部分 ) 传送到相邻节点, 存储之后根据转发表转发到 下一个节点 根据交换过程的差异, 由可以进一步分为 数据报交换 (Datagram) 和 虚电路交 换 (Virtual Circuit) 两种, 前者的每个分组自包含目的信息而可以被单独转发, 后者的分组经由事 先建立的虚电路转发 在点到点传输过程中, 路由器设备和交换机设备的存储转发机制并无明显区别, 我们还是 按照交换网络的情况进行计算 下面的解法参考前面试题的结论 需要说明的是, 在吴功宜教 材 [2]P 分组交换与线路交换的比较 一节, 给出了较为详细的另外一种时延测算步骤, 有 兴趣的同学可以参阅 (1) 报文交换的情况下, 报文整体直接传输, 可以视为一个大的分组 : D P S = T SW k + T LH = (T p + T pkt + T s ) k + (T p + T pkt ) = T p (k + 1) + T s k + T pkt (k + 1) 其中, 待发送的数据大小 n = 300 (KB), 分组头部大小 h = 60 (B), 链路带宽 B = 10(Mbps), 路由 器设备数量 k = 8; 传播时延 T p = Distance speed = = (s); 处理时延 T s = 10 3 (s); 传输一 个分组的时延 T pkt = n+h B = = (s) 结合图中的拓扑,HA 和 HB 直接连在路由器上, 应为近距离的高速链路, 其传播时延 T p 可以 忽略为 0, 而路由器直接的链路长达 100 (km), 时延 T p 不能忽略, 故考虑链路传播时延的链路数减 少 2 条, 为 k = 7 条 则总时延 D P S = ( ) (8 + 1) = (s) (2) 报文分组交换的情况下, 完整的大报文被分为若干个分组进行传输 : D P S = T SW k + T LH = (T p + T pkt + T s ) k + (T p + T total ) = T p (k + 1) + T s k + T pkt (k + n d ) 7

8 其中, 待发送的数据大小仍为 n = 300 (KB), 分组数据部分大小 d = 2 (KB), 分组头部大小 h = = (B), 相应的 T pkt = d+h B 链路传播时延的链路数减少 2 条, 为 k = 7 条 = (s), 分组数量 n d = = 150 同上, 考虑 则总时延 D P S = ( ) ( ) = (s) 8

9 2 L02. 网络体系架构 2.1 [3] 1-20 题目 网络体系结构为什么要采用分层次的结构? 试举出一些与分层体系结构思想相似的日常生活案例 解答 为了保证计算机网络中大量计算机之间有条不紊地交换数据, 人们必须制订大量的协议, 构成一套完整的协议体系 对于结构复杂的网络协议体系来说, 最好的组织方式是层次结构模型 相应的, 计算机网络引入了一个重要的概念 网络体系结构 (Network Architecture) 所谓网络体系结构, 是网络层次结构模型和各层协议的集合 ; 网络体系结构对计算机网络应该实现的功能进行定 义 ; 虽然网络体系结构是抽象的, 实现网络协议的技术是具体的 采用层次结构方法的网络体系结构的主要优点 [1]: 第一, 分层可以将建造网络的问题分解为多 个可以处理的部分 不是把想要的所有功能都集中在一个软件中, 而是可以实现多个层, 每个层解决 一部分问题 第二, 分层提供了一种更为模块化的设计 如果想增加一些新的服务, 只需要修改某一层的功能, 同时可以继续使用其他各层提供的功能 层次结构的网络体系结构的优点也包括 [2]:(1) 各层之间相互独立 高层不需要知道低层的功能是如何实现的, 只需要知道通过与低层的接口就可以获得所需要的服务 (2) 灵活性好 各层都可以采用最适当的技术来实现, 某一层的实现技术发生了变化, 不会对其他各层以及整个系统的工作产生影响 (3) 易于实现和标准化 可以将网络复杂的通信工作过程化解为一系列可以控制和实现的功能模块, 使得复杂的计算机网络系统变得易于设计 实现和标准化 与分层体系结构的思想相似的日常生活有邮政系统, 物流系统等 9

10 3 L03. 网络性能评估 3.1 [1] 1-13 题目 假设在地球和新的月球定居地之间架设了一条 100Mbps 的点到点链路 从月球到地球的距离大约 是 km, 而且数据在链路上以光速传播, 即 m/s (a) 计算链路的最小 RTT (b) 使用 RTT 作为延迟, 计算链路的延迟与带宽的乘积 (c) 在 (b) 中计算的延迟与带宽的乘积值的意义是什么? (d) 在月球基地上的一部照相机拍摄了一张地球的照片, 并以数字的形式存入磁盘 假设地球上 的任务控制中心希望下载最新的图像, 大小是 25MB 计算从发出请求到传输完毕耗费的最小时间 解答 (a) 链路的最小 RTT, 即仅有传播时延 T prop, 而分组传输时延 T trans = 0 处理时延 T proc = 0 RT T min = T prop = 2 Distance SignalSpeed = = 2.57 (s) (b) 链路的带宽时延积 Bandwidth Delay = 2.57 (s) (bps) = (bit) = (MB) (c) 延迟与带宽的乘积值的意义 发送方在接收到接收方反馈回来的第一个比特之前, 发送方必须发送的比特数 (d) 从发出请求到传输完毕耗费的最小时间, 包括传播时延 T prop 和传输时间 T trans 其中 T trans 的 最小值即视 25MB 为一个报文来传输的时间 T trans = F ilesize Bandwidth = = 2.10 (s) Delay = T prop + T trans = = 4.67 (s) 3.2 [2] 1-7 题目 长度为 8B 与 536B 的应用层数据通过传输层时加上了 20B 的 TCP 报头, 通过网络层时加 上 60B 的 IP 分组头, 通过数据链路层时加上了 18B 的 Ethernet 帧头和帧尾 分别计算两种情况下 的数据传输效率 解答 分组数据的构成示意图 6 数据传输效率的定义为待传输数据 (L data ) 与所传输的数据总 量 (L header + L data ) 的比率 (1) 应用层数据长度为 8 (byte) 的数据传输效率 1 L data = 8 (byte) 2 L header = = 98 (byte) L 3 η = data L header +L data = = 7.55% 10

11 Ethernet IP TCP 图 6: 分组数据构成的示意图 (2) 应用层数据长度为 536 (byte) 的数据传输效率 1 L data = 536 (byte) 2 L header = = 98 (byte) L 3 η = data L header +L data = = 84.54% 11

12 4 L04. 直连网络 4.1 [1] 2-11 题目 说明为什么二维奇偶校验可以检测到所有的 3 比特错误 解答 需要说明的是, 检测错误 (Error Detection) 是发现是否存在错误, 而非定位并纠正错误 (Error Correction) 即, 只知道有误, 但是并不知道具体的错误比特 与一维奇偶校验一样, 二维奇偶校验只能发现错误并要求重传而不能纠正错误 下面区分不同的情况进行具体分析 : (1) 如果三比特错误发生在同一行, 那么一定是有三列, 每列包含一个一比特错误, 那么根据一 维的奇偶校验可以检测到每一列中的错误比特 (2) 如果三比特错误发生在两行, 且不同的三列, 则等同于情况 (1); (3) 如果三比特错误发生在两行的两列, 例如表 2 所示 当行或者列出现偶数个错误时, 奇偶校验 无法检测相关错误 不过在这种情况下, 还是存在行或者列有奇数个错误的, 因此奇偶校验还是会报错, 并请求发送方重传, 实现了检测是否有错误的目的 表 2: 3 比特错误示意图 (4) 如果三比特错误发送在三行, 则等同于情况 (1) 综上, 二维奇偶校验可以检测到所有的 3 比特错误 4.2 [1] 2-18 题目 假设我们想要传输消息 , 并用 CRC 多项式 x 防止它出错 (a) 使用多项式长除法确定应传输的消息 (b) 假设由于传输链路上的噪声使得消息最左端的比特发生反转 接收方的 CRC 的计算结果是什么? 接收方如何知道发生了一个差错? 解答 在系统方法教材 [1] 中对 CRC 基本原理进行了介绍, 在吴功宜教材 [2]P109, 给出了较为清晰的 CRC 校验案例, 有兴趣的同学可以参阅 (a) 原始消息 M = ,C(x) = x 可知阶数为 3, 所以 T = , 用 T 除以 C = 1001, 得到 R = 011, 运算过程如下图 7 所示 则应传输的消息 P = T XOR R =

13 图 7: 发送方利用二进制长除法计算获得待传输的余数 (b) 接收方接收到的消息 T = , 除以 C = 1001, 计算得到商为 , 余数为 010, 运算过程如下图 8 所示 由于 T 不能被 C 整除, 所以接收消息中有比特出错 图 8: 接收方利用二进制长除法校验是否整除 13

14 5 L05 可靠传输 5.1 [1] 2-24 题目 假设你为到月球的一条 1Mbps 点到点链路设计一个滑动窗口协议, 单程时延是 1.25s 假设每帧 携带 1KB 数据, 最少需要多少比特作序号? 解答 为了充分利用带宽, 应该使每次通信过程都保证链路饱和, 即滑动窗口中的全部数据帧大小等于 带宽时延积 (1) 链路的带宽时延积 Bandwidth Delay = (bps) (s) = (bit) = (KB) = (KB) (2) 发送窗口的大小 (Sender Window Size, SWS) 应尽可能接近带宽时延积 故 SWS 为 : SW S = N pkt = KB 1KB = = 305 (frame) (3) 假设该链路可以正常双工通信, 且所需的发送窗口和接收窗口大小一致 (RW S = SW S), 则 序号空间应大于发送窗口与接收窗口之和, 以区分传输过程中的不同数据帧 故需要的比特数为 : n log 2 (305 2) = 9.25 = 10 (bit) 5.2 [1] 2-29 题目 给出当接收方用完缓冲区空间时, 你如何通过让 ACK 携带额外的信息以减小 SWS, 从而实 现带有流量控制的滑动窗口协议 假设初始 SWS 和 RWS 都是 4, 链路速度是瞬时的, 并且接收方 能够以每秒一个的速率释放缓冲区 ( 即接收方是瓶颈 ); 用传输的一条时间线说明你的协议 说明 在 T = 0, 1,..., 4s 时会发生什么 解答 在授课时我们介绍滑动窗口协议 (Sliding Window Protocol) 是以可靠传输 (Reliable Transmission) 为目的的, 但该协议同时用于流量控制 (Flow Control) 本题就是展示滑动窗口协议在后者的功 能 其基本原理是, 当接收方 (Receiver, R) 的资源成为瓶颈 需要控制所接收流量的速率的时候, 接收方 R 通过 ACK 携带额外信息, 通知发送方 (Sender, S) 调整其发送窗口大小 (Sender Window Size, SWS) 假设接收方 R 通过 ACK 报文携带了一个额外的变量 k,k 用来指示接收方目前可用缓冲区大 小 ( 其实现方式可以是 ACK 报文里面的一个特定的字段 ) 发送方 S 接收到 k 后, 即以其作为其当 前 SWS 值 如果 k = 0, S 则停止发送 这样,S 的发送速率就受到 R 的可用缓冲区大小的控制, 从而 实现流量控制 在图 9 中, 我们给出一个示例, 其中 SWS 和 RWS 的初始值都是 4 T = 0,S 发送 1, 2, 3, 4 号帧,R 收到这 4 个帧并回复 4 个 ACK 由于题意中说链路速度是瞬时的, 在此不考虑传输时延和传播时延 S 立即就收到了相应的 ACK1...ACK4, 其中的 k 值分别为 3, 2, 1, 0 于是 S 将 SWS 相应地设置为 3, 2, 1, 0 当 SWS 为 0 时,S 的窗口停止向前滑动 14

15 SWS=4 sender T=0 frame1-frame4 receiver RWS=4 SWS=0 k=3 k=2 k=1 k=0 SWS=1 T=1 k=1 frame5 SWS=0 k=0 SWS=1 T=2 k=1 frame6 SWS=0 k=0 T=3 k=1 SWS=1 frame7 SWS=0 k=0 T=4 k=1 SWS=1 SWS=0 k=0 图 9: 滑动窗口协议传输时间线 T = 1, 根据题意,R 的上层取走了一个帧, 释放了相应的缓冲区,R 即发送新的 ACK 并通知发送方 S 当前资源有空闲 (k = 1) S 的发送窗口向前滑动,SWS 大小为 1, 发送 5 号帧 R 收到后发送 ACK 表明资源被占满 (k = 0) T = 2, 3, 4,..., 与前一个时隙类似, 接收方 R 释放了一个帧的缓冲区, 通知 S 目前 k = 1 S 发送新的帧,R 收到后通知 S 当前 k = 0 frame8 综上,R 将当前可用资源的数量经由 ACK 通知 S,S 相应地控制其发送窗口的大小, 最终 S 的发 送速率控制在每个时隙一个帧, 与 R 的缓冲区资源使用速率相当, 系统达到了流量控制的目的 15

16 6 L06 媒体接入控制 6.1 [1] 2-44 题目 2-44 令 A 和 B 是试图在一个以太网上传输的两个站 每个站有一个准备发送的帧的稳定队列 ;A 的帧 被编号为 A1 A2, 等等,B 的帧类似 令 T=51.2µs 是指数退避的基本单元 假设 A 和 B 同时想发送帧 1, 导致冲突, 并分别发生选择退避时间 0 T 和 1 T, 这意味着 A 在竞 争中获胜并传输 A1 而 B 等待 在这次传输结束时,B 将试图重传 B1 而 A 试图传输 A2 这种首次尝试 又会冲突, 但现在 A 退避 0 T 或者 1 T, 而 B 退避的时间等于 0 T, 1 T,..., 3 T 中之一 (a) 给出第一次冲突后 A 立即在第二次退避竞争中获胜的概率 ; 就是说,A 第一次选择的退避时 间 k 51.2 小于 B 的退避时间 (b) 假设 A 在第二次退避竞争中获胜 A 传输 A3, 当传输结束时, 在 A 试图传输 A4 而 B 试图再传 输 B1 时,A 和 B 又发生冲突 给出第一次冲突后 A 立即在第三次退避竞争中获胜的概率 (c) 为 A 在所有余下的退避竞争中获胜的概率给出一个合理的下界 (d) 然后对帧 B 发生什么? 这种情形称为以太网的捕获作用 ( Capture Effect) 解答 2-44 以太网 CSMA/CD 为了解决信道争用的公平性问题, 采用了二进制指数退避 (Binary Exponential Backoff) 算法, 在系统方法的教材 [1]P71 和吴功宜教材 [2]P148 有所介绍 需要指出的是, 基本的指 数退避算法有一些缺陷, 主要表现为竞争公平性问题, 本题以及下一题就是对其合理性进行考察 (a) 根据题意, 第 1 轮冲突后 : 节点 A 的退避窗口大小为 2, 其可能的退避时间集合为 {0 T, 1 T },A 选择了 0 T 节点 B 的退避窗口大小为 2, 其可能的退避时间集合为 {0 T, 1 T },B 选择了 1 T A 和 B 的竞争结果是 A 胜出 第 2 轮冲突后 : 节点 A 的退避窗口大小仍然为 2, 其可能的退避时间集合为 {0 T, 1 T }, 假设 A 选择了 x 节点 B 的退避窗口大小扩大 1 倍为 4, 其可能的退避时间集合为 {0 T, 1 T, 2 T, 3 T }, 假 设 B 选择了 y 选择了 y 如果我们希望 x < y, 则 如 x = 0 T,y 可能的取值集合为 {1 T, 2 T, 3 T }, 共计 3 种情况 如 x = 1 T,y 可能的取值集合为 {2 T, 3 T }, 共计 2 种情况 而 x 与 y 的所有排列组合为 2 4 = 8 种情况, 所以第 2 轮冲突后,A 胜出 B 的概率为 % = 62.5% (b) 根据题意, 第 3 轮冲突后 : 节点 A 的退避窗口大小仍然为 2, 其可能的退避时间集合为 {0 T, 1 T }, 假设 A 选择了 x 节点 B 的退避窗口大小再扩大 1 倍为 8, 其可能的退避时间集合为 {0 T, 1 T,..., 7 T }, 假设 B 如果我们希望 x < y, 则 如 x = 0 T,y 可能的取值集合为 {1 T,..., 7 T }, 共计 7 种情况 16

17 为 如 x = 1 T,y 可能的取值集合为 {2 T,..., 7 T }, 共计 6 种情况 而 x 与 y 的所有排列组合为 2 8 = 16 种情况, 所以 7+6 第 3 轮冲突后,A 胜出 B 的概率为 % = 81.25% (c) 根据题意 : 如果 A 在剩下的竞争中永远获胜, 则其退避窗口大小保持 2, 其可能的退避时间 x {0 T, 1 T } 在第 n 轮竞争 (n 2) 的时候,B 的可能的退避时间 y {0 T,..., (2 n 1) T } 如 x = 0 T, 则 y > x 的可能性有 (2 n 1) 1 种情况 如 x = 1 T, 则 y > x 的可能性有 (2 n 1) 2 种情况 而 x 与 y 的所有排列组合为 2 2 n = 2 n+1 种情况, 所以第 n 轮冲突后,A 胜出 B 的概率为 P n = 2n n n+1 = n+1 那么 A 永远胜出的概率为 n P = P i = (1 3 8 ) ( ) (1 3 3 )... (1 ) (1) 32 2n+1 i=1 由于指数增长较为迅速, 当 n = 15 时,P n = 1 3 1,A 胜出概率 lim 2 P 可以近似 16 n i=1 P i (d) 如果发生这种情况 B 永远发送不出帧,B 将对上层报错, 放弃在该链路上进行数据发送 6.2 [2] 5-3 题目 主机 A 连接在总线长度为 1000m 的局域网总线的一端, 局域网媒体访问控制方式为 CSMA/CD, 发送速率为 100Mbps 电磁波在该总线传输介质中的传播速度为 m/s 如果主机 A 最先发送 帧, 并且在检测出冲突发生的时候还有数据要发送 请回答 : (a) 主机 A 检测到冲突需要多长时间? (b) 当检测到冲突的时候, 主机 A 已经发送多少位的数据? 解答 以太网 CSMA/CD 的设计中, 考虑了在总线型线缆段上进行冲突检测的需求 相应的计算问题, 在系统方法的教材 [1] P71 和吴功宜教材 [2]P146 有所介绍, 有兴趣的同学可以参阅 (a) 考虑最差的情况, 即主机 A 在总线一端, 发生冲突的主机 B 在总线的另一端, 当主机 A 的信号 抵达 B 时,B 正好有信号发送产生冲突,B 的信号抵达 A 处时 A 才能检测到冲突的发生 整个过程, 需 要 2 倍的信号传播时间 信号在该总线介质中的传播时间为 T prop = Distance SigalSpeed = (s) = 5 (µs) 检测到冲突需要的时间 T dect = 2 T prop = 2 5 (µs) = 10 (µs). (b) 当检测到冲突时, 主机 A 已经发送的数据为 : F = Rate T = = 1000 (bit) = 125 (byte). 17

18 7 7.1 L07.网 网桥 与 交 换 机 [2] 5-9 题目 如图10所示的网络结构中 6台主机通过透明网桥B1 B2连接在互联的局域网中 网桥初始 转发表是空的 假设主机发送帧的顺序是 H1发送给H5 H5发送给H4 H3 发送给H6 H2发送 du. cn 给H4 H6发送给H2 H4发送给H3 请根据网桥自学习的原理完成网桥B1与B2的转发表 hu s t.e 图 10: 用网桥互联的局域网结构示意图 解答 根据网桥自学习的原理 如果网络现在能够从端口x 收到从源地址为A的主机发送的数据帧 那 么以后就可以从端口x转发目的地址为A的数据帧 网桥建立相应的转发表 记录 主机-端口 的映 射关系 H1发送给H5 数据帧源地址为H1 B1学习到 H1-端口1 B1不知道H5在哪个网段 于是 向端口2转发 B2学习到 H1-端口1 继续向端口2 转发 H5收到数据帧 w H5发送给H4 数据帧源地址为H5 B2学习到 H5-端口2 B2不知道H4在哪个网段 于是 liu 向端口1转发 H4收到数据帧 B1学习到 H5-端口2 H3发送给H6 数据帧源地址为H3 B1学习到 H3-端口2 B1不知道H6在哪个网段 于是 向端口1转发 同时B2学习到 H3-端口1 继续向端口2转发 H6收到数据帧 H2发送给H4 数据帧源地址为H2 B1学习到 H2-端口1 B1不知道H4在哪个网段 于是 向端口2转发 H4收到数据帧 B2学习到 H2-端口1 H6发送给H2 数据帧源地址为H6 B2学习到 H6-端口2 B2知道H2在端口1 于是向端 口1转发 B1学习到 H6-端口2 B1知道H2 在端口1 继续向端口1 转发 H2收到数据帧 H4发送给H3 数据帧源地址为H4 H3收到数据帧 B1 学习到 H4-端口2 B1知道H3在该 网段 于是不转发 B2学习到 H4-端口1 B2知道H3在该网段 于是不转发 最终我们可以获得两个网桥的转发表如下表所示 7.2 [1] 3-32 题目 假设在全部通信量介于一台服务器和N台 客户端 之间的环境中 用一台10M bps交换机替换 一台10M bps 以太网集线器 或中继器 因为所有通信量仍需通过服务器-交换机的链路 所以名义 18

19 表 3: B1 转发表 序号 目的地 端口 1 H1 1 2 H5 2 3 H3 2 4 H2 1 5 H6 2 6 H4 2 表 4: B2 转发表 序号 目的地 端口 1 H1 1 2 H5 2 3 H3 1 4 H2 1 5 H6 2 6 H4 1 上没有改进带宽 (a) 你认为带宽会有任何改进吗? 如果有, 为什么? (b) 交换机与集线器相比还有哪些优缺点? 答案 (a) 带宽会有改进 假设每个客户端总与服务器通信, 每个通信会话中的通信量包括客户端发起的请求 (F upload ) 以及 从服务器获取的回复 (F download ), 会话的有效带宽为两者的最小值, 即 min(f upload, F download ) 在集线器环境下通信的示意图为图 11 图 11: 用集线器联网的系统示意图 服务器与 N 台客户端之间将共享总共 10Mbps 的带宽 此时, 接到集线器上的设备共有 N + 1 台 (N 台客户端加上 1 台服务器 ) 客户端与服务器间的通信将以 CSMA/CD 的方式竞争信道, 假设 各个设备之间均匀分配资源, 则每个客户端可以请求的上行带宽 (F upload ) 和服务器回复的下行带 10 宽 (F download ) 均为 N+1 Mbps 这时, 只要客户端或者服务器竞争获得了带宽, 即可实现会话内的有效通信, 因此每个会话可以获得的有效带宽为 F hub = min(f upload, F download ) = min( 10 N+1, 10 N+1 ) = 10 N+1 (Mbps) 在交换机环境下通信的示意图为图 12 每对服务器与 N 台客户端之间通信都可以有 10Mbps 的独占带宽, 无信道竞争共享问题 则在每 个会话内, 客户端可以请求的最大上行带宽 (F upload,max ) 和服务器回复的最大下行带宽 (F download,max ) 19

20 图 12: 用交换机联网的系统示意图 均为 10Mbps 此时, 虽然客户端和服务器不会竞争交换机的带宽, 但是多个并发的会话会共享服 务器的上传总带宽, 即在客户端并发连接服务器时会竞争服务器的总下行带宽, 即平均每个连接的下行带宽为 F download = 10 N (Mbps) 因此每个会话可以获得的有效带宽为 F switch = min(f upload, F download ) = min(10, 10 N ) = 10 N (Mbps). 因此, 使用交换机之后可以带来的吞吐量提升为 : F = F switch F hub = 10 N 10 N+1 = 10 N (N+1) (Mbps) (b) 交换机与集线器的比较 集线器是物理层设备, 仅增强了信号的传播但无转发功能 ; 而交换机是数据链路层设备, 可以根 据 MAC 地址转发数据帧 交换机相较于集线器的优点主要包括 : (1) 带宽更高 集线器环境下是一个共享介质的网络, 总带宽由 CSMA/CD 机制共享 交换机环 境下是专有介质的网络, 可以获得交换机的总带宽 (2) 扩展性更好 集线器可用于扩展以太网段, 但是由于物理传输限制, 在传统的 协议下最 多只能扩展 4 个集线器, 距离在 2500m 以内 ; 而交换机更适用于以太网段的扩展 借助于学习型网桥 和生成树算法的支撑, 以太网路由器的扩展几乎是无需配置的 (3) 安全性更好 集线器由于是共享介质, 那么数据帧可以被其他主机侦听, 同时, 恶意广播将 会降低网段的通信效率 ; 而交换机是专有介质, 不存在侦听的情况, 同时, 恶意广播也可以由交换机 的端口管理功能加以控制 交换机相较于集线器的主要缺点可能在于成本 高速以太网交换机比集线器昂贵 然而, 在 10/100Mbps 以太网中, 目前的两者的价格相差无几 20

21 8 L08. 网络互连原理 8.1 [1] 3-36 题目 假设一个 TCP 消息包含 2048 字节数据和 20 字节的 TCP 首部, 这个 TCP 消息要传送给 IP, 传送通过因特网上的两个网络 ( 即从源主机到一个路由器, 再从路由器到目的主机 ) 第一个网络使用 14 字节的首部, 并且有一个 1024 字节的 MTU; 第二个网络使用 8 字节的首部和 512 字节的 MTU 每个网络的 MTU 给出链路层帧能够承载的最大 IP 数据报尺寸 请给出传送到目的主机网络层的分段序列的尺寸和偏移量 假定所有 IP 首部的尺寸是 20 字节 解答 在传输层,TCP 待发送的数据量为 2048 (byte) 在网络层,IP 待发送的数据量需要额外考虑 TCP 的首部 20 (byte), 共计 = 2068 (byte) 在数据链路层, 网络一的 MTU 为 1024 (byte), 小于待发送的 IP 数据报的数据量, 故而 IP 分组会 在网络一进行分段 (Segmentation) 在每个数据帧中需要额外考虑 IP 首部 20 (byte), 所以网络一中每 个数据帧中能够包含的数据最多为 = 1004 (byte) 因为在 IP 数据文件中是以 8 (byte) 的倍数计算长度, 最接近的可用数据长度是 1000 (byte) 故而: 网络一中将分成 X 1, X 2, X 3 三个数据帧传输, 其数据部分的大小分别为 X 1 = 1000 (byte), X 2 = 1000 (byte), X 3 = = 68 (byte) 经过网络二时, 其 MTU 为 512 (byte), 小于网络一数据帧中的 IP 报文的数据量, 故而 IP 分组会在网络二进一步分段 在每个数据帧中需要额外考虑 IP 首部 20 (byte), 所以网络二中每个数据帧中能够包含的数据最多为 = 492 (byte) 因为在 IP 数据文件中是以 8 (byte) 的倍数计算长度, 最接近的可用数据长度是 488 (byte) 故而: 在网络二中 X 1 将会进一步分成三个数据帧 Y 1, Y 2, Y 3 传输, 其数据部分的大小分别为 Y 1 = 488 (byte), Y 2 = 488 (byte), Y 3 = = 24 (byte), 对应的偏移量分别为 61,61,3 同理 X 2 将会进一步分成三个数据帧 Y 4, Y 5, Y 6 传输, 其数据部分的大小分别为 Y 4 = 488 (byte), Y 5 = 488 (byte), Y 6 = = 24 (byte), 对应的偏移量分别为 61,61,3 而 X 3 较小, 将直接转化为数据帧 Y 7 传输, 其数据部分的大小为 Y 7 = 68 (byte) 整个分析的过程如下图 13 所示 最后可以获得下表的数据报分段结果, 其累计偏移量由上述偏移量累加计算得到 表 5: 数据报分段表 数据报编号 标识符 累计偏移量

22 TCP TCP 2048 B IP MTU 2068 IP IP X1 IP < MTU=1024 B IP =X1+X2+X3=2068 B MTU, X1 X2 IP IP IP IP IP Y1 Y2 X2 X B IP IP Y4 Y5 IP Y7 IP Y3 IP Y6 图 13: IP 数据报文分段过程演示图 8.2 [2] 6-1 题目 给出 5 种网络设备 : 集线器 (Hub) 中继器 (Repeater) 交换机 (Switch) 网桥 (Bridge) 与路由器 (Router), 请分别填在图 14 中的 5 处位置, 并说明理由 图 14: 不同网络设备的连接设置 解答 网络设备与组网问题的讨论, 参见吴功宜教材 [2] 的 P168 页 第 5.5 节 Ethernet 组网设备与组网方 法, 请同学们注意不同网络设备的对比区别 22

23 位置 3: 两个 10Base-2 细缆以太网网段互联, 此为直连网络的扩展问题, 属于物理层问题, 应该使用中继器对信号进行放大 位置 4:10Base-2 细缆以太网与令牌环网之间互联, 这两种局域网的网络介质不同, 无法直接在物理层上实现扩展, 需要实现两个局域网网段之间的帧转发, 因此属于数据链路层的问题, 应该用网桥实现局域网网段之间的帧转发 位置 2:10Base-T 双绞线以太网的多个主机互联, 根据介质情况需要采用星形拓扑的局域网设备, 即集线器或者交换机, 综合考虑位置 2 和位置 1, 此处应该放置集线器 位置 5: 要与 Internet 连接, 支持不同网络之间的互联, 应该使用路由器 位置 1: 该设备要实现 100Base-T 双绞线快速以太网的多个主机互联, 还要支持与位置 5 处的路由器 位置 2 处的集线器互联, 判定该设备应该是支持星形拓扑的 且支持多种链路连接的交换机设备 23

24 9 L09. 网络互连原理 -II 9.1 [1] 3-74 题目 一个 ISP 有一个 B 类地址, 基于 CIDR 方法将一部分地址分配给一家新公司 新公司网络中的三个部门的机器需要 IP 地址 : 工程部 市场部和销售部 这三个部分计划中的增长如下 : 工程部在第一年开始时有 5 台机器, 伺候每周增加一台 ; 市场部最多需要 16 台机器 ; 销售部的每两个客户需要一台机器 第一年开始时, 公司没有客户, 但是销售模式指出第二年开始, 公司将有 6 个客户, 并且, 此后每周增加一个新客户的概率为 60%, 失去一个客户的概率为 20%, 或者以 20% 的概率维持原数目不变 (a) 如果市场部使用它所有的 16 个地址, 并且销售部和工程部向计划预期的那样, 那么, 至少在 7 年内, 支持此公司增长的计划的地址范围是什么? (b) 这样的地址分配可以维持多长时间? 当公司的地址空间用完时, 如何给三个部门分配地址? (c) 如果在 7 年内不使用 CIDR 编址方法, 那么, 新公司还有什么得到地址空间的选择? 回答 关于网络地址划分的问题, 在系统方法的教材 [1] 上谈的不多, 推荐参阅吴功宜的教材 [2] 的 P 页的相关内容以及案例 (a) 每个部门预计的机器数量增长如下 : 工程部 : 最初 5 个主机, 每一周至多增加 1 个,1 年为 52 周, 因此其 7 年需求量为 = 369 个主机 市场部 : 至多需要 16 台机器 销售部 : 需要为每两个客户配置 1 个主机 在第一年, 没有客户 第二年, 有 6 个客户 每周增加的客户比例是 1 60% 1 20% % = 0.4 所以该部门的 7 年的需求 ( )/2 = 个主机综上所述 : 总的机器数要求为 = 451 个主机, 因此这家新公司需要范围 512 的 IP 地址 (b) 地址使用过程中 : 假设支持 512 台主机的 IP 地址可以持续 x 年, 则需要满足 (5+52 x)+( (x 1))/ , 解该不等式得出 x 8.03, 即最多使用 8 年 届时的地址分配方案是 : 工程部 : = 421 市场部 :16 销售部 :( (x 1))/2 = (c) 申请地址范围 : 由于 B 类和 C 类支持 个主机地址和支持 254 个地址, 该公司可能要求得到一个 B 类或两个 C 类 网络地址 24

25 9.2 [1] 3-72 题目 表 6 是一个使用 CIDR 的路由表 地址字节为 16 进制 C /12 中的 /12 表示网络掩码的前 12 位为 1, 即 FF.F0.0.0 注意, 最后 3 个记录覆盖每一个地址, 因此可代替一条缺省路由 请说明下列地址将被送到的下一跳各是什么 : (a)c4.5e (b)c4.5e (c)c (d)5e (e)c4.6d.31.2e (f)c4.6b.31.2e 表 6: R1 路由表网络 / 掩码长下一跳 C /12 C4.5E.10.0/20 C /12 C /14 A B C D /1 E /2 F /1 G 解答 根据最长前缀匹配原则 (Longest Prefix Matching), 需要将到来的 IP 分组分别与前缀 20 的子网掩码进行运算和比对, 如果与路由器中的某一条记录匹配则根据该记录转发, 否则进行依次与前缀 的子网掩码进行运算和比对 运算过程如表格 7 所示 最终的具体结果为 : (a)c4.5e 下一跳是路由器 B (b)c4.5e 下一跳是路由器 A (c)c 下一跳是路由器 E (d)5e 下一跳是路由器 F (e)c4.6d.31.2e 下一跳是路由器 C (f)c4.6b.31.2e 下一跳是路由器 D 9.3 [2] 6-6 题目 如果将 /25 划分为三个子网, 其中子网 1 可以容纳 50 台计算机, 子网 2 和子网 3 分别容纳 20 台计算机, 要求网络地址从小到大依次分配给三个子网, 请写出三个子网的掩码与可用的 IP 地址段 解答 25

26 表 7: 根据最长前缀匹配原则查找路由表的过程 序号 目的地址 匹配前缀长度 目的网络 查表下一跳 a C4.5E C4.5E B b C4.5E C4.5E 无 14 C4.5C 无 12 C A c C C 无 14 C 无 12 C 无 2 C 无 E d 5E E 无 14 5E 无 12 5E 无 F e C4.6D.31.2E 20 C4.6D.30.0 无 14 C4.6C.0.0 无 12 C C f C4.6B.31.2E 20 C4.6B.30.0 无 14 C D 网络 /25, 即 , 其最多可以容纳的地址数量为 = 2 7 = 128, 地址范围从 到 ( 其中下划线标记了主机号对应的位 段 ), 即 到 根据网络地址的约定, 在每个子网内主机号全 0 的地址标识该网络的网络地址, 主机号全 1 的地址 标识该网络的广播地址, 因此三个子网所需要的地址总数量为 52,22,22 相应的, 最接近的地址块 大小为 64,32,32, 其总数为 128 对于子网 1 而言, 所需地址块大小 64, 相应的所需主机号位数为 log 2 (64) = 6, 所 以子网 1 的网络地址为 , 即 , 子网掩码为 , 即 对于子网 2 而言, 所需地址块大小 32, 相应的所需主机号位数为 log 2 (32) = 5, 所 以子网 2 的网络地址为 , 即 , 子网掩码为 , 即 同理可以计算子网 3 的地址 最终地址划分结果如下表所示, 其中可用主机地址范围排除了主机号部分全 0( 即子网网络地址 ) 和全 1( 即子网广播地址 ) 的两种情况 表 8: 子网地址划分结果子网名称子网子网掩码可用主机地址数量主机地址范围 子网 / 子网 / 子网 /

27 10 L10. 路由协议实现 10.1 [1] 3-48 题目 对于图 15 中给出的网络, 试述链路状态算法如何建立节点 D 的路由表 A 3 C 6 8 B 2 1 F 解答 D 2 E 图 15: 习题 的网络 参照 [1]P137 的表 3-14 的例子, 节点 D 建立路由表的步骤如表 9 所示 表 9: 节点 D 建立路由表的步骤步骤证实表试探表注释 1 (D,0,-) 因为 D 是证实表中唯一的新成员, 所以观察它的 LSP 2 (D,0,-) (A,8,A)(E,2,E) 因 D 的 LSP 表明, 我们可以以开销 8 到达 A, 比表中任何其 他路径都好, 因此把它加入试探表中, 同理 E 也加入 3 (D,0,-) (E,2,E) (A,8,A) 把试探表中开销最小的记录 E 加入证实表中, 接着, 检查 4 (D,0,-) (E,2,E) (D,0,-) (E,2,E) (C,3,E) (D,0,-) (E,2,E) (C,3,E) (D,0,-) (E,2,E) (C,3,E) (B,4,E) (D,0,-) (E,2,E) (C,3,E) (B,4,E) (A,6,E) (D,0,-) (E,2,E) (C,3,E) (B,4,E) (A,6,E) (F,9,E) (A,8,A) (B,4,E) (C,3,E) (A,8,A) (B,4,E) (A,6,E) (B,4,E) (F,9,E) (A,6,E) (F,9,E) (F,9,E) 证实表中新的成员 E 的 LSP E 的 LSP 告诉我们可以以开销 4 到达 B 以及以开销 3 到达 C 把试探表中开销最小的记录 C 加入证实表中, 观察它 的 LSP 因为通过 C 到达 A 的开销是 6, 所以替换记 录 (A,8,A),C 的 LSP 告诉我们可以开销 9 到达 F 把试探表中最小的开销记录 B 加入证实表中 把试探表中最小开销记录 A 加入证实表中 把试探表中开销最小的成员 F 移入证实表中, 结束 最终路由器 D 的路由表为 : 27

28 表 10: 路由器 D 的路由表序号目的地代价下一跳 1 A 6 E 2 B 4 E 3 C 3 E 4 E 2 E 5 F 9 E 10.2 [1] 3-54 题目 对于图 15 中给出的网络, 假设按照习题 46 建立所有的转发表, 然后 C-E 链路出错 给出 : (a)c 和 E 报告出错信息后,A B D 和 F 的表 (b)a 和 D 在它们下一次互相交换信息之后的表 (c)a 与 C 交换信息后,C 的表 解答 本题演示了距离向量路由算法的 计数到无穷 (count-to-infinity) 问题 当 C-E 链路出错 后,C E 间的链路距离将会被设置为 (a) 由链路状态算法可知,A B D F 的转发表变更为 : 表 11: 节点 A 转发表目的地开销下一跳 B - C 3 C D - E - F 9 C 表 13: 节点 D 转发表目的地开销下一跳 A - B 4 E C - E 2 E F - 表 12: 节点 B 转发表目的地开销下一跳 A - C - D 4 E E 2 E F - 表 14: 节点 F 转发表目的地开销下一跳 A 9 C B - C 6 C D - E - (b)a 和 D 交换信息后,A 和 D 的转发表如下 : (c)a 和 C 交换信息后,C 的转发表如下 : 28

29 表 15: A D 交换信息后, 节点 A 转发表目的地开销下一跳 B 12 D C 3 C D 8 D E 10 D F 9 C 表 16: A D 交换信息后, 节点 D 转发表目的地开销下一跳 A 8 A B 4 E C 11 A E 2 E F 17 A 表 17: 节点 C 转发表目的地开销下一跳 A 3 A B 15 A D 11 A E 13 A F 6 F 29

30 11 L11. 路由 -BGP 11.1 [1] 3-62 题目 在图 16 所示的网络中, 请给出前向搜索算法在建立节点 A 的路由数据库时如表 3-14 的步骤 D 5 E A 5 4 B C 回答 图 16: 习题 62 的网络 参考 [1]P137 的表 3-14, 节点 A 建立路由表的步骤如表 18 所示 表 18: 节点 A 建立路由表的步骤步骤证实表试探表注释 1 (A,0,-) 因为 A 是证实表中唯一的新成员, 所以观察它的 LSP 2 (A,0,-) (B,5,B)(D,2,D) 因 B 的 LSP 表明, 我们可以以开销 5 到达 B, 比表中任何其 他路径都好, 因此把它加入试探表中, 同理 D 也加入 3 (A,0,-) (D,2,D) (B,5,B) 把试探表中开销最小的记录 D 加入证实表中, 接着, 检查 证实表中新的成员 D 的 LSP 4 (A,0,-) (D,2,D) (B,4,D) (E,7,D) 因为通过 D 到达 B 的开销是 4, 所以替换记 (A,0,-) (D,2,D) (B,4,D) (A,0,-) (D,2,D) (B,4,D) (A,0,-) (D,2,D) (B,4,D) (E,6,D) (A,0,-) (D,2,D) (B,4,D) (E,6,D) (A,0,-) (D,2,D) (B,4,D) (E,6,D) (C,7,D) (E,7,D) 录 (B,5,B),D 的 LSP 告诉我们可以开销 7 到 E 把试探表中开销最小的记录 B 加入证实表中, 观察它 的 LSP (E,6,D) (C,8,D) 因为通过 B 到 E 的开销是 6, 所以替换记录 (E,7,D),B 的 LSP 告诉我们可以开销 8 到达 C (C,8,D) (C,7,D) 把试探表中最小的开销记录 E 加入证实表中, 接着检查证 实表中新的成员 E 的 LSP 因为通过 E 到达 C 的开销是 7, 所以替换记录 (C,8,D) 把试探表中开销最小的成员 C 移入证实表中, 结束 11.2 [2] 6-8 题目 根据如图 17 所示的网络结构与地址, 填写路由器 R1 的路由表 ( 与 R1 的 m0 接口连接的对方路由器的 IP 地址为 /24) 30

31 图 17: 路由信息图 回答 路由表的案例, 参见吴功宜教材 [2] 的 P222 页 5. 路由表的生成与使用 路由器 R1 与 R2 是直连链路, 所以该直连链路上的网络地址 /24 无需计入路由表 路由器 R1 与 LAN2 是经由 m2 连接的, 所以 LAN2 的网络地址 /24 应作为目的网络地址计入路由表 路由器 R1 需要缺省路由记录, 根据拓扑, 合理的缺省路由 ( /0) 是询问 m0 接口对应的路由器 其他待计入路由表的网络 LAN1 和 LAN2 的网络地址 / /16 由于该拓扑是一个环形拓扑, 所以到网络 LAN1( /16) 分别有两个路径 在没有给定相应的链路的代价情况下, 我们缺省认为以跳数作为代价, 这两个等代价的路径都应该计入 R1 的路由表 到网络 LAN2 的也有两条路径, 只需要计入较短的一条 综上,R1 的路由表有 1 条直接交付的路由 ( 至 LAN2),1 条向 Internet 发送的路由 (m0),2 个间接交 付的 LAN1 和 LAN3 共有 3 条路由, 一共需要加入 5 条路由表的记录, 如表 19 所示 : 表 19: R1 路由表 序号 目的网络 下一跳地址 输出端口 /24 - m / m / m / m / m0 31

32 12 L12.IPv6 与移动 IP 协议 12.1 [1] 4-5 题目 假设 P Q 和 R 是网络服务提供商, 各自的 CIDR 地址分别为 C /8 C /8 和 C /8 每个提供商的客户最初接收的地址分配是提供商地址的一个子集 P 有如下客户 : PA, 分配地址 C1.A3.0.0/16 PB, 分配地址 C1.B0.0.0/12 Q 有如下客户 : QA, 分配地址 C2.0A.10.0/20 QB, 分配地址 C2.0B.0.0/16 假设没有其他提供商和客户 (a) 给出 P Q 和 R 的路由表, 假设每个提供商都和另外两个提供商连接 (b) 现在假设 P 连接 Q,Q 连接 R, 但 P 和 R 不直接连接 给出 P 和 R 的路由表 (c) 假设除现有链路外, 客户 PA 需要一条到达 Q 的直接链路, 且 QA 需要一条到达 P 的直接链路 给出 P 和 Q 的路由表, 忽略 R 回答 (a) 根据最长前缀匹配, 可知 P Q 和 R 的路由表分别如下 : 表 20: P 的路由表目的地址下一跳 C / 8 C / 8 C1.A3.0.0/ 16 C1.B0.0.0/ 12 Q R PA PB 表 21: Q 的路由表 目的地址 C / 8 C / 8 C2.0A.10.0/ 20 C2.0B.0.0/ 16 下一跳 P R QA QB 表 22: R 的路由表目的地址下一跳 C / 8 C / 8 (b) 与 (a) 稍有不同在于 P 的路由表中修改去 R 的路由信息, 需要经由 Q 转发 ; 以及 R 的路由表中修 改去 P 的路由信息, 需要经由 Q 转发, 修改的信息如下 : P: C / 8 Q R: C / 8 Q (c) 由于现需要 PA 与 Q 以及 QA 与 P 的直连, 故修改相应的路由表如下 : P Q 表 23: P 的路由表目的地址下一跳 C / 8 C2.0A.10.0/ 20 C1.A3.0.0/ 16 C1.B0.0.0/ 12 Q QA PA PB 表 24: Q 的路由表 C / 8 P C1.A3.0.0/ 16 PA C2.0A.10.0/ 20 QA C2.0B.0.0/ 16 QB 32

33 12.2 [1] 4-20 题目 判断以下 IPv6 地址的表示是否正确 (a)::0f53:6382:ab00:67db:bb27:7332 (b)7803:42f2:::88ec:d4ba:b75d:11cd (c)::4ba8:95cc::db97:4eab (d)74dc::02ba (e)::00ff: 回答 (a) 正确 ; (b) 错误, 没有 ::: 这种缩写形式 ; (c) 错误,:: 这种缩写形式只可用于一个地址中连续多个 0 的集合 ; (d) 正确 ; (e) 正确 33

34 13 L13.TCP-I 13.1 [1] 5-9 题目 假设你受雇设计一个使用滑动窗口的可靠的字节流协议 ( 如像 TCP) 这个协议将运行在 100Mbps 的网络上 网络的 RTT 是 100ms, 而且数据段的最大生存期是 60 秒 (a) 应该在协议首部的 AdvertisedWindow 字段和 SequenceNum 字段中包含多少比特? (b) 怎样确定上述数值, 哪个值可能不太确定? 回答 (a)tcp 是一个字节流协议, 它的缺省通告窗口 AdvertisedWindow 字段为 16 (bit), 有效的大小为 2 16 = (byte) = 64 (KB), 它的序号 SequenceNum 字段为 32 (bit), 是 AdvertisedWindow 大小的两倍 接收方通告窗口字段应该具有记录发送方的发送窗口中字节数的能力, 我们由此可以估测 AdvertisedWindow 字段的长度 发送方的发送窗口的设置需要考虑两点, 一是接收方的缓存大小, 二是链路的带宽时延积 题目没有提到接收方缓存大小的限制, 因此我们假设接收方拥有足够大的缓存作为接收窗口, 只考虑保持 100(Mbps)*100(ms) 的链路管道满载的需求来估算发送窗口的最大值 链路的带宽时延积为 100(Mbps) 100(ms) = 10 7 (bit) = (byte) 将 AdvertisedWindow 的字段长度记为 k (bit), 接收窗口可以描述的字节数需要大于链路的带宽时延积的字节数, 即 : 2 k 解之,k log 2 (10 7 ) 3 = 因此,AdvertisedWindow 字段至少需要 k = 21 (bit) SequenceNum 的设置需要考虑两点, 一是必须是 AdvertisedWindow 大小的两倍以保证不出现序号重复 ; 二是支持数据段的最大生存期, 即可以描述数据量 100(Mbps) 60(s) = (bit) = (byte) 将 SequenceNum 的大小记为 s bit, 需要满足 : (1)s k + 1; (2)2 s 解之,s 22 且 s 因此,SequenceNum 字段至少需要 s = 30 (bit) (b) 上述计算中带宽时延积是对网络传输通道容量的刻画, 其中带宽是固定的, 但是 RTT 会随着传输路径和传输负载的改变而改变, 因此其可能不太确定 另外, 最大生存时间 MSL(Maximum Segment Life) 是一个用户自定义的变量, 反映了用户对端对端的网络时延 网络复杂性等因素的估计, 也是可能不太确定的 13.2 [2] 7-10 题目 34

35 图7-29给出了TCP连接建立的三次握手与连接释放的四次握手的过程示意图 请根据与TCP协议 hu s t.e du. cn 的工作原理 写出(1) (8) 位置的序号值 图 18: 7-29的TCP握手过程示意图 回答 TCP的连接建立和断开的过程需要发送方和接收方的信令交互 通过TCP报文首部的标志位和 w 序号值来实现 TCP报文段的首部格式如下图19所示 liu 在TCP的报文头部包括少量标志位字段 标志位字段只有1 bit 值为1或者0 表示是否启动该标 志 与TCP连接建立与释放相关的包括SYN 连接建立 FIN 连接释放 ACK 确认 等 TCP报文段首部还包括两个记录序号的字段 即seq 报文段序号 和ack 确认序号 其取值 范围为(0 232 ) (a) 记发送方为S 接收方为R 则TCP连接建立的三次握手过程可以表示为 第一次握手(S R) [SYN=1,ACK=0,seq=x] 其中 标志位[SYN=1,ACK=0]表示S请求建立连接 根据TCP规定 SYN=1的连接建立报文不 携带数据 仍然要消耗一个数据段的序号 这里[seq=x]是S选择的初始数据段序号 第二次握手(S R) [SYN=1,ACK=1,seq=y,ack=x + 1] 其 中 [SYN=1,ACK=1,ack=x + 1] 表 示R向S回 复 确 认 收 到 了 刚 才 序 号 为x的 建 立 请 求 报 文 根据TCP规定 SYN=1的连接建立报文不能携带数据 仍然要消耗一个数据段的序号 这 里[seq=y]是R选择的初始数据段序号 第三次握手(S R) [SYN=0,ACK=1,seq=x + 1,ack=y + 1] 35

36 图 19: TCP 报文段示意图其中 :[SYN=0,ACK=1,ack=y + 1] 根据 TCP 规定,SYN=0,ACK=1 的报文可以携带数据, 下一个数据段的序号为 [seq=x + 1] 在本题中 S 的 IP 地址为 ,R 的 IP 地址为 ,x = 10020,y = 25609, 因此 : 第 6 行,R 发送的第二次握手报文的 ack 序号 1 为 x + 1 = 10021; 第 7 行,S 发送的第三个握手报文的 SEQ 序号 2 为 x + 1 = 10021,ack 序号 3 为 y + 1 = (b) 记发送方为 S, 接收方为 R, 则 TCP 连接释放的四次握手过程可以表示为 : 第一次握手 (S R) [FIN=1,ACK=0,seq=x,ack=y] 其中 : 标志位 [FIN=1,ACK=0] 表示 S 请求释放连接 ; 序号 [seq=x] 记录 S 发出的请求报文的序号 ; 根据 TCP 规定,FIN=1 的报文需要消耗掉一个数据段序号 ; 这里 [seq=x] 是 S 结合上文待发送的数据段序号 ; 而 [ack=y] 表示 S 期待从 R 收到的下一个数据段 第二次握手 (S R) [FIN=0,ACK=1,seq=y,ack=x + 1] 其中 :[ACK=1,ack=x+1] 表示 R 向 S 回复确认收到了序号为 x 的建立释放报文 ;[FIN=0] 表示 R 并 没有立即请求释放连接, 此时 TCP 进入了半关闭状态,S 不会向 R 发送数据, 但是 R 还可以向 S 发送数 据并且等待其上层应用取走缓存中的数据 序号 [seq=y] 表示发送刚才 S 期待接收的数据段 第三次握手 (S R) [FIN=1,ACK=1,seq=z,ack=x + 1] 其中 :[FIN=1,ACK=1,ack=x + 1] 表示 R 向 S 发起连接释放的请求, 且该连接释放请求是对先前序号为 x 的报文的确认 序号 [seq=z] 记录当前 R 向 S 发送的数据段序号 ; 在实际情况中,R 可能在第二次握手后继续向 S 发送数据, 即 (z y) 但是在本例中, 该第三次握手的报文和第二次握手被连续观测到的, 期间并没有发送数据, 因此 z = y 第四次握手 (S R) [FIN=0,ACK=1,seq=x + 1,ack=z + 1] 其中 :[FIN=0,ACK=1,ack=z + 1] 表示 S 向 R 回复确认收到了刚才序号为 z 的建立释放报文, 至此双方都确认没有数据需要发送, 即各自完成一次 FIN=1 的断开信令过程 ; 根据 TCP 规定,FIN 报文需要消耗一个序号, 因此 S 的第四次握手的序号为 [seq=x + 1] 在本题中 S 的 IP 地址为 ,R 的 IP 地址为 第 24 和 27 行的 S 的地址应为 ; 第 23 和 24 行的 SQL 应为 SEQ 相应的报文内 SEQ 和 ack 的关系为 : 第 25 行,S 向 R 发送第一次握手报文, 其 SEQ 序号为 x = 16955;ack 为 y = 60036; 第 26 行,R 向 S 发送第二次握手报文, 其 SEQ 序号 4 应为刚才 25 行 ack 序号, 即 y = 60036,ack 序号 5 为第 25 行 36

37 的 SEQ 增 1, 即 x + 1 = 16956; 第 27 行,R 向 S 发送第三次握手报文, 其 SEQ 序号 6 应为刚才 26 行 SEQ 重复, 即 z = y = 60036,ack 序号应与第 26 行的 ack 相同, 即 x + 1 = 16956; 第 28 行,S 向 R 发送第三次握手报文, 其 SEQ 序号与第 27 行的 ack 相同, 即 x + 1 = 16956,ack 序号为第 27 行的 SEQ 增 1, 即相同 y + 1 = 60037; 综上, 最终答案为 :110021; ; ; ; ; ; ;

38 14 L14.TCP-II 14.1 [1] 6-16 题目 假设 TCP 实现一个扩展, 允许窗口大小远大于 64KB 假定你用这一扩展 TCP 在一条延迟为 100 毫秒的 1Gbps 链路上传送一个 10MB 的文件, 而且 TCP 接收窗口为 1MB 如果 TCP 发送 1KB 的分组 ( 假设无拥塞, 无丢失分组 ): (a) 当慢启动打开发送窗口达到 1MB 时用了多少 RTT? (b) 发送该文件用了多少 RTT? (c) 如果发送文件的时间由所需的 RTT 的数量与链路延迟的乘积给出, 传输的有效吞吐量是多少? 链路带宽的利用率是多少? 回答 在 TCP 报文头部的原始设计中,AdvertisedWindow 的长度为 16bit, 即 2 16 = = 64 KB 因此, 原始 TCP 的最大有效发送窗口大小为 64KB 题目的第一句话松弛了这一约束 (a) 这个 TCP 会话通过链路的时延带宽积是 TCP 发送窗口的物理极限值 w max, 即 w max = 1(Gbps) 100(ms) = (bit) = (bit) = (MB) 本小题中,1MB 的发送窗口和接收窗口并没有超过链路的带宽时延积, 是可以达到的 TCP 有效发送窗口 w send 大小为流量控制的接收窗口 (w ad, 即协议中的 AdvertisedWindow) 和拥 塞控制的拥塞窗口 (w cwnd, 即 CongestionWindow) 的最小值, 即 w send = min(w ad, w cwnd ) 在不考虑 拥塞的情况下, 初始情况下影响 TCP 发送窗口的主要因素是 w cwnd 的增长 在慢启动阶段,w cwnd 的原始大小是 1 倍的数据段 (segment) 大小, 即 1 KB 成功传输一次 RTT 之 后, 窗口变为原来的 2 倍, 成功传输 i 个 RTT 之后,w cwnd = 1 2 i KB 根据题意, 设 x 个 RTT 后窗口达到 1(MB), 则 2 x = 1024(KB) 因此 x = log 2 (1024) = 10 这 时,TCP 已经完成了 10 次 RTT 的传输,TCP 发送窗口达到 1MB, 并在即将进行的第 11 次发送生效 (b)tcp 有效发送窗口 w send = min(w ad, w cwnd ) 当发送窗口超过 1MB 之后,w cwnd w ad, 控 制 TCP 流速的主要参数为 w ad 因此该传输过程可以分为两个阶段 : 第一个阶段是拥塞控制的慢启动机制起主要作用,w send 随 着 w cwnd 而 2 倍增长 ; 当 w send 达到 w ad 限制后, 即进入第二阶段, 该阶段是流量控制机制起作用, 此 时 w send 保持不变 第一阶段 : 达到 1(MB) 的发送窗口需要 10RTT 时间, 总共传输的数据有 Y = 10 i=1 (2i 1 ) 1(KB) = ( ) 1(KB) = (2 10 1) 1(KB) = 1MB 1KB. 第二阶段 : 受限于接收方的缓存 w ad = 1 (MB), 后续的数据发送过程中, 每个 RTT 只能传 输 1(MB) 待发送数据大小为 10MB (1MB 1KB) = 9MB + 1KB, 则还需要 10 个 RTT 传输剩余 的数据 所以总共需要 10+10=20RTT 完成文件的传输 (c) 如果发送窗口主要由带宽时延积给出, 即释放了接收窗口大小为 1MB 的约束 由于 w max > 10 MB, 因此该文件可以在慢启动阶段完成传输 假设传输文件需要 x 个 RTT, 则有 ( x 1 ) 1(KB) 10(MB) 2 x

39 解之,x log 2 (10241) = 13.32, 因此,x = 14, 即传输这个文件将花费 14 个 RTT 该过程中的吞吐量为 为 59.92MB/1Gbps = 5.99% 10(MB) (ms) = /1.4(bps) = 59.92(Mbps), 则链路带宽的利用率 14.2 [2] 7-8 题目 假设 TCP 拥塞控制的 AIMD 算法中, 慢开始 SST1 的阈值设置为 8, 当拥塞窗口上升到 12 时, 发送端检测出超时,TCP 使用慢启动与拥塞避免 试给出第 1 次到第 15 次传输的拥塞窗口分别为多少? 回答 TCP 的慢启动和拥塞避免的详细讨论, 参见吴功宜教材 [2] 的 P 页的案例与讨论 (1) 慢启动阶段 当 TCP 连接初始化时, 将拥塞窗口大小 (CongestionWindow, cwnd) 设置为 1 慢 启动的阈值 SST1(Slow-start Threshold, SST) 设置为 8 在慢启动阶段, 当 cwnd 经过 3 个往返传输之 后, 按照指数算法已经增长到 8 时, 进入 拥塞避免 控制阶段 这个过程经过了 3 个往返的过程 (2) 拥塞避免阶段 进入拥塞避免阶段之后,cwnd 按照线性的方法增长,cwnd 值从 8 上升到 12, 经过了 4 个往返过程 (3) 超时后窗口调整 cwnd=12 时, 发送端检测出现超时, 认为网络处于拥塞状态, 第 8 个往返时拥塞窗口 cwnd 重新回到 1 (4) 重新进入慢启动与拥塞控制 当出现一次网络拥塞之后的慢开始阈值 SST2 设置是出现超时的 cwnd 最大值的 1/2, 即 SST2=12/2=6, 然后重新开始慢启动与拥塞避免的过程 (5) 慢启动 第 8 个往返的拥塞窗口取 cwnd=2 0 = 1; 按照指数增长, 第 9 个往返的 cwnd=2 1 = 2; 第 10 个往返 cwnd=2 2 = 4; 第 11 个往返 cwnd 不能够超过 SST2=6,cwnd=6. (6) 加性增加 第 12 个往返的 cwnd 在 6 的基础上加 1,cwnd=7; 以此类推, 第 个往返的 cwnd 分别应该等于 按照上述分析和计算的 TCP 拥塞控制过程如图 20 所示 (KB) 图 20: GBN 工作示意图 第 1 个往返到第 15 个往返的 cwnd 值分别为

40 参考文献 [1] Larry L. Peterson and Bruce S. Davie. Computer Networks: A Systems Approach (Fifth Edition). Morgan Kaufmann, [2] 吴功宜. 计算机网络. 清华大学出版社 ( 第三版 ), [3] 谢希仁. 计算机网络. 电子工业出版社 ( 第六版 ),