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 章 介质访问子层

1. The formula is the standard formula for Markov queueing given in section namely,

. Here C = 108 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，可用的带宽是×56 Kb/s = Kb/ s。 每个站需要的带宽为1000/100=10b/s。而 N=10304/10≈1030 所以，最多可以有1030 个站，即N 的最大值为1030。

3. 答：对于纯的ALOHA，发送可以立即开始。对于分隙的ALOHA，它必须等待下一个时隙。这样，平均会引入半个时隙的延迟。因此，纯ALOHA 的延迟比较小。

4. 每个终端每200（=3600/18）秒做一次请求，总共有10 000 个终端，因此，总的负载是200 秒做10000 次请求。平均每秒钟50 次请求。每秒钟8000 个时隙，所以平均每个时隙的发送次数为50/8000=1/160。

5. 答：

（a）在任一帧时间内生成k 帧的概率服从泊松分布

生成0 帧的概率为e-G 对于纯的ALOHA，发送一帧的冲突危险区为两个帧时，在两帧内无其他帧发送的概率是e-G×e –G=e-2G

对于分隙的ALOHA，由于冲突危险区减少为原来的一半，任一帧时内无其他帧发送的概率是e-G 。

现在时隙长度为40ms，即每秒25 个时隙，产生50 次请求，所以每个时隙产生两个请求，G=2。因此，首次尝试的成功率是：e-2 = 1/ e2

（b）

（c）尝试k 次才能发送成功的概率（即前k-1 次冲突，第k 次才成功）为：

那么每帧传送次数的数学期望为

6. 答：

（a）从泊松定律得到p0＝e –G ，因此G＝ -lnp0= ＝ （b） S＝G e -G ， G ＝，e -G= S=×=

（c）因为每当G>1 时，信道总是过载的，因此在这里信道是过载的。

7. 答：每帧传送次数的数学期望为：

E 个事件为E-1 个长度等于4 个时隙的间隔时间所分隔。因此一个帧从第一次发送开始时间到最后一次尝试成功的发送开始时间之间的长度即延迟是4(eG-1)，吞吐率S= Ge-G。

对于每一个G 值，都可以计算出对应的延迟值D=4(eG--1)，以及吞吐率值S=Ge-G 。 按此方法即可画出时延对吞吐率的曲线。

8. (a) The worst case is: all stations want to send and s is the lowest numbered station. Wait time N bit contention period + (N-1) d bit for transmission of frames. The total is N+(N-1) 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 N-1 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 版本的二进制倒计数法。在二进制倒计数法中，每个想要使用信道的站点首先将其地址以二进制位串的形式按照由高到低的顺序进行广播，并且假定所有地址的长度相同。为了避免冲突，必须进行仲裁：如果某站发现其地址中原本为0 的高位被置换为1，那么它便放弃发送。对于次高位进行同样的信道竞争操作，直到最后只有一个站赢得信道为止。一个站点在赢得信道竞争后便可发送一帧，然后另一个信道竞争周期又将开始。Mok 和Ward 提出了二进制倒计数法的一个变种。该方法采用了并行接口而不是串行接口：还使用虚拟站号，在每次传输之后对站重新编号，从0开始，已成功传送的站被排在最后。如果总共有N 个站，那么最大的虚拟站号是N-1。 在本题中，当4 站发送时，它的号码变为0，而0、1、2 和3 号站的号码都增1，10 个站点的虚站号变为8，3，0，5，2，7，4，6，9，1当3 站发送时，它的号码变为0，而0、1 和2 站的号码都增1，10 个站点的虚站号变为：8，0，1，5，3，7，4，6，9，2

最后，当9 站发送时，它变成0，所有其他站都增1，结果是：9，1，2，6，4，8，5，7，0，3。

10. 答：在自适应树遍历协议中，可以把站点组织成二叉树（见图）的形式。在一次成功的传输之后，在第一个竞争时隙中，全部站都可以试图获得信道，如果仅其中之一需用信道，则发送冲突，则第二时隙内只有那些位于节点B 以下的站（0 到7）可以参加竞争。如其中之一获得信道，本帧后的时隙留给站点C 以下的站；如果B 点下面有两个或更多的站希望发送，在第二时隙内会发生冲突，于是第三时隙内由D 节点以下各站来竞争信道。

本题中，站2、3、5、7、11 和13 要发送，需要13 个时隙，每个时隙内参加竞争的站的列表如下：

第一时隙：2、3、5、7、11、13 第二时隙：2、3、5、7 第三时隙：2、3 第四时隙：空闲 第五时隙：2、3 第六时隙：2 第七时隙：3 第八时隙：5、7 第九时隙：5 第十时隙：7 第十一时隙：11、13 第十二时隙：11 第十三时隙：13

11. 答： 2 n个站点对应n+1 级，其中0 级有1 个节点，1 级有2 个节点， n 级有2 n个节点。在i 级的每个节点下面所包括的站的个数等于总站数的1/2 i。本题中所需要的时隙数取决于为了到达准备好发送的两个站的共同先辈点必须往回走多少级。先计算这两个站具有共同的父节点的概率p1。在2n个站中，要发送的两个站共享一个指定的父节点的概率是