计算机网络（自顶向下）学习笔记

计算机网络学习笔记

• 第二章 应用层

  • • 第二章 第一节 应用层协议的工作原理
    • • 第二章 第一节 第一 subsection 网络应用程序的体系结构
      • 第二章 第一节 第二 subsection 进程间通信
      • 第二章 第一节 第四 subsection 互联网提供的传输服务
      • 第二章 第一节 第五 subsection 应用层协议的作用机制

• 2.2 Web技术和HTTP协议*

• • 2.2.1 HTTP概述*

• 一次性数据传输与长期的数据传输（Subsection: 非持续连接与持续连接）

• 数据报文的格式（Subsection: HTTP报文格式）

• 客户端与服务器之间的交互：Cookie机制（Subsection: 用户与服务器的交互：cookie）

• 网络缓存技术（Subsection: Web缓存）

• 带有条件的GET请求（Subsection: 条件GET方法）

  • 2.3 因特网中的电子邮件
  • • 2.3.1 SMTP
    • 2.3.2 与HTTP的对比
    • 2.3.3 邮件报文格式
    • 2.3.4 邮件访问协议

• 2.4 DNS（Domain Name System）作为互联网目录服务的一种

• • DNS的主要功能包括：
    • 对于DNS服务器而言其核心任务就是解析主机名到IP地址的映射关系
    • 提供子域名解析功能以简化网络地址管理
    • 实现多级域名称到主机IP地址的转换过程

• 关于DNS的工作原理进行了简要介绍

• 在网络中常见的DNS记录类型有A记录TTL记录MX记录等主要用于不同类型的网络查询需求

• 在数据包传输过程中也会涉及到与DNS相关的安全问题因此需要采取相应的防护措施以确保网络通信的安全性

• 2.5 数据的分布式传输与共享机制

• 2.6 实时媒体流与内容分发系统

  • 2.6.1 网络视频服务概述

  • 2.6.2 基于HTTP的媒体流传输及DASH技术解析

  • 2.6.3 网络存储与分发技术研究（CDNS）

  • 2.7 套接字编程：生成网络应用

  • • 2.7.1 UDP套接字编程
    • 2.7.2 TCP套接字编程

  • CH3 运输层

  • • 3.1 概述和运输层服务

    • • 3.1.1 传输层和网络层的关系
      • 3.1.2 因特网运输层概述

    • 3.2 多路复用与多路分解

    • 3.3 无连接传输：UDP

    • • 3.3.1 UDP报文段结构
      • 3.3.2 UDP校验和

• 3.4 建立可靠的传输机制

• • 3.4.1 设计可靠的协议架构
• • 3.4.2 采用流水线机制优化协议
• • 3.4.3 引入回退机制以确保稳定

• • 3.4.4 灵活应用重传策略

    • 3.5 面向连接的传输：TCP

    • • 3.5.1 TCP连接
      • 3.5.2 TCP报文段结构
      • • 1 序号和确认号

    • 2 Telnet案例

      • 3.5.3 往返时间的估计与超时
      • • 1 估计往返时间

    • 2 设置和管理重传超时间隔

      • 3.5.4 可靠数据传输
      • 3.5.5 流量控制
      • 3.5.6 TCP连接管理

    • 3.6 拥塞控制原理

    • • 3.6.1 拥塞原因与代价
      • 3.6.2 拥塞控制方法

    • 3.7 TCP拥塞控制

    • • 3.7.1 TCP公平性
      • 3.7.2 明确拥塞通告（ECN）：网络辅助拥塞控制

• CH4网络层在数据平面上运行

  • • 4.1 网络层概述

    • • 4.1.1 涉及数据与控制平面的转发与路由选择过程
      • • 1 控制平面采用传统架构

    • 2 利用软件定义网络（SDN）技术实现的控制平面架构

      • 4.1.2 网络服务模型

第4章第2节路由器的工作原理中包含以下内容：
第4章第2节中的内容包括：

• 第4章第2节中的第一部分讨论了输入端口的处理以及基于目的地址的转发机制。

• 第一部分详细阐述了数据帧如何在输入端口进行交换过程。

• 第二部分则深入探讨了输出端口的管理流程。

• 在这一节中还分析了队列的形成位置。
  在第5节中进一步细化了关于队列的内容：
  5.1 节专门讨论输入队列的情况；
  5.2 节则专注于输出队列的具体管理策略

  复制代码

  * 4.2.5 分组调度
  * * 1 先进先出（FCFS，FIFO）

  • 2 优先权排队
  • 3 循环和加权公平排队

• 4.3 网络层中的寻址机制：基于IPv4的通信框架与其他网络技术的集成应用

  • 复制代码

    * 4.3.1 IPv4数据报组成要素解析

  • 复制代码

    * 4.3.2 数据报分片的作用与操作流程分析

  • 复制代码

    *  IP地址分配机制的设计与优化策略探讨

  • 复制代码

    * 高级地址转换功能在动态网络中的应用实例

  • 复制代码

    * 第六代IP地址体系的引入与扩展规划

  • 4.4 通用转发和SDN

  • • 4.4.1 匹配

• CH5 网络层：网络层中的控制平面功能模块

  • • 5.1 概述
    • 5.2 路由选择算法
    • • 5.2.1 链路状态路由选择算法过程
      • 5.2.2 距离向量路由选择算法机制

• 5.3 自主系统内部的路由决策机制：OSPF

• 5.4 不同ISP之间的 routing 协商：BGP

• • 5.4.1 BGP的功能与作用

• 5.4.2 发布与传播 BGP routing 信息

• 5.4.3 识别最优连接路径

• 5.4.5 路径优化策略

第5章 软件定义网络（SDN）体系结构

数据层与控制层间交互的具体案例

第第章软件定义网络（SDN）体系结构

第第6小节软件定义网络（SDN）中的关键组件分析

• CH6 链路层和局域网

• • 6.1 链路层概述

  • • 6.1.1 链路层提供的服务
    • 6.1.2 链路层在何处实现

  • 6.2 差错检测与纠正技术

  • • 6.2.1 奇偶校验
    • 6.2.2 检验和方法
    • 6.2.3 循环冗余检测

• 6.3 多端口通信链路及协议体系

• • 6.3.1 信道分配机制

  • 6.3.2 动态接入策略

  • 6.3.3 轮换制接入方法

  • 6.3.4 DOCSIS标准：适用于光纤以太网络的分层通信协议

    • 6.4 交换局域网
    • • 6.4.1 链路层寻址和ARP
      • 6.4.2 以太网
      • 6.4.3 链路层交换机

CH2 应用层

2.1 应用层协议原理

2.1.1 网络应用程序体系结构

Client/Server模式 (HTTP, IMAP, FTP)
服务器端：始终开启；配备固定不变的IP地址；通常部署于数据中心以实现扩展功能
客户端端：与服务器进行通信；可采用间歇式连接方式；可能拥有动态IP地址，并无需与其他客户端直接建立通信关系

p2p模式 ( P2P文件共享 [BitTorrent] )

• 任意两端之间实现了直连通信

  • 对等实体主动发起请求以获取服务，并在满足一定条件后作为回报提供相应服务

    • 自扩展特性——通过新增对等实体增强了整体承载能力，并提升了业务处理效率

  • 对等体间歇性连接并更改IP地址（复杂管理）

2.1.2 进程通信

process ：运行在端系统中的一个程序

• 当多个进程在同一个端系统上运行时, 它们通过进程间通信机制(由操作系统决定)来实现通信
  • 两个位于不同端系统的进程中, 会通过跨越计算机网络交换报文来实现通信

客户端进程中：发送消息给服务端的过程； 服务端进程中：在对话建立前接收客户端连接请求； （例如，在P2P架构中也存在客户端和服务器角色）

socket（套接字）
进程向网络发送报文和从网络接收报文的软件接口

进程寻址
IP地址、端口号（0-65535）

2.1.4 因特网提供的运输服务

应用程序对运输层协议的服务要求：可靠数据传输、吞吐量、定时和安全性

TCP协议：通过机制确保数据传输可靠性；采用算法避免网络拥塞；配备机制实现流量管理；面向连接型网络环境（无固定时间安排、最低发送速率保障、具备数据安全防护措施）。

UDP协议 ：不可靠数据传输

TCP安全

**安全套接字层（SSL）**增强型TCP：通过加密技术实现数据的安全传输，并提供数据完整性验证和端点身份认证等安全性服务。

2.1.5 应用层协议

应用层协议明确说明了互换式的报文类型、各报文类型间的语法结构、各字段的数据意义以及进程发送或接收报文的时间点及其处理流程。

• 开放协议：按照RFC文档的规定，在全球范围内统一标准的基础上制定；支持互操作性（如HTTP、SMTP）
  • 专有协议：目前主流的专有通信工具包括Skype和Zoom

2.2 Web和HTTP

Web页面 由多个位于不同Web服务器上的元素构成。这些元素中包含了多种类型的资源信息，并且这些资源信息中有一些会被其他页面所链接到。每一个资源都可以通过其唯一的URL地址来访问。

2.2.1 HTTP概况

HTTP 为实现Web通信而发展出的应用层协议；其中采用客户/服务器模式（客户端为浏览器, 服务器为Web服务器）。

HTTP如何使用TCP ：

1. 客户端对服务器建立TCP连接（设置绑定地址），绑定在80号端口。
2. 服务器对客户端响应连接请求。
3. 客户端与服务器之间传输HTTP请求数据包。
4. 断开TCP连接。

HTTP is a stateless protocol : the HTTP server does not store any information about the client (in-state protocols require maintaining past records and must coordinate lost records if either the server or client fails).

2.2.2 非持续连接和持续连接

非持续连接HTTP ：一次连接只发送一个对象，发送多个对象需要多次连接

发送一个对象：响应时间 = 2RTT + 文件传输时间

持续链接HTTP ：单次连接能够传输多个实体，在接收端完成接收操作后会立即发起下一个请求

2.2.3 HTTP报文格式

HTTP报文有两种：请求报文（request）和响应报文（response）

HTTP请求报文 （ASCII 人类可读形式）

    GET /index.html HTTP/1.1\r\n	//请求行（GET,POST,HEAD方法） /r回车符  /n换行符
    //首部行
    Host: www-net.cs.umass.edu\r\n	
    User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:80.0) Gecko/20100101 Firefox/80.0 \r\n
    Accept: text/html,application/xhtml+xml\r\n
    Accept-Language: en-us,en;q=0.5\r\n
    Accept-Encoding: gzip,deflate\r\n
    Connection: keep-alive\r\n
    \r\n	//行首回车符和换行符表示首部行结束

首部行

Host：首部行指明对象所在的主机

Connection：close开头的数据包用于在发送完报文后关闭该TCP连接（通常适用于断开状态下的TCP连接）

User-agent：首部行指明用户代理，即向服务器发送请求的浏览器的类型

Accept-language：首部行表示用户想得到该对象的语言版本

提交方式：常见的网页结构中经常会有表单字段；这些字段中的输入数据会被存储于相应的实体部分中进行管理与显示

GET方法 （传输数据）：HTTP GET请求消息的URL字段中包含用户的数据显示于以‘？’分隔的位置。

HEAD方法 ：请求使用GET方法请求特定URL时返回的报文的首部字段

上传至服务器的 PUT 方法：存储至服务器上的文件实体；通过 POST 请求传输完整的文件内容到指定路径下的目标位置。

HTTP响应报文

状态码

• 状态码2xx返回OK表示资源已成功接收
• 状态码3xx永久重定向表明目标已转移至不可用位置
• 状态码4xx错误回应通常由客户端提交的无效数据引起
• 状态码5xx内部错误通常由服务器内部错误引起

首部行

Connection：close首部行告诉客户发送完报文后关闭该TCP连接

Date：首部行指示服务器产生并发送该响应报文的日期和时间

Server：首部行指示该报文是由一台Apache Web服务器产生

Last-Modified：首部行指示了对象创建或最后修改的日期和时间

Content-Length：首部行指示了被发送对象中的字节数

Content-Type：首部行指示了实体体中的对象是HTML文本

2.2.4 用户和服务器的交互：cookie

网站和客户端浏览器使用cookie 来维护业务之间的某些状态

cookie技术有四个组件：

1. HTTP响应报文中包含的cookie头部字段
2. 下一时刻发送的HTTP请求报文中包含的cookie数据字段
3. 用户本地存储用于保存cookie文件，并由浏览器负责管理这些文件的位置
4. Web站点后台使用的数据库存储位置

cookie用处 ：授权、购物车、推荐、用户会话状态（Web邮件）

如何维护状态

• 协议端点处需在多个事务中维护发送方与接收方的状态。
  • 报文中包含HTTP请求中的cookie来表示状态。

隐私：使站点在其所属网站上深入了解您。第三方持久Cookie（持续追踪Cookie）通过持续追踪同一身份（Cookie值），允许在同一身份下访问多个网站。

2.2.5 Web缓存

目标 ：在不涉及源服务器的情况下满足客户端请求

• 用户将浏览器设置为仅向本地Web缓存器（代理服务器）发送HTTP请求。
  • 该过程表示浏览器将所有HTTP请求转发至缓存存储。
    • 当目标对象已存在时，则会直接从本地存储中调取该对象供客户端使用。
    • 若目标对象不存在于本地存储中，则会发起一次网络请求至源服务器获取目标。

Web缓存作用

• 提升响应速度（缓存器部署得越靠近客户端越好）
• 降低机构在传输路径上的数据流量
• 通过机制帮助"负面"内容提供商更好地完成交付任务

例子

• 接入带宽为1.54Mbps
  • 经过机构内路由器至服务器之间的往返时延为2秒
  • 网页对象尺寸为100kb
  • 平均请求数率为每秒15次

流量强度：(100k * 15) / 1.54Mbps = 0.97 排队时延大

增加一个缓存器，假设缓存命中率0.4

40%的请求被缓存器命中，响应用时很短可以忽略不计

60%的请求的流量强度：(100k * 15 * 0.6) / 1.54Mbps = 0.58 排队时延短

2.2.6 条件GET方法

目标 ：如果浏览器有最新的缓存版本，则不发送对象（无对象传输延迟）

• 客户端需配置HTTP请求以指定浏览器缓存副本的时间戳
  • 服务器将根据当前时间戳评估缓存的有效性；若最新缓存有效，则返回无内容响应并使用状态码HTTP/1.0 304 Not Modified

2.3 因特网中的电子邮件

主要组成部分：用户代理、邮件服务器和简单邮件传输协议

• User Agent

  • 撰写、编辑、阅读邮件，e.g. Outlook

• 邮件服务器

• 每个接收方在其专用的邮件服务器上拥有一个邮箱（mailbox） * 待发送的数据被组织在一个专门的队列中

• SMTP protocol

  • 基于TCP协议
  • 每台邮件服务器上同时支持运行SMTP客户端以及SMTP服务器端。

2.3.1 SMTP

使用TCP 服务从客户端传输邮件报文到服务器端，端口25

SMTP传输的三个阶段：握手、数据传输、关闭

命令/响应交互

• 命令：ASCII文本
• 响应：状态码和短语

2.3.2 与HTTP的对比

SMTP和HTTP都有ASCII命令/响应交互，状态码

2.3.3 邮件报文格式

• 每个首部行必须包含至少一个From字段和至少一个To字段。
  • 一个首部行可能包含至少一个Subject字段以及其他可选的字段。
  • 这里的To字段与From字段属于邮件报文自身的一部分。
  • 在2.3.1中的示例中提到的RCPT TO与MAIL FROM命令属于SMTP握手协议的一部分。

2.3.4 邮件访问协议

通过SMTP协议作为代理服务将邮件发送至发送方的邮箱（即用户的本地邮箱），该邮箱系统随后通过另一个SMTP客户端程序转发这些电邮至接收方邮箱

邮件访问协议：受信方通过用户代理发起从其所属邮件服务器获取邮件的操作，并需按照相关协议进行

• IMAP（因特网邮件访问协议）
• HTTP
• POP3（第三版的邮局协议）

POP3

• 采用删除模式下载：当接收方更改客户端主机后就无法再次接收一次邮件
  • 采用保留模式下载：邮件保留在服务器；客户端获得备份

POP3在会话间是无状态的

IMAP

• 通过邮件服务器系统自动完成对所有电子邮件的存储
• 支持用户以文件夹形式组织和管理其电子邮件
• 确保记录对话会话期间用户的活动状态，并详细说明每个文件夹名称对应的具体电子邮件及其相关聊天记录。

2.4 DNS：因特网的目录服务

Domain Name System（DNS，域名解析系统）

• 由基于层次化结构的DNS服务器 实现的分布式数据库。
• 一个使得主机能够进行分布式数据库查询的协议栈 * 网络功能核心, 并支撑其网络功能的核心实现。
• 复杂性主要体现在网络边缘部分。

2.4.1 DNS提供的服务

DNS服务

主机名到IP地址的转换相关技术方案设计。
应用层程序通过DNS解析机制获取指定主机别名对应的规范 hostname 值。
邮件服务器别名为 ... 的配置项设置。
负载均衡管理方案要求将冗余Web服务器的IP地址集合与同一个规范 hostname 相关联。

2.4.2 DNS工作机理概述

单一DNS服务器集中式分布的问题

• 单点故障
• 通信容量
• 远距离的集中式数据库
• 维护

分布式、层次数据库

根DNS服务器、顶级域（DNS）服务器、权威DNS服务器

本地DNS服务器

严格来说不属于DNS服务器层次结构

将主机的DNS请求转发到DNS服务器层次结构中

每个ISP都有一台本地DNS服务器

迭代查询

递归查询

DNS缓存

当某个DNS服务器接收到一个DNS响应时（或说），它会将其（或说）域名到地址的映射缓存至本地存储器中（或说），以便能够处理相应的查询请求

缓存机制提升了网络响应时间，并减少了网络上广泛传播的DNS报文数量。
映射到缓存中的资源具有TTL时间限制。
顶级域名服务器的映射通常被本地DNS服务器缓存。

缓存机制提升了网络响应时间，并减少了网络上广泛传播的DNS报文数量。
映射到缓存中的资源具有TTL时间限制。
顶级域名服务器的映射通常被本地DNS服务器缓存。

2.4.3 DNS记录和报文

DNS服务器存储了资源记录（Resource Record，RR）

RR格式：(name, value, type, ttl)

• 当类型设置为 A 时，则 name 为主机的主名称（primary host name），而 value 是该 IPv4 地址。
• 当类型设置为 NS 时，则 name 为其所属的 a 域（a domain），而 value 是该域权威 DNS 服务器（authoritative DNS server）的主机名称。
• 当类型设置为 CNAME 时，则 name 是主名称的一个别名（alias for the host name），而 value 则为其对应的规范主机名称（canonical host name）。
• 当类型设置为 MX 时，则 name 是邮件 MX 服务器的一个别名（mail MX server alias for），而 value 则是指向该别名为其对应的规范主机名称（.MX record points to）。

DNS报文

DNS的查询和响应报文结构相同

• 首部区域（12字节）
• 标识符字段（16位），会被传输至查询的回答结果中

• 标志字段（多个），包含多个标志。
  • 查询/回答：响应类型包括问题与答案
  • 权威的：响应质量高且可信度强
  • 希望递归：支持进一步搜索与扩展结果
  • 递归可用：允许嵌套搜索以获取更深层的信息

在DNS数据库中插入记录

• 由DNS注册登记机构来注册域名

• 提交基本和辅助权威的DNS服务器名称及对应的IP地址

• 注册登记机构将这些记录插入到.com顶级域服务器中

  • 用提供给机构的IP地址创建本地权威DNS服务器

DNS安全

DDos攻击

使用持续发送大量流量的方式攻击 root server。
迄今为止始终未能实现目标。
流量被进行过滤处理后，在众多 DNS 根服务器中被分组过滤器进行防护。
本地 DNS 根 server 存储 TLD server 的 IP 地址，并通过避开 root server 实现通信。

• 轰炸TLD服务器
  • 可能更危险

嗅探攻击

拦截DNS查询，返回虚假回复

• DNS缓存中毒

2.5 P2P文件分发

P2P体系结构的拓展性

分发N份文件：CS VS P2P 分发时间

具有P2P体系结构的应用程序能够是自拓展的

BitTorrent

• 文件被分割为256KB的数据块

  • 洪流中的对应方接收并传递块数据
  • 新加入洪流的参与者：
    • 不具备初始数据包，在后续过程中逐步收集
    • 通过注册跟踪器来获取当前参与节点的完整列表
    • 并将其连接至本地的邻近节点集合中（"邻居"群体）

• 在下载过程中, 对端节点会将数据块传输给另一方的网络节点.

  • 对端节点可能会更换与其交换数据块的连接对象.
  • 流失风险: 对端节点随时可能出现.
  • 当某个端点完整获取了整个文件后, 它有可能退出网络, 或者选择继续传播这份文件.

请求块

• 在任何时候，每个对等体各自拥有不同的文件块子集。
• Alice会定期请求其他对等体提供他们的块列表。
• 当Alice发现某个块缺失时，请她协助补充。

发送块：“一报还一报”

• Alice向自身当前拥有的速率最高的四个对等体（可用带宽最大值为疏通 ）传递数据分片

• 其他对等体被隔离（即无法从Alice接收任何数据分片）

• 每隔10秒进行一次评估以确保网络状态更新

  • 每30秒：随机选择另一个对等体，开始发送块

2.6 视频流和内容分发网

2.6.1 因特网视频

• 流媒体数据量：互联网带宽的主要用途
• 面临规模进一步扩大
• 引发多样性

  • 各类型用户对网络资源的需求存在显著差异

  • 解决方案：分布式应用程序级基础架构

视频流面临的挑战：

• 强制同步播放 ：在视频流过程中（即客户端视频播放期间），系统会严格同步回放时间以保证一致效果

• 但网络抖动导致延迟不可预测 ，因此系统必须设计足够的缓存能力来应对这种场景

• 其他潜在挑战：

  • 客户端操作：包括暂停、快进、倒退以及跳过功能
  • 视频分组传输可能出现丢失现象，并需进行重新发送

客户端缓冲和播放延迟 ：补偿网络增加的延迟、延迟抖动

2.6.2 HTTP流和DASH

HTTP的动态适应性流（DASH）

服务器

• 对视频文件进行分块处理
• 采用多种不同的编码速率对各个块进行处理
• 各文件采用的编码速率有所差异
• 将各文件复制到多个CDN节点中以增强访问效率
• 告知文稿：为每个分块提供相应的URL链接作为参考信息

客户端：

• 定期审查服务器至客户端的网络带宽
  • 获取告示文件中的数据块时，请每次仅提交一个块
    • 基于当前网络带宽状况，在确保数据传输稳定的前提下，请选择可持续的最大编码速率
    • 根据实时可用的网络状况，在不同时间段或不同服务器之间灵活设置编码速率

客户端的智能：客户端决定

• 什么时候请求块（以确保不会出现缓冲区溢出问题）
• 请求哪种编码速率（以提高传输质量）
• 在什么地方请求块（可以选择从与客户端‘接近’的位置或者从具有高可用带宽的URL服务器那里请求）

流媒体视频 = 编码 + DASH + 播放缓冲

2.6.3 内容分发网（CDNS）

难题：如何从数百万个视频中筛选出合适的并实时传送至数十万在线观众？

在多个地理分布的站点（ CDN ）存储/提供多个视频副本

CDN服务器安置原则：

• 深入挖掘 。通过在全球范围内的多个接入ISP节点部署服务器集群以透彻地到达ISP网络，并贴近终端用户。
• 吸引参与 。通过在几个核心位置建立大规模集群以吸引其他系统加入ISP网络。

2.7 套接字编程：生成网络应用

2.7.1 UDP套接字编程

2.7.2 TCP套接字编程

CH3 运输层

3.1 概述和运输层服务

传输层服务：在不同主机上运行的应用程序进程之间提供逻辑通信

3.1.1 传输层和网络层的关系

传输层：实现进程间交流（依赖并增强网络层服务）

网络层：实现主机间交流

3.1.2 因特网运输层概述

传输层动作

发送者负责处理相关事务，
提交至应用层数据包之前，
计算数据包头部字段值以确保完整性，
生成数据包结构并将其存储，
传输至IP地址处的数据包完成任务。

接收实体

TCP: Transmission Control Protocol

可靠、有序的交付

拥塞控制

流量控制

连接建立

UDP: User Datagram Protocol

• 不可靠、无序的交付
• “尽力而为”IP的简单扩展

TCP和UDP不提供的服务

• 延迟保证
• 带宽保证

3.2 多路复用与多路分解

为了使主机正确地将到达的传输层报文段分配至适当的套接字，在接收端处理每个传输层报文段时会包含多个字段信息。运输层协议在分析这些字段后能够识别出目标套接字，并相应地将数据包转发至对应的连接器。

运输层报文中数据被分配到正确的目标套接字的过程被称为多路分解（demultiplexing）。
源主机从多个套接字接收数据块，并对每个块进行打包加上头部信息以供后续分解使用；随后将组装好的报文重新发送至网络层的所有操作即被称为多路复用（multiplexing）。

多路复用工作原理

• 接收端通过主机获取到IP数据报

• 每个数据包包含发往与收往的源目标IP地址信息

• 每一个数据包都包含一个传输层的数据分组

• 其每个分组字段中均设有发送端口与接收端口字段

  • 主机通过端口号和IP地址将报文段交付给正确的套接字

无连接的多路复用与分解

当服务器在接收UDP数据包时，在接收UDP数据包时，在接收UDP报文段时（视具体实现而定），识别或获取该UDP数据包的目的端口号，并将该数据包转发至对应的网络接口。

当两个UDP报文段的源IPv4地址或源端口不同（包括同时不同），而它们的目标IPv4地址及目标端口一致时，则该两份数据将被目标网络层协议（OSPF/IS-IS）统一转发至同一个目标进程。

面向连接的多路复用与多路分解

TCP套接字是通过一个由四个元素组成的四元组来表示的：这四个元素包括源的IP地址、目标端口号码、目的的IP地址以及目的端口号号码。

多路分解：接收方使用所有四个值（四元组）将报文段定向到适当的套接字

服务器主机能够处理多个同时建立的TCP套接字；每一个这样的TCP套接字都对应一个运行中的进程，并由其唯一的四元组来标识。

3.3 无连接传输：UDP

• “简单直接”的互联网传输协议

  • “尽职尽力”服务下：
    • UDP报文段可能出现数据丢失的情况
    • 可能导致应用无法按预期顺序收到数据块

• 无连接性：

• UDP发送方与接收方的运输层实体之间没有握手过程

• 每个UDP报文段能够独立地处理与其他报文段无关的事宜

UDP好处：

• 关于确定传输数据内容及传输时机的应用层管理策略更为细致（采用无拥塞控制方案）
  • 无需进行连接操作（避免了建立连接所导致的时延与RTT问题）
  • 处于未连接状态
  • 分组头端（分组首部）开销较小

UDP应用：

• 流媒体应用（容忍丢失，速率敏感）
• DNS
• SNMP
• HTTP/3

使用UDP完成可靠数据传输（例如HTTP/3）

• 在应用层添加需要的可靠性
• 在应用层添加拥塞控制

3.3.1 UDP报文段结构

UDP首部只有4个字段，每个字段由两个字节组成

3.3.2 UDP校验和

校验和用作判断在UDP报文段从源发送到目的地的过程中是否存在比特的变化

字段相加，溢出则回卷（+1），得到和取反为校验和

在接收方，全部的16bit字段（包括校验和）加在一起将是1111 1111 1111 1111（分组中没有差错）

3.4 可靠数据传输原理

3.4.1 构造可靠数据传输协议

有限状态机

rdt1.0 经完全可靠信道的可靠数据传输

rdt2.0 经具有比特差错信道的可靠数据传输

自动重传请求协议（ARQ）

• 差错检验

  • 校验和

• 收取回馈

• acknowledgements (ACKs): 接收方明确告知发送方接收的分组

• negative acknowledgements (NAKs): 接收方明确告知发送方接收的分组存在错误

  • 重传。接收方收到有差错的分组时，发送方重传该分组

停止等待协议：发送方每发送一个分组，都要等待接收方的响应

rdt2.1 发送方处理出错的ACK/NAK

为分组添加“序号”字段

rdt2.2 无NAK的可靠数据传输协议

接收方接收到受损的数据段而不作NAK应答，并非对上次成功接收的数据段发出NAK报文

rdt3.0 经具有比特差错的丢包信道的可靠数据传输

发送方倒计数定时器

• 当每次发送一个分组时，则会触发定时器的启动。
  • 当定时器中断发生时做出响应（包括重传操作）。
  • 当正确接收ACK时，则会停止该定时器。

停等协议：链路容量大的情况下对于链路的利用率低

3.4.2 流水线可靠数据传输协议

• 扩展序列号的覆盖范围
  • 该协议在发送端与接收端之间存储多个数据分组
• 差错恢复：
  • 基于回退N步机制（Go-Back-N, GBN）
  • 基于选择重传机制（Selective Repeat, SR）

3.4.3 回退N步

发送方缓冲区 > 1 接收方缓存区 = 1

发送方

序号范围长度为N的窗口，存储连续的已发送但未被确认的分组

发送方收到ACK时，对序号为n的分组的确认采取累计确认 的方式

接收方

只接收正确序号的分组，不接收乱序分组

接收到乱序分组时丢弃并返回已接收最高序号的ACK

发送方窗口大小 <= 2^n - 1（n表示用几个比特位对发送数据序列编号）

GBN和SR的窗口最大尺寸 - 知乎 (zhihu.com)

3.4.4 选择重传

发送方缓存区 > 1 接收方缓存区 > 1

接收方独自核验全部准确接收的数据块

• 当接方接收的分组数据存在不确定性时,发送方将独立进行超时处理或进行再传输操作
• 发送方负责对每一个未经确认的分组配置计时机制

接收方窗口大小不得超过发送方窗口大小；SR窗口的最大值是2^{(n-1)}（其中用于编码发送数据序列编号所需多少比特位）

3.5 面向连接的传输：TCP

3.5.1 TCP连接

TCP连接是点对点 的，即在单个发送方与单个接收方之间的连接。

全双工数据传输：在同一连接中的双向数据流传递

MSS：最大报文段长度

3.5.2 TCP报文段结构

1 序号和确认号

序号（sequence number）

• 报文段首字节的字节流编号

确认号（ACK）

• 接收方期望接收到的下一字节编号
• 累计确认

TCP没有对乱序到达的分组规定处理动作

1. 接收方放弃接收顺序混乱的数据块
2. 接收方保存顺序错乱的数据单元，并同时处理缺失的单元以恢复完整数据序列

2 Telnet案例

3.5.3 往返时间的估计与超时

1 估计往返时间

SampleRTT：从报文段传输到ACK接收的测量时间（忽略重传）

EstimatedRTT：SampleRTT均值

获得一个新SampleRTT时，对EstimatedRTT进行更新：

    EstimatedRTT = (1 - α) * EstimatedRTT + α * SampleRTT				typical value: α = 0.125

• 指数加权移动平均（EWMA）
  • 过去样本的影响呈指数级快速下降

RTT偏差DevRTT：SampleRTT与EstimatedRTT差值的EWMA

    DevRTT = (1 - β) * DevRTT + β * |SampleRTT - EstimatedRTT|			typical value: β = 0.25

2 设置和管理重传超时间隔

超时间隔：EstimatedRTT + 安全余量

    TimeoutInterval = EstimatedRTT + 4 * DevRTT

3.5.4 可靠数据传输

简化的TCP发送方

    NextSeqNum = InitialSeqNumber
    SendBase = InitialSeqNumber		//最早未被确认的字节的序号
    
    loop(forever) {
    	swith(event)
    		
    		event: 从上层接收到数据
    			生成具有序号NextSeqNum的TCP报文段
    			if(定时器没有运行)
    				启动定时器
            向IP传递报文段
            NextSeqNum = NextSeqNum + length(data)
            break;
            
        event: 定时器超时
        	重传最早发送仍未接收确认的报文段
        	启动定时器
        	break;
        	
        event: 收到ACK，具有ACK字段值y
        	if(y > SendBase) {
        		SendBase = y
        		if(当前仍无任何应答报文段)
        			启动定时器
        	}
        	break;
    }

产生TCP ACK的建议 [RFC 5681]

例如SendBase = 71，MSS = 30

在数据链路层协议中定义的数据传输速率控制参数中

快速重传

发送方在报文段超时前接收到3个冗余ACK，则立即重传

3.5.5 流量控制

TCP通过让发送方维持一个（接收窗口）变量机制来实现流量控制

TCP接收方在TCP报头的接收窗口字段rwnd中通知空闲缓冲区容量；接收缓存RcvBuffer：通过设置套接字选项指定大小（常见默认值为4096字节）；不同操作系统根据需求自动调整RcvBuffer的大小

发送方对于接收到的rwnd限制未确认的数据（传输中）的数量

3.5.6 TCP连接管理

两次握手的问题

主机在收到关于会话确认的信息之前触发计时器后会重新发送此会话请求
只有当会话被关闭时才会发送重传请求
服务器会维持部分冗余连接，并且如果主机没有收到第二次会话确认就会重新建立该会话

| 发送方在维护冗余半连接时收到原来连接关闭前重发的数据

TCP建立连接三次握手：

1. 客户端的TCP先向服务器端的TCP发送一个特殊的TCP报文段。该报文段不包含应用层数据。该报文段首部SYN比特置为1，称为SYN报文段 。随机选取序号
2. 服务器从到达的数据报提取出TCP SYN报文段，为该TCP连接分配TCP缓存和变量。向客户端发送允许连接的SYNACK报文段
3. 客户端接收到SYNACK报文段后为该TCP连接分配缓存和变量，向服务器端发送确认的报文段，SYN比特置为0。该报文段负载中可以携带客户到服务器的数据

关闭连接

• 客户端、服务器各自关闭连接端

  • 发送FIN比特=1的TCP报文段

• 响应收到的FIN报文段发送ACK

  • 收到FIN后，ACK可以与自己的FIN组合

• 支持并行处理多个FIN交换流程

  • 在等待过程中若未接收到应方发送的数据，则判定并关闭连接

3.6 拥塞控制原理

3.6.1 拥塞原因与代价

1 情况一：两个发送方和无限缓存路由器

拥塞代价

• 分组的到达速率接近链路容量时（流量强度接近1），分组经历巨大排队时延

2 情况二：两个发送方和有限缓存路由器

拥塞代价

• 发送方被迫执行重传以弥补因缓存溢出导致的数据丢失
• 当网络出现长时间延迟时，发送方进行过度重传可能导致路由器误判超时时延并利用其链路带宽转发过多的分组副本

3 情况三：4个发送方和多台有限缓存路由器和多跳路径

右侧路由器中绿色流量率先争占缓存（红色流量必须经过上方阻塞路由器），其他 Routers 同样面临此问题而产生死锁

拥塞代价

当路由器丢弃一个分组时，在这条路径上每个上游路由器负责转发这个分组以导致其被丢弃的过程中所消耗的传输容量最终并未得到利用。

3.6.2 拥塞控制方法

端到端的拥塞控制

• 未从网络直接获得反馈
• 根据观察到的丢包和延迟推断出的拥塞
• 采用的技术手段

网络辅助的拥塞控制

• 路由器通过利用拥塞路由器的流向发送方/接收方发送确认信息。
  • 该方法能够反映拥塞程度并明确设定数据传输速率。
  • TCP ECN、ATM、DECbit 协议。

3.7 TCP拥塞控制

运行在发送方的TCP拥塞控制机制跟踪一个额外变量拥塞窗口（cwnd）

TCP rate = cwnd / RTT bytes/sec

在一个发送方中未确认的数据量不会超过cwnd与rwnd中的最小值，即

LastByteSent - LastByteACKed <= min{cwnd，rwnd}

通过调节cwnd的值，发送方因此能调整它向连接发送数据的速率

慢启动

在发生拥塞前

• 初始化：cwnd = 1MSS
• 每接收到一个ACK：cwnd +=1MSS
• 每个RTT的cwnd翻倍

初始速率慢，但是指数级增加快

拥塞避免

慢启动阈值ssthresh

• 当遇到拥塞时, 会触发拥塞避免机制, 计算并设置ssthresh为当前cwnd的一半, 并将窗口大小减少至最小值（1 MSS）, 然后开始缓慢增涨。
• 一旦窗口大小达到或超过当前拥塞阈值, 每个RTT周期会增加一个 MSS。
• 在遇到拥塞事件后, 会重复前述操作。

快速恢复

• 当接收到三个冗余的ACK消息时（即ssthresh），系统将触发快速重传机制（即快速恢复状态），并根据以下公式进行调整：ssthresh等于当前窗口大小的一半（即ssthresh = cwnd / 2），同时将窗口大小更新为ssthresh加上传输长度（即cwnd = ssthresh + 3 * MSS）。
• 每个冗余的ACK都会导致窗口大小增加一个报文长度（即cwnd = cwnd + MSS）。
• 直到接收到来自缺少报文段落的ACK消息为止（此时窗口大小将被重置至ssthresh值），系统将转入拥塞控制阶段。

加性增、乘性减（Additive-Increase，Multiplicative-Decrease，AIMD）

忽略慢启动阶段，假设丢包由三个冗余ACK引起

**TCP吞吐量 ** 一条连接的平均吞吐量 = 0.75cwnd/RTT

3.7.1 TCP公平性

假设共有K个基于相同带宽R的瓶颈链路同时运行着多个TCP会话，则每个会话的实际传输速率将准确达到理论上的最大值即R/K。

TCP在理想情况下是公平的

• 每个连接的RTT相同
• 对于一个主机—目的地对而言只有一条TCP连接

3.7.2 明确拥塞通告（ECN）：网络辅助拥塞控制

TCP部署通常实现网络辅助拥塞控制：

• 网络路由器通过在IP报头（ToS字段）中设置两个特定位来标识数据流量的拥塞情况。

  • 网络运营商根据网络性能需求和质量保证要求来决定如何设置流量标记策略。

• 通过发送拥塞报告向接收方发出

  • 接收方在ACK字段中指定ECE标志位
  • 包括：基于IP协议的ECN字段以及基于TCP协议的C、E控制位。

CH4 网络层：数据平面

4.1 网络层概述

数据平面 和控制平面

在发送主机和接收主机间传输报文段

• 发送方负责将报文段以数据包形式传递给链路层。
• 接收方通过传输层协议接收并传递该报文段。

每个网络设备中都有网络层协议：主机、路由器

路由器：

• 分析所有IP数据报的头部信息
  • 通过将数据报从输入端口转移到输出端口的方式，在整个路径上进行转发

4.1.1 转发和路由选择：数据平面和控制平面

网络层的两个重要作用

• 数据包传输（data packet forwarding） ：数据包被发送至相应的输出链路以完成传输任务 *

数据平面 负责处理来自不同输入链路的数据报，并将其转发到相应的输出链路之一。

Control Plane：network-level logical ，data packets are routed through end-to-end paths between the source and destination host machines via routers' routing configurations.

• 多种控制平面实现方案
• 常用的路由算法在路由器上进行配置
• 软件定义网络技术（SDN）则主要应用于服务器端的配置

1 控制平面：传统的方法

每个路由器中的各个路由算法组件在控制平面中相互作用

2 控制平面：SDN方法

远程控制器在路由器中计算并安装转发表

4.1.2 网络服务模型

网络层能提供的可能服务：

• 确保交付
• 具有延迟上界的确保交付
• 有序分组交付
• 确保最小带宽
• 安全性

因特网“尽力而为服务（best-effort service） ”不能保证

• 有序分组交付
• 确保交付
• 端到端时延
• 最小带宽

但是好处

• 该机制的简洁性使互联网得以广泛普及。
  • 配置充足的带宽可使实时应用如交互式语音、视频通常都能达到足够的性能水平。
  • 应用层分布式服务通过复制机制连接至客户端附近的数据中心和内容分发网络。
  • 弹性服务的拥塞控制有助于提升性能。

4.2 路由器工作原理

4.2.1 输入端口处理和基于目的地转发

输入端口处理

• 查询：执行查询操作时，请使用输入端口中的首部字段值，并通过映射表查找输出端口（匹配加操作）。

  • 转发

    • **基于目的地的转发；**此类型转发仅依据目的IP地址完成（传统型）
    • **广义化转发；**此类型转发可根据任意一组头部字段值进行实现

  • 排队：如果数据报到达的速度比转发到交换结构的速度快

最长前缀匹配规则 （当有多个匹配时）

在进行给定目标位置的转录表查询时,应采用与该位置匹配的最大前缀长度作为查询依据

通常使用三态内容可寻址存储器（TCAM）

• 内容可寻址：通过单个时钟周期快速定位地址，并适用于各种规模的表格
  • Cisco Catalyst设备支持存储多达1,048,576个TCAM转发表项

4.2.2 交换

交换结构

• 将数据块从输入链路传输至相应的输出链路

  • 交换速率达到：数据包在输入端至输出端传送的速度

    • 通常情况下，交换设备的工作速度是其输入/输出通道速度的多倍
    • 当系统拥有N个独立的输入通道时，在理论上最大化的交换速度应为其单通道处理速度乘以N（即达到理论极限）

  • 三种交换结构：经内存交换，经总线交换，经互联网络交换

经内存交换

第一代路由器

• 由CPU直接控制完成的数据交换操作采用传统计算机架构
• 数据分组被复制至系统内存后CPU读取目标地址字段并执行查找操作确定对应输出端口后完成数据传输至该端口位置
• 数据转发速率受限于内存带宽容量导致网络吞吐量存在物理限制
• 每次处理仅限单个数据分组

经总线交换

• 数据报借助共享总线将分组从输入端口转发至输出端口。
• **总线竞争（bus contention）**指的是交换速率受限于总线带宽。
• 每次仅处理单个分组。
• 接入层及企业网级路由器可满足需求（不适用于区域网或骨干线路）。

经互联网络的交换

• 在同一时间并行转发多个数据包, 突破总线带宽限制.
  • 采用2N条总线构成的多级异步交换网络.
  • 利用并行处理技术将数据报分割为固定长度的小块.
  • 在输出端通过交换网络完成数据再组合.

• 通过并行的多个交换“平面”的并行拓展实现规模与速度的提升

Cisco CRS路由器：

• 基本单元：8个交换平面
• 每个平面：三级互联网络
• 高达100T bps的交换速率

4.2.3 输出端口处理

4.2.4 何处出现排队

1 输入排队

• 当数据交换机制的速度低于输入端口的汇聚速度时，在输入端口可能导致队列形成
• 队列等待时间以及因输入缓存溢出而导致的数据丢失

线路前端发生阻塞（Head-Of-the-Line, HOL blocking）：处于队列前端等待传输的数据报将阻止队列中后续的数据报正常前进。

2 输出排队

• 当输入数据分组的速率超过链路传输速度时, 系统将执行缓存机制以减少丢包风险. 在面对网络拥塞时, 缓存已无剩余存储空间, 可能导致部分数据分组无法保存.

• 请阐述当前系统的删除策略: 当所有缓存均处于满负荷状态时, 请说明将优先删除哪些数据分组.

• 按照数据传输优先级策略 ，系统遵循从队列中选择待传输的数据报进行传输

• 在实施优先权调度机制时 ，系统将确保所有参与竞争的数据报能够公平地获得传输机会

需要多少缓存

RFC 3439 thumb rule (empirical rule): the cache size (B) should be equal to the round-trip time (RTT) multiplied by the link capacity (C).

当前理论研究：当大量TCP流（每个）经过一条链路时，在线路上所需的缓存数目为B等于RTT乘以C除以根号N

但是过多的缓冲会增加延迟（特别是在家庭路由器中）

• 较大的Round-Trip Time（长RTT）：会影响实时性应用的表现，并导致TCP数据传输效率下降
  • 基于延迟的拥塞控制 : 一种机制旨在"确保瓶颈链路始终处于适度负载状态"

缓存区管理

• 丢弃 ：缓冲区已满时添加、丢弃哪个分组

  • 弃尾 ：丢弃到来的分组
  • 基于优先权

• 标记 ：哪个分组被作为拥塞新号标记（ECN, RED）

4.2.5 分组调度

分组调度 ：决定下一个在链路上发送哪个分组

• FCFS
• 优先权排队
• 循环排队
• 加权公平排队

1 先进先出（FCFS，FIFO）

按到达顺序传输到输出端口的数据包

2 优先权排队

• 到达的分组分类，按类别排队

  • 任何首部字段都可用于分类

• 通过缓存中的高优先级队列传输该分组

• 同一批次的分组将按照先到达先服务原则处理

3 循环和加权公平排队

循环排队（RR scheduling）

• 到达的分组分类，按类别排队
  • 任何首部字段都可用于分类

服务器定期地循环扫描类别队列，并按顺序向每个可用的类传输一组完整的数据块。

加权公平排队（WFQ）

• 广域循环机制
  • 对于每一个类i来说，在每一个周期内都会分配到与其相关的加权服务量。
    分配的比例等于该类权重与所有权重之和的比值。
  • 每条数据流的最低传输速率设定基于其所属流量等级与所有流量等级对应的速率乘积。

网络中立性

• 已知端口号、源IP地址和目标IP地址等信息在技术层面可以被用来将流量进行分类管理，并实现差异化优先级处理。

• 技术层面而言：ISP应当如何合理配置网络资源。

• 分组调度与缓冲区管理是网络运营的核心手段之一；分组调度是实现数据传输效率的重要机制之一；缓冲区管理则是优化网络延迟的关键手段。

  • 社会、经济原则

    • 保护言论自由
    • 鼓励创新和竞争

  • 强制执行的法律规则和政策

2015年美国联邦通信委员会发布了一系列旨在保护和促进开放互联网的命令。这些规定明确划分了网络服务提供商与个人用户之间的边界

• 允许通过…依法进行网络管理的前提下不会阻止任何正当信息（包括但不限于应用程序、服务以及非恶意设备）的访问。
• 无限速率…基于互联网资源的前提下，在依法规范网络行为的情况下不会导致正常运行的服务受到损害。
• 不享有付费优先权…

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

主机、路由器中的网络层功能

4.3.1 IPv4数据报格式

4.3.2 IPv4数据报分片

最大传送单元（Maximum Transmission Unit, MTU） 是指链路层帧所能传输的最大容量

    最大分片可封装数据：d = MTU-20（20字节为IP首部大小）
    总片数：n = (L-20)/d
    每片的片偏移字段：Fi = d/8 * (i-1) , 1<=i<=n
    每片的总长度：Li = d+20(1<=i<n), Ln = L-(i-1)*d

4.3.3 IPv4编址

• 网络地址：每个主机或路由器与其物理链路通过网络地址进行绑定。
  • 连接口：用于实现主机或路由器与其物理链路的接合。
    • 路由器通常设有多个连接口。
    • 主机一般配置有一个或两个连接口（如基于以太网的固定连接或无线接入）

IP地址分为子网部分（高位bits）和 主机部分（低位bits）

子网

• 不依赖于路由器即可实现
  • 各主机之间可通过物理线路实现直接通信（通过单点中继交换数据包）
  • 位于同一子网中的节点（包括主机和路由器）其IP地址的高比特部分一致
  • 这些节点共同构成的部分称为该主网络中的一个子网

子网判断

• 为了确定一个子网, 可以将各个接口从主机或路由器上拆分出来, 形成若干个独立的网络
  • 每个子网（网络）都可以被称为 subnet

IP地址分类

• A类网络：以第1位开头（固定值），其中第2-8位（共7位）用于表示该网段的地址空间；第三至第十六位（共3字节）用于表示供该网段使用的主机数量。
  • B类网络：由前2位固定为"十"号符（即"十"），其中第3-第十六位（共十四bit）用于表示该网段的地址空间；最后两位作为子网地址使用。
  • C类网络：由前面固定的三个bit值"一十"决定其地址空间范围，在此范围内有二十一位bit组成地址空间；其中只有一位bit用于标识供该网段使用的主机数量。
  • D类网络：采用组播方式（内部广播）
  • E类网络：保留待用状态

特殊IP地址

• 子网部分：网络层全0位设置为本网络标识
  • 主机部分：网络层全0位设置为本主机标识
  • 主机部分：网络层全1位设置为广播地址，该网络下所有主机都能通过该地址进行通信
  • 当本地主机收到来自同一网络的127.0.0.1 multicast报文时，会立即转发给上层

内网（专用）IP地址

• 地址空间的一部分专为专用地址分配
  • 永远不会被视为公共地址分配
    • 仅在特定局域网内具有意义
      • 以识别不同设备为依据

该路由器不会转发那些目标地址属于专用地址范围的分组

无类别域间路由选择（Classless InterDomain Routing，CIDR）

• 子网部分可以在任意位置
• 地址格式：a.b.c.d/x，x为表示子网的位数

动态主机配置协议（Dynamic Host Configuration Protocol，DHCP）

目标：允许主机在加入网络时，动态地从服务器那里获得IP地址

当主机的IP地址租用临近到期时可以进行更新。
重新启动后可允许复用前使用的IP。
支持时段内新增移动用户接入网络。

DHCP工作概况（广播）

主机广播“DHCP discover”报文（可选）

* 源IP地址：0.0.0.0，目的地IP地址：255.255.255.255，yiaddrr：0.0.0.0

DHCP服务器用“DHCP offer”报文响应（可选）

* 源IP地址：DHCP服务器IP地址，目的地地址：255.255.255.255，yiaddrr：分配的IP地址

主机请求IP地址：发送“DHCP request”报文

* 源IP地址：0.0.0.0，目标IP地址：255.255.255.255，yiaddrr：选择的地址

DHCP服务器发送地址：“DHCP ack”报文

* 源IP地址：DHCP服务器IP地址，目的地地址：255.255.255.255，yiaddrr：选择的IP地址

DHCP不止可以返回子网中已经分配的IP地址：

• 默认网关
• DNS服务器的域名和IP地址
• 网络子网掩码

DHCP是运行在UDP上的

路由聚集（route aggregation）

多个子网可以通过高位相同的大子网进行聚集

4.3.4 地址网络转换

地址网络转换（Network Address Translation，NAT）

• 对外界而言，在本网络中所有端点仅共享一个IPv4标识符。
  • 在本网络内每个端点仅有一个有效的IPv4标识符。
  • 特点：
    • 不必由ISP分配专有IPv4号段即可给整个局域网提供统一IP——节省成本
    • 局域网内的IP配置变更无需对外公告
    • 无需因ISP更换其分配的IPv4号段影响到内部设置
    • 本网络内的各端点无固定IP对外不可见——确保通信安全

私有地址范围

• 10.0.0.0/8
• 172.16.0.0/12
• 192.168.0.0/16

NAT路由器

• 对 输出数据包 进行 替代处理 ，将 源IP地址及指定端口 替换为 NAT IP地址及新的指定端口 ，其中目的IP及端口保持不变。远端客户端（C/S）会采用NAT IP地址以及新的指定端口作为目标通信地址。
• 特别关注每一个 转换项（在NAT转换表中） 。
• 对 输入数据包 进行 替代处理 ，采用存储于NAT表中的映射项，并以 (源IP,指定端口) 的形式进行处理。

NAT争议

• 路由器不应仅限于对网络层的信息处理作用，在本例中对链路层的端口号进行了处理

  • 这一行为违背了传统的"端到端架构"原则
    • 复杂性在传输过程中被放置于网络边缘位置
      • 这种配置方式无需经过中转节点或进行数据转换即可直接送达目标主机
        • NAT技术可能会被一些应用设计者考虑到
          • 例如，在设计P2P应用时需要特别注意该问题
            • 在外网部署的设备可能无法主动连接至内网的服务器或终端设备上

• 通过IPv6技术能够有效克服地址资源不足的问题

  • 关于如何实现客户端穿透NAT后连接远程服务器的具体步骤是什么？

4.3.5 IPv6

• 采用固定长度首部字段来实现快速处理/转发功能
• 支持跨层级的网络层处理策略以实现对'流'的不同操作
• 首部格式的优化有助于提升服务质量（Quality of Service）

IPv6数据报格式

• next hdr: 数据报需传输给的上层协议与IPv4中的upper layer字段一致
  • 没有包含校验和首部字段（用于快速处理）
  • 不包含分片或重组相关字段
  • 没有选项字段（这些通常位于next hdr字段中）

从IPv4到IPv6的过渡

通道：在 IPv4 路由器之间的 IPv4 数据报中作为有效载荷携带的 IPv6 数据报（‘数据包中的数据包’）

4.4 通用转发和SDN

传统互联网网络设备：

• 垂直集成 ：每台路由器或其他网络设备均集成于独立的操作系统环境，并且包含硬件实现互联网标准协议（如IP、RIP等）的私有化版本。

  • 该技术通常由单一 vendor 提供整个架构设计。
  • 这样的架构成本较高，并可能导致设备对 vendor 的高度依赖性。

• 每个设备都具备了控制平面和操作平面的功能

  • 控制平面的功能是分布式的实现（升级存在困难）

传统方法实现网络功能的问题

• 垂直集成>高昂、不利于创新生态发展
  • 分布式的固有特性导致网络设备类型复杂
    • 无法影响数据流量的常规管理流程
    • 不具备实现流量工程等高级功能的能力
    • 配置错误可能导致整个网络运行出现故障
    • 升级及维护工作需要对所有设备进行操作：增加了管理上的复杂性
    • 要求系统具备丰富的硬件资源以应对未来需求：设计、开发并部署新型专用硬件以支持新增功能

SDN：逻辑上集中的数据平面

一种不同（多为远程）的控制器与控制代理（CA）进行交互，在这种模式下，控制器负责处理分组转发机制，并通过软件配置实现自动决策；而CA则在各自设备上处理相关数据以完成其职责。

• 将网络设备的功能划分为数据平面与控制平面两部分

  • 数据平面-分组交换机

    • 根据统一化的管理机制与功能划分原则，在SDN架构下将路由器及各类网络设备的功能进行整合与优化
      • 按照预设的流表（由SDN的控制平面动态配置的规则）进行智能处理流程
        • 包括基于流量信息的分类处理过程以及相应的操作指令生成
          • 如数据包转发与丢弃操作
          • 包括端到端的数据传输实现策略
          • 以及动态地址转换等关键功能模块
    • 整合化 设备功能：SDN分组交换机，在执行基于流量信息的智能处理逻辑

  • 控制平面-控制器+网络应用

    • 分离、集中
    • 计算和下发控制逻辑：流表

SDN控制平面和数据平面分离的优势

• 横向整合 通过构建良好的产业生态系统来推动行业发展（而非依赖封闭架构），从而实现了更加开放的网络部署方式。
  交换机设备及其相关的控制逻辑网络可由多家厂商进行专业化生产，并通过竞争促进整个行业的发展形成良好的生态系统。

• 采用集中的方式实现对控制逻辑的管理，并使网络状态易于管理。

  • 集中式控制器实时监控网络状态，并且编程较为简便，在传统方法中则较为复杂。
  • 通过该方案可防止路由器发生(MDoS)配置错误。

• 该方案采用流表匹配与行为操作相结合的方式，使得分组交换具备可配置性。

• 通过该技术框架来实现流量工程等高级特性。

• 在此架构下开发支持多种未来类型网络设备的技术方案。

4.4.1 匹配

每个路由器都有一个转发表（流表）

• 匹配附加操作：配对到达的分组中的比特，并根据结果采取相应的附加操作。
  • 目标地址转发策略：基于目标IP地址的转发策略。
  • 广义转发机制：
    • 多个头部字段均能决定执行的动作
    • 可能采取的具体操作包括丢弃、复制、修改以及记录分组信息

流表

• 流量（flow)： 由分组头字段定义（位于链路层、网络层及传输层的字段中）
  • 广域转发（广域转发）： 基本的分组处理逻辑
  • 模式匹配流程 ：通过与流表进行模式匹配来处理分组头字段
  • 动作执行 ：对于成功匹配的分组可实施丢弃、转发、修改或发送至控制器等操作
  • 优先级决策 ：当多个模式均被匹配时，则需确定优先顺序以消除歧义
  • 计数器设置 : 定义为#bytes and #packets

OpenFlow

CH5 网络层：控制平面

5.1 概述

构建网络层控制平面的两种方法：

• 每个路由器采用传统管理方式每个路由器内部均设有独立的路由算法组件负责管理其所在的网络段之间的交互协作

• *逻辑集中式控制（SDN）*远程控制器计算转发表并安装到路由器中

5.2 路由选择算法

路由算法分类

集中式还是分布式

中心化的路径选择机制（全局知识）：每个路由器都拥有完整的拓扑结构和链路成本数据。

  * **状态链路（LS）算法** * 

分散式路由选择算法（分散信息） ：迭代计算过程，与邻居交换信息。

  * 路由器最初只知道连接邻居的链路成本
  * **距离向量（DV）算法**

静态还是动态

• 静态路由选择算法 ：其路由变化速度较慢
• 动态路由选择算法 ：其路由变化速度较快
• 算法遵循基于链路代价的时间间隔进行更新响应

5.2.1 链路状态路由选择算法

迪杰斯特拉链路状态路由算法

• 集中式架构中掌握网络拓扑结构与各链路的成本信息

• 该架构被链路状态广播机制所实现

• 所有节点均掌握一致的信息

  • 计算从一个节点（源）到所有其他节点的最少代价路径

    • 给那个节点转发表

  • 迭代算法 ：经过第k次迭代后，可知道k个目的节点的最短开销路径

记号：

• C_{x,y} 表示在图中两个相邻顶点之间的一条边的成本或权重；当两个顶点之间不存在边时取值为无穷大。
  • D(s, v) 表示在本次迭代过程中找到的目标顶点s到达另一个目标顶点v所需花费的所有可能路径中的最小权重之和。
  • pred(s, v) 或者 p(s, v) 表示图中连接顶点s与顶点v之间的最短路径上的上一顶点（即父顶点）。
  • S 是图的一个顶点子集，在广度优先搜索算法中被标记为访问过的所有顶点集合。

源节点u的链路状态（LS）算法

    初始化：
    	N'={u}
    	对于节点v
    		如果v与u相邻
    			则D(u)=Cu,v
    		否则D(u)=∞
    		
    循环：
    	找到不在N'中且D(w)为最小值的节点w
    	将w添加到N'中
    	更新所有不在N'中且与w相邻的节点v的D(v):
    		D(v)=min{D(v), D(w)+Cw,v}
    直到 N'=N

例子

算法复杂性：n个节点

• 在每一次迭代过程中：系统性地检查所有节点以识别出那些既不在N’中又具有最低开销的节点w。
• 计算数量达到n平方级别，并由此带来较高的计算复杂度。
• 一种更为高效的方法能够将计算复杂度降低至O(n log n)。

消息复杂性：

• 每个 router 需要发送节点状态信息给所有的 other routers。
• 该算法通过 O(n) 条链路实现自源节点出发的广播信息传播。
• 单个 router 发送的信息会经过 O(n) 条链路进行传播：整个网络中所有 router 之间交换信息所需的总消息量达到 O(n²) 的复杂度。

振荡：

• 当路径成本受交通量影响时，可能产生路线振荡现象。
• 例子：
  • 流量从节点d、c、e分别以速率1、e（小于1）、1汇聚至目的地a。
  • 路径成本具有方向性特征，并受到容量限制的影响。

5.2.2 距离向量路由选择算法

Bellman-Ford方程

令Dx(y)是从节点x到节点y的最低开销路径

Bellman-Ford例子：

假设u的相邻节点x、v、w知道目的地z：

距离向量(Distance-Vector，DV)算法

关键思想：

每个节点不时地向邻居发送自己的距离矢量估计值

每当x从任何一个邻居获得一个新的距离矢量估计值时,它应用B-F方程来更新自己的距离矢量估计值

    Dx(y) <- minv{Cx,v + Dv(y)} for each node y ∈ N

在较小的自然条件下，估计值Dx(y)收敛到实际最小成本Dx(y)

迭代、异步 ：每一个迭代由以下原因引起：

• 本地链路开销变化
• 来自邻居的DV更新消息

分布式、自动停止 ：每一个节点只在它的DV改变时告知邻居

• 之后邻居通知它们的邻居—— 只在必要时
• 没有收到通知就不采取行动

链路开销改变：

节点检测到本地链路开销改变

更新路由信息，重新计算本地DV

如果DV改变，通知邻居

“好消息传的快，坏消息传的慢”

* 链路开销增大时，可能会出现无穷计数问题（**路由选择环路** ）

LS VS DV

收敛速率：采用O(n²)算法伴随O(n²)消息量的同时可能存在振荡现象；在收敛过程中可能会伴随收敛时间的变化；也可能存在路由选择过程中的自环现象；同时需关注网络中可能出现的无穷计数值问题。
鲁棒性方面：
当路由器出现故障或遭受损坏时可能会引发异常行为。
在正常的网络运行状态下 DV（距离向量） routers 会报告不正确的路径成本；
然而每个 router 只独立处理自身维护的 routing table；
而 DV routers 则有可能 incorrect地广播 path cost information 导致 routing loops 或者所谓的 "black holes"；
其他 router 会利用这些 table 来传播错误信息

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

路由选择的现实问题：

• 规模范围数以十亿计。

• 无法将全部目的地存储于转表中。

• 转表的变更会导致链路被覆盖。

• 自主管理机制：

• 互联网可被视为由多个子网相互连接而成

• 各个Internet Service Providers（ISP）都希望拥有自主控制本地网络路由的能力

将路由器组织进**自治系统（Autonomous System，AS，a.k.a. “domains”）**来解决

• internal-AS (intra-domain): 实现了同一_AS 内的路由传输。

  • 所有这些_routers_都遵循相同的内网协议。
  • 不同区域中的_routers_可以选择性地采用不同的内网协议。
  • Gateways: 边界节点，在其所属_AS 的边缘与其他_routers_连接。

• exterior AS (interdomain inter-AS) 负责管理其内部网络与外部网络之间的通信

• 负责处理内部和外部路由的路由器被称为内间外间路由器；而专门处理内部路由的路由器则被称为内间路由器

为了完成内部交换服务协议与外部交换服务协议的转变（消息通过从一个Autonomous System（AS）内转发到另一个AS内），AS的网关路由器必须

• 识别哪些路由依赖关系通过AS2可到达，并确定哪些路由依赖关系通过AS3可到达 *
  • 向AS中的所有路由器传输并通知其有关可到达性信息 *

最常见的内部网关协议：

• RIP：Routing Information Protocol * 基于DV：DV每30s交换一次

  • 不再广泛使用

• EIGRP：Enhanced Interior Gateway Routing Protocol采用了Distance Vector。

• 在过去的十年中专为Cisco设计。

• OSPF routing protocol: 按最短路径权重优先开放算法 LS路由选择算法

• IS-IS protocol primarily employs the same strategy as OSPF

OSPF路由

• 公开：可供公众使用

  • 经典 LS

    • 每个 router 都会发送其连接到 AS 中所有其他 routers 的链路状态信息
    • 包括带宽、延迟等因素在内的多种链路性能指标
    • 每个 router 都有完整的网络架构，并使用迪杰斯特拉算法计算路由表（Route Table）

  • 安全 ：所有OSPF信息都是经过鉴定的

OSPF层次化

• 采用两层架构划分本地网络与骨干网络
• 链路状态信息仅限于本地范围内的节点进行广播
• 每个路由器都具备本区域内完整的路径信息数据库；仅能识别并处理跨区目的地址（即边界路由器）

OSPF优点

• 安全是系统运行的基础保障
• 系统能够处理多种不同开销路径下的路由配置情况
• 具备全面支持单播与多播路由方案的能力
• 系统设计能够有效管理单个自治系统内的网络层次结构

5.4 ISP之间的路由选择：BGP

5.4.1 BGP的作用

外部网关协议：BGP（Border Gateway Protocol）

• 一种用于互联网之间相互连接的粘合剂
• 子网通过通告自身信息及可达目标与网络外部实现交互
• BGP协议为AS设计了方法：
  • eBGP 通过邻接AS获取子网可达性信息
  • iBGP 将该信息传播至AS内部所有路由器
  • 基于可达性信息以及 策略参数 选择前往其他网络的最优路径

5.4.2 通告BGP路由信息

B GP 交互：被两个等价实体（‘对等体’）通过半永久的TCP连接进行通信以交换B GP数据（基于179号端口）。

• 通告到不同目的网络前缀的 路径 （BGP是一个“路径向量”协议）

AS接收到来自其他AS的通告后可以将其转发给另一个AS

5.4.3 确定最好的路由

BGP属性和BGP路由

• BGP用于路由通告：由前缀和属性构成

• prefix表示需要通告的目的地

• 有两个关键属性：

  • AS路径（AS-path）：描述已通过的Autonomous System列表
  • 下一跳的Autonomous System网关路由器的IP地址（NEXT-HOP）

• 遵循策略的路由机制：

• 网关路由器在接收到路由通告时会依据导入策略来决定是否接受或拒绝该路径。

• 此外，在AS层也会根据AS策略来确定是否向其他AS发送该路径。

AS1中每台路由器都知道了到前缀x到两台BGP路由：

    路由器2a的最左侧接口的IP地址(NEXT-HOP)：AS2，AS3(AS-PATH)；x(prefix)
    路由器3a的最左侧接口的IP地址：AS3；x

BGP消息

• 不同BGP对等体之间通过TCP协议进行BGP消息的传输
  • BGP消息具体包括以下四种类型：
    • OPEN: 建立与远程BGP对等体之间的TCP连接并验证发送方身份
    • UPDATE: 通知新增路径信息（或删除旧有的路径记录）
    • KEEPALIVE: 在未携带更新信息的情况下维持连接的有效性，并确认OPEN请求的到来
    • NOTIFICATION: 报告上一条消息出现的问题，并用于关闭当前会话

内部网关协议与外部网关协议的不同

策略 ：

• 外部网关协议：管理员希望决定流量的路由方式，并确定哪些设备通过其网络进行路由。
  • 内部网关协议：由单一管理员负责管理网络配置，策略的重要性降低。

规模 ：

• 分层路由减少转发表大小，减少更新流量

性能 ：

• 外部网关协议：策略比性能更重要
• 内部网关协议：主要关注性能

热土豆路由选择（在AS内部进行选择）

• 选择内部代价更小的网关路由器，不关心外部网关协议的代价（AS跳数）

5.4.5 路由选择策略

ISP只想将数据流量转发至其内部网络或从内部网络转发数据流量（不涉及外部ISP之间的数据流动——这种做法符合现实应用场景）

A向B和C通告路径Aw

B选择不向C通告路径BAw

• 路由器CBAw对节点B并没有带来收益效果, 其原因在于端点w、A以及C均不属于节点B的客户群体
• 对于节点C而言, 并未发现存在通路经过节点A→B→C

C通过CAw路由到w

A,B,C是ISP

x,y,w是客户网络

x是多宿接入：加入到两个网络

策略强制 ：x不想B到C的路由经过x

* x不会向B通过到C的路由

路由器可以了解到到达目的地AS的多条路由，根据以下内容选择路由：

• 本地偏好值属性由策略控制。
  • 基于AS路径的最短路径。
  • 直接与之相连的路由器：立即转发模式。
  • 附加标准。

5.5 SDN控制平面

逻辑上集中 的控制平面的好处

• 更为简便的网络管理措施：防止路由器配置失误的同时使网络流量管理更加灵活

  • 基于表格转发机制（通过调用OpenFlow API）使得对路由器进行"软件定义"式控制成为可能

    • 集中式"软件定义"控制更为便捷：通过集中计算数据流表并分发给各节点完成转发任务
    • 分中式"软件定义"控制较为复杂：因为需要依据在每个节点上运行的分布式算法（协议）来确定数据流路径

  • 控制平面的开放（非专有）实现

    • 开放的生态系统

SDN关键特征

• 基于流量的分组转发
• 将数据平面与控制平面分开设计
• 网络控制功能由位于数据平面交换机外部的设备负责实现
• 具有高度可配置性的网络

SDN体系结构组件

• 分组式数据转发交换机：

• 硬件平台实现了通用数据平面转发功能，并以简洁高效的方式支持商业部署（第4.4节）。这种设计确保了性能和易用性。

• 流量调度表计算逻辑在控制器管理下配置完成。

• OpenFlow等API为基于表的数据平铺交换机提供了核心控制逻辑。

  • 与SDN控制器交流的协议（e.g.，OpenFlow）

• SDN控制器（网络控制平台）：

• 收集并管理当前网络运行状态的数据

• 通过北向接口接收并处理来自上层应用程序的控制指令

• 通过南向接口发送数据指令给连接的交换机设备

• 采用分布式架构设计以提升系统的性能、扩展性和容错能力

• 网络控制应用：

• 控制操作的核心：借助SDN控制器提供的底层服务及接口功能发挥网络控制作用

• 非解耦模式：可由第三方平台独立方提供实施：不同于传统的路由管理方式及现有的SDN架构

5.5.1 SDN控制平面：SDN控制器和SDN网络控制应用程序

SDN控制器结构

• 该网络控制应用程序层的接口通过北向接口与网络控制应用进行交互。
  • 该网络范围的状态管理层由分布式数据库管理，其涉及的元素包括：网络链路、交换机以及服务的状态。
  • 该通信层主要关注SDN控制器与受控设备之间的数据传输过程。

5.5.2 OpenFlow协议

控制器与交换机之间的操作

• 使用TCP交换报文

  • 选择性加密

• 三类OpenFlow报文：

  • 控制器到交换机
  • 异步（交换机到控制器）
  • 对称（其他）

• 与OpenFlow API不同

  • API是用于指定通用转发操作

控制器到交换机的报文：

• 配置（configuration）* ：控制器查询并设置交换机相关参数
• 特性（features）* ：通过发送请求来获取交换机属性
• 状态管理（modify-state）* ：动态维护表项信息
• 输出数据包（packet-out）* ：指定端口输出特定数据包

交换机到处理器的报文：

• 将无法与任何流量表项匹配的分组发送至控制器。（由来自控制器的 packet-out 报文决定如何发送）
• 触发 controller 删除相应的 flow table entry.
• 更新 controller 关知 port 的运行状态信息。

5.5.3 数据平面和控制平面交互的例子

S1经历与S2之间出现的网络故障后,通过使用OpenFlow协议中的"port-status"报文向网络控制器发出通知。
SDN网络控制器接收到该报文后,会根据其存储的信息更新各交换机的连接状态数据。
迪杰斯特拉路由算法会在完成自身注册流程之后,在遇到网络连接状态发生变更时,会主动向相关节点发送通知。
Dijkstra算法通过访问网络拓扑结构信息以及 controller中的当前连接状态数据,来计算出新的最优路由方案。
该路径状态路由管理程序会与SDN controller中的流量调度模块进行协同工作,负责生成所需的流量调度指令序列。
Network controller将利用OpenFlow协议向所有需要更新配置的交换机发送指令,从而完成新的流量规则表的配置工作。

CH6 链路层和局域网

6.1 链路层概述

术语：

设备：节点
通过通信路径与相邻节点建立联系的信道：链路 * 有线
无线
局域网

• 链路层分组：帧（frame） ，封装数据报

链路层负责在一个节点和它实际相邻 的节点之间通过链路传输数据报

链路层具体内容

数据报跨越不同网络路径采用多种网络传输机制进行传输。例如，在第一个网络通道上采用WiFi技术，在第二个则依赖于以太网连接。

• 每种链路层协议提供不同的服务
  • e.g., 提不提供可靠服务

6.1.1 链路层提供的服务

• 成帧 * 将数据报封装成帧，添加报头和尾部

• 介质上的通信 * 共享介质下的通信过程

• 媒体访问控制协议遵循共享介质下的媒体访问机制

• 媒体访问控制字段明确标识源设备和目的设备（与IP地址不同）

• 可靠数据传输在相邻节点之间进行 * 可靠数据传输（参见第3.4节）

• 未采用可靠交付机制的低比特差错链路包括光纤、同轴电缆以及双绞铜线等。

• 无线通信介质通常伴随着较高的比特错误率。

  • 流量控制 * 协调发送节点和接收节点之间的步调
    • 不提供拥塞控制

• 差错检测受到信号衰减与电磁噪声所导致的比特差错的影响

• 接收方通过检测差错来标记重传或丢弃帧

  • 差错纠正 * 接收方确认差错出现的位置并纠正差错（无需重传）

  • 全双工和半双工 * 使用半双工，链路是双向的，但是不能同时双向传输

6.1.2 链路层在何处实现

• 对于所有主机而言

  • 主体功能主要集中在网络适配器（network adapter）这一组件上；这也被称为网络接口卡（Network Interface Card, NIC）

  • 其核心功能体现在链路层控制器上；该控制器负责执行一系列链路相关的服务操作

  • 同时支持完成链路层与物理层的数据传输处理

  • 连接到主机对系统总线

  • 软件、硬件和固件的结合

6.2 差错检测与纠正技术

EDC：用于差错检测和纠正的比特

D：被差错检验保护的数据，可能包含报头

差错检验不是100%可靠

• 协议可能忽略少数错误事件，但这种情况较为罕见。
  • 采用多位EDC进行检测能够更有效地纠正差错。

6.2.1 奇偶校验

d比特数据和1比特的校验比特

• 偶校验

  • 这d+1比特中1的总数是偶数

• 奇校验

  • 这d+1比特中1的总数是奇数

二维奇偶校验

• 将D中的d个比特分成i行j列的形式，并对每一行和每一列计算其奇偶性。
  • 这种机制能够识别出现错误的比特并进行纠正。

6.2.2 检验和方法

因特网检验和

发送方：

• 将UDP报文字段（包括UDP头部域与IP地址）视为一个由16位整数组成的序列
  • 校验字段：计算该序列的总值。其补码即为互联网校验字段
  • 将计算出的校验字段值放置于报文段头部

接收方：

• 处理接收到了的报文段中的检验值
  • 核对计算所得的结果值与其对应的报告校验字段是否存在差异

6.2.3 循环冗余检测

D：数据比特，d位

R：CRC比特，r位

G：生成多项式，r+1位

发送方计算R

    R=reminder[D*2^r/G]			//D左移r位，除以G，得到的余数就是R（不够r位高位补0）

例：D=101110 d=6 G=1001 r=3

接收方用G去除接收到的d+r比特看能否整除

可以检测所有小于r+1比特的突发差错

检测到大于r+1比特的突发差错的概率为1-0.5^r

6.3 多路访问链路和协议

两种类型的网络链路：

• 点对点
• 广播链路

共享的广播信道是单一的

• 多个节点同时传输：通信冲突
  • 当节点在同一时间段接收多个信号时，就会出现碰撞（collision）。

多种接入协议（Multiple Access Protocol，MAP）/媒体接入控制协议（Media Access Control，MAC）

一种基于决策节点的分布式算法决定了如何在信道上共享资源，并根据情况确定传输时机。
信道间的交流必须依赖于现有信道机制。
这种系统缺乏用于协调的非主干通信通道。

MAP分类

• 信道划分（channel partitioning）协议 * 通过将信道分割为更小的“片”来实现资源细粒度的管理。

• 这些片被分配给节点作为专用资源。

  • 随机接入（random access）协议 * 不划分信道，允许碰撞
    • 从碰撞中“恢复”

轮换（taking-turns）协议 在该机制中，节点依次发送数据，在这种安排下, 负责发送更多数据的节点则可以采用较长的周期.

6.3.1 信道划分协议

时分多路复用（Time Division Multiple Access，TDMA）

• 按照时间段划分出若干个时隙（slot）。
  • 各节点在各自的时间段内接收固定长度的时隙。
  • 未被占用的时隙则保持空闲状态。

频分多路复用（Frequency Division Multiple Access，FDMA）

• 将信道的 freq spectrum 划分为多个不同的 sub-freq spectrum.
  • 每个 node 被分配到固定 freq 的 sub network 中.
  • 在传输过程中未使用的 sub-freq spectrum 处于 idle 状态.

6.3.2 随机接入协议

随机接入协议规定

• 如何检测碰撞
• 如何从碰撞恢复

时隙ALOHA

假设：

• 所有帧长度一致。
• 时间被划分为等长的时间片（每个时隙所占用的时间长度相同）。
• 节点仅在启动时刻开始传输。
• 节点是同步运行的。
• 如果多个节点在同一时间片内进行传输，则所有节点都会检测到冲突。

操作：

• 当节点接收新的帧后，在下一个时间间隔内完成传输
• 如果未发生冲突，则发送数据包
• 当冲突发生时，在后续的每一个时间段内有p的概率尝试重传

优点：

• 在一个特定的时间间隔内只有单个节点处于活动状态，则该信道能够被充分利用
• 高度分散性：每个节点在检测到冲突后会自主地选择是否再试一次
• 简单

缺点：

• 碰撞会导致时段的浪费
• 空闲时段会造成资源的流失
• 节点在发送数据的过程中能够及时识别冲突；尽管如此，在冲突发生后仍然会立即发送数据 frames, leading to the entire time slot being consumed.
• A time synchronization mechanism is in place.

时隙ALOHA效率：成功发送的时隙的占比

• 假设系统中有大量（多个）节点参与数据传输，在每个时间片内所有节点都会发送数据帧，并且每个节点在当前时间片内成功的发送概率为p。

• 某一个特定的节点在其时间片内实现数据发送的概率计算式为p乘以（1-p）的(N-1)次方。

• 当存在多个独立竞争的发送者时，在任一时间片内至少有一个设备能够成功发送数据的概率计算式是N乘以p再乘以（1-p）的(N-1)次方。

• 当系统中的总设备数量趋于无限大。

• 通过求导数并找出其极大值点的方法确定了最优的成功概率值约为0.37。

  • 最好：信道37%的时间被用于有效传输

纯ALOHA

• 无时隙：更简单，不需要同步

  • 帧到达就立即进行传输

• 不进行同步导致碰撞可能性提高

• 纯ALOHA效率：18%

载波侦听多路访问（CSMA）

传输之前进行监听

如果信道是空的 ：传输整个帧

如果信道忙 ：不传输

进行了载波侦听也可能发生碰撞：

* 传播时延导致两个节点间侦听不到对方刚开始进行的传播

发生碰撞会导致整个帧的传输时间浪费

* 距离和传播时延参与决定碰撞的可能

具有碰撞检测的载波侦听多路访问（CSMA/CD）

• 快速识别出冲突
• 当冲突发生导致传输中断时，请立即停止操作以避免资源浪费
• 有线网络中的冲突检测相对容易，在无线网络中则面临挑战

以太网CSMA/CD算法

1. NIC将从网络层接收的数据包打包成数据帧
2. 该网接口持续监测信道状态，并在信道可用时执行数据传输操作
3. 若数据传输过程中未发生冲突，则认为此次通信已顺利完成
4. 检测到冲突导致中止本次通信并发射干扰信号（jam signal）
5. 采用二进制指数退避策略以避免冲突，并在下一时间单位开始新的数据发送尝试

二进制指数后退算法（binary exponential backoff）

第n碰撞后，从[0,2^n-1]中随机选取一个整数K，等待K*512比特时间后进行重传

• 碰撞越多次，下一次碰撞都概率越低，平均等待时间越长

CSMA/CD效率

Tprop：局域网中两个节点间的传播时延

我们定义为Ttrans：发送完整帧的传输时延；并且该网络模型在性能上优于现有的类似方案；同时在复杂度上更低、成本上更为节省以及易于实现

6.3.3 轮流协议

轮询（polling）协议

• 主节点发起询问以确定其他节点是否需要传输数据 * 主要适用于低效的机器类型 * 缺点： * currying overhead * latency * (主节点成为单一故障点)

令牌传递（token-passing）协议

• 轮流转递机制使得 tokens 依次被各节点持有，在传输请求出现时才释放 tokens。
• token 本质是一种特殊的帧。
• 缺点：
  • 每次交换所需的资源消耗较高
  • 系统响应时间存在一定的延迟
  • 当单一故障发生时可能导致整个系统崩溃（token）

6.3.4 DOCSIS：用于电缆因特网接入的链路层协议

• 多路下行（广播）FDM信道：高达1.6Gbps/channel

  • 单CMTS在下行信道传输

• 多个传输通道（最高可达1Gbps per channel）

• 多路访问机制下，在同一时间所有用户争夺特定的上行信道时隙；而对于其他情况，则采用时分multiplexing（TDM）进行分配。

DOCSIS（Data Over Cable Service Interface Specification）

• 采用FDM技术对上下行信道进行处理
• TDM上行信道方面：指定一部分时间隙用于数据传输与业务承载
• 下行MAP帧用于动态调整与优化上行时间隙配置

6.4 交换局域网

6.4.1 链路层寻址和ARP

LAN中每个接口

• 都有独特的48位MAC地址
• 有本地独特的32位IP地址

1.MAC地址

• 作用：在同一子网内通过本地设备将数据帧从一个端口传输到另一个物理连接端口。
• MAC地址存储于NIC ROM中，并通常可通过软件配置实现设置。
• e.g.：1A-2F-BB-76-09-AD（十六进制表示）
• 扁平化架构确保MAC地址保持不变（与层次化架构相反）。
• 此特性使得将设备接入不同的局域网时无需更改MAC地址。
• 相比IP地址，在跨子网迁移会导致IP发生变更

MAC广播地址：全1，FF-FF-FF-FF-FF-FF

2.地址解析协议（Address Resolution Protocol，ARP）

局域网中每个IP节点（主机、路由器）都有一个ARP表

• 对于LAN中节点的IP/MAC地址映射：

  • <IP address；MAC address；TTL>

• TTL：映射表项缓存的时间

例子：主机A想要向主机B发送数据报（同一子网）

1. A尝试访问自己记录的ARP表，并未发现与B设备相关的MAC地址。
2. A向网络中发送携带B设备IP地址的信息以发起ARP查询。
3. B接收到请求后立即回应，并提供自身的MAC地址。
4. A立即处理请求信息，并成功地将与B设备相关的IP和MAC地址添加到其本地化的ARP数据库中。

3.发送数据报到子网以外

假设：

• A知道B的IP地址

• A知道第一跳路由器R的IP地址

  • iBGP

• A知道网关路由器R的MAC地址

  • 通过ARP查询

1. A生成包含源设备A的IP地址和目的设备B的IP地址的数据报。

2. 将数据包打包成帧

   • 帧的目的地是R设备的MAC地址（E6-E9-00-17-BB-4B）

3. R接收到一帧，并解析出其中的数据包后传递给网络层（IP）。

4. R通过查询路由表以确定出发送送路径，并传输包含源端点A IP 地址与目的端点B IP 地址的数据包至下一层。

5. R将链路层的数据包封装成一帧（包括出发送送端口所对应的MAC 地址），随后向上传输该帧。

   • 此时该帧的源MAC 地址即为选择作为出发送送端口使用的设备对应的MAC 地址：1A-23-F9-CD-06-9B
   • 为了获得目标端点对应的MAC 地址信息，R采用了ARP协议来获取该信息。

6.4.2 以太网

主导的有线LAN技术：

• 第一个广泛使用的LAN技术
• 简单便宜
• 速度：10Mbps - 400Gbps
• 单芯片，多种速度

以太网物理拓扑

• 总线：90年代流行

  • 所有节点在同一个碰撞域（相互之间可能碰撞）
  • 集线器

• 交换机：如今流行（替代集线器）

  • 不会相互碰撞

1.以太网帧结构

preamble（前同步码）：

• 用来同步发送方和接收方的时钟速率
• 7字节10101010 + 1字节10101011

address：MAC地址，每个6字节

• 如果 NIC 接收到匹配的 MAC 地址或广播 MAC 地址的帧，则将帧中的数据送到网络层的数据链路层协议 *
  否则的话，则丢弃该帧

type：指示上层协议

• 大多数为IP协议
• 用于在接收方上层解复用

CRC：循环冗余校验码

以太网：无连接、不可靠

• 无连接 ：接收方与发送方 NIC 之间不存在通信 handshake。

• 不可靠 ：接收方 NIC 不会向发送方 NIC 发送 ACK 或 NAK。

• 被丢弃的帧中的数据仅在发送方使用上层可靠传输（例如 TCP）时得以恢复；否则该数据将无法恢复而丢失。

  • 以太网的MAC协议：非时隙CSMA/CD，采用二进制指数后退

2.以太网技术

许多不同的以太网标准：

• 统一介质访问控制协议与帧结构
• 传输速率包括2 Mbps、10 Mbps、100 Mbps、1 Gbps、10 Gbps及40 Gbps（BASE之前）
• 以光纤、电缆及铜线作为介质的传输架构（后缀类型）

6.4.3 链路层交换机

交换机是一个链路层设备

存储、转发以太网帧

检测到收到的数据帧，并采用智能转发策略通过指定出口介质将数据帧发送至网络。

透明 ：主机间的交换机是“透明”的，主机不知道交换机会不会接收并转发帧

即插即用，自学习 ：

* 交换机不需要人工配置

交换机：多路同时传输

• 主机与交换机之间建立专用直连

• 交换机缓存数据包

• 以太网协议分别在每一个链路上独立运行：

  • 避免冲突的同时支持双向通信
  • 每一个链路都独立构成一个冲突域

• 数据交换中, A至A'与B至B'能够同步完成.

• 然而, 在同一时间段内无法实现同一节点间的同步完成.

每个交换机都有一个交换表：

• （主机MAC地址，主机对应接口，时间戳）

1.交换机转发和过滤

当帧到达交换机：

1. 采集接入口x及主机对应的MAC地址信息
2. 通过交换表查找对应的MAC地址
3. 当检测到目标端口y与当前处理端口x一致时
   • 若当前处理端口为y（即x=y），则对该帧进行过滤丢弃；若当前处理端口不为y（即x≠y），则将该帧转发至端口y
   • 否则将该帧发送给所有相关端口

2.自学习

• 交换表从头开始为空状态
• 每当某个接口接收一个以太网数据包（即入帧）时，在交换机的数据结构中记录下以下信息：发送端MAC地址、接收端IP地址以及当前事件发生的时间戳
• 如果某个时间段内未接收到来自该MAC地址对应设备发送的数据包，则将该MAC地址从交换机的数据结构中删除

3.链路层交换机的性质

• 消除碰撞
• 异质的链路（彼此隔离）
• 易于进行网络管理

4.交换机和路由器比较

都是存储转发：

• 路由器：网络层设备（检查网络层首部）
• 交换机：链路层设备（检查链路层首部）

都有转发表：

• 路由器：依据其连接的网络接口与其配置的路由策略动态生成相应的数据包转发表
  • 交换机：通过主动学习机制以及动态生成MAC地址的方式构建数据包转发表