计算机网络复习笔记

发表于 更新于 分类于 阅读次数：

计算机网络与因特网

一个协议定义了在两个或多个通信实体之间交换报文的格式与次序，以及报文发送/接收或其他事件所采取的动作。

协议层次及其服务模型

因特网协议栈（Internet protocol stack）自顶向下：

  1. 应用层：网络应用程序及应用层协议存留的地方。
  • 常见应用层协议：HTTP、DNS、FTP、SMTP、DHCP
  • 位于应用层的分组信息称为报文（message）
  1. 运输层：负责在应用程序端点之间传送应用层报文。
  • 常见运输层协议：TCP、UDP
  • 位于应用层的分组信息称为报文段（segment）
  1. 网络层：负责在主机间传送网络层的分组。
  • 常见网络层协议：IP
  • 位于网络层的分组信息称为数据报（datagram）
  1. 链路层：负责将整个帧从一个网络元素移动到临近的网络元素。
  • 链路层的例子包括以太网，WiFi
  • 由于分组从源到目的地传送通常要经过几条链路，所以可能被途径不同的链路层协议处理
  • 位于链路层的分组信息称为帧（frame）
  1. 物理层：将帧中的每个比特从一个结点移动到下一结点。
  • 与链路的实际传输媒介相关。

ISO-OSI 模型：

  1. 应用层
  2. 表示层：使通信的应用协议能够解释交换数据的含义，提供数据压缩、数据解密、数据描述等服务；
  3. 会话层：提供数据交换的定界和同步功能，包括建立检查点和恢复方案的方法；
  4. 运输层
  5. 网络层
  6. 链路层
  7. 物理层

网络边缘

几种因特网的接入方式：

  • 家庭接入：DSL（数字用户线，Digital Subscriber）、电缆、FTTH（光纤到户，Fiber To The Home）、拨号和卫星
  • 企业（和家庭）接入：以太网和 WiFi
  • 广域无线接入：3G 和 LTE

网络核心

网络核心：由连接因特网端系统的分组交换机和链路构成的网络。

通过网络链路和交换机移动数据的两种基本方法：

  1. 分组交换（packet switching）
  2. 电路交换（circuit switching）

分组交换

将长报文分成较小的数据块（称为分组），在源和目的地之间，每个分组都通过通信链路和分组交换机（packet switch）传送。

分组交换机主要有两类：

  • 路由器（router）：常用于网络核心中，网络中大于几千台主机时使用
    • 使用网络层地址转发分组，是第三层的分组交换机；
    • 优点：分组不会通过路由器循环；防火墙保护
    • 缺点：不是即插即用的；对每个分组处理时间更长
  • 链路层交换机（link-layer switch）：常用于接入网中，网络中小于几百台主机时使用
    • 使用 MAC 地址转发分组，是第二层的分组交换机；
    • 优点：即插即用；相对高的分组过滤和转发速率
    • 缺点：大型交换网络生成可观的 ARP 流量和处理量；对广播风暴不提供任何保护措施

存储转发传输（store-and-forward transmission）：两种分组交换机能够开始向输出链路传输该分组的第一个比特之前，都必须接收到整个分组。因此存在一定的存储转发时延。设分组为 L 比特，链路传输速率为 R 比特/秒，则每条链路的存储转发时延为 L/R 秒。

电路交换

每台主机都与一台交换机直连，当两台主机通信时，该网络在两台主机之间创建一条专用的端到端连接（end-to-end connection，又称电路）。

端系统通信会话期间需要预留资源（缓存，链路传输速率）。端到端连接的实现方式包括频分复用和时分复用。

分组交换与电路交换的对比

  • 电路交换不考虑需求，而预先分配了传输链路的使用，使得已分配而并不需要的链路时间未被使用，对线路的利用率很低；
  • 分组交换按需分配链路使用。

趋势朝着分组交换方向发展。

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

结点总时延 = 处理时延 + 排队时延 + 传输时延 + 传播时延

  • 节点处理时延（nodal processing delay）：检查分组首部和决定该分组导向何处所需时间（可能包括检查比特级差错）；
  • 排队时延（queuing delay）：分组在队列中等待传输的时间；
  • 传输时延（transmission delay）：路由器将分组推出所需时间；
  • 传播时延（propagation delay）：分组从一台路由器向另一台路由器传播所需时间。

  • 丢包（packet lost）：当排队队列满时，由于没有地方进行缓存，路由器将丢弃该分组。丢弃的分组可能重传，也可能不传。

  • 吞吐量（throughput）：

    • 瞬时吞吐量（instantaneous throughput）：主机接受文件的速率（bps）
    • 平均吞吐量（average throughput）：主机在某个时间区间接受文件的平均速率（bps）

应用层

非重点知识

因特网为应用程序提供了两个运输层协议：

  • TCP：面向连接、可靠数据传输、有拥塞控制机制；
  • UDP：不提供不必要服务、无连接、不可靠、没有拥塞控制机制。

套接字（Socket）：同一台主机内应用层与运输层之间的接口。也称为应用程序编程接口（API）。

往返时间（Round-Trip Time，RTT）：一个短分组从客户到服务器然后再返回客户所花费的时间。

HTTP

HTTP（超文本传输协议，HyperText Transfer Protocol）：

  • 定义了 Web 客户端向 Web 服务器请求 Web 页面的方式；
  • 使用 TCP 作为支撑运输层协议 => 连接建立后可以通过套接字访问
  • 无状态协议（stateless protocol）：不保存关于客户机的任何信息

HTTP 默认使用持久连接，但 HTTP 客户和服务器也能配置成使用非持久连接。

  • 非持久连接（non-persisitent connection）：当客户机/服务器交互运行于 TCP 协议上时，每个请求/响应对是经一个单独的 TCP 连接发送；
  • 持久连接（persistent connection）：当客户机/服务器交互运行于 TCP 协议上时，所有请求/响应对是经相同的 TCP 连接发送。

HTTP 1.0 vs HTTP 1.1

  • 请求方法的增加：HTTP 1.0 只有 GET、POST、HEAD 三个请求方法；HTTP 1.1 新增了 PUT、DELETE、OPTIONS、CONNECT、TRACE。
  • HTTP 1.0 使用非持久连接，需要为每一个请求的对象建立和维护一个连接，给 Web 服务器造成较大负担，且有额外时延；HTTP 1.1 使用持久连接，通过请求头中的“Connection: Keep-Alive”实现。
  • HTTP 1.1 还有一些性能改善措施，例如支持请求流水线，100（Continue）响应码，Host 请求头字段等。

HTTP 请求页面过程

  1. 有了 HTTP 服务器的 IP 地址之后，主机就能够生成 TCP 套接字，该套接字将用于向 Web 服务器发送 HTTP GET 报文。
  2. 在生成 TCP 套接字之前，必须先与 HTTP 服务器进行三次握手来建立连接。生成一个具有目的端口 80 的 TCP SYN 报文段，并向 HTTP 服务器发送该报文段。
  3. HTTP 服务器收到该报文段之后，生成 TCP SYN ACK 报文段，发回给主机。
  4. 连接建立之后，浏览器生成 HTTP GET 报文，并交付给 HTTP 服务器。
  5. HTTP 服务器从 TCP 套接字读取 HTTP GET 报文，生成一个 HTTP 响应报文，将 Web 页面内容放入报文主体中，发回给主机。
  6. 浏览器收到 HTTP 响应报文后，抽取出 Web 页面内容，之后进行渲染，显示 Web 页面。

cookie 技术的四个组件：

  1. 在 HTTP 响应报文中的一个 cookie 首部行；
  2. 在 HTTP 请求报文中的一个 cookie 首部行；
  3. 用户浏览器管理的 cookie 文件；
  4. 位于 Web 站点的一个后端数据库。

Web 缓存

Web 缓存器/代理服务器：代表初始 Web 服务器来满足 HTTP 请求的网络实体。

优点：

  • 减少对客户请求的响应时间；
  • 减少一个机构的接入链路到因特网的通信量。

条件 GET：

  • 目的：防止缓存器中的对象副本不是最新；
  • 判别方法：请求报文使用 GET 方法，且包含一个“If-Modified-Since:”首部行。

FTP

FTP（文件传输协议，File Transfer Protocol）：客户端通过 FTP 向一台远程主机上传文件或从远程主机下载文件。

FTP 和 HTTP 比较：

  • 相同点：都是文件传输协议，都运行在 TCP 上；
  • 不同点：
    1. FTP 是带外传送的（out-of-band），它使用两个并行 TCP 连接来传输文件，一个是控制连接（control connection），一个是数据连接（data connection）；HTTP 是带内的（in-band），在同一个连接中发送请求和响应首部行。
    2. FTP 服务器必须在整个会话间保存用户状态信息，而 HTTP 不保存客户机的任何信息。

DNS

DNS（域名系统，Domain Name System）：主要任务是负责将用户提供主机名解析为 IP 地址。其他提供的服务有：

  • 主机别名（host aliasing）；
  • 邮件服务器别名（mail server aliasing）；
  • 负载分配（load distribution）。

DNS 通常由其他应用层协议使用，包括 HTTP、SMTP 和 FTP。DNS 运行在 UDP 上，使用 53 号端口。

DNS 解释域名过程的简单描述：

  1. 应用程序调用 DNS 客户端，并指明需要被转换的主机名；
  2. 用户主机上的 DNS 向网络中发送一个 DNS 查询报文；
  3. 经过若干毫秒到若干秒的时延后，用户主机上的 DNS 接收到一个提供所希望映射的 DNS 报文，并传递到调用 DNS 的应用程序。

DNS 既是一个允许主机查询分布式数据库的应用层协议，也是一个由分层的 DNS 服务器实现的分布式数据库。DNS 的层次结构包含根 DNS 服务器，顶级域（TLD）DNS 服务器，权威 DNS 服务器。DNS 不适用于集中式设计的原因包括：

  1. 单点故障：如果 DNS 服务器崩溃，整个因特网随之瘫痪；
  2. 通信容量：整个 DNS 服务器不得不处理所有的 DNS 查询；
  3. 远距离的集中式数据库：距离 DNS 服务器远的主机的查询将产生严重的延迟；
  4. 维护：集中式的数据库非常庞大，难以维护。

SMTP

SMTP（简单邮件传输协议，Simple Mail Transfer Protocol）是因特网电子邮件应用的核心，用于从发送方的邮件服务器发送报文到接收方的邮件服务器。

SMTP 和 HTTP 比较：

  • 相同点：都用于从一台主机向另一台主机传送文件，都使用持续连接；
  • 不同点：
    1. SMTP 是一个推协议（push protocol），即发送邮件服务器把文件推向接收邮件服务器；而 HTTP 是一个拉协议（pull protocol）。
    2. SMTP 要求每个报文使用 7-bit ASCII 码格式，HTTP 数据则不受这种限制。
    3. 处理既有文本又有图像的文档时，SMTP 把所有报文对象放在一个报文之中，而 HTTP 把每个对象封装到独立的响应报文中。

DHCP

DHCP（动态主机配置协议，Dynamic Host Configuration Protocol）提供了即插即用的连网方式，用户不再需要去手动配置 IP 地址等信息。

DHCP 配置的内容不仅是 IP 地址，还包括子网掩码、默认路由器 IP 地址、域名服务器的 IP 地址。

工作方式如下：需要 IP 地址的主机广播发送 DHCP 发现报文（将目的地址置为全 1，即 255.255.255.255:67，源地址设置为全 0，即 0.0.0.0:68），DHCP 服务器收到发现报文之后，则在 IP 地址池中取一个地址，发送 DHCP 提供报文给该主机。

运输层

运输层协议：

  • 为运行在不同主机上的应用进程之间提供了逻辑通信；
  • 在端系统中实现（而非路由器）；
  • UDP 和 TCP 最基本的责任是，将两个端系统间 IP 的交付服务扩展为运行在端系统上的两个进程之间的交付服务。TCP 还附加提供可靠数据传输、拥塞控制等服务。

多路复用和多路分解

多路分解（demultiplexing）：将运输层报文段中的数据交付到正确的套接字的工作。

多路复用（multiplexing）：从源主机的不同套接字中收集数据块，并为每个数据块封装上首部信息从而生成报文段，然后将报文段传递到网络层的工作。

UDP 套接字：由包含目的 IP 地址和目的端口号的二元组标识。

TCP 套接字：由包含源 IP 地址、源端口号、目的 IP 地址、目的端口号的四元组标识。

对于两个具有相同目的 IP 地址和目的端口号，但具有不同源 IP 地址或源端口号的报文段，UDP 报文段将通过相同的目的套接字被定向到相同的目的进程；TCP 报文段将被定向到两个不同的套接字。

无连接运输：UDP

特点：

  • 尽力而为：报文段可能无序到达或丢失；
  • 无连接：发送报文段前没有握手。

选择使用 UDP 构建应用的原因：

  1. 应用层能更好地控制要发送的数据和发送时间（相对的，TCP 有一个拥塞控制机制）；
  2. 无需连接建立（不会引入建立连接的时延）；
  3. 无连接状态：不用维护连接状态或跟踪参数，可以支持更多活跃客户；
  4. 分组首部开销小：TCP 报文段有 20 字节的首部开销，而 UDP 只有 8 字节。

UDP 差错检测——检验和

UDP 检验和（checksum）提供差错检测功能，以检测报文段运输时的比特改变，但不提供差错恢复。

checksum.png

发送方：

  1. 对报文段中 3 个 16 比特字求和；
  2. 求和遇到的溢出被回卷（左边溢出的 1 加到最右边）；
  3. 对和进行反码运算，结果放在检验和字段。

接收方：全部的 4 个 16 比特字（包括检验和）加在一起，若没有差错，接收方处该和将是 1111 1111 1111 1111。

可靠数据传输

可靠数据传输的实现在运输层、链路层以及应用层。

可靠数据传输协议（reliable data transfer protocol）的演变思路：

为了解决发送方利用率极低的问题，停等操作 => 流水线操作（允许发送方发送多个分组而无需等待确认）。解决流水线操作的差错恢复的两种方法：回退 N 步（Go-Back-N，GBN）、选择性重传（Selective Repeat，SR）。

回退 N 步协议（GBN）

允许发送方发送多个分组，但流水线中未确认的分组数不能超过某个最大允许数 N。

GBN 协议也被称为滑动窗口协议（sliding-window protocol），N 被称为窗口长度。

GBN 发送方必须响应三种类型的事件：

  • 上层的调用
  • 收到一个 ACK：累计确认，表明正确接收到序号 n 及之前的分组
  • 超时事件：出现超时，发送方重传所有已发送但还未被确认过的分组

GBN 接收方：

  • 正确、按序接收到分组 n，则为其发送一个 ACK；否则丢弃该分组，并为最近按序接收的分组重新发送 ACK。
  • 丢弃所有失序分组。

优点：不需要缓存任何失序分组。

缺点：对该分组的重传也许会丢失或出错，甚至因此需要更多重传。

选择性重传协议（SR）

通过让发送方仅重传那些它怀疑在接收方出错（即丢失或受损）的分组，来避免不必要的重传。

SR 接收方：确认一个正确接收的分组而不管是否按序。失序的分组将被缓存，直到所有序号更小的分组都被收到为止，这时将一批分组按序交付给上层。

困境：序号范围有限时，接收方可能因窗口太大而无法分辨是一个新分组还是一次重传。 => 窗口大小须小于等于序号空间大小的一半。

面向连接的运输：TCP

TCP 连接

  • 全双工服务：TCP 连接是双向的
  • 最大报文段长度（MSS，Maximum Segment Size）：运输层概念，指 TCP 可从缓存中取出并放入报文段中的数据量，通常根据最初确定的由本地发送主机发送的最大链路层帧长度（即最大传输单元，MTU）来设置。
报文段结构

  • 序号：用于对字节流进行编号，例如序号为 301，表示第一个字节的编号为 301，如果携带的数据长度为 100 字节，那么下一个报文段的序号应为 401。
  • 确认号：期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段，序号为 501，携带的数据长度为 200 字节，因此 B 期望下一个报文段的序号为 701，B 发送给 A 的确认报文段中确认号就为 701。
  • 数据偏移：指的是数据部分距离报文段起始处的偏移量，实际上指的是首部的长度。
  • 确认 ACK：当 ACK=1 时确认号字段有效，否则无效。TCP 规定，在连接建立后所有传送的报文段都必须把 ACK 置 1。
  • 同步 SYN：在连接建立时用来同步序号。当 SYN=1，ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接，则响应报文中 SYN=1，ACK=1。
  • 终止 FIN：用来释放一个连接，当 FIN=1 时，表示此报文段的发送方的数据已发送完毕，并要求释放连接。
  • 窗口：窗口值作为接收方让发送方设置其发送窗口的依据。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。

可靠数据传输

TCP 在 IP 不可靠的尽力而为服务之上创建了一种可靠数据传输服务，确保一个进程从其接收缓存中读出的数据流是无损坏、无间隔、非冗余和按序的数据流。

TCP 发送方 3 个与发送和重传有关的主要事件：

  1. 从上层应用接收数据；
  2. 定时器超时；
  3. 收到 ACK 报文。

快速重传!：TCP 使用冗余 ACK（再次确认某个报文段的 ACK），而非否定确认。一旦收到 3 个冗余 ACK，TCP 就执行快速重传，即在该报文段的定时器过期之前重传丢失的报文段。

TCP 的差错恢复机制是 GBN 协议和 SR 协议的混合体。

流量控制（flow control）

TCP 流量控制的目的：消除接收方缓存溢出的可能性。

TCP 流量控制的实现：发送方维护一个称为接收窗口（receive window）的变量，通过发给发送方报文段的接收窗口字段，通知发送方该接收方还有多少可用的缓存空间。

TCP 连接管理

三次握手

假设 A 为客户端，B 为服务器端。

  • 首先 B 处于 LISTEN（监听）状态，等待客户的连接请求。
  • A 向 B 发送连接请求报文段，SYN=1，ACK=0，选择一个初始的序号 x。
  • B 收到连接请求报文段，如果同意建立连接，则向 A 发送连接确认报文段，SYN=1，ACK=1，确认号为 x+1，同时也选择一个初始的序号 y。
  • A 收到 B 的连接确认报文段后，还要向 B 发出确认，确认号为 y+1，序号为 x+1。
  • B 收到 A 的确认后，连接建立。

原因：第三次握手是为了防止失效的连接请求到达服务器，导致服务器错误打开连接。

四次挥手

  • A 发送连接释放报文段，FIN=1。
  • B 收到之后发出确认，此时 TCP 属于半关闭状态，B 能向 A 发送数据但是 A 不能向 B 发送数据。
  • 当 B 不再需要连接时，发送连接释放请求报文段，FIN=1。
  • A 收到后发出确认，进入 TIME-WAIT 状态，等待 2 MSL 时间后释放连接。
  • B 收到 A 的确认后释放连接。

原因：客户端发送了 FIN 连接释放报文之后，服务器收到了这个报文，就进入了 CLOSE-WAIT 状态。这个状态是为了让服务器端发送还未传送完毕的数据，传送完毕之后，服务器会发送 FIN 连接释放报文。

拥塞控制（congestion control）

TCP 拥塞控制的目的：消除路由器缓存溢出导致的丢包和重传，以及缓存队列造成的排队时延。

流量控制为了让接收方来得及接收，而拥塞控制是为了降低整个网络的拥塞程度。

拥塞控制方法

根据网络层是否为运输层拥塞控制提供了显式帮助，区分两种拥塞控制方法：

  • 端到端拥塞控制：没有显式支持，通过对网络行为观察来推断是否拥塞（TCP 采用）；
  • 网络辅助的拥塞控制：网络层构件（路由器）向发送方提供反馈信息。拥塞信息可以通过专门的阻塞分组或者分组中的字段从网络反馈到发送方。
TCP 拥塞控制

TCP 让每一个发送方根据所感知到的网络拥塞程度来限制其能向连接发送流量的速率。

问题：

  1. 如何限制发送流量速率？答：发送方维护变量拥塞窗口（cwnd），LastByteSent - LastByteAcked <= min{cwnd, rwnd}。通过调节 cwnd 的值，发送方能调整它向连接发送数据的速率；
  2. 如何感知拥塞？答：超时或收到 3 个冗余 ACK；
  3. 感知到拥塞时，采用何种算法去改变发送速率？答：(1) 一个丢包意味着拥塞，因此降低发送方速率；(2) 当对先前未确认报文段的确认到达时，能够增加发送方的速率；(3) 带宽探测：增加速率以响应到达的 ACK，除非出现丢包，此时才减小传输速率。

TCP 拥塞控制算法（TCP congestion control algorithm）包括三个主要部分：

  1. 慢启动（强制）；
  2. 拥塞避免（强制）；
  3. 快速恢复（推荐）；

网络层

网络层的作用是将在主机间传送分组，因此需要两种重要的网络层功能：

  • 转发（forwarding）：当一个分组到达路由器的一条输入链路时，路由器必须将该分组移动到适当的输出链路；
  • 路由选择（routing）：当分组从发送方流向接收方时，网络层必须决定这些分组所采用的路由或路径。

因特网的网络层提供尽力而为服务（best-effort service），有三个主要组件：

  • IP 协议
  • 路由选择协议
  • ICMP 协议（互联网控制报文协议）：用于主机和路由器沟通网络层的信息。最典型的用途是差错报告。

虚电路与数据报网络

  • 虚电路（Virtual-Circuit，VC）网络：仅在网络层提供连接服务的计算机网络。由路由器维持连接状态信息。
  • 数据报网络：仅在网络层提供无连接服务的计算机网络。每当一个端系统要发送分组，它就为该分组加上目的端系统的地址，然后将分组推进网络中。

路由器

  • 主要作用：将数据报从入链路转发到出链路；
  • 路由器具有截断的协议栈，即没有网络层以上的部分；
  • 每台路由器具有一张转发表（forwarding table），指示分组对应的输出端口；
  • 路由器的四个组成部分：输入端口 + 交换结构 + 输出端口 + 路由选择处理器；
  • 每个输入端口存放一份转发表副本的原因：转发决策能在每个输入端口本地做出，无须调用中央路由选择处理器，因此避免了集中式处理的瓶颈。

IPv4 vs IPv6

IPv4 数据报格式

  • 版本：有 4（IPv4）和 6（IPv6）两个值；
  • 首部长度：占 4 位，因此最大值为 15。值为 1 表示的是 1 个 32 位字的长度，也就是 4 字节。因为首部固定长度为 20 字节，因此该值最小为 5。如果可选字段的长度不是 4 字节的整数倍，就用尾部的填充部分来填充。
  • 区分服务：用来获得更好的服务，一般情况下不使用。
  • 总长度：包括首部长度和数据部分长度。
  • 标识：在数据报长度过长从而发生分片的情况下，相同数据报的不同分片具有相同的标识符。
  • 标志：发生分片时，最后一个片此位设为 0，其他所有片此位设为 1。
  • 片偏移：和标识符一起，用于发生分片的情况。片偏移的单位为 8 字节。

  • 生存时间：TTL，它的存在是为了防止无法交付的数据报在互联网中不断兜圈子。以路由器跳数为单位，当 TTL 为 0 时就丢弃数据报。
  • 协议：指出携带的数据应该上交给哪个协议进行处理，例如 ICMP、TCP、UDP 等。
  • 首部检验和：因为数据报每经过一个路由器，都要重新计算检验和，因此检验和不包含数据部分可以减少计算的工作量。
  • 源和目的 IP 地址。
  • 选项：允许 IP 首部被扩展。因为复杂，在 IPv6 首部已去掉。

IPv4 编址

接口（interface）：主机和物理链路之间的边界。一个 IP 地址技术上是与一个接口相关联的。

子网（subnet）：分开主机和路由器的每个接口，产生几个隔离的网络岛，这些子网使用接口连接。

IP 编址为子网分配一个地址：223.1.1.0/24，其中的 /24 记法称为子网掩码（network mask），指示了 32 比特中的最左侧 24 比特定义了子网地址。

因特网的地址分配策略是无类别域间路由选择（Classless Interdomain Routing, CIDR），使用网络前缀和主机号来对 IP 地址进行编码，网络前缀的长度可以根据需要变化。CIDR 的记法上采用在 IP 地址后面加上网络前缀长度的方法，例如 128.14.35.7/20 表示前 20 位为网络前缀。

动态主机配置协议（Dynamic Host Configuration Protocol, DHCP），又被称为即插即用协议（plug-and-play protocol）。利用 DHCP，主机可以自动获取 IP 地址。除了为主机分配地址外，DHCP 还允许一台主机获取其他信息，如它的子网掩码，默认网关，本地 DNS 服务器地址等。DHCP 协议的 4 个步骤：

  1. DHCP 服务器发现
  2. DHCP 服务器提供
  3. DHCP 请求
  4. DHCP ACK

IPv6

IPv6 引入的变化：

  • 扩大的地址容量：IP 地址长度从 32 比特增加到 128 比特；
  • 简化高效的 40 字节定长首部；
  • 流标签与优先级。

IPv6 中不包含的 IPv4 字段：

  • 分片/重新组装：IPv6 不允许在中间路由器上进行分片与重新组装，只能在源与目的地上执行；
  • 首部检验和：运输层和链路层协议已执行了检验操作；
  • 选项。

从 IPv4 到 IPv6 的迁移：

  • 双栈（dual-stack）：使用该方法的 IPv6 结点还具有完整的 IPv4 实现；
  • 建隧道（tunneling）：将两台 IPv6 路由器之间的中间 IPv4 路由器集合称为一个隧道。借助于隧道，在隧道发送端的 IPv6 结点可将整个 IPv6 数据报放到一个 IPv4 数据报的有效载荷字段中。

路由选择算法

  • 目的：给定一组路由器以及连接路由器的链路，找到一条源路由器到目的路由器的好路径。
  • 分类方式：
    • 全局式 vs 分散式：全局式要求以所有结点之间的连通性及所有链路费用为输入，而分散式中每个结点仅有与之相连链路的费用知识；
    • 静态 vs 动态：动态算法对网络变化有较大反应；
    • 负载敏感 vs 负载迟钝：负载敏感算法中链路费用动态变化以反映底层链路的当前拥塞水平。当今的因特网路由选择协议（RIP、OSPF 和 BGP）都是负载迟钝的。

链路状态路由选择算法（LS）

  • 迭代、全局式
  • 根据 Dijkstra 算法实现
  • 最差情况 O(n^2)，用堆可控制在 O(nlogn)
  • 可能的问题：振荡 => 解决方案：并非所有路由器都同时运行 LS 算法

距离向量路由选择算法（DV）

  • 迭代、异步、分布式
  • 根据 Bellman-Ford 方程实现
  • 对于结点 x：
    • 知道 x 到直接相连邻居 v 的费用
    • 保存每个邻居的距离向量 Dv = [Dv(y); y 为每个结点]
    • 保存结点 x 自己的距离向量 Dx = [Dx(y); y 为每个结点]
  • 迭代：每个结点等待来自任何邻居的更新，当接收到一个更新时计算它的新距离向量，并向它的邻居发布其新距离向量（最终会收敛）
  • 问题：当某链路费用增加时，可能发生无穷计数问题 => 毒性逆转（poisoned reverse）技术：如果 z 通过 y 路由选择到目的地 x，则 z 将告诉 y Dz(x) 无穷大

层次路由选择

前两种算法将网络只看作一个互联路由器的集合，忽视了规模带来的复杂度和管理自治的需要。由此引入自治系统（Autonomous System, AS）：

  • 由一组通常处于相同管理控制下的路由器组成
  • 在同一 AS 中的路由器运行同样的路由选择算法，且拥有彼此的信息
  • 为了互联 AS，每个 AS 内有一台或多台网关路由器（gateway router），负责向在本 AS 之外的目的地转发分组

路由选择协议!

互联网使用的路由选择协议都是自适应的，能随着网络通信量和拓扑结构的变化而自适应地进行调整。

可以把路由选择协议划分为两大类：

  • AS 内部路由选择协议：RIP（路由选择信息协议）、OSPF（开放最短路优先）
  • AS 间路由选择协议：BGP（边界网关协议）

RIP

RIP（路由选择信息协议）是一种分布式的基于距离向量（DV）的路由选择协议。距离是指跳数，直接相连的路由器跳数为 1，跳数最多为 15，超过 15 表示不可达。

RIP 按固定的时间间隔仅和相邻路由器交换自己的路由表，经过若干次交换之后，所有路由器最终会知道到达本 AS 中任何一个网络的最短距离和下一跳路由器地址。

算法过程：

  • 对地址为 X 的相邻路由器发来的 RIP 报文，先修改报文中的所有项目，把下一跳字段中的地址改为 X，并把所有的距离字段加 1；
  • 对修改后的 RIP 报文中的每一个项目，进行以下步骤：
  • 若原来的路由选择表中没有目的网络 N，则把该项目添加到路由选择表中；
  • 否则：若下一跳路由器地址是 X，则把收到的项目替换原来路由选择表中的项目；否则：若收到的项目中的距离 d 小于路由选择表中的距离，则进行更新（例如原始路由表项为 Net2, 5, P，新表项为 Net2, 4, X，则更新）；否则什么也不做。
  • 若 3 分钟还没有收到相邻路由器的更新路由表，则把该相邻路由器标为不可达，即把距离置为 16。

优点：实现简单，开销小

缺点：能使用的最大距离为 15，限制了网络的规模。并且当网络出现故障时，要经过比较长的时间才能将此消息传送到所有路由器。

OSPF

OSPF（开放最短路优先）路由选择协议基于链路状态（LS）。路由器向本 AS 内所有路由器广播信息（洪泛法），信息包括与哪些相邻路由器相连以及链路的度量。当链路状态发生变化或者周期到达时，路由器才会发送信息。

优点：

  • 更新收敛快
  • 安全
  • 允许使用多条相同费用的路径
  • 对单播与多播路由选择的综合支持
  • 支持在单个路由选择域内的层次结构

BGP

AS 之间的路由选择很困难，主要是因为互联网规模很大。并且各个 AS 内部使用不同的路由选择协议，就无法准确定义路径的度量。并且 AS 之间的路由选择必须考虑有关的策略，比如有些 AS 不愿意让其它 AS 经过。

BGP（边界网关协议）只能寻找一条比较好的路由，而不是最佳路由。它的手段如下：

  1. 从相邻 AS 处获得子网可达性信息；
  2. 向本 AS 内部的所有路由器传播这些可达性信息；
  3. 基于可达性信息和 AS 策略，决定到达子网的好路由。

每个 AS 都必须配置 BGP 发言人，通过在两个相邻 BGP 发言人之间建立 TCP 连接来交换路由信息。

链路层

两种不同类型的链路层信道：

  • 点对点链路（point-to-point link）：由链路一端的单个发送方和链路另一端的单个接收方组成；
  • 广播链路（broadcast link）：多个发送和接收结点都连接到相同的、单一的、共享的广播信道上。

链路层提供的服务：

  • 成帧（framing）：将数据报封装成链路层帧；
  • 链路接入（link access）：媒介访问控制（Medium Access Control，MAC）协议用于协调多个结点的帧传输；
  • 可靠交付（reliable delivery）
  • 差错检测和纠正（error detection and correction）

差错检测与纠正技术

3 种技术：

  • 奇偶校验（Parity Checking）：用于描述差错检测与纠正的基本思想。单个奇偶校验位原理是附加一个校验 bit，使其和数据 bit 中总有偶数个 1。因为无法处理偶数个 bit 差错的情况，因此可以使用二维奇偶校验，根据行和列来识别实际发生差错的 bit 并纠正。

  • 检验和方法（Checksum）：常用于运输层。因特网检验和是数据的 3 个 16 bit 字求得的和的反码。接收方对接收的数据（包括检验和）的和取反码，检测其是否全部为 1。

  • 循环冗余检测（Cyclic Redundancy Check，CRC）：常用于适配器中的链路层。

    1. 发送方和接收方首先必须协商一个 r+1 比特模式，称为生成多项式（generator）G（最高位为 1）；
    2. 对于 d 比特数据段 D，发送方附加 r 比特 R；
    3. d+r 比特用模 2 算数恰好能被 G 整除。

接收方检测和纠正错误的能力被称为前向纠错（Forward Error Correction，FEC）。

多路访问链路和协议

广播链路的多路访问问题（multiple access problem）：如何协调多个发送和接收结点对一个共享广播信道的访问。 => 多路访问协议

碰撞（collide）：结点同时接收到多个帧。碰撞帧的信号纠缠在一起，以至于涉及这次碰撞的所有帧都丢失了。

任何多路访问协议能被划分为 3 种类型之一：

  • 信道划分协议（channel partitioning protocol）
    • 时分多路复用（TDM）：优点是消除了碰撞且公平；缺点是限速，且需等待轮次。
    • 频分多路复用（FDM）：优缺点同上。
    • 码分多址（CDMA）：每个结点使用被分配的唯一编码来对它发送的数据进行编码。不同的结点能够同时传输，并且抗干扰。
  • 随机接入协议（random access protocol）：有碰撞时，涉及碰撞的每个结点反复重发（重发前等待一个随机时延）
    • 时隙 ALOHA：时间被划分为时隙（传输一帧的时间）。结点只在时隙起点开始传输帧。如果有碰撞，该结点在时隙结束前检测到这次碰撞，并以概率 p 在后续的每个时隙中重传直到无碰撞传输。
    • 纯 ALOHA：非时隙，完全分散
    • 载波侦听多路访问（CSMA）
    • 具有碰撞检测的载波侦听多路访问（CSMA/CD）
  • 轮流协议（taking-turns protocol）
    • 轮询协议（polling protocol）：结点之一被指定为主结点，以循环的方式轮询每个结点，告诉其能传输的帧。高效，但引入了轮询时延，且主结点不够健壮。
    • 令牌传递协议（token-passing protocol）：固定次序传递令牌（一个小的特殊帧），收到令牌的结点仅当有帧要发送时持有令牌，否则转发。没有主结点，缺点是一个结点的故障使整个信道崩溃，并且有结点忘记释放时需要调用恢复步骤。

载波侦听（carrier sensing）：一个结点在传输前先听信道，如果信道上有其他帧则等待。

碰撞检测（collision detection）：一个传输结点在传输时一直在侦听此信道，如果检测到另一个结点正在传输干扰帧，则停止传输，随机等待一段时间。

交换局域网

链路层编址

MAC 地址是节点（主机或路由器）的适配器具有的链路层地址，长度为 6 字节，具有扁平结构。

地址解析协议（ARP，Address Resolution Protocol）将 IP 地址转换为 MAC 地址。ARP 可看作跨越链路层和网络层两边的协议，并且是即插即用的，无需系统管理员配置。

发送方用 ARP 解析并在子网之内发送的工作流程：

  1. 构造 ARP 分组，包括发送、接收 IP 地址和自己的 MAC 地址；
  2. 让适配器在链路层帧中封装 ARP 分组，在子网中广播；
  3. 每个适配器把帧中的 ARP 分组传递给 ARP 模块进行比对；
  4. 匹配的节点给查询主机发送响应 ARP 分组；
  5. 查询主机更新 ARP 表。

以太网

  • 以太网是目前为止最流行的有线局域网。
  • 以太网技术向网络层提供无连接、不可靠服务。
  • CSMA/CD：以太网的多路访问协议

链路层交换机

  • 交换机的任务：接收入链路层帧并将它们转发到出链路
  • 交换机的功能：
    • 过滤（filtering）：决定一个帧应该转发到某个接口还是被丢弃
    • 转发（forwarding）：决定一个帧应该被导向哪个接口
  • 交换机的功能通过交换机表（switch table）完成：
    • 表项包含一个 MAC 地址，通向该 MAC 地址的交换机接口和表项放置在表中的时间（非过期时间）；
    • 如果没有对于目的地址的表项，交换机广播该帧；
    • 交换机表动态、自治建立，这是通过自学习（self-learning）实现。
  • 自学习（self-learning）：对于在每个接口接收到的每个入帧，存储：
    1. 该帧源地址字段中的 MAC 地址；
    2. 该帧到达的接口；
    3. 当前时间。

VLAN（虚拟局域网）

VLAN（虚拟局域网，Virtual Local Network）：端口被网络管理员划分为组，每组构成一个 VLAN

支持 VLAN 的交换机：

  • 允许经一个单一的物理局域网基础设施定义多个虚拟局域网，在一个 VLAN 内的主机彼此通信，仿佛它们与交换机连接；
  • 问题：VLAN 隔离：流量无法在 VLAN 中交换；
  • 解决方案：VLAN 交换机的一个端口与一台外部路由器相连，并将该端口配置为属于两个 VLAN（即视为通过路由器转发跨越）。

参考资料

主要参考机械工业出版社《计算机网络自顶向下方法（第 6 版）》。

其他参考资料：