1、第 1 章 通信網絡概論及數學基礎1.1 通信網絡有哪些基本要素組成？試舉例列出五種常用的通信網絡。1.2 常用的通信鏈路有哪些？其主要特征是什么？1.3 試簡述分組交換網的要點。1.4 什么叫做虛電路？它與傳統電話交換網中的物理鏈路有何差異？1.5 ATM 信元與分組有何差別？ ATM網絡是如何支持不同種類業務的？1.6 分層的基本概念是什么？什么是對等層？1.7 試述 OSI七層模型和 TCP/IP 協議體系的區別和聯系。1.8 一個典型的通信網絡可由哪些物理子網構成？路由器在該網絡中的作用 是什么？1.9 通信網絡要研究的基本理論問題有哪些？1.10 設隨機過程 X(t)定義為： X(t

2、) 2cos(2 t Y)，其中 Y是離散隨機變量，11PY 0 , P Y 且 2 2 2 。試求該過程在 t 1時的均值，和 t1 0, t2 1時的自相關函數值。1.11 設隨機過程 X (t)是一個隨機相位信號，即 X(t) Acos(wct ) ，式中 Af( )和 wc 為常量， 是一個均勻分布的隨機變量，其概率密度函數為試求 X(t) 的均值函數和自相關函數。并討論其平穩性和各態歷經性。1.12 試求 Poisson 過程的均值函數，方差函數和相關函數。1.13 設到達某商店的顧客組成強度為 的 Poisson 流，每個顧客購買商 品的概率為 p，各顧客是否購買商品與其它顧客無關

3、，分別用 Y(t),t 0 和Z（t）,t 0 表示購買商品顧客和未購買商品顧客的顧客流過程，請證明他們分別 是強度為 p 和 （1 p） 的 Poisson 流1.14 設某辦公室來訪的顧客數 N（t） 組成 Poisson 流，平均每小時到訪的 顧客數為 3人，求：（ 1）一上午（ 8到 12點）沒有顧客來訪的概率；（ 2）下 午（2 點到 6 點）第一個顧客到達的時間分布。1.15 設有三個黑球和三個白球，把這六個球任意分給甲乙兩人，并把甲圖 1-25 習題 1-16 圖擁有的白球數定義為該過程的狀態，則有 四種狀態 0，1，2，3。現每次從甲乙雙方 各取一球，然后相互交換。經過 n 次

4、交換 后過程的狀態記為 X n，試問該過程是否是 馬氏鏈？如是，試計算其一步轉移概率矩 陣，并畫出其狀態轉移圖。1.16 分別利用 Prim-Dijkstra 算法 和 Kruskal 算法求解圖 1-25 中的最小重量 生成樹。第 2 章 端到端的傳輸協議2.1 常用的組幀方式有哪幾種？哪一種方式的傳輸開銷最小？2.2 接收機收到了如下一個采用十六進制表示的字符串， C0 C0 10 36 87 DB DC DB DC DC DD DB DD C0 7C 8D DC DB DC ，C0試根據 SLIP 幀格式恢復出接收 的幀。2.3 針對輸入序列 0110111110011111101011

5、1111111101111010應用 2.1.2 節的比特插入技術，給出相應的輸出結果。如果接收到的序列為：01111110111110110011111001111101111101100011111101011111試0,移去插入 的比特并指出 Flag 的位置。2.4 假定 2.1.2 節幀中插“ 0”的規則修改為： 僅在原始數據中出現 015 時插 入一個 0。試詳細描述這種變化后接收端去 0 的規則，并說明該規則是如何去掉 下列比特串中的 0：0110111110111111011111010111111。0 (如果設計的規則正 確，在該串中應去掉 2個 0并且僅有一個 Flag 。

6、)2.5 設有一個奇偶校驗碼由 3個數據比特和 4個校驗比特組成。 假定 3個碼 字分別為 1001011, 0101101 和 0011110。試求產生該碼的運算規則，并寫出所 有 8 個碼字。并求出該碼的最小距離 (兩個相同長度的碼字之間的距離定義為兩 個碼字比特取值不同的位置數)。D 4S(D)2.6 令g(D) D4 D2 D 1， S(D) D3 D 1，求 g(D) 的余數。k1C(D)SiC(i) (D);i02.7 對于一個給定的 L 階生成多項式 g(D) 和一個給定的數據比特長度 K，假 定輸入序列除第 i 位為 1 以外，全部為 0，即 S(D)=Di ，0 i K 1,

7、 其對應的 CRC 結果為： C(i)(D) CL(i)1DL 1C1(i)D C0(i),試證明：1)對于一個任意的數據多項式 S( D) ，其 CRC多項式K1上式說L 1 L 2CjSiC(ji);0 j L(2) 令C(D) CL 1D L 1 CL 2DL 2C1D C0,則i 0明每一個 C j是一個奇偶校驗比特。也就是說， CRC校驗碼也是一種奇偶校驗碼2.8 假定改變停等式 ARQ的傳輸策略，在連續發送的分組中，不使用序號，j分組CRC而是改為；發送的 DLC發送給定分組已被重傳的次數，即幀格式這為，里 j 為重傳的次數 (j =0為分組第一次發送 )，接收 DLC對每一個接收

8、的幀采用 ACK或 NAK予以應答(應答中沒有請求的序號) 。試通過舉 例證明無論接收端 DLC采用什么規則來接收分組，該傳輸策略都不能正確工作。2.9 試證明停等式 ARQ的序號可采用模 2 表示。2.10 在停等式 ARQ中，設重發分組之間的間隔為 Tr（包括分組傳輸時間、 傳 播時延、等待應答時間和處理時延等），分組正確接收的概率為 ，試證明最大 max的可傳送的分組到達率Tr 。2.11 在相同的幀長和相同的幀錯誤的情況，重畫圖 2-11（a） 和（c） ，考察分 組從節點 B到A的傳輸情況，即說明 SN和節點 B的窗口，以及 RN和輸出給 A 的分組。2.12 設從節點 A 向節點

9、B 傳輸分組，令 是節點 B每成功接收一個分組， A 到 B所發送幀的平均次數。 令 p是到達 B的幀出錯的概率 （連續的幀相互獨立） 。 假定 A總是忙于發送幀，窗口長度 n 足夠地大，在沒有反饋的情況下， A絕不會 返回重發，但在聽到一個等待應答的幀有錯時， A 總會在下一幀返回重發。令 是一個給定幀從其傳輸開始到接收到與該幀對應的反饋幀 （包括反饋幀到達時 A 正在傳輸的那一幀）之間從 A到 B平均發送的幀數。證明 滿足 1 p（ ）。 定義效率 為 1/ ，求出 與 、 p 的函數。64kbps，單向傳播2.13 一條雙向對稱無誤碼的傳輸鏈路，鏈路傳輸速率為 時延為 15ms。設數據幀

10、長為 3200bits ，確認幀長度為 128bits ，采用停等式 ARQ 協議，忽略處理時延。問 1）在僅有單向數據傳輸業務的情況下，在 820 秒內最 多可以傳輸多少個數據幀？ 2）如果雙向都有業務傳輸，且應答幀的傳輸只能跟在返向數據幀的尾部（格式為：數據幀應答幀），問在 820 秒內每一個方向最多可以傳輸多少個數據幀？ 3）若采用返回 n-ARQ且 n=3，重新計算 1） 和 2）的 結果。2.14 在 2.2.2 節介紹的四種 ARQ方式中，鏈路利用率與哪些參數有關？哪 一種方式的鏈路利用率最高，請定量說明。2.15 試畫出 Kopt與 E（M），V及j 的關系曲線，并對該結果進行討

11、論。2.16 HDLC 中是如何保證數據透明傳輸的？ HDLC有幾種工作模式？2.17 試解釋例 2.4 中圖 2-19 的詳細工作過程2.18 （1）假定采用 2.3.2 節的平衡初始化和拆除連接協議，節點 A和 B都 認為它們之間的鏈路處于 UP狀態。假定在時刻 t 節點 A 開始拆除連接（即發送 DISC）。試證：在采用與 2.2.2 節相同的假定條件下，每個節點最終都會認為鏈 路處于 DOWN狀態。（2）假定節點 A 認為鏈路處于 UP狀態，節點 B正在進行鏈路初始化，但還 沒有從 A收到ACKI。若 A開始拆除連接，試證明 B最終認為鏈路為 UP狀態。然 后 B開始拆除連接，在此以后

12、， A和 B最終都會認為鏈路為 DOW狀N 態。2.19 （ 1）在主從式初始化協議中，假定一個從節點故障恢復的節點開始處 于 UP狀態，通過先發 DISC 再發 INIT 來進行初始化，舉出一個類似于圖 2-24 中不正確工作的例子。（2）現假定一個任意的協議用于初始化。已知從故障中恢復的節點A 將發送一條消息 X，節點 B 從故障中恢復并收到消息 X 后將發送消息 Y，在這些條件 下當節點 A收到 Y 時，節點 A將能被正確初始化。 試構造一個故障和時延序列說 明該協議不能正常工作。2.20 一個通信子網內部采用虛電路方式， 沿虛電路共有 n 個節點交換機，在 交換機中為每一個方向設有一個

13、緩沖區， 可存放一個分組。 在交換機之間采用停 止等待協議， 并采用以下的措施進行擁塞控制。 節點交換機在收到分組后再發回 確認，但條件是；（ 1）接收端已成功地收到該分組；（ 2）有空閑的緩沖區。設 發送一個分組需 T 秒（數據或確認），傳輸的差錯可忽略不計，用戶（ DTE）和 節點交換機（ DCE）之間的數據傳輸時延也可忽略不計。試問：分組交付給目的 用戶（ DTE）的速率最快是多少？2.21 有AB和BC兩條鏈路。A經過 B向 C發送數據。B收到 A發來的數據時， 可以先向 C轉發再向 A發確認，也可以把這順序反過來。也就是說， B 要做的三 件事的順序是；收數據轉發發確認，或：收數據發

14、確認轉發。現假定 B 在做完第二件事后處理機即現故障， 內存中所存信息全部丟失， 但很快又恢復了 工作。試證明：只有采用端到端發確認信息的方法（即從 C向 A 發確認信息）， 才能保證在任何情況下數據都能從 A經 B正確無誤地交付到 C。2.22 兩個用戶（ U1和 U2）通過他們的主機 H（ DTE）同 X.25 網建立了虛電路 連接。圖 2-35 的時序圖表示分組到達網絡層的過程。這里 Pij 為從第 i 個用戶i =1,2 ）來的第 j 個分組。網絡層將虛信道號 VC與發送序號 P（S） （即網絡層的 SN)插入到網絡層分組頭中。假設 U1的 VC為 5，U2 的 VC為 17。而后所有

15、分 組采用多路復用方式發往數據鏈路層。數據鏈路層按順序將發送序號N(S) (即鏈路層的 SN)插入到幀頭的其他參數中。畫出分組在主機 H與網絡間的接口上 傳送的時序圖。按順序說明每一分組的 N(S)、VC、P(S) 的值。圖 2-35 分組到達網絡層的時序圖2.23 一個 TCP連接使用 256kb/s 鏈路，其端到端時延為 128ms。經測試， 發 現吞吐量只有 120kb/s 。試問窗口是多少？2.24 設 TCP的擁塞窗口長度置為 18kB。網絡發生了超時， TCP使用慢啟動、 加速遞減和擁塞避免。設報文段的最大長度為 1kB，試問：擁塞窗口從最小值經 過 6 次變化后是多少？2.25

16、網絡層差錯控制與數據鏈路層差錯控制的主要差別是什么？2.26 ARQ 協議用于差錯控制和流量控制有何異同？第 3 章 網絡的時延分析3.1 設顧客到達一個快餐店的速率為每分鐘 5 人，顧客等待他們需要的食品 的平均時間為 5 分鐘，顧客在店內用餐的概率為 0.5 ，帶走的概率為 0.5 。 一次用餐的平均時間為 20 分鐘。問快餐店內的平均顧客數是多少？3.2 設有兩個通信節點 1和2向另一個節點 3發送文件。文件從 1和 2到 3 所需的平均傳輸時間分別為 R1和R2個單位時間。節點 3處理節點 i (i =1，2)的文件所需的平均時間為 Pi個單位時間，在處理結束后再向節點 1或 2請求另

17、一個文件。（具體選擇節點的規則未定。）如果 i 是節點 i 以每單位時間內發送的文件數表示的通過率，試求所有可行的通過率對（1, 2 ）的區間？3.3 一個健忘的教授將與兩個學生的會談的時間安排在相同時間， 設會談的 區間是獨立的，服從均值為 30 分鐘的指數分布。第一個學生準時到達，第 二個學生晚到 5 分鐘，問第一個學生到達時刻到第二個學生離開的平均間隔 是多少？3.4 一個通信鏈路分成兩個相同的信道，每一個信道服務一個分組流，所有 分組具有相等的傳輸時間 T 和相等的到達間隔 R（R>T）。假如改變信道的使 用方法，將兩個信道合并成一個信道，將兩個業務流統計復接到一起，每個 分組的

18、傳輸時間為 T/2 。試證明一個分組在系統內的平均時間將會從 T下降 到（T/2 3 T/4 ），分組在隊列中等待的方差將會從 0變為T 16？3.5 一個通鏈路的傳輸速率為 50kb/s ，用來服務 10個 Session ，每個 Session 產生的 Poisson 業務流的速率為 150分組/ 分鐘，分組長度服從指數分布， 其均值為 1000bit 。（1）當該鏈路按照下列方式為 Session 服務時，對于每一個 Session ， 求在隊列中的平均分組數，在系統中的平均分組數，分組的平均延時。 10 個相等容量的時分復用信道； 統計復用。（2）在下列情況下重做（ 1）： 5 個 S

19、ession 發送的速率為 250分組/分鐘； 另 5 個 Session 發送的速率為 50 分組/ 分鐘。3.6 考察一個到達率及服務速率與服務系統狀態相關的類似于 M/M/1 的系 統。設系統中的顧客數為 n，除了到達率為 n ，服務速率為 n 外與 M/M/1完全相同，試證明 Pn 1 （ 0. n）p0，式中 k k k 1 及k0p0 1 （ 0. k ） 13.7 考察一個離散型 M/M/1 系統，該系統的到達間隔和服務時間均為整數值， 即顧客在整數時刻到達或離開。令 是一個到達發生在任何時刻 k 的概率， 并假定每次最多僅有一個到達。 一個顧客在 k+1 時刻被服務結束的概率為

20、 試求以 和 表示的系統狀態（顧客數）概率分布 pn3.8 設有一個 M/M/ 隊列，其服務員分別標有 1，2，。現增加一個限制， 即一個顧客到達時將選擇一個空閑的，且具有最小編號的服務員。試求每一 個服務員是忙的時間比例。如果服務員數目是有限的，答案有無變化？3.9 假定在 M/M/2 隊列中，兩個服務員具有不同的服務速率，試求系統的穩 態分布。（當系統為空時，到達的顧客分配到服務速率較快的服務員。）3.10 設有 M個顧客， m個服務臺，緩沖器的容量為 K的排隊系統， 到達速率 和服務速率為：（M k）0kK 1k 0其它k0kmkk mkm假設到達過程為 Poisson 過程，服務時間為

21、指數分布， 且 M K=m。畫出狀態轉換 圖。求該排隊系統中顧客數的穩態分布，平均時延和阻塞概率。3.11 M/M/m/m排隊是在電路交換應用中產生的。 這里設呼叫到達過程為 Poisson 過程，它由最大值為 m個指數分布的服務臺服務。 當系統中有 m個呼叫時，第（m+1） 個呼叫被阻塞。 設系統的狀態 l 表示當前正在進行的呼叫數。 到達和服務速率為lml0 l m其中， l=l ，l =1，2，, m，求系統中呼叫個數的穩態分布，阻塞概率 Bl和呼 叫等待時間的期望值 E（W） 。3.12 設一條傳輸鏈路有 m個等容量的電路組成，有兩種類型的 Session ，其 Poisson 到達率

22、分別為 1和 2 。當所有電路都忙時，一個到達的 Session 將被拒 絕而離開系統， 否則一個到達的 Session 被分配到任一個空閑的電路。 兩種類型 的服務時間(保持時間)服從指數分布，其均值分別為 1 1和1 2 ，求該系統的穩 態阻塞概率。3.13 試利用平均剩余服務時間的概念證明 M/D/1 系統的等待時間為W2 1 。3.14 在 M/G/1 系統中，試證明：P系統空閑 =1- X1 忙區間之間的平均長度 =X忙區間的平均長度 =1 X1 在一個忙區間內服務的平均顧客數 =1 X3.15 考察一個有單一休假期的 M/G/1 系統，即在每個忙區間后跟有一個休假期。 一旦這個休假

23、期結束， 到達的顧客進入空閑系統立即得到服務。 假定休假的區間 是獨立同分布的且與用戶的到達間隔和服務時間獨立。 試證明隊列中的平均等待 時間為2X V 2 W=2(1 ) 2I這里 I 是空閑周期的平均長度。試說明如何計算 I 。3.16 考察一個服務受限的系統，對于閘門型和部分閘門型，試證明：(1)在一個預約區間內一個分組到達的穩態概率為 1- 。( 2)一個預約期間后跟一個空閑數據區間的穩態概率為 (1 V) (1 )圖 3-23 習題 3.17 中的網絡3.17 有一個網絡如圖 3 23 所示，有四個 Session ACE，ADE， BCEF和 BDEF，它們發送的 Poisson

24、業務的速率分別為 100，200，500，和 600 分組/ 分鐘，分組的長度是均值為 1000比特的指數分布，所有傳 輸鏈路的容量均為 50kb/s 。每 條鏈路的傳輸時延為 2ms，利用 Kleinrock 的獨立性近似。 試求 解系統中的平均分組數， 分組的 平均時延（不區分 Session ）， 以及每個 Session 中分組的平均時延圖 3-24 習題 3.18 的圖3.18 設有一個 CPU連接到 m 個 I/O 設備，如圖 3 24 所示，任務進入系統是服從 速率為 的 Poisson 過程， 通過 CPU后分別以概率 pi ， i =1，m分送到第 i 個 I/O 設備，而以

25、概率 p0 離開系 統。任務在 CPU和第 i 個 I/O 設備內的服務時間分別服從 均值為1 0和1 i 的指數分 布。假定在所有隊列中所有 任務的服務時間是相互獨立的， 試求系統的穩態狀態概率分布， 并構造一個具有 相同分布的“等效”的 m+1 個隊列級聯的系統。第 4 章 多址技術4.1 請討論固定多址接入協議的優缺點是什么？4.2 在 ALOHA協議中，為什么會出現穩定平衡點和不穩定的平衡點，重傳概率對 系統的性能有何影響？4.3 設信道數據速率為 9600bit/s ，分組長度為 804bit 。計算當 G 0.75 時純 ALOHA 系統負荷為多少？4.4 n 個節點共享一個 96

26、00bit/s 的信道，每個節點以每 100s 產生一個 1000bit 分組的平均速率發送數據分組。試求在純 ALOHA系統和時隙 ALOHA系統中最 大可容許的系統用戶數 N 的值？4.5 什么叫穩定的多址接入協議？使用偽貝葉斯算法的時隙ALOHA協議是不是穩定的多址接入協議？如果是，其穩定的最大通過率是多少？4.6 CSMA協議的基本原理是什么？與 ALOHA系統相比，為什么 CSMA系統有可能 獲得更高的系統吞吐率？4.7 CSMA系統主要是在什么問題的處理決策上去區分三種不同類型的CSMA協議？說明它們各自的關鍵技術特點。4.8 CSMA方法有什么應用環境限制？在衛星信道上能采用 C

27、SMA接入方法嗎？為 什么？4.9 假設有以下兩個 CSMA/CD網：網絡A是LA（N局域網），傳送速率為 5Mbit/s ，電纜長1km，分組長度 1000bit ；網絡B是MAN（城域網），電纜長 50km，分組長度 1000bit 。那么，網絡 B 需要多大的傳送速率才能達到與網絡 A相同的吞吐率？4.10 K 個節點共享 10Mbit/s 的總線電纜，用CSMA/CD作為訪問方案 （即以太網 LAN）。總線長 500m，分組長 L 比特，假設網絡上的 K 個節點總 有業務準備傳送（重負荷情況）。 P 是競爭時隙 中一個節點發送分組的概率。令 K 10 ，傳播速 度是 3 108 m/s

28、。求競爭周期的平均時隙數、競爭 周期的平均持續時間及以下兩種情況的信道利用 率。(1) L 100bit圖 4-26 習題 4.11 圖（2） L 1000bit 。4.11 出圖 4-26 所示網絡中的無沖突矢量集合。第 5 章 路由算法5.1 一個理想的路由算法應具有哪些特點？為什么實際的路由算法總是不如 理想的？5.2 路由算法有哪些類型？所謂“確定型”和“自適應型”的分類， 是在什么 意義上而言的。5.3 試述廣域網的路由與互連網的路由的區別和聯系？5.4 分別使用Bellman-Ford 和 Dijkstra 算 法求解圖 5-21 中從每一個節 點到達節點 1 的最短路由。5.5 在距離矢量法中為什么 會出現“計數至無窮”的 現象？如何解決？5.6 鏈路狀態法的基本步驟 是什么？它與距離矢量法 相比有何優點？5.7 一個廣域網有 50 個節點，每個節點和其它 3 個節點相連。若采用距離矢量 算法，每秒鐘交換路由信息 2 次，而節點間的時延用 8bit 編碼。試問：為了 實現分布式路由算法，每條