ME2014第4节习题.doc

ME2014 高级计算机网络 ME2014第4章习题 2014.-03 4.1【1】考虑一个虚电路网络，如果其VC号是一个16比特的字段，链路能承载的虚电路的最大数量是多少？【2】试比较数据报网络和虚电路网络的转发表：在数据报网络中的基本转发表有两列，这些列中的值的涵义分别是什么？在虚电路网络中的基本转发表有4列，这些列中的值的涵义是什么？ 解答: （1）在一条链路上VC的最大数量是2^16=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，下图中各结点A~J都是路由器，各条边是链路使用的代价（费用）。请按Dijkstra算法找出结点A到J的最短路径和代价。[可简化些解答] 7 C I 4 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 J 0 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 J 0 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 J 0 A 8,A 4,A ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 AC 8,A 5,C 8,C