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 4.1.1, namely,
. Here C = 108 and, so sec. For the three arrival
rates, we get (a) 0.1 msec,(b) 0.11 msec, (c) 1 msec. For case (c) we are operating a queueing system with , which gives the 10×delay.
2. 答：对于纯的ALOHA，可用的带宽是0.184×56 Kb/s =10.304 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 对于纯的ALOHA，发送一帧的冲突危险区为两个帧时，在两帧内无其他帧发送的概率是e-G×e –G=e-2G
对于分隙的ALOHA，由于冲突危险区减少为原来的一半，任一帧时内无其他帧发送的概率是e-G 。
现在时隙长度为40ms，即每秒25 个时隙，产生50 次请求，所以每个时隙产生两个请求，
-22
G=2。因此，首次尝试的成功率是：e = 1/ e
（b）
-G
（c）尝试k 次才能发送成功的概率（即前k-1 次冲突，第k 次才成功）为：
那么每帧传送次数的数学期望为
6. 答：
（a）从泊松定律得到p0＝e ，因此G＝ -lnp0= -ln0.1＝2.3 （b） S＝G e ， G ＝2.3，e =0.1 S=2.3×0.1=0.23
（c）因为每当G>1 时，信道总是过载的，因此在这里信道是过载的。
7. 答：每帧传送次数的数学期望为：
-G
-G
–G
E 个事件为E-1 个长度等于4 个时隙的间隔时间所分隔。因此一个帧从第一次发送开始
G-G时间到最后一次尝试成功的发送开始时间之间的长度即延迟是4(e-1)，吞吐率S= Ge。
对于每一个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
个节点。在i 级的每个节点下面所包括的站的个数等于总站数的1/2 。本题中所需要的时隙数取决于为了到达准备好发送的两个站的共同先辈点必须往回走多少级。先计算这两个站具
n
有共同的父节点的概率p1。在2个站中，要发送的两个站共享一个指定的父节点的概率是
总共2 n -1个父节点，所以，
因为 2 >> 1 所以p1≈2
- n
n
在共享父节点的条件下遍历树，从第二级开始每一级访问两个节点，这样遍历树所走过的节点总数n1 = 1++2+…+2+2=1=2n，接下来，我们考察两个发送站共享祖父节点的概率p2和遍历树所走过的节点总数n2。此时在每个父节点下面仅可能有一个站发送。两个发送站共享一个指定的祖父节点的概率是1/ C 22n-1。
共有2 n -2个祖父节点
遍历树比1 n 减少两个节点，即
通过类似的分析和计算，可以得到，两个发送站共享曾祖父节点（属n-3 级祖先节点）
-n++2
的概率是 p3=2
遍历树所经过的节点总数比n2又少两个节点，
因此，最坏的情形是2n+1 个时隙（共享父节点），对应于i=0；
最好的情形是3 个时隙，对应于i=n-1 （两个发送站分别位于左半树和右半树），所以平均时隙数等于
该表达式可以简化为
12. 答：如果所有站的发射有效范围都很大，以至于任一站都可以收到所有其他站发送的信号，那么任一站都可以与其他站以广播方式通信。在这样的条件下，CSMA/CD 可以工作的很好。