通信網(wǎng)絡(luò)基礎(chǔ)模擬試題五

通信網(wǎng)絡(luò)基礎(chǔ)模擬試題五一、填空題（共10空，每空2分，共20分）在分組交換網(wǎng)中，網(wǎng)絡(luò)節(jié)點(diǎn)按照一定的規(guī)則（路由算法）將發(fā)送到選定的上的過(guò)程稱為交換。答案：輸入分組 輸出鏈路解析：在分組交換網(wǎng)中，在每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)中采用存儲(chǔ)轉(zhuǎn)發(fā)的工作方式來(lái)將輸入的分組發(fā)送到選定的輸出鏈路上，這種按照一定的規(guī)則（路由算法）將輸入分組發(fā)送到選定的輸出鏈路上的過(guò)程稱為交換。馬爾可夫過(guò)程的基本特點(diǎn)是。答案：無(wú)后效性解析：馬爾可夫過(guò)程的基本特點(diǎn)是無(wú)后效性。即當(dāng)該過(guò)程在t0時(shí)刻的狀態(tài)為已知的條件下，則該過(guò)程在t（＞t0）所處的狀態(tài)與該過(guò)程在t0時(shí)刻之前的狀態(tài)無(wú)關(guān)。如果對(duì)于一個(gè)圖中所有的邊，都有（u,v）和（v,u）同時(shí)存在，即圖中的所有邊都是，則稱該圖為。答案：無(wú)向邊無(wú)向圖解析：在一個(gè)圖中，可以用邊的兩個(gè)頂點(diǎn)來(lái)表示邊。如果邊e的兩個(gè)頂點(diǎn)是u和v，那么e可寫成e=（u,v），這里（u,v）表示u和v的有序?qū)?。如果有（u,v）和（v,u）同時(shí)存在，它表達(dá)了以u(píng)，v為端點(diǎn)的一條無(wú)向邊。如果圖中的所有邊都是無(wú)向邊，則稱該圖為無(wú)向圖。從排隊(duì)論的觀點(diǎn)出發(fā)，多址信道可以看成一個(gè) 的。答案：多進(jìn)單出排隊(duì)系統(tǒng)解析：從排隊(duì)論的觀點(diǎn)出發(fā)，多址信道可以看成一個(gè)多進(jìn)單出的排隊(duì)系統(tǒng)（即該系統(tǒng)有多個(gè)輸入而僅僅有一個(gè)輸出。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)按照幾何圖形的形狀可分為五種類型：、、、星形拓?fù)浜途W(wǎng)狀拓?fù)洹４鸢福嚎偩€拓?fù)?環(huán)形拓?fù)?樹(shù)形拓?fù)浣馕觯壕W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)按照幾何圖形的形狀可分為五種類型：總線拓?fù)?、環(huán)形拓?fù)?、?shù)形拓?fù)?、星形拓?fù)浜途W(wǎng)狀拓?fù)洹６⒑?jiǎn)答題（共3小題，每小題20分，共60分）請(qǐng)寫出生成樹(shù)的定義，并簡(jiǎn)述生成樹(shù)的構(gòu)造過(guò)程。答案：【1】定義：對(duì)于圖，包含了圖G中所有頂點(diǎn)的樹(shù)稱為生成樹(shù)?！?】對(duì)于一個(gè)給定的圖G=（V,E），其生成樹(shù)的構(gòu)造算法如下：（1） 令n是V中的任意一個(gè)頂點(diǎn)，構(gòu)造子圖G'=（V’，E’），其中，V’=｛n｝,E=0｛空集｝;（2） 如果V’=V則停止。此時(shí)G’=（V’，E’）就是一個(gè)生成樹(shù)。否則進(jìn)行第3）步；（3） 令（i,j）cE，其中ieV9 ,jeV-V9 ，并采用下列方式更新V和V’ : V’ ：=V’ u｛j｝，E:=E’u｛（i,j）｝，轉(zhuǎn)到第2）步。【3】該算法是從僅有一個(gè)頂點(diǎn)、0條邊的子圖開(kāi)始，以后每執(zhí)行一次第3）步就增加一個(gè)頂點(diǎn)和一條邊。這就意味著最終生成的樹(shù)有Ivl個(gè)節(jié)點(diǎn)，Ivl—1條鏈路。評(píng)分標(biāo)準(zhǔn)：【1】、【3】各4分，【2】中（1）、（2）、（3）各4分。請(qǐng)簡(jiǎn)要說(shuō)明樹(shù)形分裂算法。答案：【1】假設(shè)在第k個(gè)時(shí)隙發(fā)生碰撞，碰撞節(jié)點(diǎn)的集合為S。所有未介入碰撞的節(jié)點(diǎn)進(jìn)入等待狀態(tài)。S被隨機(jī)的分成兩個(gè)子集，用左集（L）和右集（R）表示?！?】左集（L）先在第k+1時(shí)隙傳輸。如果第k+1時(shí)隙中傳輸成功或空閑，則R在第k+2時(shí)隙中傳輸?！?】如果在第k+1時(shí)隙中發(fā)生碰撞，則將L再分為左集（LL）和右集（LR），LL在第k+2個(gè)時(shí)隙總傳輸?！?】如果第k+2時(shí)隙中傳輸成功或空閑，則LR在第k+3個(gè)時(shí)隙中傳輸?！?】以此類推，直至集合S中所有分組傳輸成功。【5】從碰撞的時(shí)隙（第k個(gè)時(shí)隙）開(kāi)始，直至S集合中所有的分組成功傳輸結(jié)束的時(shí)隙稱為一個(gè)沖突分解期（CRP）。以上過(guò)程可以用下圖來(lái)加以說(shuō)明。SubwiLRRLSubsetlrrrCcllisinnSubsetLLCoHisiQnSubwiLRRLSubsetlrrrCcllisinnSubsetLLCoHisiQnSuccess評(píng)分標(biāo)準(zhǔn)：【1】、【2】、【3】、【4】、【5】各3分，示例圖5分。請(qǐng)簡(jiǎn)述漏斗式速率控制算法。答案：【1】假設(shè)有一個(gè)漏斗，不管水的流量如何，只要漏斗中有水，漏斗將以恒定的速率向外流水。而且，當(dāng)漏斗裝滿水后，如果還向其注水，將導(dǎo)致注入的水從漏斗中溢出。只有當(dāng)漏斗為空時(shí)，輸出的速率才為0?！?】這種思想也可以應(yīng)用到分組傳輸?shù)倪^(guò)程中。每臺(tái)主機(jī)都可以通過(guò)一個(gè)類似于漏斗的接口與網(wǎng)絡(luò)相連，即漏斗是一個(gè)容量有限的內(nèi)部隊(duì)列。如果分組到達(dá)隊(duì)列時(shí)，隊(duì)列滿，則分組將被丟棄。只要隊(duì)列的長(zhǎng)度不為0，分組就會(huì)以恒定的速率進(jìn)入網(wǎng)絡(luò)?！?】這種策略相當(dāng)于將用戶產(chǎn)生的非平穩(wěn)的分組流變成了一個(gè)平穩(wěn)的分組流，從而平滑了用戶數(shù)據(jù)分組的突發(fā)性，進(jìn)而大大降低了擁塞的機(jī)會(huì)。這種算法就被稱為漏斗算法?！?】漏斗算法有兩種實(shí)現(xiàn)方式：一種是針對(duì)分組長(zhǎng)度固定的情況；另一種是針對(duì)可變長(zhǎng)度分組的情況。如果分組長(zhǎng)度固定，漏斗算法每隔一個(gè)固定的時(shí)間間隔輸出一個(gè)分組。當(dāng)分組的長(zhǎng)度可變時(shí)，則漏斗算法每隔一個(gè)固定的間隔，輸出一各固定數(shù)目的字節(jié)（或比特）。評(píng)分標(biāo)準(zhǔn)：【1】、【2】、【3】、【4】各4分，示例圖4分。三、計(jì)算題（共1小題，每小題20分，共20分）1.一個(gè)通信鏈路的傳輸速率為50kb/s，設(shè)分組到達(dá)該鏈路的過(guò)程服從Poisson分布，平均到達(dá)率為600分組/分鐘，分組長(zhǎng)度固定為1000bit。求分組的平均等待時(shí)間。答：【1】由題意，該鏈路符合M/D/1排隊(duì)模型，且人=600分組/分鐘=10分組/秒，分組的傳輸時(shí)間固定為1/^=1000/50000=0.02秒，所以信道利用率p=^/|i=0.2，代入下式可求得分組的平均等待時(shí)間：⑵ W-,p、2日（1-p）

【3】代入求得N=°-°222x