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

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

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