Computer Networking A Top-Down Approach 笔记

Chapter 1: Computer Networks and the Internet

1.1 What Is the Internet?

在这本书中我们使用 public Internet（一种特定的计算机网络）作为讨论计算机网络、协议的主要途径。但是什么是 Internet？

• 首先我们可以讨论 nuts and bolts（基本组成部分） of the Internet，即组成 Internet 的基本硬件、软件
• 我们可以在为分散的各种应用提供服务的互联网基础设施这方面讨论

1.1.1 A Nuts-and-Bolts Description

The Internet 是一个将几十亿全世界计算设备互相连接的计算机网络。

在互联网，这些设备被称作 hosts 或者 end systems。据估计，在 2015 年大约有 50 亿设备连接到互联网，在 2020 这个数字达到了 250 亿。

end systems 被一个由 communication links 和 packet switches 的网络连接起来。不同的 links 以不同的传输率 transmission rate 传输数据（bits/second）。

当一个 end system 有数据传输到另一个 end system，发送方将数据分段并且给每个段 segment 加一个头部 header 。这样组成的信息包以计算机网络的属于被称为 packet。

一个 packet switch 接受来自一个输入端的 packet 然后 forwards 到一个 communication links。最著名的 packet switch 是 router（路由器）和 link-layer switch（链路层交换机）。后者通常用于 access network（接入网）中，前者通常用于 network core（网络核心）中。

从发送端到接收端的路径被称为 route 或者 path（through the network）

End systems 通过 Internet Service Providers（ISPs，网络业务提供商）连接到互联网。分为居民 ISPs（local cable 或者电话公司）；企业 ISPs；大学 ISPs；在机场、旅店提供 wifi 的 ISPs。每个 ISP 内部是一个 packet switches、communication links 的网络。

End systems，packet switches 以及其它互联网组件都运行着 protocols（协议）。协议控制着互联网内发送、接受信息的行为。

• Transmission Control Protocol（TCP）
• Internet Protocol（IP），IP 协议制定了包的格式。

Internet 最重要的协议合起来就叫做 TCP/IP。

由于协议在互联网中很重要，所有人对协议的统一认识是很重要的，这就是 standards（标准）起作用的地方。Internet standards（互联网标准）由 IETF（Internet Engineering Task Force，互联网工程任务组）制定，他们的文档称作 requests for comments（RFCs）。RFC 定义了很多协议（TCP、IP、HTTP、SMTP等），现在有 7000 多 RFCs。

1.1.2 A Services Description

我们上面通过组成要件的视角讨论了互联网，但是我们还能通过“给应用提供服务的基础设施”这么一个角度讨论。

各种应用被称为 distributed applications（分布式应用），因为他们包含了许多互相交换信息的 end systems。比较重要的是，互联网应用运行在 end systems 上——而不运行在 network core 的 packet switches 上。

附着在互联网上的 end systems 提供了一个 socket 接口，这一接口制定了一个 end system 上的程序怎样让互联网设施传输消息到一个指定目的地。

互联网给应用提供了许多 services，应用开发这需要选择其中来使用。

1.1.3 What Is a Protocol

两个（或多个）的 communicating entities 需要运行相同的协议来共同完成一个任务。

所有两个或更多的交流实体参与的互联网活动都由协议来保证。

一个协议定义了两个交流实体间传递信息的“格式”和“顺序”，以及在传递、接受信息或者其它事件时所做的行为。

1.2 The Network Edge

在本 section 中，我们来专注于互联网的 edge——即 end systems 或者说 hosts。

hosts 被粗分为两类：clients 和 servers。

1.2.1 Access Networks

在认识到 end systems 是互联网的边缘之后，我们来考虑接入网——也就是物理上将 end systems 连接到一级路由器（也叫 edge router，边缘路由器）的网络。

家庭接入：DSL（数字用户线路）、Cable（缆线）、FTTH（Fiber To The Home，光纤到户）、Dial-Up、Satellite

• DSL：使用普通双绞铜线（电话线），速度不如但便宜
• Cable：使用有线电视同轴线，速度快延迟低，使用广泛，但是峰值速度低。
• FTTH：使用很薄的玻璃纤芯（光纤），速度快、传输距离长但是贵。

企业接入（家庭也逐渐使用）：Ethernet（以太网）and WiFi

在公司和一些家庭中，一个 local area network（LAN，本地局域网）被用于将一个 end system 与 edge router 相连接。虽然有很多种 LAN 技术，Ethernet 是最流行的技术。以太网用户使用双绞铜线连接到一个以太网交换器，然后交换器连接到一个路由器。

然而逐渐的，人们正无线地连接到互联网。在一个无限的局域网设置中（wireless LAN），无限用户通过一个接入点（Access Point，AP）（这个接入点有线地连接在企业网络中，常用的还是有线的以太网），这一就连接上了有线网。无限 LAN 基于标准 IEEE 802.11 技术，也就是广为人知的 WiFi。

广域的无线接入：3G 和 LTE

和 WiFi 不同的是，用户在一个基站的几十千米处也能上网（WiFi 需要很近）。

1.2.2 Physical Media

双绞铜线、同轴电缆、光纤、地面无线电通信、卫星无线电通信。

1.3 The Network Core

在品鉴完 Network Edge 后，我们来深入研究一下 Network Core —— packet switches 和 links 组成的网络，连接着 end systems（中间部分），通常就是 ISP 那边内部连的。

1.3.1 Packet Switching

一个 packet（大小为 L bits）通过一个传输率为 R bits/sec 的 link 发送数据，那么需要 L/R 的时间。

Store-and-Forward Transmission

大部分 packet switches 在输入的连接上使用 store-and-forward 传输策略。这意味着这个 packet switch 必须收到完整的包（packet）后才能往输出链路上发送第一个 bit。

所以当它收到第一个 bit 的时候，它必须把它 buffer 起来，直到收到一个 packet 的所有 L 个 bits，然后开始发送。所以两个 link 中间有个 packet switch 的结构，假设两个 link 都是 R，由于 saf，总传输时间是 2L/R。如果不采用这个策略（直接传输），那么这个两个 link 直接可以看作一条带，那么总时间就是 L/R。

Queuing Delays and Packet Loss

每个 packet switch 都有很多 links 连接它。对于每一个连接到它的 link，它都要维护一个 output buffer/queue，储存着要发给这个 switch 的 packets。如果有个包需要使用这个 link 但是它正忙，它就必须在 output buffer 里 wait。所以除了 store-and-forward delay，这里产生了 queuing delays，这个 delay 由网络的拥塞情况决定。由于 buffer 是有限的，如果 buffer 满了，就会发生丢包（packet loss）——将进来的包或者队列里中的某个包将会丢掉。

Forwarding Tables and Routing Protocols

Forwarding Table 简单说就是 router 维护了一个 destination 地址（或者它的一部分）到它的出边的映射。问题：这玩意儿一开始是怎么建起来的？答案是采用了特殊的路由协议自动建立起。一个路由协议可能会找一条最短路，然后根据这个建立 forwarding table。

1.3.2 Circuit Switching

在一个由 links 和 switches 构成的网络中，有两种基本的方式来传输数据：circuit switching 和 packet switching。

在一个电路交换的网络中，一条路径所需的用来提供给 communication 的资源（buffers，link transmission rate）在 communication session 期间是被 reserved 的。而在一个 packet-switched network 中，这些资源没有被 reserved。一个 session 的消息按需使用资源，并且也因此，可能需要等待（queue）。

传统的电话网络就是电路交换的一个例子。在两个人可以交换信息之前，该网络必须在两者间建立一个连接。以电话通讯的属于来说，这个连接就被称作 circuit。当 circuit 被建立时，它也同时在这个网络的 links 上预定了一个固定的传输率（即代表了每一个链路上的一部分传输能力），这也就意味着可以确保以某一确定速率来传输数据。

Multiplexing in Circuit-Switched Networks

在一个 link 中的 circuit 用 FDM（frequency-division multiplexing，频分复用） 或者 TDM（time-division multiplexing） 策略来实现。

使用 FDM 时，一个 link 的频谱按所有通过这个 link 的连接来分割。更准确地说，这个 link 给每一个给每一个连接都分配了一个频段。在电话网络中，这个频段通常有着 4kHZ 的宽度。这个频段的宽度被称作带宽，bandwidth。

对于一个 TDM 链接，时间被划分为固定长度的“帧”，并且每一帧被划分为固定数量的 time slots。当这个网络建立起一个通过某一个 link 的 connection，它给这个连接在每个帧中分配了一个 time slot。这些 slots 为这个连接所独用。每个 time slot 都可以用来在这个时候传输数据。

对于 TDM，某个 circuit 的传输率等于每秒帧数乘以每个 slot 的 bit 数。

packet switching 的支持者总是宣称 circuit switching 很浪费，因为分配到电路在某些时候是空闲的（idle）。例如，当一个打电话的人暂时停下通话时，这个空闲资源无法被其他人所用。

例：发一个 640000 bits 的文件，网络使用 TDM，每个帧有 24 slots，总 bit rate 为 1.536 Mbps。那么传输需要多少时间？首先对于一个 circuit，由于时分复用，传输率为 1.536Mbps/24 = 64kpbs。所以所需要的时间为 640 kbits/64 kpbs = 10 sec。当然还需要加上一点建立连接的开销。

Packet Switching VS Circuit Switching

packet switching 的批评者通常宣称 packet switching 不适合一些 real-time services（例如通话、视频会议，因为它延迟的可变性和不确定性。这主要是 queuing delays 的不确定性）。而支持者认为它提供了更好的传输能力复用，并且它简单、高效并且易于实现。

为什么 Packet Switching 更高效？假设用户共享一个 1 Mbps 的 link，并且假设每个用户有活跃期和冷静期，活跃期以 100kbps 速率生成数据，冷静期不生成数据。进一步假设每个用户只有 10% 的时间活跃。在电路交换下，100 kbps 都要为每一个用户长期预留。例如，使用 TDM，如果每个 frame 由 10 个 slots 组成，每个 frame 100ms，那么每个用户每帧会被分配一个 time slot。

因此，电路交换只能支持 10 个同时存在的用户。而使用 packet switching，假设用户的活跃率是 0.1，如果有 35 个用户，那么同时有 >=11 个同时活跃的用户的概率大约只有 0.0004 （二项分布）。所以总计数据代打率小等于 1 Mbps，这也是这个 link 的 output rate。因此，在大概率情况下，分组交换可以无延迟地进行传输。当 >=11 个用户时，包的到达速率超过了 link 的输出能力，那么 queue 开始变长。由于这个概率很小，因此分组交换在这时几乎和电路交换提供相同的分布，但它提供了三倍的用户支持量。

考虑另一个简单的例子。假设有 10 个用户，并且一个用户瞬间产生了一千个 1000-bit 的包，而其它用户此时不产生包。使用 TDM 电路交换，10 slots，每个 slot 1000 bits，那么活跃用户每个 frame 只能使用一个 slot，剩下 9 个都是 idle。那么大概就需要 10 sec。而使用分组交换，活跃用户此时可以使用 link 的所有资源，所以只需要 1 sec。

尽管在当代的通信网络中两种方式都很流行，packet switching 却逐渐成为主流。

1.3.3 A Network of Networks

我们之前讨论过 end systems，它通过 access ISP 接入互联网。access ISP 使用 DSL，cable，FTTH，WiFi 等技术。但是不同的 access ISP 之间也需要连接起来，这件事通过创建一个 “网络的网络，network of networks” 来实现。

随着时间的推移，网络的网络已经演化成了一个非常复杂的结构。许多演化是一位经济、国家的政策而非对效率的考量。为了理解现代的互联网结构，我们来逐渐地建立起一系列网络结构。回忆一下，我们整个架构的目标是为了将不同的 access ISP 相互连起来，使得所有的 end systems 可以相互发包。一个简单的方法是将每个 access ISP 和其它所有 access ISP 相互连起来，但是这样代价太高了（全世界有很多很多 ISP）。

我们的第一个结构，是将所有的 ISP 连接到一个 global transit ISP。我们想象中的 imaginary global transit ISP 是一个 routers 和 links 组成的网络，它需要在全世界分布，并且对于每一个 access ISP 都要至少有一个比较靠近的 router。当然，这花费也很高。为了利润，自然对每个接入的 access ISP 都要收费，并且收费以它们之间的通信量为准。因此 access ISP 被叫做 customer，global transit ISP 被称作 provider。

现在如果一些公司建立起了一个能获利的 global transit ISP，那么其它公司自然也会建造它们自己的 global transit ISPs 并且相互竞争，这产生了新的网络结构，由成百上千个 access ISPs 和一些 global transit ISPs 组成。access ISPs 当然更喜欢新的这种结构，因为它们现在可以根据性能、价格选择一个 global transit providers。注意到，这时候 global transit ISPs 之间也必须相互连接起来。

上面这个新的结构只是描述了了一个两层结构（two-tier hierarchy）。而在现实生活中，没有 ISP 能够在所有城市出现并且连接上当地的 access ISPs，因此需要有地域 ISP（a regional ISP）。每个地域 ISP 之后连接到一级 ISP，也就是我们想象中的 global transit ISP。世界上大概有十多个 tier-1 ISP。

回到这个网络的网络，这里不仅有一级 ISP 的竞争，还要同一个地域的不同 regional ISP 的竞争。在这样一个架构下，每一个 access ISP 给它所属的 regional ISP 付费。并且每一个 regional ISP 给每一个它连接的 tier-1 ISP 付费。（access ISP 也可以直接连接 tier-1 ISP）注意到 tier-1 ISP 不给谁付费，因为它是这个层级的顶点。更复杂地，有些地方可能有 larger regional ISPs 和 smaller regional ISPs。

为了更贴近现在的网络结构，我们必须要添加 PoPs，multi-homing，peering，以及 IXP。PoPs（接入点） 就是provider‘s network 中的一群 routers。customer ISPs 可以通过这里连接上 provider ISP。multi-home 就是一个 access ISP 可以连接很多个上层的 ISPs。这样如果一个 provider 失败了它还是能照常工作。

为了减少花费，一些靠近的 customer ISPs 可以 peer，也就它们可以直接互相连接，不用经过第三方。第三方公司可以创建一个 IXP（Internet Exchange Point），这是一个许多 ISPs peer 起来的共通点。

最后，我们终于到达了今天的互联网结构，只要再在层级顶端加上 content-provider networks（Google）。

1.4 Delay, Loss, and Throughput in Packet-Switched Networks

计算机网络有时必需限制 throughput，带来 delays，并且可能 lose packets。在一方面，很不幸的是现实的物理定律会带来这些问题。在另一方面，由于计算机网络有这些问题，就有许多措施去解决这些问题。这一章我们主要来检视、量化计算机网络中的 delay，loss 和 throughput。

1.4.1 Overview of Delay in Packet-Switched Networks

当 packet 顺着路径传输时，有很多种 delays：

• nodal processing delay
• queuing delay
• transmission delay
• propagation delay

这些 delay 合起来成为一个 total nodal delay。

Types of Delay

router A 有一个 outbound link 到 router B。这个 link 前有一个 queue（buffer）。当一个 packet 到达 router A，它会先检查这个 packet 的 header 来确定合适的 outbound link，然后将包往这个出边发送。这个 packet 能被 transmit 到这个 link 上，当且仅当没有包正在 link 上传输并且没有其他包在这个队列前（即它是队首）。否则，这个包将会被 queue。

Processing Delay

就是 router 检查 packet 并且决定哪个出边的过程。

Queuing Delay

当 packet 在 queue 中等待着被 transmit 时，这部分 delay 被称作 queuing delay。

Transmission Delay

这部分时间是用来把 packet 的所有 bit push 到 link 上所用时间。如果包有 L bits，link 有 R bps，那么 transmission delay 就是 L/R。

Propagation Delay

当一个 bit 被 push 到 link 上时，它需要在 link 上传播。这部分时间是 bit 顺着 link 走的所用时间，范围大概是 $2 \times 10^8$ m/sec - $3 \times 10^8$ m/sec。注意它和 transmission delay 的区别。

1.4.2 Queuing Delay and Packet Loss

令 a 为平均的 packet 到达率，单位为 packet/sec。R 为传输率，bits/sec。packet 大小为 L bits。那么定义 traffic intensity（通信量强度）为 La/R，这个量在估计 queuing delay 中能起到重要作用。如果 La/R > 1，那么比特的平均到达率超过了比特的平均传输速率。在这个情况下，queue 会无限增长，并且 queuing delay 会到达无穷。所以黄金准则是，Design your system so that the traffic intensity is no greater than 1.

现在考虑 La/R <= 1 的情况。这里，通信情况到来的性质影响了 queuing delay。例如，如果 packets 间歇性到来，每 L/R 秒来一个 packet，那么每个 packet 到达时队列都是空的，此时 queuing delay 就是 0。而另一方面，如果 packets 在一段时间内爆发性到来（不过还是 periodically 的），那么将会产生一个有意义的平均 queuing delay。例如，假设 N 个 packets 在每 (L/R)N seconds 同时到来，那么第一个 packet 没有 queuing delay，第二个 packet 就有 L/R 的 queuing delay，…，第 N 个 packet 就有 (N-1)L/R 的 queuing delay。

上述的两个例子都有点太学术了。而通常的，这个到达的过程是随机的，也就是不遵循任何模式，packets 在时间上均匀地分布。在这个更真实的例子，量 La/R 通常不再够用来完全刻画 queuing delay。尽管如此，它对我们用直觉理解估计出一个 queuing delay 的范围很有帮助。特别地，如果 traffic intensity 很靠近 0，那么 packet 到达得很少并且一个 packet 很难发现领域给 packet 在队列中。因此，平均的 queuing delay 也将趋于 0。另一方面，如果 traffic intensity 趋于 1，那么将会有到达率超过传输能力的一段时间（因为 packet arrival rate 通常是变化的），在这段时间内 queue 将会形成；当到达率小于传输能力时，队列长度将会减少。尽管如此，随着 traffic intensity 到达 1，平均队长将会越来越大。

（图：La/R = 1 是渐近线。也就是说 La/R -> 1，平均 queuing delay 趋于无穷。）

Packet Loss

在我们前面的讨论，我们假设 queue 可以容纳无限多的 packets。而现实中一个 link 前面的 queue 只有有限大的容量，尽管 queuing 能力很大程度上取决于 router 的设计和花费。因为 queue 容量是有限的，随着 La/R 接近 1，packet delays 不会真的到达无穷。取而代之，当一个 packet 遇到一个满队列时，router 会 drop 这个 packet。

从 end-system 的视角看，一个丢包时间看起来像这个 packet 传入了 network core 但是永远没有从目的地那出来。因此，一个 node 的性能不应当只以 delay 衡量，还应当考虑丢包率。

1.4.3 End-to-End Delay

我们前面的讨论集中于 nodal delay，也就是一个 router 上产生的 delay。现在我们来考虑从 source 到 destination 的总 delay。假设有 N-1 个 routers，并且假设网络此时不拥堵（可以不考虑 queuing delay），那么总 delay 就是

$$d_{end-end} = N(d_{proc} + d_{trans} + d_{prop})$$

在这里 $d_{trans} = L/R$。

Traceroute

略

End System, Application, and Other Delays

end systems 上也有一些 delays 可能会发生。比如，一个 end system 希望将一个包传输到一个共享介质上，可能会故意延迟这个传播来实现某一协议（这个行为时为了能够正常和其它 end systems share 这个介质）。另一个重要的 delay 是 media packetization delay（将信息打包成 packet 花的时间）

1.4.4 Throughput in Computer Networks

除了 delay 和 packet loss 外，另一个关键的性能衡量标准是 end-to-end throughput（吞吐量）。为了定义 throughput，考虑从 A 到 B 传输一个大文件。instantaneous throughput（瞬时吞吐量）是 B 接收到这个文件的速率（bits/sec）（许多应用在下载时会显示这个数值）。如果这个文件由 F bits 组成且从 A 到 B 需要花费 T seconds 来传输这个文件的所有 bits，那么 average throughput（平均吞吐）就是 F/T bits/sec。对于一些应用，比如互联网通话，它们需要低延迟以及稳定低于某个 threshold 的瞬时吞吐。对于其它应用，比如文件传输，delay 不重要，但是 throughput 越高越好。

假设 server 和 client 之间只有一个 router，server 到 router 之间的传输率为 Rs，router 到 client 之间的传输率为 Rc。在这个理想场景下，server-to-client 的 throughput 是多少？我们需要把数据看成流（fluid），这些 links 看作管道（pipe），也就是源源不断的。显然，如果 Rs < Rc，那么传输到 router 的数据会很快地被传输到 client，这时候 throughput 就是 Rs；如果 Rs > Rc，那么前面的过程就是快的。因此，一条路上的 throughput 在这个模型下就是 min{Rs, Rc}，也即由 bottleneck link 决定。如果要传输一个大小为 F bits 的文件，可以简单估计时间为 F/min{Rs, Rc}。

推广：min{R1, R2, …, RN}

考虑另一个例子，server 以 Rs 的 link 接入网络，client 以 Rc 的 link 接入，假设网络内部的传输率都非常高。那么此时 throughput 还是 min{Rs, Rc}。事实上，现代互联网 throughput 的主要限制因素确实就是接入网。

最后一个例子，考虑 10 个 servers 和 10 个 clients 连到一个 network core。这个例子里可以有 10 对 client-server，中间连了一个共同的 link R。每个 client 都是以 Rc 接入，每个 server 都是以 Rs 接入。那么如果 R 很大，那么每个 client-server 的 throughput 还是 min{Rc, Rs}；但是如果 R 不是那么大，那么可能 bottleneck 就会变成它，也就是 R/10（假设它们同时在传输的话）。

1.5 Protocol Layers and Their Service Models

讨论到这里，显然互联网是一个极端复杂的系统。那么有什么办法可以组织整理一个网络的体系结构呢？

1.5.1 Layered Architecture

（前面是一大段类比）一个分层的架构让我们可以讨论一个良好定义的巨大、复杂系统的某一特定部分，。这一简化其实是一种模块化的思想，它让改变某一层的服务变得简单。只要某一层向上层提供的都是相同的服务，并且也使用下层的相同服务，那么即使某一层的实现改变了也不影响系统的其它部分。

Protocol Layering

为了提供设计网络协议的架构，网络设计师们将协议以及实现协议的软硬件按层级组织。每一个 protocol 都属于一个层。我们对一个层向它上层提供的服务感兴趣，这就是所谓的 service model（服务模型）of a layer。

一个协议可以被软件，硬件或者二者协同实现。应用层的协议——例如 HTTP 和 SMTP——大多数都是软件上由 end-systems 实现的，传输层协议也是如此。由于物理层和数据链路层需要处理一个特定 link 上的通信，它们通常被实现在一个网卡上。网络层通常是软硬件混合实现的。

分层提供了一个结构化的视角让我们来讨论系统构建，模块化使得更新系统部件变得更容易。但是也有一些人反对，因为一个缺点是层与层之间可能有冗余功能（干了相同的事），例如许多协议栈提供了纠错服务（per-link and end-to-end）另一个可能的缺点是某一层所需的人信息可能出现在另一层，这违反了分层的目标。

不同层的协议被叫做 protocol stack（协议栈）。因特网协议栈由五层组成——物理层，链路层，网络层，传输层和应用层。我们使用一个自顶向下的视角，首先来看应用层然后再往下。

Application Layer

应用层是网络应用和应用层协议所在的地方。因特网应用层包含了许多协议：HTTP，SMTP 和 FTP 协议。将人类友好的域名转化为 32 位的网络地址也是通过一个特定的应用层协议——DNS 完成的。

一个应用层协议分布在许许多多不同的 end systems 上。我们将应用层的 packet 也称作 message。

Transport Layer

传输层负责在应用端点（endpoints）之间传输应用层的 message，即负责两个主机之间进程到进程，端口到端口的通信。在互联网中有两种传输层协议——TCP 和 UDP。TCP 提供一个连接导向的服务，它保证了信息传递，提供了流控制 flow control，将长 message 打碎成 segments，以及提供了一个拥塞控制机制。UDP 提供了一个无连接服务，没有可靠性，没有流控制，没有拥塞控制。我们将传输层的 packet 称作 segment。

Network Layer

网络层负责将网络层的 packets（被称作 datagrams）从一个主机（host）到另一个。传输层的协议从一个 source host 出发，将一个传输层的 segment 传输到一个网络层的目标地址。网络层给传输层提供了将一个 segment 发送到目标地址的服务。

因特网的网络层包含了著名的 IP 协议，它们定义了 datagram 中的 fields 以及 end systems 和 routers 如何对这些 fields 作出 action。因特网有很多路由协议（routing protocol），因为它是一个网络的网络。尽管网络层同时有 IP 协议和许多路由协议，但由于 IP 重要的胶水作用，网络层也被称作 IP 层。

Link Layer

网络层通过一系列 source 和 dest 之间的 routers 来路由一个 datagram。为了将一个 packet 从一个 node 移动到另一个 node，网络层依赖于链路层的服务。特别地，在每一个 node，网络层将 datagram 向下传递到链路层，链路层根据 route 发送到下一个 node。在下一个 node，链路层再将 datagram 向上传回网络层。

链路层提供的服务取决于特定的使用在 link 上的链路层协议。链路层协议的例子有 Ethernet，WiFi 和 cable access network 的 DOCSIS 协议。链路层的 packets 被称作 frame。

Physical Layer

物理层的任务是将帧中独立的 bit 从一个 node 传输到另一个。这层协议不仅 link dependent，还 depend on 具体的传输介质。

The OSI Model

Internet protocol stack 不是唯一的协议栈。在 1970s，ISO 提出了 OSI 七层模型。

1.5.2 Encapsulation

routers 和链路层的 switches 都是 packet switches。相似地，它们也按层组织软硬件，但是它们不用实现协议栈的所有层。链路层 switch 实现了链路层和物理层，router 多实现一个网络层。这意味着链路层 switches 无法识别 IP 地址而只能识别 MAC 地址。

封装概念：一开始是一个 application-layer message，然后加上传输层的 header 变成了传输层的 segment。添加上的内容可能包含纠错码等信息。然后传给网络层，加上了网络层的 header，比如 source 和 dest 的 end system 地址，产生了 network-layer datagram。然后再加上 link-layer 的 header 形成 link-layer frame。因此，我们可以看到每一层一个 packet 有两个 fields：header 和 payload。payload 就是上层的完整 packet。

1.6 Networks Under Attack

略

1.7 History of Computer Networking and the Internet

略

Chapter 2: Application Layer

在本章中我们研究网络应用层上的概念和实现。我们从定义一些关键的应用层概念开始，包括应用层需要的网络服务，clients 和 servers，进程和传输层接口。我们仔细考察了一些网络应用，包括 Web，email，DNS，P2P 文件分布存储和视频流。然后我们介绍了网络引用的开发，基于 TCP 和 UDP。特别地，我们研究 socket 接口并且在 python 尝试了一些简单的 client-server 应用。我们也提供了一些有趣的 socket 编程作业。

2.1 Principles of Network Applications

网络应用开发的核心是写在 end systems 上运行的程序并且通过网络互相通信。例如浏览器程序运行在 user 的 host 上，而 web server 程序运行在 Web server host 上。再例如，在一个 P2P 文件共享系统上，每个 host 都运行着一个相同的程序。

特别地，你不需要写在 network-core devices 上运行的程序，例如 routers 或 链路层 switches（即使你想也做不到）。

2.1.1 Network Application Architectures

记住一个 application 的 architecture 和 network architecture（例如，之前提到的五层互联网架构）有兵线不同。从应用开发者的视角，network architecture 是固定的并且提供特定服务的。而 application architecture，在另一方面，是由 application developer 设计的并且决定了 application 是怎样在不同的 end systems 上形成架构的。有两种主要的 application architecture：client-server architecture 和 peer-to-peer architecture。

在一个 client-server 架构，有一个始终运行（always-on）的 host 叫做 server，它处理者从许多其它 hosts（叫做 clients）来的许多服务请求。许多出名的应用如 Web，FTP，Telnet 和 e-mail 都是这个架构。

通常在一个 cs 架构，单服务器难以承受持续到来的所有 client 的 request。因此，data center，集结了许多 hosts，经常被用于创造一个强大的 virtual server。

在一个 P2P 架构，应用在成对的 hosts 间直接沟通，称作 peers。这些 peers 不是由 service provider 拥有的，而是用户控制的 desktop 和 laptop。（BitTorrent，Xunlei，Skype）

P2P 架构的一个最引人注目的特性是它的 self-scalability（自扩展性）。在 P2P 中，每个 peer 既给网络增加了 workload，也增加了这个系统的服务能力。但是 P2P 也面临着安全，性能和 reliability 方面的挑战。（由于它高度去中心化的结构）

2.1.2 Processes Communicating

按操作系统的用词，实际上在通信的不是程序（programs）而是进程（processes）。一个 process 可以被看作一个运行在特定 end system 上的 program。当 processes 运行在相同 end system 上时，它们可以通过 IPC（interprocess communication） 之类的来通信，使用 os 提供的服务。

而 processes 位于两个不同的 end systems 上通过在计算即网络上交换 message 来互相通信。

Client and Server Processes

对于一对通信中的 processes，我们可以特别将其中一个称为 client，另一个称为 server。你会发现在一些 app 中，比如 P2P 文件共享，一个 process 既可以是 client 也可以是 server。尽管如此，在任意一个给定一对 process 通信会话（ session） 的上下文中，我们仍然可以分出 client 和 server。特别地，定义初始化这个 communication 的 process 为 client，等待被 contact 来开始 session 的进程叫做 server。

The Interface Between the Process and the Computer Network

一个进程通过一个计算机网络中的软件接口叫 socket 来发送、接受信息。类比就是，一个 process 就像一个房子，而 socket 是它的门。当一个进程想和另一个进程通信，它将信息推出它自己的门外。这个发送 process 假设在它的门另一端有一个传输设施，会将这个 message 传输到目的地的门前。当信息被送到时，接收方的门会收到消息，然后接收方会根据消息做出 action。

一个 socket 是应用层和传输层之间的 interface，它也叫做 application 和 network 之间的 API（Application Programming Interface）。应用开发者可以完全控制 socket 在应用层这边的部分，但是几乎无法涉及它在传输层那边的部分（只能选择传输协议、修改一些参数比如 maximum buffer 等）。

Addressing Processes

为了将 packets 发送到另一个 host，接受 process 需要有一个地址。为了识别接受的 process，两部分信息应该被指定：1. 接收方 process 所在的 host 的地址；2. 一个在 host 中识别该 process 的标识符。

在 Internet 中，host 被 IP 地址唯一识别。现在，我们对 IP 地址所知的就是它是一个 32-bit 的可以唯一确定 host 的地址。以及一个目标 process 的端口号（port number）能达到第二个目的。流行的应用通常被分配了特定的端口号。例如，一个 Web 应用被分配 80 端口号，一个 mail 应用被分配 25 端口号。

2.1.3 Transport Services Avaliable to Applications

回忆一下，一个 socket 是 application process 和传输层协议之间的 interface。在应用层这边，应用将 messages 放进 socket 中。在 socket 的另一头，传输层协议需要负责将 message 运送到接受进程的 socket。

一个传输层协议能给应用层提供什么服务呢？我们可以简单分为四个维度。

Reliable Data Transfer

在前面讨论过，计算机网络中可能会丢包。在很多应用中，丢包会产生灾难性的后果。因此，为了支持这些应用，需要做一些事来保证数据被正确完整（correctly and completely）地传输到 application 的另一端。如果一个协议提供了这么一个有保证的数据传输服务，我们说它提供了一个 reliable data transfer。

当一个传输层协议不提供 reliable data transfer 时，有些数据可能永远也到达不了接收端。这对于一些 loss-tolerant 应用是可以接受的。

Throughput

在第一章，我们介绍了 available throughput 的概念。在一个两个进程间通信会话的上下文中，就是 sending process 向 receiving process 传输 bit 的 rate。

由于其它 sessions 会来来往往，available throughput 会随着时间波动。这个观察自然导出了一个传输层协议可以提供的服务，也就是，保证 available throughput 在一个给定的 rate 以上。有这个服务后，应用层可以指定一个 throughput 为 r bits/sec，然后传输层会保证 available throughput 至少为这个值。这个服务对于 bandwidth-sensitive applications 是很友好的。相比之下，elastic applications 可以尽可能地利用目前的 throughput。

Timing

一个传输层协议也可以提供 timing 的保证。有了 throughput guarantees 后，timing guarantees 可以以许多形式出现。一个例子是，sender 放进 socket 的每一个 bit 到接受 socket 至多花费 100 msec。这种服务比较吸引 interactive real-time applications，例如 Internet telephony 或者 multiplayer games。

Security

最终，一个传输层协议可以给一个应用提供一个或多个安全服务。例如，在 sending host，一个传输层协议可以加密所有发出的数据，并且在接收端数据可以被解密。这样一个服务会给两个进程间的通信带来可信度，即使传输过程中数据被看到了。

2.1.4 Transport Services Provided by the Internet

Internet（更广泛地说，TCP/IP 网络）给应用提供了两种传输层协议，UDP 和 TCP。

TCP Services

TCP 服务模型包括一个连接导向的服务和一个可信数据传输服务。

• connection-oriented service. TCP 在应用层 message 开始流通之前有着传输层的控制信息交换。这被称作 handshaking。在 handshaking 阶段过后，一个 TCP connection 在 sockets 之间被建立。这个连接是双向通讯（full-duplex）的。当应用传输信息完成后，它必须中断连接。
• reliable data transfer service。TCP 传输的数据可以做到 without error 以及 in the proper order。

TCP 还有一个拥塞控制（congestion-control）机制，这是一个为了 Internet 全局好处的服务而不仅仅是两个通信进程。当网络拥堵时，这个机制会对一个 sending process 进行节流。并且拥塞控制还尝试限制每个连接的带宽到它们公平享用的份额。

UDP Services

UDP 是一个无装饰的，轻量级的解析，提供最小级别的服务。它是无连接的，所以没有两个进程间的握手。UDP 提供一个 unreliable data transfer service。此外，message 到达的顺序也不确定。UDP 也没有拥塞控制机制，所以发送方可以以任意速率将 data 发到网络层。（不过真实的端到端 throughput 可能小于这个 rate，因为拥塞或者 link 的有限传输能力）

Services Not Provided by Internet Transport Protocols

…

2.1.5 Application-Layer Protocols

一个应用协议定义了：

• 交换信息的类型。例如，request 和 response。
• 不同信息类型的语法，比如 message 中的 fields 以及这些 fields 怎样被划定。
• 这些 fields 的语义，即它们的 meaning。
• 确定一个 process 何时、怎样发送，回复一个信息。

有一些应用层协议被定义在 RFCs 中，例如 HTTP（RFC 2616）. 还要其它应用层协议在公共上不可见（专有协议），比如 Skype。

2.1.6 Network Applications Covered in This Book

…

2.2 The Web and HTTP

2.2.2 Non-Persistent and Persistent Connections

应用层开发者需要做一个决定：每对 request/response 应该分别使用一个 TCP 连接，还是所有 requests 和 responses 使用相同的连接？前者叫 non-persistent，后者叫 persistent。

2.3 Electronic Mail in the Internet

…

2.4 DNS——The Internet’s Directory Service

…

2.5 Peer-to-Peer File Distribution

…

2.6 Video Streaming and Content Distribution Networks

…

2.7 Socket Programming: Creating Network Applications

…

2.8 Summary

…

Chapter 3: Transport Layer

传输层位于应用层与网络层之间。它给不同主机上的 application processes 提供连接服务。

我们将会先讨论传输层与网络层的关系。这涉及到第一个传输层关键的功能——将网络层提供的主机之间的传输服务扩展到运行在 end systems 上两个应用层进程间的通信服务。

然后我们回到计算机网络最基础的问题之一——两个实体怎样在一个会丢弃、损坏数据的中间介质中 reliably 通信。通过一些列逐渐复杂场景，我们将会建立一系列技术来解决这个问题。

接下来我们将会进入网络第二重要的功能——控制传输层实体的传输率（transmission rate）来避免拥塞或者从中恢复。

3.1 Introduction and Transport-Layer Services

一个传输层协议给不同主机上的进程提供逻辑通信（logical communication）。通过 logical communication，意思是，从主机的视角来看，这些 processes 像是直接连接起来的一样。但实际上，这些主机可能在星球的两端，通过无数 routers 和 links 连接起来。（logical end-to-end communication）

传输层协议在 end systems 上实现而非 network routers。在发送端，传输层将应用层的 messages 转化成传输层的 packets，也就是 segments。这通过将 message 打碎成小 chunks 并且添加传输层的 headers 来实现。传输层然后将 segment 传给网络层然后发送到目的地。意识到网络 routers 只对包中网络层 datagram 上的 field act 是很重要的，也就是它们不管那些只在传输层出现的 fields。在接收端，网络层从 datagram 中抽出传输层的 segment 然后向上传到传输层。传输层然后处理收到的 segment，让其中的数据能被接受端的 application 接受。

3.1.1 Reltionship Between Transport and Network Layers

• 传输层提供 logical communications between different processes running on different hosts
• 网络层提供 logical communications between hosts

…

3.1.2 Overview of the Transport Layer in the Internet

回忆起两大协议 UDP（User Datagram Protocol） 和 TCP（Transmission Control Protocol）。

我们这里将传输层的 packets 都叫做 segment。但是在 RFC 中，UDP 的 packet 被叫做 datagram，并且网络层的 packet 其实也叫这个。为了更清楚，本书都叫 segment。

在讨论 UDP 和 TCP 之前，讨论一些网络层的东西是有用的。Internet 的网络层协议有一个名字——IP（Internet Protocol）。IP 提供 hosts 之间的 logical communication。IP 服务模型是一个 best-effort delivery service。也就是说 IP 尽力在 hosts 间传输数据，但是不作任何保证。因此它是一个 unrealiable service。同时我们要记住每个 host 有一个 IP 地址。

将 host-to-host 的运送拓展到 process-to-process 运送被叫做传输层复用和解复用（multiplexing and demultiplexing）

3.2 Multiplexing and Demultiplexing

然而，我们强调，multiplexing/demultiplexing 服务是所有互联网网络都需要的。

回忆起之前说过，一个 process 可以有一到多个 sockets。因此，接受 host 上的传输层实际上不是真正把数据直接交给某个 process，而是交给一个中间 socket。因为在任意时候接受 host 上都可能有超过一个 socket，所以每个 socket 都有一个唯一标识符。标识符的格式由协议是 UDP 还是 TCP 决定。

现在我们考虑怎样将一个到来的传输层 segment 定向到合适的 socket。每个 segment 有一个 field 来达到这种目的，接收端会查看这个 field 来唯一识别接受 socket，然后交给他。将数据传输给正确的 socket 的过程叫做 demultiplexing。将数据从 source host 的不同 sockets 收集起来，给每个数据块加上一个 header 来产生 segment，并把它传给网络层的过程叫 multiplexing。

在上文的讨论中，我们提到了那个特定的 field，这个 field 就是 souce port number field 以及 destination port number field。每个端口号是一个 16 位数字（0~65535）。 0~1023 端口号被称作 well-known 端口号，并且是收限制的，为 well-known application （例如 HTTP, 80 FTP, 21）所保留的。这些 well-known 端口号列表在 RFC 1700。

Connectionless Multiplexing and Demultiplexing

UDP 会根据 segment 中的 destination port number 字段进行 demultiplex，发送到端口号对应的 socket。

注意到一个 UDP socket 完全被二元组（destination IP，destination port number）唯一标识。也即两个 source destination 相同的 segment 会发送到同一个 socket。

你可能会奇怪，source port number 的目的是什么？答案是，对于 A-to-B 中，当 B 想回复时，这个字段就是一个 return address。

Connection-Oriented Multiplexing and Demultiplexing

TCP socket 和 UDP socket 的一个微小的区别就是，TCP socket 被一个四元组唯一识别：（source IP，source port，destination IP，destination port）。因此，TCP segment 到达 host 时，host 使用全部四个值来 demultiplex。如果两个 segment source不同（除了一开始建立连接的那个 request），它们将会被 direct 到不同的 socket。

Web Servers and TCP

Web Server 为每个连接都新开一个 process。实际上，现在的高性能 Web servers 其实只用一个 process，为每个连接新开一个 thread。

3.3 Connetionless Transport: UDP

除了 multiplexing/demultiplexing 和一些轻量的错误检查，UDP 相比于 IP 没做什么更多的事。因为 UDP 没有 sending 和 receiving 之间的 handshaking，所以它是无连接的。

DNS 是一个应用层使用 UDP 的典型例子。当应用层想要发起 query 时，它构建一个 DNS query message 然后传给 UDP。你可能会想为什么一个应用层开发者有时候会选择 UDP 而不是 TCP，这有一些理由：

• Finer application-level control over what data is sent and when. UDP 会迅速将 segment 传给网络层，而 TCP 有拥塞控制机制。并且 TCP 会继续 resend 一个 segment 直到收到 ACK 为止，不管这个 reliable delivery 花了多长时间。
• No connection establishment。TCP 使用三次握手来建立连接，而 UDP 不做任何事。这可能是 DNS 使用 UDP 的最本质原因——DNS 如果使用 TCP 会变得很慢。HTTP 使用 TCP，这是因为 reliability 对于网页是很重要的。但是，TCP 连接建立的延迟也会带来一些影响，因此有人提出了 QUIC（Quick UDP Internet Connection），使用 UDP 作为底层传输协议并且在应用层实现了 reliability（被用于 Chrome在中）。
• No connection state。TCP 在 end systems 中需要维护 connection state，包括 receive 和 send buffers，拥塞控制的 parameters，以及 sequence 和 acknowledgement number 参数。之后我们来看到这些东西对于实现 reliable data transfer 是很重要的。
• Small packet header overhad。TCP 有 20 bytes header 而 UDP 只有 8 bytes。

3.3.1 UDP Segment Structure

RFC 768 定义了 UDP Segment 的结构。UDP 的 header 只有 4 个 fields，每个占 2 bytes。

source port # (2 bytes, 16-bit)
dest. port # (2 bytes, 16-bit)
length (the length of the UDP Segment)
checksum
======================================= (header)
Application data (message)

3.3.2 UDP Checksum

checksum 是用来做 error detection 的。计算方式是，把前面的三个 16-bit 数全部加起来，然后做一次 1s complement（反码，0-1 反转）。

在接收端，所有的四个 16-bit 数都被加起来。如果没有 error，那么正确的结果应该是全 1 串。如果有一位是 0，我们就知道发生了错误。

你可能会奇怪为什么 UDP 优先提供了 checksum，因为很多链路层协议也有纠错机制。这是因为不是所有链路上都能有纠错机制，并且即使在 link 上传输没问题，存在 router 的 memory 中也可能会出现错误。所以 UDP 必须在 end-end 的基础上提供纠错机制。（end-end principle in system design：比起在高层提供某些功能，在低层提供这些功能可能会重复或者价值比较小。）

3.4 Principles of Reliable Data Transfer

在这部分，我们在一般一意义下考虑 reliable data transfer。这是合适的因为这一问题不仅在传输层，也在链路层、应用层出现。

framework for reliable data transfer

Application Layer            
					 
Transport Layer    ↓(Reliable data transfer protocol, sending)         ↑(Reliable..., receiving)        

Network Layer                              →→→→→ Unreliable channel   

由于下面的层可能是 unreliable 的，所以这个任务很困难。

在本章我们只考虑 unidirectional data tranfer（单向数据传输）。

3.4.1 Building a Reliable Data Transfer Protocol

Reliable Data Transfer over a Perfectly Reliable Channel: rdt 1.0

首先我们考虑最简单的情况，即下面的 channel 是完全可信的。这样这个 protocol 本身就是 trivial 的（我们叫 rdt1.0），和平时的传输没有区别。

Reliable Data Transfer over a Channel with Bit Errors: rdt 2.0

一个更现实的模型是 packet 中的 bit 可能损坏的情况。这种 bit errors 特别地会在一个包 transmit，propagate 或者 buffered 时发生在一个网络的物理元件上。我们仍然假设所有 packets 都能被接受（即使它们的 bits 可能会错），并且仍然按发送时的顺序。

考虑人会怎么做。当人在通话时听到一条模糊的消息，会叫对方重复一遍（negative acknowledgements）；如果听到完整的话，则回复 OK（positive acknowledgements）。这种基于重新传输的协议在 reliable data transfer protocol 中被叫做 ARQ（Automatic Repeat reQuest） protocols。

基本地，ARQ protocols 要求三种附加的协议能力来处理 bit errors 的出现：

• Error detection。首先，需要有一种机制让 recevier 检测到 bit error 的发生。回忆一下，UDP 的 checksum 就是为了这个。现在我们只需要知道，这种技术需要额外的 bits；这些 bits 会一起并进 rdt 2.0 packet 的 checksum field 中。
• Recevier feedback。因为 sender 和 receiver 运行在不同的 end systems 上，它们之间通信的唯一方式就是发送 packet。positive acknowledgement（ACK）和 negative acknowledgement（NAK）就是这种例子。我们的 rdt2.0 也会相似地从 recevier 向 sender 发回 ACK 和 NAK。原则上，这些包只要 1 bit 长（0：NAK，1：ACK）。
• Retransmission。一个被检测到 bit error 的 packet 会被 sender 重新发送。

简单来说，rdt 2.0 的 FSM 就是接到 NAK retransmit sender 发送的 last packet，并且继续等待 ACK 或 NAK。注意当 sender 处于 wait-for-ACK-or-NAK state 时，它不能再从 upper layer 获得更多 data。也就是说 rdt_send 事件不会发生。只有当 sender 收到 ACK 才能退出这个状态。因此 rdt2.0 也叫做 stop-and-wait protocols。

注意 rdt2.0 有一个 fatal flaw（致命缺陷）。特别地，我们没有考虑 ACK 和 NAK packet 发生 error 的情况！不幸的是，这个微小的观察并不是和它看起来一样无害。最简单地，我们可以给 ACK 和 NAK packet 添加 checksum bits 来查错。但是困难之处在于 protocol 怎样从这种错误中恢复。sender 无法知道 recevier 是否正确收到了最后一段传输出去的数据。

考虑三种处理 corrputed ACKs 和 NAKs 的可能性。

• 对于第一种可能，可以在 ACK 错误时回复一个 “What did you say?”，也就是再回复一个 negative acknowledgement。但是如果这个回复也 corrupted 呢？显然，这个事情很困难。
• 第二种选择是加入足够的 checksum bits 让 sender 不仅能检测，还能 recover from bit errors。
• 第三种方法是，在 sender 收到一个混乱不清的 ACK 或者 NAK 时，简单地重新发送。然而，这种方法在 client server 的 channel 中引入了 duplicate packets（重复的包）。duplicate packets 的基本困难在于，receiver 不知道它最后发出的 ACK/NAK 在 sender 被正确收到。因此，它对下一个到来的包到底是一个新数据包还是上一次的 retransmission 没有先验知识（priori）。

一个简单的解决方案是给 data packet 加入一个新的 field，并且让 sender 给这些 data packets 编号，通过将一个 sequence number 放到这个 field 中。那么接收者只需要 check 这个 sequence number，就能知道它是一个新包还是一个 retransmission。对于这个简单的 stop-and-wait protocol，1 bit sequence number 就够了，因为我们只需要区分相邻的 packet（这个 packet 还是下个 packet）来分辨 retransmission。因为我们假设不会丢包，所以 ACK 和 NAK 不需要在它们自己里指明 sequence number。因为 sender 知道收到的 ACK 或者 NAK 是对最近（most recently）的 packet 的回复。这个修正的版本可以叫做 rdt2.1。

对于发送 NAK，我们可以用对同一个包发送两个 ACK 来替代（receives duplicate ACKs）。这个没有 NAK 的版本可以叫做 rdt2.2。

Reliable Data Transfer over a Channel with Bit Errors: rdt 3.0

假设现在除了 corrupting bits 问题，丢包也会发生了（在今天的计算机网络并不是一个罕见的事情）。两件事需要被新的 protocol 考虑到：怎样检测一个丢包事件，并且在丢包时应该做什么。在 rdt2.2 中使用的 checksuming，sequence numbers，ACK packets 和 retransmission 技术可以解决第二个问题。而解决第一个问题需要引入新的机制。

有很多解决丢包的方法。在这里，我们将检测和恢复的重担交给 sender。假设一个 sender 发送一个 packet，并且这个 packet 或者它的 ACK 丢失了。不管在何种情况，recevier 都不会给 sender 回复。如果一个 sender 等 ACK 等太久，那么肯定这个 packet 已经丢失了。它可以简单地 retransmit 数据包。

但是 sender 需要等多久才能认为丢包了？sender 必须至少等待一个从 sender 到 receiver 一个来回（round trip）的 delay，加上在 receiver 中处理 packet 需要的时间。（也就是正常数据包来回的所用时间）在很多网络，这个时间的最坏情况很难被估计。并且 protocol 应该尽可能块地从丢包中恢复。在实践中的做法是，sender 审慎地（judiciously）选择一个时间值，让 packet loss 很可能（尽管不能保证）发生了。注意到如果一个 packet 经历了很长一段的 delay，即使它和它的 ACK 都没有丢包，sender 也可能会 resend。这就带来了 duplicate data packets 的可能性。所幸的是，rdt2.2 对于 duplicate packets 已经能够处理。

对于 sender 来说，retransmission 是一个 panacea（灵丹妙药）。不管是丢包还是超时，sender 的 action 都是 retransmit。实现这么一个机制需要一个 countdown timer，可以在 expire 时中断 sender。然后 sender 会对 timer interrupt 做回复。这些合起来就是 rdt3.0 了。因为使用 1-bit 的 sequence number，这个协议有时也叫做 alternating-bit protocol。

3.4.2 Pipelined Reliable Data Transfer Protocols

rdt3.0 是一个功能上正确的协议，但是不是所有人都喜欢它的效率。因为它的核心还是 stop-and-wait。

问题：如果不 pipeline 的话，单纯等一个包过去、回来（一个 RTT）是很浪费时间的。解决方式是，sender 被允许发送多个 packets （而不是等待 ACK）。这个技术被叫做 pipeling。它对 protocol 有以下的影响：

• sequence number 的值域要扩大（而不是0-1）。这些多个 packet 需要有唯一的 sequence number 了，并且会有许多在传输过程中，unacknowledged 的 packets。
• sender 和 receiver 端必须要 buffer 多于一个 packet。
• 所需的 sequence number 范围和 buffering 要求取决于这个协议怎样对这些情况做出回应。两种基本的 pipelined error recovery 策略被叫做：Go-Back-N 和 selective repeat。

3.4.3 Go-Back-N（GBN）

在 GBN 协议中，sender 允许发送多个 packets 而不是等待一个 ACK，但是 unacknowledged packcts 数量不能超过某个最大值 N。

如果我们定义 base 为队列中最早的 unacknowledged packt，并且 nextseqnum 为最小的未被用的 sequence number（也就是下一个要发出的 packet 的 sequence number）。那么就会出现 4 个间隔：在 [0, base-1] 中间对应着已经被发出去并且 acknowledged 的 packets。[base, nextseqnum-1] 对应着被发出但是没有 acknowledged 的 packets。在 [nextseqnum, base+N-1] 可以被接下来到达的上层数据（可以被立即发出的 packet）使用。[base+N, +\infty] 还不能被使用，直到编号为 base 的 packet 被 acknowledge。

按这个协议，一个长度为 N 的 window 在 sequence number 空间上滑行，因此 N 也被称作 window size，并且 GBN 自身叫做 sliding-window protocol。为什么要限制一个窗口大小N？一个原因是 3.5 会谈到的 flow control，另一个是 3.7 会谈到的 congestion control。

假设 sequence number 在 packet header 里占 k 位，那么 sequence number 的范围就是 [0, 2^k-1]。所以一切的运算都是在模 2^k 下进行的。（极端点的，rdt3.0 的 sequence number 相当于模 2）我们在 3.5 中可以看到 TCP 有 32-bit 的 sequence number field，并且 TCP 的 sequence numbers 数的是 bytes 而不是 packets。

GBN 的 FSM 如下所示：

rdt_send(data)
_____________________
if nextseqnum < base+N:
	sndpkt[nextseqnum] = make_pkt(nextseqnum, data, checksum)
	udt_send(sndpkt[nextseqnum])
	if base == nextseqnum:
		start_timer
		next_seqnum++
else:
	refuse_data(data) (队列满了)


timeout
______________________
start_timer
udt_send(sndpkt[base])
udt_send(sndpkt[base+1])
...
udt_send(sndpkt[nextseqnum-1]) （把目前窗口里的东西全部重发一遍）


rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
________________________________________
base = getacknum(rcvpkt) + 1
if base == nextseqnum:
	stop_timer
else:
	start_timer

rdt_rcv(rcvpkt) && nocorrupt(rcvpkt) && hasseqnum(rcvpkt, expectedseqnum)
____________________________________________________
extract(rcvpkt, data)
deliver_data(data)
sndpkt=make_pkt(expectedseqnum, ACK, checksum)
udt_send(sndpkt)
expectedseqnum++

default
______________
udt_send(sndpkt)  (不断往回发)

init
______________
expectedseqnum=1
sndpkt=make_pkt(0, ACK, checksum)

也就是说，接收端那边有一个 expectedseqnum 一直在 ++。如果发过来的包中的 seqnum 和接收端期望的不同（后来先到），那么接收端也会拒收。

GBN sender 需要对三种事件做回复：

• 高层调用。当高层调用 rdt_send 时，它先查看 window 是不是满了，如果满了就直接退回数据；否则在 window 中放下该数据，然后进行发送。
• 接受 ACK。在我们的 GBN 协议中，对一个带有 sequence number n 的 packet 的接受是按 cumulative acknowledgement 策略进行的，也就是当收到 n 号 packet 时，sender 认为 n 号及以前的 packet 都已经被正确接收。因此我们可以直接把 base 前置。
• timeout 事件。协议名 Go-back-N 就是从 sender 行为来命名的。就像在 stop-and-wait 协议里做的那样，一个 timer 会用来记录是否超时。如果超时，sender 会 resend 所有目前没被 acknowledged 的包（就是从base 开始到 nextseqnum-1 结束）

基于事件的编程（event-based programming）

3.4.4 Selective Repeat（SR）

然而 GBN 在一些场景下也存在 performance 问题。特别地，当 window size 和带宽延迟都很大时，只是一个 packet error 都会让 GBN 重新发送大量的 packets（可能是不必要的）。

就像名字说的那样，selective-repeat 协议通过只让 sender 重发那些它怀疑 error 的 packets 来避免不必要的重发。和 GBN 相似，N 也会用来作为窗口大小限制最大 unacknowledged 包数。然而，不像 GBN，sender 已经在这个 window 中接收到了一些 ACKs。（GBN 从base到nextseqnum-1都是没接受的）以下是 sender 的事件与行为

• data received from above。当 SR sender 收到上层的发送请求时，它先 check 下一个 available 的 seqnumber，如果它还在 window 里就发送。否则就 buffer 或者返回上层回拒（和 GBN 一样）
• timeout。现在，每个 packet 有自己的 local timer，因为 timeout 时只有一个包会被重发。一个单个硬件 timer 可以被用来模拟多个 logical timers 的操作。
• 收到 ACK。如果一个 ACK 被收到，sender 将对应的 packet 标记为已收到。（保证它在 window 里）如果这个包的 sequence number 等于 base，那么window base 会往右移到最小的 unacknowledged packet 的位置（略过所有 acknowledged 的）。如果在 window 移动过程中有新的，未被 transmit 的 packets 现在落在 window 里（？可能是 buffer 了），那么它们会被发送。

以下是 receiver 的行为

• sequence number 在 [recv_base, recv_base+N-1] 中的 packet 被正确收到。在这种情况下， 收到的 packet 落在了 receiver 的 window 里，并且一个 selective 的 ACK packet 会被发回 sender。如果这个包此前没有被接收过，它会被 buffer（在 recv 端！）。如果这个包的 seqnum 等于 recv_base，recv 的窗口会向前移，略过所有（receiver认为的）已经发过 ACK 的 packet，并且略过的这些 packet 都能交给 upper layer（正是如此才要缓存）。
• seq num 在 [recv_base-N, recv_base-1] 里。在这种情况，回一个 ACK 即可，因为已经上交了（窗都滑走了）

注意这里 send 有一个 window，recv 有一个 window。与此相比，GBN recv 端收到就可以上交 upper layer 了，也因此 recv 部分不需要 buffer packet。

考虑到 seq num 的范围是有限的，因此在模意义下（如果用的快的话）可能会出现相同 seq num 但是不同包的情况。实际上，令 seq #size >= 2*window size。

3.5 Connection-Orented Transport: TCP

我们已经聊过了 reliable data transfer 的底层原则了，现在让我们将目光转向 TCP。

3.5.1 The TCP Connection

TCP 是基于连接的，因为在两个应用进程要通信前，它们需要先 handshake。TCP 连接不是 end-to-end 的 TDM 或者 FDM circuit。这里的连接是逻辑上的，指的是两个 end systems 之间共同的状态。

一个 TCP 连接提供了 full-duplex service（完全双向）。TCP 连接一直是 point-to-point 的，也就是单对单。multicasting，也即 one sender-many receivers，对于 TCP 是不可能的。

回忆：初始化连接的进程叫做 client process，另一个叫做 server process。TCP 通过三个特殊的 segnment 建立连接。前两个 segment 没有 payload；第三个可能带一个 payload，这就是三次握手（three-way handshake）。

TCP 连接将数据放入 send buffer 中（三次握手时建立）。

MSS：maximum segment size。

3.5.2 TCP Segment Structure

source and destination port numbers，checksum（as with UDP）

• 32-bit sequence number field & 32-bit acknowledgment number。用于实现 reliable data transfer service。
• 16-bit receive window，用于 flow control。
• 4-bit header length。
• optional field
• flag field（6-bit）。ACK bit，SYN FIN CWR ECE PSH URG
• urgent data pointer（？）
• data field。

Sequence Numbers and Acknowledgment Numbers

TCP 将 data 看作没有包装的有序 bytes 流。TCP 在字节流上（而非一系列 segments 上）使用 sequence numbers。例如 MSS=1000，传输一个 500000 bytes 的文件。第一个 segment 得到 0 这个 seqnum，第二个 segment 得到 1000 这个 segnum，…

然后让我们来考虑 acknowledgment numbers。Host A 放进它的 segment 里的 ack number 就是 Host A 期望从 Host 收到下一个 byte 的 seq number。由于 TCP 只 acknowledges bytes 到第一个 missing byte 的位置，它也被认为提供了 cumulative acknowledgments 机制。

一般来说，发送方的包中包括 seq 和 len。那么接收方 ack=seq+len。不过特殊情况在于三次握手时，len=0，但是 ack=seq+1。

前面我们假设初始的 seq num 是 0。实际上，TCP connections 的两端都随机选择一个初始的 seq number。这是为了使得以下时间的概率最小化：一个上一个，（应该）已经终止的连接中的 segment 仍然留存于这个网络中，它就会被误认为一个 valid 的 segment。

Telnel: A Case Study for Sequence and ACknowledgment Numbers

…

3.5.3 Round-Trip Time Estimation and Timeout

TCP 就像我们之前的 rdt 协议一样，采用 timeout+retransmit 机制来从错误中恢复。而这还是要考虑 timeout 的长度。显然，timeout 应该比 RTT 长。但是应该长多少？RTT 首先应该怎样被估计？

Estimating the Rount-Trip Time

我们首先考虑怎样估计 RTT。Sample RTT，即一个 segnment 从它发送到它被接受所花的时间。比起衡量每个 segment 的 Sample RTT，大多数 TCP 实现只使用一次的 Sample RTT 测量结果，也即在某一时刻，SampleRTT 由其中一个发出去但是没有 acknowledge 的包来衡量，产生一个新的 SampleRTT（可能是一次 update）。

显然，SampleRTT 的值会随着 segnment 而浮动（因为 router 的拥塞等等）。因为这个浮动，任意给定的 SampleRTT 的值可能并不典型。为了估计一个典型的 RTT，很自然地会想到（某种）取平均。TCP 维护一个平均值，叫做 EstimatedRTT。在每个 SampleRTT 测量出来后，TCP 通过

$$EstimatedRTT = (1-\alpha) \times EstimatedRTT + \alpha \times SampleRTT$$

来 update 它。建议的 alpha 值是 0.125（RFC 6258）.

除了估计 RTT 意外，衡量 RTT 的变化也是很有价值的。DevRTT 就是一个对 RTT 变化的估计量，由 EstimatedRTT 导出

$$DevRTT = (1-\beta) \times DevRTT + \beta \times |SampleRTT - EstimatedRTT|$$

Setting and Managing the Restranmssion Timeout Interval

一般来讲，TCP 采用

$$TimeoutInterval = EstimatedRTT + 4 \times DevRTT$$

初始值被建议为 1 second（RFC 6298）

3.5.4 Reliable Data Transfer

TCP 在 IP 的不可信、best-effort 传输服务上建立了可靠的数据传输服务。它保证了接收的 bytes stream 和连接另一头的法松的 bytes stream 是完全相同的。

在我们一开始的探索中（SR），概念上很简单能假设每个未发出去的 packet 都有一个 timer。但是实践上这会带来很大的 overhead。因此，TCP 推荐只使用一个 timer。接下来的 TCP 协议遵循这个单 timer 的建议。

TCP sender 的大致行为如下：

switch (event):
	event: data received from application above
		create TCP segnment with NextSeqNum
		if timer not running:
			start timer
		pass segment to IP
		NextSeqNum += length(data)
	
	event: timer timeout
		retransmit not-yet-acknowledged segment with smallest sequence number
		start timer
	
	event: ACK received, with ACK field value of y
		if y > SendBase:
			SendBase = y
			if there are currently any not-yet-acknowledged segments
				start timer

可以看出 TCP 也采用了 cumulative acknowledgments。

A Few Interesting Scenarios

第一个场景：A 向 B 发送了一个 segment（seq# 92，8 bytes），那么 B 回复一个 ack# 100 的 ACK。但是 ACK 丢了，因此 A retransmit。而 B 收到 retransmit 时，B 发现这个 segment 接受过了。因此 B 丢弃了 retransmit segment 中的 bytes。

第二个场景：A 接连发送两个 segment：seq#92，8 bytes；seq#100，20 bytes。假设两个 segment 都到 B，并且 B 发送了两个不同的 ACK：ack#100，ack#120。现在假设没有一个到达 A，timeout 了。然后 Host A 重新发送第一个 segment（seq#92），但时第二个 segment 没有被重传。

第三个场景：A 像第二个场景一样发两个包。第一个 ACK 丢了，A 收到 ack#120（第二个 ACK），A 这样知道 B 已经收到了所有 119 bytes 以内的数据，因此不会进行 resend。

Doubling the Timeout Interval

我们现在考虑 timeout 的间隔。当每次 TCP retransmit 时，它会将下一个 timeout interval 设置成上一个值的两倍，而不是从 EstimatedRTT 和 DevRTT 中推导出来。因此，timeout interval 是指数增长的。不过，当 timer 被其它两个 event start 之后（第一个和第三个），这个 interval 是从最近的 EstimatedRTT 和 DevRTT 中推导出来的。

这个改变提供了拥塞控制的一种有限的形式。timeout 比较可能是因为网络中的拥塞造成的。所以如果你仍然按之前的速率 retransmit，拥塞会更严重。我们将会在之后研究 Ethernet 中的 CSMA/CD 中发现相似的 idea。

Fast Retransmit

timeout 触发的 retransmit 的一个问题是，timeout 间隔可能会很长，因此增加了 end-to-end delay。不过幸运的是，sender 往往能在 timeout 时间前检测到 packet loss，通过 duplicate ACK（duplicate ACK 是一个对早先已经收到的，已经 acknowledged 的 segnment 的 ACK）。我们需要先研究为什么 receiver 会重复发送 ACK。

当 TCP receiver 检测到一个 segment，seq# 比下一个期望的，按顺序的 sequence number 要大的包，它就检测出了 data stream 里的一个 gap，也就是一个 missing segment。这个 gap 可能是由 packet loss 或者 reordered segments 导致的。因为 TCP 不使用 NAK，receiver 不能显式发送一个 NAK 告诉 sender。取而代之，它对按顺序的最后一个收到的 bytes 的那个位置发一个 re-ACK。

因为 sender 通常连续发送一大堆 segments，如果一个 segment 丢了，那将会有连续的 duplicate ACKs 回来。如果 TCP sender 收到三个对于同一个 data 的 duplicate ACKs，它将其认为是丢包的象征。（在作业中，我们会考虑为什么 TCP 要等待三次 duplicate ACKs，而不是直接单个 duplicate ACK 就可以认为丢包）。当收到三个 duplicate ACKs 后，TCP sender 进行一次 fast retransmit。

首先，一次 duplicate ACKs 肯定不合适，因为中间网络设备出问题导致该 ACK发了多次，sender 就要重传了。如果是两次，还是可能由于乱序、网络延迟，造成的，三次要稳一点。

Fast Retransmit / Recovery（FRR） 是 TCP 的一个增强特性，也即无需等待 timeout 就能重传。

Go-Back-N or Selective Repeat？

TCP 的 error-recovery 机制更像是 GBN 和 SR 的混合。在 cumulative acknowledgment 上，它有点像 GBN；但是很多 TCP 都会 buffer 正确收到但是乱序的包。考虑如果 1~N，n 号包丢了，GBN 会 retransmit 所有 n+1，…，N。而 TCP 至多重传至多一个 segment n。并且如果 n+1 的 ack 到了，但是 segment n 没用 timeout，TCP 不会 retransmit segment n。

3.5.5 Flow Control

TCP 给它的应用提供了一个 flow control（流控制服务）来消除它 overflow 接收者 buffer 的可能性。因此 flow control 是一个 speed-matching 服务——将 sender 发送消息的 rate 和接收者接收消息的速率相 match。

TCP 通过让 sender 维护一个叫做 receive window 的变量来提供流控制。不正式地讲，receive window 就是让 sender 知道 receiver 还有多少 available free buffer space。因为 TCP 是完全双向的，connection 的每一端都维护了一个 receive window。记接收端 Host B 的 receive buffer 大小为 RcvBuffer。定义如下变量：

• LastByteRead：data stream 里最后一个被 B 的用户进程从 buffer 里读走的 byte 的编号。
• LastByteRcvd：最后一个到达并被放入 buffer 的 byte 的编号。

由于 TCP 不允许溢出，需要有 LastByteRcvd - LastByteRead <= RcvBuffer

receive window（记作 rwnd）被设为 buffer 的空闲空间量：

rwnd = RcvBuffer - (LastByteRcvd - LastByteRead)

因为这个空闲空间会随着时间改变，rwnd 是动态的。

连接怎样用 rwnd 变量来提供流控制服务呢？Host B 将 rwnd 放在 segment 的某个 field 里发送到 A。Host A 关注两个变量：LastByteSent 和 LastByteAcked。那么 LastByteSent - LastByteAcked 就是 A 发了但是没有被 unacknowledged 的 data。那么 Host A 只要保证 LastByteSent-LastByteAcked <= rwnd，也就是 NextSeqNum-SendBase <= rwnd。

3.5.6 TCP Connection Management

三次握手：

• Step 1. client 发送一个 TCP SYN 给 TCP（SYN flag 置为 1）. 并且 client 随机选择一个初始的 sequence number（client_isn）然后将他放进 sequence number field。
• Step 2. 当 server 接到带有 SYN flag 的包后，它会给这个连接 allocate TCP buffers 和 variables，并且给 client TCP 发送一个 connection-granted segnment（SYNACK）（在第八章，我们可以看到如果在第三步分配 buffers 和 variables，会让 TCP 对 SYN flooding 这种 DoS 攻击很脆弱。）这个 SYNACK 同样没有应用层的信息。不过，它包含三个重要的部分：首先，SYN flag 设成 1；其次，acknowledgment field 设成 client_isn+1；最后，server 选择它自己的初始 sequence number（server_isn），放到 sequence number field 里。
• Step 3. 在收到 SYNACK 后，client 也 allocates buffers 和 variables。client 发送另一个 segment，这最后一个 segnment 是对 SYNACK 的 acknowledgment（client 通过在 acknowledgment field 里放 server_isn+1 来实现）。SYN flag 被设为 0，因为连接已经建立了。三次握手的第三次阶段的包可能有 payload。

这一趟花费时间为一个 RTT。

client TCP 的状态：

CLOSED
SYN_SENT
ESTABLISHED
FIN_WAIT_1
FIN_WAIT_2
TIME_WAIT
CLOSED

server TCP 的状态

CLOSED
LISTEN
SYN_RCVD
ESTABLISHED
CLOSE_WAIT
LAST_ACK
CLOSED

四次挥手：

• client 主动关闭，向 server 发送一个 FIN。（FIN_bit 置为 1，ACK 也置为 1，连接释放报文）.发完之后，client 不能再发送数据，只能接受数据。server 会回复一个 ACK 表示收到。此时 client 发完后进入 FIN_WAIT_1 状态，server 发完 ACK 后进入 CLOSE_WAIT 状态。这时候 TCP 连接处于半关闭状态，server 仍然可以朝 client 发送数据。当 client 收到这个 ACK 后，就进入 FIN_WAIT_2 状态。
• 当 server 没什么要发送的时候，应用进程就通知 server 关闭连接。此时 server 会发送一个 FIN，并进入 LAST_ACK 状态，这个 FIN 的 seq 是某个值 w，ack 和之前那个 ACK 一样。client 收到这个 FIN 后就发一个 ack 回去，这个 ack 的 ack# 是 w+1，seq# 是一开始那个 FIN 的序号+1。（不携带数据的都要+1）。server 收到这个回复后关闭（CLOSED）
• client 发完这个东西后还要进入 2MSL 才能关闭，MSL是Maximum Segment Lifetime，最长报文寿命，一般为几分钟。这个阶段叫 TIME_WAIT。

为什么要有 TIME_WAIT？考虑 client 最后朝 server 的 ACK 丢失了，那 server 需要重发 FIN，如果直接关了就收不到了。

3.6 Principles of Congestion Control

…

3.7 TCP Congestion Control

TCP 拥塞控制包含三个组件：slow start，congestion avoidance，fast recovery。slow start 和 congestion avoidance 是 TCP 的必需组件，在它们对收到 ACK 后怎样增加 cwnd 的大小有区别。我们之后会看到 slow start 增加 cwnd 比 congestion avoidance 更陡（和它的名字不同）！Fast recovery 被推荐但是不要求一定要。

Slow Start

当 TCP 连接建立时，cwnd 的值一般被设为 1 MSS（RFC 3390），导致初始发送速率大概在 MSS/RTT 这么多。由于可用带宽可能会大于 MSS/RTT，TCP sender 想要迅速弄清可用的带宽。因此，在 slow-start 状态，cwnd 从 1 MSS 开始并且每次接收到第一个 ACK，都会增加 1 MSS。

以下图为例，TCP 发送第一个 segment 到网络中。当 ACK 到达后，TCP sender 将 cwnd 增加 1 MSS，然后发送两个 segnments。这些 segments 之后被收到，cwnd 每个 segment 都增加 1 MSS，这样就是 4 MSS，不断下去。我们可以看出这个过程导致了 sending rate 以每个 RTT 翻倍的速率增长。

但是什么时候这个指数增长会停止呢？首先，如果有一个被 timeout 认出的 loss event，TCP sender 会将 cwnd 设成 1，并且重新开始 slow start 过程。它还会设置一个叫 ssthresh（slow start threshold）的变量，值为 cwnd/2。第二种可能结束的方法是，如果 cwnd 达到了 ssthresh，slow start 结束，TCP 转化为 congestion avoidance 模式。我们可以看到在这个模式 cwnd 增长得更小心。

Congestion Avoidance

congestion could be just around the corner！因此，此时 cwnd 会采用线性上升。具体的实现方式是，cwnd 如果是 10MSS，那么它发 10 个包，每个 ACK 都让它上升 MSS/10。这样一个 RTT 无论如何就上升一个 1MSS。

那么这个线性增长什么时候会停止呢？timeout 发生时，同样，cwnd 会设成 1MSS，然后设置 ssthresh。不过回忆一下，一个 loss event 也可以被三个 duplicate 的 ACK 触发。此时 TCP 会将 cwnd 减半（AIMD，Additive Increase Multiplicative Decrease）。其实是 cwnd = ssthresh + 3 MSS（考虑到这三个重复的 ACK 的效果）。然后进入 fast recovery 状态。

Fast Recovery

…

3.8 Summary

…

Chapter 4: The Network Layer: Data Plane

我们可以看出不同于传输和应用层，网络层位于每个网络中的 host、router 上。网络层大概是协议栈中最复杂的一层，被分为两个相互交错的部分：data plane（数据平面） 和 control plane（控制平面）。在第四章，我们会先讲解数据平面的功能——per-router 功能，也就是决定一个到达 router 的 datagram 怎样被 forward 到 router 的一个 output link。我们会同时讲解传统的 IP forwarding 和一般的 forwarding。我们还会详细研究 IPv4 和 IPv6 协议、寻址。

在第五章，我们会涉及控制平面的功能——一个datagram怎样在一个从source host到destination host的end-to-end path上被route。我们会涉及 routing 算法，例如 OSPF 和 BGP。传统地，数据控制平面是实现在一起的。SDN（Software-defined networking）显式地将数据平面和控制平面分开，通过将控制平面的功能实现成一个分离开的服务，在一个特定的远程 controller。

4.1 Overview of Network Layer

4.1.1 Forwarding and Routing: The Data and Control Planes

网络层的两个重要功能可以被概括为：

• Forwarding。当一个包到达 router 的 input link 时，router 必须要将它发送到合适的 output link。一个 packet 也可能会在 router 里被 block，或者复制很多份发往不同的 output link。
• Routing。网络层需要决定 packets 从 sender 流动到 receiver 的 path（或者叫 route）。计算这些路径的算法被叫做路由算法。

在每个网络 router 中，一个关键的元素是它的 forwarding table。一个 router 通过检查到达的 packet 中一个或多个 fields，然后使用这个 fields index into 它的 forwarding table，对应储存的 value 项即指明了 packet 应该被 forward 的 output link interface。

Control Plane: The Traditional Approach

路由算法运行在每个 router 上。一个 router 上的路由算法功能回合其它 routers 上的交流，来计算它的 forwarding table 的值。这一过程是通过根据一个 routing protocol 交换 routing message 完成的。

Control Plane: The SDN Approach

注意到 control plane 的功能从物理上的 router（routing device 只提供 forwarding 功能）分离，同时 remote controller 计算并且分配 forwarding tables。

4.1.2 Network Service Model

例子：

• Guaranteed delivery。这个服务保证一个 source host 的 packet 会最终到达 destination host。
• Guranteed delivery with bounded delay。不仅保证到达，还保证一个 host-to-host delay 的界。
• In-order packet delivery。保证 packets 按发送顺序到达目的地。
• Guranteed minimal bandwidth。保证只要在指定 bit rate 下传输，所有 packets 最终都会到达 destination host。

Internet 的网络层只提供一种服务，那就是 best-effort service。别的网络架构的服务还有比如说 ATM 网路架构的 CBR。

An Overview of Chapter 4

…

4.2 What’s Inside a Router

…

4.3 The Internet Protocol (IP): IPv4, Addressing, IPv6, and More

现在有两种版本的 IP 都在使用——IPv4 和 v6。掌握 IP 寻址就是在掌握网络层本身！

4.3.1 IPv4 Datagram Format

IPv4 datagram 的内容包括：

• header length。
• type of service（TOS）
• datagram length。
• Identifier，flags，fragmentation offset。
• time-to-live（TTL）。TTL 是为了保证一个 datagram 不会死循环（例如，在一个 routing loop 中），在每个 router 上这个 field 都会 -1。到达 0 时包会被丢弃。
• Protocol。
• Header checksum。注意在每个 router 上，checksum 都要重新算，因为 TTL 会变。
• Source and destination IP addresses。
• Options。
• Data（payload）。

IP datagram 总共有 20bytes 的 header。那么算上 TCP，就是 20+20=40bytes 的 header。

4.3.2 IPv4 Datagram Fragmentation

由于链路层对最大传输单元有大小限制（MTU，maximum transmisson unit），IP datagram 需要 divide 小的 fragments（大 datagram 变成几个小 datagram）。

例如，一个 4000 bytes 的 datagram 需要在一个 MTU 为 1500 bytes 的 link 上传输。去掉 header 就是 3980 bytes，它就被分为 1480+1480+1040，然后分别加上 header 就是 1500+1500+1060。

where to resemble fragments：在 destination host 上。

4.3.3 IPv4 Addressing

即使你现在想起来感觉 IP 寻址会是一个很直接的事情，希望你看完本节后会相信 Internet 寻址不单单是一个有趣的 topic，并且还是 Internet 中最重要的 topic 之一。

在讨论 IP 寻址之前，我们需要说一点关于 hosts 和 routers 怎样连接到互联网的事。一个 host 一般只有一个连接到网络的 link；当 host 上的 IP 想要发送 datagram 时，它通过这个 link 来发送。host 和 physical link 的边界叫做 interface。一个 router 有很多 interfaces（由于它的职能），在它和它的每个 link 之间都有一个。因为每个 host 和 router 都能发送、接受 IP datagrams，IP 要求每个 host 和 router 的 intereface 都有自己的 IP 地址。因此，一个 IP 地址技术上是针对一个 interface 的，而不是包含这个 interface 的 host 或者 router。

一个 IP 地址有 32 位。这些地址通常用所谓的 dotted-decimal notation 来写。

每个 host 和 router 上的，在全球因特网中的 interface，需要有一个 globally unique 的 IP 地址。一个 interface IP 地址的一部分被它所连的子网（subnet）决定。

如图所示，最左边的三个 hosts 前 24 位都是相同的。这四个 interfaces（加上路由器那边那个）通过一个没有路由器的的网络相互连起来。这个网络可能是通过 Ethernet LAN 相互连接，在这种情况这些 interfaces 可能通过一个 Ethernet switch 或者一个无线 AP（acces point）来连接。

用 IP 的术语，这四个 interfaces 形成了一个子网（subnet）。IP 地址给这个子网分配了一个地址：223.1.1.0/24，这里 /24（slash-24）就是子网掩码（subnet mask），表示从左开始 24 个连续的 1，也就是左边 24 位定义了子网的地址。任何在这个子网里的 hosts 被要求地址必须是 223.1.1.xxx 的格式。图中还有两个子网。

IP 对一个子网的定义不局限于这个 Ethernet 片段连接许多 hosts 到一个 router interface 的情况。事实上，一个子网可以这样定义：

把每个 interface 从它的 host 或者 router 上 拔下来，形成一些 networks 的孤岛，并且这些 interfaces 是这些网络孤岛的 end points。每一个这种孤岛都叫做 subnet。

IP 地址的分类表示有三种形式

• 分类 IP 地址。IP 地址 = 网络号（Network Num） + 主机号（Host Num）。常见的 A 类（8位网络，24位主机）；B类（16，16）；C类（24，8）；…（在 CIDR 之前），classful addressing。

  这玩意儿的缺点是粒度不够。比如说给你个 C 类，只有 2^8-2=254（两个用于特殊用途，也就是广播地址和网路地址）个 hosts；但是给个 B 类又太大了。

• 子网划分。IP 地址 = 网络号 + 子网号 + 主机号

  A 类地址默认子网掩码为 255.0.0.0

• 无分类编址 CIDR。IP 地址 = 网络前缀 + 主机号。

Internet 的地址分配策略被称作 Classless Interdomain Routing（CIDR，cider）。CIDR 将 subnet 的地址表示推广了。32位的 IP 地址被分为两部分，写作 a.b.c.d/x 这里 x 表示第一部分的有效位数。

这里的前面部分通常被叫做 prefix（network prefix）。一个组织通常分配一块连续的地址，也就是一个拥有共同前缀的范围地址。

使用 CIDR 的好处：允许 routers 进行 route aggregation（supernetting，路由聚合），以此来减少 router entries，提高效率。

最长前缀匹配：当有多个表项时，选择子网掩码最长的那个（匹配掩码长度）。

Obtaining a Block of Addresses

Obtaining a Host Address: The Dynamic Host Configuration Protocol

当一个组织获得了一块地址后，它可以给内部的 host 和 router 分配各自的 IP 地址了。地址可以被手动设置，不过通常它是通过使用 Dynamic Host Configuration Protocol（DHCP）实现的。DHCP 允许一个 host 自动获取一个 IP 地址。

由于 DHCP 能够自动将一个 host 连入网络，它也叫 plug-and-play 或者 zeroconf protocol。

DHCP 的四步如下：

• DHCP server discovery。刚进来的 host 又不知道 DHCP server 的 ip 地址。它怎么发消息呢？事实上，它通过使用一个叫 DHCP discover message（一个发到 67 端口的 UDP packet），并且采用广播的方式。这个 datagram 的 destination 是广播地址 255.255.255.255（或者一个子网内的），source IP 地址是 0.0.0.0（”this host”）。
• DHCP server offer(s)。DHCP server 收到 DHCP discover message 后，会回复（依然是广播）一个 DHCP offer message。由于一个子网里可能有多个 DHCP servers，client 可能会能够从很多个 offers 中选择一个。DHCP server message 包含事务的 ID，client 所请求的 IP 地址，network mask 和一个该 IP 地址的有效时间。
• DHCP request。新来的 client 会在多个 DHCP server offers 中选择一个，然后朝它选择的那个回复 DHCP request message。
• DHCP ACK。server 收到 DHCP request message 后会回复一个 DHCP ACK message。

4.3.4 Network Address Translation (NAT)

NAT 所做的就是把一个大的本地网络（比如 LAN）和公网接到一起。这个本地网络本来就有自己的一套 private addresses。怎样做到 WAN 的地址和 LAN 的地址的转换？

对于外界来说，这整个 LAN 的 IP 地址都是一样的，都是 NAT router input link interface 的那个 IP 地址，但是它们传进来不同的端口号（port#），NAT router 需要维护一个 translation table，根据这个端口号 forward 到正确的 LAN 地址。

private IP 地址 + NAT 的方案也（在一定程度上）解决了 IP 地址不够用的问题。

NAT 实现：发出（outgoing）的 datagram 里将（source IP address，port #）替换为（NAT IP address，new port#）。维护一个 NAT translation table。往外发（incoming）的 datagram 将 （NAT IP address，new port#）替换为（source IP address，port #）。

本质上其实就是用 IP + port 换 IP。

NAT 其实是有争议的：它违反了 end-to-end 原则。作为网络层的东西，它修改到上层的 packet 里的内容了。

4.3.5 IPv6

tunneling：IPv6 的 datagram 作为 IPv4 包中的 payload 存在，在 IPv4 routers 之间传递。

4.4 Generalized Forwarding and SDN

前面我们概括了基于地址的 forwarding 有两个步骤：查询目标地址（match），将 packet 发送到指定的输出端口（action）。现在我们来考虑一个更推广的 match+action 范例：这里 match 可以对多个 header fields 上做，action 可以包括 forwarding，在许多 outgoing interfaces 上做 load balancing，重写 header values（NAT），故意 block、drop 这个 packet，将 packet 发送到一个特定的 server 来进一步处理（例如 DPI）。

在这个推广的 forwarding 中，一个 match+action table 推广了之前 forwarding table 的概念。

例子：OpenFLow，一个高度可视化的，成功的 match+action 抽象标准。我们考虑 OpenFlow 1.0。

每一个 match+action forwarding table 中的 entry（被称作 flow table）包含：

• 一个 header fields values 的集合，用来 match。
• 一个 counters 的集合，当 packets match 这个 entry 时会被更新。这些 counters 可能包括 match 这个 entry 的 packet 的数量，或者这个 entry last updated 的时间，etc。
• 一个 actions 的集合。当 packet match 这个 entry 时，这些 actions 会被执行。这些 action 可能包括 forward 到特定的 output port，drop 这个 packet，复制 packet 并且发送到多个 output 口以及重写 header fields。

Chapter 5: The Network Layer: Control Plane

在本章，我们通过讲述控制 control plane 继续我们的网络层之旅。在 5.2，我们会讲述传统路由算法，即计算一张图中最小花费路径的算法；这些算法基于两个被广泛部署的 Internet routing protocols：OSPF 和 BGP，我们会在 5.3 和 5.4 分别讲到这两个协议。我们将会看到，OSPF 是一个在单个 ISP 网络里工作的路由协议。而 BGP 是一个为所有 Internet 中相互连接的网络服务的协议。我们还会讲到 SDN，它将 control plane 的功能实现在了一个分离的 controller 上。

在 5.6 和 5.7，我们会讲述管理 IP network 的一些组成部分：ICMP（the Internet Control Message Protocol）和 SNMP（the Simple Network Management Protocol）。

5.1 Introduction

我们注意到 forwarding table 和 flow table 是连接网络层数据和控制平面的主要元素。在本章，我们会学习这些表是怎样被计算出来，维护并且实装上的。在之前的 Introduction 章节，我们学习过有两种建表的方式：

• Per-router control。就是每一个 router 上都运行着 routing algorithm，然后它们之间可以互相交流，最后维护出 forwarding table。OSPF 和 BGP 协议都是基于 per-router approach。

• Logically centralized control。有一个逻辑上的中心控制单元，它会统一计算并且分配 forwarding tables 到每一个 router。前面提到过的推广的 match+action 抽象允许 router 提供传统 IP 的 forwarding 服务以及一些丰富的其它功能（这些功能以及预先实现在一些分离的 middleboxes 中）。

  controller 和一个在每个 router 上的 control agent（CA）交互，通过一个定义好的协议，以此来配置、管理 router 的 flow table。通常 CA 的功能非常简单，只是和 controller 交流，并且按照 controller 的指令工作。不像之前的 routing 算法，CA 之间并不互相交流。这是 per-router 和 logically centralized control 的关键区别。

  SDN 采用了这种 logically centralized control 的概念。

5.2 Routing Algorithms

通常地，一个好的路径是费用最小的路径。但是真实世界还要考虑比如政策因素（属于 Y 组织的 router

不能向 Z 组织的网络 forward）等等。无论如何，必须有一列定义好的 routers 序列，packet 会穿过这些 routers，从 sending 到达 receiving。

在网络层的上下文中，node 指的是 routers，edges 则是连接这些 routers 的 physical links。

广泛地讲，我们能根据算法是中心化的还是去中心化的将 routing algorithms 分为两类：

• A centralized routing algorithm。它通过对网络的 global knowledge 计算 source 和 destination 的最短路。这个计算可以运行在 logically centralized control 上，也可以被重复运行在 per router 上。（replicated）有 global state information 的算法经常被叫做 link-state（LS）algorithms，因为算法必须考虑到网络中的每个 link。
• A decentralized routing algorithm。最小路径的计算通过一个迭代的，分布式的方式在 routers 中计算。没有 node 拥有所有 network links 的完整信息。取而代之，每一个 node 从它们直接相连的边的信息开始。然后，随着一个迭代的计算、交换信息的过程，一个 node 逐渐计算出到一个 dest 或多个 dest 的最小路径。我们将会学习 distance-vector（DV）算法，这个算法的名字是因为每个 node 维护了一个到其它所有 node 的距离向量。

第二种分类方式是根据算法是 static 的还是 dynamic 的。在一个 static routing algorithms，router 随时间改编得很慢，并且改变通常是由于人类接入。dynamic routing algorithms 会根据网络负载或者拓扑结构的变化动态改变算好的 routing paths。一个 dynamic 算法可以阶段性地持续运行，或者由网络的变化触发运行。

第三种分类的方法是根据它们是否是 load-sensitive 的。一个 load-sensitive 的算法，link 的花费动态变化来反映目前这个 link 的拥塞情况。如果一个拥塞的 link 被分配了 high cost，算法会倾向于饶过它。现在的 routing algorithms（RIP，OSPF 和 BGP）都是 load-insensitive 的，因为一个 link 的 cost 没有显式地反映它的拥塞情况。

5.2.1 The Link-State (LS) Routing Algorithm

Initialization:
	N' = {u}
	for all nodes v
		if v is a neighbor of u
			then D(v) = c(u, v)
		else D(v) = +\infty

Loop
	find w not in N' such that D(w) is a minimum
	add w to N'
	update D(v) for each neighbor v of w not in N':
		D(v) = min(D(v), D(w) + c(w, v))
until N' = N

就是 Dijkstra 算法。

问题：如果这是一个 load-sensitive 的情况，也就是边权随着拥塞情况变化，可能能构造出一个“振荡”的例子。可能发出一个 packet，结果还没到目的地，路由更新了，packet 就一直在顺时针、逆时针跑，最后 TTL 到了被丢掉。

一个解决方案是不考虑 sensitive，也就是 cost 与拥塞情况无关，这其实不太能接受因为 routing 的一个目标就是避开重度拥堵的 links。另一个解决方案是保证不是所有的 routers 都在相同的时间运行这个算法。

5.2.2 The Distance-Vector (DV) Routing Algorithm

Initialization:
	for all destinations y in N:
		Dx(y) = c(x, y) // if y is not a neighbor, c(x,y) = +\infty
	for each neighbor w:
		Dw(y) = ? for all destinations y in N
	for each neighbor w:
		send distance vector Dx = [Dx(y): y in N] to w

Loop
	Wait (Until I see a link cost change to some neighbor w, or until I receive a 			distance vector from some neighbor w)
	
	for each y in N:
		Dx(y) = min_v {c(x, v) + Dv(y)} (v is its neighbor)

    if Dx(y) changed for any destination y:
        send distance vector Dx = [Dx(y): y in N] to all neighbors
Forever

核心思想：Bellman-Ford Equation

Node x 知道到每个 neighbor 的距离 c(x, v)；Node x 维护自己的 distance vector Dx=[Dx(y): y in N]；Node x 也维护它 neighbor 的 distance vectors

• For each neighbor v，x 维护 Dv=[Dv(y): y in N]

Distance-Vector Algorithm: Link-Cost Changes and Link Failure

现在我们来考虑，如果一个 link 的 cost 上升了会发生什么。

• 在 link cost 改变前，Dy(x) = 4, Dy(z) = 1, Dz(y) = 1, Dz(x) = 5。在 t0 时刻，y 检测到 link cost 改变（4 到 60）。y 重新计算它到 x 的距离（遍历所有邻居）

  $$D_y(x) = \min \{c(y, x) + D_x(x),\ c(y, z) + D_z(x)\} = 6$$

  当然，在全局视角，我们可以看出这个通过 z 的新 cost 是错的，因为 5 这条路已经不可行了。这就产生了一个 routing loop：为了到达 x，y routes 到 z，但是 z routes 到 y。

• 因为 y 计算了 x 的一个新的最小花费，它将新的 dv 在 他 t1 时发给 z。

• 在 t1 过了一些时间后，z 收到了 y 的新 dv，这个 dv 说 y 到 x 的新的最小距离是 6。z 知道它可以用 1 的花费到达 y，因此计算了一个新的到达 x 的距离

  $$D_z(x) = \min\{50 + 0, 1 + 6\} = 7$$

  因为 z 到 x 的最小距离上身了，它又给 y 发了新的 dv。

• 这样来回往复，Dy(x) 更新成 8，然后 Dz(x) 更新成 9。

那么这个过程会持续多久呢？答案是，会知道 z 最终通过 y 计算这个距离超过了 50。这样 z 会最终选择最小花费 path 是直接连到 x，而不是通过 y。但是我们发现这个计算复杂度和边权有关。这被称为 count-to-infinity problem。

Distance-Vector Algorithm: Adding Poisoned Reverse

上面这个问题可以用一个叫做 poisoned reverse 的技术解决。它的思想非常简单，如果 z 通过 y 路由到 x，那么 z 会告诉 y 它到 x 的距离是正无穷。也就是说 z 告诉 y，Dz(x) = 正无穷（即使 z 事实上知道 Dz(x)=5）。z 会继续说这个善意的谎言，直到它通过 y 到达 x。

毒性反转没有解决一般意义上 count-to-infinity 问题。

5.3 Infra-AS Routing in the Internet: OSPF

我们之前的模型将 network 简化成一堆互相连接的 routers，并且这些 routers 上都执行着相同的 router 算法。这个模型过于简单化，主要有如下两个理由：

• Scale。当 routers 的数量太多之后，交换，计算以及存储 routing information 的 overhead 令人望而却步。在一个有许多路由器上运行的 DV 算法可能永远都不会收敛。
• Administrative autonomy（行政自治）。一个 ISP 希望由自己喜欢的方式操作自己的网络，或者将网络内部的组织隐藏起来。理想状态下，一个组织应该能够以它想要的方式操作、管理网络，同时能够和外界连接。

这两个问题都能通过将 routers 组织成 autonomous systems（ASs）来解决。每个 AS 由一组在相同管理控制下的 routers 组成。在一个 AS 内的 routing algorithm 被叫做一个 infra-autonomous system routing protocol。（Infra-AS routing VS Inter-AS routing）

Open Shortest Path First (OSPF)

…

5.4 Routing Among the ISPs: BGP

…

5.5 The SDN Control Plane

…

5.6 ICMP: The Internet Control Message Protocol

…

5.7 Network Management and SNMP

…

5.8 Summary

…

Chatper 6: The Link Layer and LANs

在前两章中，我们学习了网络层给任意两个 hosts 提供沟通服务。在这两个 hosts 间，datagrams 穿过一系列 communication links（有线或无线），从 source host 开始，经过一系列 packet switches，然后到达目标 host。当我们从协议栈继续往下，我们自然会好奇 packets 怎样在独立的 links（组成了 end-to-end communication path）上传输。

在讨论链路层时，我们会看到两种基本的链路层 channel 的类型。第一种是广播 channel，它通过无线 LANs，卫星网络和HFC（混合光纤同轴电缆）等将不同 hosts 连起来。由于不同的 hosts 连接在相同的广播 channel 上，往往需要一个 central controller 来协调传输；有时 hosts 自己也可以协调传输。第二种是点到点的通讯连接，例如通常可以见到的连接两个 router 的很长的 link，或者一个用户的 PC 和最近的 Ethernet switch。协调点到点的 link 更加简单。

我们会在本章讨论几个重要的链路层概念和技术。我们会深入探讨 error detection 和 correction。我们会考虑 multiple access networks 和 switched LANs，包括 Ethernet。我们还会关注 virtual LANs 和 data center networks。

6.1 Introduction to the Link Layer

我们将任何运行链路层协议的一个 device 称作 node，包括 hosts，routers，switches 和 WiFi AP（在第七章讨论）。我们也将连接相邻 nodes 的通信通道叫做 links。为了将一个 datagram 从 source host 到 destination host 运输，它需要经过 end-to-end path 上的每一个独立的 links。在一个给定的 link 上，一个传输的 node 将 datagram 封装成一个链路层的 frame。例如在公司网络中，从一个无限设备上发送一个 datagram 就要经过 6 个 link：一个到 AP 的 WiFi link；AP 到 switch 的 Ethernet link；链路层 switch 到 router 的 link；两个 routers 之间的 link；一个 router 和又一个链路层 switch 的 link；最终一个 switch 和 server 的 Ethernet link。

6.1.1 The Services Provided by the Link Layer

包括

• Framing。即将 datagram 包装到一个 link-layer frame 里。一个 frame 包括一个 data field（payload，也就是 datagram 插入的地方）和一些 header fields。
• Link access。A medium access control（MAC）协议制定了一个 frame 在 link 上传输的规矩。当很多节点共享一个 broadcast link（即 multiple access problem）时，MAC 协议负责调度这些传输。
• Reliable delivery。一个链路层的可信服务经常被用于一些高错误率的介质，例如一个无线连接，目的是直接在 link 上纠错（而不是要求一个 end-to-end 的 retransmission）。不过对于 fiber，coax 和双绞铜线等，错误率其实是很低的，所以很多有线链路层协议不提供这个。
• Error detection and correction。也是通过 frame 中插入 error-detection bits，然后接收端进行一个 error check。而链路层的 error detection 经常更精细，并且它实现在硬件上。

6.1.2 Where Is the Link Layer Implemented？

大部分的链路层实现在一个 network adapter（有时也被叫做 network interface card，NIC。网络接口卡，也就是传说中的网卡）。

6.2 Error-Detection and Correction Techniques

在 sending node 端，data D 后面会附上 error-detection and correction bits（EDC）。在接收端，D’ 和 EDC’ 被接受。注意 D’ 和 EDC’ 会和原来的不一样（传输 bit 反转的结果）。

接收端的挑战是确定 D; 是否和原来的 D 一样，只给定 D’ 和 EDC’ 的条件下。

6.2.1 Parity Checks

最简单的纠错是使用一位 parity bit（奇偶校验）。在一个 even parity scheme 下，parity bit 保证 D 和 EDC 中 1 的总个数是偶数。

two dimensional bit parity：不仅可以 detect 还可以 correct single bit error。（纵横定位，就能找到错误位置）

receiver 能同时查错纠错的能力被叫做 forward error correction (FEC)。

6.2.2 Checksumming Methods

…

6.2.3 Cyclic Redundancy Check (CRC)

现在被互联网广泛使用的纠错技术基于 cyclic redundancy check codes。CRC codes 也叫做 polynomial codes，因为它将 bit string 看作系数为 0/1 的多项式，并且在多项式算术上进行操作。

考虑一个 d-bit 的 data 串 D。sender 和 receiver 首先要在一个 r+1 bit 的 pattern 上达成共识，这部分叫做 generator，我们记作 G。我们要求 G 的最左边一位为 1。给定 D，sender 会选择一个 r 位 bits R，把它接在 D 的后面产生 d+r 位 pattern，这个二进制数能被 G 精确整除（在模 2 运算下）。error checking 的过程很简单：如果 receiver 发现这个 d+r 数不能被 G 整除，那么出错。

我们想要找到一个 r bit 数 R 使得

$$D \cdot 2^r \text{ XOR } R = nG$$

那么

$$D \cdot 2^r = nG \text{ XOR } R$$

这告诉我们如果我们将 $D \cdot 2^r$ 除以 G，得到的余数就是 R（XOR 就是模 2 下的加法）。因此我们可以计算

$$R = \text{remainer} \frac{D \cdot 2^r}{G}$$

附加内容：Hamming Distance（HD）

其实就是在 n 维超立方体上的距离。比如两个二进制串，你只要比较几位不同，Hamming Distance 就是几。

结论：为了查 d 个错误，需要一个海明距离为 d+1 的编码方案；为了纠 d 个错误，需要一个距离为 2d+1 的编码方案。

6.3 Multiple Access Links and Protocols

回顾两类 links：

• Type 1：point-to-point
  • PPP（point-to-point protocol）
  • point-to-point link between Ethernet switch 和 host
• Type 2：broadcast（shared wire or medium）
  • 老式 Ethernet
  • 802.11 wireless LAN

计算机网络也有所谓的叫做 multiple access protocols 的协议来规定 nodes 传输到 shared broadcast channel 里的行为。

因为所有 nodes 都能传输 frames，大等于 2 的 nodes 可以同时在 channel 里传输 frames。当这件事发生时，所有 nodes 都同时收到多个 frames；也就是说，传输的 frames 在所有接收者上发送碰撞了（collide）。

我们可以将 multiple access protocols 分成三类：channel-partitioning protocols，random access protocols 和 taking-turns protocols。

我们来总结一下，理想情况下，一个 R bits/sec 的 channel 上的 multiple access protocols 应该有如下特性：

• 当只有一个 node 有数据要发送时，node 具有 R bps 的 throughput。
• 当 M 个 nodes 有数据要发送时，每一个 node 有 R/M 的 throughput bps。这并不要求每时每刻的瞬时速率都是这个，而是平均要这样（在一个合适的时间间隔内）。
• 协议是分布式的。
• 协议要简单。

6.3.1 Channel Partitioning Protocols

回忆：FDM 和 TDM。TDM 将时间分割成 time frames，进一步每个 frame 被分成 N 个 time slots。每个 time slot 被分配到 N nodes 的其中一个中。当一个 node 有 packet 要发送时，它在这个 slot 里发送 packet 的 bits。

TDM 的好处是它消除了碰撞并且完美地公平。但是有两个主要的缺点：首先，即使只有一个 node 在工作（其它在睡觉），throughput 也只是 R/N bps。第二个缺点是一个 node 必须要在 transmission sequence 里等到自己的 turn 才能发送，即使只有一个 node。

FDM 将 R bps 的 channel 分成不同的频率，每个有 R/N 的 bandwidth，然后给每个 node 分配一个 frequency。FDM 和 TDM 也有着相似的缺点——单个 node 最多也只能 R/N bandwidth。

第三个 channel partitioning protocol 是 code division multiple access（CDMA，码分复用）。它给每个 node 分配了一个不同的 code。每个 node 使用它们自己的 node 来 encode data。如果 codes 选的好，CDMA 网络可以允许不同网络同时传输并且同时接受。我们会在第七章详细讲（因为它和 wireless 关系密切）。

6.3.2 Random Access Protocols

在一个 random access protocol，每一个参与 collision 的 node 都重新发送它们自己的 frame。不过当一个 node 发生碰撞时，它不立刻重发；它会等待一段随机的时间。在这个部分我们会简单描述一些常用的 random access protocol——ALOHA protocol，和 carrier sense multiple access（CSMA）protocols。Ethernet 就是一个流行的 CSMA protocol。

Slotted ALOHA

当 frame 到达时，node 立即发送。

当碰撞发生时，将时间分为很多 slots。每个 nodes 在每个 slot 开始时抛一枚硬币，p 的概率在这个 slot 开始时 retransmit；1-p 的概率等到下个 slot 再抛硬币。

成功的概率：node transmit，并且没有其它的 node 在该 slot 里传输。也就是 $p(1-p)^{N-1}$。

ALOHA

Slotted ALOHA 要求所有节点在一个 slot 开始时同步传输。而 pure ALOHA 不用对齐。

如果碰撞发生，有 p 的概率立即重新发送，1-p 的概率等待一段时间（这段时间就是 a frame transmisson time）。然后在等待完之后，继续抛硬币。

成功的概率：当一个节点传输时，它的前一段时间、后一段时间都没人传输。也就是 $p(1-p)^{2(N-1)}$

Carrier Sense Multiple Access (CSMA)

ALOHA 低效的原因：传输时没考虑其它节点！

CSMA：listen before transmit（don’t interrupt others!）。adapter 会监听信道是否空闲，如果空闲，它立即传输数据；如果不是，等待直到监听到空闲。

Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

CSMA 还是可能会出现碰撞（如果两个人都觉得信道是空闲的，都开始 transmit）。CSMA/CD 加入了 collision detection（通过 measure signal strengths，compare transmitted，received signals）。如果碰撞了，会立刻 abort。在 abort 之后，随机等待一段时间。

等待的策略：binary exponential backoff 算法。简单来讲，就是当一个 frame 以及经历了 n 次碰撞后，它会随机从 $\{0, 1, 2, \dots, 2^n-1\} = [0, 2^n-1]$ 中选择一个时间来等待。

6.3.3 Taking-Turns Protocols

回忆起我们想要的两个性质：当只有一个节点通信时，有 R 的吞吐；当 M 个节点同时通信时，有 R/M 的吞吐。ALOHA 和 CSMA 有第一个性质但是没有第二个，这引出了新的一类 mac 协议——taking-turns protocols。

第一种方式是 polling。有个 master node，它 polls 每一个 nodes（使用 round-robin 的方式）。它消除了碰撞和空 slots。但是缺点有，它引入了 polling delay；以及如果 master node fails，全寄。

第二种是 token-passing protocol。这里没有 master node，而是由一种用于特殊用途的 token 来在节点中以固定顺序交换。当一个节点收到 token 时，如果它有数据要传，它保留这个 token；否则它把 token 交给下一个 node。

6.3.4 DOCSIS: The Link-Layer Protocol for Cable Internet Access

…

6.4 Switched Local Area Networks

6.4.1 Link-Layer Addressing and ARP

MAC Addresses

事实上，hosts 和 routers 没有链路层地址，只有它们的 adapters（也就是 interfaces）有，就像 IP 一样。一个很重要的事实是，链路层的 switches 没有链路层地址。这是因为链路层 switches 的目的是在 hosts 和 routers 间传递 datagram，它透明地完成这些工作，不需要被寻址。

一个链路层地址可以被叫做一个 LAN 地址，物理地址或者一个 MAC 地址。对于大多数 LANs（包括 Ethernet 和 802.11），MAC 地址有 6 bytes 长。

MAC 地址的一个有趣的性质是，没有两个 adapters 有相同的地址。这很令人震惊——因为这些东西在不同国家的不同工厂被生产。答案是，IEEE 管理者 MAC 地址空间。也就是说，当一个公司想要生产 adapters 时，它购买一端 2^24 地址的地址空间 chunk。

有时候，一个 sending adapter 希望所有其它的 LAN 里的 adapter 里收到并处理这个 frame。因此 LANs 保留了一个广播地址，全 F。

Addressing Resolution Protocol (ARP)

由于同时存在网络层的地址（例如 IP）和链路层的地址（例如 MAC），就需要在它们之间互相翻译。

每一个 LAN 上的 IP node 都有 ARP table。ARP table：IP/MAC 地址映射。

ARP 很像 DNS，但是一个重要的区别是 ARP 只在相同的子网中解析地址。

ARP 协议是哪一层的？网络 or 链路，都行吧。一般说 TCP/IP 里在网络层，因为还没有 MAC 地址嘛。

工作原理：如果发现 sending 方 IP 地址不在 ARP table 的 entry 中，sender构造一个特殊的 packet 叫做 ARP packet。一个 ARP packet 包含 sending 和 receiving 的 IP 和 MAC 地址的 field。ARP query 和 response 的包结构都是一样的。这个 query 的目的是问子网中其它所有 hosts 和 routers 来确定这个 IP 地址对应的 MAC。也就是说，它要发到广播地址。然后那个 match 的人会发回一个 response，update 那个 host 的表。

Sending a Datagram off the Subnet

现在 ARP 在一个子网内发送 datagram 的原理以及很清楚了。但如果一个 host 想要发送 datagram 到子网外的另一个 host 呢？注意到中间肯定有个 router，router 有两个 interface，一个在 subnet 1 内，一个在 subnet 2 内。

6.4.2 Ethernet

…

6.4.3 Link-Layer Switches

Self-Learning

Switches Versus Routers

虽然 switches 也是一个 store-and-forward 的 packet switch，它和 routers 的不同之处在于它使用 MAC 地址来 forward。router 是一个 layer-3 的 packet switch，而 swithc 是一个 layer-2 的。

此外，还有一个概念叫 Hubs（集线器）。这位更是

	Hubs	Routers	Switches
Traffic isolation	No	Yes	Yes
Plug and play	Yes	No	Yes
Optimal routing	No	Yes	No

6.4.4 Virtual Local Area Networks (VLANs)

6.5 Link Virtualization: A Network as a Link Layer

…

6.6 Data Center Networking

…

6.7 Retrospective: A Day in the Life of a Web Page Request

这一章可以帮你过一遍网络结构。

6.8 Summary

…

Chatper 7: Wireless and Mobile Networks

7.2.1 CDMA

7.3.2 The 802.11 MAC Protocol

CSMA may fail:

• Hidden Terminal Problem。也就是 A B C，A C 都想给 B 发送数据，但是 A C 距离较远，彼此都听不到对方，因此 A C 同时向 B 数据会发生碰撞，使得 B 无法正常接受。
• 无线信号传递的特点：信号衰减快。所以 802.11 适配器上接收到的强度要远小于发送信号的强度（可能差几百万倍）。实现碰撞检测花费过大。

CSMA/CA 原理：

• 如果一开始 station 感知到这个 channel 是 idle 的，它在一段间隔后传输数据（这段间隔被称作 Distributed Inter-frame Space，DIFS）。
• 否则，station 选择一个 random 的 backoff。它也是使用 binary exponential backoff。然后在 DIFS 之后，如果 channel 是 idle 的，它会减少倒计时。注意如果 channel 是 busy 的，这个 counter 的 value 不变。
• 当 counter 减到 0 时（注意此时肯定是 idle 的），station 将 frame 传输出去，等待 ack。
• 如果收到一个 ack，那么说明数据被正确传输。如果没有收到，重新进入 backoff 阶段（step 2），backoff 是一个从大范围选择的随机值。

回忆 CSMA/CD。注意在倒计时时，CSMA/CA 即使在 channel idle 时也不传输，而是等候。而 CSMA/CD 一旦空闲就传输（指 busy 时，CSMA/CD 会先等着。然后 idle 了立刻开传，只有碰撞了才开始等；而 CSMA/CA 会在 sense 到 busy 时就进入 random backoff，并且只在 idle 时减少 counter）。这是因为 CSMA/CA 希望”avoid collision”。

Dealing with Hidden Terminals: RTS and CTS

当一个 station 想发 frame 时，它可以先发一个 RTS frame 到 AP，这个 frame 里面说清楚传输 data 和 ack 需要的总时间。然后 AP 回复一个 CTS（广播），这主要有两个目的：告诉这个 station 可以发，并且告诉其它站在这段期间不能发。

Power Management

休眠机制：一个 node 休眠取决于：它有没有消息发给别人，以及别人有没有消息发给它。AP 会间隔广播一个叫 beacon frame 的包，如果 node 在里面没发现送给自己的 frame，并且自己也没有数据需要发送，则它会告诉 AP 自己进入睡眠状态（直到下一个 beacon frame）。

Chapter 8: Security in Computer Networks

…

Chapeter X: Communication Principle

信息量：

$$I(x_j) = \log_a(\frac{1}{p(x_j)}) = - \log_a p(x_j)$$

信息熵：

$$H(X) = E[I(X)] = - \sum_{j=1}^n p(x_j) \log_a p(x_j)$$

信号的分类：

• 模拟信号（连续，一系列）
• 数字信号（离散，01）

真实传输的时候是数字信号（Use）。

带宽（bandwidth，单位Hz）：信号在频域上正半轴的信号宽度，即信号包含的谐波最高频率与最低频率之差。

傅里叶变换卷积定理：时域上的卷积等于频域上的乘积。

基带信号是一个频域上包含很接近0的部分的信号，频带信号就是可以是任意一段频率的信号。

基带传输的问题：不能支持 channels（比如 FDM）

频带传输（passband）：可以在某个频段进行传输，支持多个频段。

Modulation：一个基带信号经常被一个载波（carrier）所调制成一个频带信号来使得它可以通过 radio 进行传播。分类：AM，FM，PM