3/4/6/9/11/13/14/17/22/25/27/28/30/31/

2/3/4/5/7/8/18/22/28/29/30/33/34/39/41/42/43/44/50/53/

1/2/5/6/16/17/18/19/20/21/22/23/24/25/26/28/29/30/32/

1/2/3/4/5/6/8/10/14/21/22/23/24/37/38/42/43/

1/2/3/5/6/7/9/10/12/14/15/21/22/23/24/25/27/28/31/32/34

1/2/4/5/6/7/8/9/10/11/12/13/14/15/18/19/20/23

1/2/5/6/7/8/9/10/11/26/27/28

The performance of a client-server system is influenced by two network factors: the bandwidth of the network (how many bits/sec it can transport) and the latency (how many seconds it takes for the first bit to get from the client to the server). Give an example of a network that exhibits high bandwidth and high latency. Then give an example of one with low bandwidth and low latency.

A transcontinental fiber link might have many gigabits/sec of bandwidth, but the latency will also be high due to the speed of light propagation over thousands of kilometers. In contrast, a 56-kbps modem calling a computer in the same building has low bandwidth and low latency.

答：横贯大陆的光纤连接可以有很多千兆位/秒带宽， 但是由于光速度传送要越过数千公里，时延将也高。相反，使用56 kbps调制解调器呼叫在同一大楼内的计算机则有低带宽和较低的时延。

Besides bandwidth and latency, what other parameter is needed to give a good characterization of the quality of service offered by a network used for digitized voice traffic?

A uniform delivery time is needed for voice, so the amount of jitter in the network is important. This could be expressed as the standard deviation of the delivery time. Having short delay but large variability is actually worse than a somewhat longer delay and low variability.

声音的传输需要相应的固定时间，因此网络时隙数量是很重要的。传输时间可以用标准偏差方式表示。 实际上，短延迟但是大变化性比更长的延迟和低变化性更糟。

A client-server system uses a satellite network, with the satellite at a height of 40,000 km. What is the best-case delay in response to a request?

The request has to go up and down, and the response has to go up and down. The total path length traversed is thus 160,000 km. The speed of light in air and vacuum is 300,000 km/sec, so the propagation delay alone is 160,000/300,000 sec or about 533 msec.

答：由于请求和应答都必须通过卫星，因此传输总路径长度为160,000千米。在空气和真空中的光速为300，000 公里/秒， 因此最佳的传播延迟为160,000/300，000秒，约533 msec。

A group of 2n - 1 routers are interconnected in a centralized binary tree, with a router at each tree node. Router i communicates with router j by sending a message to the root of the tree. The root then sends the message back down to j. Derive an approximate expression for the mean number of hops per message for large n, assuming that all router pairs are equally likely.

The mean router-router path is twice the mean router-root path. Number the levels of the tree with the root as 1 and the deepest level as n. The path from the root to level n requires n − 1 hops, and 0.50 of the routers are at this level. The path from the root to level n − 1 has 0.25 of the routers and a length of n - 2 hops. Hence, the mean path length, l, is given by
.or.

This expression reduces to l = n - 2. The mean router-router path is thus 2n - 4.

这意味着，从路由器到路由器的路径长度相当于路由器到根的两倍。 若在树中，根深度为1，深度为n，从根到第n层需要n-1跳，在该层的路由器为0.50。 从根到n-1 层的路径有router的0.25和n–2跳步。 因此，路径长度l为：

This expression reduces to l＝n－2，这意味着，router-router 路径为2n-4。

What are two reasons for using layered protocols?

Among other reasons for using layered protocols, using them leads to breaking up the design problem into smaller, more manageable pieces, and layering means that protocols can be changed without affecting higher or lower ones.

答：通过协议分层可以把设计问题划分成较小的易于处理的片段。分层意味着某一层的协议的改变不会影响高层或低层的协议。

What is the principal difference between connectionless communication and connection-oriented communication?

Connection-oriented communication has three phases. In the establishment phase a request is made to set up a connection. Only after this phase has been successfully completed can the data transfer phase be started and data transported. Then comes the release phase. Connectionless communication does not have these phases. It just sends the data.

答：主要的区别有两条。 其一：面向连接通信分为三个阶段，第一是建立连接，在此阶段，发出一个建立连接的请求。只有在连接成功建立之后，才能开始数据传输，这是第二阶段。接着，当数据传输完毕，必须释放连接。而无连接通信没有这么多阶段，它直接进行数据传输。 其二：面向连接的通信具有数据的保序性， 而无连接的通信不能保证接收数据的顺序与发送数据的顺序一致。

Two networks each provide reliable connection-oriented service. One of them offers a reliable byte stream and the other offers a reliable message stream. Are these identical? If so, why is the distinction made? If not, give an example of how they differ.

Message and byte streams are different. In a message stream, the network keeps track of message boundaries. In a byte stream, it does not. For example, suppose a process writes 1024 bytes to a connection and then a little later writes another 1024 bytes. The receiver then does a read for 2048 bytes. With a message stream, the receiver will get two messages, of 1024 bytes

答：不相同。在报文流中，网络保持对报文边界的跟踪；而在字节流中，网络不做这样的跟踪。例如，一个进程向一条连接写了1024 字节，稍后又写了另外1024 字节。那么接收方共读了2048 字节。对于报文流，接受方将得到两个报文。每个报文1024 字节。 而对于字节流，报文边界不被识别。接收方把全部的2048 个字节当作一个整体，在此已经体现不出原先有两个报文的事实。

In some networks, the data link layer handles transmission errors by requesting damaged frames to be retransmitted. If the probability of a frame's being damaged is p, what is the mean number of transmissions required to send a frame? Assume that acknowledgements are never lost.

第k个帧需要传输的可能性是k-1个帧传输失败的可能性，乘以第k个帧传输成功的可能性，所以平均数是 ,乘以(1-p). 也就是

What is the main difference between TCP and UDP?

TCP is connection oriented, whereas UDP is a connectionless service

答：TCP 是面向连接的，而UDP 是一种数据报服务。

When a file is transferred between two computers, two acknowledgement strategies are possible. In the first one, the file is chopped up into packets, which are individually acknowledged by the receiver, but the file transfer as a whole is not acknowledged. In the second one, the packets are not acknowledged individually, but the entire file is acknowledged when it arrives. Discuss these two approaches.

If the network tends to lose packets, it is better to acknowledge each one separately, so the lost packets can be retransmitted. On the other hand, if the network is highly reliable, sending one acknowledgement at the end of the entire transfer saves bandwidth in the normal case (but requires the entire file to be retransmitted if even a single packet is lost).

如果网络容易丢失分组，那么对每一个分组逐一进行确认较好，此时仅重传丢失的分组。而在另一方面，如果网络高度可靠，那么在不发差错的情况下，仅在整个文件传送的结尾发送一次确认，从而减少了确认的次数，节省了带宽；不过，即使有单个分组丢失，也需要重传整个文件。

An image is 1024 x 768 pixels with 3 bytes/pixel. Assume the image is uncompressed. How long does it take to transmit it over a 56-kbps modem channel? Over a 1-Mbps cable modem? Over a 10-Mbps Ethernet? Over 100-Mbps Ethernet?

同轴电缆内的光速大约是 200,000 km/sec, 也就是 200 meters/µsec. 在 10 Mbps速度上, 需要 0.1 µsec 来传输一个bit. 所以, 0.1 µsec, 其间传输了20米，所以一个 bit在这里是20米。

An image is 1024 x 768 pixels with 3 bytes/pixel. Assume the image is uncompressed. How long does it take to transmit it over a 56-kbps modem channel? Over a 1-Mbps cable modem? Over a 10-Mbps Ethernet? Over 100-Mbps Ethernet?

The image is 1024 768 3 bytes or 2,359,296 bytes. This is 18,874,368 bits. At 56,000 bits/sec, it takes about 337.042 sec. At 1,000,000 bits/sec, it takes about 18.874 sec. At 10,000,000 bits/sec, it takes about 1.887 sec. At 100,000,000 bits/sec, it takes about 0.189 sec.

图像是1024*768*3 bytes, 也就是2,359,296 bytes, 18,874,368 bits….

Wireless networks are easy to install, which makes them inexpensive since installation costs usually far overshadow equipment costs. Nevertheless, they also have some disadvantages. Name two of them.

One disadvantage is security. Every random delivery man who happens to be in the building can listen in on the network. Another disadvantage is reliabil- ity. Wireless networks make lots of errors. A third potential problem is bat- tery life, since most wireless devices tend to be mobile.

劣势有安全性，可靠性，和电池能量补给。

List two advantages and two disadvantages of having international standards for network protocols.

One advantage is that if everyone uses the standard, everyone can talk to everyone. Another advantage is that widespread use of any standard will give it economies of scale, as with VLSI chips. A disadvantage is that the political compromises necessary to achieve standardization frequently lead to poor standards. Another disadvantage is that once a standard has been widely adopted, it is difficult to change,, even if new and better techniques or methods are discovered. Also, by the time it has been accepted, it may be obsolete.

优点1：如果每个人都使用标准，那么每个人都可以与其他任何人交流；优点2：广泛使用标准将导致规模经济，比如生产大规模集成电路芯片。缺点1：为了取得标准化所需要的政治妥协经常会导致差的标准；缺点2：一旦标准被广泛采用了，要对它再做改变就会非常困难，即使发现了新的更好的技术或方法，也难以替换。

A noiseless 4-kHz channel is sampled every 1 msec. What is the maximum data rate?

答：无噪声信道最大数据传输率公式：最大数据传输率=2Hlog2V b/s。因此最大数据传输率决定于每次采样所产生的比特数，如果每次采样产生16bits，那么数据传输率可达128kbps；如果每次采样产生1024bits，那么可达8.2Mbps。注意这是对无噪声信道而言的，实际信道总是有噪声的，其最大数据传输率由香农定律给出。

Television channels are 6 MHz wide. How many bits/sec can be sent if four-level digital signals are used? Assume a noiseless channel.

答：采样频率12MHz，每次采样2bit，总的数据率为24Mbps。

If a binary signal is sent over a 3-kHz channel whose signal-to-noise ratio is 20 dB, what is the maximum achievable data rate?

答：信噪比为20 dB 即 S/N =由于 log2101≈6.658，由香农定理，该信道的信道容量为3log2+=19.98kbps。 又根据乃奎斯特定理，发送二进制信号的3kHz 信道的最大数据传输速率为 2*3 log22=kbps。 所以可以取得的最大数据传输速率为6kbps。

What signal-to-noise ratio is needed to put a T1 carrier on a 50-kHz line?

答：为发送T1 信号，我们需要
而.
得出
接近90dB
所以，在50kHz 线路上使用T1载波需要93dB的信噪比。

How much bandwidth is there in 0.1 micron of spectrum at a wavelength of 1 micron?

因此，在0.1的频段中可以有30THz。

It is desired to send a sequence of computer screen images over an optical fiber. The screen is 480 x 640 pixels, each pixel being 24 bits. There are 60 screen images per second. How much bandwidth is needed, and how many microns of wavelength are needed for this band at 1.30 microns?

答：数据速率为480×640×24×60bps，即442Mbps。

A simple telephone system consists of two end offices and a single toll office to which each end office is connected by a 1-MHz full-duplex trunk. The average telephone is used to make four calls per 8-hour workday. The mean call duration is 6 min. Ten percent of the calls are long-distance (i.e., pass through the toll office). What is the maximum number of telephones an end office can support? (Assume 4 kHz per circuit.)

答：每部电话每小时做0.5 次通话，每次通话6 分钟。因此一部电话每小时占用一条电路3 分钟，60/3=20，即20 部电话可共享一条线路。由于只有10%的呼叫是长途，所以200 部电话占用一条完全时间的长途线路。局间干线复用了1000000/4000=250 条线路，每条线路支持200 部电话，因此，一个端局可以支持的电话部数为200*250=50000。

A modem constellation diagram similar to Fig. 2-25 has data points at the following coordinates: (1, 1), (1, -1), (-1, 1), and (-1, -1). How many bps can a modem with these parameters achieve at 1200 baud?

每个波特有4 个合法值，因此比特率是波特率的两倍。对应于1200 波特，数据速率是2400bps。

Ten signals, each requiring 4000 Hz, are multiplexed on to a single channel using FDM. How much minimum bandwidth is required for the multiplexed channel? Assume that the guard bands are 400 Hz wide.

There are ten 4000 Hz signals. We need nine guard bands to avoid any interference. The minimum bandwidth required is 4000×10+400×9 =43,600 Hz.

有10个4000Hz的信号，我们需要9个守护band来避免干扰，虽小的带宽是 4000×10+400×9 =43,600 Hz.

Why has the PCM sampling time been set at 125 µsec?

答：125的采样时间对应于每秒8000 次采样。一个典型的电话通道为4kHz。根据奈奎斯特定理，为获取一个4kHz 的通道中的全部信息需要每秒8000 次的采样频率。

What is the percent overhead on a T1 carrier; that is, what percent of the 1.544 Mbps are not delivered to the end user?

每一帧中，端点用户使用193 位中的168（7*24）位，开销占25（=193-168）位，因此开销比例等于25/193=13%。

What is the difference, if any, between the demodulator part of a modem and the coder part of a codec? (After all, both convert analog signals to digital ones.)

答：有。编码器接受任意的模拟信号，并从它产生数字信号。而解调器仅仅接受调制了的正弦（或余弦）波，产生数字信号。

A signal is transmitted digitally over a 4-kHz noiseless channel with one sample every 125 µsec. How many bits per second are actually sent for each of these encoding methods?

1. CCITT 2.048 Mbps standard.
2. DPCM with a 4-bit relative signal value.
3. Delta modulation.

答：

1. CCITT 2.048Mbps 标准用32 个8 位数据样本组成一个125 的基本帧，30个信道用于传信息，2 个信道用于传控制信号。在每一个4kHz信道上发送的数据率就是8*8000=64kbps。
2. 差分脉码调制（DPCM）是一种压缩传输信息量的方法，它发送的不是每一次抽样的二进制编码值，而是两次抽样的差值的二进制编码。现在相对差值是4位，所以对应每个4kHz 信道实际发送的比特速率为4*8000=32bps。
3. 增量调制的基本思想是：当抽样时间间隔s t很短时，模拟数据在两次抽样之间的变化很小，可以选择一个合适的量化值?作为阶距。把两次抽样的差别近似为不是增加一个?就是减少一个?。这样只需用1bit二进制信息就可以表示一次抽样结果，而不会引入很大误差。因此，此时对应每个4kHz信道实际发送的数据速率为1*8000=8kHz。

What is the essential difference between message switching and packet switching?

Message switching sends data units that can be arbitrarily long. Packet switching has a maximum packet size. Any message longer than that is split up into multiple packets.

Three packet-switching networks each contain n nodes. The first network has a star topology with a central switch, the second is a (bidirectional) ring, and the third is fully interconnected, with a wire from every node to every other node. What are the best-, average-, and-worst case transmission paths in hops?

答：The three networks have the following properties:

• 星型：最好为2，最差为2，平均为2；
• 环型：最好为1，最差为n/2，平均为n/4
• 如果考虑n 为奇偶数，则n
• 为奇数时，最坏为（n-1）/2，平均为（n+1）/4n 为偶数时，最坏为n/2，平均为n2/4(n-1)
• 全连接：最好为1，最差为1，平均为1。

Compare the delay in sending an x-bit message over a k-hop path in a circuit-switched network and in a (lightly loaded) packet-switched network. The circuit setup time is s sec, the propagation delay is d sec per hop, the packet size is p bits, and the data rate is b bps. Under what conditions does the packet network have a lower delay?

对于电路交换， t=s时电路建立起来； 时报文的最后一位发送完毕；时报文到达目的地。而对于分组交换，最后一位在时发送完毕。 为到达最终目的地，最后一个分组必须被中间的路由器重发k次，每次重发花时间p/ b，所以总的延迟为:

为了使分组交换比电路交换快，必须：

所以：

Suppose that x bits of user data are to be transmitted over a k-hop path in a packet-switched network as a series of packets, each containing p data bits and h header bits, with x p + h. The bit rate of the lines is b bps and the propagation delay is negligible. What value of p minimizes the total delay?

所需要的分组总数是 x/p ，因此总的数据加上头信息交通量为(p+h)x/p 位。 源端发送这些位需要时间为(p+h)x/pb 中间的路由器重传最后一个分组所花的总时间为(k-1)(p+h)/b 因此我们得到的总的延迟为:
秒。
对p求导，我们得到：

In a typical mobile phone system with hexagonal cells, it is forbidden to reuse a frequency band in an adjacent cell. If 840 frequencies are available, how many can be used in a given cell?

Each cell has six neighbors. If the central cell uses frequency group A, its six neighbors can use B, C, B, C, B, and C respectively. In other words, only 3 unique cells are needed. Consequently, each cell can have 280 frequencies.

Suppose that A, B, and C are simultaneously transmitting 0 bits, using a CDMA system with the chip sequences of Fig. 2-45(b). What is the resulting chip sequence?

The result is obtained by negating each of A, B, and C and then adding the three chip sequences. Alternatively the three can be added and then negated. The result is (+3 +1 +1 −1 −3 −1 −1 +1).

A CDMA receiver gets the following chips: (-1 +1 -3 +1 -1 -3 +1 +1). Assuming the chip sequences defined in Fig. 2-45(b), which stations transmitted, and which bits did each one send?

Just compute the four normalized inner products:
(−1 +1 −3 +1 −1 −3 +1 +1) * (−1 −1 −1 +1 +1 −1 +1 +1)/8 = 1
(−1 +1 −3 +1 −1 −3 +1 +1) * (−1 −1 +1 −1 +1 +1 +1 −1)/8 = −1
(−1 +1 −3 +1 −1 −3 +1 +1) * (−1 +1 −1 +1 +1 +1 −1 −1)/8 = 0
(−1 +1 −3 +1 −1 −3 +1 +1) * (−1 +1 −1 −1 −1 −1 +1 −1)/8 = 1
The result is that A and D sent 1 bits, B sent a 0 bit, and C was silent.

An upper-layer packet is split into 10 frames, each of which has an 80 percent chance of arriving undamaged. If no error control is done by the data link protocol, how many times must the message be sent on average to get the entire thing through?

由于每一帧有0.8的概率正确到达，整个信息正确到达的概率为 。 为使信息完整的到达接收方，发送一次成功的概率是p，二次成功的概率是(1-p)p，三 次成功的概率为，i 次成功的概率为，因此平均的发送次数等于：

The following character encoding is used in a data link protocol: A: 01000111; B: 11100011; FLAG: 01111110; ESC: 11100000 Show the bit sequence transmitted (in binary) for the four-character frame: A B ESC FLAG when each of the following framing methods are used:

1. Character count.
2. Flag bytes with byte stuffing.
3. Starting and ending flag bytes, with bit stuffing.

答：

1. 00000100 01000111 11100011 11100000 01111110
2. 01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110
3. 01111110 01000111 110100011 111000000 011111010 01111110

A bit string, 0111101111101111110, needs to be transmitted at the data link layer. What is the string actually transmitted after bit stuffing?

答：011110111110011111010.

When bit stuffing is used, is it possible for the loss, insertion, or modification of a single bit to cause an error not detected by the checksum? If not, why not? If so, how? Does the checksum length play a role here?

答：可能。假定原来的正文包含位序列01111110 作为数据。位填充之后，这个序列将变成01111010。如果由于传输错误第二个0 丢失了，收到的位串又变成01111110，被接收方看成是帧尾。然后接收方在该串的前面寻找检验和，并对它进行验证。如果检验和是16 位，那么被错误的看成是检验和的16 位的内容碰巧经验证后仍然正确的概率是1/216。如果这种概率的条件成立了，就会导致不正确的帧被接收。显然，检验和段越长，传输错误不被发现的概率会越低，但该概率永远不等于零。

Data link protocols almost always put the CRC in a trailer rather than in a header. Why?

答：CRC 是在发送期间进行计算的。一旦把最后一位数据送上外出线路，就立即把CRC编码附加在输出流的后面发出。如果把CRC 放在帧的头部，那么就要在发送之前把整个帧先检查一遍来计算CRC。这样每个字节都要处理两遍，第一遍是为了计算检验码，第二遍是为了发送。把CRC 放在尾部就可以把处理时间减半。

A channel has a bit rate of 4 kbps and a propagation delay of 20 msec. For what range of frame sizes does stop-and-wait give an efficiency of at least 50 percent?

答：当发送一帧的时间等于信道的传播延迟的2 倍时，信道的利用率为50%。或者说，当发送一帧的时间等于来回路程的传播延迟时，效率将是50%。而在帧长满足发送时间大于延迟的两倍时，效率将会高于50%。 现在发送速率为4Mb/s，发送一位需要0.25 。

只有在帧长不小于160kb 时，停等协议的效率才会至少达到50%。

A 3000-km-long T1 trunk is used to transmit 64-byte frames using protocol 5. If the propagation speed is 6 µsec/km, how many bits should the sequence numbers be?

答；为了有效运行，序列空间（实际上就是发送窗口大小）必须足够的大，以允许发送方在收到第一个确认应答之前可以不断发送。信号在线路上的传播时间为 6×3000=18000，即18ms。 在T1 速率，发送64 字节的数据帧需花的时间：64×8÷(1.536×106)= 0.33。 所以，发送的第一帧从开始发送起，18.33ms 后完全到达接收方。确认应答又花了很少的发送时间（忽略不计）和回程的18ms。这样，加在一起的时间是36.33ms。发送方应该 有足够大的窗口，从而能够连续发送36.33ms。 36. 33/0.33=110 也就是说，为充满线路管道，需要至少110 帧，因此序列号为7 位。

In protocol 3, is it possible that the sender starts the timer when it is already running? If so, how might this occur? If not, why is it impossible?

It can happen. Suppose that the sender transmits a frame and a garbled acknowledgement comes back quickly. The main loop will be executed a second time and a frame will be sent while the timer is still running.

它可能发生。假设发送方传送一个框架和一 乱码确认回来快。主循环将 执行第二次并且帧将被发送，而定时器仍在运行

Imagine a sliding window protocol using so many bits for sequence numbers that wraparound never occurs. What relations must hold among the four window edges and the window size, which is constant and the same for both the sender and the receiver.

发送窗口为 (Sl , Su), 接收窗口为 (Rl , Ru). 窗口大小为 W. 下列关系必须被满足： 0 ≤Su- Si +1 ≤W1 Ru Rl 1 W Sl ≤Rl ≤Su 1

If the procedure between in protocol 5 checked for the condition a ⇐ b ⇐ c instead of the condition a ⇐ b < c, would that have any effect on the protocol's correctness or efficiency? Explain your answer.

答：改变检查条件后，协议将变得不正确。假定使用3 位序列号，考虑下列协议运行过程： A 站刚发出7 号帧；B 站接收到这个帧，并发出捎带应答ack。A 站收到ack，并发送0~6 号帧。假定所有这些帧都在传输过程中丢失了。B 站超时，重发它的当前帧，此时捎带的确认号是7。考察A 站在r.rack=7 到达时的情况，关键变量是ack_expected=0，r.rack=7，next_frame_to_send_=7。修改后的检查条件将被置成“真”，不会报告已发现的丢失帧错误，而误认为丢失了的帧已被确认。另一方面，如果采用原先的检查条件，就能够报告丢失帧的错误。所以结论是：为保证协议的正确性，已接收的确认应答号应该小于下一个要发送的序列号。

In protocol 6, when a data frame arrives, a check is made to see if the sequence number differs from the one expected and no_nak is true. If both conditions hold, a NAK is sent. Otherwise, the auxiliary timer is started. Suppose that the else clause were omitted. Would this change affect the protocol's correctness?

答：可能导致死锁。假定有一组帧正确到达，并被接收。然后，接收方会向前移动窗口。 现在假定所有的确认帧都丢失了，发送方最终会产生超时事件，并且再次发送第一帧，接收方将发送一个NAK。然后NONAK 被置成伪。假定NAK 也丢失了。那么从这个时候开始，发送方会不断发送已经被接收方接受了的帧。接收方只是忽略这些帧，但由于NONAK 为伪，所以不会再发送NAK，从而产生死锁。如果设置辅助计数器（实现“else”子句），超时后重发NAK，终究会使双方重新获得同步。

Suppose that the three-statement while loop near the end of protocol 6 were removed from the code. Would this affect the correctness of the protocol or just the performance? Explain your answer.

答：删除这一段程序会影响协议的正确性，导致死锁。因为这一段程序负责处理接收到的确认帧，没有这一段程序，发送方会一直保持超时条件，从而使得协议的运行不能向前进展。

Suppose that the case for checksum errors were removed from the switch statement of protocol 6. How would this change affect the operation of the protocol?

答：It would defeat the purpose of having NAKs, so we would have to fall back to timeouts. Although the performance would degrade, the correctness would not be affected. The NAKs are not essential.

这样一来NAK就不需要了，我们可以回到超时机制，这样性能也许会下降，正确性却不会受影响，NAK不再是必要的了。

In protocol 6 the code for frame_arrival has a section used for NAKs. This section is invoked if the incoming frame is a NAK and another condition is met. Give a scenario where the presence of this other condition is essential.

答：这里要求r.rack+1<next_frame_to_send。考虑下列操作细节： A 站发送0 号帧给B 站。B 站收到此帧，并发送ACK帧，但ACK丢失了。A 站发生超时，重发0 号帧。但B 站现在期待接收1 号帧，应此发送NAK，否定收到的0 号帧。显然，现在A 站最好不重发0 号帧。由于条件r.rack+1<next_frame_to_send 不成立，所以用不着选择性重传0 号帧，可以继续向前推进传送1 号帧。这个例子就说明了这段程序中的另一个条件，即r.rack+1<next_frame_to_send 也是重要的。

Imagine that you are writing the data link layer software for a line used to send data to you, but not from you. The other end uses HDLC, with a 3-bit sequence number and a window size of seven frames. You would like to buffer as many out-of-sequence frames as possible to enhance efficiency, but you are not allowed to modify the software on the sending side. Is it possible to have a receiver window greater than 1, and still guarantee that the protocol will never fail? If so, what is the largest window that can be safely used?

答：不可以。最大接收窗口的大小就是1。现在假定该接收窗口值变为2。开始时发送方发送0 至6 号帧，所有7 个帧都被收到，并作了确认，但确认被丢失。现在接收方准备接收7 号和0 号帧，当重发的0 号帧到达接收方时，它将会被缓存保留，接收方确认6 号帧。当7 号帧到来的时候，接收方将把7 号帧和缓存的0 号帧传递给主机，导致协议错误。因此，能够安全使用的最大窗口值为1。

In protocol 6, MAX_SEQ = 2n - 1. While this condition is obviously desirable to make efficient use of header bits, we have not demonstrated that it is essential. Does the protocol work correctly for MAX_SEQ = 4, for example?

答：不能，协议的运行将会失败。当MaxSeq=4，序列号的模数=4+1=5，窗口大小将等于：NrBufs⇐5/2=2.5，即得到，NrBufs=2。因此在该协议中，偶数序号使用缓冲区1。这种映射意味着帧4 和0 将使用同一缓冲区。假定0 至3 号帧都正确收到了，并且都确认应答了，并且都确认应答了。如果随后的4 号帧丢失，且下一个0 号帧收到了，新的0 号帧将被放到缓冲区0 中，变量arrived[0]被置成“真”。这样，一个失序帧将被投递给主机。事实上，采用选择性重传的滑动窗口协议需要MaxSeq 是奇数才能正确的工作。然而其他的滑动窗口协议的实现并不具有这一性质。

Frames of 1000 bits are sent over a 1-Mbps channel using a geostationary satellite whose propagation time from the earth is 270 msec. Acknowledgements are always piggybacked onto data frames. The headers are very short. Three-bit sequence numbers are used. What is the maximum achievable channel utilization for (a) Stop-and-wait. (b) Protocol 5. © Protocol 6.

答：对应三种协议的窗口大小值分别是1、7 和4。 使用卫星信道端到端的典型传输延迟是270ms，以1Mb/s 发送，1000bit 长的帧的发送时间为1ms。我们用t=0 表示传输开始的时间，那么在t=1ms 时，第一帧发送完毕；t=271ms时，第一帧完全到达接收方；t=272ms，对第一帧的确认帧发送完毕；t=542ms，带有确认的帧完全到达发送方。因此一个发送周期为542ms。如果在542ms 内可以发送k 个帧，由于每一个帧的发送时间为1ms，则信道利用率为k/542，因此： （a） k=1，最大信道利用率=1/542=0.18% （b） k=7，最大信道利用率=7/542=1.29% （c） k=4，最大信道利用率=4/542=0.74%

Compute the fraction of the bandwidth that is wasted on overhead (headers and retransmissions) for protocol 6 on a heavily-loaded 50-kbps satellite channel with data frames consisting of 40 header and 3960 data bits. Assume that the signal propagation time from the earth to the satellite is 270 msec. ACK frames never occur. NAK frames are 40 bits. The error rate for data frames is 1 percent, and the error rate for NAK frames is negligible. The sequence numbers are 8 bits.

答：使用选择性重传滑动窗口协议，序列号长度是8位。窗口大小为128。卫星信道端到端的传输延迟是270ms。以50kb/s 发送，4000bit(3960+40)长的数据帧的发送时间是0.02*4000=80ms。 我们用t=0表示传输开始时间，那么，t=80ms，第一帧发送完毕；t=270+80=350ms， 第一帧完全到达接收方；t=350+80=430ms， 对第一帧作捎带确认的反向数据帧可能发送完毕；t=430+270=700ms，带 有确认的反向数据帧完全到达发送方。因此，周期为700ms，发送128 帧时间80*128=10240ms，这意味着传输管道总是充满的。每个帧重传的概率为0.01，对于3960 个数据位，头开销为40位，平均重传的位数为4000*0.01=40位，传送NAK 的平均位数为40*1/100=0.40 位，所以每3960个数据位的总开销为80.4 位。 因此，开销所占的带宽比例等于80.4/(3960+80.4)=1.99%。

A 100-km-long cable runs at the T1 data rate. The propagation speed in the cable is 2/3 the speed of light in vacuum. How many bits fit in the cable?

答：在该电缆中的传播速度是每秒钟200 000km，即每毫秒200km，因此100km 的电缆将会在0.5ms 内填满。T1 速率125 传送一个193 位的帧，0.5ms 可以传送4 个T1 帧，即193*4=772bit。

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 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 frame arrival rates, give the delay experienced by the average frame, including both queueing time and transmission time.

1. 90 frames/sec.
2. 900 frames/sec.
3. 9000 frames/sec.

The formula is the standard formula for Markov queueing given in section 4.1.1, namely, Here and so sec. For the three arrival rates, we get

1. 0.1 msec,
2. 0.11 msec,
3. 1 msec.

For case 3 we are operating a queueing system with , which gives the 10× delay.

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 one has not yet been sent (e.g., the stations can buffer outgoing frames). What is the maximum value of N? 答：对于纯的ALOHA，可用的带宽是0.184×56 Kb/s=10.304Kb/ s。 每个站需要的带宽为1000/100=10b/s。而N=10304/10≈1030 所以，最多可以有1030个站，即N 的最大值为1030。

Consider the delay of pure ALOHA versus slotted ALOHA at low load. Which one is less? Explain your answer. 答：对于纯的ALOHA，发送可以立即开始。对于分隙的ALOHA，它必须等待下一个时隙。这样，平均会引入半个时隙的延迟。因此，纯ALOHA 的延迟比较小。

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 µsec. What is the approximate total channel load?

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

A large population of ALOHA users manages to generate 50 requests/sec, including both originals and retransmissions. Time is slotted in units of 40 msec.
A. What is the chance of success on the first attempt?
B. What is the probability of exactly k collisions and then a success?
C. What is the expected number of transmission attempts needed?

答：
A. 在任一帧时间内生成k 帧的概率服从泊松分布

生成0 帧的概率为 对于纯的ALOHA，发送一帧的冲突危险区为两个帧时，在两帧内无其他帧发送的概率是 对于分隙的ALOHA，由于冲突危险区减少为原来的一半，任一帧时内无其他帧发送的概率是。 现在时隙长度为40ms，即每秒25个时隙，产生50次请求， 所以每个时隙产生两个请求，G=2。因此， 首次尝试的成功率是：
B. .

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

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

Measurements of a slotted ALOHA channel with an infinite number of users show that 10 percent of the slots are idle. (a) What is the channel load, G? (b) What is the throughput? © Is the channel underloaded or overloaded?

答： （a）从泊松定律得到，因此 （b） S=2.3×0.1=0.23 （c）因为每当G>1 时，信道总是过载的，因此在这里信道是过载的。

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 (a) the basic bit-map protocol? (b) Mok and Ward's protocol with permuting virtual station numbers?

答： (a) 最糟糕的情况是，所有站点都想要发送并且s是编号最小的站点。 等待 N bit contention period + (N-1) d bit帧传输时间，总共是 N+(N-1) dbit times.
(b) 最糟糕的情况是，所有的站点都有帧要发送并且s是虚拟编号最小的站点。 轮到s传送是其他N-1个站点传送以后，并且竞争周期都是log2N，所以等待时间是(N-1)×d+N×log2N bits.

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 are needed to resolve the contention?

站点 2, 3, 5, 7, 11, 和 13 想要发送. 需要11个slot,内容如下：

slot 1: 2, 3, 5, 7, 11, 13
slot 2: 2, 3, 5, 7
slot 3: 2, 3
slot 4: 2
slot 5: 3
slot 6: 5, 7
slot 7: 5
slot 8: 7
slot 9: 11, 13
slot 10: 11
slot 11: 13

答：在自适应树遍历协议中，可以把站点组织成二叉树（见图）的形式。在一次成功的传输之后，在第一个竞争时隙中，全部站都可以试图获得信道，如果仅其中之一需用信道，则发送冲突，则第二时隙内只有那些位于节点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

Six stations, A through F, communicate using the MACA protocol. Is it possible that two transmissions take place simultaneously? Explain your answer.

答：Yes. Imagine that they are in a straight line and that each station can reach only its nearest neighbors. Then A can send to B while E is sending to F.

可能，假设他们在直线上，两个不相邻的站点向相邻的下个站点传输

Consider building a CSMA/CD network running at 1 Gbps over a 1-km cable with no repeaters. The signal speed in the cable is 200,000 km/sec. What is the minimum frame size?

答：对于1km 电缆，单程传播时间为1/200000=5×10-6 s，即5，来回路程传播时间为2t =10。为了能够按照CSMA/CD 工作，最小帧的发射时间不能小于10。以1Gb/s 速率工作，10可以发送的比特数等于：

因此，最小帧是10 000 bit 或1250 字节长。

An IP packet to be transmitted by Ethernet is 60 bytes long, including all its headers. If LLC is not in use, is padding needed in the Ethernet frame, and if so, how many bytes?

The minimum Ethernet frame is 64 bytes, including both addresses in the Ethernet frame header, the type/length field, and the checksum. Since the header fields occupy 18 bytes and the packet is 60 bytes, the total frame size is 78 bytes, which exceeds the 64-byte minimum. Therefore, no padding is used.

最小的以太网帧是64byte，包括帧头内的双方地址，类型/长度位，和校验位。 头部占18个byte且包是60个byte，整个帧长度是78byte，超过了最小64位的长度，所以不需要

Ethernet frames must be at least 64 bytes long to ensure that the transmitter is still going in the event of a collision at the far end of the cable. Fast Ethernet has the same 64-byte minimum frame size but can get the bits out ten times faster. How is it possible to maintain the same minimum frame size?

答：The maximum wire length in fast Ethernet is 1/10 as long as in Ethernet.

Some books quote the maximum size of an Ethernet frame as 1518 bytes instead of 1500 bytes. Are they wrong? Explain your answer.

答：The payload is 1500 bytes, but when the destination address, source address, type/length, and checksum fields are counted too, the total is indeed 1518.

Consider the interconnected LANs showns in Fig. 4-44. Assume that hosts a and b are on LAN 1, c is on LAN 2, and d is on LAN 8. Initially, hash tables in all bridges are empty and the spanning tree shown in Fig 4-44(b) is used. Show how the hash tables of different bridges change after each of the following events happen in sequence, first (a) then (b) and so on. (a) a sends to d. (b) c sends to a. © d sends to c. (d) d moves to LAN 6. (e) d sends to a.

The first frame will be forwarded by every bridge. After this transmission, each bridge will have an entry for destination a with appropriate port in its hash table. For example, D’s hash table will now have an entry to forward frames destined to a on LAN 2. The second message will be seen by bridges B, D, and A. These bridges will append a new entry in their hash table for frames destined for c. For example bridge D’s hash table will now have another entry to forward frames destined to c on LAN 2. The third message will be seen by bridges H, D, A, and B. These bridges will append a new entry in their hash table for frames destined for d. The fifth message will be seen by bridges E, C, B, D, and A. Bridges E and C will append a new entry in their hash table for frames destined for d, while bridges D, B, and A will update their hash table entry for destination d.

One consequence of using a spanning tree to forward frames in an extended LAN is that some bridges may not participate at all in forwarding frames. Identify three such bridges in Fig. 4-44. Is there any reason for keeping these bridges, even though they are not used for forwarding?

答：Bridges G, I and J are not used for forwarding any frames. The main reason for having loops in an extended LAN is to increase reliability. If any bridge in the current spanning tree fails, the (dynamic) spanning tree algorithm reconfigures the spanning tree into a new one that may include one or more of these bridges that were not a part of the previous spanning tree.

Briefly describe the difference between store-and-forward and cut-through switches.

答：A store-and-forward switch stores each incoming frame in its entirety, then examines it and forwards it. A cut-through switch starts to forward incoming frames before they have arrived completely. As soon as the destination address is in, the forwarding can begin.

Store-and-forward switches have an advantage over cut-through switches with respect to damaged frames. Explain what it is.

答：Store-and-forward switches store entire frames before forwarding them. After a frame comes in, the checksum can be verified. If the frame is damaged, it is discarded immediately. With cut=through, damaged frames cannot be discarded by the switch because by the time the error is detected, the frame is already gone. Trying to deal with the problem is like locking the barn door after the horse has escaped.

give two example computer applications for which connection-oriented service is appropriate. Now give two examples for which connectionless service is best.

答：文件传送、远程登录和视频点播需要面向连接的服务。另一方面，信用卡验证和其他的销售点终端、电子资金转移，以及许多形式的远程数据库访问生来具有无连接的性质，在一个方向上传送查询，在另一个方向上返回应答。

Are there any circumstances when connection-oriented service will (or at least should) deliver packets out of order? Explain.

答：有。中断信号应该跳过在它前面的数据，进行不遵从顺序的投递。典型的例子是当一个终端用户键入退出（或kill）健时。由退出信号产生的分组应该立即发送，并且应该跳过当前队列中排在前面等待程序处理的任何数据（即已经键入但尚未被程序读取的数据）

Datagram subnets route each packet as a separate unit, independent of all others. Virtual-circuit subnets do not have to do this, since each data packet follows a predetermined route. Does this observation mean that virtual-circuit subnets do not need the capability to route isolated packets from an arbitrary source to an arbitrary destination? Explain your answer.

答：不对。为了从任意源到任意目的地，为连接建立的分组选择路由，虚电路网络肯定需要这一能力。

Consider the following design problem concerning implementation of virtual-circuit service. If virtual circuits are used internal to the subnet, each data packet must have a 3-byte header and each router must tie up 8 bytes of storage for circuit identification. If datagrams are used internally, 15-byte headers are needed but no router table space is required. Transmission capacity costs 1 cent per 106 bytes, per hop. Very fast router memory can be purchased for 1 cent per byte and is depreciated over two years, assuming a 40-hour business week. The statistically average session runs for 1000 sec, in which time 200 packets are transmitted. The mean packet requires four hops. Which implementation is cheaper, and by how much?

答：虚电路实现需要在1000 秒内固定分配5*8=40 字节的存储器。数据报实现需要比虚电路实现多传送的头信息的容量等于(15-3 ) ×4×200＝9600字节-跳段。现在的问题就变成了40000 字节-秒的存储器对比9600 字节-跳段的电路容量。如果存储器的使用期为两年，即秒，一个字节-秒的代价为分，那么40000字节-秒的代价为2.7毫分。另一方面，1个字节-跳段代价是分，9600个字节-跳段的代价为分，即9.6毫分，即在这1000秒内的时间内便宜大约6.9毫分。

Assuming that all routers and hosts are working properly and that all software in both is free of all errors, is there any chance, however small, that a packet will be delivered to the wrong destination?

答：有可能。大的突发噪声可能破坏分组。使用k 位的检验和，差错仍然有2k的概率被漏检。如果分组的目的地段或虚电路号码被改变，分组将会被投递到错误的目的地，并可能被接收为正确的分组。换句话说，偶然的突发噪声可能把送往一个目的地的完全合法的分组改变成送往另一个目的地的也是完全合法的分组。

Consider the network of Fig. 5-7, but ignore the weights on the lines. Suppose that it uses flooding as the routing algorithm. If a packet sent by A to D has a maximum hop count of 3, list all the routes it will take. Also tell how many hops worth of bandwidth it consumes.

答：It will follow all of the following routes: ABCD, ABCF, ABEF, ABEG, AGHD, AGHF, AGEB, and AGEF. The number of hops used is 24.

Consider the subnet of Fig. 5-13(a). Distance vector routing is used, and the following vectors have just come in to router C: from B: (5, 0, 8, 12, 6, 2); from D: (16, 12, 6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The measured delays to B, D, and E, are 6, 3, and 5, respectively. What is C's new routing table? Give both the outgoing line to use and the expected delay.

答：
通过B 给出（11，6，14，18，12，8）
通过D 给出（19，15，9，3，12，13）
通过E 给出（12，11，8，14，5，9）
取到达每一目的地的最小值（C 除外）得到：（11，6，0，3，5，8）
输出线路是：（B，B，-，D，E，B）

If delays are recorded as 8-bit numbers in a 50-router network, and delay vectors are exchanged twice a second, how much bandwidth per (full-duplex) line is chewed up by the distributed routing algorithm? Assume that each router has three lines to other routers.

答：路由表的长度等于8*50=400bit。该表每秒钟在每条线路上发送2 次，因此400*2=800b/s，即在每条线路的每个方向上消耗的带宽都是800 bps。

For hierarchical routing with 4800 routers, what region and cluster sizes should be chosen to minimize the size of the routing table for a three-layer hierarchy? A good starting place is the hypothesis that a solution with k clusters of k regions of k routers is close to optimal, which means that k is about the cube root of 4800 (around 16). Use trial and error to check out combinations where all three parameters are in the general vicinity of 16.

对4800个路由器进行分级路由，若采用三级分级结构，则应选择多大的区和簇才能减小路由表的长度？最小的路由表长度可能是多少？ 答：所谓分级路由，就是将路由器按区（REGION）进行划分，每个路由器只须知道在自己的区内如何为分组选择路由到达目的地的细节，而不用知道其他区的内部结构。对于大的网络，也许两级结构是不够的，还可以把区组合成簇（CLUSTER），把簇再组合成域（ZONE），⋯⋯对于等级式路由，在路由表中对应所有的本地路由器都有一个登录项，所有其他的区（本簇内）、簇（本域内）和域都缩减为单个路由器，因此减少了路由表的尺寸。 在本题中，4800=15*16*20。当选择15 个簇、16 个区，每个区20 个路由器时（或等效形式，例如20 个簇、16 个区，每个区15 个路由器），路由表尺寸最小，此时的路由表尺寸为15+16+20=51。

Looking at the subnet of Fig. 5-6, how many packets are generated by a broadcast from B, using (a) reverse path forwarding? (b) the sink tree?

答：在一个子网中，从所有的源到一个指定的目的地的最佳路由的集合形成一棵以该目的地为根的树。这样的树就称作汇集树。汇集树不必是唯一的，其他具有相同通路长度的树可能存在。所有路由选择算法的目标都是要为所有的路由器寻找和使用汇集树。在广播形式的应用中，源主机需要向所有其他的主机发送报文。在称为反向通路转发的广播路由选 韶关学院信息工程学院 骆耀祖 择中，当广播分组到达路由器时，路由器对此分组进行检查，查看该分组是否来自于通常用于发送分组到广播源的线路，如果是，则此广播分组本身非常有可能是从源路由器来的第一个拷贝。 在这种情况下，路由器将此分组复制转发到进入线路以外的所有线路。然而，如果广播分组到来的线路不是到达源端的线路，那么分组就被当作副本而扔掉。 （1）反向通路转发算法，算法进行到5 个跳段后结束，总共产生28 个分组。 （2）使用汇集树算法，需要4 个跳段，总共产生14 个分组。

Consider the network of Fig. 5-16(a). Imagine that one new line is added, between F and G, but the sink tree of Fig. 5-16(b) remains unchanged. What changes occur to Fig. 5-16©?

答：Node F currently has two descendants, A and D. It now acquires a third one, G, not circled because the packet that follows IFG is not on the sink tree. Node G acquires a second descendant, in addition to D, labeled F. This, too, is not circled as it does not come in on the sink tree.

As a possible congestion control mechanism in a subnet using virtual circuits internally, a router could refrain from acknowledging a received packet until (1) it knows its last transmission along the virtual circuit was received successfully and (2) it has a free buffer. For simplicity, assume that the routers use a stop-and-wait protocol and that each virtual circuit has one buffer dedicated to it for each direction of traffic. If it takes T sec to transmit a packet (data or acknowledgement) and there are n routers on the path, what is the rate at which packets are delivered to the destination host? Assume that transmission errors are rare and that the host-router connection is infinitely fast.

答：
对时间以T秒为单位分时隙。在时隙中，源路由器发送第一个分组。
在时隙2的开始，第2个路由器收到了分组，但不能应答。
在时隙3的开始，第3个路由器收到了分组，但也不能应答。
这样，此后所有的路由器都不会应答。仅当目的地主机从目的地路由器取得分组时才会发送第1个应答。
现在确认应答开始往回传播。在源路由器可以发送第2个分组之前，需要两次穿行该子网，需要花费的时间等于2(n-1)T 秒/分组，显然，这种协议的效率是很低的。

A datagram subnet allows routers to drop packets whenever they need to. The probability of a router discarding a packet is p. Consider the case of a source host connected to the source router, which is connected to the destination router, and then to the destination host. If either of the routers discards a packet, the source host eventually times out and tries again. If both host-router and router-router lines are counted as hops, what is the mean number of (a) hops a packet makes per transmission? (b) transmissions a packet makes? © hops required per received packet?

答：
（1）由源主机发送的每个分组可能行走1 个跳段、2 个跳段或3 个跳段。走1 个跳段的概率为p ，走2 个跳段的概率为（1-p）p ，走3 个跳段的概率为。那么，一个分组平均通路长度的期望值为：
（2）一次发送成功（走完整个通路）的概率为，令，两次发射成功的概率等于(1-a) a，三次发射成功的概率等于 ，…，因此一个分组平均发送次数为：

即一个分组平均要发送次。
（3）最后，每一个接收到的分组行走的平均跳段数等于

Describe two major differences between the warning bit method and the RED method.

答：First, the warning bit method explicitly sends a congestion notification to the source by setting a bit, whereas RED implicitly notifies the source by simply dropping one of its packets. Second, the warning bit method drops a packet only when there is no buffer space left, whereas RED drops packets before all the buffer are exhausted.

Give an argument why the leaky bucket algorithm should allow just one packet per tick, independent of how large the packet is. 请说明漏桶算法为什么每个滴答时间允许一个分组进入网络，而不考虑分组的大小。

答：原始漏桶算法很简单。漏桶由一个有限队列构成。当分组到达时，如果队列未满，将其加到队尾；否则丢弃它。每个时钟节拍发送一个分组（除非队列为空）。 通常计算机能够以很高的速率产生数据，网络也可以用同样的速率运行。然而，路由器却只能在短时间内以同样高的速率处理数据。对于排在队列中的一个分组，不管它有多大，路由器必须做大约相同分量的工作。显然，处理10 个100 字节长的分组所作的工作比处理1 个1000 字节长的分组要做的工作多得多。

The byte-counting variant of the leaky bucket algorithm is used in a particular system. The rule is that one 1024-byte packet, or two 512-byte packets, etc., may be sent on each tick. Give a serious restriction of this system that was not mentioned in the text.

答：不可以发送任何大于1024 字节的分组。

A computer on a 6-Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 1 Mbps. It is initially filled to capacity with 8 megabits. How long can the computer transmit at the full 6 Mbps?

答：在一个6Mbps网络上的一台计算机受到令牌漏桶的交通管制。假定令牌填入速率为1Mbps，开始时漏桶装填的容量是8M位。那么，计算机可以用完全速率6Mbps发送多长时间？ 答：本题乍看起来，似乎以6Mb/s 速率发送用4/3 秒的时间可以发送完桶内8Mb 的数据，使漏桶变空。然而，这样回答是错误的，因为在这期间，已有更多的令牌到达。正确的答案应该使用公式S＝ C/(M-P)，这里的S表示以秒计量的突发时间长度，M表示以每秒字节计量的最大输出速率，C表示以字节计的桶的容量，P表示以每秒字节计量的令牌到达速率。则： S=8/(6-1)=1.6 因此，计算机可以用完全速率6Mb/s发送1.6s的时间。

Imagine a flow specification that has a maximum packet size of 1000 bytes, a token bucket rate of 10 million bytes/sec, a token bucket size of 1 million bytes, and a maximum transmission rate of 50 million bytes/sec. How long can a burst at maximum speed last?

答：令最大突发时间长度为? t 秒，在极端情况下，漏桶在突发期间的开始是充满的（1MB），在突发期间另有10? t MB 进入桶内。在传输突发期间的输出包含50? t MB。由等式1+10? t=50? t，得到? t=1/40s，即25ms。因此，以最大速率突发传送可维持25ms 的时间。

Consider the user of differentiated services with expedited forwarding. Is there a guarantee that expedited packets experience a shorter delay than regular packets? Why or why not?

答：There is no guarantee. If too many packets are expedited, their channel may have even worse performance than the regular channel.

Is fragmentation needed in concatenated virtual-circuit internets or only in datagram systems? 答：在这两种情况下都需要分割功能。即使在一个串接的虚电路网络中，沿通路的某些网络可能接受1024 字节分组，而另一些网络可能仅接受48字节分组，分割功能仍然是需要的。

Suppose that host A is connected to a router R 1, R 1 is connected to another router, R 2, and R 2 is connected to host B. Suppose that a TCP message that contains 900 bytes of data and 20 bytes of TCP header is passed to the IP code at host A for delivery to B. Show the Total length, Identification, DF, MF, and Fragment offset fields of the IP header in each packet transmitted over the three links. Assume that link A-R1 can support a maximum frame size of 1024 bytes including a 14-byte frame header, link R1-R2 can support a maximum frame size of 512 bytes, including an 8-byte frame header, and link R2-B can support a maximum frame size of 512 bytes including a 12-byte frame header.

答：The initial IP datagram will be fragmented into two IP datagrams at I1. No other fragmentation will occur. Link A-R1: Length = 940; ID = x; DF = 0; MF = 0; Offset = 0 Link R1-R2: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60 Link R2-B: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60

In our example transport primitives of Fig. 6-2, LISTEN is a blocking call. Is this strictly necessary? If not, explain how a nonblocking primitive could be used. What advantage would this have over the scheme described in the text?

答：不是。事实上，LISTEN 调用可以表明建立新连接的意愿，但不封锁。当有了建立连接的尝试时，调用程序可以被提供一个信号。然后，它执行，比如说，OK 或REJECT 来接受或拒绝连接。然而，在原先的封锁性方案中，就缺乏这种灵活性。

In the model underlying Fig. 6-4, it is assumed that packets may be lost by the network layer and thus must be individually acknowledged. Suppose that the network layer is 100 percent reliable and never loses packets. What changes, if any, are needed to Fig. 6-4?

答：从“被动连接建立在进行中”到“已建立”的虚线不再依确认的传输情况而定。该变迁可立即发生。实质上，“被动连接建立在进行中”状态已经消失，因为它们什么时候都不可见。

Suppose that the clock-driven scheme for generating initial sequence numbers is used with a 15-bit wide clock counter. The clock ticks once every 100 msec, and the maximum packet lifetime is 60 sec. How often need resynchronization take place (a) in the worst case? (b) when the data consumes 240 sequence numbers/min?

答：在具体解答这个问题之前，需要先熟悉一下时钟驱动方案的内容。首先我们引入参数T，假定在发送出一个分组之后等待长度等于T 的时间，我们就可以肯定，所有关于该分组的踪迹都已消失，不管是该分组本身，还是对于它的确认都不会再以外的出现。我们还假定，每个主机都配有一个表示一天的时间的时钟，不同主机上的时钟不必同步。每个时钟都采用二进制计数器的形式，并且以长度一致的间隔时间递增。而且，计数器的比特数必须等于或超过序列号所使用的比特数。最后一点，时钟被假定是连续运行，即使主机关闭时也不间断。 时钟驱动方案的基本思想是同一时间不会有两个活动的TPDUs 使用相同的序列号。在一条连接建立的时候，时钟的低端k 个比特被用作初始序列号（也是k 位）。因此，每条连接可以从不同的序列号开始为TPDU 编号。序列号空间应该足够大，使得当编号循环一周时，具有相同号码的旧的TPDU 已经不复存在。 当主机系统崩溃时会产生一些问题。在重新启动后，主机的传输层实体不知道它曾经处在序列号空间的什么位置。一种解决方法是要求传输实体在恢复后的T 秒内处于空闲状态，让所有老的TPDUs 都消失。然而，在一个复杂的互联网上，T 值可能很大，所以这不是一个好的解决方法。 为了避免从崩溃恢复后的T 秒不工作状态，需要对序列号的使用施加新的限制。在一些编号可能被用作初始序列号之前，必须在长度为T 的时间内禁止使用这些编号。在任何连接上发送TPDU 之前，传输层实体必须读一次时钟，检查该TPDU 的编号是否在禁止区内。 显然，在任何连接上的最大数据率是每个时钟滴答发送一个TPDU。在系统崩溃后重启动时，在打开一条新的连接之前，传输实体必须等待到下一个时钟滴答，以避免同样的号码重复使用。如果数据速率低于始终速率，实际使用的序列号对于时间的曲线将最终从左边进入禁止区。如果这样的情况发生了，要么延迟TPDU 达T 长度时间，或者重新同步序列号。 作为例子，如果在坐标起点发1 号TPDU，到接近时钟大循环编码的末尾才发送第2 个TPDU，此时为避免在下一大循环开始重复使用序列号，就需要在大循环接近末尾处重新同步，使用大的初始序列号，以避免使用禁止区号码。 （a） 时钟大循环周期是215，即32768 滴答，每滴答100ms，即0.1 秒，所以大循环周期是3276.8s 。假定数据产生速率非常低（接近零），那么发送方在3276.8-60=3216.8 秒时进入禁止区，需要进行一次重新同步。 （b） 每分钟使用240 个序列号，即每秒使用4 个号码，如果时间以t 表示（以秒为单位），那么实际的序列号是4t。当接近大循环的末尾时以及在下一大循环的开始阶段，4t 有一定的大小，位于禁止区的上方，现在由于每秒钟10个滴答，禁止区的左边是10(t-3216.8)。令t =10(t-3216.8)，得t=5316.3秒。即当 t=5316.3时，开始进入禁止区，因此当 t=5316.3时需要进行一次重新同步。

Why does the maximum packet lifetime, T, have to be large enough to ensure that not only the packet but also its acknowledgements have vanished?

答：首先看三次握手过程是如何解决延迟的重复到达的分组所引起的问题的。 正常情况下，当主机1 发出连接请求时，主机1 选择一个序号x，并向主机2 发送一个包含该序号的请求TPDU；接着，主机2 回应一个接受连接的TPDU，确认x，并声明自己所选用的初始序列号y；最后，主机1 在其发送的第一个数据TPDU 中确认主机2 所选择的初始序列号。 当出现延迟的重复的控制TPDU 时，一个TPDU 是来自于一个已经释放的连接的延迟重复的连接请求（ CONNECTION REQUEST），该TPDU 在主机1 毫不知情的情况下到达主机2。 主机2 通过向主机1 发送一个接受连接的TPDU（CONNECTION ACCEPTED）来响应该TPDU，而该接受连接的TPDU 的真正目的是证实主机1 确实试图建立一个新的连接。在这一点上，关键在于主机2 建议使用y 作为从主机2 到主机1 交通的初始序列号，从而说明已经不存在包含序列号为y 的TPDU，也不存在对y 的应答分组。当第二个延迟的TPDU 到达主机2 时，z 被确认而不是y 被确认的事实告诉主机2 这是一个旧的重复的TPDU，因此废止该连接过程。在这里。三次握手协议是成功的。 最坏的情况是延迟的“连接请求”和对“连接被接收”的确认应答都在网络上存活。可以设想，当第2 个重复分组到达时，如果在网上还存在一个老的对序列号为y 的分组的确认应答，显然会破坏三次握手协议的正常工作，故障性的产生一条没有人真正需要的连接，从而导致灾难性的后果。

Imagine that a two-way handshake rather than a three-way handshake were used to set up connections. In other words, the third message was not required. Are deadlocks now possible? Give an example or show that none exist.

假定TCP使用两次握手替代三次握手来建立连接。也就是说，不需要第三个报文。那么现在是否可能产生死锁？请给出例子来说明你的答案。 答：我们知道，3 次握手完成两个重要功能，既要双方做好发送数据的准备工作（双方都知道彼此已准备好），也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送与确认。 现在把三次握手改成仅需要两次握手，死锁是可能发生的。作为例子。考虑计算机A和B 之间的通信。假定B 给A 发送一个连接请求分组，A 收到了这个分组，并发送了确认应答分组。按照两次握手的协定，A 认为连接已经成功的建立了，可以开始发送数据分组。 可是，B 在A 的应答分组在传输中被丢失的情况下，将不知道A 是否已经准备好，不知道A 建议什么样的序列号用于A 到B 的交通，也不知道A 是否同意A 所建议的用于B到A交通的初始序列号，B 甚至怀疑A 是否收到自己的连接请求分组。在这种情况下，B 认为连接还未建立成功，将忽略A 发来的任何数据分组，只等待接收连接确认应答分组。而A在发出的分组超时后，重复发送同样的分组。这样就形成了死锁。

Imagine a generalized n-army problem, in which the agreement of any two of the blue armies is sufficient for victory. Does a protocol exist that allows blue to win?

答：（a）参见教材。 （b）不存在。对于多于两支部队的情况，问题在实质上是同样的。

Consider the problem of recovering from host crashes (i.e., Fig. 6-18). If the interval between writing and sending an acknowledgement, or vice versa, can be made relatively small, what are the two best sender-receiver strategies for minimizing the chance of a protocol failure?

答：在解答本题前，让我们先考察主机从崩溃恢复所带来的问题。我们总是希望，在服务器崩溃随后又很快重新引导的情况下，客户机能够继续工作。为了说明这一问题的难度，我们假定一个客户主机发送一个长文件给另一个服务器主机，并且使用简单的停-等协议。在服务器上的传输层只是简单的把接收到的TPDU 一个一个的递交给传输用户。假定在文件传输的过程中，服务器崩溃了。当服务器恢复的时候，它的表被重新初始化，因此再也不知道崩溃前文件传送到什么地方了。 在试图恢复先前状态的过程中，服务器可能发送一个广播到所有其他主机，宣布自己刚刚发生了一次崩溃，请求客户告知所有打开的连接的状态。此时。每个客户机都可能处于二中选一的状态：有一个悬而未决的TPDU 的S1 状态，或者没有未确认应到的TPDU 的S0 状态。 可以想到的一种解决方案是基于这一状态信息，客户机决定是否要重复发最近的一个TPDU。 乍看起来，这一解决方案似乎能解决问题，可是深入仔细的分析一下，困难仍然很大。作为示例，假定服务器的传输层实体先发送ACK，在ACK 被发出之后，再执行把收到的TPDU写到应用进程的操作。把TPDU 写到输出设备和发送ACK 是两个不同的事件，不能同时进行。如果服务器主机的崩溃刚好发生在应答被发送之后，并且是在写操作之前，那么客户机将接收到确认应答，当崩溃恢复到达时会处于状态S0。因此，客户机不会重传TPDU，错误的认为服务器成功的接收到并存放好了它最后一次发送的TPDU。实际的情况并非如此，从而结果是丢失了最后一个TPDU。 到此，你也许认为：“这个问题容易解决，只要你重新编写程序，让传输实体先执行写操作然后再发送ACK就可以了。”可是，写操作尽管成功了，但崩溃可能发生在发送出ACK之前。此时客户机将会处于状态S1，因而重新发送，导致对服务器的应用进程的输出中产生未检测到的重复TPDU。 如图6-18 所示，服务器可以选择两种方式中的一种：先确认应答，或者先执行写操作。客户机可以选择4 种方式中的一种：总是重传最后一个TPDU，永不重传最后一个TPDU，仅在S0 状态时重传，或者仅在S1 状态时重传。这样就存在8 种可能的组合，但可以看出，对于每一种组合，都有一些事件会使协议的运行失败。 在服务器方可能发生3 种事件：发送一个ACK（A），对输出进程的写操作（W）和系统崩溃（C）。3 种事件可能以6 种不同的次序发生：AC（W），AWC，C（AW），C（WA），WAC和WC（A），这里的圆括号表示，在系统崩溃C 后，A 和W 事件就不可能了。图6-18 示出了客户机和服务器的策略的所有8 种组合，以及对于每一种组合的有效事件序列。值得注意的是，对于每一种策略都存在某些事件会引起协议失败。例如，如果客户机选择总是重发送，AWC 事件将产生检测不出来的收到重复分组的错误。尽管对于C（AW）和C（WA）该协议都工作的很好。 现在回到本题的答案。如果AW 或WA 间隔时间很短，事件AC（W）和W（CA）就不太可能发生。此时的最好发送方策略是，如果崩溃恢复时处于状态S1，应该重传最后一个TPDU，接收方采用顺序AW 或WA 则无关紧要。

Are deadlocks possible with the transport entity described in the text (Fig. 6-20)?

答：该传输实体有可能死锁。当双方同时执行RECEIVE 时就会进入死锁状态。

Out of curiosity, the implementer of the transport entity of Fig. 6-20 has decided to put counters inside the sleep procedure to collect statistics about the conn array. Among these are the number of connections in each of the seven possible states, ni (i = 1, … ,7). After writing a massive FORTRAN program to analyze the data, our implementer discovers that the relation Sni = MAX_CONN appears to always be true. Are there any other invariants involving only these seven variables?

答：有， n2+n3+n6+n7=1 因为状态listening（n2）、waiting（n3）、sending（n6）和receiving（n7）都意味着用户被封锁，因此当处在其中的一个状态时，就不可能是在另一个状态。

What happens when the user of the transport entity given in Fig. 6-20 sends a zero-length message? Discuss the significance of your answer.

答：长度为零的报文被另一边接收。这种报文的发送可以被用来表示文件结束的信号。

For each event that can potentially occur in the transport entity of Fig. 6-20, tell whether it is legal when the user is sleeping in sending state.

答：因为文件处于封锁状态，所有的传输层原语都不可能执行。因此，仅分组到达事件是可能的，而且还不是所有的到达事件。事实上，仅仅跟呼叫请求、清除请求、数据分组和信用量分组这几个分组到达有关的事件是合法的。

Discuss the advantages and disadvantages of credits versus sliding window protocols.

答：滑动窗口协议比较简单，仅需要管理窗口边缘一组参数，而且，对于到达顺序有错的TPDU 不会引起窗口增加和减少方面的问题。然而，信用量方案比较灵活，允许独立于确认，动态的管理缓冲区。

Why does UDP exist? Would it not have been enough to just let user processes send raw IP packets?

答：仅仅使用IP 分组还不够。IP 分组包含IP 地址，该地址指定一个目的地机器。一旦这样的分组到达了目的地机器，网络控制程序如何知道该把它交给哪个进程呢？UDP 分组包含一个目的地端口，这一信息是必须的，因为有了它，分组才能够被投递给正确的进程。

Consider a simple application-level protocol built on top of UDP that allows a client to retrieve a file from a remote server residing at a well-known address. The client first sends a request with file name, and the server responds with a sequence of data packets containing different parts of the requested file. To ensure reliability and sequenced delivery, client and server use a stop-and-wait protocol. Ignoring the obvious performance issue, do you see a problem with this protocol? Think carefully about the possibility of processes crashing.

It is possible that a client may get the wrong file. Suppose client A sends a request for file f1 and then crashes. Another client B then uses the same protocol to request another file f2. Suppose client B, running on the same machine as A (with same IP address), binds its UDP socket to the same port that A was using earlier. Furthermore, suppose B’s request is lost. When the server’s reply (to A’s request) arrives, client B will receive it and assume that it is a reply its own request.

Both UDP and TCP use port numbers to identify the destination entity when delivering a message. Give two reasons for why these protocols invented a new abstract ID (port numbers), instead of using process IDs, which already existed when these protocols were designed.

答：Here are three reasons. First, process IDs are OS-specific. Using process Ids would have made these protocols OS-dependent. Second, a single process may establish multiple channels of communications. A single process ID (per process) as the destination identifier cannot be used to distinguish between these channels. Third, having processes listen on well-known ports is easy, but well-known process IDs are impossible.

What is the total size of the minimum TCP MTU, including TCP and IP overhead but not including data link layer overhead?

答：默认段长为536字节，TCP和IP各增加20字节，使得默认总段长为576 字节。

Datagram fragmentation and reassembly are handled by IP and are invisible to TCP. Does this mean that TCP does not have to worry about data arriving in the wrong order?

数据报的分片和重组由IP控制，并且对于TCP不可见。这是不是意味着TCP不必担心到达数据的失序问题？ 答：尽管到达的每个数据报都是完整的，但可能到达的数据报的顺序是错误的，因此，TCP必须准备适当的重组报文的各个部分。

A process on host 1 has been assigned port p, and a process on host 2 has been assigned port q. Is it possible for there to be two or more TCP connections between these two ports at the same time?

答：不可以。一条连接仅仅用它的套接口标识。因此，（1，p）-（2，q）是在这两个端口之间唯一可能的连接。

Many business computers have three distinct and worldwide unique identifiers. What are they?

许多商用计算机有3个不同的全球唯一标识符，它们是什么？

答：它们是：域名（DNS name）、IP地址和物理地址（例如：以太网地址Ethernet address）。

According to the information given in Fig. 7-3, is little-sister.cs.vu.nl on a class A, B, or C network?

答：Its IP address starts with 130, so it is on a class B network. See Chap. 5 for the IP address mapping.

DNS uses UDP instead of TCP. If a DNS packet is lost, there is no automatic recovery. Does this cause a problem, and if so, how is it solved?

答：DNS is idempotent. Operations can be repeated without harm. When a process makes a DNS request, it starts a timer. If the timer expires, it just makes the request again. No harm is done.

In addition to being subject to loss, UDP packets have a maximum length, potentially as low as 576 bytes. What happens when a DNS name to be looked up exceeds this length? Can it be sent in two packets?

答：The problem does not occur. DNS names must be shorter than 256 bytes. The standard requires this. Thus, all DNS names fit in a single minimumlength packet.

Can a machine with a single DNS name have multiple IP addresses? How could this occur?

答：Yes. In fact, in Fig. 7-3 we see an example of a duplicate IP address. Remember that an IP address consists of a network number and a host number. If a machine has two Ethernet cards, it can be on two separate networks, and if so, it needs two IP addresses.

Can a computer have two DNS names that fall in different top-level domains? If so, give a plausible example. If not, explain why not.

答：It is possible. www.large-bank.com and www.large-bank.ny.us could have the same IP address. Thus, an entry under com and under one of the country domains is certainly possible (and common).

The number of companies with a Web site has grown explosively in recent years. As a result, thousands of companies are registered in the com domain, causing a heavy load on the top-level server for this domain. Suggest a way to alleviate this problem without changing the naming scheme (i.e., without introducing new top-level domain names). It is permitted that your solution requires changes to the client code.

答：There are obviously many approaches. One is to turn the top-level server into a server farm. Another is to have 26 separate servers, one for names beginning with a, one for b, and so on. For some period of time (say, 3 years) after introducing the new servers, the old one could continue to operate to give people a chance to adapt their software.

Some e-mail systems support a header field Content Return:. It specifies whether the body of a message is to be returned in the event of nondelivery. Does this field belong to the envelope or to the header?

答：It belongs to the envelope because the delivery system needs to know its value to handle e-mail that cannot be delivered.

Electronic mail systems need directories so people's e-mail addresses can be looked up. To build such directories, names should be broken up into standard components (e.g., first name, last name) to make searching possible. Discuss some problems that must be solved for a worldwide standard to be acceptable.

答：This is much more complicated than you might think. To start with, about half the world writes the given names first, followed by the family name, and the other half (e.g., China and Japan) do it the other way. A naming system would have to distinguish an arbitrary number of given names, plus a family name, although the latter might have several parts, as in John von Neumann. Then there are people who have a middle initial, but no middle name. Various titles, such as Mr., Miss, Mrs., Ms., Dr., Prof., or Lord, can prefix the name. People come in generations, so Jr., Sr., III, IV, and so on have to be included. Some people use their academic titles in their names, so we need B.A., B.Sc., M.A., M.Sc., Ph.D., and other degrees. Finally, there are people who include certain awards and honors in their name. A Fellow of the Royal Society in England might append FRS, for example. By now we should be able to please even the learned: Prof. Dr. Abigail Barbara Cynthia Doris E. de Vries III, Ph.D., FRS

A multithreaded Web server is organized as shown in Fig. 7-21. It takes 500 µsec to accept a request and check the cache. Half the time the file is found in the cache and returned immediately. The other half of the time the module has to block for 9 msec while its disk request is queued and processed. How many modules should the server have to keep the CPU busy all the time (assuming the disk is not a bottleneck)?

答：If a module gets two requests, one will be a cache hit and one will be a cache miss on average. The total CPU time consumed is 1 msec, and the total wait time is 9 msec. This gives a 10% CPU utilization, so with 10 modules the CPU is kept busy.

The standard http URL assumes that the Web server is listening on port 80. However, it is possible for a Web server to listen to some other port. Devise a reasonable syntax for a URL accessing a file on a nonstandard port.

答：The official RFC 1738 way to do this is http://dns-name:port/file.

Although it was not mentioned in the text, an alternative form for a URL is to use the IP address instead of its DNS name. An example of using an IP address is http://192.31.231.66/index.html. How does the browser know whether the name following the scheme is a DNS name or an IP address?

答：DNS names may not end with a digit, so there is no ambiguity.