网络课堂练习答案.pdf

第一次课 1 a 中法两国外长需要通过电话达成某项协议 但两人都不会对方的 语言 另两人都没有带能将自己的语言翻译为对方语言的翻译 然而 两国外长都带着英语翻译 试画图描述这种情况并描述每个层次的交 互过程 b 现假设中国外长的译员掌握日语 而法国外长有一德语翻译 重新 画图并描述 2 2 答案 a The PMs speak as if they are speaking directly to each other For example when the French PM speaks he addresses his remarks directly to the Chinese PM However the message is actually passed through two translators via the phone system The French PM s translator translates his remarks into English and telephones these to the Chinese PM s translator who translates these remarks into Chinese b An intermediate node serves to translate the message before passing it on 2 广播网络是从任一连接在网上的站点发出的信息都会被所有网上的 其他站点收到的网络 例如总线拓扑的局域网 如以太网 以及无线电 网络 请讨论在广播网上网络层 OSI第3层 是否需要 2 5 答案 2 5 可以从两个方面考虑 1 首先从网络层执行的功能来看 它负责数据在网络中的路由 但 是在广播网络中不需要路由 网络层的其他功能如在端系统间的顺序检 测 流量控制和差错控制可以在第2层完成 因为在没有中间交换结点 的情况下数据链路层是直接连接两个端系统的 因此从这个角度看不需 要网络层 2 从上层协议使用网络层的角度来看 上层协议将自己视为通过一 个接入点连到网络来与其他主机通信 负责确保数据通过网络传输到其 他端系统的层次是网络层 因此从这个角度考虑网络层是需要的 事实上 广播网络中OSI的第2层分为两个子层 较低的子层关心媒体访 问控制 MAC 它负责任一时刻仅有一个端系统传输数据 同时还负责 在LAN上定 位其他端系统 较高的子层称为逻辑链路控制 LLC 它执 行通常的链路控制功能 有了MAC LLC 可以不需要网络层 但是可能需 要一个互联网层 3 在图2 4中 一个第N层上的协议数据单元 PDU 正好被装配在第 N 1 层的一个PDU中 也可能将一个第N层的PDU分解为多个 N 1 层 的PDU 这叫做分段 或多个N层的PDU组合成一个 N 1 层的PDU 这叫做 组块 a 对于分段的情况 每一个 N 1 层的段必须 包括一个第N层 的首部的副本吗 b 对于组块的情况 将第N层的多个PDU打包到一个第 N 1 层的 PDU中时 需不需要将各个第N层PDU的首部保留不变 抑或是将它们合 并成一个具有单个第N层首部的第N层PDU 2 7 答案 2 7 a 不需要 如果这样做将违反层间的分离原理 对 N 1 层来说 N层的PDU仅仅是一块数据 它根本不知道N层PDU的内部格式 它只要将 它分解成多个段并在接收端按正确的次序组装它 b 各个第N层PDU的首部必须保持不变 理由同 a 1 一个4480字节的数据报要进行传输并需要分片 因为它要经过一个 最大有效载荷1500字节字节的以太网 画出每个数据报片的总长度 More标志和分片偏移字段的值 3 8 答案 3 8 原数据报包含20字节的首部和4460字节的数据字段 以太网帧能装 载1500字节的数据 故它能装载首部为20字节数据字段为1480字节的IP 数据报 注意到1480字节能被8整除 因为数据字段长度必须为64 bit的 整数倍 所以除了最后一个数据报片外 其他的数据报片都能使用最 大长度 1480字节 因此每个IP数据报片如下 数据报片1234 总长度15001500150040 More标志1110 偏移0185370555 2 一个运输层报文由1500 bit的数据和160 bit的首部组成 它被送 到一个互联网层 被互联网层加上160 bit的首部 这个数据报然后经 过两个网络进行传输 每个网络都使用24 bit的分组首部 目的网络 的最大分组长度是800 bit 把分组首部计算在内 一共有多少位被交 付给了目的端的网络层 3 11 3 11 数据加上运输层首部加上互联网层首部共1820 bit 整个数据报 被分段为一系列分组进行传输 其中每个分组包含24 bit的网络首部加 上至多为776 bit的高层数据 需要3个分组 因此交付给目的端网络层 的位数为 1820 3 24 1892 bit 3 比较IPv4首部和IPv6首部的单个字段 考虑每一个IPv4字段所提 供的功能 试说明在IPv6中是如何提供这些功能的 3 12 3 12 版本 IPv6首部中有同样字段 其值由4变为6 网际首部长度 IHL 去除了 因为IPv6首部的长度的固定的所以不需 要 服务类型 去除了 该字段的前3个比特定义了8个优先级值 在IPv6首 部中被通信量类型字段中的优先级子字段所取代 它同样为非拥塞控制 的通信量定义了8个优先级值 该字段的剩余比特处理可靠性 时延和 吞吐量等问题 IPv6中的等价功能可通过流标号字段来实现 总长度 被IPv6首部中的有效载荷长度所取代 标识符 相同的字段出现在IPv6的分片首部中 标志 More 位出现在IPv6的分片首部中 IPv6中分片只允许在源结 点进行 因此去除了 Don t Fragment 位 片偏移 相同的字段出现在IPv6的分片首部中 生存时间 TTL 在IPv6首部中被跳数限制所取代 两者在实践中同样 处理 协议 在IPv6首部中被下一个首部所取代 它或者指出下一个IPv6扩展 首部 或者指出使用IPv6的协议 首部校验和 因考虑到计算该校验和影响性能 所以去除了该字段 源地址 目的地址 32比特的IPv4源地址 目的地址字段在IPv6首部中被 128比特的源地址 目的地址所取代 1 对于一个交换网络定义下列参数 N 给定的两个端系统之间经过的跳数 L 以bit为单位的报文长度 B 数据率 单位是bps P 固定的分组长度 单位是bit H 每个分组中的额外开销 首部 位 S 呼叫建立时间 电路交换或虚电路 单位是s D 每跳的传播时延 单位是s a 对于D 4 L 3200 B 9600 P 1024 H 16 S 0 2 D 0 001 计算电路交换 虚电路分组交换和数据报分组交换的端到端时延 假 定不存在确认并忽略结点处理时间 b 对于 a 中的三种交换方式 推导时延的一般表达式 每次对两种 方式进行比较 找到其时延相等的条件 4 2 4 2 a 电路交换 T C1 C2 其中 C1 呼叫建立时间 C2 报文传播时间 C1 S 0 2 C2 传播时延 传输时延 N D L B 4 0 001 3200 9600 0 337 T 0 2 0 337 0 537 sec 数据报分组交换 T D1 D2 D3 D4 其中 D1 所有分组经过第1跳的传输时延和传播时间 D2 最后一个分组经过第2跳的传播时间 D3 最后一个分组经过第3跳的传播时间 D4 最后一个分组经过第4跳的传播时间 每个分组的数据部分长度为 P H 1024 16 1008 bit 一个 3200 bit的报文需要4个分组 3200 bits 1008 bits packet 3 17 packets D1 4 t p 其中 t 一个分组的传输时延 p 一跳的传播时延 D1 4 P B D 4 1024 9600 0 001 0 428 D2 D3 D4 t p P B D 1024 9600 0 001 0 108 T 0 428 0 108 0 108 0 108 0 752 sec 虚电路分组交换 T V1 V2 其中 V1 呼叫建立时间 V2 数据报分组交换时间 T S 0 752 0 2 0 752 0 952 sec b 电路交换 vs 数据报分组交换 Tc 端到端时延 电路交换 Tc S N D L B Td 端到端时延 数据报分组交换 Td D1 N 1 D2 D1 所有分组经过第1跳的传输时延和传播时间 D2 最后一个分组经过1跳的传播时间 D1 Np P B D D2 P B D Td Np N 1 P B N D S L B Np N 1 P B 电路交换 vs 虚电路分组交换 TV 端到端时延 虚电路分组交换 TV S Td TC TV L Np N 1 P 数据报分组交换 vs 虚电路分组交换 TV Td S Td S 0 2 在上题中 对于数据报网络而言 当P取什么值时 以N L和H的函 数表示 端到端时延最小 假定L比P大得多而D 0 4 3 4 3 从4 2中我们得到Td Np N 1 P B N D 为方便计算我们假设Np L P H 为一个整数 另有D 0 因此 Td L P H N 1 P B 为得到最小时延 我们求导 0 dTd dP 0 1 B L P H N 1 P B L P H 2 0 L P H N 1 P H 2 LP 0 LH N 1 P H 2 P H 2 LH N 1 P H 1 局域网中争用方式的缺点是由于多个站点在同一时间试图接入总线 时会引起总线容量浪费 假设将时间分为离散的时隙 总线上的N个站 点在每个时隙都分别以概率p试图接入总线 那么由多个同时的发送企 图所引起的时隙浪费占多大比例 6 3 6 3 时隙浪费是由于多个站试图同时发送引起的 其概率等于两个站 或多个站在同一时隙试图传输的概率 Pr 2个或多个站试图传输 1 Pr 0个站试图传输 Pr 仅1个站 试图传输 1 1 p N Np 1 p N 1 2 假定1 km长的CSMA CD网络的数据率为1 Gbps 设信号在网络上的 传播速率为200000 km s 求能够使用此协议的最短帧长 第2题 传播时延 媒体长度 信号传播速率 传输时延 帧长 数据率 以太网中为检测冲突 要求传输时延 2倍的传播时延 因此 最短帧长 2 媒体长度 信号传播速率 数据率 10000 bit 即1250 字节 1 有人提出了一种叫做许可证控制的拥塞控制技术 在这种方案中 通过向网络中插入固定数目的通行证 使网络中正在传送的分组数目 可以保持固定 这些通 行证在帧中继网中随机地传播 每当一个帧处 理模块要将与其相连的用户发送给它的一个帧转发出去 就必须先捕 获并毁掉一个通行证 当与目的用户相连的帧处理 模块将帧交付给该 用户时 帧处理模块就重新发出一个通行证 列出这一技术的三种潜 在问题 10 1 10 1 1 该项技术只能限制整个网络中正在传送的分组数目 并不能 保证网络中某个特定结点不会充斥大量分组而导致拥塞 2 通行证在网中随机传播 没有好的方法将通行证分配到最需要它 的地方 可能造成网络利用率降低 3 如果通行证在网中传播时由于偶然因素遭到破坏 整个网络的容 量就不知不觉降了下来 并没有提供相应机制解决这个问题 1 一个信道的数据率是4 kbps而传播时延是20 ms 帧的大小在多大 范围之内才能使停止等待的效率至少达到50 11 2 11 2 设L为帧长度 有a 传播时间 传输时间 20 10 3 L 4 103 80 L 而要求S 1 1 2a 0 5 可求得L 160 2 在讨论停止等待ARQ的时候没有提到拒绝帧 REJ 对停止等待 ARQ而言 为什么REJ0和REJ1是不必要的 11 6 11 6 在停止等待ARQ中 发送方如果没有收到接收方发来的ACK 会由 于定时器超时而重发数据 因此可以不需要REJ帧 但是如果使用REJ帧 可以尽可能早地通知发送方重发数据 从而提高效率 3 假设一个拒选ARQ方案的n 4 通过举例说明需要一个3 bit的序 号 11 7 11 7 假设使用一个2 bit的序号 1 结点A向结点B发送帧0 1和2 2 结点B收到全部3个帧 并使用累积确认向A发送RR3 3 RR3在传输过程中丢失了 4 结点A超时后重发帧0 5 B已经将其接收窗口调整到准备接收帧3 0 1 2 因此它收到重 发的帧0后会以为帧0是一个新帧而帧3在传输过程中丢失了 4 两个相邻的结点 A和B 使用具有3位序列号的滑动窗协议 作为ARQ 机制 使用窗口大小为4的go back N 假设A正在传送而B正在接收 画出下列事件序列的窗口位置 a 在A发送任何帧之前 b 在A发送了帧0 帧1 帧2并且接收到B对帧0和帧1的应答之后 c 在A发送了帧3 帧4和帧5并且B确认了帧4而ACK已经被A收到了 11 9 5 在图中结点A产生的帧经由结点B发往结点C 确定要使B不溢出 结 点B和结点C之间所要求的最小传输速率 条件如下 l A和B之间的数据率是100 kbps l 两条线路的传输时延都是5 m km l 结点之间的链路是全双工链路 l 所有数据帧长度都是1000 bit ACK帧是单独发送的 其长度可以 忽略 l 在A和B之间使用窗口大小为3的滑动窗协议 l 在B和C之间使用停止等待协议 l 无差错发生 11 4 11 4 在A到B之间的链路上有 传播时延 4000 5 ms 20 ms 每帧的传输时延 1000 100 103 10 ms 在B到C之间的链路上有 传播时延 1000 5 ms 5 ms 每帧的传输时延 1000 R 其中R为欲求的B和C之间的最小传输速率 为了不使B的缓存发生溢出 进入和离开B的平均帧的个数在较长时段内 应该相同 换句话说 就是两条链路上的绝对吞吐量的值应该相等 A到B之间的链路采用滑动窗机制 其相对吞吐量公式为 其绝对吞吐量为 B到C之间的链路采用停止等待协议 其相对吞吐量公式为 S 1 2a 1 这里a 5 1000 R R 200 绝对吞吐量表达式为 1 2 R 200 1 R 令 1 2 R 200 1 R 60 kbps 可求得R 150 kbps 本题也可不利用推导的公式 根据滑动窗机制和停止等待的原理直接分 析 A能够向B连续发送3个帧 然后等待第1个帧的确认才能发送其他的帧 第一个帧传输时间为10 ms 传播时间为20 ms 确认帧的传播时间为20 ms 所以第1个帧的确认返回A需要50 ms 即A在50 ms时间内能向B发送 3个帧 B每次只能向C发送一个帧 然后等待确认才能发送下一个帧 确认帧返 回需要10 1000 R ms 即B在10 1000 R ms时间内能向C发送1个帧 因此有 3 10 1000 R 50 从而R 150 kbps 1 原来的TCP SRTT估值器碰到的一个困难是对初值的选取 在没有任 何特殊网络状况知识的情况下 典型的方法是选择一个任意值 例如3 秒 并希望这会快速收敛到准确的数值 如果这个估值太小 TCP就会 进行不必要的重传 如果它太大 TCP在第一个报文段丢失后要等待很 长的时间才重传 还有 收敛可能很慢 本题对此加以说明 a 选择 0 85而SRTT 0 3 s 假设所有测量的RTT 1 s并且没有出现分组丢失 SRTT 19 是多少 b 现在令SRTT 0 1 s 假定测量的RTT 3 s并且没有出现分组丢失 SRTT 19 是 多少 12 5 12 5 进行公式变换 因为RTT K RTT K 1 RTT 1 RTT 因此SRTT K a SRTT K 1 1 a RTT K a2SRTT K 2 a 1 a RTT K 1 1 a RTT K a2SRTT K 2 1 a 1 a RTT aKSRTT K 2 1 a 1 a a2 aK 1 RTT aKSRTT 0 1 aK RTT a SRTT 19 1 1 sec b SRTT 19 2 9 sec 两种情况下收敛速度都比较慢 因为SRTT的初始值选的不合适 2 虽然带有拥塞避免的慢启动是对付拥塞的一种有效方法 但它在高 速网络中可能导致很长的恢复时间 这个问题表明了这一点 a 假定往返时延为60 ms 大约是跨越一个大陆的时间 而链路的可用带宽是1 Gbps 报文段的大小是576字节 确定要保持管道充满所需的窗口大小以及使用 Jacobson方法在一个超时后到达该窗口要花的时间 对于16 KB的报文段大小重复 a 12 11 12 11 a W 109 0 06 576 8 13000 如果窗口大小从1开始线性增长 需要经过大约13000个往返时间窗口大 小才能增加到最大 这需要大概13分钟 如果窗口大小从1开始使用慢启动增长到窗口大小为13000 2后再线性增 长 需要log26500 6500 6512 次往返时间 即6 5分钟 b W 109 0 06 16000 8 460 相应的数值为460 28秒 238 14秒 1 设某路由器建立了如下路由表 三列分别是目的网络 子网掩码和 下一跳路由器 若直接交付则最后一列表示从哪一个接口转发出 去 128 96 39 0 255 255 255 128 接口0 128 96 39 128 255 255 255 128 接口1 128 96 40 0 255 255 255 128 R2 192 4 153 0 255 255 255 192 默 任 R4 现共收到5个分组 其目的站IP地址分别为 1 128 96 39 10 2 128 96 40 12 3 128 96 40 151 4 192 4 153 17 5 192 4 153 90 试分别计算其下一跳 1 1 接口0 2 R2 3 R4 4 R3 5 R4 2 假定网络中的路由器B的路由表有如下的项目 这三列分别表示目的 网络 距离和下一跳路由器 N1 7 A N2 2 C N6 8 F N8 4 E N9 4 F 现在B收到从C发来的路由信息 这两列分别表示目的网络和距 离 N2 4 N3 8 N6 4 N8 3 N9 5 试求出路由器B更新后的路由表 2 N1 7 A 无新信息 不改变 N2 5 C 相同的下一跳 更新 N3 9 C 新的项目 添加进来 N6 5 C 不同的下一跳 距离更短 更新 N8 4 E 不同的下一跳 距离一样 不改变 N9 4 F 不同的下一跳 距离更大 不改变 3 图15 6涉及的计数到无穷大问题即使在没有网络是不可达的情况下 也会出现 在图15 6中加上一个广域网 连接C和D 每个方向的链路 耗费是10 a 为每个路由器给出到网络5的距离L x 5 和下一跳R x 5 b 现在假设网络3失效 相应的路由将调整为经过C到D的链路 路由的变更是从B 发现到D的路由不可用开始的 为每个路由器给出稳定的新路由产生以后L x 5 和R x 5 的值 15 7 15 7 a RouterDistance L x 5 Next Hop R x 5 A3B B2D C3B D1 b RL x 5 R x 5 L x 5 R x 5 L x 5 R x 5 L x 5 R x 5 L x 5 R x 5 A3B4C5C 11C12C BUU4C5C 11C12C C3B4A5A 11A11D D1 1 1 1 1 Iteration 1 Iteration 2 Iteration 3 Iteration 9 Iteration 10 U Unreachable 1 在讨论图16 2 下页左图 时 我们讨论了将一个分组发送给多播地 址的3种方法 广播 多个单播和真 正的多播 然而还有另一种方法 就是洪泛法 源点将分组发送给它的所有相邻路由器 每个路由器收 到分组时要在除接收到分组的接口以外的所有输出接口上转发该 分 组 每个分组都标记有一个唯一的标识符 路由器不会对同一个分组 洪泛多次 计算该方法所产生的分组副本数 并对其结果做出说明 16 2 16 2 N1N2N3N4N5N6L1L2L3L4L5Total 1111111211213 2 大多数多播选路协议 如MOSPF 都使得每个组成员的路径耗费最 小 但它们并不从整体上优化对互联网的使用 本题就要说明这个事 实 a 一个源点的分组按照图16 3 a 上页右图 的生成树实现多播传输 对其中每个分 组所经历的各跳耗费求和 b 设计另一棵生成树 使得求和后的总费用最小 给出树及其总耗费 16 4 16 4 a N1N3N4N5N6L3L4Total 0112113422 b N1N3N4N5N6L3L5Total 0112113220 1 令牌桶方法给出了以最大数据率发送通信量的时间上限 设令牌桶 定义桶的大小为b B 字节 令牌到达率为r B s 而最大输出数据率 为M B s a 试推导最大速率突发的长度S的公式 这就算说 受令牌桶的控制 一个流以最 大输出速率发送时 能够维持多长时间 b 当b 250 KB r 2 MB s 而M 25 MB s时 S的值是多少 17 6 17 6 a 在突发的S秒内 一共传输的通信量为M S字节 在此期间 消 耗掉了桶中原有的b字节的令牌 另外 在S秒内又有r S字节的新令牌 到来 因此有 b r S M S 从而 S b M r b S 250 103 23 106 11 ms 2 GPS排队规则可定义如下 令Si t 为在区间 t 内所发送的 流i的通信量 于是一个GPS服务器的定义满足下式 Si t Sj t i j j 1 2 N 通过证明 可从上式 导出 来证实这个定义 17 7 17 7 对所有的流求和