ME2014第4章习题.doc

ME2014 高级计算机网络 ME2014第4章习题 2014.-034.1【1】考虑一个虚电路网络，如果其VC号是一个16比特的字段，链路能承载的虚电路的最大数量是多少？【2】试比较数据报网络和虚电路网络的转发表：在数据报网络中的基本转发表有两列，这些列中的值的涵义分别是什么？在虚电路网络中的基本转发表有4列，这些列中的值的涵义是什么？解答:（1）在一条链路上VC的最大数量是216=65536。（2）数据报转发表的两列分别是：目的地的地址和出去的接口。虚电路VC转发表的各列分别是：进入的接口、进入的VC号、出去的接口和出去的VC号。4.2，请画出路由器内部结构的示意图，并请简要说明路由器的输出端口的工作原理和引起排队的主要原因。解答: 1当datagrams从fabric到达的速率快于链路的transmission rate时，要求排队缓冲。2输出端口采用调度规则在队列中选出相应的datagrams传输。也可以举例画出争用输出端口的示例图表明:buffering when arrival rate via switch exceeds output line speed;queueing (delay) and loss due to output port buffer overflow。4.3，下图中各结点AJ都是路由器，各条边是链路使用的代价（费用）。请按Dijkstra算法找出结点A到J的最短路径和代价。可简化些解答7 C I4 1 4 1 5源 A D E G J 目的地2 2 8 2 4 1 8 B F H 4 3解答:按Dijkstra算法找出结点A到J的最短路径和代价的基本方法小结如下：1首先在结点集合中列入出发结点（A），在该结点的直接相邻的各个结点的项目列中记入出发结点及相应的边上的费用代价。凡是不直接相邻的结点项目列中应记如无穷大记号。如下例所示：步骤 结点集合 D(B)P(B) D(C)P(C) D(D)P(D) D(E)P(E) D(F)P(F) D(G)P(G) H I J0 A 8,A 4,A 2从刚才记入的一行中选出费用代价最小的对应结点（本题中是结点C，费用4最小），加入到结点集合中。3因为在结点集合中新加入了结点，根据这个新加入的结点（比如现在首先是C），在该新加入的结点的直接相邻的各个结点的项目列下（比如现在C的相邻结点是D、E和I）记入相应边的费用代价，比如有：步骤 结点集合 D(B)P(B) D(C)P(C) D(D)P(D) D(E)P(E) D(F)P(F) D(G)P(G) H I J0 A 8,A 4,A 1 AC 8,A 5,C 8,C 11,C 特别注意：如果原来已有其它路径也到达相应结点时，要计算比较费用，应取最小费用的路径。比如在结点D加入结点集合时，改变了A到B的路径和A到E的路径，如下例：步骤 结点集合 D(B)P(B) D(C)P(C) D(D)P(D) D(E)P(E) D(F)P(F) D(G)P(G) H I J0 A 8,A 4,A 1 AC 8,A 5,C 8,C 11,C 2 ACD 7,D 7,D 11,C 4返回到步骤2继续进行，一直到获得了出发结点到目的地结点的最小费用路径为止。步骤 结点集合 D(B)P(B) D(C)P(C) D(D)P(D) D(E)P(E) D(F)P(F) D(G)P(G) H I J0 A 8,A 4,A 1 AC 8,A 5,C 8,C 11,C 2 ACD 7,D 7,D 11,C 3 ACDB 7,D 12,B 11,C 4 ACDBE 7,D 11,E 9,E 11,C 5 ACDBEG 7,D 11,E 10,G 10,G 6 ACDBEGI 7,D 11,E 10,G 15,IA到J的最短路径是:ACDEGIJ；代价是15。4.4，下图中A、B、C结点是三个路由器，各条边是链路使用的代价（费用）。请按DV算法列出结点A的距离表和转发表。A6 1 B C 3解答：1先根据图分别列出各结点到相邻结点的代价，如下图。每一行是一个距离向量结点A的距离表 结点B的距离表 结点C的距离表 A B C A B C A B C A 0 6 1 A A B B 6 0 3 B C C C 1 3 02A把变化的A行向量发给B,C；B把B行距离向量发向A,C；C把C行向量发向A, B后，这时在A的距离表中需要根据新收到的距离向量信息，用Bellman-Ford方程，重新比较A到目的地B或C的费用。比如从A到B有：DA（B）=MINC（A，B）+DB（B），C（A，C）+DC（B）=MIN（6，1+3）=4；类似地，对于B的距离表来说，B收到了来自A与C的距离向量，也要做类似的费用代价比较：DB（A）=MINC（B，A）+DA（A），C（B，C）+DC（A）=4；结点A的距离表 结点B的距离表 结点C的距离表 A B C A B C A B C A 0 4 1 A 0 6 1 A 0 6 1 B 6 0 3 B 4 0 3 B 6 0 3 C 1 3 0 C 1 3 0 C 1 3 03A再把变化的A行向量发给结点B，C；B把变化的B行向量发向结点A，C后有结点A的距离表结点A的距离表 结点B的距离表 结点C的距离表 A B C A B C A B C A 0 4 1 A 0 4 1 A 0 4 1 B 4 0 3 B 4 0 3 B 4 0 3 C 1 3 0 C 1 3 0 C 1 3 0到完全不变时结束算法。根据A的距离表有：结点A的转发表为 目的地 经由结点 代价B C 4 C C 14.5某链路数据单元MTU的大小是500字节，现在需要向该链路发送一个3000字节的报文段，假定初始的数据报标识号为422，这将会产生出多少个数据报？请描述这些数据报的主要参数特征（长度、偏移量Offset和FLAG等）。解答：因为IP数据报的首部有20字节，在每一数据报分片中数据段大小是50020480字节。因此需要有（300020）480向上取整7个数据报。每个数据报都有标识422，除了最后一个数据报分片外，每个数据报分片的大小是500字节（包括IP首部）；最后一个分片的大小是120字节（包括首部）；（300020）6个分片480100；10020120字节）。7个分片的偏移量Offset分别是：0、60、120、180、240、300和360；（数据部分的480字节8 =60）。头6个分片中的FLAG=1；最后一个分片中的FLAG=0。4.6，填空题【1】CIDR地址192.168.10.0 /20所产生的IP地址范围是_192.168.10.0-192.168.15.255_。【2】按照分类IP网络的标准判别具有IP地址136.123.46.243的主机分别属于_B_类网络。【3】给定某单位一个B类地址135.86.0.0，如果希望使其最大的一个子网能有2000台主机；那么在划分子网时，允许能划分有_31_个子网。【4】已知某访问主机的IP地址是143.170.132.154，子网屏蔽码是255.255.224.0，此主机所属的子网的直接广播地址是_143.170.159.255_（即能广播到此子网内的所有主机）。【5】BGP路由器反复进行三类涉及路由通告的主要活动应是：（1）接收和过滤来自直接连接的相邻结点的路由通告；（2）针对目地地实施路由选择；以及（3）发送路由公告给邻居结点。【6】多播地址空间的大小为_228_。假定现有两个不同的多播组随机地选择一个多播地址，它们选择同一地址的概率是_2(-28) =_3.73x10(-9)_。4.7 考虑如下图所示的网络，假定每个节点初始时都知道其与每个邻居之间的费用，请采用距离向量DV算法，列出节点Z的距离表的表项。 1 U V 5 Z 2 15 2 10 X 1 Y4.8 假定源主机A与目的地主机B之间的数据报的大小被限制为1500字节（包括首部）。如果IP首部是20个字节，要发送一个由400万字节组成的MP3文件需要用多少个数据报？最后一个数据报大小是多少？（提示：数据先应装入首部为20字节的TCP报文段内）。4.9，请按照分类IP网络的标准判别具有以下的IP地址的主机分别属于何类网络？为什么？该类网络内最多允许有多少台主机？（1）198.215.16.27； （2）97.220.186.54； 4.10，给定某单位一个B类地址135.86.0.0，如果希望使其最大的一个子网能有2000台主机；那么在划分子网时，允许能划分有多少个子网？这个B类网络总共能有多少台主机？请你确定此时的子网屏蔽码。还请你指出子网的屏蔽码(也称为掩码)有什么作用?4.11，已知某访问主机的IP地址是143.170.132.154，子网屏蔽码是255.255.224.0，请推算出该主机属于何类网络？该网络中有多少个子网？该台主机的内部子网号与子网内部主机号是什么？请給出此子网的直接广播地址（即能广播到此子网内的所有主机）。4.12考虑一个使用32比特主机地址的数据报网络。假定一台路由器有4条链路，编号为0到3，分组能被转发到链路接口，如下所列： 目的地址的范围 链路接口 1110 0000 0000 0000 0000 0000 0000 0000 到 0 1110 0000 1111 1111 1111 1111 1111 1111 1110 0001 0000 0000 0000 0000 0000 0000 到 1 1110 0001 0000 0000 1111 1111 1111 1111 1110 0001 0000 0001 0000 0000 0000 0000 到 2 1110 0001 1111 1111 1111 1111 1111 1111 其他 3（1）请为其提供一个具有4项的转发表，使用最长前缀匹配，把分组转发到正确的炼路接口。（2）描述该转发表是如何为具有下列目的地址的3个数据报分别确定出适当的链路接口。 11001000 1001 0001 0101 0001 01010101 1110 0001 0000 0000 1100 0011 0011 1100 1110 0001 1000 0000 0001 0001 0111 0111（3）请使用a.b.c.d/x记号法取代二进位字符串记号法重写出该转发表。4.13 考虑使用8比特主机地址的数据报网络。假定一个路由器使用最长前缀匹配并具有下列转发表： 前缀匹配 接口 1 0 11 1 111 2 其他 3对这4个接口的每一个，给出相关的目的地主机地址的范围和在该范围中的地址数量。4.14, 请列出下图执行链路状态算法的详细步骤，算出从A到F的最优路径和代价。其中代价AB-1；AC-2；BD-5，CD-6， B DCE-2，DE-1，DF-2，EF-4。 A 1 5 2 F 2 6 1 4 C 2 E 4.15, 如果根据距离向量算法，推算出结点E的距离表如下表所示，1请你列出结点E的路由转发表。2对该路由转发表中各项的含义作出必要的说明。 经由下列结点到达目的地的代价 DE（） A B D A 3 16 2 目 B 6 5 8 的 C 5 4 6 地 D 10 7 64.16 请分析下图所示的网段，网络中所有的链路费用都是正整数值。其中X只有两个相连的邻居W和Y。W有一条通向目的地U的最低费用路径，费用值是5。Y也有一条通向目的地U的最低费用路径，费用值是6。图中未显示W与Y到目的地U（以及W与Y之间）的完整路径。 W 1 X Y 4（1）请分别给出X对目的地W、Y和U的距离向量。（2）试给出对于C（X，W）或C（X，Y）链路费用的变化，使得执行了距离向量算法后，X将通知其邻居有一条通向U的新最低费用路径。（3）试给出一种C（X，W）或C（X，Y）链路费用的变化，使得执行了距离向量算法后，X将不通知其邻居有一条通向U的新最低费用路径。4.17， 如果主机只有一个接口，为什么主机还是需要有路由表?提示:参见路由表的实现例4.18，假定用户在主机10.0.0.3请求IP地址203.174.104.18的一台WEB服务器80端口,请以此为例,简述NAT的原理,实现要求和主要问题。所用到的路由器的IP地址请自行合理假定。4.19，请举例说明在BGP操作中所涉及到的主要路由通告活动。4.20，请简要描述在BGP中是如何检测在路径中的环路的。广播与组播4.21考虑实现广播的两种基本方法：单播模拟与有路由器协助的网络层广播，并假定使用生成树广播来实现网络层广播。如果有1个发送方和32个接收方，假定发送方通过一