哈尔滨工业大学 深圳 高级计算机网络 2017 习题集

1. A channel has a bit rate of 4 kbps and a propagation delay of 20 msec. For what range of frame sizes does stop-and-wait give an efficiency of at least 50%?

answer: 发送一帧的时间等于信道的传播延迟的2倍,信道的利用率为50%,所以,在帧长满足发送时间大于延迟时间的2倍是,效率将会高于50%。由于4kbps=4000bps故 4000*20*0.001*2=160bit

只有在帧长不小于160bit时,停止等待协议的效率才会至少是50%。

解此题可供参考的公式有两个,下面这两种情况下都可以得到答案:

一个是效率=??+2??其中P是传输一帧所需要的时间,t是端到端传送时延。所以可以由

????+2??

??

>=50%,解出帧N>=160bit;

中第42张中讲到的公式,公式综合考虑了多种因素,信道丢失率????,

二是

帧头的大小n???n??,以及ACK的发送时间n??/R。在不考虑数据帧的处理时间tproc和ACK

发送时间的情况下,我们可以推出帧的最小大小为160bit。答案详情参看上次文档。

作业中得到错误答案有两个(1)N>=80bit得出此答案的同学没有弄清楚停等协议,在停等协议公式1分母下面的2t是往返时间,而不是t。

(2)160kbit,单位换算错误。我可以负责任的告诉你没有哪个网络里面帧能够有十几万比特大小的,以太网里最大帧不过1526字节。

2. Imagine a sliding window protocol using so many bits for sequence numbers that wraparound never occurs. What relations must hold among the four window edges and the window size, which is constant and the same for both the sender and the receiver?

answer: 假设发送者的窗口为(S1,Sn),接受者的窗口为(R1,Rn),窗口大小为W,则 需满足:0<=Sn-S1+1<=W Rn-R1+1=W S1<=R1<=Sn+1 即可。

这题答案很简单,可能有疑问的同学被题目的第一句话给迷惑了。第一句话是滑动窗口协议正常运行必要条件。 第一个式子很好理解,

是已发送但未确认数据包和等待发送数据包的序列范围

内的数据包总个数,如果窗口是从左向右滑动,已发送但未确认数据包序列号在等待发送数据包左侧。很显然这个值是不能大于窗口大小的。

第二个式子,通常在滑动窗口协议里,窗口的大小是在链接初期协商的,在此题中接收窗口等于发送窗口,表示接收方可以缓存发送方的任何帧。接收方可以通过接受的第一个帧的序列号R1来确认自己可以接收的帧序列号范围为W+R1-1。因此在接收方,可接收序列号范围就是窗口的小。序列号范围内的数据包个数是Ru-Rl+1而不是Ru-Rl。不代表接收方缓存是满的。

第三个式子,Rl就是已发送但未确认数据包和等待发送数据包的边界,由于接收方缓存里只有那些已接受但未确认数据包,所以Rl>=Sl但一定有Rl<=Su+1,因为接收者缓存里不可能有发送者等待队列之外的数据。

3. A large population of ALOHA users manages to generate 50 requests/sec, including both originals and retransmissions. Time is slotted in units of 40 msec. (a) What is the chance of success on the first attempt?

(b) What is the probability of exactly k collisions and then a success? (c) What is the expected number of transmission attempts needed?

answers: (a) according to the definition, throughput of Slotted ALOHA, a frame will not suffer a collosion if no other frames are sent at the beginning of the same frame time, the probability of no other traffic during the same slot is P=e^-G; 50*40*0.001=2, so, G=2 P=e^-2=1/e^2 So, the chance of success on the first attempt is 1/e^2. (b) that is to say, a transmission requiring exactly K+1 attempts. So, the probability is P=(e^-G)*(1-e^-G)^K, G=2, So, P=(1-e^2)^K(e^-2)=0.135*(1-0.135)^K=0.135*0.865^K (c)according to the definition of throughput of slotted ALOHA, the expected number of transmissions E= e^G, G=2, So, E=e^2

参考《计算机网络(第五版)》美·特南鲍姆204~205页内容,解题关键是先求出G(单位时隙里生成的帧数),剩下的都是套公式。

3. What’s the remainder obtained by dividing x7+x5+1 by the generator polynomial x3+1? Solution:

The polynomial x7+x5+1 corresponds to 10100001,the generator polynomial is 1001.So the remainder is 1010000101 = 111.

1.A group of N stations share a 56-kbps pureALOHA channel. Eachstation outputs a 1000-bit frame on an average of once every 100 sec,even if the previous one has not yet been sent(e.g., the stations canbuffer outgoing frames). What“is the maximum value of N?

答:对于100%的ALOHA,可用的带宽是0.184×56 Kb/s?=10.304?Kb/ s。每个站需要的带宽为1000/100=10b/s。而N=10304/10≈1030 所以,最多可以有1030 个站,即N 的最大值为1030。

3.Measurements of a slotted ALOHA channel with an infinite number ofusers show that 10 percent of the slots are idle.

(a) What is the channel load, G? (b) What is the throughput?

(c) Is the channel underloaded or overloaded?

答:(a)从泊松定律得到p0=e^-G ,因此G=-lnp0= -ln0.1=2.3 (b)由题知S=G *e -G , G=2.3,e^ -G=0.1 S=2.3×0.1=0.23

(c)因为每当G>1 时,信道总是过载的,因此在这里信道是过载的。

4.What is the baud rate of the standard 10 Mbps Ethernet?

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4