Computer Networks Part Answers 5 - 1

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

可能发生错序.
在面向连接的服务中, 由于所有发往目的站的数据包都沿着相同的路径传输, 一般不会出现乱序提交的情况.
但是, 对于特殊的数据包, 如异常事件 (例如中断信号) 应该优先处理, 不排队, 不按照顺序交付.
例如在应用中, 一个用户键入退出键 (如 Ctrl-C) 时, 所产生的数据应该立即发送, 并且应当跳过当前队列中排在前面的其它数据包.

2. 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); 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.

由题意, 我们可以列出下面这个表格:

目的地	延迟			最终选择	时延
	数据来源(括号内为传输延迟)
	B(6)	D(3)	E(5)
A	5	16	7	B	11
B	0	12	6	B	6
C	8	6	3	C	--
D	12	0	9	D	3
E	6	9	0	E	5
F	2	10	4	B	8

C 的路由表为:

目的地	延迟	下一跳
A	11	B
B	6	B
C	0	–
D	3	D
E	5	E
F	8	B

附, 一个用于画出上图的 Python 代码:

import matplotlib.pyplot as plt


def draw_hexagon():
    # 定义六边形的顶点坐标
    x = [-1, 1, 2, 1, -1, -2]
    y = [0, 0, 1, 2, 2, 1]

    # 创建一个图形对象
    fig, ax = plt.subplots()

    # 绘制六边形
    # ax.fill(x, y, 'b', alpha=0.5)  # 使用蓝色填充，透明度为0.5

    # 在每个顶点上标注字母标记
    labels = ['E', 'F', 'D', 'C', 'B', 'A']
    for i in range(len(x)):
        ax.text(x[i], y[i], labels[i], ha='center', va='center', fontsize=12)

    # 连接六边形的边
    ax.plot([x[0], x[1]], [y[0], y[1]], 'r-')  # 连接 A-B
    ax.plot([x[1], x[2]], [y[1], y[2]], 'r-')  # 连接 B-C
    ax.plot([x[2], x[3]], [y[2], y[3]], 'r-')  # 连接 C-D
    ax.plot([x[3], x[4]], [y[3], y[4]], 'r-')  # 连接 D-E
    ax.plot([x[4], x[5]], [y[4], y[5]], 'r-')  # 连接 E-F
    ax.plot([x[5], x[0]], [y[5], y[0]], 'r-')  # 连接 F-A
    ax.plot([x[4], x[1]], [y[4], y[1]], 'r-')  # 连接 B-F
    ax.plot([x[3], x[0]], [y[3], y[0]], 'r-')  # 连接 C-E
    # 在边和对角线上标记数字
    ax.text((x[0] + x[1]) / 2, (y[0] + y[1]) / 2, '8', ha='center', va='center', fontsize=12, color='black')
    ax.text((x[1] + x[2]) / 2, (y[1] + y[2]) / 2, '7', ha='center', va='center', fontsize=12, color='black')
    ax.text((x[2] + x[3]) / 2, (y[2] + y[3]) / 2, '3', ha='center', va='center', fontsize=12, color='black')
    ax.text((x[3] + x[4]) / 2, (y[3] + y[4]) / 2, '2', ha='center', va='center', fontsize=12, color='black')
    ax.text((x[4] + x[5]) / 2, (y[4] + y[5]) / 2, '4', ha='center', va='center', fontsize=12, color='black')
    ax.text((x[5] + x[0]) / 2, (y[5] + y[0]) / 2, '5', ha='center', va='center', fontsize=12, color='black')

    ax.text((x[4] + 3 * x[1]) / 4, (y[4] + 3 * y[1]) / 4, '6', ha='left', va='top', fontsize=12, color='black')
    ax.text((x[3] + 3 * x[0]) / 4, (y[3] + 3 * y[0]) / 4, '1', ha='left', va='top', fontsize=12, color='black')

    # 设置坐标轴范围
    ax.set_xlim(-2.5, 2.5)
    ax.set_ylim(-0.5, 2.5)

    # 设置坐标轴刻度标签为空
    ax.set_xticks([])
    ax.set_yticks([])

    plt.savefig('题2.svg', format='svg')

    # 显示图形
    plt.show()


# 调用函数绘制六边形
draw_hexagon()

3. 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 = 15 \times 16 \times 20 $, 即, 当选择 15 个簇, 16 个区域, 每个区域 20 个路由器时, 路由表尺寸最小.
路由表表项为也可选择 20 个簇, 16 个区, 每区 15 个路由器, 总表项长度一样, 为 49 (15 + 16 + 20 - 2), 以此类推, 一共 6 种组合.
这里为什么还有个 -2 而不是 -3 呢, 因为每一层的路由器都不需要在路由表里构建自己的信息啊. 可以这样想, 在 “簇” 这一层,
每个路由器只需要保存除自己外其他同层路由器的信息, “区” 这一层也是如此, 但是情况到了 “区” 这一层则有所变化了. “区”
这一层的路由器除了需要保存 19 个本层的路由器. 还需要保存一个与其所在区相连的区一级别的路由器的路由信息.
所以最后计算结果需要 -2 而不是 -3.

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

(a): 一帧经过的跳数可能是: 1, 2, 3. 概率分别为:

$$P_1 = p \quad P_2 = (1 - p)p \quad P_3 = (1 - p)p^2$$

则传输过程中, 每个包的平均跳数为:

$$averageHops = \frac{P_1 + 2P_2 + 3P_3}{3} = p^2 - 3p + 3$$

(b): 一个包要想正确传达, 需要经历三跳, 每个包正确到达的概率为 $ P_3 $, 则, 每个包产生的传输次数:

$$\sum^{\infty}_{i = 1} i \times ((1 - p)^2)^i = \frac{1}{(1 - p)^2}$$

如下图所示:

(c): 由 a, b 两小问可知, 每个包送达的总跳数为:

$$\frac{p^2 - 3p + 3}{(1 - p)^2}$$

5. Describe the two main differences between the Explicit Congestion Notification (ECN) and Random Early Detection (RED).

1. ECN 通过在 IP 包中设定通知位, 明确地 (显式) 发送拥塞通知给源主机. 而 RED 通过丢弃数据包来隐式地通知源主机发生拥塞.
2. ECN 只在路由器的缓冲空间耗尽 (队列满) 时丢弃数据包; RED 则是在剩余缓存达到临界值, 而不是耗尽时丢弃数据包.

6. 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 秒. 由题可知: $ 50M \times t = 1M + 10M \times t $, 解得 $ t = 0.025 $, 最长能持续 25 ms.

7. Suppose that host A is connected to a router R1, R1 is connected to another router, R2, and R2 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.

1. A -> R1: MTU = 1010 Bytes (1024 - 14), 一个 IP 报文能承载的最大数据为: 980 Bytes (1010 - 20), 从传输层获得的数据最长为
   920 Bytes (20 + 900). 所以只需发送一个包即可.
   总长度: 940 Bytes (20 + 920), ID = 任意值; DF, MF, Offset = (0, 0, 0).
2. R1 -> R2: MTU = 504 Bytes (512 - 8), 一个 IP 报文能承载的最大数据为: 484 Bytes (504 - 20), 所以需要发送多个数据包.
   1. 总长度: 500 Bytes (20 + 480), 这里解释一下为什么要数据部分长度为 400. 因为所能承载最大数据的 484, 不能被 8
      整除, 所以选择距离 484 最近, 小于 484, 且可以被 8 整除的最大整数.
      ID = X; DF, MD, Offset = (0, 1, 0)
   2. 总长度: 460 Bytes (20 + 440), ID = X; DF, MD, Offset = (0, 0, 60). 这个 Offset 的计算方式就是 480/8
3. R2 -> B: MTU = 500 Bytes (512 - 8 ), 一个 IP 报文能承载的最大数据为: 480 Bytes (500 - 20), 所以需要发送多个数据包.
   1. 总长度: 500 Bytes (20 + 480), ID = X; DF, MD, Offset = (0, 0, 0).
   2. 总长度: 460 Bytes (20 + 440), ID = X; DF, MD, Offset = (0, 0, 60).

8. 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 bits, 所以共有 65536 个 ID, 最多能产生 65536 个不同 ID 的包, 所以最大传输速度为: $ (65536 \times 1024
\times 8) \div 10 = 54 Gbps $.

9. 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?

如果使用 20 位网络号, 除去2位的B类地址标识, 有 18 位留给网络. 因此, 网络数量将是 $ 2^18 $ 或 262144 个.

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

194.47.21.130

2023-06-18 
IP属地: 北京