«计算机网络»笔记：第8章 作业

本章记录自己写的作业，不保证正确性，不喜欢参考答案写死！！！

没意思的题可能不做。

PS：题目排版非本人（捂脸）。

第一章作业

（英文版教材第一章 1、2、3、4、5、9、10,11,12,15,16,17,18,20,22,30,35）

\1. An alternative to a LAN is simply a big timesharing system with terminals for all users. Give two advantages of a client-server system using a LAN.

这是对比 LAN C/S 架构和时分复用架构。显然前者更好，原因随便两个：

1. 方便扩展软硬件。可以随时加入一台电脑。

2. 当用户数量很多的时候，时分复用会导致每个人可以操作的时间不足。

\2. The performance of a client-server system is strongly influenced by two major network characteristics: the bandwidth of the network (that is, how many bits/sec it can transport) and the latency (that is, 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 but also high latency. Then give an example of one that has both low bandwidth and low latency.

\3. 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 (i) digitized voice traffic? (ii) video traffic? (iii) financial transaction traffic?

\4. A factor in the delay of a store-and-forward packet-switching system is how long it takes to store and forward a packet through a switch. If switching time is 10 μsec, is this likely to be a major factor in the response of a client-server system where the client is in New York and the server is in California? Assume the propagation speed in copper and fiber to be 2/3 the speed of light in vacuum.

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

\9. A disadvantage of a broadcast subnet is the capacity wasted when multiple hosts attempt to access the channel at the same time. As a simplistic example, suppose that time is divided into discrete slots, with each of the n hosts attempting to use the channel with probability p during each slot. What fraction of the slots will be wasted due to collisions?

\10. What are two reasons for using layered protocols? What is one possible disadvantage of using layered protocols?

\11. What is the principle difference between connectionless communication and connection-oriented communication? Give one example of a protocol that uses

1. connectionless communication 2)connection-oriented communication.

\12. 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.

\15. In some networks, the data link layer handles transmission errors by requesting that damaged frames 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.

\16. Which of the OSI layers and TCP/IP layers handles each of the following:

1. Dividing the transmitted bit stream into frames

2. Determining which route through the subnet to use.

\17. If the unit exchanged at the data link level is called a frame and the unit exchanged at the network level is called a packet, do frames encapsulate packets or do packets encapsulate frames? Explain your answer.

\18. A system has an n-layer protocol hierarchy. Applications generate messages of length M bytes. At each of the layers, an h-byte header is added. What fraction of the network bandwidth is filled with headers?

\20. What is the main difference between TCP and UDP?

\22. 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.

\30. Suppose there is a change in the service (set of operations) provided by layer k. How does this impact services at layers k-1 and k+1?

\35. The ping program allows you to send a test packet to a given location and see how long it takes to get there and back. Try using ping to see how long it takes to get from your location to several known locations. From these data, plot the one-way transit time over the Internet as a function of distance. It is best to use universities since the location of their servers is known very accurately. For example, berkeley.edu is in Berkeley, California; mit.edu is in Cambridge, Massachusetts; vu.nl is in Amsterdam; The Netherlands; <www.usyd.edu.au> is in Sydney, Australia; and <www.uct.ac.za> is in Cape Town, South Africa.

第二章作业

（英文版教材第二章 2, 3, 4, 7, 8, 21, 24, 25, 26, 28, 35, 36, 37

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

\3. 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?

\4. What signal-to-noise ratio is needed to put a T1 carrier on a 100-kHz line?

\7. It is desired to send a sequence of computer screen images over an optical fiber. The screen is 1920 × 1200 pixels, each pixel being 24 bits. There are 50 screen images per second. How much bandwidth is needed?

\8. Is the Nyquist theorem true for high-quality single-mode optical fiber or only for copper wire?

\21. A modem constellation diagram similar to Fig. 2-23 has data points at (0, 1) and (0, 2). Does the modem use phase modulation or amplitude modulation?

\24. An ADSL system using DMT allocates 3/4 of the available data channels to the down-stream link. It uses QAM-64 modulation on each channel. What is the capacity of the downstream link?

\25. Ten signals, each requiring 4000 Hz, are multiplexed onto a single channel using FDM. What is the minimum bandwidth required for the multiplexed channel? Assume that the guard bands are 400 Hz wide.

\26. Why has the PCM sampling time been set at 125 μsec?

\28. Compare the maximum data rate of a noiseless 4-kHz channel using

(a) Analog encoding (e.g., QPSK) with 2 bits per sample.

(b) The T1 PCM system.

\35. 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?

36, Compare the delay in sending an x-bit* message over ak-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 isd* sec per hop, the packet size is p* bits, and the data rate isb* bps. Under what conditions does the packet network have a lower delay? Also, explain the conditions under which a packet-switched network is preferable to a circuit switched network.

\37. Suppose that x* bits of user data are to be transmitted over ak-hop* path in a packet switched network as a series of packets, each containing p* data bits andh* 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?

第三章作业

（英文版教材第三章 1、2、3、4、6、7、9、11、14、15、16, 补充题1，17, 18, 20, 27, 28, 29, 30, 31, 32, 33，补充题2-5

\1. An upper-layer packet is split into 10 frames, each of which has an 80% 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?

\2. The following data fragment occurs in the middle of a data stream for which the byte stuffing algorithm described in the text is used: A B ESC C ESC FLAG FLAG D. What is the output after stuffing?

\3. What is the maximum overhead in byte-stuffing algorithm?

\4. 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?

\6. To provide more reliability than a single parity bit can give, an error-detecting coding scheme uses one parity bit for checking all the odd-numbered bits and a second parity bit for all the even-numbered bits. What is the Hamming distance of this code?

\7. An 8-bit byte with binary value 10101111 is to be encoded using an even-parity Hamming code. What is the binary value after encoding?

\9. One way of detecting errors is to transmit data as a block of n rows of k bits per row and add parity bits to each row and each column. The bit in the lower-right corner is a parity bit that checks its row and its column. Will this scheme detect all single errors? Double errors? Triple errors? Show that this scheme cannot detect some four-bit errors.

\11. Suppose that data are transmitted in blocks of sizes 1000 bits. What is the maximum error rate under which error detection and retransmission mechanism (1 parity bit per block) is better than using Hamming code? Assume that bit errors are independent of one another and no bit error occurs during retransmission.

\14. What is the remainder obtained by dividing x 7 + x 5 + 1 by the generator polynomial x 3 + 1?

\15. A bit stream 10011101 is transmitted using the standard CRC method described in the text. The generator polynomial is x 3 + 1. Show the actual bit string transmitted. Suppose that the third bit from the left is inverted during transmission. Show that this error is detected at the receiver’s end. Give an example of bit errors in the bit string transmitted that will not be detected by the receiver.

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

补充题1：已知数据位流为1101 0110，采用CRC 校验，G(x)=x3+1，计算出校验位。

\17. In the discussion of ARQ protocol in Section 3.3.3, a scenario was outlined that resulted in the receiver accepting two copies of the same frame due to a loss of acknowledgement frame. Is it possible that a receiver may accept multiple copies of the same frame when none of the frames (message or acknowledgement) are lost?

\18. 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%?

\20. 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?

\27. Consider the operation of protocol 6 over a 1-Mbps perfect (i.e., error-free) line. The maximum frame size is 1000 bits. New packets are generated 1 second apart. The timeout interval is 10 msec. If the special acknowledgement timer were eliminated, unnecessary timeouts would occur. How many times would the average message be transmitted?

\28. 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?

\29. 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?

(c) Protocol 6?

\30. Consider an error-free 64-kbps satellite channel used to send 512-byte data frames in one direction, with very short acknowledgements coming back the other way. What is the maximum throughput for window sizes of 1, 7, 15, and 127? The earth-satellite propagation time is 270 msec.

\31. 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?

\32. Give at least one reason why PPP uses byte stuffing instead of bit stuffing to prevent accidental flag bytes within the payload from causing confusion.

\33. What is the minimum overhead to send an IP packet using PPP? Count only the overhead introduced by PPP itself, not the IP header overhead. What is the maximum overhead?

补充题2. 采用3 比特序号的选择重传（SR）协议，若接收窗口为5，则发送窗口的最大值是多少?

补充题3. 50-kbps 的卫星信道，往返时延为 500ms，帧长为 1000 位，使用捎带确认（搭载ACK）的SR协议，若使效率达到50%，序号的比特数至少是多少?

补充题4. 数据链路层采用GBN（回退N步） 协议，发送方已经发送了编号为0-7 的帧，当计时器超时时，若发送方只收到0、4、5 号帧的确认，则发送方需要重发的帧数是多少?

补充题5. 两台计算机的数据链路层协议实体采取滑动窗口机制利用16kbps 的卫星信道传输长度为128 字节的数据帧，信道传播时延为270ms。

1. 计算使用停等协议的信道利用率；

2. 计算使用发送窗口为7 的GBN 协议的信道利用率；

3. 计算使用发送窗口为15 的GBN 协议的信道利用率；

4. 为使信道利用率达到最高，使用GBN 协议时序号的比特数最少为多少位？

第四章作业

（英文版教材第四章 6,11,13,14,15,16,17,18,20,22,23,24,38,39,41,42

\6. What is the length of a contention slot in CSMA/CD for (a) a 2-km twin-lead cable (signal propagation speed is 82% of the signal propagation speed in vacuum)?, and (b) a 40-km multimode fiber optic cable (signal propagation speed is 65% of the signal propagation speed in vacuum)?

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

\13. What is the baud rate of classic 10-Mbps Ethernet?

\14. Sketch the Manchester encoding on a classic Ethernet for the bit stream 0001110101.

\15. （不做）A 1-km-long, 10-Mbps CSMA/CD LAN (not 802.3) has a propagation speed of 200 m/μsec. Repeaters are not allowed in this system. Data frames are 256 bits long, including 32 bits of header, checksum, and other overhead. The first bit slot after a successful transmission is reserved for the receiver to capture the channel in order to send a 32-bit acknowledgement frame. What is the effective data rate, excluding overhead, assuming that there are no collisions?

\16. 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?

\17. 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?

\18. 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?

\20. How many frames per second can gigabit Ethernet handle? Think carefully and take into account all the relevant cases. Hint: the fact that it is gigabit Ethernet matters.

\22. In Fig. 4-27, four stations, A, B, C, and D, are shown. Which of the last two stations do you think is closest to A and why?

\23. Give an example to show that the RTS/CTS in the 802.11 protocol is a little different than in the MACA protocol.

\24. A wireless LAN with one AP has 10 client stations. Four stations have data rates of 6 Mbps, four stations have data rates of 18 Mbps, and the last two stations have data rates of 54 Mbps. What is the data rate experienced by each station when all ten stations are sending data together, and

(a) TXOP is not used?

(b) TXOP is used?

\38. Consider the extended LAN connected using bridges B1 and B2 in Fig. 4-41(b). Suppose the hash tables in the two bridges are empty. List all ports on which a packet will be forwarded for the following sequence of data transmissions:

(a) A sends a packet to C.

(b) E sends a packet to F.

(c) F sends a packet to E.

(d) G sends a packet to E.

(e) D sends a packet to A.

(f) B sends a packet to F.

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

\41. To make VLANs work, configuration tables are needed in the bridges. What if the VLANs of Fig. 4-47 used hubs rather than switches? Do the hubs need configuration tables, too? Why or why not?

\42. In Fig. 4-48, the switch in the legacy end domain on the right is a VLAN-aware switch. Would it be possible to use a legacy switch there? If so, how would that work? If not, why not?

第五章第1次作业

（英文版教材第五章 1、5、7、14、15、16、补充题1）

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

答：是的，例如有需要紧急发送的数据包。（比如中断信号）

\5. Consider the network of Fig. 5-12(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 cost of the links from C 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 cost.

\7. 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.

\14. A datagram network 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?

(c) hops required per received packet?

\15. Describe two major differences between the ECN method and the RED method of congestion avoidance.

\16. 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?

补充题一：网络节点A收到了下列LSR路由信息包。请画出该网络的拓扑结构，并使用Dijkstra算法构造出A的路由表。

第五章第2次作业

（英文版教材第五章 20、21、23、24、25、27、28、29、30、31、34、35、38、39、补充题2）

\20. 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.

A---------R1---------R2---------B
  1024(14)   512(8)      512(12)

[20B H][900B D]

设 ID=1。MTU 分别是：1010, 504, 500

IP 包头的最小长度是 20B. 要传输的 IP 包大小为 920+20=940B

A -> R1: 940<1010，不分段。由于不知道下个链路的 MTU，所以 DF 设为 0，让下个链路自行决定是否分段。

LEN=940, ID=1, DF=0, MF=0, 0FF=0

R1->R2: 920>512，分两段。(504-20)/8=60.5，因此第一分片长度是 60*8+20=480+20=500

第二分片，920-480=440，加上头部 440+20=460

分片：

1. LEN=500, ID=1, DF=0, MF=1, 0FF=0

2. LEN=460, ID=1, DF=0, MF=0, 0FF=(500-20)/8=60

第三分片：延续上面即可：

1. LEN=500, ID=1, DF=0, MF=1, 0FF=0

2. LEN=460, ID=1, DF=0, MF=0, 0FF=(500-20)/8=60

\21. A router is blasting out IP packets whose total length (data plus header) is 1024 bytes. Assuming that packets live for 10 sec, what is the maximum line speed the router can operate at without danger of cycling through the IP datagram ID number space?

IP 包的 ID 字段长度为 16，也即支持 2^16 个序号。

$$ 8\cdot 2^{16} \cdot 1024 /10=2^{29}/10=53687091.2 \text{bps} $$

\23. Suppose that instead of using 16 bits for the network part of a class B address originally, 20 bits had been used. How many class B networks would there have been?

$2^{20-2}= 2^{18}$

\24. Convert the IP address whose hexadecimal representation is C22F1582 to dotted decimal notation.

C2			2F			15			82
1100 0010	0010 1111	0001 0101	1000 0010
194	  		47			21			130

\25. A network on the Internet has a subnet mask of 255.255.240.0. What is the maximum number of hosts it can handle?

二进制：

11111111 11111111 1111 0000 0000 0000

$$ 2^{12}-2=4096-2=4094 $$

\27. A large number of consecutive IP addresses are available starting at 198.16.0.0. Suppose that four organizations, A, B, C, and D, request 4000, 2000, 4000, and 8000 addresses, respectively, and in that order. For each of these, give the first IP address assigned, the last IP address assigned, and the mask in the w.x.y.z/s notation.

$$ 4000 < 4096 = 2^{12}\\ 2000 < 2048 = 2^{11}\\ 8000 < 8192 = 2^{13} $$

0000 0000 A 		0
0001 0000 A_MAX+1 	16		// A+= 2^12
0001 0000 B			16
0001 1000 B_MAX+1	24
0010 0000 C 		32
0011 0000 C_MAX+1	48
0100 0000 D 		64
0110 0000 D 		96

分配如下：

• A: 198.16.0.0/20：198.16.0.0~198.16.15.255

• B: 198.16.16.0/21：198.16.16.0~198.16.23.255

• C: 198.16.32.0/20：198.16.32.0~198.16.47.255

• D: 198.16.64.0/19：198.16.64.0~198.16.95.255

\28. A router has just received the following new IP addresses: 57.6.96.0/21, 57.6.104.0/21, 57.6.112.0/21, and 57.6.120.0/21. If all of them use the same outgoing line, can they be aggregated? If so, to what? If not, why not?

首先对第三段地址进行位分析

96=64+32

104=64+32+8

112=64+32+16

120=64+32+16+8

这几个地址， 前 21 位固定而且相同，因此可以聚合为 57.6.96.0/21.

\29. The set of IP addresses from 29.18.0.0 to 29.18.127.255 has been aggregated to 29.18.0.0/17. However, there is a gap of 1024 unassigned addresses from 29.18.60.0 to 29.18.63.255 that are now suddenly assigned to a host using a different outgoing line. Is it now necessary to split up the aggregate address into its constituent blocks, add the new block to the table, and then see if any reaggregation is possible? If not, what can be done instead?

29.18.0.0/17 是固定前 17 位，也即范围是：

BIN_OF_29. BIN_OF_18. 0XXX XXXX. XXXX XXXX

范围是：29.18.0.0~29.18.127.255

这与 29.18.60.0~29.18.63.255 存在交叉，可以重新划分为：

但是新来的可以表示为：29.18.48.0/20，比 17 的范围要小，只需要单独添加这一条规则，利用最长匹配即可，不需要重新划分。

\30. A router has the following (CIDR) entries in its routing table:

Address/mask	Next hop
135.46.56.0/22	Interface 0
135.46.60.0/22	Interface 1
192.53.40.0/23	Router 1
default	Router 2

For each of the following IP addresses, what does the router do if a packet with that address arrives?

把 CIDR 转为地址范围：

Address/mask	范围	Next hop
135.46.56.0/22	135.46.56.0-135.46.59.255	Interface 0
135.46.60.0/22	135.46.60.0-135.46.63.255	Interface 1
192.53.40.0/23	192.53.40.0-192.53.41.255	Router 1
default		Router 2

这就很显然了：

(a) 135.46.63.10：Interface 1

(b) 135.46.57.14：Interface 0

(c) 135.46.52.2：Router 2

(d) 192.53.40.7：Router 1

(e) 192.53.56.7：Router 2

\31. Many companies have a policy of having two (or more) routers connecting the company to the Internet to provide some redundancy in case one of them goes down. Is this policy still possible with NAT? Explain your answer.

假设连线情况为：

公网<----路由器1<----内网---->路由器2--->公网

增加 NAT 之后，内部地址映射到公网地址，那么由于一个内部地址不能同时映射到两个公网地址，所以如果一端断开，另一端是无法访问的。

\34. Most IP datagram reassembly algorithms have a timer to avoid having a lost fragment tie up reassembly buffers forever. Suppose that a datagram is fragmented into four fragments. The first three fragments arrive, but the last one is delayed. Eventually, the timer goes off and the three fragments in the receiver’s memory are discarded. A little later, the last fragment stumbles in. What should be done with it?

第四个先放进缓存，然后等前三个到达，如果超时仍然未到达，就丢弃。

\35. In IP, the checksum covers only the header and not the data. Why do you suppose this design was chosen?

校验由数据链路层完成。只校验包头有利于高性能传输，并更好确保包头的正确性。

\38. The Protocol field used in the IPv4 header is not present in the fixed IPv6 header. Why not?

降低耦合，在传输的过程中意义不大。

\39. When the IPv6 protocol is introduced, does the ARP protocol have to be changed? If so, are the changes conceptual or technical?

ARP 的地址长度要扩展到 128 位，另外还应该做出 IPv4 和 IPv6 的区分。

补充题2：

某公司网络拓扑图如下图所示，

路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。

1. 将IP地址空间202.118.1.0/24划分为两个子网，分配给局域网1、局域网2，每个局域网分配的地址数不少于120个，请给出子网划分结果。说明理由或给出必要的计算过程。

202.118.1.0/24 的范围是 202.118.1.0~202.118.1.255，显然只够划分两个了。2^8=128，划分为：

LAN 1：202.118.1.0/25，范围是 202.118.1.0~202.118.1.127

LAN 2：202.118.128.0/25，范围是 202.118.1.128~202.118.1.255

2. 请给出R1的路由表，使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和互联网的路由。 请采用路由聚合技术，给出R2到局域网1和局域网2的路由。

R1 路由表：

来源接口	目的地址	下一跳地址
E1	202.118.1.0/25	/
E2	202.118.128.0/25	/
L0	202.118.3.2/32	202.118.2.2
L0	0.0.0.0/0	202.118.2.2

R2 路由表：

来源接口	目的地址	下一跳地址
L0	202.118.1.0/24	202.118.2.1

第六章作业

（英文版教材第六章 8、10、11、18、19、21、22、25、26、27、28、补充题

\8. In Figure 6-20, suppose a new flow E is added that takes a path from R1 to R2 to R6. How does the max-min bandwidth allocation change for the five flows?

R1-R2 上，A 分配 1/2 带宽，在 R2-R3 上继续分配 1/2 带宽

R1-R2 上，E 分配 1/2 带宽, 在 R2-R6 上继续分配 1/2 带宽

\10. Some other policies for fairness in congestion control are Additive Increase Additive Decrease (AIAD), Multiplicative Increase Additive Decrease (MIAD), and Multiplicative Increase Multiplicative Decrease (MIMD). Discuss these three policies in terms of convergence and stability.

1. 收敛性：AIMD 的收敛性优于 MIAD

2. 稳定性：AIMD 满足慢增快减，其它都不如

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

UDP 实现了进程级别的无连接服务。用 IP 包也不是不行，但是要实现进程到进程，那操作系统层面还得封装一下，岂不是重新发明了 UDP（

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

TCP 最小 MSS 为 536 octets，IHL 20 字节，TCP HEADER 20 字节，所以 IP MTU 至少 576 octets

\19. 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分段的原因是MSS，IP分片的原因是MTU。二者不是必须相干的，如果是 TCP 的分段造成的乱序，需要 TCP 自己解决。

\21. 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?

不能，TCP 连接的唯一性就是源IP:端口和目的IP:端口所确定的

\22. In Fig. 6-36 we saw that in addition to the 32-bit acknowledgement field, there is an ACK bit in the fourth word. Does this really add anything? Why or why not?

ACK 表示下一个发送的起始序号，在建立连接时使用。

\25. Consider the effect of using slow start on a line with a 10-msec round-trip time and no congestion. The receive window is 24 KB and the maximum segment size is 2 KB. How long does it take before the first full window can be sent?

初始 CWND=2KB，需要经过左移（平方） $\log_2 (12)≈3.58$ 次，向上取整 4 次，每次耗时 10ms，所以需要大概 40ms 达到最大窗口速率。

\26. Suppose that the TCP congestion window is set to 18 KB and a timeout occurs. How big will the window be if the next four transmission bursts are all successful? Assume that the maximum segment size is 1 KB.

阈值 18KB，超时，阈值减半，变成 9KB，重新慢启动。1«4=16>9，因此经过四次成功传输，窗口大小变成了 9KB

\27. If the TCP round-trip time, RTT, is currently 30 msec and the following acknowledgements come in after 26, 32, and 24 msec, respectively, what is the new RTT estimate using the Jacobson algorithm? Use α = 0.9.

环回 30ms，

$$ \operatorname{SRTT} = \alpha \operatorname{SRTT}+(1-\alpha)\operatorname{RTT} $$

求得：29.6, 29.84, 29.256

\28. A TCP machine is sending full windows of 65,535 bytes over a 1-Gbps channel that has a 10-msec one-way delay. What is the maximum throughput achievable? What is the line efficiency?

往返时延 20ms，速率 65535*8/0.02=26Mbps左右，利用率 2.6% 左右

补充题

主机甲和乙已建立了TCP连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段。若甲在t时刻发生超时时拥塞窗口为8KB，则从t时刻起，不再发生超时的情况下，请计算经过10个RTT后，甲的发送窗口是多少？

超时阈值减半，变成 4KB，CWND=1。

RTT 1：CWND=2KB

RTT 2：CWND=4KB

剩余 8 个线性增，4+8=12KB.

不过不是还有快速恢复算法吗？感觉这个不太实际。