计算机网络考试题
计算机网络习题课
上海交通大学 计算机科学与技术 2009-12-9
Shannon定理
• 2.4 如果在一条3kHz的信道上发送一个二进制信号,该信道的信噪比 为20dB,则最大可达的数据传输率为多少? • 解:
根据Shannon定理 C=B*log2(1+S/N) =3*log2(1+100) =19.975 kHz Nyquist定理 C=2*B*log2L ,
Let t = 0 denote the start of transmission. At t = 1 ms, the first frame has been fully transmitted. At t = 271 ms, the first frame has fully arrived. At t = 272 ms, the frame acknowledging the first one has been fully sent. At t = 542 ms, the acknowledgement-bearing frame has fully arrived. Thus, the cycle is 542 msec. A total of k frames are sent in 542 ms, for an efficiency of k/542. Hence
t1=s+x/b+d*k
对于分组交换网络,最后一位在x/b时刻发送出去,最后一个分组需转发 k-1次,每次需p/b秒,所以总延迟为
t2=x/b+(k-1)*p/b+d*k
令t2<t1得
s > (k − 1)p /b.
4
调制解调
• 模拟调制(输入为模拟信号)
调幅 调频 调相
5
调制解调
• 数字调制(输入为数字信号)
3Байду номын сангаас
电路交换VS分组网络
• 2.42请比较一下在一个电路交换网络中和一个(负载较轻的)分组交 换网络中,沿着k跳的路径发送一个x位消息的延迟情况。电路建立的 时间为s秒,每一跳的传播延迟为d秒,分组的大小为p位,数据传输率 为b bps。在什么条件下分组网络的延迟比较短? • 解: 对于电路交换网络,最后一位在s+x/b时刻发送出去,总延迟为
• Iterative
21
RSA
RAS算法 1.找到两个大的素数p和q(典型情况为1024位) 2.计算n=p*q和z=(p-1)*(q-1) 3.选择一个与z互素的数,将它称为d 4.找到e,使其满足e*d=1 mod z 加密: 计算 C=Pe (mod n) 解密: 计算P=Cd (mod n)
15
路由转发规则
• 5.43一台路由器的路由表有以下的(CIDR)表项: 对于下面的每一个IP地址,请问, 如果一个到达分组的目标地址为 该IP地址,那么该路由器怎么办? (a)135.46.63.10 地址/掩码 下一跳 (b)135.46.57.14 135.46.56.0/22 接口0 135.46.60.0/22 接口1 (c)135.46.52.2 192.53.40.0/23 路由器1 (d)192.53.40.7 默认 路由器2 (e)192.53.56.7 解:
x>2*r*d
d a b
13
Chord
• 5.20 考虑图5.24中的Chord圆。假设结点10突然上线,请问它会影响 结点1的指取表吗?如果有影响的话,如何影响? 解: i m
Start=k+2 (mod 2 ) Successor(start[i])
10
14
IP地址分配
• 5.40假定从198.16.0.0开始有大量连续的IP地址可以使用。现在4个组 织A、B、C、D按照次序申请4000、2000、4000和8000个地址。对于 每一个申请,请利用w.x.y.z/s的形式写出所分配的第一个IP地址和最后 一个IP地址,以及掩码。 • 解:
接下来的三次估计值分别为29.6, 29.84, 29.256ms
18
MIME
• 7.16假设你想要发送一个MP3文件给一个朋友,但是你朋友的ISP闲置 进入邮件的大小为1MB,而该MP3文件4MB。通过使用RFC822和MIME ,是否有办法可以处理这种情形? 解:
19
DNS
20
DNS查询
• Recursive
ASK,FSK,PSK,QAM
QAM
6
曼彻斯特编码
• 曼彻斯特编码
包含同步信息 编码效率50%
7
CRC
• 3.15利用本章中介绍的标准CRC方法来传输1001101,生成器的多项式 为x3+1。请给出实际被传输的位串。假设在传输过程中左边第三位变 反了。请证明,这个错误可以在接收端被检测出来. 解:
23
T1骨干线路传输速度1.536Mbps,对于64字节的帧,往返延迟为 2*3000*6+64*8/1.536=36333us=36.3ms 序列号窗口必须保证在RTT时间内不重复,发送每个帧需要0.3ms 序列号必须大于36.3/0.3=121,至少要有7位。
9
信道利用率
• 3.29利用地球同步卫星在一个1Mbps的信道上发送1000位的帧,该信 道离开地球的传输延迟为270ms,确认信息总是被捎带在数据帧上。 头部非常短,并且使用3位序列号。在下面的协议中,最大可获得的信 道利用率是多少? (a)停-等协议 (b)协议5 (c)协议6 • 解:
16
拥塞窗口
• 6.29假设TCP的拥塞窗口被设置为18KB,并且出现了一个超时。如果 接下来的4次传输全部成功的话,则接受窗口将是多大?假设最大数据 段长度为1KB、 解: TCP拥塞窗口策略: (a)当遇到拥塞时,阈值为当 前窗口的一半,窗口设为最大数 据段长度. (b)小于阈值,指数增加 (c)大于阈值,和式增加 阈值设为9KB,接下来的第一次传输,窗口大小为1KB, 第2,3,4次成功传输后,窗口大小为2KB,4KB,8KB。 第5次成功后为9KB,第6次成功后为10KB
22
RSA
• 8.14使用RSA公开密钥密码系统,并且a=1,b=2,以此类推, (a)如果p=7,q=11,请列出5个合法的d值。 (b)如果p=13,q=31,d=7,请找出e。 (c)使用p=5,q=11,d=27,请找到e,并加密“abcdefghij” 解: (a)z=60, d= 7, 11, 13, 17, and 19 (b)z=360, 7e=1 mod 360, e=103 (c)z=40, e=3, 使用C = P3 mod 55进行加密, 用1到10表示“abcdefghij” 加密后为1, 8, 27, 9, 15, 51, 13, 17, 14, 10
11
二进制指数后退算法
• 两个CSMA/CD站都企图传送大的文件(即多帧文件)。在每一帧被送 出之后,它们就使用二进制指数后退算法竞争信道。在第k轮结束竞争 的概率是多少?每个竞争周期的平均轮数是多少? 解:
12
最小包长度
• 链路上有两个结点a和b,链路传输速度为r。结点a在t1=0时刻发送一 个数据包,大小为x,传输延迟为d,则数据包第一位在t2=d到达结点b 。若此时b正好也要发数据,则发生冲突,但是结点a在t3=2*d时刻才 能检测到信道冲突(CSMA),若此时结点a的数据包已发送完,则结 点a不会发现冲突。所以,最小数据包必须满足
(a) k = 1, efficiency = 1/542 = 0.18% (b) k = 7, efficiency = 7/542 = 1.29% (c) k = 4, efficiency = 4/542 = 0.74%
10
ALOHA
• 4.5一大群ALOHA用户每秒钟产生50个请求,包括原始的请求和重传的 请求。时槽单位为40ms。 (a)首次发送成功的概率是多少? (b)恰好k次冲突后成功的概率是多少? (c )所需传送次数的期望值是多少? 解: (a) With G = 2 the Poisson law gives a probability of e −2. (b) (1 − e −G)ke −G = 0.135 × 0.865k . (c) The expected number of transmissions is eG = 7.4.
17
TCP定时器管理
• 6.30如果TCP往返时间RTT当前是30ms,接下来的确认分别在26、32 和24ms之后到达,那么,若使用Jacobson算法,新的RTT估计值是多 少?请使用α=0.9。 • 解:
RTT=α RTT+(1-α)M D= αD+(1- α)|RTT-M| Timeout=RTT+4*D
20dB=10log10S/N
L表示离散信号的种类
2
ADSL
• 2.26一个使用DMT的ADSL系统将3/4可用信道都分配给下行链路了。在 每条信道上它使用QAM-64调制方法。请问下行链路的容量是多少?
回顾: DMT(Discrete MultiTone, 离散多信道调制)
ADSL(Asymmetric Digital Subscriber Line ,非对称数字用户环路) 总共256条子信道,信道0用于POST,信道1-5作为隔离信道,上下行 控制信道各一条,剩下248条用于数据传输。如果3/4用于下行,采样 率为4000baud,使用QAM-64(6bit/baud),所以下行链路的容量为 6*4000*248*3/4=4.464Mbps
生成器为1001,要传输的帧为1001101,在末尾加三个零1001101000。 将1001101000除以1001余100,所以实际传输的串为10011101100。 左边第三位变反10111101100,除以1001余100,所以传输有错。