Chapter 4 The Medium Access Control Sublayer Problems

e. (b) What is the probability of exactly k collisions and then a success?

f. (c) What is the expected number of transmission attempts needed?（M）

1. For this problem, use a formula from this chapter, but first state the formula. Frames arrive randomly at a 100-Mbps channel for transmission. If the channel is （a）在任一帧时间内生成 k 帧的概率服从泊松分布

busy when a frame arrives, it waits its turn in a queue. Frame length is exponentially distributed with a mean of 10,000 bits/frame. For each of the following 生成 0 帧的概率为 e-G；对于纯的 ALOHA，发送一帧的冲突危险区为两个帧时， frame arrival rates, give the delay experienced by the average frame, including both 在两帧内无其他帧发送的概率是 e-G×e –G=e-2G；对于分隙的 ALOHA，由于冲突危险 queueing time and transmission time.（E） 区减少为原来的一半，任一帧时内无其他帧发送的概率是 e-G。 a. (a) 90 frames/sec. b. (b) 900 frames/sec. c. (c) 9000 frames/sec. 排队理论延迟时间公式： ，这里信道容量 C=108 and ，所以 现在时隙长度为 40ms，即每秒 25 个时隙，产生 50

次请求，

所以每个时隙产生 两个请求，G=2。因此，首次尝试的成功率是：e-2= 1/ e2 （b） （c）尝试 k 次冲突，第 k 次才能发送成功的概率（即前 k-1次才成功）为：

sec，对上面的三种帧到达率?，有 (a) 0.1 msec,(b) 0.11 msec, (c) 1 msec. 对于 (c)， 10 倍延迟。 由 sec. What is the approximate total channel load?（E） 2. A group of N stations share a 56-kbps pure ALOHA channel. Each station μoutputs a 1000-bit frame on an average of once every 100 sec, even if the previous 每个终端每 200（=3600/18）秒做一次请求，总共有 10 000 个终端，因此，总的

秒做 10000 次请求。平均每秒钟 50 次请求。每one has not yet been sent (e.g., the stations can buffer outgoing frames). What is 负载是 200 秒钟 8000 个时隙，所 the 以平均每个时隙的发送次数为 50/8000=1/160。 maximum value of N?（E） 5. A large population of ALOHA users manages to generate 50 requests/sec, 对于纯的 ALOHA，信道利用率为 1/e2= 0.184，可用的带宽是 0.184×56 Kb/s=10.304Kb/ s。每个站需要的带宽为 1000/100=10b/s。而N=10304/10≈1030 including both originals and retransmissions. Time is slotted in units of 40 msec. d. (a) What is the chance of success on the first attempt? 所以，最多可以有 1030 个站，即 N 的最大值为 1030。 3. Consider the delay of pure ALOHA versus slotted ALOHA at low load. Which one is less? Explain your answer.（E） 对于纯的 ALOHA，发送可以立即开始。对于分隙的 ALOHA，它必须等待下一个 时隙。这样，平均会引入半个时隙的延迟。因此，纯 ALOHA 小。 的延迟比较4. Ten thousand airline reservation stations are competing for the use of a single

slotted ALOHA channel. The average station makes 18 requests/hour. A slot is 125

7. In an infinite-population slotted ALOHA system, the mean number of slots a

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

6. Measurements of a slotted ALOHA channel with an infinite number of station waits between a collision and its retransmission is 4. Plot the delay versus throughput curve for this system.（M）

users

show that 10 percent of the slots are idle. g. (a) What is the channel load, G? h. (b) What is the throughput?

i. (c) Is the channel underloaded or overloaded?(E)

（a）从泊松定律得到 p0= e –G ，因此 G = - lnp0 = - ln0.1 = 2.3 （b） S = G e-G， G = 2.3，e –G=0.1 ，S = 2.3*0.1 = 0.23

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

的。

每帧传送次数的数学期望为： E 个事件为 E-1 个长度等于 4

个时隙的间隔时间所分隔。因此一

个帧从第一次

发送开始时间到最后一次尝试成功的发送开始时间之间的长度即延迟是 4(eG1)，吞 吐率 S= Ge-G。

对于每一个 G 值，都可以计算出对应的延迟值 D=4(eG-1)，以及吞吐率值 S=Ge-G

。

- 13 -

are needed to resolve the contention?（E）

8. How long does a station, s, have to wait in the worst case before it can start 在自适应树遍历协议中，可以把站点组织成二叉树（见图）的形式。在一次成功 transmitting its frame over a LAN that uses 的传输之后，在第一个竞争时隙中，全部站都可以试图获得信道，如果仅其中之一

需用信道，则发送冲突，则第二时隙内只有那些位于节点 B 以下的站（0j. (a) the basic bit-map protocol?

到 7）可 k. (b) Mok and Ward's protocol with permuting virtual station numbers?

以参加竞争。如其中之一获得信道，本帧后的时隙留给站点 C 以下的（M）

站；如果 B 点

(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)×\慇2Xd+N×log2 bits.

当竞争周期刚刚扫瞄过的时候，N 号站点正好由数据发送，所以他要等到数据 1

发送完（最差时前面 N-1 个站点都有数据要发，即（N-1）*d）,然后下一个扫描周

期（N 位），再等前面所有站点发送完数据；所以总的延迟为： （N-1）*d+N+(N-1)*d=2（N-1）*d+N ;

9. A LAN uses Mok and Ward's version of binary countdown. At a certain instant,

the ten stations have the virtual station numbers 8, 2, 4, 5, 1, 7, 3, 6, 9, and 0. The next three stations to send are 4, 3, and 9, in that order. What are the new virtual station numbers after all three have finished their transmissions?（E） 当 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. Sixteen stations, numbered 1 through 16, are contending for the use of a shared channel by using the adaptive tree walk protocol. If all the stations whose addresses are prime numbers suddenly become ready at once, how many bit slots

下面有两个或更多的站希望发送，在第二时隙内会发生冲突，于是第三时隙内由 D

节点以下各站来竞争信道。

的时隙数取决于为了到达准备好发送的两个站的共同先辈点必须往回走多少级。先 计算这两个站具有共同的父节点的概率 p1。在 2n个站中，要发送的两个站共享一个

指定的父节点的概率是

- 14 -

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

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

和 13 要发送，需要 11 个时

11. A collection of 2n stations uses the adaptive tree walk protocol to arbitrate

access to a shared cable. At a certain instant, two of them become ready. What are

the minimum, maximum, and mean number of slots to walk the tree if 2n >>1?（H）

2 n个站点对应 n+1 级，其中 0

级有 1

个节点，1

级有 2

个节点， n 级有 2 n个 节点。在 i 级的每个节点下面所包括的站的个数等于总站数的 1/2i。本题中所需要