高等计算机网络最终版

1.简述主动网络体系结构及主要的设计目标与对等网络的特点及其主要功能。

(1)主动网络的体系结构：如课本第七页图2.1所示，主动网络最上层是主动应用(ActiveApplication),中间是执行环境(Execution Environment),每个执行环境都可以运行多个主动应用。

执行环境接收到达的主动分组，或者执行其中的程序，或者修改他们的状态，然后再发送一个或者更多的新的分组和程序。

执行环境是体现主动网络可编程特性的最主要的部分。

执行环境运行在节点操作系统(Node OS)之上,节点操作系统为执行环境提供相应的接口完成对系统资源的管理。

主要的设计目标：<1>在设计和开发端到端的服务时尽可能地减少对标准化协议的依赖。

<2>在实现主动服务时提供尽可能多的灵活性。

<3>提供灵活的网络操作与管理功能，尤其是应该提供完善的安全管理能力。

<4>在网络规模和性能方面具有可拓展性。

<5>兼容现有的协议，主要是IP协议。

（2）对等网络特点：[1] 没有服务器。

在对等网络中，没有服务器的概念，所有的对等节点都是客户机，也都是服务器[2] 可扩展性好。

对等网络随着加入节点数量的增长而增长，新节点的加入会给系统增加新的资源，这种扩展性几乎是无限的，理论上限是现有的Internet的规模[3] 完全对称。

在对等网络中，所有的节点都是对称的，运行完全相同的软件，完成完全相同的功能。

主要功能：[1] 实时通信 (RTC) 对于 RTC，对等网络可实现无服务器介入的即时通讯以及实时的游戏对战。

[2] 协作在协作方面，对等网络允许用户共享工作区、文件和体验。

[3] 内容分发对等网络允许对用户分发文本、音频和视频，以及软件产品更新。

[4] 分布式处理对等网络允许分发计算任务，并聚合处理器资源。

[5] 改进的 Internet 技术对等网络还可进一步挖掘 Internet 的潜能，支持新的 Internet 技术2.IP使用的有五种不同字段长度的模式，每种模式都定义了一个地址类，不同的类被设计成包含了不同组织类型的需要，简述有哪些类型、及地址如何分配？一个IP地址由网络号和主机号两个字段组成，根据网络号字段的前几位，可以讲IP地址分为A、B、C、D、E五类地址。

⏹A类地址地址共有四个字节，网络号字段占第一个字节，其中只有7位可用，第一位为类别位，固定为0.可以指派的网络号是126个，网络号为00000000和01111111不可指派。

主机号占三个字节。

第一个可用的网络号为1，最后一个为126⏹B类地址共有四个字节，网络号字段占两个字节，网络号字段的最前面2位为类别位，固定为10.主机号字段占后两个字节。

第一个可用的网络号为128.1，最后一个为191.255⏹C类地址网络号字段占3个字节，网络号字段的前三位为类别位，固定为110，主机号字段占一个字节。

第一个可用的网络号为192.0.1，最后一个为223.255.255⏹D类地址前四位为类别位，固定为1110，此类地址用于多播。

⏹E类地址前四位类别为固定为1111，保留为以后使用。

3. 比较距离向量路由与链路状态路由的相同与不同之处。

相同之处：[1] 距离向量路由与链路状态路由都是自适应的分布式路由算法[2] 距离向量路由与链路状态路由每一个路由器都要不断地和其他一些路由器交换路由信息。

[3] 距离向量路由与链路状态路由算法都需要周期性的发送报文信息来维护路由器的路由表。

[4] 距离向量路由与链路状态路由算法的路由器在收到报文后都要对各自的路由表进行刷新不同之处：[1] 距离向量路由算法每个路由器只向相邻路由器周期性的发送报文，链路状态路由算法则是像所有参与的路由器广播报文。

[2] 距离向量路由算法交换的报文信息很多，而链路状态路由算法广播的路由信息很少，只与该路由器相连的链路数目和状态有关。

[3] 距离向量路由算法的路由器的路径变化信息像波动一样从相邻路由器传播出去，过程非常缓慢，可能出现路由不一致问题；而链路状态路由算法路由信息以广播的形式传播，反应迅速，性能优越。

[4] 距离向量路由算法对路由器和CPU处理能力要求不高，而链路状态路由算法则对路由器和CPU处理能力要求很高。

4．描述距离向量路由器的初始路由表距离向量路由器中包含V-D路由表。

V-D路由表中包含由若干（V,D）序偶组成的序偶表。

在（V,D）序偶中，V代表向量指出路由器可以到达的目标（网络或主机），D代表去往目标V的距离。

D按照路径上的hop数来计数，其他路由器收到（V,D）报文后，根据最短路径原则对各自的路由表进行刷新。

当一个路由器启动时，对其V-D路由表进行初始化，包含所有与本路由器直接相连的网络的路由，距离为0。

然后各路由器周期性的向外广播其V-D路由表的内容，与之相连的路由器Gi受到后，检查各相邻路由器Gj的V-D报文，并作相应修改：（1）Gj中的某个Vm在Gi中没有,则Gi路由表中需要增加相应的表项，且Gi(Vm):=Gj(Vm);Gi(Dm):=Gj(Dm)+1;Gi(nexthop-m):=Gj;（2） Gj中的路由比Gi中的路由短时，即Gj（Dn）<Gi(Dn)-1时，Gi（Dn）：=Gj（Dn）+1；Gi（nexthop-n）:=Gj;（3）Gj中的nexthop是Gi，而Gj中去往该目的的路径发生了变化。

Gj的V-D表不再包含去往该目的的路由，则Gi中应删去该路由。

Gj 的V-D 表去往该目的的距离发生变化，即Gi(Do)≠Gj(Do),则Gi 中的距离需要修改为：Gi （Do ）：=Gj （Do ）+1；V-D 算法的路由刷新发生在相邻路由器之间，所以V-D 报文不一定以广播方式发送出去，比较优化的方法是路由器直接向相邻的路由器发送V-D 报文。

5.使用有权图模型的目的是什么？举例说明使用有权图模型是为了将复杂的计算机网络抽象成易于接受和处理的数据结构，以便对其中的问题进行分析和研究。

例如：网络有交换节点和链路以及主机组成，在研究中往往将其抽象为有权图G(V,E)。

一个有向图G 是由一个非空有限集合V(G)和V(G)中某些元素的有序对集合E(G)构成的二元组，记为G=(V(G),E(G))。

其中V(G)称为图G 的顶点集或节点集，元素v V ∈称为图的一个顶点或节点；E(G)称为图G 的弧集，元素ij e E ∈记为e(v i , v j )或ij e = v i v j, 为V 中元素的有序对，称为图G 的从v i 到v j 的弧。

在有向图G=(V,E)中，令元素e E ∈具有一组有序数列（w 1,w 2,…,w k ）作为e 的属性，则称G 为有权图，其中（w 1,w 2,…,w k ）称为弧e的权。

节点集V 可以表示路由器、交换机、集线器等网络节点设备；E 则为连接V 中两个节点的链路，以及具有的k 个属性（w 1,w 2,…,w k ），这些属性可以是可用带宽、链路传输延迟、接口队列长度，、花费等参数。

6.请解释V-D 算法中出现“慢收敛”问题的原因。

并举例说明如何解决，有哪些方法。

a) b)如图，a)是一个正常的网络拓扑结构，从R1可以直接到达net1,从R2经过R1可以到达net1.正常情况下，R2收到R1的向量报文后，会建立一条路径（net1, R1, 1）。

现在假设从R1到net1的路径因故障而崩溃，但R1仍能正常工作。

R1一旦检测出到net1不可到达，它会立即将原来去往net1的路径废掉（将距离值设为16）。

如果R2赶在R1发送新的更新路由报文之前广播自己的路由更新报文，该报文必然有一条（net1, 1）表项，说明从R2出发经过一个路由器就可以到达net1。

这时R1会根据此表项修改自己的路由表，产生关于net1的新路径（net1, R2, 2）。

于是在R1与R2之间出现了路由环路，如图b)所示。

上述路径环路会通过R1、R2之间不断的路由更新报文交换而解除，但是解除过程是非常缓慢的。

在出现路径环路之后，在下一轮路由广播中，R1将向R2广播（net1,2）表项，R2收到此表项后，将去向net1的路径改为（net1, R1, 3）；然后R2向R1通告（net1, 3）表项，R1将去往net1的路径改为（net1, R2, 4）…….如此下去，直到路径长度变为16。

也就是说，要经过7次来回（至少307⨯秒）路径环路才可以消除。

这就是所谓的慢收敛问题。

解决方法：（1）简单的水平分裂法。

当路由器从某个网络接口发送路由更新报文时，其中不能包含从该接口获取的路径信息。

（2） 带有毒性逆转的水平分裂法。

路由器向某一个接口发送路由更新报文时，包含从该接口获取的路由信息，但是将这些路由项的路径设为无穷。

（3） 触发更新法。

一旦发现某一些路由表项发生变化，就立即广播路由更新报文，而不必等待下一次刷新周期。

7.简述求解Steiner 树问题的近似算法。

R1 R2 R2R1 net1 net1KMB算法是求解Steiner树问题的一种近似算法，它分为以下5个步骤：（1）从最初的网络拓扑G中创建完全距离图H。

完全距离图（complete distance graph）是这样一种图，它包括图G中所有的组成员节点并且每两个节点之间有一条边代表它们之间的最短路径。

（2）寻找图H的最小生成树U。

（3）通过把U中的每条边都替换成图G中的最短路径得到一个连接子图V。

（4）使用最小生成树算法在V中求得最小生成树T。

（5）删除T中所有不在组播组中的叶子节点。

KMB算法的性能保证是2（1-1/|M|）。

8.描述因特网中，一个路由的IP层所执行的路由算法路由选择算法根据是否随着当前网络状况（信息流量和拓扑结构）的变化而动态调整分为两大类：非自适应（静态）、自适应（动态）。

非自适应算法不能根据网络当前实际传输量和拓扑变化来做路由选择，而是按原先设计好的路径传送，路径的设定和修改时静态的。

非自适应路由算法包括扩散式、随机式、固定式等。

自适应算法是根据当前网络流量和拓扑而动态惊醒的，能较好的适应网络中通信量和拓扑的变化。

自适应算法包含集中式、孤立式、分布式、混合式、分层式等。

从宏观上看，Internet采用的是一种分层、分布式的路由算法；从微观上看，在局部范围内可能采用各种不同的路由算法。

再加上谢希仁第五版P128面的那个分组算法的步骤9.什么是网络服务质量（QOS）？为什么说传输层的功能之一是加强互联网QOS？服务质量（Quality of Service）是网络传输业务流时，业务流对网络服务的需求集合，其中业务流是指与特定QoS相关的从源到目的地的分组流。

传输层的主要功能是向用户提供可靠的、透明的端到端的数据传输，以及差错控制和流量控制机制，是完成网络中不同电脑上的用户进程之间可靠的数据传输。