The Network Layer

Introduction

网络层有如下功能： - 将从 transport layer 传来的 segment 打包成 datagram，再将 datagram 中的 segment 分离开传给 transport layer。 - 网络层协议应用在 host 和 router 中。

Router 和 Switch 都属于 packet switch。

尽管路由器和链路层交换机都被称为packet switches（分组交换机），但它们有以下根本区别：

1. 工作层次不同：
   • 路由器（Router）：工作在网络层（第3层）
   • 链路层交换机：工作在链路层（第2层）
2. 转发决策依据：
   • 路由器：基于IP地址（网络层地址）做出转发决策
   • 链路层交换机：基于MAC地址（物理地址）做出转发决策
3. 功能范围：
   • 路由器：能够连接不同网络，执行路由决策和网络互联
   • 链路层交换机：主要在同一网络内转发帧
4. 网络视角：
   • 路由器：能看到网络的拓扑结构，具有全局视野
   • 链路层交换机：仅限于局部链路的连接情况

路由器拥有的IP地址数量通常等于其活跃网络接口的数量。这是因为：

• 路由器的每个接口都需要一个IP地址来参与其所连接网络的通信
• 不同接口连接到不同的网络，因此需要不同的IP地址

Forwarding and Routing

这两个功能十分好理解： - Forwarding： 一个 router 中，决定如何移动 datagram 到正确的输出。 - Routing： 决定 datagram 在整个网络中的传输路线。

Network Service Model

需要保证，对 individual datagram：正确传输和传输时间；对 a flow of datagrams： 顺序接受，完整传输和传输最小带宽。

Virtual Circuit and Datagram Networks

网络层有两种服务：connectionless service 和 connection service；这两种服务分别应用在 datagram network 和 virtual circuit network。

Datagram Network

数据包网络使用的是动态路由，每一个数据包可以根据当前的网络状况独立地选择路径。

Forwarding Table

Forwarding table 应用在 router 中，决定如何移动 datagram 到正确的输出。

具体形式如下表格所示，可以看到就是一个简单的地址到接口的映射

Destination Address Range	Link Interface
\(\sim\)	\(0\)
\(\sim\)	\(1\)
otherwise	\(2\)

需要注意的是：表格中的 Destination Address Range 可以不是完整的 IP address，而是其的一个前缀；比如 00111000，对应的地址范围是 00111000 00000000 00000000 00000000 到 00111000 11111111 11111111 11111111 11111111。这时 forwarding table 变成：

Header	Link Interface
\(\sim\)	\(0\)
\(\sim\)	\(1\)
otherwise	\(2\)

What’s inside a Router

有两个重要的路由功能： - 运行路由算法。 - 推送 datagram。

Input Port

flowchart LR
    A[Line Termination <br> bit-level reception] --> B[Data Link Processing]
    B --> C[Look up and Forwarding <br> Queueing]
    C --> D[Switch Fabric]

这里涉及到的 look up and forwarding 的方式是 decentralized switching，也就是 forwarding table 已经存入到了 input port 的 memory 中。

Switching Fabric

有三种 switching fabrics。

Switching via Memory

这时可以把路由器看作是一个 computer。使用电脑的 CPU 来 switching。

这个流程是，先把 datagram 拷贝到电脑 memory 中，在从 memory 传到相应的 output port。

可以分析的是：memory bandwidth 是限制 switching rate 的主要因素。同时需要注意的是，每个 datagram 会经过两次 system bus。

Switching via Bus

其中只用到一个 bus。bus bandwidth 限制了 switching speed。

Switching via Interconnection Network

网状结构。先 fragmenting datagram into fixed length cells，再 switch cells through the fabric。

Output Port

flowchart LR
    A[Switch Fabric] --> B[Queueing: Buffer Management]
    B --> C[Data Link Processing]
    C --> D[Line Termination]

Output Port Queueing

Buffering when arrival rate via switch exceeds output line speed. Queueing (delay) and loss due to output port buffer overflows.

所以，需要多大的 buffer？假设 typical \(\text{RTT}\)（一般是 \(250\) ms），link capacity \(C\)，有 \(N\) 个 datagram flow。则： \[ \text{buffering} = \frac{\text{RTT} \cdot C}{\sqrt{N}} \]

Input Port Queueing

同样，输入端也会堵塞。应用了名叫 Head-of-the-Line (HOL) blocking 的机制，这个机制很好理解：就是排在前面的 datagram 传输了，其后面的 datagram 才能传输。

Internet Protocol

这个协议干了三件事：addressing conventions（地址约定），datagram format，packet handling conventions（分组处理约定）。

IP Datagram Format

IPv4

IPv4 datagram format

总结表格：

字段名	长度	作用/说明
Version	4 位	IP 协议版本号
Header Length	4 位	首部长度（单位：\(4\) 字节，最少 \(5\) ）
Type of Service	8 位	服务类型/QoS
Datagram Length	16 位	数据报总长度（单位：\(1\) 字节）
Identifier	16 位	分片标识符
Flags	3 位	分片控制标志
Fragmentation Offset	13 位	分片偏移量（单位：\(8\) 字节）
Time-to-Live (TTL)	8 位	生存时间/最大跳数
Upper-layer Protocol	8 位	上层协议类型
Header Checksum	16 位	首部校验和
Source IP Address	32 位	源 IP 地址
Destination IP Address	32 位	目的 IP 地址
Options	可变	可选字段
Data	可变	负载数据

补充： - Flags 有 \(3\) 位，第一位恒为 \(0\)，第二位表示 Don’t fragment（不可分片），第三位表示 More fragments（后续有分片）。为 \(1\) 的时候相应功能开启。

IP Fragmentation and Reassembly

从 IPv4 的 datagram format 中可以发现，必要时会对 datagram 切片。

MTU：max transfer size。这是对 link 而言，也就是说不同的 link 有不同的 MTU。

Fragmentation and Reassembly 的过程很简单，就是需要时切分 datagram，最后在最终目的主机的网络层进行：只有当所有分片都到达后，网络层才会将完整的数据报交给上层（如传输层）。

假设原 IP datagram 总长度为 \(L\)，待转发链路的 MTU 为 \(M\)，若 \(L > M\) 且 DF 为 \(0\)，则需要分片。 - 先复制 Identifier。 - 一个切片可封装的数据为：\[d = \left \lfloor \frac{M - 20}{8} \right \rfloor \times 8\] - 需要的总片数为：\[n = \left \lceil \frac{L - 20}{d} \right \rceil\]

IPv4 Addressing

Subnet

IP address: subnet part (high order bits) \(+\) host part (low order bits).

在一个 subnet 中的所有设备都可以直接物理意义上地连接。

Subnet mask：用类似 /24 的形式表示。也就是说，前 \(24\) 相同的 IP address 在同一个 subnet 中。

Classes Inter Domain Routing: CIDR

规定了 address format 为 a.b.c.d/x。

Dynamic Host Configuration Protocol: DHCP

Goal: allow host to dynamically get his IP address from a server when it joins network. - Can renew its lease on address in use. - Allows reuse of address. - Support for mobile users who want to join network.

DHCP（Dynamic Host Configuration Protocol，动态主机配置协议）是一个网络管理协议，用于在IP网络中自动分配IP地址和其他网络配置参数给网络设备。DHCP运行在应用层，使用UDP协议，客户端使用端口68，服务器使用端口67。

DHCP client-server interaction

步骤	消息类型	发送者	接收者	主要内容
1	DISCOVER	客户端	广播	“我需要一个IP地址”
2	OFFER	服务器	客户端	“你可以使用这个IP”
3	REQUEST	客户端	广播	“我想使用这个IP”
4	ACK	服务器	客户端	“IP已分配，租期为X”

yiaddr（your IP address）是DHCP协议中表示服务器提供给客户端的IP地址的字段。

补充：DHCP 还可以 return address of first-hop router for client，name and IP address of DNS server，network mask。

Network Address Translation: NAT

Network address translation

右边：局域网内通信，使用内部地址：10.0.0/24；左边：局域网外通信，共用唯一地址。注意，没有共用同一个端口号，因为端口号是用来区分的。比如：

WAN 侧 (对外显示)	LAN 侧 (实际主机)
203.0.113.5:50001	192.168.1.10:3345
203.0.113.5:50002	192.168.1.10:3346
203.0.113.5:50003	192.168.1.11:3345

这样布置有一个比较好的优势：可以更换 ISP 的同时不改变局域网内的地址。

注意到中间的 NAT router。它的功能如下： - 对 outgoing datagrams，把原始 IP address 和 port 更换为自己的 IP address 和 port。 - 再把上述转换记下来记为 NAT translation table。 - 对 incoming datagrams，更换。

现在回顾 NAT，不难察觉几个问题： - 如果 LAN 中的 host 想要通过 P2P 进行 communication，此时该怎么办？ - 如果一个服务器是 NAT 的 LAN 地址，怎么办？

Internet Control Message Protocol: ICMP

这个协议 used by hosts and routers to communicate network-level information。具体包括： - Error reporting. - Echo request and reply.

ICMP message 的结构包括：type、code、checksum 以及数据部分。

具体用来干什么？ - 通过发送 UDP segment，在 IP datagram header 内设置适当的 TTL，来计算 \(\text{RTT}\)。 - 还可以用来停止 source 持续发送 UDP segment。

字段名	长度	作用/说明
Type	8位	消息类型（如0=回显回复，3=目的不可达，8=回显请求）
Code	8位	消息子类型（进一步说明类型）
Checksum	16位	校验和（覆盖整个ICMP消息）
Rest of Header	32位	取决于Type和Code的其他信息
Data	可变	负载数据（例如原始数据包的片段）

IPv6

为了解决 IPv4 地址不足。具体 format 不讲，但要注意 header 大小为 \(40\) bytes，只有 address 大小变为 \(128\) bits。

Transition from IPv4 to IPv6

Tunneling

Tunneling: IPv6 carried as payload in IPv4 datagram among Ipv4 routers.

Routing Algorithms

Software-Defined Networking: SDN

实际上，network layer 可以分为 data plane 和 control plane，在 control plane 有一个 logically centralized routing controller，由它 compute paths。

Link State Algorithm

Dijkstra’s Link-State Algorithm

伪代码如下：

N = {u};
for (auto a : nodes) {
    if (isAdjacent(u, a)) {
      D[a] = Cost(u, a);
      P[a] = u;
    }
    else {
      D[a] = INF;
      P[a] = a;
      }
}
while (! all nodes in N) {
    D[a] = min(D)
    for (auto b : nodes) {
        if (isAdjacent(b ,a)) {
          D[b] = min(D[b], Cost(b, a) + D[a])
          if (D[b] == Cost(b, a) + D[a]) P[b] = a;
        }
    }
}

实际做题的时候可以参考书上的风格：

记 \(N'\) 为已找到最短路径的点集合，函数 \(D(x)\) 为到点 \(x\) 的最短路径，函数 \(P(x)\) 为点 \(x\) 的父母结点。可以规范化求解过程如下，其中 \(0\) 轮初始化。

Step	\(N'\)	\(D()\,P()\)	\(D()\,P()\)	\(\cdots\)	\(D()\,P()\)
\(0\)	\(u\)	dis node	dis node	dis node	dis node
\(1\)	\(uv\)	dis node	dis node	dis node	dis node
\(2\)	\(uvw\)	dis node	dis node	dis node	dis node
\(\cdots\)	\(\cdots\)	dis node	dis node	dis node	dis node
\(N\)	\(uvw \cdots l\)	dis node	dis node	dis node	dis node

这样可以求出从起点到图中其它点的所有最短路径。可以用来制作 forwarding table。

可以用优先队列优化时间复杂度。

这里需要提到一个概念 Oscillation possible，指的是网络路由状态可能出现反复波动、难以稳定的现象，是网络设计和协议实现中需要重点关注和避免的问题。这可能会导致在 Link State Algorithm 中计算到无穷的结果。

Distance Vector Algorithm

Distributed Bellman-Ford equation: \[D(x \to y) = \min_{v} \{\text{Cost}_{x \to v} + D(v \to y), \, D(x \to y)\}\]

其中，\(v\) 是 \(x\) 的邻居。

这是一个 iterative 算法，需要多次计算，直到收敛。计算过程可以参考课本，如下表所述，结点 \(z\) 的 table。

\(z\)	cost to
	\(x\)	\(y\)	\(z\)	\(u\)	\(v\)
from \(x\)	\(2\)	\(3\)	\(\infty\)	\(\infty\)	\(3\)
from \(y\)	\(3\)	\(\infty\)	\(\infty\)	\(2\)	\(\infty\)
from \(z\)	\(2\)	\(5\)	\(0\)	\(7\)	\(5\)
from \(u\)	\(\infty\)	\(2\)	\(\infty\)	\(\infty\)	\(2\)
from \(v\)	\(3\)	\(\infty\)	\(6\)	\(1\)	\(\infty\)

Hierarchical Routing

Internet approach to scalable routing: aggregate routers into regions known as autonomous system (AS)

AS structure

Intra-AS Routing Protocol

1. RIP: Routing Information Protocol (wasted).
2. OSPF: Open Shortest Path First (Link-State).
3. EIGRP: Enhanced Interior Gateway Routing Protocol.

OSPF: Open Shortest Path First

classic link-state: 1. Each router floods OSPF link-state advertisements (over IP) to all routers. 2. Multiple link costs metrics possible: bandwidth, delay. 3. Each router has full topology, Dijkstra algorithm.

Security: all OSPF messages authenticated

Hierarchical OSPF

Inter-AS Protocol

BGP: Border Gateway Protocol

BGP provides each AS a means to: - obtain destination network reachability information form neighboring ASes eBGP. - determine routers to other networks based on reachability information and policy. - propagate reachability information to all AS-internal routers: iBGP. - advertise (to neighboring networks) destination reachability information.

eBGP and iBGP sessions

• BGP对等体（BGP peers）通过半永久TCP连接（BGP会话）交换路由信息。
• BGP会话不一定对应物理链路。
• 当AS2向AS1通告前缀时：
  • AS2 承诺会为该前缀转发数据报。
  • AS2可以在通告中聚合前缀。
• 通过eBGP会话，AS3将前缀可达性信息发送给AS1。
• AS1内部的路由器（如1c）通过iBGP将新前缀信息分发给AS1内所有路由器。
• AS1的1b路由器可以通过eBGP会话将新前缀信息再通告给AS2。
• 路由器学到新前缀后，会在转发表中为该前缀创建条目。
• BGP通告的前缀包含BGP属性，前缀+属性即为路由。
• 两个重要属性：
  • AS-PATH：记录前缀通告经过的AS序列（如AS 67, AS 17）。
  • NEXT-HOP：指明到下一个AS的具体内部路由器（可能有多条链路）。
• 当网关路由器收到路由通告时，会根据import policy（导入策略）决定是否接受该路由。

假设有以下网络拓扑结构：

        +------+
        | AS65 |
        +------+
       /        \
      /          \
+------+        +------+
| AS23 |--------| AS17 |
+------+        +------+
   |                |
+------+        +------+
| AS45 |        | AS78 |
+------+        +------+
                 /
             +------+
             | AS99 |---前缀：192.168.99.0/24
             +------+

AS-PATH传播过程

假设AS99宣告前缀192.168.99.0/24，我们跟踪这个前缀在网络中的传播：

1. AS99向AS78通告前缀：
   • AS99向AS78发送BGP更新：192.168.99.0/24, AS-PATH={99}
   • AS78收到前缀后，将其存入路由表
2. AS78向AS17通告前缀：
   • AS78在转发前，将自己的AS号添加到AS-PATH
   • AS78发送BGP更新：192.168.99.0/24, AS-PATH={78, 99}
3. AS17向多个AS传播：
   • AS17向AS23发送：192.168.99.0/24, AS-PATH={17, 78, 99}
   • AS17向AS65发送：192.168.99.0/24, AS-PATH={17, 78, 99}
4. AS23收到两种路径：
   • 从AS17：192.168.99.0/24, AS-PATH={17, 78, 99}
   • 从AS45（假设AS45也与AS99间接相连）：192.168.99.0/24, AS-PATH={45, ..., 99}
   • AS23基于AS-PATH长度和其他策略选择最佳路径
5. AS65收到更新后：
   • 获得路由：192.168.99.0/24, AS-PATH={65, 17, 78, 99}
   • 若之后收到AS23的路由通告，也会比较两条路径

Subnet、Prefix和BGP Route的对比分析

Subnet（子网）

子网是指物理网络的逻辑划分，具有以下特征： - 由共享相同网络前缀的IP地址集合组成 - 通过网络地址和子网掩码定义（如192.168.1.0/24） - 子网内设备可直接通信，无需路由器转发 - 代表单一广播域内的网络段 - 通常属于单一管理实体

Prefix（前缀）

前缀是IP地址空间中的地址块，具有以下特征： - 用CIDR表示法表示（如10.0.0.0/8） - 表示IP地址中固定的网络部分位数 - 是路由表聚合的基础单位 - 可以表示不同大小的地址块 - 是地址分配和路由通告的基本单位

BGP Route（BGP路由）

BGP路由是互联网核心路由系统中的路由条目： - 包含目的地前缀和完整路径属性 - 核心属性包括AS_PATH（自治系统路径）、NEXT_HOP等 - 反映了网络政策和商业关系 - 用于自治系统间的路由决策 - 通过BGP协议在全球互联网中传播和交换

NEXT-HOP属性在BGP中用于指明到达目标网络的下一跳路由器IP地址，具体使用方式如下：

1. 路由转发决策
   • 当路由器接收到目标数据包时，通过查询BGP表中的NEXT-HOP属性确定实际转发目标
   • 路由器必须能够通过IGP协议(如OSPF)到达NEXT-HOP地址
2. BGP会话中的传递规则
   • eBGP传递：设置为发送更新的BGP对等体的IP地址
   • iBGP传递：保持NEXT-HOP值不变（除非明确配置修改）
   • 多出口AS：帮助选择最佳出口点
3. 策略实现
   • 通过修改NEXT-HOP实现流量工程
   • 支持热备份和负载均衡策略
   • 可设置为特定接口地址或第三方路由器地址

AS-PATH属性记录了路由通告经过的AS序列，在BGP中具有多重重要功能：

1. 路由选择依据
   • 作为BGP决策过程中的关键指标之一
   • AS-PATH越短的路径通常被优先选择
   • 影响决策优先级：Local Preference > AS-PATH长度 > Origin > MED等
2. 环路检测机制
   • 当路由器在AS-PATH中发现自己的AS号时，自动拒绝该路由
   • 避免路由环路产生，确保BGP路由收敛性
   • 例如：AS17收到路径“AS23, AS45, AS17, AS78”会直接丢弃
3. 路径操纵技术
   • 通过AS-PATH预置(prepending)增加路径长度
   • 例如：“AS78, AS78, AS78, AS99”使路径看起来更长
   • 降低特定路径被选择的可能性，实现出站流量控制
4. 路由过滤依据
   • 基于AS-PATH中的特定AS创建过滤策略
   • 可拒绝包含竞争对手或不信任AS的路由
   • 实现复杂的路由策略控制和商业关系维护

三者关系对比

特性	Subnet	Prefix	BGP Route
范围	局部网段	地址块	全球路由
用途	网络分段	地址分配与聚合	域间路由决策
包含信息	网络地址+掩码	地址块+长度	前缀+路径属性
管理层次	单一管理域内	可跨域使用	多AS协作
通告机制	不直接通告	内部路由协议	BGP协议
聚合能力	固定大小	可变大小	可聚合或特定

层次关系

这三个概念形成了一个层次结构： - Subnet：最基础，表示实际网络分段 - Prefix：中间层，表示可路由的地址块 - BGP Route：最高层，表示如何到达特定前缀的完整路径信息

一个BGP路由可以指向一个前缀，而一个前缀可以包含多个子网。

End-of-chapter exercises

P.6

Questions:

In the text we have used the term connection-oriented service to describe a transport-layer service and connection service for a network-layer service. Why the subtle shades in terminology?

Answer:

The subtle difference in terminology reflects the distinct roles and responsibilities of the transport and network layers:

• Connection-oriented service (Transport Layer):
  At the transport layer, a connection-oriented service (such as TCP) establishes, maintains, and terminates a logical end-to-end connection. This connection is defined between two processes on the end hosts (e.g., two TCP sockets). This service ensures reliable, ordered, and error-checked delivery of data across the entire network path, directly between the communicating applications.

• Connection service (Network Layer):
  At the network layer, a connection service (such as a virtual circuit) refers to the establishment of a logical path through the network, typically between routers or switches. This connection is defined between two hosts (and their intervening routers in the case of virtual-circuit networks). This path helps guide packets from source to destination but does not necessarily guarantee reliability or ordering. The focus here is on the route and forwarding of packets within the network infrastructure.

In summary:
The term “connection-oriented service” at the transport layer emphasizes end-to-end reliability and communication, while “connection service” at the network layer highlights the setup of a path through the network, without necessarily providing full end-to-end guarantees. The nuanced terminology helps clarify the different scopes and guarantees provided by each layer.

P.9

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:

Destination Address Range	Link Interface

|

11100000 00000000 00000000 00000000
through
11100000 00111111 11111111 11111111

                           |       0        |

|

11100000 01000000 00000000 00000000
through
11100000 01000000 11111111 11111111

                           |       1        |

|

11100000 01000001 00000000 00000000
through
11100001 01111111 11111111 11111111

                           |       2        |

|

otherwise

                                                                                                                        |       3        |

Questions and Answers:

a. Provide a forwarding table that has four entries, uses longest prefix matching, and forwards packets to the correct link interfaces.

Header	Link Interface(output)
11100000 00	0
11100000 01000000	1
1110000	2
otherwise	3

Explanation:
- Each entry uses the longest prefix that matches the given address range. - The router checks the destination address against each prefix, starting from the longest, and forwards the packet to the corresponding interface.

b. Describe how your forwarding table determines the appropriate link interface for datagrams with destination addresses:

11001000 10010001 01010001 01010101

11100001 01000000 11000011 00111100

11100001 10000000 00010001 01110111

1. 11001000 10010001 01010001 01010101
   • This address does not match any of the specified prefixes (does not start with 111…), so it is forwarded to interface 3.
2. 11100001 01000000 11000011 00111100
   • This address matches the third entry:
     • Prefix: 1110000
     • So, it is forwarded to interface 2.
3. 11100001 10000000 00010001 01110111
   • This address matches the third entry:
     • Prefix: 1110000
     • So, it is forwarded to interface 2.

P.10

Consider a datagram network using 8-bit host addresses. Suppose a router uses longest-prefix matching and has the following forwarding table:

Prefix Match	Interface
00	0
010	1
011	2
10	2
11	3

Question and Answer:

For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range.

Interface	Destination Address Range	Number of Addresses
0	00000000 - 00111111	64
1	01000000 - 01011111	32
2	01100000 - 01111111 10000000 - 10111111	96
3	11000000 - 11111111	64

P.17

Question and Answer:

Consider sending a 2400-byte datagram into a link that has an MTU of 700 bytes. Suppose the original datagram is stamped with the identification number 422. How many fragments are generated? What are the values in the various fields in the IP datagram(s) generated related to fragmentation?

According to IPv4 datagram format, each fragment includes a 20-bytes header.

先计算数据大小 \(d = \lfloor \frac{700 - 20}{8} \rfloor \times 8 = 680\) bytes。

所以需要分成 \(n = \lceil \frac{2400 - 20}{d} \rceil = 4\)

主要变化在 Offset 和 Flag，所以：

Fragment	Datagram length	Offset	Flag
1	700	0	001
2	700	85	001
3	700	170	001
4	360	255	000

P.18

Question and Answer:

Suppose datagrams are limited to 1,500 bytes (including header) between source Host A and destination Host B. Assuming a 20-byte IP header, how many datagrams would be required to send an MP3 consisting of 5 million bytes? Explain how you computed your answer.

MTU 为 \(1500\) bytes，一个 datagram 的 data 大小为 \(d = \lfloor \frac{1500 -20}{8} \rfloor \times 8 = 1480\) bytes。

最终，datagram 的数目为 \(n = \lceil \frac{5 \times 10^6}{d} \rceil = 3379\) 个。

P.19

Consider the network setup in Figure 4.22. 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.

Network address translation

Questions and Answers:

a. Assign addresses to all interfaces in the home network.

也即是说，中间的 router WAN 的 IP address 是 24.34.112.235，LAN 的是 192.168.1/24，不妨和原图一样，设为 192.168.1.4。则右边的三个 host 的 LAN IP address 分别为：

• Host 1 address is 192.168.1.1
• Host 2 address is 192.168.1.2
• Host 3 address is 192.168.1.3

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.

总共有 \(6\) 个 TCP connection，随便分几个端口号：

WAN side	LAN side
24.34.112.235, 50001	192.168.1.1, 3345
24.34.112.235, 50002	192.168.1.1, 3346
24.34.112.235, 50003	192.168.1.2, 3345
24.34.112.235, 50004	192.168.1.2, 3346
24.34.112.235, 50005	192.168.1.3, 3345
24.34.112.235, 50006	192.168.1.3, 3346

P.24

Graph P.24

Question:

Consider the following network. With the indicated link costs, use Dijkstra’s shortest-path algorithm to compute the shortest path from x to all network nodes. Show how the algorithm works by computing a table similar to Table 4.3.

Answer:

\(N' = \{x\}\)

step	\(D(x)\) \(P(x)\)	\(D(y)\) \(P(y)\)	\(D(z)\) \(P(z)\)	\(D(v)\) \(P(v)\)	\(D(u)\) \(P(u)\)	\(D(w)\) \(P(w)\)	\(D(t)\) \(P(t)\)	\(N'\)
0	\(0\) \(x\)	\(6\) \(x\)	\(8\) \(x\)	\(3\) \(x\)	\(\infty\)	\(6\) \(x\)	\(\infty\)	\(x\)
1	\(0\) \(x\)	\(6\) \(x\)	\(8\) \(x\)	\(3\) \(x\)	\(6\) \(v\)	\(6\) \(x\)	\(7\) \(v\)	\(xv\)
2	\(0\) \(x\)	\(6\) \(x\)	\(8\) \(x\)	\(3\) \(x\)	\(6\) \(v\)	\(6\) \(x\)	\(7\) \(v\)	\(xvy\)
3	\(0\) \(x\)	\(6\) \(x\)	\(8\) \(x\)	\(3\) \(x\)	\(6\) \(v\)	\(6\) \(x\)	\(7\) \(v\)	\(xvyu\)
4	\(0\) \(x\)	\(6\) \(x\)	\(8\) \(x\)	\(3\) \(x\)	\(6\) \(v\)	\(6\) \(x\)	\(7\) \(v\)	\(xvyuw\)
5	\(0\) \(x\)	\(6\) \(x\)	\(8\) \(x\)	\(3\) \(x\)	\(6\) \(v\)	\(6\) \(x\)	\(7\) \(v\)	\(xvyuwt\)
6	\(0\) \(x\)	\(6\) \(x\)	\(8\) \(x\)	\(3\) \(x\)	\(6\) \(v\)	\(6\) \(x\)	\(7\) \(v\)	\(xvyuwtz\)

So the shortest path from \(x\) to all nodes is follow.

Destination	Shortest Distance	Path
\(x\)	\(0\)	\(x\)
\(v\)	\(3\)	\(x \to v\)
\(y\)	\(6\)	\(x \to y\)
\(w\)	\(6\)	\(x \to w\)
\(u\)	\(6\)	\(x \to v \to u\)
\(t\)	\(7\)	\(x \to v \to t\)
\(z\)	\(8\)	\(x \to z\)

P.26

Graph P.26

Question:

Consider the network shown below, and assume that each node initially knows the costs to each of its neighbors. Consider the distance-vector algorithm and show the distance table entries at node z.

Answer:

Node z table:

First round

	cost to
	x	y	z	u	v
from x	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)
from y	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)
from z	2	\(\infty\)	0	\(\infty\)	6
from u	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)
from v	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)

Second round

	cost to
	\(x\)	\(y\)	\(z\)	\(u\)	\(v\)
from \(x\)	\(2\)	\(3\)	\(\infty\)	\(\infty\)	\(3\)
from \(y\)	\(3\)	\(\infty\)	\(\infty\)	\(2\)	\(\infty\)
from \(z\)	\(2\)	\(5\)	\(0\)	\(7\)	\(5\)
from \(u\)	\(\infty\)	\(2\)	\(\infty\)	\(\infty\)	\(2\)
from \(v\)	\(3\)	\(\infty\)	\(6\)	\(1\)	\(\infty\)

Because the question only asks to show the distance table entries at node z, we do not need to compute the full routing tables for all nodes. The Second round result about node z is also the finial result. 到这一步 from z to other 的 cost 表就收敛了，题目也只问了 node z。