【正文】 那么在 t=1ms 時(shí)，第一幀發(fā)送完畢； t=271ms時(shí)，第一幀完全到達(dá)接收方； t=272ms，對第一幀的確認(rèn)幀發(fā)送完畢； t=542ms，帶有確認(rèn)的幀完全到達(dá)發(fā)送方。因此一個(gè)發(fā)送周期為 542ms。如果在 542ms 內(nèi)可以發(fā)送 k 個(gè)幀，由于每一個(gè)幀的發(fā)送時(shí)間為 1ms，則信道利用率為 k/542，因此： （ a） k=1，最大信道利用率 =1/542=% （ b） k=7，最大信道利用率 =7/542=% （ c） k=4，最大信道利用率 =4/542=% 30. 答： 使用選擇性重傳滑動(dòng)窗口協(xié)議，序列號長度是 8 位。窗口大小為 128。衛(wèi)星信道端到端的傳輸延遲是 270ms。以 50kb/s 發(fā)送， 4000bit（ 3960+40）長的數(shù)據(jù)幀的發(fā)送時(shí)間是 *4000=80ms。我們用 t=0 表示傳輸開始時(shí)間，那么， t=80ms，第一幀發(fā)送完畢； t=270+80=350ms，第一幀完全到達(dá)接收方； t=350+80=430ms，對第一幀作捎帶 確認(rèn)的反向數(shù)據(jù)幀可能發(fā)送完畢； t=430+270=700ms，帶有確認(rèn)的反向數(shù)據(jù)幀完全到達(dá)發(fā)送方。因此，周期為 700ms，發(fā)送 128 幀時(shí)間 80*128=10240ms，這意味著傳輸管道總是充滿的。每個(gè)幀重傳的概率為 ，對于 3960 個(gè)數(shù)據(jù)位，頭開銷為 40 位，平均重傳的位數(shù)為 4000*=40位，傳送 NAK 的平均位數(shù)為 40*1/100= 位，所以每 3960 個(gè)數(shù)據(jù)位的總開銷為 位。 因此，開銷所占的帶寬比例等于 (3960+)=%。 31. 答： 使用衛(wèi) 星信道端到端的傳輸延遲為 270ms，以 64kb/s 發(fā)送，周期等于 604ms。發(fā)送一幀的時(shí)間為 64ms，我們需要 604/64=9 個(gè)幀才能保持通道不空。 對于窗口值 1，每 604ms 發(fā)送 4096 位，吞吐率為 4096/=。 對于窗口值 7，每 604ms 發(fā)送 4096*7 位，吞吐率為 4096*7/=。 對于窗口值超過 9（包括 1 127），吞吐率達(dá)到最大值，即 64kb/s。 32. 答： 在該電纜中的傳播速度是每秒鐘 200 000km，即每毫秒 200km，因此 100km 的電纜將會(huì)在 內(nèi)填滿。 T1 速率 125 傳送一個(gè) 193 位的幀， 可以傳送 4 個(gè) T1 幀，即 193*4=772bit。 33. Each machine has two key variables: next3frame3to3send and frame3expected, each of which can take on the values 0 or 1. Thus, each machine can be in one of four possible states. A message on the channel contains the sequence number of the frame being sent and the sequence number of the frame being ACKed. Thus, four types of messages exist. The channel may contain 0 or 1 message in either direction. So, the number of states the channel can be in is 1 with zero messages on it, 8 with one message on it, and 16 with two messages on it (one message in each direction). In total there are possible states for the plete system. 34. The firing sequence is 10, 6, 2, 8. It corresponds to acceptance of an even frame, loss of the acknowledgement, timeout by the sender, and regeneration of the acknowledgement by the receiver. 35. The Petri and state graph are as follows: The system modeled is mutual exclusion. B and E are critical sections that may not be active simultaneously, ., state BE is not permitted. Place C represents a semaphore that can be seized by either A or D but not by both together. 36. PPP was clearly designed to be implemented in software, not in hardware as HDLC nearly always is. With a software implementation, working entirely with bytes is much simpler than working with individual bits. In addition, PPP was designed to be used with modems, and modems accept and transmit data in units of 1 byte, not 1 bit. 37. At its smallest, each frame has two flag bytes, one protocol byte, and two checksum bytes, for a total of five overhead bytes per frame. 第 4 章 介質(zhì)訪問子層 1. The formula is the standard formula for Markov queueing given in section , namely, . Here C = 8 and , so sec. For the three arrival rates, we get (a) msec,(b) msec, (c) 1 msec. For case (c) we are operating a queueing system with , which gives the 10 delay. 2. 答： 對于純的 ALOHA，可用的帶寬是 = Kb/ s。 每個(gè)站需要的帶寬為 1000/100=10b/s。而 N=10304/10≈ 1030 所以，最多可以有 1030 個(gè)站，即 N 的最大值為 1030。 3. 答： 對于純的 ALOHA，發(fā)送可以立即開始。對于分隙的 ALOHA，它必須等待下一個(gè)時(shí)隙。這樣，平均會(huì)引入半個(gè)時(shí)隙的延遲。因此，純 ALOHA 的延遲比較小。 4. 每個(gè)終端每 200（ =3600/18）秒做一次請求，總共有 10 000 個(gè)終端，因此，總的負(fù)載是 200 秒做 10000 次請求。平均每秒鐘 50 次請求。每秒鐘 8000 個(gè)時(shí)隙，所以平均每個(gè)時(shí)隙的發(fā)送次數(shù)為 50/8000=1/ 5. 答： （ a）在任一幀時(shí)間內(nèi)生成 k 幀的概率服從泊松分布 生成 0 幀的概率為 eG 對于純的 ALOHA，發(fā)送一幀的沖突危險(xiǎn)區(qū)為兩個(gè)幀時(shí)，在兩幀內(nèi)無其他幀發(fā)送的概 率是eG e – G=e2G 對于分隙的 ALOHA，由于沖突危險(xiǎn)區(qū)減少為原來的一半，任一幀時(shí)內(nèi)無其他幀發(fā)送的概率是 eG 。 現(xiàn)在時(shí)隙長度為 40ms，即每秒 25 個(gè)時(shí)隙，產(chǎn)生 50 次請求，所以每個(gè)時(shí)隙產(chǎn)生兩個(gè)請求， G=2。因此，首次嘗試的成功率是： e2 = 1/ e2 （ b） （ c）嘗試 k 次才能發(fā)送成功的概率（即前 k1 次沖突，第 k 次才成功）為： 那么每幀傳送次數(shù)的數(shù)學(xué)期望為 6. 答： （ a）從泊松定律得到 p0＝ e – G ，因此 G＝ lnp0= ＝ （ b） S＝ G e G ， G ＝ ， e G= S= = （ c）因?yàn)槊慨?dāng) G1 時(shí)，信道總是過載的，因此在這里信道是過載的。 7. 答： 每幀傳送次數(shù)的數(shù)學(xué)期望為： E 個(gè)事件為 E1 個(gè)長度等于 4 個(gè)時(shí)隙的間隔時(shí)間所分隔。因此一個(gè)幀從第一次發(fā)送開始時(shí)間到最后一次嘗試成功的發(fā)送開始時(shí)間之間的長度即延遲是 4(eG ，吞吐率 S= GeG。 對于每一個(gè) G 值，都可以計(jì)算出對應(yīng)的延遲值 D=4(eG ，以及吞吐率值 S=GeG 。 按此方法即可畫出時(shí)延對吞吐率的曲線。 8. (a) The worst case is: all stations want to send and s is the lowest numbered station. Wait time N bit contention period + (N1 d bit for transmission of frames. The total is N+(N1 dbit times. (b) The worst case is: all stations have frames to transmit and s has the lowest virtual station number. Consequently, s will get its turn to transmit after the other N1 stations have transmitted one frame each, and N contention periods of size log2 N each. Wait time is thus(N+1) d+N log2 bits. 9. 答： 在解答這一問題之前，首先要了解什么是 Mok 和 Ward 版本的二進(jìn)制倒計(jì)數(shù)法。在二進(jìn)制倒計(jì)數(shù)法中，每個(gè)想要使用信道的站點(diǎn)首先將其地址以二進(jìn)制位串的形式按照由高到低的順序進(jìn)行廣播，并且假定所有地址的長度相同。為了避免沖突，必須進(jìn)行仲裁：如果某站發(fā)現(xiàn)其地址中原本為 0 的高位被置換為 1，那么它便放棄發(fā)送。對于次高位進(jìn)行同樣的信道競爭操作，直到最后只有一個(gè)站贏得信道為止。一個(gè)站點(diǎn)在贏 得信道競爭后便可發(fā)送一幀，然后另一個(gè)信道競爭周期又將開始。 Mok 和 Ward 提出了二進(jìn)制倒計(jì)數(shù)法的一個(gè)變種。該方法采用了并行接口而不是串行接口：還使用虛擬站號，在每次傳輸之后對站重新編號，從 0開始，已成功傳送的站被排在最后。如果總共有 N 個(gè)站，那么最大的虛擬站號是 N1。 在本題中，當(dāng) 4 站發(fā)送時(shí)，它的號碼變?yōu)?0，而 0、 2 和 3 號站的號碼都增 1， 10 個(gè)站點(diǎn)的虛站號變?yōu)?8， 3， 0， 5， 2， 7， 4， 6， 9， 1當(dāng) 3 站發(fā)送時(shí)，它的號碼變?yōu)?0，而 0、1 和 2 站的號碼都增 1， 10 個(gè)站點(diǎn)的虛站號變?yōu)椋?8， 0， 1， 5， 3， 7， 4， 6， 9， 2 最后，當(dāng) 9 站發(fā)送時(shí)，它變成 0，所有其他站都增 1，結(jié)果是： 9， 1， 2， 6， 4， 8， 5，7， 0， 3。 10. 答： 在自適應(yīng)樹遍歷協(xié)議中，可以把站點(diǎn)組織成二叉樹（見圖）的形式。在一次成功的傳輸之后，在第一個(gè)競爭時(shí)隙中，全部站都可以試圖獲得信道，如果僅其中之一需用信道，則發(fā)送沖突，則第二時(shí)隙內(nèi)只有那些位于節(jié)點(diǎn) B 以下的站（ 0 到 7）可以參加競爭。如其中之一獲得信道，本幀后的時(shí)隙留給站點(diǎn) C 以下的站；如果 B 點(diǎn)下面有兩個(gè)或更多的站希望發(fā)送，在第二時(shí)隙內(nèi)會(huì)發(fā)生沖突，于是第三時(shí)隙內(nèi)由 D 節(jié)點(diǎn)以下各站來競爭信道。 本題中，站 11 和 13 要發(fā)送，需要 13 個(gè)時(shí)隙，每個(gè)時(shí)隙內(nèi)參加競爭的站的列表如下： 第一時(shí)隙： 1 13 第二時(shí)隙： 7 第三時(shí)隙： 3 第四時(shí)隙：空閑 第五時(shí)隙： 3 第六時(shí)隙： 2 第七時(shí)隙： 3 第八時(shí)隙： 7 第九時(shí)隙： 5 第十時(shí)隙： 7 第十一時(shí)隙： 1 13 第十二時(shí)隙： 11 第十三時(shí)隙： 13 11. 答： 2 n個(gè)站點(diǎn)對應(yīng) n+1 級，其中 0 級有 1 個(gè)節(jié)點(diǎn)， 1 級有 2 個(gè)節(jié)點(diǎn)， n 級有 2 n個(gè)節(jié)點(diǎn)。在 i 級的每個(gè)節(jié)點(diǎn)下面所包括的站的個(gè)數(shù)等于總站數(shù)的 1/2 i。本題中所需要的時(shí)隙數(shù)取決于為了到達(dá)準(zhǔn)備好發(fā)送的兩個(gè)站的共同先輩點(diǎn)必須往回走多少級。先計(jì)算這兩個(gè)站具有共同的父節(jié)點(diǎn)的概率 p1。在 2n個(gè)站中，要發(fā)送的兩個(gè)站共享一個(gè)指定的父節(jié)點(diǎn)的概率是 總共 2 n 1個(gè)父節(jié)點(diǎn)，所以， 因?yàn)? 2n 所以 p1≈ 2 n 在共享父節(jié)點(diǎn)的條件下遍歷樹，從第二級開始每一級訪問兩個(gè)節(jié)點(diǎn)，這樣遍歷樹所走過的節(jié)點(diǎn)總數(shù) n1 = 1+ +? +2+2=1=2n，接下來，我們考察兩個(gè)發(fā)送站共享祖父節(jié)點(diǎn)的概率p2和遍歷樹所走過的節(jié)點(diǎn)總數(shù) n2。此時(shí)在每個(gè)父節(jié)點(diǎn)下面僅可能有一個(gè)站發(fā)送。兩個(gè)發(fā)送站共享一個(gè)指定的祖父節(jié)點(diǎn)的概率是 1/ C 22n1。