计算机网络：自顶向下方法 阅读笔记 <Computer Networking: A Top-Down Approach> 2024.10.22 Course Notes

1 计算机网络和因特网、

1.1 什么是因特网

• 终端系统
  • 主机
  • 运行使用因特网的服务
• 通信链路
• 分组交换机
  • 路由器
  • 链路层交换机
• 因特网服务提供商
  • 你说得对，从NJU WLAN接入

1.2 网络边缘

如端系统、客户、服务器、数据中心等。

1.3 网络核心

即由互联因特网端系统的分组交换机和链路构成的网状网络。

分组交换

• 存储转发传输：交换机开始向输出链路传输该分组的第一个比特之前，必须接收到整个分组。
• 排队时延和分组丢失：如果到达的分组需要传输的链路正忙，就需要承受排队时延。而受限于有限的缓存大小，如果到达时队列已满，将出现分组丢失（丢包）。
• 转发表和路由选择协议：每台路由器具有一个转发表，将目前地址映射为输出链路。路由器检查该地址并选择合适的出链路。

电路交换
传统电话，创建专用的端到端连接。

• 频分复用：在连接期间链路为每条连接专设一个频段，如无线电台。
• 时分复用：实践划分为固定时段的帧，网络在每个帧中为该连接指定一个时隙。如老电话。

趋势向分组交换而非电路交换。

1.4 分组交换网中的时延、丢包和吞吐量

• 单台路由器上的时延
  • 节点处理时延：检查分组的头部和决定该分组导向何处。
  • 排队时延：在链路上排队等待传输 。
    • 流量强度：分组到达速率 * 平均大小 / 传输速率，必须小于1。
    • 一旦流量强度大于1，将导致无限大的排队时延（假设容量无穷），或者一大堆丢包。
  • 传输时延：将分组中的所有比特推向链路（实际上占比最大）。
  • 传播时延：取决于链路种类（光纤等）。
• 端到端时延
  • 将路径上的所有路由器的时延相总和。
• 吞吐量：接收者主机接收到文件的速率（bps）。
  • 瓶颈链路：路径上所有路由器中传输速度最慢的。

1.5 协议层次和服务模型

该课程使用如下模型：

• 应用层
• 运输层
• 网络层
• 链路层

封装

• 网络应用产生应用层报文（application-layer message）传送给运输层。
• 运输层收取报文并附上附加信息（允许接收端运输层向上向适当的应用程序交付报文，差错位检测等），生成运输层报文段（transport-layer segment），这就是一层封装，然后向网络层传输该报文段。
• 网络层收取报文段，增加系统地址等信息，生成网络层数据报（network-layer datagram），传递给链路层。
• 链路层增加自己的首部信息生成链路层帧（link-layer frame）。
• 最后通过物理层（电线等）传递给链路层交换机。

2. 应用层

2.1 网络应用原理

• 客户-服务器体系结构
  • 有一个总是打开的主机称为服务器
  • Web, FTP, Telnel, mail
• 对等（P2P）体系结构
  • 每台主机既是客户也是服务器

客户通过套接字（socket）的软件接口向网络发送报文和从网络接收报文。

运输服务四个方面：

• 可靠数据传输
  • 确保应用程序的一段发送的数据正确完全地交付
• 吞吐量
  • 带宽敏感的应用具有一定的吞吐量要求
• 定时
• 安全性

运输服务：

• TCP
  • 面向连接：三次握手，同时收发报文
  • 可靠的数据传输服务
• UDP
  • 无连接
  • 不可靠的数据传输

2.2 Web和HTTP

HTTP

HTTP(HyperText Transfer Protocol)超文本传输协议，定义了Web客户向Web服务器请求Web页面的方式，以及服务器向客户传送Web页面的方式。

HTTP使用TCP作为支撑运输协议。HTTP是一个无状态协议，其服务器不保存关于客户端任何信息（但是有Cookie）。

非持续连接和持续连接

• 非持续连接：每个请求/响应是经一个单独的TCP连接发送
• 持续连接：所有的请求机器响应经相同的TCP连接发送

往返时间RTT：指一个短分组从客户端到服务器然后再返回客户所花费的时间。发起连接-收到回复产生一个RTT，请求文件-收到文件产生一个RTT + 文件传输时间。

HTTP响应报文

此处使用了HEAD来仅请求头部信息。GET会在之后附上data。

• 状态行（status line）
  • 指示使用HTTP/1.1，并且正常200 OK。
• 首部行（header line）
  • 每行形如Name: Value
• 实体体（entity body）

你说得对，这部分不考，但是我希望你知道：

• 1xx：信息性状态码
  • 100 Continue：初始部分已接收，客户端可以继续请求。
  • 101 Switching Protocols：服务器正在切换协议。
• 2xx：成功状态码
  • 200 OK：请求成功，响应包含所请求的数据。
  • 201 Created：请求成功并创建了新的资源。
  • 202 Accepted：请求已接受，但尚未处理。
  • 203 Non-Authoritative Information：请求成功，但返回的信息来自其他来源。
  • 204 No Content：请求成功，但没有返回内容。
  • 205 Reset Content：请求成功，但客户端应重置视图。
  • 206 Partial Content：部分内容已成功返回。
• 3xx：重定向状态码
  • 300 Multiple Choices：请求的资源有多种选择。
  • 301 Moved Permanently：请求的资源已被永久移动到新位置。
  • 302 Found：请求的资源临时移动到其他位置。
  • 303 See Other：应使用GET方法访问其他URI。
  • 304 Not Modified：自上次请求后资源未被修改。
  • 305 Use Proxy：请求的资源必须通过代理访问。
  • 307 Temporary Redirect：请求的资源临时移动，保持原有方法。
• 4xx：客户端错误状态码
  • 400 Bad Request：请求无效，服务器无法理解。
  • 401 Unauthorized：未授权，需身份验证。
  • 402 Payment Required：保留状态，暂未实现。
  • 403 Forbidden：服务器拒绝请求，无法访问资源。
  • 404 Not Found：请求的资源未找到。
  • 405 Method Not Allowed：请求方法不被允许。
  • 406 Not Acceptable：请求的资源不可接受。
  • 407 Proxy Authentication Required：需要代理身份验证。
  • 408 Request Timeout：请求超时，客户端未及时发送请求。
  • 409 Conflict：请求冲突，导致无法完成。
  • 410 Gone：请求的资源已永久删除，不再可用。
  • 411 Length Required：未提供Content-Length头。
  • 412 Precondition Failed：请求的先决条件失败。
  • 413 Payload Too Large：请求体过大，服务器无法处理。
  • 414 URI Too Long：请求的URI过长。
  • 415 Unsupported Media Type：不支持的媒体类型。
  • 416 Range Not Satisfiable：请求的范围不满足。
  • 417 Expectation Failed：期望失败。
• 5xx：服务器错误状态码
  • 500 Internal Server Error：服务器内部错误，无法完成请求。
  • 501 Not Implemented：服务器不支持请求的方法。
  • 502 Bad Gateway：作为网关或代理的服务器接收到无效响应。
  • 503 Service Unavailable：服务器当前无法处理请求。
  • 504 Gateway Timeout：作为网关或代理的服务器未能及时响应。

Cookie
HTTP是无状态的，这不错，但是一个web站点希望能够识别用户，因此在传给用户的包中设置cookie，之后的通信中用户都会带上这个cookie，以方便识别。

Web缓存
ISP通常有Web缓存，在用户试图连接网站时，先从Web缓存中查找是否已经有过缓存。

2.4 DNS（域名服务）

DNS提供进行主机名到IP地址转换的目录服务。
DNS是一个由分层的DNS服务器实现的分布式数据库，使得主机能够查询分布式数据库的应用层协议。

在用户试图发送包时，必须得到URL的IP地址。

• 访问同一台主机上运行DNS应用的客户端
• 将URL传给DNS应用
• DNS向DNS服务器发送请求
• 收到回答报文

分布式、层次数据库
根DNS服务器，顶级域DNS服务器和权威DNS服务器。

Root DNS Server
com DNS Server    org DNS Server    edu DNS Server
xxx.com           xxx.org           xxx.edu

本地DNS服务器

本地DNS服务器能够缓存IP地址。

2.5 P2P文件分发

最小分发时间$D_{cs} \geq \max \{ \frac{NF}{u_s}, \frac{F}{d_{min} } \}$，即同时考虑服务器自身的上传速度和所有对等方最小的下载速度。

3. 运输层

3.1 运输层服务

运输层是在端系统中实现的。将接收到的应用程序的报文转换为运输层报文段，然后交由下层网络层进行运输。网络层提供了主机之间的逻辑通信，而运输层为运行在不同主机上的进程之间提供了逻辑通信。

UDP提供了一种不可靠、无连接的服务，而TCP提供了一种可靠的、面向连接的服务。在网络层中，IP的服务模型是尽力而为交付模型，因此TCP和UDP的实现并不相同。将主机间交付扩展到进程间交付被称为运输层的多路复用与多路分解。TCP额外有可靠数据传输和拥塞控制。

3.2 多路复用与多路分解

将报文段的数据交付到正确的套接字的工作称为多路分解，将主机的不同套接字中手机数据块，封装为报文段传递到网络层的工作称为多路复用。为套接字设定端口号能够非常精确地描述复用和分解。

3.3 UDP

无需连接建立、无连接状态，嗯传。
UDP报文段：

• 16b源端口号
• 16b目的端口号
• 16b长度
• 16b检验和
• data

3.4 可靠数据传输原理

在写完实验check3后，紧急跳过前面部分先来阅读这一部分。

可靠数据传输为上层实体提供的服务抽象是：数据可以通过一条可靠的信道进行传输。借助可靠信道，传输数据比特将不会受到损坏或丢失，而且所有数据都是按照其发送顺序进行交付。

rdt1.0：如果底层信道是完全可靠的，那么这是rdt1.0。不必担心任何数据损坏和丢失，直接进行传输/接收即可。

rdt2.0：也称停等协议。底层信道的分组中的比特可能受损。基于肯定确认和否定确认控制报文使得接收方能够使发送方知道哪些内容被正确接收。基于这样的重传机制的可靠数据传输协议称为自动重传请求（ARQ）协议。

• 检测差错：check位
• 收方反馈：肯定确认ACK和否定确认NAK
  • 发送方在发送一个包后，必须等待ACK，否则不会传下一个包。如果等待到NAK，那么重传。
• 重传：收到有差错的分组时，发送方将重传
  但是rdt2.0协议的ACK或NAK可能受损，引入的解决方法是：在数据分组中添加一新字段：序号。使用0和1两个序号来表示发的包是重传还是另外的正常传输。由此引入rdt2.1和rdt2.2.

rdt3.0：假定底层信道还会丢包。引入倒计数定时器，控制重传和切断连接。但是仍然基于2.0的停等协议，会出现协议限制底层硬件运行速度的情况。因此有了：

• 回退N步（GBN）：允许发送方发送多个分组而不用等待确认
  • <- ACK -> | <- Outstanding -> <- Sending -> | <- Unavailable ->
  • 一次性发送整个窗口长度N的包，在收到回应后继续发送之后的包。
  • 如果出现超时，那么接收方将丢弃所有失序分组。在得到超时信号后，发送方从超时包开始全部重新发送。
  • 优点：接收缓存简单，接收方不需要缓存任何失序分组。
  • 如果分组序号的比特位数为k，则序号范围为$[0, 2^k - 1]$
• 选择重传（SR）：让发送方仅重传那些它怀疑在接收方出错的分组。对于每个收到的包回应对应的ACK，以此让发送方知道哪些包没有收到。另：窗口长度必须小于等于序号空间大小的一半。

3.5 TCP

三次握手：SYN, ACK + SYN, ACK + DATA

• SYN = 1, seqno = 114
  • 和我讲话！我生成的初始随机序列号为114！
• ACK = 115, SYN = 1, seqno = 514
  • 收到讲话请求，和我讲话！确认前114，期待第115位，我生成的初始随机序列号为514！
• SYN = 0, seqno = 115, ACK = 515, data
  • 收到讲话请求！收到对于114位的确认，现在发送首位序列号115，确认前514位，期待第515位！

关闭连接：客户关闭连接：FIN, ACK / 服务器发送完所有数据后：FIN, ACK

报文段的长度首先于最大报文段长度（MSS）。TCP为每块客户数据配上一个TCP header，从而形成TCP报文段。

• 16b源端口号 + 16b目的端口号
• 32b序号字段 + 32b确认号字段
  • 序号和确认号由双方各自维护
• 4b首部长度字段 + 保留未用字段 + 6bFLAG字段
  • ACK, RST, SYN, FIN, PSH（交给上层）, URG（紧急数据）
• 16b接收窗口
• 16b检验和 + 16b紧急数据指针
• 选项字段
• 数据

书中简单明了的工作图：

loop {
  switch
    从应用层接收到数据e：
      生成报文段向IP传递
      如果定时器未启动，则启动
      维护序列号
    定时器超时：
      重传最小序号而未收到确认的报文段
      重设定时器（加倍时间）
    收到ACK：
      维护ACK
      如果确实有包被对方成功接收，重设定时器（初始时间）
      如果收到了三次冗余ACK，则立刻重传
}

流量控制：维护剩余空间的窗口大小，记录为rwnd (reserve window)，使得发送者不会发送过多的包。

3.7 TCP拥塞控制

需要考虑拥塞窗口和剩余窗口大小的关系，即min( rwnd, cwnd )。

• 慢启动
  • cwnd初始值为一个MSS的较小值，随后不断翻倍。
  • 在收到超时丢包时，设置cwnd为1并重新开始慢启动。此时将ssthresh (Slow Start Threshold)设置为拥塞窗口值的一半。
• 拥塞避免
  • 当cwnd的值到达ssthresh时，结束慢启动并缓慢增加cwnd。
  • 当收到三个冗余的ACK时，ssthresh设置为cwnd的一半，将cwnd的值减半。
• 快速恢复
  • Reno
    • 较新版本，对于三个冗余ACK设置cwnd为0.5 * cwnd + 3
  • Tahoe
    • 早期版本，对于三个冗余ACK也会将cwnd设置为1.

4. 网络层：数据平面

4.1 概述

路由器不运行应用层和传输层的协议。网络层的作用从表面上看极为简单，将分组从一台发送主机移动到一台接收主机。

• 转发：当一个分组到达某路由的一条输入链路时，该路由需要将其移动到适当的输出链路。转发时在数据平面中实现的唯一功能，尽管也是最为常见和重要的功能。
  • 转发是在路由器本地操作，在几纳秒中发生，通常用硬件实现。
• 路由选择：当分组从发送方流向接收方时，网络层必须决定这些分组所采用的路由或路径。计算这些路径的算法称为路由选择算法。
  • 路由是确定分组从源到目的地所采取的端到端路径的网络范围处理过程，发生在几秒钟，因此通常使用软件来处理。

考虑网络层能提供的某些可能的服务：

• 确保交付。确保分组最终到达。
• 具有时延上界的确保交付。在规定时延内交付。
• 有序分组交付。
• 确保最小带宽。如果主机传输的速率低于最小带宽，那么所有分组最终都会交付到目的。最小带宽指的是瓶颈带宽。
• 安全性。提供机密性。

网络层提供了单一的服务，称为尽力而为服务。看上去很不负责，但是实际上能够适用于绝大部分的应用，还是“足够好”的。

4.2 路由器工作原理

接收输入，在交换结构中决定其输出，运送到输出端。

实际上，通过输入端口收到数据后，所有做的工作是：

• 数据链路处理（一些的头部信息）：帧的解析，帧校验，去掉链路层头部。
• 查找：使用最长前缀匹配规则，在该表中寻找最长的匹配项，向最长前缀匹配相关联的链路接口转发分组。
• 转发：在查找到合适的路由表条目后，路由器将分组从输入接口移交到输出接口。修改分组头部的TTL字段（减1，防止环路）。更新校验和。根据下一跳重新封装分组，交给输出接口。
• 排队：在通过该查找确定了某分组的输出端口后，该分组就能够发送进入交换结构。如果有来自其他输入端口的分组正在使用当前该交换结构，那么此时就会产生阻塞。

在这些工作均完成后，该数据将会进入交换结构。

4.2.2 交换

• 经内存交换：在CPU的直接控制下完成。路由器或交换机的CPU负责处理分组。分组先从输入端口被传送到内存，CPU读取分组的头部信息后决定它的输出端口，并将分组写入该端口的缓冲区。
  • 输入端口将分组拷贝到内存。
  • CPU读取分组，根据路由表或转发表查找目的端口。
  • 分组通过内存被传递到对应的输出端口。
  • 由于每个分组必然经过存储和转发两次访问，那么总的转发吞吐量必然少于内存最高读取速率的一半。速度受内存带宽限制。需要CPU参与每一个分组的处理，无法满足高吞吐量的要求。
• 经总线交换。通过共享的高速总线连接输入端口和输出端口。输入端口将分组加上目标输出端口的标记，传输到总线，输出端口根据标记接收分组。
  • 分组从输入端口打上标记后传输到总线。
  • 总线广播分组到所有端口，只有目标端口接收分组。
  • 分组从总线传递到输出端口。
  • 相比内存交换，数据不需要存储在中央内存中，总线传输较快。总线带宽是瓶颈。对于小型企业网、局域网，这是足够的。
• 经互联网络交换。输入端口和输出端口通过交叉互连网络或复杂的交换结构连接，分组从输入端口直接传输到目标输出端口，无需通过单一总线或内存。
  • 输入端口根据分组头部信息将其送入互联网络。
  • 互联网络中的交叉点控制器根据分组的目的输出端口，动态调整连接路径。
  • 分组直接到达目标输出端口。
  • 高吞吐量，支持多个分组同时传输。解决了内存和总线的瓶颈问题。适用于大型路由器或高性能交换机。

4.2.3 输出端口处理

分组从交换结构中的输出端口出来后，需要经过：

• 排队（缓存管理）
• 数据链路处理
• 线路端接

4.2.4 何处出现排队

• 在输入时
  • 当分组到达输入端口时，如果该端口当前正在处理其他分组，新的分组必须进入一个队列（输入队列）。
  • 如果多个输入端口的分组同时需要通过交换结构进入同一个输出端口，可能会产生端口阻塞，导致排队。
    • 队列首部(Head-Of-the-Line, HOL)阻塞，即在一个输人队列中排队的分组必须等待通过交换结构发送(即使输出端口是空闲的)，因为它被位于队列首部的另一个分组所阻塞。
  • 缓存可能会溢出（即输出队列存储空间不足），导致丢包。
• 在输出时
  • 当没有足够的内存来缓存一个入分组时，就必须做出决定。要么DROP：丢弃到达的分组[采用一种称为弃尾(drop-tail)的策略]，要么MARKING：删除一个或多个已排队的分组为新来的分组腾出空间。

多少缓存才够用？

$$Buffering = \frac{RTT * C}{\sqrt{N}}$$

其中RTT是往返时延，C是链路容量，那么$RTT * C$代表了链路的带宽时延积，代表网络中总共可以容纳的比特数（也即正在传输的比特数）。

现在的研究要求除以根号N，N代表例如TCP流的数量。

我们很容易这样想:更多的缓存必定更好，因为更大的缓冲区将使路由器有能力承受分组到达率的更大波动，从而降低路由器的分组丢失率。但是更大的缓冲区也意味着潜在的更长的排队时延。

4.2.5 分组调度

讨论排队的分组如何经链路传输的问题。

• FCFS(FIFO):：DROP + 先进先出
• Priority Queuing：分为高优先级队列和低优先级队列，优先发送高优先级队列中的分组，分组内部使用FIFO。
• Round Robin（循环排队规则）：为每个流分配一个权重。权重值越大，流的优先级越高，能够获得的带宽越多。根据流的权重，分配比例化的服务时间。高权重流在循环中被选中的频率更高。能够近似实现“比率公平性”（Proportional Fairness），即流的服务带宽与其权重成比例。

4.3 网际协议：IPV4、寻址、IPV6及其他

主机与物理链路之间的边界叫做接口。路由器与它的任意一条链路之间的边界也叫做接口。而IP要求每台主机和路由器接口拥有自己的IP地址。因此，从技术上讲，一个IP地址与一个接口相关联，而不是与包括该接口的主机或路由器相关联。

在全球因特网中，每台主机和路由器上的每个接口都必须有一个全球唯一的P地址(NAT后面的接口除外)。然而，这些地址不能随意地自由选择。一个接口的IP地址的一部分需要由其连接的子网来决定。互联的若干个主机接口与一个路由器接口的网络形成一个子网，例如主机接口223.1.1.1, 223.1.1.2, 223.1.1.3与路由器接口223.1.1.4，前三者可能由一个以太网LAN互联。IP编址为这个子网分配一个地址223.1.1.0/24，其中的/24称为子网掩码，指示最左侧的24比特定义了子网地址。

地址聚合：

可以任意地选取前缀长度，称为无类别域间路由选择（CIDR），在这之前只能按照/8，/16和/24分类。另外，当发出255.255.255.255时，代表分发给同一个网络中的所有主机。

如何获取一块IP地址？

• 通过网络管理员和ISP（网络服务提供商）联系。
• 动态分配（DHCP）
  • 主机发送DHCP Discover广播包，寻找DHCP服务器。
  • DHCP服务器回复DHCP Offer，提供一个可用IP地址。
  • 主机确认接受地址（DHCP Request）。
  • DHCP服务器发送DHCP Acknowledge，完成分配。
  • 无需人工干预，支持设备即插即用。
  • 分配的地址可能会变化，不适合需要固定IP的设备。

Hierarchical Addressing（分层地址）和Route Aggregation（路由聚合）
分层地址通过将IP地址分为不同层级（例如网络号、子网号和主机号），实现更高效的地址分配和管理。
路由聚合也称为路由汇总，指将多个具体的路由条目合并为一条更大的路由条目，减少路由表中的记录数量。

4.3.3 NAT 网络地址转换

NAT（Network Address Translation）

NAT允许多台设备通过共享一个或多个公共 IP 地址访问外部网络（如互联网）。它是在路由器或防火墙上执行的，用于转换本地网络中私有 IP 地址和公共网络中可路由 IP 地址之间的映射。

• IP地址节省
  • 在IPv4地址资源有限的情况下，NAT允许大量设备通过少量的公共IP访问互联网。
  • 局域网设备使用私有IP地址（例如：192.168.x.x、10.x.x.x），这些地址在互联网中不可路由，通过NAT转换为公共IP与外部通信。
• 隐藏局域网拓扑
  • NAT隐藏了内部网络的真实结构，外部设备只能看到路由器的公共IP地址。
  • 提升了网络的安全性，防止直接访问内部设备。
• 网络灵活性
  • 内网设备可以自由更改私有IP地址，而不会影响到公共IP的使用。

当一台局域网设备发送数据包到外部网络，NAT设备（如路由器）将其私有IP地址替换为路由器的公共IP地址。路由器在内部维护一个映射表，记录每个连接的私有IP和端口号，以便返回时找到对应设备。
外部设备向公共IP地址发送数据包时，NAT设备根据映射表将数据包转换并转发到正确的私有IP和端口。

4.3.4 IPV6

• 扩大了地址容量
• 简化头部
• 新增流标签

但是如何迁移？

• 升级限制：
  • 并非所有路由器都能同时升级。
  • 没有“标志日”（flag days），即没有一个特定的日子来统一进行升级。
• 混合环境下的网络运行：
  • 如何在网络中同时使用IPv4和IPv6路由器？
• 隧道技术：
  • 隧道技术是指将IPv6数据报作为负载封装在IPv4数据报中，在IPv4路由器之间传输。
  • 这种方法类似于“包内包”的概念。
  • 隧道技术在其他上下文中也广泛使用，例如4G/5G网络。

4.4 泛化转发和SDN

泛化转发（Generalized Forwarding）是一种网络数据转发方式，与传统基于目的地址的路由和转发不同，它基于灵活、通用的匹配规则对数据包进行处理和转发。通常用于高级网络架构如SDN（软件定义网络），它支持多种协议和复杂的流量管理需求。泛化转发允许现代路由器更加智能地转发分组。

匹配 + 操作转发 Match + Action
网络设备根据数据包的特定字段（Match，匹配）选择需要执行的操作（Action，动作），从而决定如何处理数据包。

Match 阶段是通过检查数据包头中的多个字段，确定是否满足预定义的规则。可以匹配的字段包括：

• 二层：MAC 地址、VLAN ID
• 三层：IP 地址（源或目的）
• 四层：TCP/UDP 端口号
• 其他字段：如协议类型、标签、流 ID 等

匹配字段可以是：

• 完全匹配：字段值完全相同。
• 掩码匹配：如最长前缀匹配（CIDR）。
• 通配符匹配：可以匹配所有可能的值。

Action 指对满足匹配条件的数据包执行的具体操作。这些操作可以是：

• 转发：将数据包转发到指定的输出端口。
• 丢弃：直接丢弃数据包。
• 修改：更改数据包内容，如修改源或目的地址。
• 复制：将数据包复制到多个端口。
• 计数：记录数据包匹配规则的统计信息（如数量、字节数）。
• 转发到控制器：将数据包发送到 SDN 控制器作进一步处理。

OpenFlow中的Match + Action
在 OpenFlow 协议中，Match+Action 是通过流表（Flow Table）实现的：

• 流表结构：
  • 每条流表项包含：匹配字段、优先级、计数器、超时和动作列表。
  • 数据包进入交换机后，会逐条与流表项进行匹配。
• 操作步骤：
  • 数据包进入交换机后，首先匹配流表项（匹配字段包括二层到四层的多个字段）。
  • 如果找到匹配项，则执行该流表项定义的动作（例如转发到指定端口）。
  • 如果没有找到匹配项，数据包可能被发送到 SDN 控制器或直接丢弃。
• 优先级与多表支持：
  • 流表项之间有优先级机制，优先匹配高优先级规则。
  • OpenFlow 也支持多级流表，允许数据包按规则链路顺序逐步处理。

5. 网络层：控制平面

5.1 概述

控制平面决定“去哪里”，是网络的大脑；
而数据平面负责“怎么去”，是网络的执行者。
控制平面负责管理和决定如何将数据包从源地址转发到目的地址。它定义了路由策略并生成路由表。数据平面负责实际的数据转发，将数据包从输入接口转发到输出接口。

• 每路由器控制（Per-Router Control）
  • 每个路由器独立地进行路由决策。它们根据自身配置的算法或协议，使用本地信息来决定数据包的转发路径
• 逻辑集中式控制（Logically Centralized Control）
  • 逻辑集中式控制由一个中心控制器（如 SDN 的控制平面）来计算和管理整个网络的路由决策。路由器只负责接收控制器的指令，执行数据转发。

5.2 路由选择算法

路由选择算法的目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径。通常指的是最低开销的路径。

• 集中式路由选择算法（Centralized Routing Algorithm）：路径的选择由一个具有网络全局视图的中央控制节点计算完成，其他网络设备从控制节点获取转发规则。
  • 控制节点拥有整个网络的拓扑结构（包括链路状态、带宽等），并基于此计算最优路径。
  • 优化能力强，易于管理，一致性高
  • 单点故障风险，扩展性差，实时性较低
  • 使用：链路状态路由选择算法（LS），Dijkstra算法，每次更新最近距离，将距离最近的点合并到已经处理完的集合当中。
• 分散式路由选择算法（Decentralized Routing Algorithm）：路由选择由网络中的每个节点独立计算完成，它们依赖局部信息和邻居节点的通信来更新路由。
  • 每个节点仅知道自己与直接邻居的连接状态，并通过通信交换信息更新路由。
  • 容错性高，扩展性强，动态适应，单个节点故障不会影响整个网络，能够快速
  • 收敛速度慢，信息有限，复杂性高，路由更新需要时间，可能出现短暂的不一致性（如路由环）。
  • 使用：距离向量路由选择算法（DV），福特-贝尔曼算法，每个节点根据其邻居的信息计算到网络中所有其他节点的最短路径。节点定期将自己的路由表发送给所有邻居。邻居接收到后，使用这些信息更新自己的路由表。

在DV中节点依赖于邻居的信息来更新自己的路由表。如果网络拓扑发生变化（如某条路径失效），节点可能通过错误的信息更新自己的路由，从而形成路由环路。例如：A→B→C→A 形成的环路。
当某条路径失效时，节点可能逐步增加到目标节点的距离（成本），直到达到预设的“无穷”值。这一问题会导致网络收敛变慢。例如：路由表更新的成本从 3→4→5→⋯ 缓慢增长。

毒性逆转是一种简单的策略：如果一个节点通过某个邻居 N 到达目标节D，它就会告诉邻居 N 该目标 D 的距离为无穷大。
正常情况下：节点与邻居交换路由信息，更新最优路径。
路径断开时：如果节点发现通过邻居N 到目标节点 D 的路径失效，它会告诉邻居 N，目标 D 的距离是无穷大。
效果：邻居 N 会忽略通过节点的这条路径，从而防止环路或错误更新

其可以防止两个路由之间的环路，但是对于三个或更多的路由之间便不行。无法完全解决无穷计数问题。

5.3 因特网中自治系统内部的路由选择：OSPF

OSPF（Open Shortest Path First）是一种链路状态路由协议，用于 IP 网络中动态选择路由，是开放标准协议。使用链路状态算法（LS），每个路由器拥有整个网络的拓扑结构。

我们迄今为止对路由协议的研究是理想化的，具体表现为：

• 假设所有路由器都是相同的。
• 假设网络是“扁平”的，即没有层次结构。

然而，这些假设在实际应用中并不成立：

• 存储所有目的地的信息在路由表中是不可能的。
• 路由表的交换会淹没网络链路。

互联网是一个网络的集合，每个网络可能希望控制其内部的路由。为了解决这一问题，将路由器聚合成称为“自治系统”（Autonomous Systems, AS）的区域。

各个 Intra-AS（自治系统内部） 路由协议的特点：

• 路由信息协议RIP: Routing Information Protocol
  • DV机制：每 30 秒，路由器之间会定期交换距离向量表（包括目标网络和跳数）。
  • RIP由于效率和扩展性问题，现在已经不再广泛使用，仅在一些简单的网络中还存在。
• 增强型内部网关路由协议EIGRP: Enhanced Interior Gateway Routing Protocol
  • 基于DV算法
  • 尽管已经开放，但由于其历史上的 Cisco 专属特性，多数非 Cisco 网络未广泛采用。
• 开放式最短路径优先OSPF: Open Shortest Path First
  • 使用LS算法
  • 中间系统到中间系统协议 IS-IS: Intermediate System to Intermediate System 基于链路状态，与 OSPF 功能类似。

5.4 ISP之间的路由选择：BGP

在OSPF之后，需要一个自治系统间路由选择协议，在AS通信时运行相同的AS间路由选择协议。在因特网中，所有的AS运行相同的AS间路由选择协议，称为边界网关协议（BGP）。

BGP是一种自治系统（AS）之间使用的路径矢量路由协议，主要用于互联网的路由选择，为数据包找到最佳路径。在BGP中，分组并不是路由到一个特定的目的地址，而是路由到CIDR化的前缀，其中每个前缀表示一个子网或一个子网的集合。作为一种AS间的路由选择协议，BGP为每台路由器提供了一种完成以下任务的手段：

• 从邻居AS获得前缀的可达性信息。BGP允许每个子网向因特网的剩余部分通告它的存在。
• 确定到该前缀的“最好的”路由。对于某台路由器，其将在本地运行一个BGP路由选择过程，使用它经过相邻的路由器获得的前缀可达性信息。

对于每个AS，每台路由器要么时一台网关路由器（位于AS边缘，直连到其他AS），要么是一台内部路由器。

考虑向所有路由器通告前缀x的可达性信息。AS3向AS2发送一个BGP报文“AS3 x”，表示在AS3中；AS2向AS1发送一个BGP报文“AS2 AS3 x”，表示路径。

实际上这并不准确。在BGP中，每对路由器通过使用179端口的半永久TCP丽娜姐交换路由选择信息。每条直接连接以及所有通过该连接发送的BCP报文，称为BGP连接(BGPconnection)。此外，跨越两个AS的BCP连接称为外部BGP(eBGP)连接，而在相同AS中的两台路由器之间的BGP会话称为内部BGP(iBGP)连接。

• 3a -> 2c eBGP: “AS3 x”
• 2c -> all in AS2 iBGP: “AS3 x”
• 2a -> 1c eBGP: “AS2 AS3 x”
• 1c -> all in AS1: “AS2 AS3 x”

在拥有多条路径时（例如拥有1d -> 3d），那么接下来需要确定最好的路由。

5.4.3 确定最好的路由

BGP 通过 TCP 连接 在 BGP 邻居（Peers）之间交换消息，用于建立路由表和维护连接。当路由器通过 BGP 连接通告前缀时，它在前缀中包括一些 BGP 属性（BGP attribute）。用 BGP 术语来说，前缀及其属性称为路由（route）。

两个较为重要的属性是 AS-PATH 和 NEXT-HOP。

• AS-PATH：属性包含通告已经通过的 AS 的列表，例如“AS2 AS3”，和 “AS3”。

• NEXT-HOP：属性指定下一跳地址。

• OPEN 消息：用于建立 BGP 会话，并完成初始化和认证。

• UPDATE 消息：传递路由更新信息，通告新路径或撤销旧路径。
• KEEPALIVE 消息：用于维持 BGP 会话的活跃状态，确认对方仍然在线。
• NOTIFICATION 消息：用于报告错误，并可选择关闭 BGP 会话。

热土豆路由选择（Hot Potato Routing）

目标是将流量尽快从当前网络移交给其他网络，仅仅是选择距离其最近延迟的路由器（这我会，手捧雷嘛）。例如在1a中，如果1a收到来自1b的”AS2 AS3 x”和来自1d的”AS3 x”，那么如果1b的延迟更低，尽管其跳数更多，也会选择1b。

路由选择算法

1. 本地偏好
2. 选择最短AS-PATH的路由
3. 热土豆路由选择
4. BGP标识符

6. 链路层和局域网

6.1 链路层概述

任一链路层的基本服务都是将数据报通过单一通信链路从一个节点移动到相邻节点。所提供的服务细节随链路层协议的不同而变化。

• 成帧：使用链路层帧进行封装。几乎所有的协议都用到。
• 链路接入：介质访问控制协议（MAC）
• 相邻节点之间的可靠传输
• 流控制
• 错误检测
• 错误修正

以太网功能要么集成到主板芯片组，要么在专用以太芯片。接入总线。

6.2 差错检测和纠正技术

对于数据D，一并发送差错检测和纠正比特（Error-Detection and-Correction EDC）来增强数据。

奇偶校验
在受保护的一帧未检测出差错的概率能够达到50%。对于奇偶校验方案的二维一般化方案，对每行和每列计算奇偶值。产生的i(行) + j(列) + 1个比特作为EDC。二维奇偶校验能够检测一个分组中两个比特差错的任何组合，但不一定能纠正。

因特网检验和
将数据分为多个固定长度的段，将所有段用一’补码加法（最高位溢出加到结果的最低位）相加，进行检验。

循环冗余检测（CRC）
预定义G(x)作为生成多项式，在原始数据后附加一段全零的比特序列，其长度与生成多项式的阶相同。作模2除法，仅按位XOR，不进位，余数为CRC校验码。

6.3 多路访问链路和协议

有两种类型的网络链路：点对点链路和广播链路。

• 点对点：单个发送方，单个接受方
• 广播：多个发送和接收节点都连接到相同的广播信道上，当任意节点传播一个帧时，所有的节点都会收到一份副本。

多路访问协议
如果多个节点同时发送数据，那么传输的帧将在所有的接收方处碰撞，没有一个接收节点能够有效地获取任何传输的帧。因此产生多路选择协议，应该具有以下特性：

• 仅有一个节点发送数据时，享有全部的吞吐量
• 多个节点发送数据时，每个节点拥有平均的吞吐量
• 去中心化的，不会因某主节点故障而使整个系统崩溃
• 简单的，实现不昂贵

目前而言划分为三种类型：信道划分协议，随机接入协议，轮流协议

6.3.1 信道划分协议

将网络的共享通信信道划分为多个独立的部分，分配给不同用户。

• 频分多路复用（Frequency Division Multiplexing, FDM）：
  • 将信道划分为多个频率范围，每个频段平均分配R带宽，每个用户占用一个固定频率。
  • 过于公平，节点被限制于 R/N 平均速率，即使只有它一个节点在传输。N为频段总数。
• 时分多路复用（Time Division Multiplexing, TDM）：
  • 将信道按时间划分为多个时隙，每个用户分配特定的时隙。
  • 同样过于公平，节点被限制于 R/N 平均速率，即使只有它一个节点在传输。N为节点总数。
• 码分多路复用（Code Division Multiplexing, CDM）：
  • 每个用户分配唯一的编码（伪随机码），在相同时间和频率上传输。
  • 在精心选择编码后，所有的节点能够同时传输。抗干扰。

6.3.2 随机接入协议

随机接入协议允许节点在不预先协调的情况下访问共享信道。

• ALOHA 协议：
  • 纯 ALOHA：
    • 节点在任hec意时间发送数据。
    • 如果发生冲突，等待一个帧传输时间，然后以概率p立即重传，或者以概率1-p在另一个帧重传。
    • 效率低：理论上信道利用率为 $\frac{1}{2e}$。
  • 时隙 ALOHA：
    • 将时间划分为离散时隙，节点仅在时隙开始时发送数据。
    • 效率提升：理论上信道利用率为两倍的纯ALOHA。
• CSMA（载波侦听多路访问，Carrier Sense Multiple Access）：
  • 载波侦听：在传输前侦听信道是否空闲，若忙碌，则等待直到检测到一小段时间没有传输，才开始传输。
  • 因此，端到端的信道传播时延在决定其性能方面起了关键作用。
• CSMA 的增强协议：
  • CSMA with Collision Detection (CSMA/CD)：
    • 碰撞检测：如果在传输时检测到另一个节点正在传输，那么停止传输，发送阻塞信号。等待一段随机时间。
    • 等待的随机时间：二进制后退算法。在经历了一连串的n次碰撞后，节点随机地从${0, 1, …, 2^{n-1}}$中随机选择一个K值等待。
    • 令$d_{prop}$表示信号能量在任意两个适配器之前传播所需的最大时间。令$d_{trans}$表示传输一个最大长度的以太网帧的时间。效率式近似为：

$$Efficiency = \frac{1}{1 + 5 d_{prop} / d_{trans} }$$

6.3.3 轮流协议

轮流协议通过有序轮流方式分配信道，确保各节点公平访问信道。

• 轮询协议（Polling Protocol）：
  • 一个集中控制的主节点轮询各从节点，依次授予发送权限，每个节点仅在获得轮询信号时发送数据。
  • 引入了轮询时延。另外，如果主节点出现故障，那么整个系统崩溃。
• 令牌传递协议（Token Passing Protocol）：
  • 没有主节点，一个逻辑令牌在节点之间按照固定的次序传递，持有令牌的节点有权发送数据。当没有数据要发送时，立刻将该令牌传递给下一个节点。
  • 令牌丢失时需重新生成。

6.3.4 DOCSIS

在有线接入网络中，使用了 FDM（频分多路复用）、TDM（时分多路复用） 和 随机接入协议（Random Access Protocols） 的组合，以高效地支持上下行通信需求。
下行（从 CMTS 到用户）通信采用 频分多路复用（FDM）。上行通信（从用户到 CMTS）采用了一种混合方式，结合了 随机接入协议 和 时分多路复用（TDM）。

6.4 交换局域网

6.4.1 链路层寻址和ARP

链路层地址（MAC地址）长度6字节，每个字节为一对十六进制数。MAC地址被设计为永久的，在硬件制造时由制造商分配，并作为设备的唯一标识符，通常与网络接口卡（NIC）绑定。

特殊的MAC广播地址：FF-FF-FF-FF-FF-FF

地址解析协议ARP
当主机或路由器需要向局域网中的另一设备发送数据时，首先需要知道目标设备的 MAC 地址。如果只有目标设备的 IP 地址，ARP 负责查询并获得相应的 MAC 地址。

• ARP 请求（ARP Request）：
  • 主机 A 在局域网内广播一条 ARP 请求，内容为：“谁是 192.168.1.3？请告诉我。”
  • 广播的目标 MAC 地址为 FF:FF:FF:FF:FF:FF，表示所有设备都能接收到。
• ARP 回复（ARP Reply）：
  • 主机 B 接收到请求后，发现自己的 IP 地址匹配请求。
  • 主机 B 发送一个单播 ARP 回复，内容为：
  • “192.168.1.3 的 MAC 地址是 BB:BB:BB:BB:BB:BB。”
  • 主机 A 接收到回复后，将 IP 地址和对应的 MAC 地址存入其 ARP 缓存。
• 数据通信：
  • 主机 A 根据 ARP 获取的 MAC 地址，将数据帧发送到主机 B。

为减少频繁的 ARP 查询，主机会将最近获取的 IP-MAC 映射存入 ARP 缓存。ARP 缓存中的条目有 生存时间（TTL），过期后会被清除。、

发送数据报到子网以外

主机发送ARP请求，寻找路由器接口IP地址对应的适配器的MAC地址。随后创建一个数据报，包含到对应IP地址的寻址请求，然后把数据报发到自己所在的子网中。如此便会传递给路由器，随后由路由器转发出去。

6.4.2 以太网

以太网帧结构

前同步码 | 目的地址 | 源地址 | 类型 | 数据 | CRC

• 数据：最少46字节，最多1500字节
  • 这和512比特时间的最小帧长度没有矛盾。因为还要算上前14字节和后4字节的帧头帧尾，刚好匹配512比特（64字节）。
• 目的地址：6字节，包含目的适配器的MAC地址。
• 源地址：6字节，包含传输该帧到局域网上的适配器的MAC地址。
• 类型字段：2字节，允许以太网复用多种网络层协议，能偶使用除IP以外的其他网络层协议。
• CRC：4字节，循环检测冗余。
• 前同步码：8字节，这部分不算是帧的正式内容。用于同步接收方时钟。

所有的以太网技术都向网络层提供：

• 无连接服务，类似于数据报服务和UDP的无连接服务
• 不可靠服务，当帧通过CRC校验时不发送确认帧，不通过时也不发送否定确认帧。

6.4.3 链路层交换机

交换机在以太网网络中传输数据时对连接的设备和网络协议的工作方式是“隐形”的，不会对数据帧进行修改或干预。

过滤和转发：
当收到一份帧时，索引其转发表：

• 表中没有对应表项，则广播
• 有表项与收到该帧的接口相关联，则丢弃
• 有不与收到该帧的接口相关联的表项，则转发

自学习：
对于收到的每个入帧，自动地维护其表项，记录。如果在一段时间之后某个表项都没有用到，则清除。这使其能够称为即插即用设备。

6.4.4 虚拟局域网

在同一个物理局域网（LAN）中将设备分成多个逻辑子网。VLAN 可以让处于不同物理位置的设备通过逻辑上的分组方式像在同一个局域网中工作。

实现逻辑隔离，使不同 VLAN 的设备无法直接通信，就像在物理上分离的网络中一样。另外通过减少广播域的大小，降低广播流量对网络性能的影响。

VLAN干线连接
每台交换机上的一个特殊接口被配置为干线接口，以互联这两台VLAN交换机，以拓展互联VLAN，使多个 VLAN 的数据可以在交换机之间流动。干线连接中使用 VLAN 标签（如802.1Q）标记数据帧。

802.1Q
在以太网帧头部（目标地址-源地址-TAG-TYPE）插入一个 4 字节的 VLAN 标签。

• 2字节标识为802.1Q帧
• 3位流量控制
• 1位是否可丢弃
• 12位支持4096个VLAN，0和4095保留。

6.5 链路虚拟化：网络作为链路层

多协议标签交换（MPLS）
为数据包分配简短的标签，减少了传统路由中基于 IP 查找的复杂性，加速了数据包的转发过程。

在网络层和传输层之间工作，加入MPLS首部，带有标签、实验、S、TTL四个字段。立刻的，由MPLS加强的帧只能在两个均有MPLS使能的路由器之间发送。有MPLS使能的路由器称为标签交换路由器。

注意是路由器R1主动向R2和R3通告可达A的消息，具有MPLS标签6的接收帧将要转发到目的地A。如此完成了带有、不带有MPLS路由器之间的相互协调。

6.7 回顾：Web页面请求的历程

现在你启动了笔记本，希望得到www.google.com页面。

整体路线：初始化IP，得到网关MAC，得到谷歌IP，TCP

1. DHCP请求报文：连接到网络时，此时这台机子还没有一个IP地址，因此需要得到一个。将该报文段放入UDP报文段，报文目的端口为DHCP服务器，源端口为客户。
   UDP报文段放入IP数据报中，目的地址为广播，IP源地址为0.0.0.0。
   IP数据报放入以太网帧中，目的地址为广播，源MAC地址为笔记本MAC地址。
   将该以太网帧发送到以太网交换机。交换机广播该帧。
   路由器在对应的MAC地址接收到了这个帧。抽取出IP数据报，分析广播得知这不是针对自己的特定通信，而是一个需要传递给更高层协议的信息，可能是为了进一步分发到网络上的所有主机，或者是为了执行某些本地处理（如DHCP服务器响应客户端请求）。因此IP数据报继续被分解，得到UDP报文段，得知这是一个DHCP请求。
   如果路由器是DHCP中继代理，那么会转发给DHCP服务器。如果路由器是DHCP服务器，那么会响应该DHCP请求。数据内容为：分配的IP地址，DNS服务器的IP地址，默认网关路由器的IP地址，子网块。生成一个如此的DHCP ACK报文发送回，目标MAC是笔记本的MAC地址。
   交换机收到该帧。由于是自学习的，因此转发给笔记本。
   笔记本收到该帧，得知IP，DNS，网关，子网块。初始化完成。
2. ARP查询：Web浏览器需要生成一个TCP套接字，向谷歌网址发送HTTP请求。为了生成，需要知道网址的IP地址，这需要DNS服务。
   生成一个包含DNS请求报文的数据报、以太网帧，打算发送给网关路由器。但是仍然不知道网关路由器的MAC。这需要ARP协议。
   ARP查询报文的IP和源MAC已设置好，目的MAC为广播。
   网关路由器在收到后发送ARP回复。笔记本收到。
3. DNS查询：向网关服务器发送DNS查询，目标MAC为网关MAC。
   网关服务器收到，根据转发表发送到Comcast网络中最左侧的服务器。
   对应服务器收到，根据转发表确定出口，向DNS转发数据报。而转发表已根据域内协议（如RIP，OSPF）以及因特网域间协议BGP填写。
   DNS服务器收到，抽取出DNS查询，查找谷歌网址。如果没找到，则向根服务器发送查询。
   总之是得到了，然后生成DNS回答报文，放入UDP报文段中，原路返回。
   笔记本收到。
4. TCP协议：同谷歌三次握手，建立TCP套接字。
   生成HTTP GET报文，写入套接字，报文段交给IP数据报，发送给谷歌。
   谷歌抽取出报文，生成HTTP响应，发送进TCP套接字中。
   计算机收到。终于显示了网页。