计算机网络课程作业与参考答案.doc

计算机网络课程作业与参考答案一、计算机网络基本概念1.在OSI的第几层分别处理下面的问题?a. 将待传送的比特流化分成帧b. 决定使用哪一条路径通过子网c. 传输线路上的位流信号同步d. 两端用户间传输文件2.一个系统的协议结构有N层。应用程序产生M字节的报文。网络软件在每层都加上 h 字节长的协议头。那么,网络带宽中有多大比率用于协议头信息的传输?3.有确认服务和无确认服务之间的差别是什么?在下列情况下,请说出哪些可能是有确认服务或无确认服务?哪些两者皆可?哪些两者皆不可?a. 连接建立b. 数据传输c. 连接释放4.参照下图回答问题。图中的每个方框表示一个网络结点。以星号标注的圆圈表示你的终端。 a.你的本地结点是哪一个?b.哪些结点是你的本地结点的相邻结点?c.对你的本地结点来说,哪些结点是远程结点?d.哪些结点是终端结点(END NODES?e.哪些结点是路由结点(ROUTING NODES?f.从结点F到G的最短通路有多少跳段(HOPS?习题解答1.a.第二层(数据链路层将待传输的比特流化分为帧b.第三层(网络层决定使用哪条路径通过子网c.第一层(物理层d.第七层(应用层2.总共有N层,每层加h字节,在每个报文上附加的头字节的总数等于hN,因此,头消耗的有关空间所占的网络带宽的比率为hN/(M+hN。3.在有确认服务中,作为对请求原语的反应,接收方要发出一个明确的响应原语。具体的说,有确认服务包括请求,指示,响应和证实4个原语,而无确认服务则只有请求和指示2个原语。连接服务总是有确认服务,因为远程对等实体必须同意才能建立连接。在所给出的3个例子中,a必须是有确认服务;取决于网络设计者的选择,b和c可以是有确认服务,也可以是无确认服务。4. a. Cb. A和Gc.A,B,D,E,F,G和Hd.D,F,G和He.A,B,C和Ef. 5二、物理层1.一个用于发送二进制信号的3kHz信道,其信噪比为20dB,可以取得的最大数据速率是多少?2.比较在一个电路交换网和在一个(负载轻的分组交换网上将x(bit报文沿k个跳段传输的通路传输的延迟.假定电路建立时间是s,每跨段上的传输延迟为d,分组大小为p(bit,数据传输速率是b(b/s.在什么情况下,分组交换网的延迟更短?(忽略分组头的开销3.在两个DTE之间传送1000bit的数据块.试对下列类型的链路分别计算传播延迟对发射延迟的比率.a. 100m的双绞线和10kb/s的发射速率.b. 10km的同轴电缆和1Mb/s的发射速率.c. 50000km的自由空间(卫星链路和10Mb/s的发射速率。假定在每种类型的电缆内电信号的传播速率时2 108 m/s,在自由空间内信号的传播速率时3 108m/s。参考答案1.20=10lg100仙农极限是3log(1+100=36.66=19.98kb/s奈魁斯特极限是6kb/s显然,瓶颈是奈魁斯特极限,最大数据速率是6kb/s。2.对于电路交换,t=s时电路就会建立起来;t=s+x/b时报文的最后一位发送完毕;t=s+x/b+kd 时报文到达目的地。而对于分组交换,最后一位在t=x/b时发送完毕。为到达最终的目的地,最后1个分组必须被中间的路由器重发k-1次,每次重发花时间p/b(一个分组的所有比特都接收齐了,才能开始重发,因此最后1位在每个中间结点的停滞时间为最后一个分组的发送时间,所以总的延迟为:x/b+(k-1p/b+kd为使分组交换比电路交换快,令:x/b+(k-1p/b+kd (k-1p/b当满足此条件时,分组交换网得延迟更短。3.(aT P = S / V = 100 /2108 = 510-7 sT X = N / R = 1000 / 10103 = 0.1 sa = T P / T X = 510-7 / 0.1 = 510-6(bT P = S / V = 10103 / 2108 = 510-5 sT X = N / R = 1000 / 1106 = 110-3 sa = T P /T X = 510-5 / 110-3 = 510-2(cT P = S / V = 5107 / 3108 = 1.6710-1 sT X = N / R = 1000 / 10106 = 110-4 sa = T P / T X = 1.6710-1 /110-4 = 1.67103三、数据链路层1.为提供比使用单个奇偶位可能得到的更大可靠性,一种检错编码方案使用一个奇偶位检测所有的奇数位,用第二个奇偶位检测所有的偶数位。那么此代码的海明距离时多少?2.信息有效数据m是每个字符用7bit字节编码的ASCII码串“well”,即m长28位,其中,w=1110111,e=1100101,l=1101100,取多项式CRC-12=X做循环冗余检验编码,求该码串的冗余部分r(要求写出主要的计算步骤。3.一个信道的比特率是4kb/s,传输延迟为20ms,那么帧的大小在什么范围内,停-等协议才有至少50%的效率?4.一个3000km长的T1干线被用来传输采取后退n帧错误重传滑动窗口协议的长度都是64字节的数据链路帧。如果传播速度是每公里6微秒,那么序列号应该是多少位?5.假定在一条无错线路上运行采用选择性重传的滑动窗口协议,线路速率是1Mb/s,最大帧长度是1000bit。每一秒产生一个新帧。超时间隔是10ms。如果删除ACK超时机制,将会发生不必要的超时事件。平均每个报文要传送多少次?6.在一个1Mb/s的卫星信道上发送1000bit长的帧。确认总是捎带在数据帧中。帧头很短,使用3位序列号。对以下协议而言,可以取得的最大信道利用率是多少?(a停-等协议(b回退N滑动窗口协议(c选择性重传滑动窗口协议7.使用选择性重传滑动窗口协议,在有重负载的50kb/s的卫星信道上,传输包括40位的头部和3960个数据位的数据帧,ACK帧从未发生过,NAK帧长40位,数据帧的错误率是1%,NAK的传输错误率可忽略不计,序列号长度是8位。试计算花在开销(头和重传上的带宽的比例。8.使用一个64kb/s的无错卫星通道发送512字节的数据帧(在一个方向上,而在另一个方向上返回很短的确认帧。对于窗口大小1,7,15,和127的最大吞吐率是多少?参考答案:1. 由于奇偶位性质,对任何有效码字做一个改变不会产生另一个有效码字。对偶数位做两个改变或对奇数位做两个改变将产生另一个有效码字,因此海明距离是2。2. 用被除数= 1110111 1100101 1101100 1101100 000000000000除数= 1100 0000 01111做二进制除法,得到商= 1011010 1010101 1001000 1010110余数r = 1111 0001 0010,因此该码串的冗余部分r就等于1111 0001 00103. 当发送一帧的时间等于信道的传播延迟的2倍时,信道的利用率是50%。或者说,当发送一帧的时间等于来回路程的传播延迟时,效率将是50%。20ms2 = 40ms现在发送的速率是每秒4000bit,即发送一位需0.25ms40ms0.25ms/bit = 160bit所以当帧大于160位停-等协议才有至少50%的效率。4.为了有效运行,序列空间(实际就是发送窗口的大小必须足够大,以允许发送方在收到第1个确认应答之前可以不断发送。63000 = 18000 us传播时间是18000us,即18ms。在T1速率,即:8248000 = 1.536106b/s (不包括每个物理帧中的1个帧位 发送64字节的帧需花时间:6481.536333 us, 即0.333 ms, 约等于0.3ms。因此,第一个帧从开始发送起,18.3ms后完全到达接收方。确认应答又花了回程18ms 加上很少的(可以忽略发送时间,就可以完全收到。这样,加在一起的总时间为36.3ms。发送方应该有足够的窗口空间,从而能够连续发送36.3ms。36.30.3 = 121也就是说,为充满管道需要121帧,因此序列号应该是7位。5. 发送1位用时间1us,发送1000bit的最长帧花时间1ms。由于超时间隔是10ms,而1s才能产生一个新的数据帧,所以超时是不可避免的。假定A站向B站发送一个帧,正确到达接收方,但较厂时间无反向交通。不久,A站发生超时事件,导致重发已发过的一帧。B站发现收到的帧的序列号错误,因为该序列号小于所期待接收的序列号。因此B站将发送一个NAK,该NAK会携带一个确认号,导致不再重发该帧。结果是,每个帧都被发送两次。6. 对应三种协议的窗口大小值分别是1,7和4。使用卫星信道端到端的传输延迟是270ms。以1Mb/s发送,1000bit长的帧的发送时间是1ms。我们用t = 0表示传输开始时间,那么在t = 1ms时,第一帧发送完毕。t = 271ms,第一帧完全到达接收方。t = 272ms时,对第一个帧的确认帧发送完毕。t = 542ms时带有确认的帧完全到达发送方。因此周期是542ms。如果在542ms内可以发送k个帧,(每个帧发送用1ms 时间,则信道的利用率是k/542,因此:(ak = 1,最大信道利用率= 1/542 = 0.18%(bk = 7,最大信道利用率= 7/542 = 1.29%(ck = 4,最大信道利用率= 4/542 = 0.74%7. 使用选择性重传滑动窗口协议,序列号长度是8位。窗口大小为282 = 128。卫星端到端的传输延迟是270ms。以50kb/s发送,4000bit(3960+40 = 4000长的数据帧的发送时间是0.024000 = 80ms。我们用t = 0表示传输开始时间,那么在t = 80ms时,第一帧发送完毕。t =279+80 = 350ms时,第一帧完全到达接收方。t = 350+80 = 430ms时,对第一帧做捎带确认的反向数据帧可能发送完毕。t = 430+270 = 700ms时,带有确认的反向数据帧完全到达发送方。因此周期是700ms。在700ms内可以发送128帧,80ms128 = 1024ms。显然, 1024ms700ms意味着传输管道总是充满的。每个帧重传的概率是0.01,对于3960个数据位,头位开销40位,平均重传位数是40000.01 = 40位,传送NAK的平均位数是401/100 = 0.40位,所以每3960个数据位的总开销是80.4位。因此开销所占带宽比例等于80.4(3960+80.4 1.99%。8. 使用卫星信道端到端的传输延迟是270ms,以64kb/s发送,512字节长的数据帧占据通道的时间是512864000 = 64ms。我们用t = 0表示传输开始时间,那么在t = 64ms时,第一帧发送完毕。t = 64+270 = 334,第一帧完全到达接收方,并开始返回很短的确认帧(发射时间忽略不记,t =334+270 = 604ms,确认帧完全到达发送方。因此,周期等于604ms,我们需要窗口大小为60464 9个帧才能保持通道的不空。对于窗口值1,每604ms可发送4096位,吞吐率为40960.604 6781b/s。对于窗口值7,吞吐率为67817 = 47637b/s,约为47.5kb/s。对于窗口值超过9帧,(包括15帧和127帧的情况,吞吐率达到完全速率64kb/s。四、介质访问子层 1.一组 N 个站点共享一个 56kb/s 的纯 ALOHA 信道。每个站点平均每 100 秒输出一个 1000bit 的帧，即使前一个帧还没有发送完也依旧进行。N 的最大值是多少？ 2.一个 1km 长的 10Mb/s 的 CSMA/CD 局域网（不是 802.3） ，其传播速度是每微秒 200 米。数据帧的长度是 256bit，其中包括用于帧头部，检验和以及其他开销的 32bit。传输成 功后的第一个时槽被留给接收方，用来捕获信道并发送一个 32bit 的确认帧。假定没有冲突 发生，有效数据速率（不包括开销）是多少？ 3.有一个重负荷的 1km 长的 10Mb/s 的令牌环网，其传输速率是 200 米每微秒，50 个站 空间上均匀绕环分布。数据帧 256 位，其中包括 32 位开销，确认应答捎带在数据帧中，因 此是包括在数据帧内备用的位中，而不占用额外的时间。令牌是 8 位。请问，这个环的有效 数据速率比 CSMA/CD 网是高还是低？ 4.一个用作城域网的光纤令牌环长 200km， 并且以 100Mb/s 速率运行。 在发送一帧之后， 一个站在重新产生令牌之前把该帧从环上清除。在光纤中的信号传播速率示每秒 20 万 km， 且最大帧长 1000 字节。问该环的最大效率示多少？（忽略所有其他的开销来源） 5.一个大学计算机系由 3 个以太子网用两个透明网桥连成一个线形网络。有一天，管理 员有事临时由他人代替， 这个新的管理员注意到网络两端没连， 便用一个新的透明网桥进行 连接组成一个环。请问回发生什么情况？ 参考答案： 1对于纯 ALOHA，可用的带宽是： 0.18456Kb/s=10.304b/s 每个站需要的带宽是： 1000100=10b/s 因此， N=10304101030 所以，最多可以有 1030 个站，即 N 的最大值是 1030。 2电缆的来回路程传播时间是 10us（=10002002） 。一个完整的传输有 4 个阶段： 发送方获取电缆（10us） ； 发送数据帧（25.6us） ； 接收方获取电缆（10us） ； 发送确认帧（3.2us） 。 4 个阶段的时间总和是 48.8us， 在这期间共发送 224 个数据比特。 22448.84.6Mb/s。 因此，有效数据速率约为 4.6Mb/s。 3从获取到令牌的时刻开始计量，发送一个分组需要 0.1256 = 25.6us。此外，必须发 送一个令牌，需要 0.18 = 0.8us 的时间。令牌必须传输 20（=100050）m，经过时间 20200 = 0.1us 才能到下一站。 此后， 下一站又可以再发送数据帧。 因此， 我们在 26.5 =25.6+0.8+0.1） （ us 内发送了 224（=256-32）位的数据，数据速率等于 22426.58.5Mb/s，而 10Mb/s 的 CSMA/CD 在重负荷 50 个站的情况下的有效数据率不超过 3Mb/s。显然，该令牌环强于以 太网的有效带宽。 4 由环长 200km 和传播速率每秒 20 万 km， 可知 1bit 绕环一周的时间是 200 （20104） = 10-3s，即 1ms。发送速率是 100Mb/s，因此发送 1bit 的时间是 0.01us。发送最长帧 1000 字 节需要的时间是 0.0110008 = 80us，即 0.08ms。当一个站抓到了令牌时，它发送数据帧用 0.08ms，然后等待最后 1 位绕环一周用 1ms。当它再放出一个闲令牌时，下一站通过把令牌 中的 1 个令牌位置 1 就可以立即把该令牌转换成一个常规数据帧的开头 3 个字节， 从而又抓 住了令牌，开始发送数据帧。 5将不会发生什么特殊情况。新的桥接器在网上宣告自己的存在，生成树算法为新的 配置计算一个生成树。 新的拓扑会把其中的一个桥接器设置成备用方式， 它将在其他桥接器 失效的情况下投入工作。这种类型的配置以附加的代价提供附加的可靠性，但并非不正常。 它不会引起任何的问题， 因为无论你连接多少个桥接器， 结果总是以生成树的形式运行网络。 五、网络层 1考虑下图所示的子网。使用距离向量路由选择，下列向量刚刚被路由器 C 收到： 来自 B： （5，0，8，12，6，2） 来自 D： （16，12，6，0，9，10） 来自 E： （7，6，3，9，0，4） 路由器 C 测量得到的到达 B，D，和 E 的延时分别等于 6，3 和 5。试问路由器 C 的新的路 由表是什么？请给出所使用的输出线路和所预期的延时。 2一个 6Mb/s 网络上的一台计算机受到令牌桶的交通管制。假定令牌填入速率为 1Mb/s， 开始时漏桶装填的容量是 8Mb。那么，计算机可以用完全速率 6Mb/s 发送多长时间？ 3 假定 IP 的 B 类地址不是使用 16 位而是使用 20 位作为 B 类地址的网络号部分，那么将 会有多少个 B 类网络？ 4 在因特网上的一个 B 类网络具有子网掩码 255.255.240.0。问每个子网中的最大主机数 目是多少？ 参考答案： 1通过 B 给出（11，6，14，18，12，8 ） 通过 D 给出（19，15，9，3，12，13） 通过 E 给出（12，11，8，14，5，9） 取到达每一目的地的最小值（C 除外）得到： （11，6，0，3，5，8） 输出线路是： （B，B，-，D，E，B） 2我们使用公式 S = C/（M-P） ，这里的 S 表示以秒计量的突发时间长度，M 表示 以每秒字节计量的最大输出速率，C 表示以字节计量的桶的容量，P 表示以每秒字节计量的 令牌到达率。 将 C = 81068 =106，M = 61068，P = 11068 代入公式得到： S = 1.6s。 因此，计算机可以用完全速率 6Mb/s 发送 1.6s 的时间。 3除去 2 位作为前缀，将剩下的 18 位表示网络。从概念上讲，网络数目可以有 218 个， 即 262144 个。然而全 0 和全 1 是特别地址，所以只有 262142 个可提供分配。 4对于一个 B 类网络，高端 16 位形成网络号，低端 16 位是子网或主机域。在子网掩码的 低端 16 位中，最高有效 4 位是 1111，因此剩下 12 位（第 3 字节低 4 位和第 4 字节）用于 主机号。因此，存在 4096 个主机地址，但由于然而全 0 和全 1 是特别地址，因此最大主机 数目是 4094 个。 六、传输层 1 数据报的分片和重组由 IP 控制，并且对于 TCP 不可见。这是不是意味着 TCP 不必担心 到达数据的失序问题？ 2一台 TCP 机器在 1Gb/s 的通道上使用 65535 字节的发送窗口，单程延迟时间等于 10ms。 问可以取得的最大吞吐率是多少？线路效率是多少？ 3考虑在一条具有 10ms 来回路程时间的线路上采用慢启动拥塞控制而不发生网络拥塞情 况下的效应。接收窗口 24KB，且最大段长 2KB。那么，需要多长时间才能够发送第一个完 全窗口？ 4假定 TCP 拥塞窗口被置成 18K 字节，并且发生了超时事件。如果接着的 4 个突发量传 输都是成功的，那么该窗口将是多大？假定最大报文段长度是 1KB。 5一个 TCP 链接使用 256kb/s 的链路，其端到端延时为 128ms。经测试发现吞吐量只有 128kb/s。试问窗口大小是多少？忽略 PDU 封装的协议开销以及接收方应答分组的发射时间 （假定应答分组长度很小） 。 参考答案 1尽管到达的每个数据报都是完整的，但可能到达的数据报顺序是错误的，因此，TCP 必 须准备适当地重组报文的各个部分。 210ms 2=20ms 每 20ms 可以发送一个窗口大小的交通量，每秒 50 个窗口（1000 20=50） 。 65535 50=26.214Mb/s 8 26.214Mb/s 1000Mb/s=2.6% 所以，最大吞吐率是 26.214Mb/s，线路效率约为 2.6%。 3慢启动拥塞控制考虑了两个方面的问题，即网络容量和接收方容量，并且分别处理了每 一个问题。为此，每个发送方都维持两个窗口，即接收方准许的窗口和拥塞窗口。发送方可 以发送的字节数是这两个窗口中的最小值。 当建立一条连接的时候， 发送方把拥塞窗口初始化为在该连接上使用的最大报文段 尺寸，然后它发送一个最大报文段。如果这个报文段在超时之前得到确认，发送方就把拥塞 窗口增加到两个最大报文段长，并发送两个报文段。当发出的每个报文段被确认时，拥塞窗 口都要增加一个最大报文段长。因此，当拥塞窗口是 n 个报文