04 网络层

复习题

R1

R1. Let’s review some of the terminology used in this textbook. Recall that the name of a transport-layer packet is segment and that the name of a link-layer packet is frame. What is the name of a network-layer packet? Recall that both routers and link-layer switches are called packet switches. What is the fundamental difference between a router and link-layer switch?
R1. 我们回顾在本书中使用的某些术语。前面讲过运输层的分组名字是报文段， 数据链路层的分组名字是帧。 网络层的分组名字是什么？前面讲过路由器和链路层交换机都被称为分组交换机,路由器与链路层交换机间的根本区别是什么？

网络层分组的名字是数据报。路由器工作在网络层，根据网络层字段进行分组转发；链路层交换机工作在数据链路层，根据链路层字段进行分组转发。

R3

R3. We made a distinction between the forwarding function and the routing function performed in the network layer. What are the key differences between routing and forwarding?
R3. 我们对网络层执行的转发功能和路由选择功能进行区别。路由选择和转发的主要区别是什么？

转发是指 : 路由器将到达某条输入链路的分组转发到恰当的输出链路。
路由选择是指 : 在路由器组成的图结构中，选择一条最恰当 (例如费用最低) 的从发送方到接收方的路径，将分组从源主机移动到目的主机。

R6

R6. In Section 4.2, we saw that a router typically consists of input ports, output ports, a switching fabric and a routing processor. Which of these are implemented in hardware and which are implemented in software? Why? Returning to the notion of the network layer’s data plane and control plane, which are implemented in hardware and which are implemented in software? Why?
R6. 在4.2节中， 我们看到路由器通常由输入端口、 输出端口、 交换结构和路由选择处理器组成。其中哪些是用硬件实现的， 哪些是用软件实现的？为什么？转到网络层的数据平面和控制平面的概念， 哪些是用硬件实现的， 哪些是用软件实现的？为什么？

• 输入端口, 输出端口, 交换结构是用硬件实现的. 路由选择处理器是用软件实现的。因为它们的数据报处理功能对于软件实现而言太快了。传统路由器内部的路由处理器使用软件来执行路由协议，维护路由表和附加的链接状态信息以及计算路由器的转发表。SDN路由器中的路由处理器还依赖于与遥控器通信的软件，以便接收转发表项并将它们安装在路由器的输入端口中。
• 数据平面是用硬件实现的, 控制平面是用软件实现的。原因是在数据平面处理两个数据报之间的时间非常短, 软件无法在这么短的时间内完成转发。 控制平面则不同于数据平面的, 它的主要功能是维护转发表, 逻辑比数据平面复杂多了, 而且它不需要短时间处理大量时间, 只需要及时更新就行了, 因此用软件实现。

R7

R7. Discuss why each input port in a high-speed router stores a shadow copy of the forwarding table.
R7. 讨论为什么在高速路由器的每个输入端口都存储转发表的影子副本。

首先一个路由器是有很多个输入端口的, 转发行为的第一步是在转发表中查找输出接口。 如果每个输入端口都并发地调用路由选择器查找输出接口必然会产生时延。所以要在高速路由器的每个输入端口都存储转发表的影子副本, 使转发决策能在每个输入端口本地做出, 避免了集中式处理的瓶颈。

R8

R8. What is meant by destination-based forwarding? How does this differ from generalized forwarding (assuming you’ve read Section 4.4, which of the two approaches are adopted by Software-Defined Networking)?
R8. 基于目的地转发意味着什么？这与通用转发有什么不同（假定你已经阅读4.4节， 两种方法中哪种是软件定义网络所采用的）？

Destination-based forwarding means that a datagram arriving at a router will be forwarded to an output interface based on only the final destination of the datagram. Generalized-forwarding means that besides its final destination, other factors associated with a datagram is also considered when a router determines the output interface for the datagram. Software defined networking adopts generalized forwarding, for example, forwarding decision can be based on a datagram’s TCP/UDP source or destination port numbers, besides its destination IP address.

• 基于目的地转发意味着到达路由器的数据报将仅基于数据报的最终目标转发到输出接口，如果是根据目的地的IP地址转发的话, 路由转发表中可能需要有40多亿项. 当然可以通过匹配IP地址的最长前缀对所有IP地址进行分组. 但是这样的路由器功能太单一, 不具有普遍性.
• 通用转发当路由器确定数据报的输出接口时，除了其最终目的地外，还将考虑与数据报相关的其他因素。通用转发延续了基于目的转发的”匹配+动作”模式, 但不受限于通过源分组的IP地址匹配目的IP地址进行转发, 而是通过富足首部字段值集合和计数器集合对动作集合进行匹配。
• 软件定义的网络采用通用转发，例如，除了目标IP地址外，转发决策还可以基于数据报的TCP / UDP源或目标端口号。

R11

R11. Describe how packet loss can occur at input ports. Describe how packet loss at input ports can be eliminated (without using infinite buffers).
R11. 描述在输入端口会出现分组丢失的原因。 描述在输入端口如何消除分组丢失（不使用无限大缓存区）。

• 丢失原因：如果分组到达输入链路的速率超过了交换结构处理分组的速率，那么就会产生排队，如果这种速度的不匹配持续下去，那么分组的队列将越来越长，最终溢出输入端口缓冲区，产生丢包。
• 消除分组丢失：在输入端口消除分组丢失的方式是使交换结构的速率尽可能大，比如输入链路 A 的分组到达速率为 v1，输入链路 B 的分组到达速率为 v2，以此类推，那么为了消除输入链路的丢包，交换结构的速率至少为 ，N 是输入链路的个数。

R12

R12. Describe how packet loss can occur at output ports. Can this loss be prevented by increasing the switch fabric speed?
R12. 描述在输出端口会出现分组丢失的原因。通过提高交换结构速率， 能够防止这种丢失吗？

• 交换结构对某输出端口的发送速度快于输出端口的输出速度，会造成排队现象，排队过长就会发生丢失。
• 增加交换结构的速率对丢失现象起到相反的作用。速率越高丢失越多。

R17

R17. Suppose Host A sends Host B a TCP segment encapsulated in an IP datagram. When Host B receives the datagram, how does the network layer in Host B know it should pass the segment (that is, the payload of the datagram) to TCP rather than to UDP or to some other upper-layer protocol?
R17. 假定主机 A 向主机 B 发送封装在一个IP数据报中的TCP报文段。 当主机 B 接收到该数据报时， 主机 B 中的网络层怎样知道它应当将该报文段（即数据报的有效载荷）交给 TCP 而不是 UDP 或某个其他东西呢？

主机 B 的网络层通过检查 IPv4 数据报首部的 “上层协议” 字段来确定应该将网络层数据报交给 UDP 还是 TCP 或者其他什么东西。

R20

R20. When a large datagram is fragmented into multiple smaller datagrams, where are these smaller datagrams reassembled into a single larger datagram?
R20. 什么时候一个大数据报分割成多个较小的数据报 ？较小的数据报在什么地方装配成一个较大的数据报 ？

• 网络层的数据报需要往下经过链路层封装成链路层帧才能放上链路开始传输. 然而一个链路层帧的载荷大小根据链路层协议的不同而不同, 数据报的大小不能超过一个链路层帧的最大传送单元(Maximum Transmission Unit, MTU). 所以当链路层遇到大于自身MTU的数据报时需要把数据报分割成多个较小的数据报. 这项工作将放到端系统中进行, 因为如果在路由器中进行的话会大大降低路由器的性能.
• IP数据报的片段的重组在目的端系统的网络层中完成。

R26

R26. Suppose you purchase a wireless router and connect it to your cable modem. Also suppose that your ISP dynamically assigns your connected device (that is, your wireless router) one IP address. Also suppose that you have five PCs at home that use 802.11 to wirelessly connect to your wireless router. How are IP addresses assigned to the five PCs? Does the wireless router use NAT? Why or why not?
R26. 假定你购买了一个无线路由器并将其与电缆调制解调器相连。 同时假定 ISP 动态地为你连接的设备（即你的无线路由器） 分配一个 IP 地址。 还假定你家有5台PC, 均使用802.11以无线方式与该无线路由器相连。 怎样为这5台 PC 分配 IP 地址？该无线路由器使用 NAT 吗？为什么？

• 这5台PC的IP地址会通过请求DHCP服务器获得.
• 该无线路由器会使用NAT, 因为无线路由器仅从 ISP 获得一个 IP 地址，家庭网络可能会随时加入许多台联网设备, 而最简单常用的管理这些设备IP地址的方法就是NAT.

R27

R27. What is meant by the term “route aggregation”? Why is it useful for a router to perform route aggregation?
R27. “路由聚合 ” 一词意味着什么？路由器执行路由聚合为什么是有用的？

• 路由聚合意味着一个子网只通过接入IP地址的部分前缀和外部因特网相连, 外界并不关心子网内还存在着多个组织, 这种使用单个网络前缀通告多个网络的能力通常称为路由聚合.
• 对于路由器而言, 假设一台组织外的路由器要转发一个数据报, 该数据报的目的地址在组织内部, 那么该组织外的路由器转发到组织内的一台路由器时, 只需要考虑地址的前x比特即可. 这个做法相当大地减少了在这些路由器中转发表的长度. (使转发表不用记录每个具体目的IP地址, 只需要记录一个类似223.1.1.0/24一样的带前缀的地址即可)

R31

R31. It has been said that when IPv6 tunnels through IPv4 routers, IPv6 treats the IPv4 tunnels as link-layer protocols. Do you agree with this statement? Why or why not?
R31. 有人说当IPv6 以隧道形式通过IPv4 路由器时，IPv6将 IPv4 隧道作为链路层协议。 你同意这种说法吗？为什么？

可以这样理解。因为整个IPv6数据报（包括报头字段）都封装在IPv4数据报中，对IPV6报文来讲隧道就相当于过了一跳路由器，因此IPv6将IPv4隧道视为链路层协议，IPv6 相当于把 IPv4 的首部当成了 “链路层首部”。

R34

R34. What is meant by the “match plus action” operation of a router or switch? In the case of destination-based forwarding packet switch, what is matched and what is the action taken? In the case of an SDN, name three fields that can be matched, and three actions that can be taken.
R34. 路由器 或交换机的“匹配加动作”意味着什么？在基于目的地转发的分组交换机场合中，要匹配什么并采取什么动作？在 SDN 的场合中， 举出3个能够被匹配的字段和3个能被采取的动作。

“匹配加操作”是指路由器或交换机试图在流表中的一些条目之间找到数据包的一些报头值之间的匹配，然后根据该匹配，路由器决定将数据包转发到哪个接口，甚至在数据包上进行更多的操作。 在基于目标的转发包交换机的情况下，路由器只试图在流表条目与到达包的目标IP地址之间找到匹配，其作用是决定将数据包转发到哪个接口。 在SDN的情况下，可以匹配许多字段，例如IP源地址、TCP源端口和源MAC地址；也可以采取许多操作，例如转发、删除和修改字段值。

习题

P1

P1. Consider the network below.
a. Show the forwarding table in router A, such that all traffic destined to host H3 is forwarded through interface 3.
b. Can you write down a forwarding table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3, while all traffic from H2 destined to host H3 is forwarded through interface 4? (Hint: This is a trick question.)
P1. 考虑下面的网络。
a. 显示路由器 A 中的转发表， 使得目的地为主机 H3 的所有流址都通过接口 3 转发。
b. 写出路由器 A 中的转发表， 使得从 H1 发往主机 H3 的所有流量都通过接口 3 转发， 从 H2 发往主机 H3 的所有流量都通过接口 4 转发。（提示：这是一个技巧性的问题。）

a.

b. 不能，因为转发表是根据目的地来区分的，而不是源地址。

P2

P2. Suppose two packets arrive to two different input ports of a router at exactly the same time. Also suppose there are no other packets anywhere in the router.
a. Suppose the two packets are to be forwarded to two different output ports. Is it possible to forward the two packets through the switch fabric at the same time when the fabric uses a shared bus?
b. Suppose the two packets are to be forwarded to two different output ports. Is it possible to forward the two packets through the switch fabric at the same time when the fabric uses switching via memory?
c. Suppose the two packets are to be forwarded to the same output port. Is it possible to forward the two packets through the switch fabric at the same time when the fabric uses a crossbar?
P2. c的时刻到达一台路由器的两个不同输入端口。 同时假设在该路由器中没有其他分组。
a. 假设这两个分组朝看两个不同的输出端口转发。 当交换结构使用一条共享总线时， 这两个分组可能在相同时刻通过该交换结构转发吗？
b. 假设这两个分组朝着两个不同的输出端口转发。当交换结构使用经内存交换时， 这两个分组可能在相同时刻通过该交换结构转发吗？
c. 假设这两个分组朝着相同的输出端口转发。 当交换结构使用纵横式时， 这两个分组可能在相同时刻通过该交换结构转发吗？

a. 不能，只能在共享总线上一次传输一个数据包。
b. 不能，在共享系统总线上一次只能完成一个内存读/写。
c. 不能，在这种情况下，两个数据包必须同时通过相同的输出总线发送，这是不可能的

P5

P5. Consider a datagram network using 32-bit host addresses. Suppose a router
has four links, numbered 0 through 3, and packets are to be forwarded to the
link interfaces as follows:

a. Provide a forwarding table that has five entries, uses longest prefix match-
ing, and forwards packets to the correct link interfaces.
b. Describe how your forwarding table determines the appropriate link inter-
face for datagrams with destination addresses:

P5. 考虑使用 32 比特主机地址的某数据报网络。假定一台路由器具有4条链路， 编号为0~3， 分组能被转发到如下的各链路接口：
a. 提供一个具有 5个 表项的转发表，使用最长前缀匹配，转发分组到正确的链路接口。
b. 描述你的转发表是如何为具有下列目的地址的数据报决定适当的链路接口的。

a.

b.

• 对于地址 1100 1000 1001 0001 0101 0001 0101 0101 进行最长前缀匹配，发现它能匹配的是端口 3
• 对于地址 1110 0001 0100 0000 1100 0011 0011 1100 进行最长前缀匹配，发现它能匹配的是端口 2
• 对于地址 1110 0001 1000 0000 0001 0001 0111 0111 进行最长前缀匹配，发现它能匹配的是端口 3

P11

P11. Consider a subnet with prefix 128.119.40.128/26. Give an example of one IP address (of form xxx.xxx.xxx.xxx) that can be assigned to this network. Suppose an ISP owns the block of addresses of the form 128.119.40.64/26. Suppose it wants to create four subnets from this block, with each block having the same number of IP addresses. What are the prefixes (of form a.b.c.d/x) for the four subnets?
P11. 考虑一个具有前缀 128.119.40.128/26 的子网。 给出能被分配给该网络的一个 IP 地址 （形式为 xxx.xxx.xxx.xxx)的例子。假定一个 ISP 拥有形式为 128.119.40.64/26 的地址块。假定它要从该地址块生成 4 个子网， 每块具有相同数量的 IP 地址。 这4个子网（形式为 a.b.c.d/x)的前缀是什么？

• 128.119.40.128/26 写成二进制字符串
  • 119 = 64 + 32 + 16 + 4 + 2 + 1 = 0111 0111
  • 40 = 32 + 8 = 0010 1000
  • 最终结果为 10000000 01110111 00101000 00
  • 所以能够分配给该网络的一个 IP 地址为 128.119.40.32
• 128.119.40.64/26 写成二进制字符串
  • 10000000 01110111 00101000 01 剩下 6 个比特来分配 IP 地址，故总共可以使用的 IP 地址有 个即 64 个，那么要分成 4 个子网，即每个子网 16 个。因此子网划分如下 | 地址范围 | 前缀匹配 | 前缀匹配 | | —- | —- | —- | | 10000000 01110111 00101000 01000000
    10000000 01110111 00101000 01001111 | 10000000 01110111 00101000 0100 | 128.119.40.64/28 | | 10000000 01110111 00101000 01010000
    10000000 01110111 00101000 01011111 | 10000000 01110111 00101000 0101 | 128.119.40.80/28 | | 10000000 01110111 00101000 01100000
    10000000 01110111 00101000 01101111 | 10000000 01110111 00101000 0110 | 128.119.40.96/28 | | 10000000 01110111 00101000 01110000
    10000000 01110111 00101000 01111111 | 10000000 01110111 00101000 0111 | 128.119.40.112/28 |

P16

P16. Consider the network setup in Figure 4.25. Suppose that the ISP instead assigns the router the address 24.34.112.235 and that the network address of the home network is 192.168.1/24.
a. Assign addresses to all interfaces in the home network.
b. Suppose each host has two ongoing TCP connections, all to port 80 at host 128.119.40.86. Provide the six corresponding entries in the NAT translation table.

P16. 考虑在图 4-25 中建立的网络。假定 ISP 现在为路由器分配地址 24.34.112.235, 家庭网络的网络地址是 192.168.1/24。
a. 在家庭网络中为所有接口分配地址。
b. 假定每台主机具有两个进行中的 TCP 连接， 所有都是针对主机 128. 119. 40. 86 的 80 端口的。在 NAT 转换表中提供 6 个对应表项。

a.

b.

P17

P17. Suppose you are interested in detecting the number of hosts behind a NAT. You observe that the IP layer stamps an identification number sequentially on each IP packet. The identification number of the first IP packet generated by a host is a random number, and the identification numbers of the subsequent IP packets are sequentially assigned. Assume all IP packets generated by hosts behind the NAT are sent to the outside world.
a. Based on this observation, and assuming you can sniff all packets sent by the NAT to the outside, can you outline a simple technique that detects the number of unique hosts behind a NAT? Justify your answer.
b. If the identification numbers are not sequentially assigned but randomly assigned, would your technique work? Justify your answer.
P17. 假设你有兴趣检测 NAT 后面的主机数量。你观察到在每个 IP 分组上 IP 层顺序地标出一个标识号。 由一台主机生成的第一个 IP 分组的标识号是一个随机数， 后继 IP 分组的标识号是顺序分配的。假设由 NAT 后面主机产生的所有 IP 分组都发往外部。
a. 基于这个观察， 假定你能够俘获由 NAT 向外部发送的所有分组， 你能概要给出一种简单的技术来检测 NAT 后面不同主机的数量吗？评估你的答案。
b. 如果标识号不是顺序分配而是随机分配的， 这种技术还能正常工作吗？评估你的答案。

a. 意思是每台主机进行 IP 分片时，为 IP 数据报选择的 2 字节标示是一个随机值，第一个报文的所有分片都是该随机值，第二个报文的所有分片是该随机值加 1，由于每台主机都是选一个随机的初始值，但随后的分组都是连续递增的，所以将这些切片划分为连续递增的多个簇，最后统计簇的数量，就是 NAT 后面主机的数量。
b. 不能，因为无法统计连续递增的标示号的数量了。

P19

P19. Consider the SDN OpenFlow network shown in Figure 4.30. Suppose that the desired forwarding behavior for datagrams arriving at s2 is as follows:

• any datagrams arriving on input port 1 from hosts h5 or h6 that are destined to hosts h1 or h2 should be forwarded over output port 2;
• any datagrams arriving on input port 2 from hosts h1 or h2 that are destined to hosts h5 or h6 should be forwarded over output port 1;
• any arriving datagrams on input ports 1 or 2 and destined to hosts h3 or h4 should be delivered to the host specified;
• hosts h3 and h4 should be able to send datagrams to each other. Specify the flow table entries in s2 that implement this forwarding behavior.

Specify the flow table entries in s2 that implement this forwarding behavior.
P19. 考虑显示在图 4-30 中的 SDN OpenFlow 网络。假定对于到达 s2 的数据报的期望转发行为如下：

• 来自主机 h5 或 h6 并且发往主机 h1 或 h2 的任何数据报应当通过输出端口 2 转发到输入端口 1。
• 来自主机 h1 或 h2 并且发往主机 h5 或 h6 的任何数据报应当通过输出端口 1 转发到输入端口 2。
• 任何在端口 1 或 2 到达并且发往主机 h3 或 h4 的数据报应当传递到特定的主机。
• 主机 h3 和 h4 应当能够向彼此发送数据报。

详述实现这种转发行为的 s2 中的流表项。

Ingress Port = 2; IP Dst = 10.2.0.4
Ingress Port = 1; IP Dst = 10.2.0.4
Ingress Port = 2; IP Dst = 10.2.0.3 | Forward (3)
Forward (4)
Forward (3)
Forward (4) |

| | | | | | | Ingress Port = 4

Ingress Port = 3 | Forward (3)
Forward (4) |

P20

P20. Consider again the SDN OpenFlow network shown in Figure 4.30. Suppose that the desired forwarding behavior for datagrams arriving from hosts h3 or h4 at s2 is as follows:

• any datagrams arriving from host h3 and destined for h1, h2, h5 or h6 should be forwarded in a clockwise direction in the network;
• any datagrams arriving from host h4 and destined for h1, h2, h5 or h6 should be forwarded in a counter-clockwise direction in the network. Specify the flow table entries in s2 that implement this forwarding behavior.

P20. 再次考虑显示在图 4-30 中的 SDN OpenFlow 网络。假定在 s2 对于来自主机 h3 或 h4 的数据报的期望转发行为如下：

• 任何来自主机 h3 并且发往主机 h1 、 h2 、 h5 或 h6 的数据报应当在网络中以顺时针方向转发。
• 任何来自主机 h4 并且发往主机 h1 、 h2 、 h5 或 h6 的数据报应当在网络中以逆时针方向转发。

Ingress Port = 3; IP Dst = 10.3.*.* | Forward   (2)
Forward (2) |

| Ingress Port = 4; IP Dst = 10.1..

Ingress Port = 4; IP Dst = 10.3.*.* | Forward (1)
Forward (1) |

P21

P21. Consider again the scenario from P19 above. Give the flow tables entries at packet switches s1 and s3, such that any arriving datagrams with a source address of h3 or h4 are routed to the destination hosts specified in the destination address field in the IP datagram. (_Hint: _Your forwarding table rules should include the cases that an arriving datagram is destined for a directly attached host or should be forwarded to a neighboring router for eventual host delivery there.)
P21. 再次考虑上面 P19 的场景。给出分组交换机 s1 和 s3 的流表项、 使得具有 h3 或 h4 源地址的任何到达数据报被路由到在 IP 数据报的目的地址字段中定义的目的主机。（提示：你的转发表规则应当包括如下情况， 即到达的数据报被发往直接连接的主机， 或应当转发到相邻路由器以便传递到最终主机。）

P22

P22. Consider again the SDN OpenFlow network shown in Figure 4.30. Suppose we want switch s2 to function as a firewall. Specify the flow table in s2 that implements the following firewall behaviors (specify a different flow table for each of the four firewalling behaviors below) for delivery of datagrams destined to h3 and h4. You do not need to specify the forwarding behavior in s2 that forwards traffic to other routers.

• Only traffic arriving from hosts h1 and h6 should be delivered to hosts h3 or h4 (i.e., that arriving traffic from hosts h2 and h5 is blocked).
• Only TCP traffic is allowed to be delivered to hosts h3 or h4 (i.e., that UDP traffic is blocked).
• Only traffic destined to h3 is to be delivered (i.e., all traffic to h4 is blocked).
• Only UDP traffic from h1 and destined to h3 is to be delivered. All other traffic is blocked.

P22. 再次考虑显示在图 4-30 中的 SDN OpenFlow 网络。假定我们希望交换机 s2 的功能像防火墙一样。在 s2 中定义实现下列防火墙行为的流表， 以传递目的地为 h3 和 h4 的数据报（对下列四种防火墙行为， 每种定义一张不同的流表）。不需要在 s2 中定义将流量转发到其他路由器的转发行为。

• 仅有从主机 h1 和 h6 到达的流量应当传递到主机 h3 或 h4（即从主机 h2 和 h5 到达的流量被阻塞）。
• 仅有 TCP 流量被允许传递给主机 h3 或 h4（即 UDP 流量被阻塞）。
• 仅有发往 h3 的流量被传递（即所有到 h4 的流量被阻塞）。
• 仅有来自 h1 并且发往 h3 的 UDP 流量被传递。所有其他流量被阻塞。

UDP没有源IP，分别使用不同Port