西电21秋通信网络基础模拟试题五答案

离线作业答案

一、填空题（共10空，每空2分，共20分）
1.  在分组交换网中，网络节点按照一定的规则（路由算法）将________发送到选定的________上的过程称为交换。
答案：输入分组     输出链路
解析：在分组交换网中，在每一个网络节点中采用存储转发的工作方式来将输入的分组发送到选定的输出链路上，这种按照一定的规则（路由算法）将输入分组发送到选定的输出链路上的过程称为交换。

2. 马尔可夫过程的基本特点是________。
答案：无后效性
解析：马尔可夫过程的基本特点是无后效性。即当该过程在t0时刻的状态为已知的条件下，则该过程在t (>t0)所处的状态与该过程在t0时刻之前的状态无关。

3. 如果对于一个图中所有的边，都有（u,v）和（v,u）同时存在，即图中的所有边都是________，则称该图为________。
答案：无向边     无向图
解析：在一个图中，可以用边的两个顶点来表示边。如果边e的两个顶点是u和v，那么e可写成e=(u,v)，这里（u,v）表示u和v的有序对。如果有（u,v）和（v,u）同时存在，它表达了以u，v为端点的一条无向边。如果图中的所有边都是无向边，则称该图为无向图。

4. 从排队论的观点出发，多址信道可以看成一个         的________。
答案：多进单出   排队系统
解析：从排队论的观点出发，多址信道可以看成一个多进单出的排队系统（即该系统有多个输入而仅仅有一个输出。

5. 网络拓扑结构按照几何图形的形状可分为五种类型：       、       、       、星形拓扑和网状拓扑。
答案：总线拓扑    环形拓扑      树形拓扑
解析：网络拓扑结构按照几何图形的形状可分为五种类型：总线拓扑、环形拓扑、树形拓扑、星形拓扑和网状拓扑。

二、简答题（共3小题，每小题20分，共60分）
1. 请写出生成树的定义，并简述生成树的构造过程。
答案：
【1】定义：对于图，包含了图G中所有顶点的树称为生成树。
【2】对于一个给定的图G = (V, E) ，其生成树的构造算法如下：
（1）令n是V中的任意一个顶点，构造子图G’= (V’,E’)，其中，V’={n}, E’=Æ｛空集｝；
（2）如果V’=V 则停止。此时G’= (V’,E’)就是一个生成树。否则进行第3）步；
（3）令(i,j)ÎE，其中iÎV’ , jÎV-V’ ，并采用下列方式更新V和V’ ：V’:=V’È{ j} ， E’:=E’È{(i, j)} ，转到第2）步。
【3】该算法是从仅有一个顶点、0条边的子图开始，以后每执行一次第3）步就增加一个顶点和一条边。这就意味着最终生成的树有|v|个节点，|v|－1条链路。
评分标准：【1】、【3】各4分，【2】中（1）、（2）、（3）各4分。

2. 请简要说明树形分裂算法。
答案：
【1】假设在第k个时隙发生碰撞，碰撞节点的集合为S。所有未介入碰撞的节点进入等待状态。S被随机的分成两个子集，用左集（L）和右集（R）表示。【2】左集（L）先在第k+1时隙传输。如果第k+1时隙中传输成功或空闲，则R在第k+2时隙中传输。【2】如果在第k+1时隙中发生碰撞，则将L再分为左集（LL）和右集（LR），LL在第k+2个时隙总传输。【3】如果第k+2时隙中传输成功或空闲，则LR在第k+3个时隙中传输。【4】以此类推，直至集合S中所有分组传输成功。【5】从碰撞的时隙（第k个时隙）开始，直至S集合中所有的分组成功传输结束的时隙称为一个冲突分解期（CRP）。以上过程可以用下图来加以说明。


评分标准：【1】、【2】、【3】、【4】、【5】各3分，示例图5分。

3. 请简述漏斗式速率控制算法。
答案：
【1】假设有一个漏斗，不管水的流量如何，只要漏斗中有水，漏斗将以恒定的速率向外流水。而且，当漏斗装满水后，如果还向其注水，将导致注入的水从漏斗中溢出。只有当漏斗为空时，输出的速率才为0。【2】这种思想也可以应用到分组传输的过程中。每台主机都可以通过一个类似于漏斗的接口与网络相连，即漏斗是一个容量有限的内部队列。如果分组到达队列时，队列满，则分组将被丢弃。只要队列的长度不为0，分组就会以恒定的速率进入网络。【3】这种策略相当于将用户产生的非平稳的分组流变成了一个平稳的分组流，从而平滑了用户数据分组的突发性，进而大大降低了拥塞的机会。这种算法就被称为漏斗算法。【4】漏斗算法有两种实现方式：一种是针对分组长度固定的情况；另一种是针对可变长度分组的情况。如果分组长度固定，漏斗算法每隔一个固定的时间间隔输出一个分组。当分组的长度可变时，则漏斗算法每隔一个固定的间隔，输出一各固定数目的字节（或比特）。
漏斗算法可以用下图来加以表示：

评分标准：【1】、【2】、【3】、【4】各4分，示例图4分。

三、计算题（共1小题，每小题20分，共20分）
1.一个通信链路的传输速率为50kb/s，设分组到达该链路的过程服从Poisson分布，平均到达率为600分组/分钟，分组长度固定为1000bit。求分组的平均等待时间。
答：
【1】由题意，该链路符合M/D/1排队模型，且=600分组/分钟=10分组/秒，分组的传输时间固定为1/=1000/50000=0.02秒，所以信道利用率=/=0.2，代入下式可求得分组的平均等待时间：
【2】

【3】 代入求得


评分标准：答出【1】给5分，写出公式【2】给5分，正确计算【3】得10分，计算过程正确但是结果错误给5分，只有结果没有计算过程只能给5分。注：最后计算结果也可以写成0.0025。