计算机网络

计算机网络

中国科学技术大学 郑烇老师 - 计算机网络

参考教材 ： 计算机网络-自顶向下方法 原书第7版

计算机网络与因特网

这一章的目标是从整体上粗线条地勾勒出计算机网络的概貌，并且描述计算机网络的框架。包括大量的背景知识，讨论大量的计算机网络构件，而且将他们放在整个网络的大环境中进行讨论

目标：

• 了解基本术语和概念
• 掌握网络的基本原理

什么是 Internet？

从具体构成角度描述

节点

• 主机及其上运行的应用程序
• 路由器、交换机等网络交换设备

边 ： 通信链路 (communication link)

• 接入网链路 ： 主机连接到互联网的链路
• 主干链路： 路由器间的链路

数以亿计的、互联网的计算设备：

• 主机（host） = 端系统 (end system)
• 运行 网络应用程序

通信链路：

• 光纤、同轴电缆、无线电、卫星
• 传输速率 = 带宽 （bps)

分组交换设备 ： 转发分组（packets）

• 路由器和交换机

**协议**控制发送、接收消息

• 如 TCP、IP、HTTP、FTP、PPP

Internet ： “网络的网络”

• 松散的层次结构，互连的 ISP
• 公共 Internet vs. 专用 intranet

Internet 标准

• RFC ： Request for comments
• IETF ： Internet Engineering Task Force

从服务角度描述

使用通信设施进行通信的分布式应用

• Web、VoIP、email、分布式游戏、电子商务、社交游戏…
• …

通信基础设施为 apps 提供编程接口（通信服务）

• 将发送和接收数据的app与互联网连接起来
• 为APP 应用提供服务选择，类似于邮政服务
  • 无连接不可靠服务
  • 面向连接的可靠服务

什么是协议

人类协议和计算机网络协议示例

人类协议

发送特定的消息

收到消息时采取特定的行动或其他事件

网络协议

• 类似人类协议
• 机器之间的协议而非人与人之间的协议
• Internet 中所有的通信行为都受协议制约

协议（protocol）定义了在两个或多个通信实体之间交换的 报文格式 和 **次序**，以及 在 报文传输和 / 或接收 或 其他事件方面所采取的 动作

网络结构

• 网络边缘：
  • 主机
  • 应用程序（客户端和服务端）
• 网络核心
  • 互连着的路由器
  • 网络的网络 以 中国科学技术大学 郑烇老师的计算机网络为主线，<计算机网络-自顶向下方法>第7版、自己查阅资料辅助总结的学习笔记。内容包括 计算机网络概述、应用层、运输层、网络层、数据链路层、物理层等知识。
• 接入网、物理媒体
  • 有线或者无线通信链路

网络边缘

• 端系统（主机）
  • 运行 应用程序
  • 如 web、email
  • 在 “ 网络的边缘”
• 客户/服务器模式
  • 客户端向服务器端请求/接收服务
  • 如 web 浏览器/服务器 ： email 客户端/服务器
• 对等（peer-peer） 模式
  • 很少（甚至没有）专门的服务器
  • 如 GnutElla、KaZaA、Emule

采用 网络设施的面向连接服务

目标 ： 在 端系统之间传输数据

握手：

在数据传输之前做好准备

• 人类协议中 ： 你好、你好
• 两个通信主机之间为 连接建立状态

TCP - 传输控制协议（Transmission Control Protocol）

Internet 上面向连接的服务

• 可靠地、按顺序地传送数据
  • 确认和重传
• 流量控制
  • 发送方 不会淹没接收方
• 拥塞控制
  • 当网络拥塞时，发送方降低发送速率

采用基础设施的无连接服务

**目标**：在端系统之间传输数据

UDP - 用户数据报协议 （User Datagram Protocol )

• 无连接
• 不可靠数据传输
• 无流量控制
• 无拥塞控制

使用 TCP 的应用

• HTTP（web）
• FTP（文件传送）
• Telnet（远程登录）
• SMTP（email）

使用 UDP 的应用

• 流媒体
• 远程会议
• DNS
• Internet 电话

网络核心

网络核心： 路由器的网状网络（即由互联因特网端系统的分组交换机和链路构成的网状网络）

数据怎样通过网络进行传输？

• 电路交换：为每个呼叫预留一条专有电路：如 电话网
• **分组交换**：
  • 将要传送的数据分成一个个单位： 分组
  • 将分组从一个路由器传到相邻路由器（hop ），一段段最终从源端传到 目标端
  • 每段 ： 采用链路的 最大传输能力（带宽）

电路交换

在电路交换网络中，在端系统间通信会话期间，预留了端系统间沿路径通所需要的资源（缓存、链路传输速率）

端到端的资源被分配给从源端到目标端的呼叫 “ call ”

• 图中 ，每段链路有四条线路：
  • 该呼叫采用了上面链路的第二个线路，右边线路的第一个线路（piece）
• 独享资源： 不共享
  • 每个呼叫一旦建立起来就能够保证性能
• 如果 呼叫没有数据发送，被分配的资源将被浪费 （**no sharing**）
• 通常被传统电话网络采用

为 呼叫 预留端-端资源

• 链路带宽、交换能力
• 专用资源 ： 不共享
• 保证性能
• 要求建立呼叫连接

网络资源（如带宽）被分成 片

• 为呼叫分配片
• 如果某个资源处于**空闲状态**（不共享）
• 将 带宽分成片
  • 频分（Frequency - division multiplexing）
  • 时分（Time - division multiplexing）
  • 波分（Wave - division multiplexing）

FDM 与 TDM

链路中的电路是通过 频分复用（Frequency - Division Multiplexing，FDM） 或 时分复用（Time - Division Multiplexing， TDM） 来实现的。

对于 FDM，链路的频谱是由 跨越链路创建的所有连接共享。特别是，在连接期间链路为每条连接专用一个频段。

对于一条 TDM 链路，时间被划分为 固定期间的帧，并且每个帧又被划分为固定数量的时隙。当网络跨越一条链路创建一条连接时，网络在每个帧中为该连接指定一个时隙。这些时隙专门由该连接单独使用，一个时隙（在每个帧中）可用于传输该连接的数据

习题

计算示例

电路交换不适合计算机之间的通信的原因

• 连接建立时间长
• 计算机之间的通信有突发性，如果使用线路交换，则浪费的片比较多
  • 即使 这个呼叫没有数据传输，其所占据的片也不能够被别的呼叫使用
• 可靠性不高 ？

分组交换

以分组为单位存储-转发方式

• 网络带宽资源不再分为一个一个片，传输时使用全部带宽
• 主机之间传输的数据 被划分为一个个分组

资源共享，按需使用

• 存储 - 转发 ： 分组每次移动一跳（hop）
  • 在转发之前，节点必须收到整个分组
  • 延迟比线路交换要大
  • 排队时间

统计多路复用

A & B 时分复用 链路资源

A & B 分组没有固定模式 -> 统计 多路复用

网络核心的关键功能

存储 - 转发

**分组交换**：分组的存储转发一段一段从源端传到目标端，按照有无网络层的连接，分成：

• **数据报网络**：
  • 分组的目标地址决定下一跳
  • 在不同的阶段，路由可以改变
  • 类似 ： 问路
  • Internet
• **虚电路网络**：
  • 每个分组都带标签（虚电路标识 VCID），标签决定下一跳
  • 在 呼叫建立时 决定 路径，在整个呼叫中路径保持不变
  • 路由器维持每个呼叫的状态信息
  • X.25 和 ATM

数据报的工作原理

• 在通信之前，无须建立一个连接，有数据就传输
• 每一个分组都独立路由（路径不一样，可能会失序）
• 路由器 根据分组的目标地址进行路由

虚电路的工作原理

• 被传输到下一个链路之前，整个分组必须到达路由器 ： 存储 - 转发
• 在 一个速率为 R bps 的链路，一个长度为 L bits 的 分组的存储转发延时 ： L/R s
  • L = 7.5 Mbits
  • R = 1.5 Mbps
  • 三次 存储转发延时 ： 15 s

排队延迟和丢失

排队和延迟

每台分组交换机有多条链路与之相连。对于每条相连的链路，该分组交换机具有一个输出缓存（output buffer,也称为输出队列（output queue)),它用于存储路由器准备发往那条链路的分组。该输出缓存在分组交换中起着重要的作用。如果到达的分组需要传输到某条链路，但发现该链路正忙于传输其他分组，该到达分组必须在输出缓存中等待。因此，除了存储转发时延以外，分组还要承受输出缓存的排队时延（queuing delay)。这些时延是变化的，变化的程度取决于网络的拥塞程度。因为缓存空间的大小是有限的，一个到达的分组可能发现该缓存已被其他等待传输的分组完全充满了。在此情况下，将出现**分组丢失（丢包）**(packet loss),到达的分组或已经排队的分组之一将被丢弃。

如果 到达速率 > 链路的输出速率

• 分组将会排队，等待传输
• 如果 路由器的缓存用完了，分组将会被抛弃

转发表和路由选择协议

**路由**： 决定分组采用的源到目标的路径

转发: 将分组从路由器的输入链路转移到输出链路

在因特网中，每个端系统具有一个称为 IP 地址的 地址。当源主机要向目标主机要向目的端系统发送一个分组时，源在该分组的首部包含了目的地的 IP 地址，如同 邮政地址那样，该地址具有一种等级结构。当一个分组到达网络中的路由器时，路由器检查该分组的目的地址的一部分，并向一台相邻路由器转发该分组。 特别的是，每台路由器具有一个 转发表（forwarding table），用于将目的地址（或者目的地址的一部分）映射成为输出链路。当某分组 到达一台路由器时，路由器检查该地址，并用这个地址搜索其转发表，以发现适当的输出链路。路由器则将分组导向该出链路。

以上解释了 路由器使用分组的目的地址来索引转发表并决定适当的出链路。但是 转发表是如何进行设置的呢 ？

因特网 具有一些特殊的 路由选择协议（routing protocol），用于 自动地设置这些转发表。

例如 ： 一个路由选择协议 可以决定从每台路由器到每个目的地的最短路径，并使用这些最短路径的结果来配置 路由器中的转发表。

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

同样的网络资源，分组交允许更多的用户使用 网络

• 1 Mb/s 链路
• 每个用户
  • 活动时 100 kb/s
  • 10 % 的时间是活动的

电路交换：

• 10 用户

分组交换：

• 35 用户时
• >= 10 用户活动的概率为 0.0004

分组交换是 “突发数据的胜利者”？

• 适用于对 突发式数据传输
  • 资源共享
  • 简单，不必建立呼叫
• 过度使用会造成网络瘫痪 ：分组延迟和 丢失
  • 对可靠地数据传输需要协议来约束 ： 拥塞控制
• 怎样提供 类似电路交换的 服务 ？
  • 保证 音频/视频应用需要的带宽
  • 一个 仍未解决的问题 （chapter 7）

网络分类

接入网和物理媒体

怎样将端系统和边缘路由器连接 ？

• 住宅接入网络
• 单位接入网络（学校、公司）
• 无线接入网络

注意

• 接入网络的带宽（bits per second）?
• 共享/专用

接入网

考虑了位于 “网络边缘” 的应用程序 和 端系统后，下面考虑 接入网 ，这是指将端系统物理连接到其 边缘路由器（edge route） 的网络。

边缘路由器是指 端系统到任何其他远程端系统的路径上的第一台路由器。

住宅接入 ： modem

将 上网数据 调制 加载音频信号上，在电话线上传输，在局端将其中的数据 解调 出来；反之亦然

• 调频
• 调幅
• 调相位
• 综合调制

拨号调制器

• 56 kbps 的速率直接接入路由器（通常更低）
• 不能同时上网和打电话：不能 总是在线

住宅接入 ：线缆模式

数字用户线 digital subscriber line （DSL）

• 采用 现存的 到交换局 DSLAM（数字用户线接入复用器） 的电话线
  • DSL 线路上的数据被传到互联网
  • DSL 线路上的语音被传到电话网
• < 2.5 Mbps 上行传输速率 （typical < 1 Mbps）
• < 24 Mbps 下行传输速率 （typical < 10 Mbps）

线缆网络

有线电视信号线缆双向改造

FDM ： 在 不同频段传输不同信道的数据，数字电视和 上网数据（上下行）

• HFC ： hybrid fiber coax
  • 非对称 ： 最高 30 Mbps 的下行传输速率， 2 Mbps 的上行传输速率
• 线缆和 光纤网络 将每个家庭用户 接入到 ISP 路由器
• 各用户 共享 到 线缆头端的接入网络
  • 与 DSL 不同，DSL 的每个用户 一个专用线路到 CO （central office）

家庭网络

企业接入网络（Ethernet）

• 经常被企业和大学等机构采用
  • 10 Mbps，100 Mbps，1 Gbps，10 Gbps 传输速率
  • 现在，端系统经常直接接到 以太网络交换机上

无线接入网络

• 各无线端系统共享接入网络（端系统到 无线路由器）
  • 通过基站或者叫 接入点

物理媒体

• **Bit**：在发送-接收对 间传播
• **物理链路**：连接每个发送-接收对 之间的物理媒体
• 导引型媒体
  • 信号沿固体媒介被导引
    • 同轴电缆
    • 光纤
    • 双绞线
• 非导引型媒体
  • 开放的空间传输电磁波或者光信号，在电磁或者光信号中承载数字数据

**双绞线**：

两根绝缘铜导线拧合

• 5 类 ：100 Mbps 以太网，Gbps 千兆以太网
• 6 类 ： 10 Gbps 万兆以太网

同轴电缆、光纤

同轴电缆

• 两根同轴的铜导线
• 双向
• 基带电缆
  • 电缆上一个单个信道
  • Ethernet
• 宽带电缆
  • 电缆上有多个 信道
  • HFC

光纤和光缆

• 光脉冲，每个脉冲表示一个 bit，在玻璃纤维中传输
• 高速
  • 点到点的高速传输（如 10Gbps - 100 Gbps 传输速率）
• 低误码率 ： 在两个中继器之间可以有很长的距离，不受电磁噪声的干扰
• 安全

无线链路

• 开放空间传输电磁波，携带要传输的数据
• 无需物理 “线缆”
• 双向
• 传播环境效应
  • 反射
  • 吸收
  • 干扰

无线链路类型

• 地面微波
• LAN
• wide-area
  • 3G cellular : ~ 几 Mbps
  • 4G ：10Mbps
  • 5G ： 数 Gbps
• 卫星
  • 每个信道 kbps 到 45 Mbps（或者多个聚集信道）
  • 270 msec 端到端延迟
  • 同步静止卫星和地轨卫星

Internet 结构 和 ISP

互联网络结构 ： 网络的网络

• 端系统通过 接入**ISPs** (Internet Service Providers) 连接到互联网
  • 住宅，公司和 大学的 ISPs
• 接入 ISPs 相应的必须是互联的
  • 因此任何两个 端系统可互相发送分组给对方
• 导致的 “ 网络的网络” 非常复杂
  • 发展和演化是通过 经济的 和 国家的 政策来驱动的
• 让我们采用渐进方法来描述当前互联网的结构

• 在网络的最中心，一些为数不多的充分连接的大范围网络（分布广、节点有限、但是之间有着多重连接）
  • “ tier-1” commercial ISPs ,国家或者国际范围的覆盖
  • content provider network : 将他们的数据中心接入 ISP，方便周边用户的访问；通常私有网络之间用专网绕过第一层 ISP 和

network of networks

• 松散的层次结构
• 中心：第一层 ISP （如 UUNet，BBN/Genuity，Sprint，AT&T） 国家/国际覆盖，速率极高
  • 直接与其他第一层 ISP 相连
  • 与大量的 第二层 ISP 和 其他客户网络相连

• 第二层 ISP ： 更小些的（通常是区域性的）ISP
  • 与一个或多个第一个 ISPs ，也可能与其他第二层 ISP

• 第三层 ISP 与其他本地 ISP
  • 接入网（与端系统最近）

• 一个分组要经过许多分组

• 许多内容提供商（如 Google） 可能会部署自己的网络，连接自己在各地的 DC （数据中心），走自己的数据
• 连接若干 local ISP 和各级（包括一层）ISP，更加靠近用户

ISP 之间的连接

• POP ： 高层 ISP 面向客户网络的接入点，涉及费用结算
  • 如一个低层 ISP 接入多个高层 ISP，多宿（multi home）
• 对等接入： 两个 ISP 对等接入，不涉及费用结算
• IXP ： 多个对等 ISP 互联互通之处，通常不涉及费用结算
  • 对等接入
• ICP 自己部署专用网络，同时 和各级 ISP 连接

分组延时、丢失和吞吐量

在理想状态下 ，我们希望因特网服务能够在任意两个端系统之间随心所欲的瞬间移动数据而没有任何的数据丢失。然而这是一个极高的目标。与之相反，计算机网络必定要限制在端系统之间的吞吐量（每秒能够传送的数据量）。在端与端之间引入时延，而实际上也会存在 丢失分组。

分组丢失和延时是怎么发生的？

在路由器缓冲区的分组队列

• 分组到达链路的速率大于链路传输的速率
• 分组等待排到队头、被传输

分组交换网中的时延概述

分组从一个主机（host 源）出发，通过一系列的路由器传输，在另一台主机（目的地）中结束它的历程。当分组从一个节点（主机或路由器）沿着这条路径到后继节点（主机或路由器），该分组在沿途的每个节点经受了几种不同类型的时延。这些时延最为重要的是

• 节点处理时延（nodal processing delay ）
• 排队时延（queuing delay）
• 传输时延（transmission delay）
• 传播时延（propagation delay）

这些时延总体累加起来是 节点总时延

节点处理时延

• 检查 bit 级 差错
• 检查分组首部和决定将分组导向何处

排队时延

• 在输出链路上等待被传输的时间
• 依赖于路由器的拥塞程度

传输时延

• R = 链路带宽（bps）
• L = 分组长度（bit）
• 将分组发送到链路上所需的时间 = L / R
• 存储转发延时

传播延时

• d = 物理链的长度
• s = 在媒体上传播的速度 （~ 2 x 10 ^ 8 m/sec）
• 传播延时 = d / s

Note : s and d are very different quantities

时延的类型

作为源和目的地之间的端到端路由的一部分，一个分组从上游节点通过路由器 A 向路由器B 发送。A 具有 通往 B 的出链路。该链路 前面有一个 队列 （也称缓存）。当 分组从上游节点到达路由器 A 时，路由器 A 检查该分组的首部以决定它的适当 出链路，并将该分组导向该链路。

在此例子中，对该分组的出链路是通向路由器 B 的那条链路。 仅当 在该链路没有其他分组正在传输并且没有其他分组排队在该队列之前时，才能在该链路上传输该分组

如果 该链路当前正繁忙或有其他分组已经在该链路上排队，则 新到达的分组将加入排队

处理时延

协议层次及服务类型

协议层次

网络是一个复杂的系统

• 网络的功能复杂：
  • 数字信号的物理信号承载、点到点、路由、rdt、进程区分、应用等等
• 现实来看，网络的许多构成元素和设备
  • 主机
  • 路由器
  • 各种媒体的链路
  • 应用
  • 协议
  • 硬件、软件

层次化方式实现复杂的网络功能

• 将网络复杂的功能分层功能明确的 层次，每一层实现了其中一个或一组功能，功能中有其上层可以使用的功能 ： 服务
• 本层协议实体相互交互执行本层的 协议动作，目的是实现本层功能，通过接口为上层提供更好的服务
• 在实现本层协议的时候，直接 利用率下层所提供的的服务
• 本层的服务：借助下层服务实现的本层协议实体之间交互带来的新功能（上层可以利用的） + 更下层所提供的的服务

服务

服务和服务访问点

• 服务（Service）：
  • 低层实体向上层实体提供他们之间的通信的能力
    • 服务用户（service user)
    • 服务提供者（service provider）
• 原语（primitive）
  • 上层使用下层 服务的形式，高层使用低层提供的服务，以及低层向高层提供服务都是服务访问原语来进行交互的 — 形式
• 服务访问点 SAP（ Services Access Point）
  • 上层使用下层提供的服务通过层间的接口 - 地点
    • eg: 邮箱
      • 地址（address） ： 下层的一个实体支撑着上层的多个实体，SAP 有标志不同上层实体的作用

服务的类型

面向连接的服务

• 面向连接的服务（Connection-oriented Service）
  • 连接 （Connection）
    • 两个通信实体为进行通信而建立的一种结合
  • 面向连接的服务通信的过程：
    1. 建立连接
    2. 通信
    3. 拆除连接
  • 面向连接的服务的 例子
    • 网络层的连接被称为虚电路
  • 适用范围
    • 对于大的数据块要传输；不适合小的零星报文
  • 特点
    • 保序
  • 服务类型
    • 可靠的信息流 传送页面（可靠的获得，通过接收方的确认）
    • 可靠的字节流 远程登录
    • 不可靠的连接 数字化声音

面向无连接的服务

• 无连接的服务（Connectionless Service）
  • 无连接服务
    • 两个对等层实体在通信前不需要建立一个连接，不预留资源；不需要通信双方都是活跃（eg: 寄信）
  • 特点
    • 不可靠
    • 可能重复
    • 可能失序
  • IP 分组，数据包
  • 使用范围
    • 适合 传送零星数据
  • 服务类型
    • 不可靠的数据报 电子方式的函件
    • 有确认的数据报 挂号信
    • 请求回答 信息查询

服务和协议

服务与协议的区别

• 服务（Service）
  • 低层实体向上层实体提供他们之间的通信的能力，是通过 原语（primitive） 来操作的， 垂直
• 协议（protocol )
  • 对等层实体（peer entity）之间在相互通信的过程中，需要遵循的规则的集合， 水平

服务与协议的关系

• 本层 **协议的实现 ** 要靠下层提供的服务来实现
• 本层实体通过协议为 上层 提供更高级的服务

数据单元（DU）

分层处理和实现复杂系统的好处

• 概念化
  • 结构清晰，便于标示网络组件，以及描述其相互关系
  • 分层参考模型
• 结构化
  • 模块化更易于维护和系统升级
  • 改变某一层服务的实现不影响系统中的其他层次
    • 对于其他层次而言是透明的
• 分层思想被认为有害的地方

Internet 协议栈

• **应用层**： 网络应用
  • 为人类或者其他应用进程提供网络应用服务
  • FTP、SMTP、HTTP、DNS
• **传输层**：主机之间的数据传输
  • 在网络层提供的端到端通信基础上，细分为 进程到进程，将不可靠的通信变成可靠地通信
  • TCP、UDP
• 网络层 ： 为数据报从源到目的地 选择路由
  • 主机主机之间的通信，端到端通信，不可靠
  • IP、路由协议
• **链路层**： 相邻网络节点间的数据传输
  • 2 个 相邻 2 点的通信，点到点通信，可靠或不可靠
  • 点到点协议 PPP，802.11（wifi）,Ethernet
• **物理层**：在线路上传送 bit

ISO / OSI 参考模型

• **表示层**： 允许应用解释传输的数据 （加密，压缩，机器相关的表示转换）
• **会话层**：数据交换的同步，检查点，恢复
• 互联网协议栈没有这两层（在 应用层）

封装与解封装

各层次的协议数据单元

• 应用层：报文（message）
• 传输层：报文段（segment）：tcp 段，UDP 数据报
• 网络层：分组 packet（如果无连接方式 ： 数据报 datagram ）
• 数据链路层 ： 帧（frame）
• 物理层：位 （bit)

小结

• 组成角度看 什么是互联网
  • 边缘 ： 端系统（包括应用） + 接入网
  • 核心 ： 网络交换设备 + 通信链路
  • 协议 ： 对等层实体通信过程中遵守的规则的集合
    • 语法，语义，时序
• 为了实现复杂的网络功能，采用分层方式设计、实现和调试
  • 应用层、传输层、网络层、数据链路层、物理层
  • 协议数据单位
    • 报文、报文段、分组、帧、位
• 从 服务角度 看互联网
  • 通信服务基础设施
    • 提供的通信服务： 面向连接 无连接
  • 应用
• 应用之间的交互
  • C/S 模式
  • P2P 模式
• 数据交换
  • 分组数据交换
  • 线路交换
• 比较 线路交换和 分组交换
• 分组交换的 2 中方式
  • 虚电路
  • 数据报
• 接入网和物理媒介
  • 接入网技术
    • 住宅：ADSL，拨号，cable modem
    • 单位：以太网
    • 无线接入方式
  • 物理媒介
    • 光纤，同轴电缆，以太网，双绞线
• ISP 层次结构
• 分组交换网络中 延迟和丢失是如何发生的
  • 延迟的组成：
    • 处理
    • 传输
    • 传播
    • 排队
• 网络的分层体系结构
  • 分层体系结构
  • 服务
  • 协议数据单元
  • 封装与解封装
• 历史

应用层

在本章中，我们将学习有关网络应用的原理和实现方面的知识。我们从定义关键的应用层概念开始，其中包括应用程序所需要的网络服务、客户和服务器、进程和运输层接口。

应用层是我们学习协议非常好的起点，它最为我们熟悉。

目标

• 网络应用的 原理：网络应用协议的概念和实现方面
  • 传输层的服务模型
  • 客户-服务器模式
  • 对等模式（peer-to-peer)
  • 内容分发网络
• 网络应用的 实例：互联网流行的应用层协议
  • HTTP
  • FTP
  • SMTP/POP3/IMAP
  • DNS
• 编程：网络应用程序
  • Socket API

创建一个新的网络应用

编程

• 在不同的端系统上运行
• 通过网络基础设施提供的服务，应用进程彼此通信
• 如 WEB
  • web 服务器软件与浏览器软件通信

网络核心中没有应用层软件

• 网络核心没有应用层功能
• 网络应用只在端系统上存在，快速网络应用开发和部署

应用层协议原理

网络应用程序体系结构

可能的应用架构

• 客户-服务器模式（C/S : client/server)
• 对等模式 （peer-to-peer)
• 混合体：c/s 和 p2p

客户-服务器（c/s 体系结构

服务器

• 一直运行
• 固定的 IP 地址和周知的端口号（约定）
• 扩展性：服务器场
  • 数据中心进行扩展
  • 扩展性差

客户端

• 主动与服务器通信
• 与互联网有间歇性的连接
• 可能是 动态 IP 地址
• 不直接与其他客户端通信

对等体 （peer-to-peer）体系结构

• （几乎）没有一直运行的服务器
• 任意端系统之间可以进行通信
• 每一个节点既是客户端也是服务器
  • 自扩展性 - 新 peer 节点带来新的服务能力，当然也带来新的服务请求
• 参与的主机间歇性连接且可以改变 IP 地址
  • 难以管理
• eg: 迅雷

c/s 和 p2p 体系结构混合体

Napster

• 文件搜索：集中
  • 主机在中心服务器上注册其资源
  • 主机向中心服务器查询资源位置
• 文件传输 ： p2p
  • 任意 peer 节点之间

即时通信

• 在线检测：集中
  • 当用户在线时，向中心服务器注册其 IP
  • 用户和中心服务器联系，以找到其在线好友的位置
• 两个用户之间聊天：P2P

进程通信

进程：在主机上运行的应用程序

**客户端进程**：发起通信的进程

**服务器进程**：等待连接的进程

• 在同一个主机内，使用 进程间通信机制 通信（操作系统定义）
• 不同主机，通过交换 报文（**Message**）来通信
  • 使用 OS 提供的通信服务
  • 按照 应用协议交换报文
    • 借助传输层提供的服务

注意： p2p 架构的应用也有客户端进程和服务器进程之分

分布式进程通信需要解决的问题

• 问题1 ： 进程标示和寻址问题（服务用户）
• 问题2 ： 传输层 - 应用层提供服务是如何（服务）
  • 位置： 层间页面 的 SAP（TCP/IP ：Socket）
  • 形式：应用程序接口 API （TCP/IP：socket API）
• 问题3：如何使用传输层提供的服务，实现应用进程之间的报文交换，实现应用（用户使用服务）
  • 定义应用层协议：报文格式，解释，时序等
  • 编制程序，使用 OS 提供的 API，调用网络基础设施提供通信服务传报文，实现应用应用时序等

问题1：对进程进行编址

• 进程为了 接收报文，必须有一个 标识，即 SAP （server access point)(发送也需要标识)
  • 主机：唯一的 32 位 IP地址
    • 仅仅有 IP 地址不能唯一标识一个进程：在一台端系统上有很多应用进程在运行
  • 所采用的传输层协议：TCP or UDP
  • 端口号 （Port Numbers）
• 一些知名的端口号的例子
  • HTTP：TCP 80 Mail： TCP25 ftp : TCP 2
• 一个进程：用 IP + Port 标识端节点
• 本质上，一对主机进程之间的通信由2 个端节点构成

问题2：传输层提供的服务-需要穿过层间的信息

• 层间接口必须要携带的信息
  • 要传输的报文（对于本层来说 ： SDU 【service data unit】）
  • 谁传的：对方的应用进程的标示 ： IP + TCP（UDP） 端口
  • 传给谁：对方的应用进程的标示：对方的IP+TCP（UDP） 端口
• 传输层实体（tcp 或者 udp 实体）根据这些信息进行 tcp 报文段（udp 数据报）的封装
  • 源端口号，目标端口号，数据等
  • 将 IP 地址往下交 IP 实体，用于封装 IP 数据报源IP，目标 IP

问题2：传输层提供的服务-层间信息的代表

• 如果 Socket API 每次传输报文，都携带如此多的信息，太繁琐易错，不便于管理
• 用个代号标识 通信的双方或者单方 ： socket
• 就像 OS 打开文件返回的句柄一样
  • 对 句柄的操作，就是对文件的操作
• TCP socket
  • tcp 服务，两个进程之间的通信需要之前要建立连接
    • 两个进程通信会 持续一段时间，通信关系稳定
  • 可以用一个整数表示两个应用实体之间的通信关系，**本地标示**
  • 穿过层间接口的信息量 最小
  • TCP socket ： 源 IP，源端口，目标IP，目标 端口

TCP 之上的套接字（socket）

• 对于使用面向连接服务（tcp）的应用而言，套接字是 4 元组的一个具有 本地意义的标示
  • 4 元组：**源 IP，源端口，目标IP，目标 端口**
  • 唯一的指定了一个会话（两个进程之间的会话关系）
  • 应用使用这个标示 ，与远程的应用进程通信
  • 不必在每一个报文的发送都要指定这 4 元组
  • 就像使用操作系统打开一个文件， OS 返回一个文件句柄一样，以后使用这个文件句柄，而不是使用这个文件的目录名、文件名
  • 简单，便于管理

问题2：传输层提供的服务-层间信息代码

• UDP socket
  • UDP 服务，两个进程之间通信需要之前无需建立连接
    • 每个报文都是独立传输的
    • 前后报文可能给不同的分布式进程
  • 因此，只能用一个整数表示本应用实体的标示
    • 因为这个报文可能传给另外一个分布式进程
  • 穿过层间接口的信息大小最小
  • UDP socket ： 本 IP，本端口
  • 但是传输报文时：必须要提供对方的IP ，port
    • 接收报文时：传输层需要上传对方的IP，port

UDP 之上 的套接字（socket）

• 对于 使用无连接服务（UDP）的应用而言，套接字是 2 元组的 一个具有 本地意义的标示
  • 2 元组： IP，port（源端指定）
  • UDP 套接字指定了应用所在的一个 端节点 （end point）
  • 在发送数据报时，采用创建好的本地套接字（标示 ID），就不必在发送每个报文中指明自己所采用的 ip 和 port
  • 但是在发送报文时，必须要指定对方的 IP 和 udp port (另外一个 段节点)

套接字（socket）

• 进程向 套接字 发送报文 或从 套接字接收报文
• 套接字 < - > 门户
  • 发送 进程将报文推出门户，发送进程依赖于传输层设施在 另外一侧的门将报文交付给接受进程
  • 接受进程从门的另外一侧的门户 收到 报文（依赖于传输层设施）

问题3：如何使用 传输层提供的服务实现应用

• 定义应用层协议：报文格式，解释，时序等
• 编制程序，通过API 调用 网络基础设施提供的通信服务传报文，解析报文，实现应用时序等

应用层协议

• 定义了：运行在不同端系统上的应用 进程 如何相互交换报文
  • 交换的 **报文类型**：请求和应答报文
  • 各种报文类型的 **语法**：报文中的各个字段及其描述
  • 字段的 **语义**：即 字段取值的含义
  • 进程何时、如何发送报文 及 对 报文进行响应的 规则
• 应用协议仅仅是应用的一个组成部分
  • web 应用：HTTP 协议，web 客户端，web 服务器，HTML

公开协议

• 有 RFC 文档定义
• 允许互操作
• 如 HTTP，SMTP

专用（私有）协议

• 协议不公开
• 如 Skype

运输服务

如何描述传输层的服务

• 数据丢失率
  • 有些应用则要求 100% 的可靠数据传输（如 文件）
  • 有些应用（如 音频）能容忍一定比例下的数据丢失
• 吞吐
  • 一些应用（如多媒体）必须需要最小限度的 吞吐，从而使得应用能够有效运转
  • 一些应用能够充分利用可供使用的吞吐（弹性应用）
• 延迟
  • 一些应用出于 有效性考虑，对数据传输有严格的时间限制
    • Internet 电话、交互式游戏
    • 延迟、延迟差
• 安全性
  • 机密性
  • 完整性
  • 可认证性

常见应用对传输服务的要求

Internet 传输层提供的服务

TCP 服务

• 可靠的传输服务
• 流量控制：发送方不会淹没接收方
• 拥塞控制：当网络出现拥堵时，能抑制发送方
• 不能提供的服务：时间保证、最小吞吐量保证和安全
• 面向连接：要求在客户端进程和服务器进程之间建立连接

UDP服务

• 不可靠的数据传输
• 不提供的服务：可靠，流量控制，拥塞控制，带宽保证，建立连接

为什么要有 UDP？

UDP 存在的必要性

• 能够 区分不同的进程，而 IP 服务不能
  • 在 IP 提供的主机到主机 端到端功能的基础上，区分了 主机的应用进程
• **无需建立连接**，省去 了建立连接的时间，适合事务性的应用
• **不做可靠性的工作**。例如 检错重发，适合那些对实时性要求比较高而对正确性要求不高的应用
  • 因为为了实现可靠性（正确性、保序等），必须付出时间代价（检错重发）
• 没有了 拥塞控制和流量控制，应用能够按照设定的速度发送数据
  • 而在 tcp 上面的应用，应用发送数据的速度和主机向网络发送的实际速度是不一致的，因为有流量限制和拥塞限制

Internet 应用及其应用层协议和传输协议

安全 TCP

TCP& UDP

• 都没有加密
• 明文通过互联网传输，甚至密码

SSL

• 在 TCP 上实现，提供加密的 TCp 连接
• 私密性
• 数据完整性
• 端到端的鉴别

SSL 在 应用层

• 应用采用 SSL 库，SSL库采用 TCP 通信

SSL socket api

• 应用通过 API 将 明文交给socket，SSL 将其加密在互联网上传输

Web and HTTP

一些术语

• Web 页：有一些对象组成

• 对象可以是 HTML 文件、JPEG 图像、Java 小程序、声音剪辑文件等

• Web 页 含有一个 基本的HTML 文件，该基本 HTML 文件又包含若干对象的引用（链接）

• 通过 URL 对每个对象进行引用

  • 访问协议，用户名、口令字、端口等

• URL 格式

  

HTTP 概况

HTTP：超文本传输协议

• Web 的应用层协议
• 客户/服务器模式
  • 客户：请求、接收和显示 Web 对象的浏览器
  • 服务器：对请求进行响应，发送对象的 web 服务器

使用 TCP

• 客户发起一个与服务器的 TCP 连接（建立套接字），端口号为 80
• 服务器接收客户的 TCP 连接
• 在 浏览器（HTTP 客户端 ）与 Web 服务器（HTTP 服务器 Sever） 交换 HTTP 报文 （应用层协议报文
• TCP 连接关闭

HTTP 是无状态的

• 服务器并不维护关于客户的任何信息

维护状态的协议很复杂

• 必须维护历史信息（状态）
• 如果 服务器/客户端 死机，他们的 状态信息可能不一致，二者的信息必须是一致
• 无状态的服务器能够支持更多的客户端

HTTP 连接

非持久 HTTP

• 最多只有一个对象在 TCP 连接上发送
• 下载多个对象需要多个 TCP 连接
• HTTP /1.0 使用非持久连接

持久 HTTP

• 多个对象可以在一个（在客户端和服务器之间的） TCP 连接上传输
• HTTP /1.1 默认使用 持久连接

非持久 HTTP 连接

响应时间模型

往返时间 RTT（Round-trip time）

一个小的分组从客户端服务器，在回到客户端的时间（传输时间忽略）

响应时间

• 一个 RTT 用来发起 TCP 连接
• 一个 RTT 用来 HTTP 请求并等待 HTTP 响应
• 文件传输时间

共 2RTT + 传输时间

非持久 HTTP 的 缺点

• 每个对象要两个 RTT
• 操作系统必须为每个 tcp 连接分配资源
• 但浏览器通常打开 并行 tcp 连接，以获取引用对象

持久 http

• 服务器在发送响应后，仍保持 tcp 连接
• 在相同客户端和服务器之间连续请求和响应报文通过相同的 连接继续进行传送
• 客户端在遇到一个 引用的时候，就可以尽快发送该对象的请求

非流水方式的持久 HTTP

• 客户端只能在收到前一个响应后 才能发出新的请求
• 每个引用对象花费一个 RTT

流水方式的 持久HTTP

• HTTP /1.1 的默认模式
• 客户端在遇到一个引用对象就立即产生一个 请求
• 所有 引用（小）对象只花费一个 RTT 是可能的

HTTP 请求报文

• 两种类型的 HTTP 报文： 请求、响应
• HTTP 请求 报文
  • ASCII （人能阅读）
  • 

通用格式

提交表单输入

POST 方式

• 网页通常 包括表单输入
• 包含在实体主体（entity body） 中的 输入提交到 服务器

URL方式

• 方法 ： GET
• 输入通过 请求行的 URL 字段上载

方法类型

HTTP/1.0

• GET
• POST
• HEAD
  • 要求 服务器在响应报文中不包含请求对象 -> 故障跟踪

HTTP/1.1

• GET、POST、HEAD
• PUT
  • 将实体主体的文件上载到URL字段规定的路径
• DELETE
  • 删除 URL 字段规定的文件

HTTP 响应报文

HTTP 状态响应码

位于服务器-> 客户端的响应报文中的首行

一些状态码的例子

用户 - 服务器状态 ： Cookies

大多数主要的门户网站使用 cookie

四个组成部分

1. 在 HTTP 响应报文中有一个 cookie 的 首部行
2. 在 http 请求报文含有一个 cookie的 首部行
3. 在用户端系统中保留有一个 cookie文件，由 用户的浏览器管理
4. 在 web 站点 有一个后端数据库

维护状态

cookie 能带来什么

• 用户验证
• 购物车
• 推荐
• 用户状态

如何维护状态

• 协议端节点： 在多个事务上，发送端和接收端维持状态
• cookies ： http 报文携带状态信息

Cookies 与 隐私

• Cookies 允许站点知道许多关于用户的信息
• 可能将它知道的东西卖给第三方
• 使用重定向和 cookie 的搜索引擎还能知道用户更多的信息
  • 如 通过 某个用户的行为，了解其个人浏览方式的大致模式
• 广告公司从站点获得信息

Web 缓存

目标： 不访问 原始服务器，就满足客户的请求

• 用户设置浏览器： 通过缓存访问 web
• 浏览器将所有的 HTTP 请求发送给 缓存
  • 在缓存中的 对象： 缓存直接返回对象
  • 不在缓存中的对象： 请求原始服务器，然后再将对象返回给客户端

• 缓存既是客户端 又是 服务器
• 通常 缓存是由 ISP 安装

为什么要使用 web 缓存

• 降低 客户端的请求响应时间
• 可以大大减少一个机构内部网络与 Internet 接入链路上的 流量
• 互联网大量采用了 缓存，可以使较弱的 ICP 也可以提供内容

缓存实例

更快的接入链路

安装本地缓存

条件 GET 方法

• 目标：如果 缓存器中的对象拷贝是最新的 ，就不要发送 对象
• 缓存器： 在 http 请求中指定 拷贝的 日期
• 服务器： 如果缓存拷贝陈旧，则响应报文没包含对象

FTP

ftp 文件传输协议

• 向远程主机上传输文件或从远程主机上接收文件
• c / s 模式
  • 客户端 ： 发起传输的一方
  • 服务器 ： 远程主机
• ftp : RFC 959
• ftp 服务器 ： 端口号为 21

FTP: 控制连接与数据连接分开

• FTP客户端与FTP服务器通过端口21联系，并使用TCP为传输协议
• 客户端通过控制连接获得身份确认
• 客户端通过控制连接发送命令浏览远程目录
• 收到一个文件传输命令时，服务器打开一个到客户端的数据连接
• 一个文件传输完成后，服务器关闭连接

• 服务器 打开第二个 TCP 数据连接用来传输另一个文件
• 控制连接： 带外（”out of band”） 传送
• ftp 服务器维护用户的状态信息： 当前路径、用户账户与控制连接对应

FTP 命令、响应

Email

三个主要组成部分

• 用户代理
• 邮件服务器
• 简单邮件传输协议： SMTP

用户代理

• 又名 “邮件阅读器”
• 撰写、编辑和阅读邮件
• 如 Outlook
• 输出和输入邮件保存在服务器上

邮件服务器

• 邮箱 中管理和维护发送三给用户的邮件
• 输出 报文队列 保持发送邮件报文
• 邮件服务器之间的 SMTP 协议 ： 发送 email 报文
  • 客户： 发送方邮件服务器
  • 服务器：接收端邮件服务器

SMTP [RFC 2821]

• 使用 TCP 在客户端和服务器之间传送报文，端口号为 25
• 直接传输： 从发送方服务器到接收方服务器
• 传输的三个手段
  • 握手
  • 传输报文
  • 关闭
• 命令/响应交互
  • 命令： ASCII 文本
  • 响应：状态码和状态信息
• 报文必须为 7 位 ASCII 码

SMTP 总结

• SMTP 使用 持久连接
• SMTP 要求报文（首部和主体）为7 位 ASCII 编码
• SMTP 服务器使用 CRLF 决定报文的尾部

HTTP 比较

• HTTP : 拉（pull）
• SMTP：推（push）
• 二者都是 ASCII 形式的命令 / 响应交互、状态码
• HTTP：每个对象封装在各自的响应报文中
• SMTP：多个对象封装在一个报文中

邮件报文格式

SMTP ： 交换 email 报文的协议

RFC 822 ： 文本报文的标准

• 首部行
  • To
  • From
  • Subject
• 主体
  • 报文：只能是ASCII 码字符

多媒体扩展

• MIME： 多媒体邮件扩展
• 在报文首部用额外的行申明 MIME 的 内容类型

邮件访问协议

• SMTP ： 传送到接收方的邮件服务器
• 邮件访问协议： 从服务器访问邮件
  • POP：邮局访问协议（Post Office Protocol）[RFC 1939]
    • 用户身份确认（代理 <–> 服务器） 并下载
  • IMAP ： Internet 邮件访问协议 （Internet Mail Access Protocol ）[RFC 1730]
    • 更多特性
    • 在服务器上处理存储的报文
  • HTTP ： Hotmail，Yahoo！Mail 等
    • 方便

POP3 协议

POP3 与 IMAP

DNS

DNS 的必要性

• IP地址标识主机、路由器
• 但IP地址 不好记忆，不便人类使用（没有意义）
• 人类一般倾向使用一些有意义的字符串来标识 Internet 上 的设备
• 存在着 “字符串” - IP 地址的转换的必要性
• 人类用户提供要访问机器的 字符串 名称
• 由 DNS 负责转换成为 二进制的网络地址

DNS 的历史

DNS 总体思路和目标

总体思路

• 分层的 、基于域的 命名机制
• 若干分布式的数据库完成名字到 IP 地址的 转换
• 运行在 UDP 之上的 端口号为 53 的 应用程序
• 核心的 Internet 功能，但以应用层协议实现
  • 在网络边缘处理复杂性

目标

• 实现 主机名到 IP 地址的 转换
• 其他目标
  • 主机别名到 规范名字的 转换
  • 邮件服务器 别名到邮件服务器正规名字的转换
  • 负载均衡: Load Distribution

DNS 需要解决的问题

• 问题1 ： 如何命名设备
  • 用 有意义的字符串：好记，便于人类使用
  • 解决一个平面命名的重名问题：层次化命名
• 问题2 ：如何完成名字到IP 地址的 转换
  • 分布式的 数据库维护和响应名字查询
• 问题3 ： 如何维护：增加或者删除一个域，需要在域名系统中做哪些工作

相关的问题详细，在这个章节中的知识点都有穿插

问题1 ： DNS 命名空间

• DNS 域名结构
  • 一个层面命名设备会有很多重名
  • DNS 采用层次树状结构的命名方法
  • Internet 根 被划为几百个顶级域名
    • 通用的 （generic）
      • .com
      • .edu
      • .gov
      • .mil
      • .org
      • .firm
    • 国家的
      • .cn
      • .us
      • .jp
  • 每个（子）域 下面可划分为若干子域（subdomains）
  • 树叶是主机

DNS：根名字服务器

问题2 ： 解析问题 - 名字服务器（Name Sever）

• 一个名字服务器的问题
  • 可靠性问题：单点故障
  • 扩展性问题：通信容量
  • 维护问题：远距离的集中式数据库
• 区域（zone)
  • 区域的划分由区域管理者自己决定
  • 将 DNS 名字空间划分成 互不相交 的区域，每个区域都是树一部分
  • 名字服务器
    • 每个区域都有一个名字服务器：维护着他所管辖的权威信息
    • 名字服务器允许被放置在区域之外，以保障可靠性

问题 3 ： 维护问题：新增一个域

• 在上级域的名字服务器上增加两条记录，指向这个新增的子域的域名和域名服务器的地址
• 在新增子域的名字服务器上运行名字服务器，负责本域的名字解析： 名字 -> IP 地址

名字空间被划分成若干区域：Zone

权威DNS 服务器： 组织机构的 DNS 服务器，提供组织机构服务器可访问的主机和 IP 之间的 映射

组织机构可以选择实现自己维护或由某个服务提供商来维护

TLD 服务器

顶级域（TLD）服务器： 负责顶级域名 和所有国家级的顶级域名

区域名字服务器维护资源记录

DNS记录

DNS： 保存资源记录 （RR） 的分布式数据库

DNS 大致工作流程

• 应用调用解析器（resolver）

• 解析器 作为客户向 Name Sever 发出查询报文（封装在 UDP 段中）

• Name Sever 返回响应报文

  

本地名字服务器（Local Name Server)

• 并不严格属于层级结构
• 每个 ISP 都有一个 本地的 DNS 服务器
  • 也称 默认名字服务器
• 当一个主机发起一个 DNS 查询时，查询被送到其当地 DNS 服务器
  • 起着代理的作用，将查询转发到层次结构中

名字服务器（Name Sever）

• 名字解析过程
  • 目标名字在 Local Name Sever 中
    • 情况 1 ： 查询的名字在该区域内部
    • 情况 2 ： 缓存

当与本地名字服务器不能解析名字时，联系根名字服务器 顺着根- TLD 一直找到 权威名字服务器

递归查询

• 名字解析负担都放在当前联络的名字服务器上
• 问题：根服务器负担太重
• 解决：迭代查询（iterated queries）

迭代查询

• 主机 cis.poly.edu 想知道 主机 gaia.cs.unass.edu 的 IP 地址
• 根（及各级域名）服务器返回的不是查询结果，而是下一个 NS 地址
• 最后由权威名字服务器给出解析结果
• 当前联络的服务给出可以联系的服务器的名字
• “我不知道这个名字，但可以向这个服务器请求”

DNS 协议、报文

DNS 协议： 查询和响应报文的 报文格式相同

提高性能：缓存

• 一旦名字服务器学到了一个映射，就将该映射 缓存起来
• 根服务器通常都在本地服务器中缓存着
  • 使根服务器不用被经常访问
• 目的 : 提高效率
• 可能存在的问题：如果情况变化，缓存结果和权威资源记录可能不一样
• 解决方案：TTL （默认 两天）

攻击 DNS

DDoS 攻击

• 对 根服务器进行流量轰炸：发送大量 ping
  • 没有成功
  • 原因1 ：根目录服务器配置了流量过滤器，防火墙
  • 原因2：Local DBS 服务器缓存了 TLD服务器的 IP 地址，因此无需查询 根服务器
• 向 TLD 服务器流量轰炸攻击 ： 发送大量查询
  • 可能更危险
  • 效果一般，大部分 DNS 缓存 了 TLD

重定向攻击

• 中间人攻击
  • 截获查询，伪造回答，从而攻击某个（DNS 回答指定的IP）站点
• DNS 中毒
  • 发送伪造的回答给 DNS 服务器，希望他能缓存这个虚假的结果
• 技术上比较困难：分布式截获和伪造

利用 DNS基础设施进行 DDoS

• 伪造某个 IP 进行查询，攻击这个 目标 IP
• 查询放大，响应报文比查询报文大
• 效果有限

DNS：名字空间

• 域名（Domain name)
  • 从本域往上，直到树根
  • 中间使用 . 间隔不同的级别
  • 域的域名：可以用于表示一个域
  • 主机的域名：一个域上的一个主机
• 域名的管理
  • 一个域管理其下的 子域
  • 创建一个新的域，必须征得它所属域的同意
• 域与物理网络无关
  • 域遵从组织界限，而不是物理网络
    • 一个域的主机可以不在一个网络
    • 一个网络的主机不一定在一个域
  • 域的划分是逻辑的，而不是物理的

P2P 应用

纯 P2P 架构

• 没有 （或极少）一直运行的服务器
• 任意端系统都可以直接通信
• 利用 peer 的服务能力
• Peer 节点间歇上网，每次 IP地址都有可能变化

文件分发

问题 ：从一台服务器 分发文件（大小 F) 到 N个 peer 需要多少时间

• peer 节点上下载能力是有限的资源

文件分发时间： C/S 模式

• 服务传输：都是由服务器发送给 peer，服务器必须顺序传输（上载）N个文件拷贝：
  • 发送一个 copy: F/us
  • 发送 N 个 copy ：NF / us
• 客户端：每个客户端必须下载一个文件拷贝
  • d(min) = 客户端最小的下载速率
  • 下载带宽最小的客户端下载的时间 ： F/d(min)

文件分发时间 ： P2P 模式

• 服务器传输：最少需要上载一份拷贝
  • 发送一个拷贝的时间 ：F/u(s)
• 客户端：每个客户端必须下载一个拷贝
  • 最小下载带宽客户单耗时： F / d(min)
• 客户端：所有客户端总体总体下载量 NF
  • 最大的上载带宽是
  • 除了服务器可以上载，其他所有的 peer 节点都可以上载

P2P 文件分发：BitTorrent

• 文件被分为一个个块 256KB
• 网络中的这些 peers 发送接收文件块，相互服务

• Peer 加入 torrent

  

  • 一开始没有 块，但是会通过其他节点积累文件块
  • 向跟踪服务器注册，获得 peer 节点列表，和部分 peer 节点构成邻居关系

• 当 peer 开始下载时，该 peer可以同时向其他节点提供 上载服务

• Peer 可能会变换用户交换块的 peer 节点

• 扰动 churn： peer节点可能会上线或下线

• 一旦一个 peer 拥有整个文件，他会（自私的）离开或者保留（利他主义）在 torrent

torrent： 请求, 发送文件块

请求块

• 在任何给定时间，不同 peer 节点拥有一个文件块的子集
• 周期性的，Alice 节点向邻居询问他们拥有哪些块信息
• Alice向 peer 节点请求它希望的块，稀缺的块

发送块： 一报还一报 tit-for-tat

• alice 向4个 peer 发送块，这些块向他自己提供最大带宽的服务
  • 其他 peer 被 Alice 阻塞（将不会从 Alice 处获得服务）
  • 每 10 秒重新评估一次：前 4 位
• 每个 30 秒：随机选择其他的 peer 节点，向这个节点发送块
  • “优化疏通” 这个节点
  • 新选择的 节点可以加入这个 top4

更高的上载速率： 发现更好的交易伙伴，获得更快的文件传输速率

P2P 文件共享

例子

所有的对等方都是服务器 = 可扩展性好

两大问题

• 如何定位所需资源
• 如何处理对等方的加入与离开

可能的方案

• 集中
• 分散
• 半分散

P2P：集中式目录

最初的 “Napster” 设计

1. 当 peer 连接时，它告知中心服务器
   • IP 地址
   • 内容
2. Alice 查询 资源
3. Alice 从 Bob出 请求文件

存在的问题

• 单点故障
• 性能瓶颈
• 侵犯版权

文件传输是分散的，而定位内容则是高度集中的

查询泛洪： Gnutella

• 全分布式
  • 没有中心服务器
• 开放文件共享协议
• 许多 Gnutella 客户端实现了 Gnutella 协议
  • 类似 HTTP 有许多 浏览器

覆盖网络： 图

• 如果 x 和 y 之间有一个 tcp 连接，则二者之间存在一条边
• 所有活动的对等方和边就是覆盖网络
• 边并不是物理链路
• 给定一个对等方，通常所连接的节点少于 10 个

Gnutella ：协议

• 在 已有的 TCP 连接上发送查询报文
• 对等方转发查询报文
• 以反方向返回查询命中报文

Gnutella ：对等方加入

利用不匀称性： KaZaA

• 每个对等方要么是一个组长，要么隶属于一个组长
  • 对等方与其组长之间有 TCP 连接
  • 组长对之间有 TCP 连接
• 组长跟踪其所有的孩子的内容
• 组长与其他组长取得联系
  • 转发查询到其他组长
  • 获取其他组长的数据拷贝

KaZaA : 查询

• 每个文件有一个散列标识码和一个描述符
• 客户端向其组长发送关键字查询
• 组长用匹配进行响应
  • 对每个匹配：元数据、散列标识码和 IP 地址
• 如果组长将查询转发给其他组长，其他组长以匹配进行响应
• 客户端选择要下载的 文件
  • 向拥有文件的对等方发送一个 带散列标识码的 HTTP 请求

KaZaA小技巧

• 请求排队
  • 限制并行上载的数量
  • 确保每个被传输的文件从上载节点接收一定量的带宽
• 激励优先权
  • 鼓励用户上载文件
  • 加强系统的扩展性
• 并行下载
  • 从多个对等方下载同一文件的不同部分
    • HTTP 的字节范围首部
    • 更快的检索一个文件

Distribution Hash Table（DHT）

• 哈希表
• DHT方案
• 环形 DHT 以及覆盖网络
• Peer 波动

CDN

视频流化服务和 CDN： 上下文

存储视频的 流化服务

简单场景

多媒体流化服务

• DASH ： Dynamic Adaptive Streaming over HTTP
• 服务器
  • 将视频文件分割成多个小块
  • 每个块独立存储，编码于不同码率（8 - 10 种）
  • 告示文件（manifest file) ： 提供不同块的 URL
• 客户端
  • 先获取告示文件
  • 周期性的测量服务器到客户端的带宽
  • 查询告示文件，在一个时刻请求一个块，HTTP 头部指定字节范围
    • 如果带宽足够，选择最大码率的视频块
    • 会话中的不同时刻，可以切换为不同的编码块（取决于当时的可用带宽）

流式多媒体技术：DASH

• “智能” 客户端：客户端自适应决定
  • 什么时候去请求块（不至于缓存挨饿，或者溢出）
  • 请求 什么编码速率的视频块（当带宽足够时，选择高质量的）
  • 哪里去请求块（可以向离自己近的服务器发送 URL，或者向高可用带宽的服务器请求）

Content Distribution Networks

• 挑战：服务器如何通过网络向上百万用户同时流化视频内容（上百万视频内容）
• 选择1：单个的、大的超级服务中心
  • 服务器 到客户端 路径上跳数越多瓶颈链路的带宽小导致停顿
  • “二八规律” 决定了网络同时充斥着同一个视频的多个拷贝
  • 单点故障点，性能瓶颈
  • 周边网络的拥塞
• 选择2： 通过 **CDN**，全网部署缓存节点，存储服务内容，就近为用户提供服务，提高用户体验
  • enter deep： 将 cdn 服务器深入到许多接入网
    • 更接近用户，数量多，离用户近，管理困难
  • bring home : 部署在少数（10 个左右）关键位置，如将服务器簇安装在 POP 附近
    • 采用 租用线路将服务器簇连接起来
    • LimeLight
• CDN： 在 CDN 节点中存储内容的多个拷贝
• 用户在CDN 中请求内容
  • 重定向到最近的拷贝，请求内容
  • 如果网络路径拥塞，可能选择不同的拷贝

• OTT 挑战：在拥塞的网络上复制内容

  • 从哪个CDN上 获取内容
  • 用户在网络拥塞时的行为
  • 在哪些cdn 节点存储什么内容
  

CDN： “简单” 内容访问场景

Socket 编程

应用进程使用 传输层提供的服务才能够交换报文，实现应用协议，实现应用

TCP/IP : 应用进程使用 Socket API 访问传输服务

地点：界面上的 SAP（Socket） 方式： Socket API

目标： 学习如何构建能借助 socket 进行通信的 c/s 应用程序

socket： 分布式应用进程之间的门，传输层协议提供的端到端服务接口

两种传输层服务的 socket 类型

• TCP： 可靠的、字节流的服务
• **UDP: **不可靠（数据UDP 数据报）服务

TCP Socket 编程

套接字：应用进程与端到端传输协议（TCP或 UDP）之间的门户

TCP服务： 从一个进程向另外一个进程可靠地传输 字节流

服务器首先运行，等待连接建立

1、服务器进程必须先处于运行状态

• **创建 ** 欢迎socket （serverSocket)
• 和本地端口 绑定
• 在 欢迎 socket 上阻塞式 等待接收 用户的连接

客户端主动和服务器建立连接

2、创建客户端 本地套接字（隐式捆绑到 本地 port)

• 指定服务器进程的 IP地址 和端口号，与服务器进程 连接

3、当与客户端连接请求到时

• 服务器 接收 来自 用户端的请求，接触阻塞式等待，返回一个 新的 socket（与欢迎 socket 不同），与客户端通信

  • 允许服务器与多个客户端通信
  • 使用 源 IP 和 源端口 来区分不同的 客户端

  从应用程序的角度

  TCP 在客户端与服务器进程之间提供了可靠的、字节流（管道）服务

4、连接 API 调用有效时，客户端与服务器建立了 TCP 连接

C/S 模式的应用样例

1. 客户端从标准输入装置读取一行字符，发送给服务器
2. 服务器从socket 读取 字符
3. 服务器将字符 转换成 大写 然后返回给客户端
4. 客户端 从socket 中 读取一行字符，然后打印出来

socket 交互 ： tcp

数据结构 sockaddr_in

Ip  地址和 port 捆绑关系的数据结构（标识进程的端节点）

数据结构 hostent

域名和IP地址 的数据结构

作为 调用域名解析函数时的参数

返回后，将 IP地址拷贝到 sockaddr_in 的 IP 地址部分

C 客户端（TCP）

C 服务器 （TCP）

UDP Socket 编程

UDP：在客户端与服务器之间没有连接

• 没有握手
• 发送端在每一个报文中明确地 指定目标的 IP 地址和端口号
• 服务器 必须从 收到的分组中 提取出发送端的 IP 地址和 端口号

从 进程角度看 UDP 服务

UDP 为 客户端和服务器端提供  不可靠的 字节组的传送服务

UDP： 传送的数据可能 乱序，也可能丢失

c/s socket 交互： udp

小结

• 应用程序体系结构
  • 客户-服务器
  • P2P
  • 混合
• 应用程序需要的服务品质描述
  • 可靠性
  • 带宽
  • 延时
  • 安全
• Internet 传输层服务模式
  • 可靠的、面向连接的服务： TCP
  • 不可靠的数据报：UDP
• 流行的应用层协议
  • HTTP
  • FTP
  • SMTP 、POP、IMAP
  • DNS
• Socket 编程

更重要的：学习协议的知识

• 应用层协议报文类型：请求/响应报文：
  • 客户端请求信息或服务
  • 服务器以数据、状态码进行响应
• 报文格式
  • 首部：关于数据信息的字段
  • 数据：被交换的信息
• 控制报文 vs 数据报文
  • 带内 、 带外
• 集中式 vs 分布式
• 无状态 vs 维护状态
• 可靠的 vs 不可靠的报文传输
• 在网络边缘处理复杂性

一个协议定义了在两个或多个通信实体之间交换报文的和次序，以及就一条报文传输和接收或其他事情采取的动作

传输层

运输层位于 应用层和网络层之间，是分层的网络体系结构的重要部分。 该层为 运行在不同主机上的应用进程提供直接的 通信服务起着至关重要的作用。

“关注运输是什么，他如何工作，为什么这么做”

目标：

• 理解传输层的工作原理
• 多路复用/解复用
• 可靠数据传输
• 流量控制
• 拥塞控制
• 学习 Internet 的传输层协议
  • UDP ：无连接传输
  • TCP ：面向连接的 可靠性传输
  • TCP 的拥塞控制

概述和传输层服务

运输层协议为 运行在 不同主机上的应用进程 之间 提供了 逻辑通信（logic communication） 功能。

传输服务和协议

• 运输层协议为 运行在 不同主机上的应用进程 之间 提供了 逻辑通信（logic communication） 功能。
• 传输协议 运行在端系统
  • 发送方： 将应用层的报文 分成 报文段，然后传递给网络层
  • 接收方：将报文段重组成报文。然后传递给应用层
• 有多个传输层协议可供选择
  • Internet ： TCP 和 UDP

传输层和网络层之间的关系

前面讲过，在 协议栈中，运输层刚好位于网络层之上。 网络层提供了主机之间的 逻辑通信，而运输层为 运行在不同主机上的进程之间提供了 逻辑通信

• 网络层服务：主机之间的 逻辑通信
• 运输层服务：进程之间的逻辑通信
  • 依赖于 网络层的服务
    • 延时、带宽
  • 并对网络层的服务进行增强
    • 数据丢失、顺序混乱、加密

**有些服务是可以被加强的：不可靠 - > 可靠；  安全 **

但有些服务是不可以被加强的：带宽、延迟

运输协议能够提供的服务常常受制于底层网络层协议的服务模型。如果网络层协议无法为主机之间发送的运输层报文段提供时延和带宽保证的话，运输层协议也就无法为进程之间发送的应用程序报文提供时延和带宽保证

然而，即使底层网络协议不能在网络层提供相应的服务，运输层协议也能提供某些服务。例如，即使底层网络协议是不可靠的，也就是说网络层协议会使分组丢失、墓改和允余，运输协议也能为应用程序提供可靠的数据传输服务。另一个例子是,即使网络层不能保证运输层报文段的机密性，运输协议也能使用加密来确保应用程序报文不被入侵者读取。

Internet 传输层协议

在对UDP和TCP进行简要介绍之前，简单介绍一下因特网的网络层是有用的。因特网网络层协议有一个名字叫IP,即网际协议。IP为主机之间提供了逻辑通信。IP的服务模型是尽力而为交付服务（best-effort delivery service)。这意味着IP尽它“最大的努力”在通信的主机之间交付报文段，但它并不做任何确保。特别是，它不确保报文段的交付，不保证报文段的按序交付，不保证报文段中数据的完整性。由于这些原因，IP被称为不可靠服务（unreliable service)。在此还要指出的是，每台主机至少有一个网络层地址，即所谓的IP地址。在这一章中，只需要记住每台主机都有一个 IP 地址

• 可靠的、保序的传输 ：TCP
  • 多路复用、解复用
  • 拥塞控制
  • 流量控制
  • 建立连接
• 不可靠的、不保序的传输：UDP
  • 多路复用、解复用
  • 没有尽力而为的 IP 服务添加更多的其他额外服务
• 都不提供的服务
  • 延时保证
  • 带宽保证

在对 IP 有了初步的了解之后。总结一下 TCP 和 UDP 所提供的 服务模型。 UDP 和 TCP 最基本的责任是 将两个端系统间 IP 的交付服务扩展到运行在端系统上的两个进程之间的交互服务。将主机间交付扩展到进程之间的交付被称为 运输层的多路复用 与 多路分解

多路复用与解复用

在本节中，我们讨论运输层的多路复用与多路分解，也就是将由网络层提供的主机到主机交付服务延伸到为运行在主机上的应用程序提供进程到进程的交付服务。为了使讨论具体，我们将在因特网环境中讨论这种基本的运输层服务。然而，需要强调的是，多路复用与多路分解服务是所有计算机网络都需要的。

在 socket 中，一个进程（作为网络应用的一部分）有一个或多个套接字(socket),它相当于从网络向进程传递数据和从进程向网络传递数据的门户。因此，如图3-2所示，在接收主机中的运输层实际上并没有直接将数据交付给进程，而是将数据交给了一个中间的套接字。由于在任一时刻，在接收主机上可能有不止一个套接字，所以每个套接字都有唯一的标识符。标识符的格式取决于它是UDP还是TCP套接字

一个 进程有 1 or 多个 socket

每个 socket都有唯一标识符

多路解复用

多路解复用工作原理

• 解复用作用：tcp 或者 udp 实体采用那些信息，将报文段的数据部分交给正确的 socket。从而交给正确的进程
• 主机收到 IP 数据报
  • 每个数据报有 源IP地址 和 目标地址
  • 每个数据源承载一个传输层报文段
  • 每个报文段有一个原端口号和 目标端口号
    • 端口号的 数量为 0 ~ 65535 0 ~ 1023 为周知端口号
• 主机联合使用 IP地址 和 端口号 将报文段 发送给适合的 socket

UDP 和 TCP 不同

现在应该清楚运输层是怎样能够实现分解服务的了：在主机上的每个套接字能够分一个端口号，当报文段到达主机时，运输层检查报文段中的目的端口号，并将其定向到相应的套接字。然后报文段中的数据通过套接字进入其所连接的进程。如我们将看到的那样，UDP大体上是这样做的。然而，也将如我们所见，TCP中的多路复用与多路分解更为复杂。

无连接的多路解复用

• 创建套接字

  

  serverSocket 和 sad 指定的端口号 捆绑

  

  没有 bind ，clientSocket 和 os 为之分配的某个端口号捆绑（客户端使用什么端口号无所谓，客户端主动找服务器）

• 在 接收端，udp 套接字用二元组 标识（目标IP 地址和 目标端口号）

• 当主机收到 UDP 报文段

  • 检查报文段的目标端口号
  • 用该 端口号将报文段定位给 socket

• 如果两个不同源 IP 地址/ 源端口号 的数据报，但是 有相同的目标IP 地址和目标端口号，则被定位到相同的 socket

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

为了 理解 TCP 的多路分解，我们必须更加仔细地研究 TCP socket 和 TCP 连接创建。TCP socket 和 UDP socket 之间一个细微的差别是 TCP socket 是由一个四元组来标识的

• TCP socket：四元组本地标识
  • 源IP 地址
  • 源 端口号
  • 目标 IP 地址
  • 目标 端口号
• 解复用：接收主机用这四个值来将数据报定位到合适 的 socket
• 服务器能在一个 TCP 端口上同时支持多个 tcp socket
  • 每个 socket 由其四元组标识
• web 服务器对每个连接客户端都有不同的socket
  • 非持久对每个请求有不同的 socket

服务器主机可以支持很多并行的TCP套接字，每个套接字与一个进程相联系，并由其四元组来标识每个套接字。当一个TCP报文段到达主机时，所有4个字段（源IP地址，源端口，目的IP地址，目的端口）被用来将报文段定向（分解）到相应的套接字。

面向连接的多路复用： 多线程 web server

• 一个进程下面可能有多个线程： 由多个线程分别为客户提供服务
• 在这个场景下，还是根据 4 元组决定将报文段内容 定向 到 同一个进程下的不同线程
• 解复用到不同线程

无连接传输：UDP

由 [RFC768] 定义的 UDP 只是做了运输协议能够做的最少工作。除了复用/分解功能及少量的差错检测外，它几乎没有对IP增加别的东西。实际上，如果应用程序开发人员选择UDP而不是TCP,则该应用程序差不多就是直接与IP打交道。UDP从应用进程得到数据，附加上用于多路复用/分解服务的源和目的端口号字段，以及两个其他的小字段然后将形成的报文段交给网络层。网络层将该运输层报文段封装到一个IP数据报中，然后尽力而为地尝试将此报文段交付给接收主机。如果该报文段到达接收主机，UDP使用目的端口号将报文段中的数据交付给正确的应用进程。值得注意的是，使用UDP时，在发送报文段之前，发送方和接收方的运输层实体之间没有握手。正因为如此，UDP被称为是无连接的。

• 尽力而为 服务，报文可能
  • 丢失
  • 乱序
• 无连接
  • UDP 发送端与接收端之间没有握手
  • 每个UDP 报文段都被独立地 处理

• UDP 被用于
  • 流媒体（丢失不敏感，速率敏感、应用可控制传输速率）
  • DNS
  • SNMP
• 在 UDP 上可行可靠传输
  • 在应用层增加 可靠性
  • 应用特定的差错恢复

UDP： 用户数据报协议

为什么要有 UDP

• 不建立连接（会增加延时）
• 简单：在发送端和接收端没有连接状态
• 报文段的头部很小（开销小）
• 无拥塞控制和流量控制 ： UDP 可以尽可能快 的发送报文段
  • 应用 -> 传输的速率 = 主机 -> 网络的速率

UDP 校验和

你可能想知道为什么UDP首先提供了检验和，就像许多链路层协议（包括流行的以太网协议）也提供了差错检测那样。其原因是不能保证源和目的之间的所有链路都提供差错检测；这就是说，也许这些链路中的一条可能使用没有差错检测的协议。此外，即使报文段经链路正确地传输，当报文段存储在某台路由器的内存中时，也可能引入比特差错。在既无法确保逐链路的可靠性，又无法确保内存中的差错检测的情况下，如果端到端数据传输服务要提供差错检测，UDP就必须在端到端基础上在运输层提供差错检测。这是一个在系统设计中被称颂的 端到端原则 （end-end principle)的例子[Saltzer1984],该原则表述为因为某种功能（在此时为差错检测）必须基于端到端实现：“与在较高级别提供这些功能的代价相比，在较低级别上设置的功能可能是沉余的或几乎没有价值的。”

目的：检测在被传输报文段中的差错（比如 比特反转）

发送方

• 将报文段的内容视为 16 比特的 整数
• 校验和：报文段的加法和（ 1 的 补运算）
• 发送方将校验和放在UDP 的校验和字段

接收方

• 计算得到的报文段的 校验和
• 检查 计算出的 校验和 与 校验和字段的内容是否相等
  • 不相等 – 检测到 差错
  • 相等 – 没有检测到 差错，但也许还是有差错
    • 残存错误

因为 假定 IP 是可以 运行 在 任何第二层协议之上的，运输层 提供 差错检测作为一种保险措施时非常有用的。虽然 UDP 提供 差错检测，但他对 差错恢复无能为力。UDP 的某种 实现 只是丢弃了 受损的报文段；其他 实现则是将受损的 报文段交给应用程序并且 给出警告

可靠数据传输(rdt)的原理

图3-8图示说明了我们学习可靠数据传输的框架。为上层实体提供的服务抽象是：数据可以通过一条可靠的信道进行传输。借助于可靠信道，传输数据比特就不会受到损坏(由0变为1,或者相反）或丢失，而且所有数据都是按照其发送顺序进行交付。这恰好就是TCP向调用它的因特网应用所提供的服务模型。

• rdt 在 应用层、运输层和数据链路层都很重要
• 是 网络 Top 10 问题之一

• 信道的不可靠性决定了可靠数据传输协议（rdt) 的复杂性

可靠数据传输：问题描述

我们将：

• 渐增式开发可靠数据传输协议 的发送方和接收方
• 只考虑单向数据传输
  • 但控制信息是双向流动的
• 双向的 数据传输问题实际上是两个 单向数据传输问题的综合
• 使用 有限状态机（FSM） 来描述发送方和接收方

Rdt 1.0 ：在可靠信道上的可靠数据传输

• 下层的信道是完全可靠的
  • 没有比特出错
  • 没有分组丢失
• 发送方和接收方的 FSM
  • 发送方将数据发送到下层信道
  • 接收方从下层信道接收数据

Rdt2.0: 具有比特差错的信道

• 下层信道可能会出错：将分组中的 比特 翻转

  • 用校验和 来检测 比特差错

• 问题：怎样从差错中恢复

  • 确认（ACK）: 接收方显式告诉发送方分组已被正确接收
  • 否定确认（NAK）: 接收方显式的 告诉发送方 发生了 差错
    • 发送方 收到 NAK 后，发送方重传分组

• rdt 2.0 中的新机制：采用 差错控制编码进行差错检测

• 发送方差错控制编码、缓存

• 接收方使用 编码检错

• 接收方的 反馈：控制报文（ACK、NAK）：接收方 -> 发送方

• 发送方收到反馈相应的 动作

FSM 描述

没有差错时的操作

有差错的操作

rdt2.1 : rdt2.0 的致命缺陷

如果 ack / nak 出错

• 发送方不知道接收方发生了什么事情
• 发送方如何做
  • 重传？可能重复
  • 不重传？可能死锁（或出错）
• 需要引入新的机制
  • 序号（sequence number）

处理重复

• 发送方在每个分组中加入 序号
• 如果 ack / nak 出错，发送方 重传 当前分组
• 接收方丢弃（不发给上层）重复分组

stop and wait  protocol（停等协议）

发送方发送一个分组，然后等待接受方的应答

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

rdt2.1 ：接收方处理出错的 ACK / NAK

rdt2.1 ：讨论

发送方

• 在分组中加入序列号
• 两个序列号（0,1） 就足够了
  • 一次只发送一个未经确认的 分组
• 必须检测 ACK / NAK 是否 出错（需要 EDC）
• 状态数 变成了 两倍
  • 必须记住当前分组的序列是 0 还是 1

接收方

• 必须检测 接收到的 分组是否是重复的
  • 状态会指示 希望接收到的 分组序号是 0 还是 1
• 注意 ：接收方并不知道 发送方是否正确接收到 了 其 ACK / NAK
  • 没有安排 确认的 确认（ 没有 “必要 ”）

rdt2.1 的 运行

接收方不知道它最后发送的 ACK/ NAK 是否被正确的 收到

• 发送方不对 收到的 ACK / NAK 给 确认，没有所谓的 确认的确认
• 接收方发送 ack ，如果后面接收方接收到的 是：
  • 老分组 p0?则 ack 错误
  • 下一个分组？ p1 ，ack 正确

rdt 2.2 ： 无 NAK 的协议

• 功能同 rdt 2.1 ，但只使用 ACK ，（ACK 要编号）
• 接收方 对 最后 正确接收的 分组 发 ack ,以代替 NAK
  • 接收方必须 显式地包含被 正确接收分组的 序号
• 当 收到 重复的 ACK （ 如 再次收到 ack0) 时，发送方与 收到 NAK 采取 相同的动作：重传当前分组
• 为后面的一个发送多个数据单位做一个准备
  • 一次 能够发送多个
  • 每一个应答都有 ：ACK、NACK ; 麻烦
  • 使用对前一个数据单位的 ACK，代替本数据单位的 nak
  • 确认信息减少一半，协议处理简单

rdt2.2 的运行

rdt2.2 ：发送方和接收方片断

rdt 3.0 : 具有 比特差错的和分组丢失的 信道

新的假设：下层信道可能会丢失分组（数据 或 ack)

• 会死锁
• 机制还不够处理这种状态
  • 检验和
  • 序列号
  • ACK
  • 重传

方法：：发送方等待 ack 一段 合理的时间

• 发送方超时重传：如果到时没有收到 ack -> 重传
• 问题： 如果 分组（或 ack) 只是被延迟了
  • 重传将会导致 数据重复，但是利用 序列号 已经可以处理这个问题了
  • 接收方必须指明被正确接收的 序列号
• 需要一个 倒计数定时器

rdt3.0 发送方

• 过早超时（延迟的ack）也能够 正常工作，但是效率较低，一半 的分组和确认是重复的
• 设置一个合理的 超时时间 也是非常重要的

rdt3.0 的性能

• rdt3.0 可以工作，但是链路容量比较大的情况下，性能很差（吞吐量低）
  • 链路容量较大，一次发一个 PDU 的不能够充分 利用链路的 传输能力

rdt3.0 的 停等操作

流水线：提高链路利用率

流水线协议

流水线：允许发送方在 未得到对方确认 的情况下一次性发送 多个 分组

• 必须增加 序号的 范围：用多个 bit 表示 分组的 序号

• 在发送方 / 接收方 要有缓冲区

  • 发送方缓冲 ： 未得到确认，可能需要重传的 “分组”

  • 接收方缓冲： 上层用户取用数据的速率 != 接收到的 数据速率； 接收到的 数据可能乱序，排序交付（可靠）

    

• 两种通用的 流水线协议： 回退N步（go-back-N）（GBN） 和 选择重传（selective repeat）（SR）

流水线总结

Go-back-N

• 发送端最多在流水线上有 N 个未确认的分组
• 接收端只是发送累计确认 cumulative ack
  • 接收端如果发现 gap,不确认新到来的 分组
• 发送端拥有对最老的 未确认分组的 定时器
  • 只需设置 一个 定时器
  • 当定时器到时时，重传所有未确认的分组

GBN: 发送方扩展的 FSM

GBN：接收方扩展的 FSM

• 只发送 ACK：对 顺序接收的 最高序号的 分组
  • 可能会产生 重复的 ack
  • 只需记住 expectedseqnum; 接收窗口 = 1
    • 只一个变量就可表示接收窗口
• 对 乱序的 分组
  • 丢弃（不缓存） -> 在接收方不被缓存
  • 对顺序接收的最高序号的分组 进行确认 -> 累计确认

运行中的 GBN

Selective Repeat

• 接收方对每个正确接收的分组，分别发送 ACKn(非累计确认)
  • 接收窗口 > 1
    • 接收窗口 > 1
      • 可以缓存 乱序的分组
    • 最终将 分组按顺序交付给 上层
• 发送方 只对那些没有收到 ACK 的分组进行 重发 - 选择性 重发
  • 发送方为每个未确认的 分组设定一个定时器
• 发送窗口的 最大值（发送缓冲区）限制发送 未确认分组的个数

• 发送端最多在流水线中 有 N 个未确认的分组
• 接收方对每个到来的 分组单独确认 individual ack (非累计确认）
• 发送方为每个 未确认的分组保持一个定时器
  • 当超时定时器到时时，只是重发到时的未确认分组

GBN和 SR 协议的异同

• 相同之处
  • 发送窗口 > 1
  • 一次能够可发送多个未经确认的 分组
• 不同之处
  • GBN：接收窗口尺寸 = 1
    • 接收端：只能顺序接收
    • 发送端：从表现来看，一旦一个分组没有发成功，如 ： 0,1,2,3,4；假如 1 未 成功，2，3,4 都发送出去了， 要 返回 1 再发送 ： GB1
  • SR：接收窗口 尺寸 > 1
    • 接收端：可以乱序接收
    • 发送端：发送 0,1,2,3,4 ，一旦1 未成功，2，3,4 已发送，无需重发，选择性发1

通用：滑动窗口（slide window）协议

• 发送缓冲区
  • 形式：内存中的 一个区域，落入缓冲区的分组可以发送
  • 功能：用于存放已发送，但是没有确认的 分组
  • 必要性：需要重发时可用
• 发送缓冲区的大小：一次最多可以发送多少个未经确认的 分组
  • 停等协议 = 1
  • 流水线协议 > 1，合理的值，不能很大，链路利用率不能超过 100%
• 发送缓冲区中的分组
  • 未发送的：落入发送缓冲区的分组，可以连续发送出去
  • 已经发送出去的，等待对方确认的分组；发送缓冲区的分组只有得到确认才能删除

发送窗口滑动过程-相对表示法

• 采用相对移动方式表示，分组不动
• 可缓冲范围移动，代表一段可以发送的权力

滑动窗口协议（slide window protocol）

• 发送窗口：发送缓冲区内容的一个范围
  • 那些 已发送 但是 未经确认的分组的序号构成的空间
  • 
• 发送窗口的最大值 <= 发送缓冲区的 值
• 一开始：没有发送任何一个分尊
  • 前沿 = 后沿
  • 之间为发送窗口的尺寸 = 0
• 每发送一个分组，前沿前移一个单位

• 接收窗口（receiving window）= 接收缓冲区

  • 接收窗口用于控制哪些分组可以接收
    • 只有收到的分组序号落入接收窗口之内 才允许接收
    • 若序号在接收窗口之外，则丢弃
  • 接收窗口尺寸 Wr = 1,则只能顺序接收
  • 接收窗口尺寸 Wr > 1, 则 可以乱序接收
    • ​ 但提交给上层的分组，要按序
  • 

• 接收窗口的滑动和发送确认

  • 滑动
    • 低序号的分组到来，接收窗口移动
    • 高序号分组乱序列，缓存但不交付（因为 要实现 rdt，不允许失序），不滑动
  • 发送确认
    • 接收窗口 尺寸 = 1，发送连续收到的 最大分组确认（累计确认）
    • 接收窗口尺寸 > 1；收到分组，发送那个分组的确认（非累计确认）
  • 

发送窗口的移动-> 前沿移动

• 发送窗口前沿移动的 极限：不能超过发送缓冲区

发送窗口的移动-> 后沿移动

• 发送窗口 后沿移动

  • 条件：收到老分组的确认

  • 结果：发送缓冲区罩住新的分组，来了分组可以发送

  • 移动的极限：不能超过前沿

    

滑动窗口（slide window）协议-接收窗口

正常情况下的 两个 窗口互动

• 发送窗口
  • 有新的分组落入发送缓冲区范围，发送 -> 前沿滑动
  • 来了 老的低序号分组的确认 -> 后沿向前移动 -> 新的分组可以落入发送缓冲区的范围
• 接收窗口
  • 收到分组，落入到 接收窗口范围内
  • 是低序号，发送确认给对方
• 发送端上面来了分组 -> 发送窗口滑动 -> 接收窗口滑动 -> 发确认

异常情况下 GBN的 窗口互动

异常情况下 SR 的 窗口互动

面向连接的传输：TCP

TCP被称为是面向连接的（connection-oriented),这是因为在一个应用进程可以开始向另一个应用进程发送数据之前，这两个进程必须先相互“握手”，即它们必须相互发送某些预备报文段，以建立确保数据传输的参数。作为TCP连接建立的一部分，连接的双方都将初始化与TCP连接相关的许多TCP状态变量（其中的许多状态变量将在本节和3.7节中讨论）。

TCP 连接

这种TCP“连接”不是一条像在电路交换网络中的端到端TDM或FDM电路。相反，该“连接”是一条逻辑连接，其共同状态仅保留在两个通信端系统的TCP程序中。

由于 TCP 协议只在 端系统中运行 ，而不在中间的 网络元素（路由器和链路层 ）中运行， 所以 中间的网络元素 并不会 维持 TCP 连接

事实上，中间 路由器对 TCP 的连接视而不见，他们看到的 是 数据报，而不是连接

TCP 的 连接也总是 点对点的（point - to - point），即 在单个发送方和单个接收方之间的连接

我们现在来看看TCP连接是怎样建立的。假设运行在某台主机上的一个进程想与另一台主机上的一个进程建立一条连接。发起连接的这个进程被称为客户进程，而另一个进程被称为服务器进程。

该客户应用进程首先要通知客户运输层，它想与服务器上的一个进程建立一条连接。

1

clientsocket.connect((serverName,serverPort))

其中 serverName 是服务器的名字，serverPort 标识了服务器上的进程。

客户上的TCP便开始与服务器上的TCP建立一条TCP连接。

1. 客户首先发送一个特殊的TCP报文段，
2. 服务器用另一个特殊的TCP报文段来响应，
3. 最后，客户再用第三个特殊报文段作为响应。

前两个报文段不承载“有效载荷”，也就是不包含应用层数据；而第三个报文段可以承载有效载荷。由于在这两台主机之间发送了3个报文段，所以这种连接建立过程常被称为 三次握手（three-way handshake）

一旦建立起一条TCP连接，两个应用进程之间就可以相互发送数据了。

下面考虑一下从客户进程向服务器进程发送数据的情况。客户进程通过套接字（该进程之门）传递数据流。数据一旦通过该门，它就由客户中运行的TCP控制了。如图3-28所示，TCP将这些数据引导到该连接的发送缓存（send buffer)里，发送缓存是发起三握手期间设置的缓存之一。接下来TCP就会不时从发送缓存里取出一块数据，并将数据传递到网络层。有趣的是，在TCP规范[RFC793]中却没提及TCP应何时实际发送缓存里的数据，只是描述为 “TCP应该在它方便的时候以报文段的形式发送数据” 。TCP可从缓存中取出并放入报文段中的数据数量受限于**最大报文段长度（Maximum Segment Size,MSS)。MSS通常根据最初确定的由本地发送主机发送的最大链路层帧长度（即所谓的最大传输单元（Maximum Transmission Unit,MTU))**来设置。设置该MSS要保证一个TCP报文段（当封装在一个IP数据报中）加上TCP/IP首部长度（通常40字节）将适合单个链路层帧。以太网和PPP链路层协议都具有1500字节的MTU,因此MSS的典型值为1460字节。注意到MSS是指在报文段里应用层数据的最大长度，而不是指包括首部的TCP报文段的最大长度。

TCP连接的组成包括：一台主机上的缓存、变量和与进程连接的套接字，以及另一台主机上的另一组缓存、变量和与进程连接的套接字。在这两台主机之间的网络元素（路由器、交换机和中继器）中，没有为该连接分配任何缓存和变量。

TCP 报文段结构

TCP 报文段 由 首部字段 和 一个数据字段 组成，数据字段包含一块应用数据

序号与确认号

序号

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

编号

• 期望从另一方收到的 下一个字节的 序号
• 累计确认

RTT 的估计和超时

TCP 如 rdt 一样，它采用 超时/ 重传 机制来处理报文段的丢失问题。但是 超时 间隔长度的设置 是一个明显的问题。显然，超时时间间隔 必须大于 该连接 的RTT，即从一个报文段发出到它被确认的时间，否则 会造成 不必要的 重传

Q： 怎样设置 TCP 超时

• 比 RTT 要长
  • 但 RTT 是变化的
• 太短：太早超时
  • 不必要的重传
• 太长：对报文段的丢失反应太慢

估计往返时间

估计之间往返时间的。这是通过如下方法完成的。报文段的样本RTT(表示为SampleRTT)就是从某报文段被发出（即交给IP)到对该报文段的确认被收到之间的时间量。大多数TCP的实现仅在某个时刻做一次SampleRTT测量，而不是为每个发送的报文段测量一个SampleRTT。这就是说，在任意时刻，仅为一个已发送的但目前尚未被确认的报文段估计Samp-leRTT, 从而产生一个接近每个RTT的新SampleRTT值。另外，TCP决不为已被重传的报文段计算SampleRTT; 它仅为传输一次的报文段测量SampleRTT[Kan1987]

显然，由于路由器的拥塞和端系统负载的变化，这些报文段的 SampleRTT 值会随之波动。由于这种波动，任何给定的SampleRTT值也许都是非典型的。因此，为了估计一个身型的RTT,自然要采取某种对SampleRTT取平均的办法。TCP维持一个SampleRTT均值(称为EstimatedRTT)。一旦获得一个新SampleRTT时，TCP就会根据下列公式来更新EstimatedRTT :

Q：怎样估计 RTT

• SampleRTT：测量 报文段发出到收到确认的 时间
  • 如果有重传，忽略此次测量
• SampleRTT 会变化，因此估计的 RTT 应该比较平滑
  • 对 几个最近的测量值求平均，而不是仅用当前的 SampleRTT

设置和管理重传超时间隔

很明显，超时间隔应该大于等于EstimatedRTT 否则，将造成不必要的重传。但是超时间隔也不应该比 EstimatedRTT 大太多，否则当报文段丢失时，TCP不能很快地重传该报文段，导致数据传输时延大。因此要求将超时间隔设为 EstimatedRTT 加上一定余量。当 SampleRTT 值波动较大时，这个余量应该大些；当波动较小时，这个余量应该小些。因此：

推荐的 TimeoutInterval 为 1 s, 同时当出现超时时， TimeoutInterval 值将加倍，以免即将被确认的后继报文段过早出现超时。然而，**只要收到报文段并更新 EstimatedRTT, 就使用上述公式再次计算 TimeoutInterval **

• 设置超时

  • EstimatedRTT + 安全边界时间

    • EstimatedRTT 变化大（方差大） —> 较大的安全边界时间

  • SampleRTT 会偏离 EstimatedRTT 多远

    

• 超时时间设置

  

TCP: 可靠数据传输

因特网的网络层服务（IP服务）是不可靠的。

IP不保证数据报的交付，不保证数据报的按序交付，也不保证数据报中数据的完整性。

对于IP服务，数据报能句溢出路由器缓存而永远不能到达目的地，数据报也可能是乱序到达，而且数据报中的比特可能损坏（由0变为1或者相反）。

由于运输层报文段是被IP数据报携带着在网络中传输的，所以运输层的报文段也会遇到这些问题。

TCP在IP不可靠的尽力而为服务之上创建了一种可靠数据传输服务（reliable datatransfer service)。

尽力而为服务 :: best-effort service 可以理解为 完全没服务

TCP的可靠数据传输服务确保一个进程从其接收缓存中读出的数据流是无损坏、无间隙、非穴余和按序的数据流；即该字节流与连接的另一方端系统发送出的字节流是完全相同。TCP提供可靠数据传输的方法涉及在 rdt 中所学的许多原理。

• TCP 在 IP 不可靠服务 的基础上建立了 rdt

  • 管道化的 报文段
    • GBN or SR
  • 累计确认 （像 GBN）
  • 单个 重传定时器（像 GBN）
  • 是否可以接收乱序的，没有规范

• 通过一下 事件触发重传

  • 超时（只重发最早的未确认的段 ：SR）
  • 重复的确认
    • 

• 首先考虑简化的 TCP 发送方

  • 忽略重复的确认
  • 忽略流量控制和拥塞控制

TCP 发送方事件

从应用层接收数据

• 用 nextseq 创建报文段
• 序号 nextsq 为报文段首字节的字节流编号
• 如果还没有运行，启动定时器
  • 定时器与最早确认的报文段关联
  • 过期间隔 TimeoutInterval

超时

• 重传后沿最老的 报文段
• 重新启动定时器

收到确认

• 如果是对尚未确认的 报文段确认
  • 更新已被确认的报文序号
  • 如果当前还有未被确认的报文段，重新启动定时器

TCP : 重传

超时触发重传存在的问题之一是超时周期可能相对较长。当一个报文段丢失时，这种长超时周期迫使发送方延迟重传丢失的分组，因而增加了端到端时延。幸运的是，发送方通常可在超时事件发生之前通过注意所谓冗余ACK来较好地检测到丢包情况。冗余ACK(duplicate ACK) 就是再次确认某个报文段的ACK,而发送方先前已经收到对该报文段的确认。

因为发送方经常一个接一个地发送大量的报文段，如果一个报文段丢失，就很可能引起许多一个接一个的 冗余 ACK。如果TCP发送方接收到对相同数据的3个冗余 ACK,它把这当作一种指示，说明跟在这个已被确认过3次的报文段之后的报文段已经丢失。一旦收到3个冗余 ACK,TCP就执行快速重传（fast retransmit)[RFC5681],即在该报文段的定时器过期之前重传丢失的报文段。对于采用快速重传的TCP,可用下列代码片段代替 下图 中的ACK收到事件：

• 超时周期往往太长：
  • 在 重传丢失报文段之前的延时太长
• 通过重复 的ack 来检测报文段的 丢失
  • 发送方通常连续发送大量的 报文段
  • 如果报文段丢失，通常引起多个重复的 ack
• 如果 发送方 收到同一数据的 3 个冗余 ack ，重传最小 序号的 段
  • 快速重传：在定时器过时之前重发报文段
  • 他假设跟在 被确认的数据后面的数据丢失了
    • 第一个 ACK 是正常的
    • 收到第二个该段的 ack,表示接收方收到该段之后的 2 个，3个 乱序段，可能性非常大 -> 段丢失了

快速重传算法

流量控制

前面说过，一条 TCP 连接的每一侧主机都为该链接设置了 接收缓存。当该 TCP 连接收到正确、按序的字节后，他就将数据放入缓存中。相关联的 应用进程会从该缓存中读取数据，但 不必是数据刚一到达就立即读取。 事实上，接收方可能正忙于其他任务，甚至要过很长时间才去读取该数据。如果，某应用程序读取数据时 相对缓慢，而发送方发送得太多、太快， 发送得数据就会很容易地使该链接的接收缓存溢出

• 接收方在其向发送方的 TCP 段头部的 rwnd 字段 “通告” 其 空闲的 buffer 大小

  • RcvBUffer 大小通过 socket 选项设置（典型默认大小为 4096 字节）

  • 很多操作系统 自动调整 RcvBuffer

    

• 发送方限制未确认 （“in-flight”) 字节的个数 <= 接收方发送过来的 rwnd 值

• 保证 接收方不会被淹没

这个方案还存在一个小小的问题，假设主机B的接收缓存已经存满，使得 rwnd=0 。在将 rwnd=0通告给主机A之后，还要假设主机B没有任何数据要发给主机A。此时，考虑会发生什么情况。因为主机B上的应用进程将缓存清空，TCP并不向主机A发送带有rwnd新值的新报文段；事实上，TCP仅当在它有数据或有确认要发时才会发送报文段给主机A。这样，主机A不可能知道主机B的接收缓存已经有新的空间了，即主机A被阻塞而不能再发送数据！为了解决这个问题，TCP规流中要求：当主机B的接收窗口为0时，主机A继续发送只有一个字节数据的报文段。这些报文段将会被接收方确认。最终缓存将开始清空，并且确认报文里将包含一个非0的rwnd值。

描述了 TCP 的流量控制服务之后，在此简要的 提一下 UDP 并不提供 流量控制，报文段由于缓存溢出可能在接收方丢失。 进程每次从 缓存中读取一个完整的报文段，如果 进程从缓存中读取报文段的速度还不够快，那么 缓存将会溢出，并且将丢失报文段

连接管理

TCP：建立 连接

Q: 在网络中，2 次握手建立连接总是可行吗？

• 变化的延迟（连接请求的段没有丢，但可能超时）
• 由于丢失造成的重传
• 报文乱序
• 相互看不到对方

两次握手的失败场景

TCP 三次握手

解决方案：变化的初始序号 + 双方确认对方的 序号（三次握手）

三次握手解决：半连接和接收老数据问题

TCP 三次握手 ： FSM

现在我们去更加仔细的观察如何建立 和 拆除一条 TCP 连接。

• 第一步：客户端的TCP首先向服务器端的TCP发送一个特殊的TCP报文段。该报文段中不包含应用层数据。但是在报文段的首部（参见图3-29)中的一个标志位(即SYN比特）被置为1。因此，这个特殊报文段被称为SYN报文段。另外，客户会随机地选择一个初始序号（client_isn),并将此编号放置于该起始的TCP SYN报文段的序号字段中。该报文段会被封装在一个IP数据报中，并发送给服务器。为了避免某些安全性攻击，在适当地随机化选择client_isn方面有着不少有趣的研究[CERT 2001-09]。
• 第二步：一旦包含TCP SYN报文段的IP数据报到达服务器主机（假定它的确到达了！),服务器会从该数据报中提取出TCP SYN报文段，为该TCP连接分配TCP组存和变量，并向该客户TCP发送允许连接的报文段。（我们将在第8章看到，在完成三次握手的第三步之前分配这些缓存和变量，使得TCP易于受到称为SYN洪泛的拒绝服务攻击。）这个允许连接的报文段也不包含应用层数据。但是，在报文段的首部却包含3个重要的信息。首先，SYN比特被置为1。其次，该TCP报文段首部的确认号字段被置为client_isn+1。最后，服务器选择自己的初始序号(server_isn),并将其放置到TCP报文段首部的序号字段中。这个允许连接的报段实际上表明了：“我收到了你发起建立连接的SYN分组，该分组带有初始序号client_isn。我同意建立该连接。我自己的初始序号是server_isn。”该允许连接的报文段被称为SYN ACK报文段（SYN ACK segment)。
• 第三步：在收到SYN ACK报文段后，客户也要给该连接分配缓存和变量。客户机则向服务器发送另外一个报文段；这最后一个报文段对服务器的允许连接的报文段进行了确认（该客户通过将值server_isn+1放置到TCP报文段首部的确认字段中来完成此项工作）。因为连接已经建立了，所以该SYN比特被置为0。该三次握手的第三个阶段可以在报文段负载中携带客户到服务器的数据。

一旦完成这三个步骤，客户和服务器主机就可以互相发送包括数据的 报文段 了。注意： 为了创建这个连接，在两台主机之间发送了 3 个分组，由于这个原因，这种 连接创建过程 通常被称为 三次握手

在正式交换数据之前，发送方和接收方握手建立通信关系：

• 同意建立连接（每一方都知道 对方愿意建立连接）

• 同意连接参数

  

TCP：关闭连接

任何一个都能终止该连接。当连接结束后主机中的“资源”（即缓存和变量）将被释放。

举一个例子，假设某客户打算关闭连接，如图3-40所示。客户应用进程发出一个关闭连接命令。这会引起客户TCP向服务器进程发送一个特殊的TCP报文段。这个特殊的报文段让其首部中的一个标志位即FIN比特（参见图3-29)被设置为1。当服务器接收到该报文段后，就向发送方回送一个确认报文段。然后，服务器发送它自己的终止报文段，其FIN比特被置为1。最后，该客户对这个服务器的终止报文段进行确认。此时，在两台主机上用于该连接的所有资源都被释放了。

可以注意到 上面客户端与服务器端一共有 4 次 动作，TCP 的连接关闭 也被称为 四次挥手

• 客户端，服务器分别关闭她自己这一侧的连接
  • 发送 FIN bit = 1的 TCP 段
• 一旦接收到 FIN，用 ACK回应
  • 接到 FIN 段，ACK 可以和 它自己发出的 FIN 段 一起发送
• 可以处理同时的 FIN 交换

拥塞控制原理

前面已经分析了面临分组丢失时用于提供可靠数据传输服务的基本原理及特定的TCP机制。在实践中，这种丢包一般是当网络变得拥塞时由于路由器缓存溢出引起的。分组重传因此作为网络拥塞的征兆（某个特定的运输层报文段丢失）来对待，但是却无法处理导致网络拥塞的原因，因为有太多的源想以过高的速率发送数据。为了处理网络拥塞原因，需要一些机制以在面临网络拥塞时遏制发送方。 以非正式的定义来说，太多的数据需要网络传输，超过了 网络 的处理能力 ，故造成 拥塞

拥塞

• 非正式的 定义： “太多的数据需要网络传输，超过了网络的处理能力”
• 与流量控制不同
• 拥塞的表现
  • 分组丢失（路由器 缓冲区溢出）
  • 分组经历比较长的延迟（在路由器的 队列中排序）
• 网络的前 10 位问题

拥塞的原因/代价

场景1

场景2

场景3

拥塞控制方法

在最为宽泛的级别上，我们可根据网络层是否为 运输层拥塞控制提供了 显式帮助，来区分拥塞控制的方法。 两种常见的拥塞控制方法

• 端到端拥塞控制。
  • 在端到端拥塞控制方法中，网络层没有为运输层拥塞控制提供显式支持。即使网络中存在拥塞，端系统也必须通过对网络行为的观察（如分组丢失与时延）来推断之。TCP采用端到端的方法角决拥塞控制，因为IP层不会向端系统提供有关网络拥塞的反馈信息。TCP报文段的丢失（通过超时或3次冗余确认而得知）被认为是网络拥塞的一个迹象，TCP会相应地减小其窗口长度。我们还将看到关于TCP拥塞控制的一些最新建议，即使用增加的往返时延值作为网络拥塞程度增加的指示。
• 网络辅助的拥塞控制。
  • 在网络辅助的拥塞控制中，路由器向发送方提供关于网络中拥塞状态的显式反馈信息。这种反馈可以简单地用一个比特来指示链路中的拥塞情况。该方法在早期的IBM SNA[Schwartz 1982]、DEC DECnet [Jain 1989Ramakrishnan 1990]和ATM[Black 1995]等体系结构中被采用。更复杂的网络反馈也是可能的。例如，在ATM可用比特率（Available Bite Rate,ABR)拥塞控制中，路由器显式地通知发送方它（路由器）能在输出链路上支持的最大主机发送速率。如上面所提到的，默认因特网版本的IP和TCP采用端到端拥塞控制方法。然而，最近IP和TCP也能够选择性地实现网络辅助拥塞控制。

案例学习：ATM ABR 拥塞控制

ABR：available bit rate

• 弹性服务
• 如果发送端的路径 “轻载”
  • 发送使用可用带宽
• 如果发送方的路径拥塞了
  • 发送方限制其发送的速度到最小保障速率上

RM（资源单元（信元

• 由发送端发送，在数据信元中间隔插入
• RM 信元中的 比特 被交换机设置（“网络辅助”）
  • NI bit : no increase rate (轻微拥塞) 速率不要增加 了
  • CI bit: congestion indication 拥塞指示
• 发送端发送的 RM 信元 被接收端返回，接收端不做任何改变

• 在 RM 信元 中的 两个字节（explicit rate）字段
  • 拥塞的交换机可能会降低信元中的 ER 值
  • 发送端发送速度因此是最低的可支持速率
• 数据信元中的 EFCI bit： 被拥塞的交换机设置为 1
  • 如果在 管理信元RM 前面的 数据信元 EFCI 被 设置为了 1，接收端返回的 RM 信元 中设置 CI bit

TCP 拥塞控制

在本节中，我们再次来学习TCP。TCP为运行在不同主机上的两个进程之间提供了可靠传输服务。TCP的另一个关键部分就是其拥塞控制机制。如在前一节所指出，TCP必须使用端到端拥塞控制而不是使网络辅助的拥塞控制，因为IP层不向端系统提供显式的网络拥塞反馈。TCP所采用的方法是让每一个发送方根据所感知到的网络拥塞程度来限制其能向连接发送流量的速率。如果一个TCP发送方感知从它到目的地之间的路径上没什么拥塞，则TCP发送方增加其发送速率；如果发送方感知沿着该路径有拥塞，则发送方就会降低其发送速率。但是这种方法提出了三个问题。第一，一个TCP发送方如何限制它向其连接发送流量的速率呢？第二，一个TCP发送方如何感知从它到目的地之间的路径上存在拥塞呢？第三，当发送方感知到端到端的拥塞时，采用何种算法来改变其发送速率呢？

端到端的拥塞控制机制

• 路由器不向主机有关拥塞 反馈信息
  • 路由器的负担较轻
  • 复合网络核心简单的 TCP / IP 架构原则
• 端系统根据自身得到的信息，判断 是否发生拥塞，从而采取动作

拥塞控制的 几个问题

• 如何检测拥塞
  • 轻微拥塞
  • 拥塞
• 控制策略
  • 在拥塞发送时如何 动作，降低速率
    • 轻微拥塞，如何降低
    • 拥塞时，如何 降低
  • 在拥塞 缓解时如何动作，增加速率

TCP拥塞控制：拥塞感知

发送端怎么探测到拥塞

• 某个端超时了 （丢失事件）：拥塞
  • 超时时间到，某个时间的确认没有来
  • reason1: 网络拥塞（某个路由器缓冲区没有空间了，被丢弃）概率大
  • reason2：出错被丢弃了（各级错误，没有通过校验，被丢弃）概率小
  • 一旦超时。就认为拥塞了，有一定误判，但是 总体控制方向是对的
• 有关某个段的 3 次 冗余 ack，轻微拥塞
  • 段的第一个 ack，正常，确认绿段，期待红段
  • 段的 第二个 重复 ack ，意味着红段的后一段收到了，蓝段乱序到达
  • 段的 第 2,3,4 个 ack 重复，意味着红段的 后 第2,3,4 个段都到了，橙段乱序到达，同时红段丢失的可能性很大（后面三个段都到了，红段没有到）
  • 网络这时还能够进行一定程度的传输，拥塞但情况要比第一种情况好

TCP拥塞控制：速率控制方法

如何控制发送端发送的速率

• 维持一个拥塞窗口的值 ：CogWin

• 发送端限制 已发送但未确认的 数据量（的上限）

  

• 从而粗略的限制发送方的 往网络中注入的速率

  

• CongWin 是动态的，是感知到的网络拥塞程度的函数

  • 超时或者 三个 冗余 ack ,CongWin 下降
    • 超时：CongWin 降为 1MSS，进入 SS 阶段然后再倍增到 CongWin/2 (每个RTT)， 从而进入 CA 阶段
    • 三个 冗余 ack： CongWin 降为 CongWin/2, CA 阶段
  • 否则（正常收到 ACK， 没有发送以上情况）： CongWin 跃跃欲试 增加
    • SS 阶段：加倍增加（peer RTT）
    • CA阶段：线性增加（peer RTT）

TCP 拥塞控制和流量控制的联合动作

联合控制的方法

• 发送端控制 发送但是未确认的量同时也不能超过接收窗口，满足流量控制要求
  • SendWin = min{CongWin,RecvWin}
  • 同时满足 拥塞控制和流量控制要求

TCP拥塞控制：策略概述

拥塞控制策略

• 慢启动
• AIMD：线性增、乘性减少
• 超时事件后的保守策略

慢启动

慢启动 并不慢，或者说，慢启动 很快。准确的说，TCP 发送速率起始慢，但后面以指数增长

AIMD

• 当收到 三个冗余 ack
  • CongWin 减半
  • 窗口（缓冲区大小）之后线性增长
• 当 超时 事件发生时
  • CongWin 被设置为1 MSS，进入 SS 阶段
  • 之后窗口指数增长
  • 增长到一个阈值（上次发生拥塞的窗口的一半）时，再线性增加

改进

总结：TCP 拥塞控制

• 当CongWin < Threshold,发送端处于慢启动阶段（slow-start),窗口指数性增长.
• 当CongWin > Threshold,发送端处于拥塞避免阶段(congestion-avoidance),窗口线性增长.
• 当收到三个重复的ACKs(triple duplicate ACK)
  • Threshold设置成CongWin/2
  • CongWin=Threshold+3.
• 当超时事件发生时timeout,Threshold=CongWin/2 CongWin=1 MSS,进入SS阶段

TCP 吞吐量

TCP 公平性

公平性目标：如果 K 个 TCP 会话分享一个链路带宽为 R 的瓶颈，每一个会话的有效带宽为 R/K

为什么 TCP 是公平的

两个竞争的 TCP 会话

• 加性增加，斜率为1，吞吐量增加
• 乘性减，吞吐量比例减少

公平性和 UDP

• 多媒体应用通常不使用 TCP
  • 应用发送的数据速率希望不收拥塞控制的节制
• 使用 UDP
  • 音视频 泵出数据的速率是恒定的，忽略数据的丢失
• 研究领域 ：TCP 友好性

公平性和并行 TCP 连接

• 两个主机间可以打开多个并行的 TCP 连接
• WEB浏览器
• 

Explicit Congestion Notification（ECN）

网络辅助拥塞控制

• TOS 字段中两个 bit 被网络路由器标记，用于指示是否发生拥塞
• 拥塞指示被传送到接收主机
• 在接收方 - 到 发送方的 ack中，接收方（在IP 数据报中看到了拥塞指示）设置 ECN bit，指示发送方发生了拥塞

总结

• 传输层提供的服务
  • 应用进程间的逻辑通信
    • Vs 网络层提供的是主机到主机间的通信服务
  • 互联网上传输层协议：UDP TCP
    • 特性
• 多路复用和解复用
  • 端口：传输层的 SAP
  • 无连接的多路复用和解复用
  • 面向连接的多路复用和解复用
• 实例1：无连接传输层协议 UDP
  • 多路复用和解复用
  • UDP 报文格式
  • 检错机制：校验和
• 可靠数据传输原理
  • 问题描述
  • 停止等待协议
    • rdt 1.0 2.0 2.1 2.2 3.0
  • 流水线协议
    • GBN
    • SR
• 实例2：面向连接的传输层协议 - TCP
  • 概述：TCP 特性
  • 报文段格式
    • 序号，超时机制及时间
  • TCP 可靠传输机制
  • œœ†··重传、快速重传
  • 流量控制
  • 连接管理
    • 三次握手
    • 对称连接释放
• 拥塞控制原理
  • 网络辅助的 拥塞控制
  • 端到端的拥塞控制
• TCP 的 拥塞控制
  • AIMD
  • 慢启动
  • 超时之后的保守策略

网络层

网络层概述

网络层服务

• 在发送主机和接收主机对之间 传送 段（segment）
• 在发送端将端封装到 数据报中
• 在接收端，将端上交给 传输层实体
• 网络层 协议存在于 每一个 主机 和 路由器
• 路由器检查每一个经过他的IP 数据报的头部

网络层的 关键功能

网络层功能

• 转发：将分组从路由器的输入接口转发到合适输出接口
• 路由：使用路由算法来决定分组从发送主机到目标接收主机的路径

旅行的类比

• 转发：通过单个路口的过程
• 路由：从 源到目的地路由路径的规划过程

网络层：数据平面、控制平面

数据平面

• 本地，每个路由器的功能
• 决定从路由器的输入端口到达的分组如何转发到输出端口
• 转发功能
  • 传统方式：基于目标地址 + 转发表
  • SDN方式：基于多个字段 + 流表

控制平面

• 网络范围内的逻辑
• 决定数据报如何在路由器之间路由，决定数据报从源到目标主机之间的端到端路径
• 2 个 控制平面方法
  • 传统的路由算法：在路由器中被实现
  • software-defined networking (SDN) :在远程的服务器中实现

传统方式：每-路由器（peer-router ) 控制平面

在 每一个路由器中的 单独路由器算法元件，在控制平面进行交互

传统方式：路由和转发的相互作用

SDN 方式：逻辑集中的控制平面

一个不同的（通常是 远程的）控制器和本地代理（CAs） 交互

网络服务模型

Q：从发送方主机到接收方主机传输数据报的 “通道”，网络提供怎么样的 服务模型

对于单个数据报的服务

• 可靠传送
• 延迟保证

对于数据报流的服务

• 保序数据报传送
• 保证流的最小带宽
• 分组之间的延迟差

连接建立

网络层：数据平面

在本章和下一章中，我们将学习网络层是怎样实现主机到主机的通信服务的。我们将看到 与 运输层和 应用层不同，在网络上中的每一台主机和路由器中都有一个网络层部分。正因如此，网络层协议是协议栈中最有趣的部分（也是最具有挑战性的部分）

我们将看到 **网络层能够被分解成两个相互作用的部分，即 数据平面 和 控制平面**。在数据平面，即网络层中每台路由器的功能，该数据平面功能决定到达路由器输入链路之一的数据报（即网络层的分组）如何转发到该路由器的输出链路之一。我们将涉及传统的IP转发（其中转发基于数据报的目的地址）和通用的转发（其中可以使用数据报首部中的几个不同域的值执行转发和其他功能）。我们将详细地学习IPv4和IPv6协议及其寻址

路由工作原理

下图是一个常见的通常路由器的体系架构

路由结构概况

高层面（非常简化的） 通用路由器体系架构

• 路由：运行 **路由 ** 选择算法 / 协议 - 生成路由表
• 转发：从输入到输出链路交换数据报 - 根据路由表进行 分组的 转发

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

输入端口功能

这里的端口是 路由器的物理的输入输出 接口

图4-5中显示了一个更详细的输入处理的视图。输入端口的线路端接功能与链路层处理实现了用于各个输入链路的物理层和链路层。在输入端口中执行的查找对于路由器运行是至关重要的。正是在这个地方，路由器使用转发表来查找输出端口，使得到达的分组能经过交换结构转发到该输出端口。转发表是由路由选择处理器计算和更新的（使用路由选择协议与其他网络路由器中的路由选择处理器进行交互）,或者转发表接收来自远程SDN控制器的内容。转发表从路由选择处理器经过独立总线（例如一个PCI总线）复制到线路卡

在图4-4中该总线由从路由选择处理器到输入线路卡的虚线所指示。使用在每个输入端口的影子副本，转发决策能在每个输入端口本地做出，无须基于每个分组调用集中式路由选择处理器，因此避免了集中式处理的瓶颈。

最长前缀匹配

longest  prefix matching

当给定目标地址查找转发表时，采用 最长 地址前缀匹配的目标地址表项

• 最长前缀匹配：在路由器中经常采用 TCAMs (ternary content addressable memories ) [三态内容可存址存储器]硬件来完成
  • 内容可寻址：将地址交给 TCAM ，他可以在一个时钟周期内检索出地址，不管表空间有多大
  • Cisco Catalyst 系列路由器：在 TCAM 中可以存储多达 100多万的路由表项

输入端口缓存

• 当交换机构的速率小于输入端口的汇集速率时， 在输入端口可能要排队
  • 排队时延以及由于输入缓存溢出造成丢失！
  • Head-of-the-Line (HOL) blocking :排在队头的数据阻止了队列中的其他数据向前移动

交换

交换结构位于一台路由器的核心部位，因为正是通过这种交换结构，分组才能实际地从一个输入端口交换（即 转发）到一个输出端口中。交换可以用很多种方式完成

• 将分组从 输入缓冲区 传送到合适的输出端口
• 交换速率：分组可以按照该速率从输入到输出
  • 运行速率经常是 输入/输出链路 速率的若干倍
  • N 个 输入端口：交换结构的交换速度是 输入速率的 N倍 比较 理想，才不会成为瓶颈

通过内存交换

• 在 CPU 直接控制下的交换，采用传统的计算机
• 分组被拷贝到 系统内存，CPU从分组的头部提取出目标地址，查找转发表，找到对应的输出端口，拷贝到输出端口
• 转发速率被内存的带宽限制（数据报通过 BUS两遍)
• 一次只能转发一个分组

通过总线交换

• 数据报通过共享总线，从输入端口转发到输出端口
• 总线竞争：交换速率受限于总线带宽
• 一次处理一个分组路由器
• 对于 接入或 企业级，速度足够，但是不适合区域或骨干路网络

通过互联网络（crossbar 等）的交换

• 同时并发转发多个分组，克服总线带宽限制
• Banyan(榨树）网络，crossbar(纵横）和其它的互联网络被开发，将多个处理器连接成多处理器
• 当分组从端口A到达，转给端口y;控制器短接相应的两个总线
• 高级设计：将数据报分片为固定长度的信元，通过交换网络交换
• Cisco12000:以60Gbps的交换速率通过互联网络

输出端口处理

如图所示，输出端口处理取出已经存放在输出端口内存中的分组 并将其转发到输出链路上，这包括 选择和取出排队的分组进行传输，执行所需的链路层和物理层传输功能

• 当数据报从交换结构的到达速度比传输速率快时，就需要输出端口缓
  • 数据报（分组）可能会被丢弃，由于拥塞、缓冲区没有空间
• 由调度规则选择排队的数据报进行传输

输出端口排队

• 假设 R-switch 是 R-line 的 N 倍（N： 输入端口的数量）
• 当多个输入端口同时向输出端口发送时，缓冲该分组（当通过交换网络到达的速率超过 输出速率则缓存）
• 排队带来延迟，由于输出端口缓存溢出则丢弃数据报

需要多少缓存

调度机制

• 调度：选择下一个要通过 链路 传输的分组
• FIFO scheduling ：按照分组到来的次序发送
  • 丢弃策略：如果一个分组到达一个满的队列，哪 个分组将会被抛弃
    • 
    • tail drop：丢弃刚到达的分组
    • priority ：根据优先权 丢弃/移除分组
    • random： 随机的丢弃/移除

调度策略：优先权

优先权调度：发送优先权最高的 分组

• 多类，不同类别有不同的优先权
  • 类别可能依赖于标记或者其他的头部字段
  • 先传优先级高的分组，除非没有
  • 高（低）优先级的分组传输次序：FIFO

调度策略：其他的

Round Robin (RR) scheduling:

• 多类
• 循环扫描不同的类型的队列，发送完一类的一个分组，再发送下一类的一个分组，循环所有类

Weighted Fair Queuing (WFQ):

• 一般化的 Round Robin
• 在一段时间内，每个队列得到的服务时间是 , 和权重成正比
• 每个类在一个循环中获得不同的权重的服务量

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

互联网的网络层

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

IPv4 数据报格式

注意到一个IP数据报有总长为20字节的首部（假设无选项）。如果数据报承载一个TCP报文段，则每个（无分片的）数据报共承载了总长40字节的首部（20字节的IP首部加上20字节的TCP首部）以及应用层报文。

IPv4 数据报分片

在链路层中我们将知道，并不是所有链路层协议都能承载相同长度的网络层分组。有的协议能承载大数据报，而有的协议只能承载小分组。例如，以太网帧能够承载不超过1500字节的数据，而某些广域网链路的帧可承载不超过576字节的数据。一个链路层帧能承载的最大数据量叫作最大传送单元（Maximum Transmission Unit,MTU)。因为每个IP数据报封装在链路层帧中从一台路由器传输到下一台路由器，故链路层协议的MTU严格地限制着IP数据报的长度。对IP数据报长度具有严格限制并不是主要问题。问题在于在发送方与目的地路径上的每段链路可能使用不同的链路层协议，且每种协议可能具有不同的MTU。

• 网络链路层有 MTU （最大传输单元） - 链路层帧所携带的最大 数据长度
  • 不同的链路类型
  • 不同的MTU

解决该问题的方法是将IP数据报中的数据分片成两个或更多个较小的IP数据报，用单独的链路层帧封装这些较小的IP数据报，然后通过输出链路发送这些帧。每个这些较小的数据报都称为 **片(fragment)**。

• 大的 IP 数据报在网络上被分片
  • 一个数据报被分割成若干个小的数据报
    • 相同的 IP
    • 不同的偏移量
    • 最后一个分片标记为 0
  • “重组” 只在 最终的目标主机上进行
  • IP 头部的信息被用于 标识 、排序相关分片

当一台目的主机从相同源收到一系列数据报时，它需要确定这些数据报中的某些是否是一些原来较大的数据报的片。如果某些数据报是这些片的话，则它必须进一步确定何时收到了最后一片，并且如何将这些接收到的片拼接到一起以形成初始的数据报。为了让目的主机执行这些重新组装任务，IPv4的设计者将标识、标志和片偏移字段放在IP数据报首部中。当生成一个数据报时，发送主机在为该数据报设置源和目的地址的同时贴上标识号。发送主机通常将它发送的每个数据报的标识号加1。当某路由器需要对一个数据报分片时，形成的每个数据报（即片）具有初始数据报的源地址、目的地址与标识号。当目的地从同一发送主机收到一系列数据报时，它能够检查数据报的标识号以确定哪些数据报实际上是同一较大数据报的片。由于IP是一种不可靠的服务，一个或多个片可能永远到达不了目的地。因为这种原因，为了让目的主机绝对地相信它已收到了初始数据报的最后一个片，最后一个片的标志比特被设为0,而所有其他片的标志比特被设为1。另外，为了让目的主机确定是否丢失了一个片（且能按正确的顺序重新组装片）,使用偏移字段指定该片应放在初始IP数据报的哪个位置。

IPv4 编址

然而，在讨论IP编址之前，我们需要简述一下主机与路由器连入网络的方法。一台主机通常只有一条链路连接到网络；当主机中的IP想发送一个数据报时，它就在该链路上发送。主机与物理链路之间的边界叫作接口（interface)。现在考虑一台路由器及其接口。因为路由器的任务是从链路上接收数据报并从某些其他链路转发出去，路由器必须拥有两条或更多条链路与它连接。路由器与它的任意一条链路之间的边界也叫作接口。一台路由器因此有多个接口，每个接口有其链路。因为每台主机与路由器都能发送和接收IP数据报，IP要求每台主机和路由器接口拥有自己的IP地址。因此，从技术上讲，一个IP地址与一个接口相关联，而不是与包括该接口的主机或路由器相关联。

每个IP地址长度为32比特（等价为4字节）,因此总共有232个（或大约40亿个）可能的IP地址。这些地址通常按所谓点分十进制记法（dotted-decimal notation)书写，即地址中的每个字节用它的十进制形式书写，各字节间以句点隔开。例如，考虑IP地址193.32.216.9,193是该地址的第一个8比特的十进制等价数，32是该地址的第二个8比特的 十进制 等价数，因此 该地址的 二进制记法是：

在全球因特网中的每台主机和路由器上的每个接口，都必须有一个全球唯一的IP地址（在NAT后面的接口除外）。然而，这些地址不能随意地自由选择。一个接口的IP地址的一部分需要由其连接的子网来决定。

• IP 地址：
  • 子网部分（高位 bits)
  • 主机部分（低位 bits)
• 什么是 子网（Subnet）
  • 一个子网内的节点（主机或者路由器）他们的 IP 地址的高位部分相同，这些节点构成的 网络的一部分 叫作 子网
  • 无需路由器介入，子网内 各主机可以在物理上 相互直接到达

方法：

• 要判断一个子网，将每一个接口从主机或者路由器上分开，构成了一个个网络的孤岛
• 每一个孤岛（网络）都是一个都可以被称之为 subnet

IP 地址分类

特殊的 IP 地址

• 一些约定

  • 子网部分：全为 0 — 本网络
  • 主机部分：全为 0 — 本主机
  • 主机部分： 全为 1 — 广播地址，这个网络的所有主机

• 特殊 的 IP 地址

  

内网（专用）IP 地址

• 专用地址：地址空间的一部分 供专用地址使用

• 永远不会被 当做公用地址来分配，不会与公用地址重复

  • 只在局部网络中有意义，区分不同的设备

• 路由器不对 目标地址是专用地址的分组进行转发

• 专用地址范围

  

IP 编址：CIDR

CIDR： Classess InterDomain Routing

(无类域间路由)

• 子网部分可以在任意的位置
• 地址格式： a.b.c.d/x，其中 X 是 地址中子网号的 长度

子网掩码

转发表和转发算法

• 获得 IP 数据报的 目标地址
• 对于转发表中的每一个表项
  • 如 （IP Des addr) & （mask) == destination ,则按照表项对应的接口转发该数据报
  • 如果都没有找到，则使用默认表项转发数据报

如何获得一个 IP 地址

DHCP：Dynamic Host Configuration Protocol

由于DHCP具有将主机连接进一个网络的网络相关方面的自动能力，故它又常被称为即插即用协议（plug-and-play protocol)或零配置（zeroconf)协议

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

• 可以更新对主机的在用 IP 地址的租用期 - 租期快到
• 重新启动时，允许重新使用之前的 IP 地址
• 支持移动网络用户加入该网络 （短期在网)

DHCP 工作概况

• 主机广播 DHCP discover 报文可选
• DHCP 服务器 用 DHCP offer 提供报文响应
• 主机请求 IP 地址 ：发送 DHCP request 报文
• DHCP 服务器发送地址：**DHCP  ack ** 报文

DHCP client-server scenario

DHCP 不仅仅只是 IP address

DHCP 返回

• IP地址
• 第一跳路由器的 IP 地址（默认网关）
• DNS服务器的域名和 IP 地址
• 子网掩码（指示地址部分的网络号和主机号）

对于一个新到达的主机，DHCP 是一个 4 个步骤的过程

• DHCP 服务器发现
  • 一台新到达的主机的首要任务就是发现一个 要与其交互 的 DHCP 服务器，这可以通过 DHCP发现报文 （DHCP discover message） 来完成
• DHCP 服务器提供
  • DHCP 服务器发现收到一个 DHCP 发现报文时，用 DHCP 提供 报文（DHCP offer message) 向客户 做出响应，该报文向该子网的所有节点广播 ，仍然使用 广播地址 255.255.255.255
• DHCP 请求
  • 新到达的客户从一个或多个服务器提供中选择一个，并向选中的服务器提供用DHCP请求报文（DHCP request message)进行响应，回显配置的参数。
• DHCP ack
  • 服务器用DHCP ACK报文（DHCP ACK message)对DHCP请求报文进行响应，证实所要求的参数。

一旦客户收到 DHCP ack 后，交互便完成了，并且该用户能在租用期内使用 DHCP 分配的IP 地址而且 DHCP 还 允许客户更新它对一个 IP 地址的租用

从移动性角度看，DHCP确实有非常严重的缺陷。因为每当节点连到一个新子网，要从DHCP得到一个新的IP地址，当一个移动节点在子网之间移动时，就不能维持与远程应用之间的TCP连接。在后面，我们将研究移动IP,它是一种对IP基础设施的扩展，允许移动节点在网络之间移动时使用其单一永久的地址。

层次编址：路由聚集 （route aggregation)

IP 编址：如何获得一块地址

一个 ISP 如何获得一个 地址

ICANN ：**Internet Corporation for Assigned Names and Numbers **

• 分配地址
• 管理 DNS
• 分配域名，解决冲突

网络地址转换

NAT （Network Address Translation)

• 动机：本机网络只有一个有效的 IP 地址
  • 不需要 从 ISP 分配一块地址，可用一个 IP 地址用于所有的 （局域网）设备 — 省钱
  • 可以在局域网改变设备的地址情况下而无须通知外界
  • 可以改变 ISP（地址变化）而不需要改变内部的设备地址
  • 局域网内部的设备没有具体的地址，对外是不可见的
• 实现：NAT 路由器 必须：
  • 外出数据包: 替换 源地址和端口号为 NAT IP 地址和新的端口号，目标 IP 劲儿端口不变
  • 记住 每个转换替换对（在 NAT 转换表中）
  • 进入数据包：替换 目标IP 地址和 端口号，采用存储在 NAT 表中的mapping 表项

NAT使能路由器对于外部世界来说甚至不像一台路由器。相反NAT路由器对外界的行为就如同一个具有单一IP地址的单一设备。在图4-25中，所有离开家庭路由器流向更大因特网的报文都拥有一个源IP地址138.76.29.7,且所有进入家庭的报文都拥有同一个目的IP地址138.76.29.7。从本质上讲，NAT使能路由器对外界隐藏了家庭网络的细节。(另外，你也许想知道家庭网络计算机是从哪儿得到其地址，路由器又是从哪儿得到它的单一IP地址的。在通常的情况下，答案是相同的，即DHCP!路由器从ISP的DHCP服务器得到它的地址，并且路由器运行一个DHCP服务器，为位于NAT-DHCP路由器控制的家庭网络地址空间中的计算机提供地址。）

如果从广域网到达NAT路由器的所有数据报都有相同的目的IP地址（特别是对NAT路由器广域网一侧的接口）,那么该路由器怎样知道它应将某个分组转发给哪个内部主机呢？技巧就是使用NAT路由器上的一张**NAT转换表（NAT translation table),**并且在表项中包含了端口号及其IP地址。

• 16 - bit 端口字段
  • 6 万多个同时连接，一个局域网
• 有 NAT 是 有争议的
  • 路由器 只应该对 第 3 层 做信息处理，而这里对 端口号（4 层） 做了处理
  • 违反了 end - to - end 原则
    • 端到端原则：复杂性放到 网络边缘
      • 无需借助 中转和 变换，就可以直接转送到目标主机
    • NAT 可能要被一些 应用设计者考虑
    • 外网的机器无法主动连接到内网的机器上
  • 地址短缺问题可以被 IPv6 解决
  • NAT 穿越：如果客户端需要连接 在 NAT 后面的机器，应该如何操作

NAT 穿越

IPv6

初始动机：32 - bit 的地址空间将很快被用完

另外的动机：

• 头部格式改变 帮助加速处理和转发
  • TTL-1
  • 头部 checksum
  • 分片
• 头部格式 帮助改变 QoS

IPv6 数据报格式

IPv6 头部（cont)

Priority: 标识流中数据报的等级

Low Label： 标识一个数据在一个 flow

Next header：标示上层协议

和 IPv4 的变化

• checksum: 被移除，降低在每一段中的处理速度
• options: 允许，但是在头部之外，被 Next Header 字段标识
• ICMPv6: ICMP 的新版本
  • 附加了 报文类型
  • 多播组管理功能

从 IPv4 到 IPv6 的迁移

• 不是所有路由器都可以同时升级的

  • 没有一个 标记日 “flag days”
  • 在 IPv4 和 IPv6 路由器混合时，网络如何运转

• 隧道：在 IPv4 路由器之间传输的 IPv4 数据报中携带 IPv6 数据报

  

隧道 （Tunneling）

IPv6 的应用

通用转发 和 SDN

网络层为例的数据平面和控制平面

网络层功能

• 转发：对于从某个端口到来的分组转发到 合适的 输出端口
• 路由：决定分组从 源端到 目标端的算法
  • 路由算法

数据平面

• 本地的、每个路由器的功能
• 决定某个从某个端口进入的分组从哪个端口输出
• 转发功能

控制平面

• 网络范围的逻辑
• 决定分组 端到端穿行于 各个 路由器的路径

传统方式

网络设备控制平面实现方式的特点

• 互联网网络设备 ：传统方式都是通过分布式，每台设备的方法来实现数据平面和 控制平面功能
  • 垂直集成：每台路由器或其他 网络设备，包括：
    • 硬件、在私有的 操作系统
    • 互联网 标准协议的 私有实现
    • 从上到下都由一个厂商提供
  • 每个设备都实现了数据平面和 控制平面
    • 控制平面的功能是分布式 实现的
  • 设备基本上只能（分布式升级难） 按照固定方式工作，控制逻辑固化，不同的网络设备需要不同的 防火墙、负载均衡设备
• （数据 + 控制平面） 集成 > （控制逻辑） 分布 -> 固化
  • 代价大；升级困难；管理困难

SDN：逻辑上的控制平面

一个不同的（通常是远程的） 控制器和 CA 交互，控制器决定 分组的转发逻辑（可编程），CA 所在设备执行逻辑

通用转发 和 SDN

回顾之前将基于目的地转发的特征总结为两个步骤：查找目的IP地址（“匹配”）,然后将分组发送到有特定输出端口的交换结构（“动作”）。我们现在考虑一种更有意义的通用“匹配加动作”范式，其中能够对协议栈的多个首部字段进行“匹配”，这些首部字段是与不同层次的不同协议相关联的。“动作”能够包括：将分组转发到一个或多个输出端口（就像在基于目的地转发中一样）,跨越多个通向服务的离开接口进行负载均衡分组（就像在负载均衡中一样）,重写首部值（就像在NAT中一样）,有意识地阻挡/丢弃某个分组（就像在防火墙中一样）,为进一步处理和动作而向某个特定的服务器发送一个分组（就像在DPI一样）,等等。在通用转发中，一张匹配加动作表将我们在数据平面中看到的基于目的地的转发表一般化了。因为能够使用网络层和/或链路层源和目的地址做出转发决定，所以显示在图4-28中的转发设备更为准确地描述为“分组交换机”而不是第三层“路由器”或第二层“交换机”。因此，在本节后面部分以及控制平面中，我们将这些设备称为分组交换机，这是在SDN文献中被广泛采用的术语。

我们后续对通用转发的讨论将基于 OpenFlow , OpenFlow 是一个得到高度认可和成功的标准，它已经成为匹配加动作转发抽象、控制器以及更为一般的SDN革命等概念的先驱[Feamster2013]。我们将主要考虑OpenFlow1.0,该标准以特别清晰和简明的方式引入了关键的SDN抽象和功能。

匹配加动作转发表在OpenFlow中称为流表（flow table),它的每个表项包括：

• 首部字段值的集合，入分组将与之匹配。与基于目的地转发的情况一样，基于硬件匹配在TCAM内存中执行得最为迅速（TCAM内存中可能有上百万条地址表项）[Bosshart2013]。匹配不上流表项的分组将被丢弃或发送到远程控制器做更多处理。在实践中，为了性能或成本原因，一个流表可以由多个流表实现[Bosshart2013],但我们这里只关注单一流表的抽象。
• 计数器集合（当分组与流表项匹配时更新计数器）。这些计数器可以包括已经与该表项匹配的分组数量，以及自从该表项上次更新以来的时间。
• 当分组匹配流表项时所采取的动作集合。这些动作可能将分组转发到给定的输出端口，丢弃该分组、复制该分组和将它们发送到多个输出端口，和/或重写所选的首部字段。

SDN

SDN 的主要思路

• 网络设备数据平面和 控制平面 分离
• 数据平面 - 分组交换机
  • 将 路由器、交换机 和目前大多数网络设备的功能进一步 抽象 成： 按照流表（由控制平面 设置的 逻辑） 进行 PDU （帧、分组）的动作 （包括转发、丢弃、拷贝、泛洪、阻塞）
  • 统一化 设备功能：SDN 交换机（分组交换机），执行控制逻辑
• 控制平面 - 控制器 + 网络应用
  • 分离、集中
  • 计算和下发控制逻辑：流表

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

• 水平集成 控制平面的 开放实现（而非私有实现）。创造出良好的生态，促进发展
  • 分组交换机、控制器和各种控制逻辑网络应用 app 可由不同厂商生产，专业化，引入竞争形成良好生态
• 集中 式 实现控制逻辑，网络 管理容易
  • 集中式控制器了解 网络状况，编程简单，传统方式困难
  • 避免路由器的 误配置
• 基于 流表的 匹配 + 行动 的工作方式 允许 “可编程的” 的 分组交换机
  • 实现流量工程等高级特性
  • 在此框架下实现各种 新型（未来）的网络设备

流量工程

SDN 特点

SDN 架构：数据平面交换机

数据平面交换机

• 快速、简单，商业化 交换设备 采用硬件实现通用转发功能
• 流表被 控制器计算和安装
• 基于 南向 API ，SDN 控制器访问基于流的交换机
  • 定义了哪些可以，哪些不能
• 也定义了和 控制器的协议

SDN架构：SDN 控制器

SDN 控制器 （网络 OS）：

• 维护网络状态信息
• 通过上面的南向 API 和网络交换机交互
• 逻辑集中，但是在实现上 通常由性能、可扩展性、容错性以及健壮性 采用分布式方法

SDN 架构：控制应用

网络控制应用

• 控制的大脑：采用下层提供的服务（SDN控制器提供的API），实现网络功能
  • 路由器 交换机
  • 接入控制 防火墙
  • 负载均衡
  • 其他功能
• 非绑定：可以被第三方提供，与控制器厂商通常不同，与分组交换机也可以不同

匹配

图4-29显示了11个分组首部字段和入端口ID,该ID能被OpenFlow1.0中的匹配加动作规则所匹配。前面讲过，到达一台分组交换机的一个链路层（第二层）帧将包含一个网络层（第三层）数据报作为其有效载荷，该载荷通常依次将包含一个运输层(第四层）报文段。第一个观察是，OpenFlow的匹配抽象允许对来自三个层次的协议首部所选择的字段进行匹配（因此相当勇敢地违反了我们在1.5节中学习的分层原则）。因为我们还没有涉及链路层，用如下的说法也就足够了：显示在图4-29中的源和目的MAC地址是与帧的发送和接收接口相关联的链路层地址；通过基于以太网地址而不是IP地址进行转发，我们看到OpenFlow使能的设备能够等价于路由器（第三层设备）转发数据报以及交换机（第二层设备）转发帧。

入端口是指 分组交换机上接收分组的输入接口

最后，并非一个 IP 首部中的所有字段都能被匹配

在一个时刻做一件事，将它做好。一个接口应当俘获 一个抽象的最低限度的要件。不要进行一般化，一般化通常是错误的

动作

如图4-28中所见，每个流表项都有零个或多个动作列表，这些动作决定了应用于与流表项匹配的分组的处理。如果有多个动作，它们以在表中规定的次序执行。

其中最为重要的动作可能是：

• 转发。一个人分组可以转发到一个特定的物理输出端口，广播到所有端口（分组到达的端口除外）,或通过所选的端口集合进行多播。该分组可能被封装并发送到用于该设备的远程控制器。该控制器则可能（或可能不）对该分组采取某些动作，包括安装新的流表项，以及可能将该分组返回给该设备以在更新的流表规则集合下进行转发。
• 丢弃。没有动作的流表项表明某个匹配的分组应当被丢弃。
• 修改字段。在分组被转发到所选的输出端口之前，分组首部10个字段（图4-29中显示的除IP协议字段外的所有第二、三、四层的字段）中的值可以重写。

OpenFlow 数据平面抽象

• 流： 由分组（帧） 头部字段所定义
• 通用转发：简单的分组处理规则
  • 模式：将分组头部字段和流表进行匹配
  • 行动：对于匹配上的分组，可以是 丢弃、转发、修改 、将 匹配的分组发送给控制器
  • 优先权：几个模式匹配了，优先采用那个，消除歧义
  • 计数器：# bytes 以及 #packets

OpenFlow：流表的表项结构

OpenFlow 抽象

• match + action ：统一化各种网络设备提供的功能
• 路由器
  • match：最长前缀匹配
  • action： 通过一条链路转发
• 交换机
  • match：目标 MAC 地址
  • action：转发或者泛洪
• 防火墙
  • match：IP 地址和 TCP/UDP 端口号
  • action：允许或者禁止
• NAT
  • match: IP 地址和端口号
  • action： 重写地址

目前几乎所有的网络设备都可以在这个匹配+行动模式框架进行描述，具体化为各种网络设备包括未来的网络设备

网络层：控制平面

本章目标 ： 理解网络层 控制平面的 工作原理

• 传统路由算法
• SDN 控制器
• ICMP： Internet Control Message Protocol
• 网络管理（略）

以及他们在互联网上的实现和实例

在本章中，我们将通过包含网络层的控制平面组件来完成我们的网络层之旅。控制平面作为一种网络范围的逻辑，不仅控制沿着从源主机到目的主机的端到端路径间的路由器如何转发数据报，而且控制网络层组件和服务如何配置和管理。我们将包含传统的计算图中最低开销路径的路由选择算法。这些算法是两个广为部署的因特网路由选择协议OSPF和BGP的基础，OSPF是一种运行在单一ISP的网络中的路由选择算法。BCP是一种在因特网中用于互联所有网络的路由选择算法，因此常被称为因特网的“黏合剂”。传统上，控制平面功能与数据平面的转发功能在一起实现，在路由器中作为统一的整体。如我们在数据平面所学习的那样，软件定义网络（SDN)在数据平面和控制平面之间做了明确分割，在一台分离的“控制器”服务中实现了控制平面功能，该控制器服务与它所控制的路由器的转发组件完全分开并远离。我们将在本章中讨论SDN控制器。还将涉及管理IP网络的某些具体细节：ICMP(互联网控制报文协议）和SNMP(简单网络管理协议）。

导论

回顾 网络层的内容: 两个网络层功能

• 转发：将分组从路由器的一个输入端口移到一个合适的输出端口 -> 数据平面
• 路由：确定分组从 源端到目标端的路径 -> 控制平面

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

• 每个路由器控制功能实现（传统）
• 逻辑上集中的控制功能的实现 -> SDN

我们通过回顾图4-2和图4-3,迅速建立起学习网络控制平面的环境。在这里，我们看到了转发表（在基于目的地转发的场景中）和流表（在通用转发的场景中）是链接网络层的数据平面和控制平面的首要元素。我们知道这些表定义了一台路由器的本地数据平面转发行为。我们看到在通用转发的场景下，所采取的动作不仅包括转发一个分组到达路由器的每个输出端口，而且能够丢弃一个分组、复制一个分组和/或重写第2、3或4层分组首部字段。

在本章中，我们将学习这些转发表和流表是如何计算、维护和安装的。在网络层概述中，我们已经学习了完成这些工作有两种可能的方法。

• 每路由器控制。图5-1显示了在每台路由器中运行一种路由选择算法的情况，每台路由器中都包含转发和路由选择功能。每台路由器有一个路由选择组件，用于与其他路由器中的路由选择组件通信，以计算其转发表的值。这种每路由器控制的方法在因特网中已经使用了几十年。后面所学习的OSPF和BGP协议都是基于这种每路由器的方法进行控制的。

  

• 逻辑集中式控制。图5-2显示了逻辑集中式控制器计算并分发转发表以供每台路由器使用的情况。通用的“匹配加动作”抽象允许执行传统的IP转发以及其他功能（负载共享、防火墙功能和NAT)的丰富集合，而这些功能先前是在单独的中间盒中实现的。该控制器经一种定义良好的协议与每台路由器中的一个控制代理（CA)进行交互，以配置和管理该路由器的转发表。CA一般具有最少的功能，其任务是与控制器通信并且按控制器命令行事。与图5-1中的路由选择算法不同，这些CA既不能直接相互交互，也不能主动参与计算转发表。这是每路由器控制和逻辑集中式控制之间的关键差异。

  

路由选择算法

下面我们将介绍 路由选择算法（routing algorithm),其目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径（等价于路由）。

通常，一条好路径指具有最低开销的路径。然而我们将看到，实践中现实世界还关心诸如策略之类的问题（例如，有一个规则是“属于组织Y的路由器X不应转发任何来源于组织Z所属网络的分组”）。我们注意到无论网络控制平面采用每路由器控制方法，还是采用逻辑集中式控制方法，必定总是存在一条定义良好的一连串路由器，使得分组从发送主机到接收主机跨越网络“旅行”。因此，计算这些路径的路由选择算法是十分重要的，是最重要的10个十分重要的网络概念之一。

路由选择算法是指在计算机网络中，用于选择网络中最佳路径的算法。路由选择算法的目的是选择一条最佳路径，以便在网络中传输数据时，能够快速、可靠地到达目的地。

路由 （route）的概念

• 路由：按照某种 指标 （传输延迟、所经过的站点数）找到一条从 源节点到目标节点的 较好路径
  • 较好路径： 按照某种指标 的较小路径
  • 指标：站数、费用、延迟、或者一些指标的加权平均
  • 采用什么样的指标，表示网络使用者希望网络在什么方面表现突出，什么指标网络使用者比较重视
• 以 网络 为单位进行路由 （路由信息通告 + 路由计算）
  • 网络为单位进行路由，路由信息传输、计算和匹配的代价比较低
  • 前提条件是：一个网络的所有节点地址前缀相同，且物理上聚集
  • 路由就是 ：计算 网络到其他网络 如何走 的问题
• 网络到网络的 路由 = 路由器 - 路由器 之间的路由
  • 网络对应 的路由器到其他网络对应的路由器 的路由
  • 在一个网络中 ： 路由器 - 主机之间的通信，链路层解决
  • 到了这个路由器就是这个网络
• 路由选择算法 （routing algorithm）：网络层软件的一部分，完成路由功能

网络的 图抽象

图抽象：边和路径的代价

路由的输入：拓扑、边的代价、源节点

输出的输出：源节点的汇集树

最优化原则（optimality principle）

• 汇集树（sink tree)：
  • 此节点到所有其他节点的最优路径形成的树
  • 路由选择算法 就是为 所有的路由器 找到 并 使用汇集树

路由的原则

• 路由选择算法的原则
  • 正确性（correctness):算法必须是正确的和完整的，使分组一站一站接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项；没有处理不了的目标站地址；
  • 简单性（simplicity):算法在计算机上应简单：最优但复杂的算法，时间上延迟很大，不实用，不应为了获取路由信息增加很多的通信量；
  • 健壮性（robustness):算法应能适应通信量和网络拓扑的变化：通信量变化，网络拓扑的变化算法能很快适应；不向很拥挤的链路发数据，不向断了的链路发送数据；
  • 稳定性（stability):产生的路由不应该摇摆
  • 公平性（fairness):对每一个站点都公平
  • 最优性（optimality):某一个指标的最优，时间上，费用上，等指标，或综合指标；实际上，获取最优的结果代价较高，可以是次优的

路由算法分类

全局或者局部路由信息

全局

• 所有的路由器拥有完整的拓扑和 边的代价的 信息
• “link state” LS 链路状态算法

分布式

• 路由器只知道与他有物理连接关系的邻居路由器，和到相应邻居的代价值
• 迭代地与邻居交换路由信息、计算路由信息
• “distance vector” dv 距离向量算法

集中式路由选择算法（centralized routing algorithm)用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径。也就是说，该算法以所有节点之间的连通性及所有链路的开销为输入。这就要求该算法在真正开始计算以前，要以某种方式获得这些信息。计算本身可在某个场点进行，或在每台路由器的路由选择组件中重复进行。然而，这里的主要区别在于，集中式算法具有关于连通性和链路开销方面的完整信息。具有全局状态信息的算法常被称作链路状态（Link State,LS)算法因为该算法必须知道网络中每条链路的开销。在分散式路由选择算法（decentralized routing algorithm)中，路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息相反，每个节点仅有与其直接相连链路的开销知识即可开始工作。然后，通过迭代计算过程以及与相邻节点的信息交换，一个节点逐渐计算出到达某目的节点或一组目的节点的最低开销路径。之所以叫作DV算法，是因为每个节点维护到网络中所有其他节点的开销（距离）估计的向量。这种分散式算法，通过相邻路由器之间的交互式报文交换，也许更为天然地适合那些路由器直接交互的控制平面。

静态或者动态的

静态

• 路由随时间变化缓慢

动态

• 路由变化很快
  • 周期性更新
  • 根据链路代价变化而变化

非自适应算法（non-adaptive algorithm)不能适应网络拓扑和通信量的变化，路由表是事先计算好的

自适应路由选择（adaptive algorithm):能适应网络拓扑和通信量的变化

路由选择算法的第二种广义分类方式是根据算法是静态的还是动态的进行分类。在静态路由选择算法（static routing algorithm)中，路由随时间的变化非常缓慢，通常是人工进行调整（如人为手工编辑一条链路开销）。动态路由选择算法（dynamic routing algorithm)随着网络流量负载或拓扑发生变化而改变路由选择路径。一个动态算法可周期性地运行或直接响应拓扑或链路开销的变化而运行。虽然动态算法易于对网络的变化做出反应，但也更容易受诸如路由选择循环、路由振荡之类问题的影响。

补充

路由选择算法的第三种分类方式是根据它是负载敏感的还是负载迟钝的进行划分。在负载敏感算法（load-sensitive algorithm)中，链路开销会动态地变化以反映出底层链路的当前拥塞水平。如果当前拥塞的一条链路与高开销相联系，则路由选择算法趋向于绕开该拥塞链路来选择路由。而早期的ARPA net路由选择算法就是负载敏感的,所以遇到了许多难题。当今的因特网路由选择算法（如RIP、OSPF和BGP)都是负载迟钝的（load-insensitive),因为某条链路的开销不明确地反映其当前（或最近）的拥塞水平。

链路状态选择算法 - Link State

前面讲过，在链路状态算法中，网络拓扑和所有的链路开销都是已知的，也就是说可用作LS算法的输入。实践中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的，其中每个链路状态分组包含它所连接的链路的标识和开销。在实践中（例如使用因特网的OSPF路由选择协议，讨论见5.3节）,这经常由链路状态广播（link statebroadcast)算法[Perlman 1999]来完成。节点广播的结果是所有节点都具有该网络的统一、完整的视图。于是每个节点都能够像其他节点一样，运行LS算法并计算出相同的最低开销路径集合。

给出的算法是 Dijkstra 算法

它计算从某节点（源节点，我们称之为u)到网络中所有其他节点的最低开销路径。Dijkstra算法是迭代算法，其性质是经算法的第k 次迭代后，可知道到k个目的节点的最低开销路径，在到所有目的节点的最低开销路径之中，这k条路径具有k个最低开销。

LS 路由的工作过程

• 配置 LS 路由选择算法 的路由工作过程
  • 各点通过各种渠道获得 整个网络拓扑，网络中所有链路 代价 等信息（这部分和算法没有关系，属于协议和实现）
  • 使用 LS 路由算法，计算本站点到其他站点的 最优路径（汇集树），得到路由表
  • 按照 此路由表转发分组 （datagram 方式）
    • 严格意义上说不是一个路由的 一个步骤
    • 分发到输入端口的网络层

• LS 路由的基本工作过程

  1. 发现相邻节点，获知对方网络地址

     • 一个路由器上电之后，向所有线路发送 HELLO 分组

     • 其他路由器 收到 HELLO 分组，回送 响应，在应答分组中，告知自己的名字（全局唯一）

     • 在 LAN 中，通过广播 HELLO 分组，获得其他路由器的信息，可以认为 引入一个人工节点

       

  2. 测量到相邻节点的代价

     • 实测法，发送一个分组要求对方立即响应
     • 回送一个 ECHO 分组
     • 通过测量时间可以估算出 延迟情况

  3. 组装一个 LS 分组，描述它到相邻节点的代价情况

     • 发送者名称

     • 序号、年龄

     • 列表：给出他相邻节点，和它到相邻节点的 延迟

       

  4. 将分组通过 扩散的方法 发到所有其他路由器

     • 顺序号：用于控制无穷的 扩散，每个路由器都记录（源路由器，顺序号），发现重复的或老的就不扩散

       • q1:循环使用问题
       • 路由器崩溃之后序号从 0 开始
       • 序号出现错误

     • 解决的办法：年龄字段（age）

       • 生成一个分组时，年龄字段不为0
       • 每个一个 时间段，age 字段减一
       • age 字段为 0 的分组将被 抛弃

     • 关于扩散分组的 数据结构

       

     以上 4 步 让每个路由器获得 拓扑和边代价

  5. 通过 Dijkstra 算法 找出最短路径（这才是 路由算法）

     1. 每个节点独立算出来到其他节点（路由器=网络）的最短路径

        • 路由器获得各站点 LS 分组和整个网络的拓扑
        • 通过 Dijkstra 算法 计算出到其他各路由器的最短路径（汇集树）
        • 将计算结果安装到 路由表中

     2. 迭代算法： 第 K 步 能够知道本节点到 K 个其他节点的最短路径

     3. OSPF 协议是一种 LS 协议，被用于 Internet 上

• 符号标记

  

• LS 路由选择算法的工作原理

  

距离矢量算法 - Distance vector

距离矢量路由选择算法是一种基于距离估计的算法。在距离矢量路由选择中，每个路由器会维护到其它路由器的距离估计，并将其距离向相邻的路由器发送。然后，路由器根据接收到的距离信息和自身的距离估计更新路由表。距离矢量路由选择算法的缺点是收敛速度慢，容易出现路由环路。

• 动态算法之一

• DV 算法历史以及应用情况

  

• DV 的 基本思想

  • 各路由器维护一张路由表，结构如图

    

  • 各路由器与相邻路由器交换路由表（持续）

  • 根据获得的路由信息，更新路由表（持续）

• 代价以及相邻节点代价的获得

  • 跳数（hops),延迟（delay），队列长度
  • 相邻节点间代价的获得：通过实测

• 路由信息的 更新

  • 根据实测 得到本节点A到相邻站点的代价（如：延迟）
  • 根据各相邻站点声称它们到目标站点B的代价
  • 计算出本站点A经过各相邻站点到目标站点B的代价
  • 找到一个最小的代价，和相应的下一个节点Z,到达节点B经过此节点Z,并且代价为A-Z-B的代价
  • 其它所有的目标节点一个计算法

距离矢量（Distance-Vector,DV)算法是一种迭代的、异步的和分布式的算法，而LS算法是一种使用全局信息的算法。说它是分布式的，是因为每个节点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居。说它是迭代的，是因为此过程一直要持续到邻居之间 无更多信息要交换为止。（有趣的是，此算法是自我终止的，即没有计算应该停止的信号，它就停止了。）说它是异步的，是因为它不要求所有节点相互之间步伐一致地操作。我们将看到一个异步的、迭代的、自我终止的、分布式的算法比一个集中式的算法要有趣得多！

在给出 DV 算法之前，有必要讨论一下存在于最低开销路径的开销之间的一种重要关系。令d(y)是从节点x到节点y的最低开销路径的开销。则该最低开销与著名的Bellman-Ford 方程相关，即

在该分布式、异步算法中，每个节点 不时地 向它的每个邻居发送它的距离向量副本。当节点x从它的任何一个邻居，接收到一个新距离向量，它保存v的距离向量，然后使用Bellman-Ford方程 更新 它自己的距离向量如下：

如果节点x的距离向量因这个更新步骤而改变，节点x接下来将向它的每个邻居发送其更新后的距离向量，这继而让所有邻居更新它们自己的距离向量。令人惊奇的是，只要所有的节点继续以异步方式交换它们的距离向量，每个开销估计D(y)收敛到dx(y),d(y)为从节点x到节点y的实际最低开销路径的开销!

实际上节点具有的唯一信息是它到直接相连邻居的链路开销和它从这些邻居接收到的信息。每个节点等待来自任何邻居的更新（第10-11行）,当接收到一个更新时计算它的新距离向量(第14行）并向它的邻居分布其新距离向量（第16-17行）

从邻居接收更新距离向量、重新计算路由选择表项和通知邻居到目的地的最低开销路径的开销已经变化的过程继续下去，直到无更新报文发送为止。在这个时候，因为无更新报文发送，将不会出现进一步的路由选择表计算，该算法将进入静止状态，即所有的节点将执行DV算法的第10~11行中的等待。该算法停留在静止状态，直到一条链路开销发生改变，如下面所讨论的那样。

Bellman-Ford 方程（动态规划）

那个能够达到 目标 z 最小代价的节点 x ，就在到目标节点的 下一条路径上，在转发表中使用

距离矢量算法

核心思路

• 每个节点都将自己的距离矢量估计值传送给邻居，定时或者 DV 有变化时，让对方去算

• 当 X 从邻居收到 DV 时，自己运算，更新他的最大距离矢量

  • 采用 Bellmen-Ford equation

    

• Dx(Y) 估计值最终收敛于实际的最小代价值 dx（y）

  • 分布式、迭代算法

异步式、迭代：每次本地迭代被以下事件触发

• 每个节点只是在自己的 DV 改变之后向邻居通告
  • 然后他们的邻居在有必要的时候通知他们的邻居

每个节点：

DV 的无穷计算问题

• DV 的特点

  • 好消息传得快，坏消息传的慢

• 好消息的传播 以每一个交换周期 前进一个路由器的速度进行

  • 好消息：某个路由器接入 或者 有更短的路径

    

• 坏消息传播的 非常慢（无穷计算问题）

  • 

水平分裂（split horizon）算法

Split horizon算法是一种防止路由环路的技术，常用于距离矢量路由协议中。其主要思想是防止一个路由器将其从一个接口学习到的路由信息再次返回给该接口的源路由器，从而避免路由环路的发生。

具体来说，当一个路由器从一个接口学习到一条路由信息时，它会将该信息发送到其它的接口上，但不会将该信息发送回源路由器所在的接口。这样，当源路由器再次收到该信息时，它不会再将该信息发送回该路由器，从而避免了路由环路的发生。

Split horizon算法通常与距离矢量路由协议中的毒性反转技术（poison reverse）一起使用。在毒性反转技术中，一个路由器将其从某个接口学习到的路由信息发送回该接口时，会将该路由信息的距离值设为无穷大，从而告诉源路由器该路由已经失效。

总的来说，Split horizon算法是一种简单有效的防止路由环路的技术，常用于距离矢量路由协议中。

LS 和 DV 算法的比较

消息复杂度（DV胜出）

• LS ：有 N个 节点和 E 条链路，发送报文 O(NE) 个
  • 局部的路由信息，全局传播
• DV： 只和邻居 交换信息
  • 全局的路由信息，局部传播

收敛时间（LS 胜出）

• LS: O(n2) 算法
  • 有可能震荡
• DV： 收敛较慢
  • 有可能存在路由环路
  • count - to - infinity 问题

健壮性：路由器故障会发生什么？（LS 胜出）

• LS
  • 节点会通告 不正确的链路代价
  • 每个节点只计算自己的路由表
  • 错误信息影响较小，局部，路由较 健壮
• DV：
  • DV 节点可能通告对全网所有节点的不正确路径代价
    • 距离矢量
  • 每一个节点的路由表 可能被其他节点使用
    • 错误节点可以扩散到全网

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

在我们至今为止的算法研究中，我们将网络只看作一个互联路由器的集合。从所有路由器执行相同的路由选择算法以计算穿越整个网络的路由选择路径的意义上来说，一台路由器很难同另一台路由器区别开来。在实践中，该模型和这种一组执行同样路由选择算法的同质路由器集合的观点有一点简单化，有以下两个重要原因：

• 规模。随着路由器数目变得很大，涉及路由选择信息的通信、计算和存储的开销将高得不可实现。当今的因特网由数亿台主机组成。在这些主机中存储的路由选择信息显然需要巨大容量的内存。在所有路由器之间广播连通性和链路开销更新所要求的负担将是巨大的！在如此大量的路由器中迭代的距离向量算法将肯定永远无法收敛！显然，必须采取一些措施以减少像因特网这种大型网络中的路由计算的复杂性。
• 管理自治。因特网是ISP的网络，其中每个ISP都有它自己的路由器网络。ISP通常希望按自己的意愿运行路由器（如在自己的网络中运行它所选择的某种路由选择算法）,或对外部隐藏其网络的内部组织面貌。在理想情况下，一个组织应当能够按自己的愿望运行和管理其网络，还要能将其网络与其他外部网络连接起来。

这两个问题都可以通过将路由器组织进**自治系统（Autonomous System,AS)**来解决其中每个AS由一组通常处在相同管理控制下的路由器组成。通常在一个ISP中的路由器以及互联它们的链路构成一个AS。然而，某些ISP将它们的网络划分为多个AS。特别是某些一级ISP在其整个网络中使用一个庞大的AS,而其他ISP则将它们的ISP拆分为数十个互联的AS。一个自治系统由其全局唯一的AS号（ASN)所标识。就像IP地址那样，AS号由ICANN区域注册机构所分配。

在相同AS中的路由器都运行相同的路由选择算法并且有彼此的信息。在一个自治系统内运行的路由选择算法叫作自治系统内部路由选择协议（intra-autonomous system routing protocol)。

RIP（Routing Information Protocol）

• 在 1982 年发布的 BSD-UNIX 中实现
• Distance Vector 算法
  • 距离矢量：每条链路 cost = 1 ,# of hops (max = 15 hops) 跳数
  • DV 每隔30 s 和邻居交换 DV，通告
  • 每个通告包括：最多 25 个目标子网

RIP 通告（advertisements）

• DV ：在邻居之间每 30 s 交换通告报文
  • 定期，而且在改变路由的时候发送通告报文
  • 在对方的请求下可以发送 通告报文
• 每一个通告：至多 AS 内部的 25 个目标网络的 DV
  • 目标网络 + 跳数
    • 一次公告最多 25 个子网，最大跳数为 16 hop

RIP ：链路失效和恢复

如果 180 秒没有收到通告信息 –> 邻居或者链路失效

• 发现经过这个邻居的路由已经失效

• 新的通告报文会传递给邻居

• 邻居因此发出新的通告（如果路由有变化的话）

• 链路失效快速（？）地在链路传输

• 使用 毒性逆转 （Poison reverse） 阻止 ping-pong 回路（不可达的距离：跳数无限 = 16段）

  • 毒性逆转（poison reverse）是一种距离矢量路由协议中的技术，用于防止路由环路的发生。当一条链路或节点出现故障时，毒性逆转可以迅速告知其它节点该路由不可达，防止路由环路的产生。

    具体来说，当一个路由器发现某个路由不可达时，它会将该路由的距离值设为无穷大（infinity），并将该路由信息向其它节点发送。这样，其它节点就会知道该路由不可达，并将其从其路由表中删除。如果没有使用毒性逆转，那么该路由信息会一直存在于网络中，可能会导致路由环路的产生。

    毒性逆转通常与Split horizon算法一起使用，Split horizon算法可以防止一个节点将其从一个接口学习到的路由信息再次返回给该接口的源路由器，从而避免路由环路的发生。

    总的来说，毒性逆转是一种距离矢量路由协议中的技术，可以迅速告知其它节点某个路由不可达，防止路由环路的产生。它通常与Split horizon算法一起使用，可以提高路由选择协议的稳定性和可靠性。

RIP 进程处理

• RIP 以应用进程的方式实现：route-d(daemon)
• 通告报文 通过 UDP 报文传送，周期性重复
• 网络层的协议使用了传输层的服务，以应用层实体的方式实现

OSPF（Open Shortest Path First)

OSPF（Open Shortest Path First）是一种链路状态路由选择协议，用于在大型企业网络和互联网中进行路由选择。OSPF协议适用于IPv4和IPv6网络。

OSPF协议使用链路状态算法来选择最佳路径，即将网络中的所有链路和路由器的状态信息发送给相邻的路由器，然后计算最短路径并更新路由表。OSPF协议使用路由器ID来标识每个路由器，每个路由器维护一个链路状态数据库（LSDB），其中包含了网络中所有链路和路由器的状态信息。

OSPF协议的主要特点包括：

1. 高效：OSPF协议使用链路状态算法，可以快速计算最短路径，并快速适应网络拓扑的变化。

2. 灵活：OSPF协议支持可变长度子网掩码（VLSM），可以处理不同子网掩码的网络。

3. 可靠：OSPF协议使用可靠的邻居关系协议（Neighbor Protocol），可以确保邻居关系的稳定性和可靠性。

4. 安全：OSPF协议支持认证机制，可以对路由器进行身份认证和数据加密，提高网络的安全性。

总的来说，OSPF协议是一种高效、灵活、可靠和安全的路由选择协议，适用于大型企业网络和互联网。OSPF协议的实现相对复杂，需要一定的配置和管理，但可以提供更高级别的路由选择功能和更好的网络性能。

• “open” ：标准可公开获得

• 使用 LS算法

  • LS 分组在网络中 （一个 AS 内部）分发
  • 全局网络拓扑、代价在每一个 节点中都保持
  • 路由计算使用 Dijkstra 算法

• OSPF 通告信息中携带：每一个路由器一个表项

• 通告信息会传遍 AS 全部（通过泛洪）

  • 在 IP 数据报上直接传送 OSPF 报文（而不是通过 TCP、UDP）

• IS-IS 路由协议：几乎和 OSPF 一样

  • IS-IS（Intermediate System to Intermediate System）是一种内部网关协议（IGP），用于在中等规模的企业网络和互联网中进行路由选择。IS-IS协议适用于IPv4和IPv6网络。

    IS-IS协议使用链路状态算法来选择最短路径，即将网络中的所有链路和路由器的状态信息发送给相邻的路由器，然后计算最短路径并更新路由表。IS-IS协议使用系统ID来标识每个路由器，每个路由器维护一个链路状态数据库（LSDB），其中包含了网络中所有链路和路由器的状态信息。

    IS-IS协议的主要特点包括：

    1. 高效：IS-IS协议使用链路状态算法，可以快速计算最短路径，并快速适应网络拓扑的变化。

    2. 灵活：IS-IS协议支持可变长度子网掩码（VLSM），可以处理不同子网掩码的网络。

    3. 可靠：IS-IS协议使用可靠的邻居关系协议（Neighbor Protocol），可以确保邻居关系的稳定性和可靠性。

    4. 安全：IS-IS协议支持认证机制，可以对路由器进行身份认证和数据加密，提高网络的安全性。

    总的来说，IS-IS协议是一种高效、灵活、可靠和安全的路由选择协议，适用于中等规模的企业网络和互联网。IS-IS协议的实现相对复杂，需要一定的配置和管理，但可以提供更高级别的路由选择功能和更好的网络性能。

OSPF 高级特性

• 安全：所有的 OSPF 报文都是经过认证的（防止恶意的攻击）

• 允许 有 多个代价相同的 路径存在（在 RIP 中只有一个）

• 对于每一个链路，对于不同的 TOS 有 多重代价矩阵

  • 在计算机网络中，链路的代价指的是传输数据的开销，通常表示为距离、带宽、延迟等。当网络中存在多个链路时，每个链路的代价可能不同，因此需要为每个链路定义一个代价矩阵来表示不同类型的代价。

    在某些网络中，不同类型的数据流（如语音、视频、数据等）可能需要优先考虑不同的代价因素。为了满足这种需求，网络协议可以为每种类型的流量定义不同的代价矩阵，称为多重代价矩阵（Multiple Cost Matrix）。

    以OSPF协议为例，OSPF协议为每个链路定义了一个代价值，用于计算最短路径。在OSPF中，每个链路还可以为不同类型的服务定义不同的代价值，称为TOS（Type of Service）代价。例如，语音数据可能需要优先考虑传输延迟，而数据传输可能更注重带宽。因此，OSPF协议可以为每个链路定义多个TOS代价，用于计算不同类型的数据流的最短路径。

    总的来说，多重代价矩阵是用于在网络中为不同类型的数据流设置不同的代价值，以便计算不同类型数据流的最短路径。这种技术可以提高网络的性能和服务质量，并满足不同类型数据流的需求。

• 对 单播和多播的 集成支持

  • Multicast OSPF（MOSPF） 使用相同的 拓扑数据库，就像在 OSPF 中一样

• 在 大型网络中 支持 层次性 OSPF

  • 
  • 两个级别的层次性：本地、骨干
    • 链路状态通告 仅仅在 本地区域 Area 范围内进行
    • 每一个节点拥有本地 区域的拓扑信息
      • 关于其他区域，知道去他的方向，通过区域边界路由器（最短路径）
  • 区域边界路由器：”汇集“ 到自己区域内 网络的距离，向其他区域边界路由器通告
  • 骨干路由器：仅仅在骨干区域内，运行 OSPF 路由
  • 边界路由器：连接其他 AS

ISP 之间的路由选择：BGP

层次路由

• 一个平面的路由
  • 一个网络中的所有路由器的地位都一样
  • 通过 LS、DV，或者其他的路由算法，所有的路由器都知道其他所有路由器（子网）应该怎么走
  • 所有路由器在一个平面
• 平面路由的问题
  • 规模 巨大的网络中，路由信息的存储、传输和计算代价过大
    • DV：距离矢量很大，且不能够收敛
    • LS：几百万个节点的 LS 分组的泛洪传输，存储以及最短路径的计算问题
  • 管理问题：
    • 不同的网络所有者希望按照自己的方式管理网络
    • 希望对外隐藏自己网络的细节
    • 当然，还希望和其他网络互联
• 层次路由：将互联网分成一个个 AS（路由器区域）
  • 某个区域内的路由器集合，自治系统
  • 一个 AS 用AS Number 唯一标识 （ASN）
  • 一个 ISP 可能包括一个 或者 多个 AS
• 路由 变成了：2 个 层次路由
  • AS内部路由 ：在同一个 AS 内部路由器运行相同的路由协议
    • **“intra-AS” routing protocol **:内部网关协议
    • 不同的AS 可能运行着不同内部网关的协议
    • 能够解决规模和管理问题
    • 网关路由器：AS 边缘路由器，可以连接到其他的 AS
  • AS 之间运行 AS间路由协议
    • **“int-AS” routing protocol **:外部网关协议
    • 解决 AS 之间的路由问题，完成 AS 之间的互联互通

层次路由的优点

• 解决了规模问题
  • 内部网关协议解决：AS 内部 数量有限的 路由器相互到达的问题，AS 内部规模可控
• AS 之间路由的规模问题
  • 增加一个 AS，对于 AS 之间的路由从 总体上来说，只是增加了一个节点 = 子网（每个AS 可以用一个点来表示）
  • 对于其他的AS来说只是增加了一个 表项，就是这个新增的AS 如何走的问题
  • 扩展性强：规模增大，性能不会减得太多
• 解决了管理问题
  • 各个 AS 之间可以运行不同的 内部网关协议
  • 可以使自己的网络不向外部暴露细节

互联网AS间路由：BGP

是一种互联网路由协议，用于在不同自治系统之间进行路由选择。BGP协议主要用于大规模企业网络、运营商网络以及互联网服务提供商（ISP）之间的路由选择。

BGP协议的主要作用是将路由信息从一个自治系统（AS）传递到另一个自治系统，以便实现全球互联网的路由选择。BGP协议使用TCP协议进行通信，并支持多种路由策略，如路由过滤、路由聚合、路由重分发等。

• BGP（Border Gateway Protocol） ：自治区域路由协议 “事实上的标准”
  • “将互联网各个 AS 粘在一起 的胶水”
• BGP 提供给每个 AS 以下方法
  • eBGP: 从相邻的ASes 那里获得子网可达信息
  • iBGP:将 获得的子网可达信息传遍 AS内部的所有路由器
  • 根据子网可达信息和 策略 来决定到达子网的 “好路径”
• 允许子网向互联网其他网络通告 “我在这里”
• 基于 DV 算法
  • 不仅仅是DV，还包括到达各个目标网络的详细路径（AS序号的列表）能够避免 DV 的路由环路问题

BGP协议的工作原理如下：

1. BGP协议通过向对等的BGP路由器发送UPDATE消息来传递路由信息。

2. UPDATE消息包括路由的网络地址、AS号码和其他属性信息。

3. BGP路由器使用路由策略选择最优的路由，并将其添加到自己的路由表中。

4. 如果路由器发现某个路由不再可达，它将从自己的路由表中删除该路由，并向其它BGP路由器发送WITHDRAW消息。

BGP协议的主要特点包括：

1. 支持多种路由策略，如路由过滤、路由聚合、AS路径选择等。

2. 可以跨越多个自治系统进行路由选择，支持互联网规模的路由选择。

3. 支持路由决策的可扩展性和灵活性。

4. 支持路由信息的安全性和稳定性，如路由过滤、MD5认证等。

总的来说，BGP协议是一种用于在不同自治系统之间进行路由选择的协议，是实现全球互联网的重要技术之一。BGP协议具有高度的可扩展性和灵活性，但实现和管理比较复杂，需要一定的网络知识和经验。

BGP 基础

• BGP 会话：两个BGP 路由器（“peers”）在一个半永久的TCP 连接上 交换 BGP 报文
  • 通告向不同目标子网前缀的 “路径” （BGP 是一个 DV 协议）
• 

路径的属性 & BGP 路由

• 当通告一个子网前缀时，通告包括 BGP 属性
  • prefix + attributes = "route"
• 两个重要的属性
  • **AS - PATH **: 前缀通告所经过的 AS 列表：AS 67 AS 17
    • 检测环路：多路径选择
    • 在向其他 AS 转发时，需要将自己的 ASN 加在路径上面
  • NEXT-HOP：从 当前AS 到下一跳AS 有多个链路，在 next-hop 属性中，告诉对方通过那个 I 转发
  • 其他属性：路由偏好指标，如何被插入的属性
• 基于 策略 的路由
  • 当一个 网关路由器 接收到了一个路由通告，使用 输入策略 来接受或者 过滤（accept/ decline)
    • reason1:不想经过某个 AS，转发某些前缀的 分组
    • reason2：已经有了通往某前缀路径的偏好路径
  • 策略也决定了是否向他的邻居通告收到的这个信息

BGP 路径通告

• 路由器AS2.2c从AS3.3a接收到的AS3,X路由通告（通过eBGP)
• 基于AS2的输入策略，AS2.2c决定接收AS3,X的通告，而且通过iBGP)向AS2的所有路由器进行通告
• 基于AS2的策略，AS2路由器2a通过eBGP向ASI.lc路由器通告AS2,AS3,X 路由信息
  • 路径上加上了AS2自己作为AS序列的一跳

网关路由器可能获取有关一个子网X的多条路径，从多个eBGP会话上：

• AS1网关路由器1c从2a学习到路径：AS2,AS3,X
• AS1网关路由器1c从3a处学习到路径AS3,X
• 基于策略，AS1路由器1c选择了路径：AS3,X,而且通过iBGP告诉所有AS1内部的路由器

BGP 报文

• 使用 TCP 协议交换 BGP 报文
• BGP 报文
  • OPEN：打开TCP 连接，认证发送方
  • UPDATE：通告新路径（或者撤销新路径）
  • KEEPALIVE：在没有更新时保持连接，也用于对 OPEN 请求确认
  • NOTIFICATION：报告以前消息的错误，也用来关闭连接

BGP、OSPF 转发表表项

BGP 路径选择

• 路由器可能获得一个网络前缀的多个路径，路由器必须进行路径的选择，路由选择可以基于：
  • 本地偏好值属性：偏好策略决定
  • 最短AS-PATH:AS的跳数
  • 最近的NEXT-HOP路由器：热土豆路由
  • 附加的判据：使用BGP标示
• 一个前缀对应着多种路径，采用消除规则直到留下一条路径

热土豆策略

2d通过iBGP获知，它可以通过2a或者2c到达X

热土豆策略：选择具备最小内部区域代价的网关作为往X的出口（如：2d选择2a,即使往X可能有比较多的AS跳数）:不要操心域间的代价！

热土豆策略（Hot Potato Routing）是一种网络路由策略，用于快速转发数据包到目标节点，以最小化网络延迟和传输时间。热土豆策略的基本思想是将数据包发送给最近的可用节点，以便快速到达目标节点。在热土豆策略中，每个节点都会评估到达目标节点的最短路径，并将数据包发送给最近的节点，而不是等待最佳路径。

热土豆策略的工作流程如下：

1. 当一个节点接收到一个数据包时，它会计算到达目标节点的最短路径，并将数据包发送给这条路径上最近的节点。

2. 如果当前节点没有直接连接到目标节点的最短路径上，它会将数据包发送给距离目标节点最近的节点，并等待该节点将数据包转发给下一个最近的节点，直到数据包到达目标节点。

3. 如果目标节点没有响应或不可达，数据包会被返回给发送方，或者被丢弃。

热土豆策略的主要优点是快速传输数据包，从而降低网络延迟和传输时间。它还可以提高数据包的可靠性和稳定性，因为即使某个节点出现故障，数据包仍然可以通过其他路径到达目标节点。但是，热土豆策略也存在一些缺点，如可能导致网络拥塞和负载不均衡等问题。

总的来说，热土豆策略是一种网络路由策略，用于快速传输数据包到目标节点，可以提高网络性能和数据传输的可靠性。

BGP 通过路径通告执行策略

假设一个ISP只想路由流量到/去往它的客户网络（不想承载其他ISPs之间的流量，即不通告：不是去往我的客户，也不是来自我的客户）

• A向B和C通告路径AW
• B选择不向C通告BAw:
  • B从CBAw的路由上无法获得收益，因为C,A,w都不是B的客户
  • C从而无法获知 CBAw路径的存在：每个ISP感知到的网络和真实不一致
• C可能会通过CAw(而不是使用B)最终路由到W

为什么内部网关协议和外部网关协议如此不同

SDN

数据平面已经叙述过，不再叙述

ICMP：Internet 控制报文协议

ICMP（Internet Control Message Protocol）是一种网络协议，用于在互联网上发送错误和控制消息，以及测试网络的连通性和性能。ICMP协议通常与IP协议一起使用，用于处理网络层的错误和控制信息。

ICMP协议的主要作用包括：

1. 发送错误消息：当IP数据包在传输过程中出现错误时，ICMP会发送错误消息给源节点，以便重新发送数据包或采取其他措施。

2. 发送控制消息：ICMP还可以发送控制消息，如请求和响应消息，用于测试网络的连通性和性能，如ping命令就是基于ICMP协议实现的。

3. 实现路由选择：ICMP还可以用于路由选择，例如当路由器无法找到目标节点时，将发送ICMP重定向消息告诉源节点选择更优路径。

ICMP协议的常见消息类型包括：

1. 回显请求和回显应答（Echo Request和Echo Reply）：用于测试网络的连通性和性能，如ping命令就是基于这种消息类型实现的。

2. 目标不可达（Destination Unreachable）：用于告诉源节点目标节点不可达或不存在。

3. 超时（Time Exceeded）：用于告诉源节点数据包在传输过程中已经超时或过期。

4. 重定向（Redirect）：用于告诉源节点选择更优路径。

总的来说，ICMP协议是一种用于在互联网上发送错误和控制消息的网络协议，可以用于测试网络的连通性和性能，以及实现路由选择等功能。在网络故障排除和网络性能测试中，ICMP协议是一个重要的工具和协议。

Traceroute and ICMP

Traceroute是一种网络诊断工具，用于检测数据包从源节点到目标节点所经过的路由路径，并测量每个节点的延迟时间。Traceroute通常基于ICMP协议实现，使用ICMP报文作为探测数据包。下面分别介绍Traceroute和ICMP的工作原理。

Traceroute的工作原理：

1. 在Traceroute开始时，它向目标节点发送第一个探测数据包，该数据包的TTL（Time-To-Live）值设置为1。

2. 当第一个探测数据包到达第一个路由器时，TTL值变为0，该路由器会将ICMP超时消息返回给源节点。这个ICMP消息包含了第一个路由器的IP地址。

3. Traceroute收到第一个路由器的ICMP消息后，它将向目标节点发送第二个探测数据包，TTL值设置为2。

4. 第二个探测数据包到达第二个路由器时，TTL值变为0，该路由器同样会将ICMP超时消息返回给源节点，包含了第二个路由器的IP地址。

5. Traceroute重复上述步骤，逐渐增加TTL值，直到到达目标节点，或者TTL值超过了一定的阈值，Traceroute将停止探测。

6. 最终，Traceroute将显示所有经过的路由器的IP地址和延迟时间，以及到达目标节点的总延迟时间。

ICMP的工作原理：

1. ICMP协议通常与IP协议一起使用，在IP数据包传输过程中，当出现错误或控制信息时，ICMP会发送消息给源节点或其他网络节点。

2. ICMP消息通常包含类型码和代码字段，用于指示消息类型和具体信息。例如，Echo Request和Echo Reply是ICMP的一种类型，用于测试网络的连通性和性能。

3. ICMP还可以用于路由选择，例如当路由器无法找到目标节点时，将发送ICMP重定向消息告诉源节点选择更优路径。

总的来说，Traceroute是一种基于ICMP协议实现的网络诊断工具，用于检测数据包从源节点到目标节点所经过的路由路径，并测量每个节点的延迟时间。ICMP协议是一种用于在互联网上发送错误和控制消息的网络协议，可以用于发送探测数据包、路由选择等功能。在网络故障排除和网络性能测试中，Traceroute和ICMP协议是重要的工具和协议。

网络管理

“网络管理”

包括了硬件、软件和人类元素的设置，综合和协调，以便监测，测试，轮询，配置，分析，评价和控制网络和网元资源，用合理的成本满足实时性，运行能和服务质量的要求；

网络管理的 5 大功能

网络管理架构

SNMP 协议

SNMP（Simple Network Management Protocol）是一种用于网络管理的协议，它提供了一套标准的方法，以便管理和监控网络设备和系统。SNMP协议通常用于网络设备的远程管理和监控，如路由器、交换机、服务器等。

SNMP协议的主要作用包括：

1. 监控网络设备和系统的状态：SNMP可以获取网络设备和系统的状态信息，如CPU利用率、内存使用率、网络流量等。

2. 配置网络设备和系统：SNMP可以修改网络设备和系统的配置参数，如修改路由表、修改系统参数等。

3. 监控网络性能和故障：SNMP可以监控网络的性能和故障，如检测网络中的故障、分析网络流量等。

SNMP协议的工作原理如下：

1. SNMP管理器（Manager）：它是一个用于管理网络设备和系统的计算机程序，它通过SNMP协议与SNMP代理（Agent）进行通信，以获取设备和系统的状态信息。

2. SNMP代理（Agent）：它是一个运行在网络设备和系统上的程序，它可以获取设备和系统的状态信息，并将这些信息发送给SNMP管理器。

3. SNMP MIB（Management Information Base）：它是一个用于存储和管理网络设备和系统的状态信息的数据库，包含了一系列标准的对象和属性，可以通过SNMP协议进行访问和修改。

4. SNMP协议：它是一种用于管理和监控网络设备和系统的协议，包括SNMP协议的版本、消息格式、消息类型等。

SNMP协议的主要优点包括：

1. 可扩展性：SNMP可以扩展到支持新的设备和系统，并且可以通过添加新的MIB对象来支持新的功能。

2. 简单易用：SNMP协议具有简单的消息格式和操作，易于实现和使用。

3. 标准化：SNMP协议是一个标准化的协议，可以在不同厂商的设备和系统之间进行互操作。

总的来说，SNMP协议是一种用于网络管理和监控的协议，可以获取设备和系统的状态信息、配置设备和系统、监控网络性能和故障等。SNMP协议具有可扩展性、简单易用和标准化等优点，是网络管理和监控的重要工具和协议。

SNMP 协议 报文类型

总结

• 网络层控制平面的方法
  • 每个路由器控制
  • 逻辑上集中控制
• 传统路由选择算法
  • 在互联网上的实现 ：RIP、OSPF、BGP
• SDN 控制器
  • 实际中的实现：ODL、ONOS
• ICMP
• 网络管理和SNMP 协议

链路层和局域网

导引：

• 网络层解决了 一个网络如何到达另一个网络的路由问题
• 在一个网络内部如何由一个节点（主机或者路由器）到达另一个相邻的节点
  • 链路层的 点到点 传输层功能

在网络层中，我们学习了网络层提供的任意两台主机之间的通信服务。在两台主机之间，数据报跨越一系列通信链路传输，一些是有线链路，而一些是无线链路，从源主机起始，通过一系列分组交换机（交换机和路由器）,在目的主机结束。

当我们沿协议栈继续往下，从网络层到达链路层，我们自然而然地想知道

• 分组是如何通过构成端到端通信路径的各段链路的。
• 为了在单段链路上传输，网络层的数据报是怎样被封装进链路层帧的呢？
• 沿此通信路径，不同的链路能够采用不同的链路层协议吗？在广播链路中传输碰撞是如何解决的？
• 在链路层存在编址吗？如果需要，链路层编址如何与我们在第4章中学习的网络层编址一起运行呢？
• 交换机和路由器之间到底有哪些差异？

我们将在本章回答这些和其他一些重要的问题。在链路层的讨论中，我们将看到两种截然不同类型的链路层信道。第一种类型是广播信道，这种信道用于连接有线局域网、卫星网和混合光纤同轴电缆（Hybrid Fiber Coaxialcable,HFC)接入网中的多台主机。因为许多主机与相同的广播信道连接，需要所谓的媒体访问协议来协调帧传输。在某些场合中，可以使用中心控制器来协调传输。第二种类型的链路层信道是点对点通信链路，这在诸如长距离链路连接的两台路由器之间，或用户办公室计算机与它们所连接的邻近以太网交换机之间等场合经常能够发现。协调对点对点链路的访问较为简单；点到点协议（Point-to-Point Protocol,PPP),该协议的适用范围从经电话线的拨号服务到经光纤链路的高速点到点帧传输。

目标：

• 理解 数据链路层 服务的 原理
  • 检错和纠错
  • 共享广播信道：多点接入（多路访问）
  • 链路层寻址
  • LAN ：以太网、WLAN、VLANs
  • 可靠数据传输，流控制： 解决
• 实例和各种链路层技术的实现

在计算机网络中，链路层（Data Link Layer）是网络协议栈中的第二层，它位于物理层之上，网络层之下。链路层的主要作用是将网络层传递下来的数据包转换为物理层可传输的比特流，并将接收到的比特流转换为网络层可识别的数据包。

链路层的功能主要包括以下几个方面：

1. 封装成帧：链路层将网络层传递下来的数据报封装成帧，添加首部和尾部，并在帧中加入必要的控制信息（如帧起始标志、帧类型、帧校验和等）。

2. 媒体访问控制：链路层负责媒体访问控制，即协调多个节点对共享媒体（如以太网）的访问，防止碰撞和冲突，并保证数据的可靠传输。

3. 差错控制：链路层通过帧校验和等机制，检测和纠正传输中的差错，保证数据的可靠传输。

4. 流量控制：链路层可以根据网络拓扑和节点的处理能力，控制数据的流量，避免网络拥塞和资源浪费。

5. 链路管理：链路层可以管理和监控链路状态，包括链路的连接和断开、链路速率的协商、链路质量的评估等。

常见的链路层协议包括以太网（Ethernet）、无线局域网（Wi-Fi）、令牌环网（Token Ring）等。不同的链路层协议有不同的帧格式和控制机制，但它们都具有封装成帧、媒体访问控制、差错控制、流量控制和链路管理等基本功能。

总的来说，链路层是计算机网络协议栈中的重要组成部分，它负责将网络层传递下来的数据报封装成帧，并管理和控制数据在链路上传输的过程。链路层的正常工作对于整个网络的性能和可靠性具有重要影响。

链路层概述

我们先了解一下相关术语，方便本章的讨论；我们将 运行链路层 协议的 任何设备 均称为 节点（node）。节点包括主机、路由器、交换机和 WIFI 接入点。也把 沿着通信路径连接相邻节点的通信信道 称为 链路（link）

数据链路层和局域网

• WLAN : 网络形式采用 点到点链路
  • 带宽大、距离远（延迟大）
    • 宽带延迟积大
  • 如果采用多点连接方式
    • 竞争方式：一旦冲突 -> 代价大
    • 令牌等协调方式：在其中协调节点的发送代价大
• 点到点链路的链路层服务实现非常简单，封装和解封装
• LAN 一般采用 多点连接的方式
  • 连接节点非常方便
  • 接到共享介质上（或者网络交换机），就可以连接所有其他节点
• 多点连接方式网络的链路层功能实现相当复杂
  • 多点接入：协调各节点对共享介质的访问和使用
  • 竞争方式：冲突之后的协调
  • 令牌方式：令牌产生，占有和释放等

链路层：上下文

• 数据报（分组）在不同的链路上 以不同的链路协议传输
  • 第一跳链路：以太网
  • 中间链路：帧中继链路
  • 最后一跳 802.11
• 不同的链路层协议提供不同的服务
  • 比如在 链路层 （没有或有）提供 数据可靠传送

链路层服务

• 成帧，链路接入

  • 将数据报 封装在帧中，加上帧头、帧尾
  • 如果采用的是共享性介质，信道接入或者信道访问权
  • 在 帧头部 使用 MAC 地址来标识源和目的
    • 不同于 IP 地址

• 在（一个网络内）相邻两个节点完成可靠数据传递

  • 在低出错率的链路上（光纤和双绞线电缆）很少使用

  • 在无线链路上经常使用：出错率高

    • 为什么在链路层和传输层都实现了可靠性

      一般化的链路层服务，不是所有链路层都提供这些服务，一个特定的链路层只是提供其中一部分的服务

• 在相邻节点间（一个子网内）进行可靠的转发

  

• 流量控制

  • 使得相邻发送和接收方节点的速度匹配

• 错误检测

  • 差错由信号衰减和噪声引起
  • 接收方检测到差错
    • 通知发送端进行重传或者丢弃帧

• 差错纠正

  • 接收端检查和 纠正 bit 错误，不通过重传来 纠正错误

• 半双工和全双工

  • 半双工：链路可以双向传输，但一次只有一个方向

链路层在何处实现

图6-2显示了一个典型的主机体系结构。链路层的主体部分是在网络适配器（networkadapter)中实现的，网络适配器有时也称为网络接口卡（Network Interface Card,NIC)。位于网络适配器核心的是链路层控制器，该控制器通常是一个实现了许多链路层服务（成帧、链路接入、差错检测等）的专用芯片。因此，链路层控制器的许多功能是用硬件实现的。

在发送端，控制器取得了由协议栈较高层生成并存储在主机内存中的数据报，在链路层中封装该数据报（填写该帧的各个字段），然后遵循链路接入协议将该帧传进通信链路中。 在接收端，控制器接收了整个帧，抽取出网络层数据报。 如果链路层执行差错检测，则需要发送端在首部设置 差错检测比特，由 接收控制器 执行差错检测

差错检测和纠正

在上一节中，我们提到了比特级差错检测和纠正（bit-level error detection and correc-tion),即对从一个节点发送到另一个物理上连接的邻近节点的链路层帧中的比特损伤进行检测和纠正，它们通常是链路层提供的两种服务。

图6-3图示说明了我们研究的环境。在发送节点，为了保护比特免受差错，使用差错检测和纠正比特（Error-Detection and-Correction,EDC)来增强数据D。通常，要保护的数据不仅包括从网络层传递下来需要通过链路传输的数据报，而且包括链路帧首部中的链路级的寻址信息、序号和其他字段。链路级帧中的D和EDC都被发送到接收节点。在接收节点，接收到比特序列D’和EDC’。注意到因传输中的比特翻转所致，D’和EDC’可能与初始的D和EDC不同。

接收方的挑战是 在他只收到 D‘ 和 EDC’ 的情况下，确定D’ 是否和初始的 D 相同。接收方判断的 准确措辞： 我们问是否检测到一个差错，而非是否出现了差错

差错检测和纠正技术使接收方有时但并总是检测出已经出现的比特差错。即使采用差错检测比特，也还是可能有未检出比特差错（undetected bit error);这就是说，接收方可能无法知道接收的信息中包含着比特差错。因此，接收方可能向网路层交付一个损伤的数据报，或者不知道该帧首部的某个其他字段的内容已经损伤。一般而言，差错检测和纠错技术越复杂(即那些具有未检测出比特差错概率较小的技术）,导致的开销就越大，这就是意味着需要更多的计算量及更多的差错检测和纠错比特。

我们现在来研究在传输数据中检测差错的3种技术：

• 奇偶校验（它用来描述差错检测和纠正背后隐含的基本思想）
• 检验和方法（它通常更多地应用于运输层）
• 循环冗余检测（它通常更多地应用在适配器中的链路层）。

奇偶校验

奇偶校验（Parity Check）是一种简单的差错检测技术，常用于串行传输中。在奇偶校验中，发送方会在数据中添加一个附加位（称为校验位），使得数据中1的个数成为偶数（偶校验）或奇数（奇校验）。接收方在接收数据后，会重新计算校验位，如果计算出的校验位与接收到的校验位不一致，则说明数据传输出错。

采用单个奇偶校验位方式，接收方的操作也很简单。接收方只需要数一数接收的d+1比特中1的数目即可。如果在采用偶校验方案中发现了奇数个值为1的比特，接收方知道至少出现了一个比特差错。更精确的说法是，出现了奇数个比特差错。

奇偶校验的原理很简单。以奇校验为例，假设发送方要传输一个8位二进制数10110110，那么发送方会在数据的最高位添加一个附加位，使得数据中1的个数为奇数。由于10110110中有4个1，因此发送方在最高位添加一个1，得到110110110，这就是传输的数据。在接收方，接收到数据后，会重新计算校验位，如果计算出的校验位与接收到的校验位不一致，则说明数据传输出错。

奇偶校验是一种简单的差错检测技术，它可以检测一位错误，但无法检测两位或更多的错误。并且，奇偶校验只能用于检测数据传输中的单比特错误，不能检测其他类型的错误，如漏字、重复字、失序等。因此，在实际应用中，奇偶校验常与其他差错检测技术（如循环冗余校验）结合使用，以提高数据传输的可靠性。

总的来说，奇偶校验是一种简单的差错检测技术，它可以检测数据传输中的单比特错误，但无法检测其他类型的错误。在串行传输中，奇偶校验常用于保证数据传输的可靠性。

二维奇偶校验

二维奇偶校验（Two-dimensional Parity Check）是一种常见的差错检测技术，它可以检测数据传输中的多个比特错误，并且可以同时检测行错误和列错误。

在二维奇偶校验中，发送方将数据按照固定的行列分组，在每个分组中添加一个附加位，使得该分组中1的个数为偶数（偶校验）或奇数（奇校验）。接收方在接收数据后，会重新计算每个分组的校验位，并对所有的校验位进行校验。如果某个分组的校验位与接收到的校验位不一致，则说明该分组发生了错误。

以4×4的矩阵为例，假设发送方要传输以下数据：

1
2
3
4

1 0 1 1
0 1 0 1
1 0 1 0
0 1 1 0

发送方会将数据按照行列分组，并在每个分组中添加一个附加位，使得该分组中1的个数为偶数。添加附加位后的数据如下：

1
2
3
4
5

1 0 1 1 1
0 1 0 1 0
1 0 1 0 1
0 1 1 0 0
1 1 0 0 1

在接收方，接收到数据后，会重新计算每个分组的校验位，并对所有的校验位进行校验。如果某个分组的校验位与接收到的校验位不一致，则说明该分组发生了错误。

二维奇偶校验可以检测多个比特错误，并且可以同时检测行错误和列错误。但是，它不能纠正错误，只能检测错误。因此，在实际应用中，二维奇偶校验常与其他纠错码（如海明码）结合使用，以提高数据传输的可靠性。

总的来说，二维奇偶校验是一种常见的差错检测技术，它可以检测多个比特错误，并且可以同时检测行错误和列错误。在实际应用中，二维奇偶校验常与其他纠错码结合使用，以提高数据传输的可靠性。

检验和方法

检验和（Checksum）方法是一种常见的差错检测技术，它可以检测数据传输中的多比特错误。在检验和方法中，发送方会对数据进行求和，并将结果添加到数据末尾作为校验码。接收方在接收数据后，会重新计算校验和，如果计算出的校验和与接收到的校验码不一致，则说明数据传输出错。

检验和方法的原理很简单。以16位二进制数为例，假设发送方要传输以下数据：

1

1101101011001101

发送方会对数据进行求和，得到一个16位的校验和。在计算校验和时，为了避免溢出，通常会使用反码求和，即将所有位都取反后再相加。

假设发送方使用反码求和，得到的校验和为：

1

1010110000111000

然后，发送方将校验和添加到数据末尾，组成一个20位的数据包：

1

11011010110011011010110000111000

在接收方，接收到数据后，会重新计算校验和。接收方将接收到的数据按照与发送方相同的方式进行求和，得到一个16位的校验和。然后，接收方将计算出的校验和与接收到的校验码进行比较。如果两者不一致，则说明数据传输出错。

在检验和技术中，图6-4中的d比特数据被作为一个k比特整数的序列处理。一个简单检验和方法就是将这k比特整数加起来，并且用得到的和作为差错检测比特。因特网检验和（Internet checksum)就基于这种方法，即数据的字节作为16比特的整数对待并求和。这个和的反码形成了携带在报文段首部的因特网检验和。接收方通过对接收的数据（包括检验和）的和 取反码，并且检测其结果是否为全1比特来检测检验和。如果这些比特中有任何比特是0,就可以指示出差错。

不同为1，相同为，取反 应相反，若有相同则有差错

在 TCP 和 UDP 协议中，对所有字段（包括首部和数据字段）都计算 因特网检验和。在其他协议中，对首部计算一个 检验和，对整个分组计算一个检验和

检验和方法可以检测多比特错误，但不能纠正错误。在实际应用中，检验和方法常与其他纠错码（如海明码）结合使用，以提高数据传输的可靠性。总的来说，检验和方法是一种常见的差错检测技术，它可以检测数据传输中的多比特错误。在实际应用中，检验和方法常与其他纠错码结合使用，以提高数据传输的可靠性。

循环冗余检测 （Cyclic Redundancy Check） CRC

循环冗余校验（Cyclic Redundancy Check，CRC）是一种常用的差错检测技术，它可以检测数据传输中的多比特错误，并且可以纠正少量的错误。CRC主要应用于数据通信领域，如以太网、无线局域网等。

在CRC中，发送方将数据看作一个多项式，并对该多项式进行除法运算，得到余数。余数被添加到原始数据末尾作为校验码。接收方在接收数据后，也将数据看作一个多项式，并对该多项式进行除法运算，得到余数。如果余数为0，说明数据传输正确。否则，接收方会请求发送方重新发送数据。

CRC的核心是多项式除法运算。具体来说，CRC使用一个固定的生成多项式（Generator Polynomial）进行多项式除法运算。生成多项式是一个固定的、不可变的多项式，它的次数通常比数据位数少1。在除法运算中，发送方将数据看作一个多项式，将该多项式的次数扩展到与生成多项式相同，并将两个多项式进行除法运算。除法运算的结果就是余数，余数被添加到数据末尾成为校验码。

以16位数据为例，假设发送方要传输以下数据：

1

1101101011001101

发送方会将数据扩展为一个17位的多项式：

1

x^16 + x^13 + x^12 + x^10 + x^9 + x^5 + x^2 + 1

怎么拓展为 17 位的多项式

将一个16位数据扩展为17位的多项式，可以在16位数据的最高位（即最左侧位）添加一个0，并将该0视为一次幂为16的项。

例如，假设要将16位数据1101101011001101扩展为一个17位的多项式，可以在左侧添加一个0，得到：

1	0 1101101011001101

这样就得到了一个17位的多项式，其中最高位为一次幂为16的项。

在进行CRC运算时，这个17位的多项式将与生成多项式进行除法运算，得到余数。余数的位数通常比生成多项式的次数小1，因此余数通常是16位的。将余数添加到原始数据末尾作为CRC校验码，就组成了一个包含17位的数据包。

需要注意的是，数据的扩展方式可能会影响CRC运算的结果。因此，在进行CRC运算时，需要使用与发送方相同的扩展方式。通常情况下，数据的扩展方式是由通信协议规定的，接收方需要遵守相应的规定进行数据处理。

总的来说，将一个16位数据扩展为17位的多项式，只需要在最高位添加一个0，并将该0视为一次幂为16的项。在进行CRC运算时，需要使用与发送方相同的扩展方式，以保证CRC校验的正确性。

然后，发送方将该多项式与生成多项式进行除法运算，得到余数：

1

x^3 + x^2 + 1

发送方将余数添加到数据末尾，组成一个20位的数据包：

1

1101101011001101 110

在接收方，接收到数据后，也将数据看作一个多项式，并对该多项式进行除法运算，得到余数。如果余数为0，说明数据传输正确。否则，接收方会请求发送方重新发送数据。

怎么对 多项式进行除法运算，得到余数

在CRC中，除法运算是指将多项式除以一个固定的生成多项式，得到的余数就是CRC校验码。下面简要介绍如何对多项式进行除法，得到余数。

假设要对一个16位的多项式P(x)除以一个8位的生成多项式G(x)，得到的余数为R(x)。除法运算的过程可以表示为：

1	P(x) / G(x) = Q(x) ... R(x)

其中，Q(x)表示商多项式，R(x)表示余数多项式。除法运算的过程是逐步将P(x)减去G(x)的倍数，直到无法继续减为止。

具体的操作步骤如下：

1. 将P(x)的次数扩展到与G(x)相同，并将P(x)和G(x)对齐，使得P(x)的最高位对齐G(x)的最高位。

2. 将P(x)的最高位与G(x)的最高位对齐，计算它们的差，得到一个新的多项式。

3. 如果新的多项式的次数高于或等于G(x)的次数，则将G(x)左移一位，再将新的多项式与G(x)进行异或运算。如果新的多项式的次数低于G(x)的次数，则将G(x)右移一位，然后继续执行步骤2。

4. 重复执行步骤2和步骤3，直到P(x)的次数小于G(x)的次数为止。此时，P(x)的系数就是余数多项式R(x)的系数。

例如，假设要对多项式P(x)=x^6 + x^5 + x^3 + x + 1除以生成多项式G(x)=x^4 + x + 1，得到余数R(x)。除法运算的过程如下：

1 2 3 4 5 6 7 8

x^6 + x^5 + x^3 + x + 1 / x^4 + x + 1 = x^2 x^6 + x^5 + x^3 + x + 1 - x^6 - x^5 - x^3 - x^2 - x = 1 x^2 / x^4 + x + 1 = 0 1 / x^4 + x + 1 = x^3 + x^2

余数R(x)为1。

因此，多项式P(x)除以生成多项式G(x)的余数为R(x)=1。

总的来说，CRC校验的核心是多项式除法运算。在进行除法运算时，需要将多项式对齐，并将多项式的最高位与生成多项式的最高位对齐。然后，逐步将多项式减去生成多项式的倍数，直到无法继续减为止。最后剩下的多项式就是余数，即CRC校验码。

CRC可以检测多比特错误，并且可以纠正少量的错误。但是，CRC的性能取决于生成多项式的选择。不同的生成多项式可以提供不同的性能，如检测能力、纠错能力等。因此，在实际应用中，需要根据具体的场景选择合适的生成多项式。

总的来说，CRC是一种常用的差错检测技术，它可以检测数据传输中的多比特错误，并且可以纠正少量的错误。在实际应用中，CRC的性能取决于生成多项式的选择。

CRC 性能分析

多路访问链路和协议

两种类型的链路（一个子网内部链路连接方式）

• 点到点
  • 拨号访问的 PPP
  • 以太网交换机和主机之间的点到点链路
• 广播（共享线路或媒体）
  • 传统以太网
    • HFC 上行链路
    • 802.11 无线局域网

多路访问（Multiple Access）是指多个用户共享同一通信链路的技术。在多路访问链路中，多个用户可以同时访问同一链路，实现数据的交换和传输。

因为所有的节点都能够传输帧，所以多个节点可能会同时传输帧。当发生这种情况时，所有节点同时接到多个帧；这就是说，传输的帧在所有的接收方处碰撞（collide)了。通常，当碰撞发生时，没有一个接收节点能够有效地获得任何传输的帧；在某种意义下，碰撞帧的信号纠缠在一起。因此，涉及此次碰撞的所有帧都丢失了，在碰撞时间间隔中的广播信道被浪费了。显然，**如果许多节点要频繁地传输帧，许多传输将导致碰撞，广播信道的大量带宽将被浪费掉。

为了保证多个用户之间的数据传输不会互相干扰，需要使用多路访问协议来控制用户的访问。

多路访问协议是用于控制多个用户在同一链路上访问的协议。

• 单个共享的广播型链路
• 2 个 或更多站点同时传送： 冲突（collision）
  • 多个节点在同一时刻发送，则会收到2个或多个信号叠加

多路访问协议（介质访问控制协议：MAC）

• 分布式算法 - 决定节点如何使用 共享信道，即：决定节点什么时候可以发送
• 关于共享控制的通信信道必须借助信道本身进行传输
  • 没有带外的信道，各节点使用其协调信道使用
  • 用于传输控制信息

理想的多路访问协议

给定： Rbps 的广播信道

必要条件：

1. 当一个节点要发送的时候，可以用 R 速率发送
2. 当 M 个节点要发送时，每个可以平均 R/M 的平均速率发送
3. 完全分布的
   • 没有特殊节点 协调发送
   • 没有时钟和时隙的同步
4. 简单

三大类

• 信道划分
  • 把信道划分成小片（时间、频率、编码）
  • 分配片给每个节点使用
• 随机访问
  • 信道不划分，允许冲突
  • 冲突后恢复
• 依次轮流
  • 节点依次轮流
  • 但是有很多数据传输的节点可以获得较长时间的信道使用权

常用的多路访问协议包括以下几种：

1. ALOHA协议：ALOHA协议是一种最早用于卫星通信的多路访问协议。在ALOHA协议中，用户可以随时发送数据，但是如果多个用户同时发送数据，就会发生冲突。为了解决冲突问题，ALOHA协议引入了一种随机重传机制，即发送方在发送数据后，等待一段时间后再次发送数据，如果重传的数据仍然发生冲突，则等待更长的时间再次重传，直到数据发送成功。
2. CSMA/CD协议：CSMA/CD协议是一种用于局域网的多路访问协议。在CSMA/CD协议中，用户在发送数据前先监听链路，如果链路空闲，则可以发送数据。如果多个用户同时发送数据，就会发生冲突。为了解决冲突问题，CSMA/CD协议引入了一种冲突检测机制，即发送方在发送数据时，同时监听链路，如果检测到数据冲突，则停止发送数据，并等待一段时间后重新发送数据。
3. TDMA协议：TDMA协议是一种用于无线通信的多路访问协议。在TDMA协议中，时间被分成若干个时隙，每个用户在一个时隙内发送数据。不同用户的时隙不同，因此可以避免数据冲突。TDMA协议需要在发送方和接收方之间进行协调，以保证每个用户在正确的时隙发送数据。
4. CDMA协议：CDMA协议是一种用于无线通信的多路访问协议。在CDMA协议中，每个用户使用不同的码片对数据进行编码，不同用户的码片不同，因此可以避免数据冲突。CDMA协议需要在发送方和接收方之间进行协调，以保证每个用户的码片不同。
5. FDMA协议: 频分多路复用（FDMA）是一种多路访问技术，将可用的频带分成多个频段，每个用户占用不同的频段进行通信。FDMA技术广泛应用于无线通信系统中，如AM广播、调频广播、蜂窝移动通信等。FDMA将频带分成多个频段，每个频段对应一个用户，可以有效地避免数据冲突和干扰，实现多个用户同时使用同一通信链路的目的。

总的来说，多路访问链路和协议是用于控制多个用户在同一链路上访问的技术和协议。不同的多路访问协议有不同的特点和适用范围，需要根据具体的应用场景选择合适的协议。

信道划分协议

时分多路复用（TDM） 和 频分多路复用（FDM） 是两种能够用于在所有共享信道节点之间划分广播信道带宽的技术。举例来说，假设一个支持 N 个节点的信道且信道的传输速率为Rbps。TDM将时间划分为时间帧（timeframe),并进一步划分每个时间帧为N个**时隙（slot)**。（不应当把TDM时间帧与在发送和接收适配器之间交换的链路层数据单元相混淆，后者也被称为帧。为了减少混乱，在本小节中我们将链路层交换的数据单元称为分组。）然后把每个时隙分配给N个节点中的一个。无论何时某个节点在有分组要发送的时候，它在循环的TDM帧中指派给它的时隙内传输分组比特。通常，选择的时隙长度应使一个时隙内能够传输单个分组。

信道划分协议是用于控制多个用户在同一通信链路上访问的一种协议。信道划分协议将通信链路划分为多个子信道或时隙，在不同的子信道或时隙上分配给不同的用户进行数据传输。常见的信道划分协议包括以下几种：

1. 频分多路复用（FDMA）：FDMA技术将可用的频带分成多个频段，每个用户占用不同的频段进行通信。FDMA技术广泛应用于无线通信系统中，如AM广播、调频广播、蜂窝移动通信等。

   

2. 时分多路复用（TDMA）：TDMA技术将通信时段分成若干个时隙，每个用户在一个时隙内发送数据。不同用户的时隙不同，因此可以避免数据冲突。TDMA技术广泛应用于数字通信系统中，如GSM、PDC等。

   

3. 码分多路复用（CDMA）：CDMA技术将用户数据进行编码，不同用户使用不同的码片进行编码，因此可以避免数据冲突。CDMA技术广泛应用于无线通信系统中，如CDMA2000、WCDMA等。

   

随机接入协议

随机接入协议是一种多路访问协议，用于控制多个用户在同一通信链路上访问的一种协议。在随机接入协议中，用户可以随时发送数据，一个节点总是以信道的全部速率（即 Rbps ） 进行发送，但是如果多个用户同时发送数据，就会发生冲突。当有碰撞时，涉及碰撞的每个节点反复地重发它的帧（也就是分组），直到该帧无碰撞为止。 但是当一个节点经历一次碰撞时，他不必立即重发该帧。相反，他在重发该帧之前 等待一个随机时延。涉及碰撞的每个节点 独立的 选择时延 。 换言之，为了解决冲突问题，随机接入协议引入了一种随机机制，即发送方在发送数据前随机选择一个时隙或码片进行数据传输。

常见的随机接入协议包括以下几种：

1. ALOHA协议：ALOHA协议是一种最早用于卫星通信的随机接入协议。在ALOHA协议中，用户可以随时发送数据，但是如果多个用户同时发送数据，就会发生冲突。为了解决冲突问题，ALOHA协议引入了一种随机重传机制，即发送方在发送数据后，等待一段时间后再次发送数据，如果重传的数据仍然发生冲突，则等待更长的时间再次重传，直到数据发送成功。

2. CSMA/CA协议：CSMA/CA协议是一种用于无线局域网的随机接入协议。在CSMA/CA协议中，用户在发送数据前先监听链路，如果链路空闲，则可以发送数据。如果多个用户同时发送数据，就会发生冲突。为了解决冲突问题，CSMA/CA协议引入了一种碰撞避免机制，即发送方在发送数据时，等待一段时间后再次监听链路，如果链路仍然空闲，则发送数据，否则等待更长的时间后再次尝试发送数据。

3. CDMA协议：CDMA协议是一种用于无线通信的随机接入协议。在CDMA协议中，每个用户使用不同的码片对数据进行编码，不同用户的码片不同，因此可以避免数据冲突。CDMA协议需要在发送方和接收方之间进行协调，以保证每个用户的码片不同。

总的来说，随机接入协议是一种用于控制多个用户在同一通信链路上访问的协议。随机接入协议可以灵活地分配通信资源，但是由于存在数据冲突和干扰问题，需要引入一些机制来解决这些问题。不同的随机接入协议有不同的特点和适用范围，需要根据具体的应用场景选择合适的协议。

时隙ALOHA

ALOHA是一种最早用于卫星通信的随机接入协议。在ALOHA协议中，用户可以随时发送数据，但是如果多个用户同时发送数据，就会发生冲突。为了解决冲突问题，ALOHA协议引入了一种随机重传机制，即发送方在发送数据后，等待一段时间后再次发送数据，如果重传的数据仍然发生冲突，则等待更长的时间再次重传，直到数据发送成功。

ALOHA协议的操作步骤如下：

1. 发送方发送数据：发送方在任何时刻都可以发送数据。

2. 碰撞检测：当有多个发送方同时发送数据时，就会发生碰撞。每个发送方在发送完数据后会监听链路，如果检测到链路上有数据传输，则表示发生碰撞。

3. 随机重传：发生碰撞后，每个发送方会等待一段随机时间后再次发送数据，重传时间是随机的，并且会根据网络负载情况动态调整。如果重传的数据仍然发生碰撞，则等待更长的时间再次重传，直到数据发送成功。

4. 接收方确认：接收方收到数据后会发送确认信号，通知发送方数据已经成功接收。

ALOHA协议的操作非常简单，没有任何复杂的控制机制。发送方可以随时发送数据，如果发生碰撞，则随机重传，直到数据发送成功。接收方在接收到数据后会发送确认信号，以保证数据传输的可靠性。虽然ALOHA协议存在冲突和干扰问题，但是通过随机重传机制可以一定程度上解决这个问题。

如果 有碰撞，该节点在时隙结束之前检测到这次碰撞。该节点 以 概率 P 在后续的每个时隙中重传，直到无碰撞

我们说以概率p重传，是指某节点有效地投挪一个有偏倚的硬币；硬币正面事件对应着重传，而重传出现的概率为p。硬币反面事件对应着“跳过这个时隙，在下个时隙再挪硬币”；这个事件以概率（1-p)出现。所有涉及碰撞的节点独立地投挪它们的硬币。

时隙ALOHA看起来有很多优点。与信道划分不同，当某节点是唯一活跃的节点时(一个节点如果有帧要发送就认为它是活跃的）,时隙ALOHA允许该节点以全速R连续传输。时隙ALOHA也是高度分散的，因为每个节点检测碰撞并独立地决定什么时候重传。(然而，时隙ALOHA的确需要在节点中对时隙同步；我们很快将讨论ALOHA协议的一个不分时隙的版本以及CSMA协议，这两种协议都不需要这种同步。）时隙ALOHA也是一个极为简单的协议。

当只有一个活跃节点时，时隙ALOHA工作出色，但是当有多个活跃节点时效率又将如何呢？这里有两个可能要考虑的效率问题。首先，当有多个活跃节点时，一部分时隙将有碰撞，因此将被“浪费”掉了。第二个考虑是，时隙的另一部分将是空闲的，因为所有活跃节点由于概率传输策略会节制传输。唯一“未浪费的”时隙是那些刚好有一个节点传输的时隙。刚好有一个节点传输的时隙称为一个成功时隙（successful slot)。时隙多路访问协议的效率（efficiency)定义为：当有大量的活跃节点且每个节点总有大量的帧要发送时，长期运行中成功时隙的份额。注意到如果不使用某种形式的访问控制，而且每个节点都在每次碰撞之后立即重传，这个效率将为零。时隙ALOHA显然增加了它的效率，使之大于零，但是效率增加了多少呢？

当有 N 个活跃节点时 ，时隙 ALOHA的 效率为 ，即 37%

ALOHA

当 节点 i 在传输时，其他节点不能开始传输，因为 这种传输将与节点 i 传输的后面部分相重叠。通过这种方式，我们求得 纯 ALOHA协议的 最大效率是

仅为 **17.5%**，这就是完全分散的 ALOHA 协议所需要付出的代价

载波侦听多路访问协议 CSMA

在时隙和 ALOHA协议中，一个节点传输的决定独立于连接到这个广播 信道上的其他节点的活动。特别是， 一个节点不关心在他传输的时候是否有其他节点碰巧在传输，而且即使有另一个节点在干扰他的传输也不会停止传输

两种规则

• 说话之前先听。如果有其他人正在说话，等到他们说完为止。在网络领域中，被称为 载波侦听（carrier sensing），即 一个节点在传输前先听 信道，如果有来自另一个节点的帧正向信道中发送，节点则等待 直到 检测到一小段时间没有传输，然后开始传输
• 如果与其他人同时开始说话，停止说话。这在网络领域 被称为 碰撞检测（collision detection），即 当一个传输节点在传输时一直 侦听此信道。 如果他检测到 另一个节点正在传输干扰帧，他就停止传输，在重复 “侦听 - 当空闲时传输” 循环之前等待一段随机时间

载波侦听多路访问协议（Carrier Sense Multiple Access ，CSMA）是一种用于控制多个用户在同一通信链路上访问的协议。在CSMA协议中，用户在发送数据前先监听链路，如果链路空闲，则可以发送数据。如果多个用户同时发送数据，就会发生冲突。为了解决冲突问题，CSMA协议引入了一种碰撞检测机制，即发送方在发送数据后会继续监听链路，如果检测到链路上有数据传输，则表示发生碰撞，需要等待一段时间后再次尝试发送数据。

这两个规则包含在载波侦听多路访问（Carrier Sense Multiple Access,CSMA)和具有碰撞检测的CSMA(CSMA with Collision Detection,CSMA/CD)协议族中

CSMA协议的缺点是存在隐藏终端问题和暴露终端问题。隐藏终端问题是指当两个发送方之间存在一个接收方，但是由于距离或障碍物阻挡等原因，发送方无法检测到对方的存在，从而导致碰撞。暴露终端问题是指某些发送方可能由于距离远或信号弱而无法感知到其他发送方的存在，从而导致空闲的链路被浪费。

总的来说，CSMA协议是一种常用的多路访问协议，具有灵活的资源分配、动态调整和分布式控制等优点。然而，它仍然存在某些缺陷，需要在具体场景中选择合适的协议来保证网络的性能和可靠性。

CSMA 冲突

冲突可能仍然发生

由传播延迟造成：两个节点可能侦听不到正在进行的传输

冲突

整个冲突帧的传输时间都被浪费了，是无效的传输

注意

传播延迟（距离）决定了冲突的概率

节点根据本地的信道使用情况来判断全部信道的使用情况

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

CSMA/CD是一种基于载波侦听多路访问协议（CSMA）的协议，它引入了碰撞检测（Collision Detection，CD）机制，用于检测和解决数据碰撞问题。在CSMA/CD协议中，发送方在发送数据前先监听链路，如果链路空闲，则可以发送数据。如果多个用户同时发送数据，就会发生碰撞。为了解决碰撞问题，CSMA/CD协议引入了碰撞检测机制，即发送方在发送数据的同时，继续监听链路，如果检测到碰撞，则立即停止发送数据，并等待随机时间后再次尝试发送数据。

CSMA/CD协议的操作步骤如下：

1. 发送数据：发送方在监听到链路空闲后，立即发送数据。
2. 碰撞检测：发送方在发送数据的同时，继续监听链路，如果检测到碰撞，则立即停止发送数据，并等待随机时间后再次尝试发送数据。
3. 重传数据：发送方在等待一段随机时间后，重新发送数据。如果多次重传仍然无法成功发送数据，则放弃发送。
4. 接收确认：接收方收到数据后发送确认信号，通知发送方数据已经成功接收。

对信道的浪费变少了

总的来说，CSMA/CD协议是一种常用的多路访问协议，具有良好的性能和可靠性。然而，随着网络技术的不断发展，CSMA/CD协议已经逐渐被更先进的协议所替代，如以太网的802.3标准等。

以太网 CSMA/CD 算法

1. 适配器获取数据报，创建帧

2. 发送前：侦听信道 CS

   1. 闲：开始传输帧
   2. 忙：一直等到闲再发送

3. 发送过程中，冲突检测 CD

   1. 没有冲突：成功
   2. 检测到冲突：放弃，之后尝试重发

4. 发送方适配器检测到冲突，除放弃外，还发送一个 Jam 信号，所有听到 冲突的适配器也是如此

   强化冲突：让所有站点都知道冲突

5. 如果放弃，适配器进入 指数退避状态

   在 第 m 次失败后，适配器随机选择一个 {0，1,2，…,$$2^{m-1}$$} 中 的K，等待 K * 512 位时，然后转到步骤2

   二进制指数退避算法

   binary exponential backoff

   

   在实现二进制指数退避算法时，适配器进入指数退避状态后，需要进行等待和重传数据的操作。具体来说，适配器进入指数退避状态的过程如下：

   1. 发送数据：适配器在发送数据前先监听网络，如果网络空闲，则可以发送数据。

   2. 发生冲突：如果多个适配器同时发送数据，则会发生冲突。发生冲突后，每个适配器都会停止发送数据，并进入指数退避状态。

   3. 计算等待时间：在进入指数退避状态后，适配器需要计算下一次重传数据需要等待的时间。第一次重传时，等待时间是一个随机数，之后每次等待时间前一次等待时间的两倍。

   4. 等待时间：适配器在计算出下一次重传需要等待的时间后，需要等待这段时间后再次发送数据。适配器可以使用计数器或定时器等机制来实现等待时间的计算和控制。

   5. 重传数据：在等待时间后，适配器重新发送数据。如果再次发生冲突，则适配器需要重新计算下一次重传需要等待的时间，并进行等待和重传数据的操作。

   6. 最大重传次数：如果适配器重传数据次数超过了最大重传次数，则放弃发送数据。

   需要注意的是，适配器在进入指数退避状态后，需要按照指数级递增的方式计算等待时间，以避免多个适配器在同一时间重传数据导致新的冲突。在具体实现中，等待时间需要满足一定的约束条件，如等待时间不能超过一个预设的最大值，以避免适配器等待时间过长导致网络资源浪费的问题。此外，在等待时间的计算中还可以引入一些随机性，以避免多个适配器在同一时间重传数据，从而导致新的冲突。

   总的来说，适配器进入指数退避状态后，需要进行等待和重传数据的操作，以避免网络冲突。具体实现中，适配器需要计算和控制等待时间，并在等待时间后重新发送数据。适配器可以使用计数器或定时器等机制来实现等待时间的计算和控制。在具体实现中，需要注意等待时间的计算和约束条件，以避免适配器等待时间过长导致网络资源浪费的问题。

CSMA/CD 效率

无线局域网中的 MAC：CSMA/CA

CSMA/CA是载波监听多路访问/碰撞避免（Carrier Sense Multiple Access/Collision Avoidance）的一种协议，主要用于无线局域网（WLAN）中，用于解决在无线网络中的冲突问题。

CSMA/CA协议的工作原理如下：

1. 载波监听：在发送数据前，设备需要先监听信道，检测是否有其他设备正在发送数据。如果信道空闲，设备才可以开始发送数据。
2. 随机等待：如果信道被占用，设备需要等待一段随机时间后再次进行载波监听。随机等待的时间是根据指数退避算法计算得出的，以避免多个设备在同一时间重试发送数据。
3. 帧传输：如果经过若干次随机等待后，信道仍然空闲，则设备可以开始传输数据帧。在数据传输过程中，设备将使用帧序列控制（Frame Sequence Control）字段来协调数据的传输，以避免数据的冲突和丢失。
4. 确认应答：当一个设备成功接收到数据帧后，会发送一个确认应答帧以告知发送方数据已经成功接收，从而防止数据重传和冲突。

需要注意的是，CSMA/CA协议主要用于无线网络中，由于无线信号的特性，数据传输容易受到干扰和衰减，因此需要使用一些特殊的技术来避免冲突和丢失。CSMA/CA协议是其中一种常用的技术，能够有效地提高无线网络的性能和可靠性。

总的来说，CSMA/CA是一种用于无线网络中的多路访问和碰撞避免的协议，通过载波监听、随机等待、帧传输和确认应答等机制，能够有效地避免数据的冲突和丢失，提高无线网络的性能和可靠性。

IEEE 802.11 MAC 协议：CSMA/CA

• 在 count down 时，侦听到了 信道空闲为什么不发送，而要 等到 0 时 才发送

  • 2 个站点有数据帧需要发送，第三个节点正在发送
  • LAN CD：让 2 者 听完 第三个节点发完，立即发送
    • 冲突：放弃当前的发送，避免了信道的浪费于无用冲突帧的发送
    • 代价并不昂贵
  • WLAN：CA
    • 无法 CD，一旦发送就必须发完，如冲突信道浪费，代价昂贵
    • 思想： 尽量 事先避免 冲突，而不是发生冲突时放弃然后重发
    • 听到发送的站点，分别选择 随机值，回退到 0 发送
      • 不同的随机值，一个站点会胜利
      • 失败站点会冻结计数器，当胜利节点发完再发

• 无法完全避免冲突

  

  • 两个节点相互隐藏
    • AB 相互隐藏，C在传输
    • AB 选择了随机回退值
    • 一个 节点 如A胜利了，发送
    • 而 B 节点收不到，顺利 count down 到 0 发送
    • AB 的发送在 C 附近形成了 干扰
  • 选择了非常 靠近的 随机回退值
    • AB 的选择非常近
    • A 到 0 发送
    • 但是这个信号还没到 B 时
    • B 也到 0 了，发送
    • 冲突

冲突避免

思想：允许发送方 “预约” 信道，而不是随机访问信道：避免了长数据帧的浪费

• 发送方首先使用 CSMA 向 BS 发送一个小的 RTS分组

  • RTS 可能会冲突（但是由于比较短，浪费信道较少）

  RTS（Request to Send）分组是一种用于无线局域网（WLAN）中的数据帧类型之一，用于在发送数据前请求接收方的许可。RTS帧通常与CTS（Clear to Send）帧一起使用，以确保数据的可靠传输和避免数据冲突。

  在发送数据前，发送方首先发送一个RTS帧给接收方，请求接收方的许可。RTS帧包含了一些关键信息，如发送方的地址、接收方的地址、数据长度等。接收方在接收到RTS帧后，会发送一个CTS帧给发送方，告知发送方可以开始发送数据。CTS帧中也包含了一些关键信息，如接收方的地址、发送方的地址、数据长度等。

  通过RTS/CTS机制，可以避免数据冲突和丢失。具体来说，RTS/CTS机制可以实现以下几个功能：

  1. 碰撞避免：由于使用了RTS/CTS机制，发送方和接收方可以在发送数据前进行协调，避免多个设备在同一时间发送数据，从而避免数据冲突和丢失。

  2. 优先级控制：由于RTS/CTS机制需要消耗一定的网络资源，发送方可以根据需要进行优先级控制，选择是否使用RTS/CTS机制，以充分利用网络资源。

  3. 数据传输可靠性：通过RTS/CTS机制，可以保证数据的可靠传输，避免数据的重传和丢失。

  需要注意的是，RTS/CTS机制虽然能够提高数据传输的可靠性，但是也会增加网络的负担和延迟。因此，在具体应用中，需要根据网络环境和应用场景进行选择，以平衡性能和可靠性的需求。

  总之，RTS分组是一种用于无线局域网中的数据帧类型，通过与CTS帧一起使用，可以实现碰撞避免、优先级控制和数据传输可靠性的功能，提高网络的性能和可靠性。

• BS 广播 clear - to - send CTS ，作为 RTS 的响应

• CTS 能够被所有涉及到的 节点听到

  • 发送方发送数据帧
  • 其他节点抑制发送

采用小的 预约分组，可以完全避免数据帧的冲突

轮流协议（Taking Turns ) MAC 协议

信道划分 MAC 协议：

• 共享信道 在高负载 时是 有效和公平的
• 在低负载时 效率较低
  • 只能等到自己的时隙开始发送或者 利用 1/N 的 信道频率发送
  • 当只有一个节点有帧发送时，也只能够得到 1/N 带宽分配

随机访问 MAC 协议

• 在低负载时效率高：单个节点可以利用信道的全部带宽
• 高负载时：冲突开销较大，效率极低，时间很多都浪费了

轮流协议：

有两者的优点

轮流协议

轮询

• 主节点邀请从节点依次发送
• 从节点一般比较 “dump”
• 缺点：
  • 轮询开销：轮询本身消耗信道带宽
  • 等待时间：每个节点需等到主节点轮询后开始传输，即使 只有一个节点，也需要 轮询一周后才能发送
  • 单点故障：主节点失效时造成整个系统无法 工作

令牌传递

• 控制 令牌（token） 循环从一个节点到下一个节点 的传递
• 令牌报文：特殊的帧
• 缺点：
  • 令牌开销：本身消耗带宽
  • 延迟：只有等到抓到令牌，才可传输
  • 单点故障（token）：
    • 令牌丢失 系统级故障，整个系统无法传输
    • 复杂机制重新生成令牌

DOCSIS：线缆接入网络

MAC 协议总结

LANs

图6-15显示了一个交换局域网连接了3个部门，两台服务器和一台与4台交换机连接的路由器。因为这些交换机运行在链路层，所以它们交换链路层帧（而不是网络层数据报）,不识别网络层地址，不使用如RIP或OSPF这样的路由选择算法来确定通过第二层交换机网络的路径。我们马上就会看到，它们使用链路层地址而不是IP地址来转发链路层帧通过交换机网络。我们首先以讨论链路层寻址来开始对交换机局域网的学习。然后仔细学习著名的以太网协议。在仔细学习链路层寻址和以太网后，我们将考察链路层交换机的工作方式,并随后考察通常是如何用这些交换机构建大规模局域网的。

链路层寻址和 ARP

• 32bit IP 地址
  • 网络层地址
  • 前n-1 跳：用于使数据报到达目的 IP 子网
  • 最后一跳：到达子网中的目标节点
• LAN（MAC/物理/以太网）地址：
  • 用于使帧从一个网卡传递到与其物理连接的另一个网卡（在同一物理网络中）
  • 48 bit MAC 地址固化在适配器的 ROM，有时也可以通过软件设定
  • 理论上 全球任何两个网卡的 MAC 地址都不相同

网络地址和 Mac 地址分离

1. IP地址和 MAC 地址的作用不同
   1. IP 地址是分层的
      • 一个子网所有站点网络号一致，路由聚集，减少路由表
        • 需要一个网络中的站点地址 网络号一致，如果 捆绑需要定制网卡非常麻烦
      • 希望网络层地址是配置的；IP地址完成网络到网络的交付
2. MAC地址是一个 平面 的
   • 网卡在 生产时不知道被用于那个网络，因此 给网卡一个唯一的标识，用于区分一个网络内部 不同的网卡
   • 可以完成一个物理网络内部的节点到节点的数据交付网卡
3. 分离的好处
   • 网卡坏了，IP 不变，可以捆绑到另外一个网卡的 Mac 上
   • 物理网络还可以除 IP 之外支持其他网络层协议，链路协议为任意上层网络协议
4. 捆绑的问题
   • 如果仅仅使用 IP 地址，不用 MAC 地址，那么它 仅支持 IP协议
   • 每次上电都要重新写入网卡 IP 地址
   • 另外一个选择就是不使用任何地址；不用 MAC地址，则每到来一个帧都要上传到 IP 层次，由他判断是不是要接受，干扰一次

• MAC地址由 IEEE 管理和分配
• 制造商购入 MAC地址空间（保证唯一性）
• 类比
  • Mac 地址：社会安全号
  • IP 地址：通讯地址
• MAC 平面地址 -> 支持移动
  • 可以将网卡接到其他网络
• IP 地址有层次 -> 不能移动
  • 依赖于节点连接的IP 子网，与子网的网络号相同（有与其相连的子网相同的网络前缀)

地址解析协议 ARP Address Resolution Protocol

因为存在 网络层地址（IP 地址）和 链路层地址（Mac地址），所以需要在他们之间进行转换。对于 Internet 来说，这就是 地址解析协议 ARP

ARP（Address Resolution Protocol）是一种用于将IP地址解析为MAC地址的协议，常用于局域网中。ARP协议的主要作用是将目标IP地址转换为相应的MAC地址，以便在局域网中进行数据传输。

当一个设备需要向局域网中的其他设备发送数据时，需要先获取目标设备的MAC地址。此时，设备会首先查询本地的ARP缓存表，检查是否有目标设备的IP地址对应的MAC地址。如果有，则可以直接使用该MAC地址进行数据传输；如果没有，则需要发送一个ARP请求广播，请求目标设备回应其MAC地址。收到ARP请求广播后，目标设备将会回应自己的MAC地址，发送方将收到该回应并将其缓存到本地的ARP缓存表中，以便下次快速获取目标设备的MAC地址。

需要注意的是，ARP协议只适用于同一局域网内的设备之间的通信，因为在不同的局域网中，不同的设备可能使用不同的物理地址和网络协议，因此需要使用更为复杂的协议，如路由协议等。

总之，ARP协议是一种用于将IP地址解析为MAC地址的协议，通过查询本地的ARP缓存表或发送ARP请求广播，可以获取目标设备的MAC地址，以便在局域网中进行数据传输。ARP协议是局域网中数据传输的基础，能够实现快速、可靠的数据传输。

路由到其他 LAN

以太网 Ethernet

Ethernet是一种常用的局域网（LAN）技术，是一种基于CSMA/CD协议的数据传输协议。Ethernet最初由Xerox公司开发，后来被Intel、Digital和Xerox合作推出，并逐渐成为局域网中的标准技术之一。

Ethernet的基本原理是通过物理介质（如双绞线、光纤等）连接设备，使用CSMA/CD协议来协调设备之间的数据传输，以实现数据的高速、可靠传输。在Ethernet中，每个设备都有一个唯一的物理地址（MAC地址），用于在网络中进行通信。Ethernet支持多种传输速率和距离，如10Mbps、100Mbps、1000Mbps等，以及10米、100米、1000米等传输距离，可以根据具体的需求进行选择。

在Ethernet中，每个设备都可以发送或接收数据帧（Frame），数据帧由多个字段组成，包括目标地址、源地址、数据长度、数据内容等。数据帧通过物理介质传输，经过物理层的编码和解码处理后，到达数据链路层，进行MAC地址的寻址和帧的处理。如果在传输过程中发生了冲突，设备会通过CSMA/CD协议进行协调，以避免数据的丢失和冲突。

总之，Ethernet是一种常用的局域网技术，基于CSMA/CD协议，通过物理介质连接设备，实现数据的高速、可靠传输。Ethernet具有灵活性、可靠性和可扩展性等优点，在局域网中得到了广泛应用。

以太网：物理拓扑

• 总线：
  • 所有节点在一个碰撞域中，一次只允许一个节点发送
  • 可靠性差，如果介质破损，截面形成信号的反射，发送节点误以为是冲突，总是冲突
• 星型： 目前主流
  • 连接选择： hub 或者 Switch
  • 现在一般是交换机在中心
  • 每个节点以及相连的交换机端口使用（独立的）以太网协议（不会和其他节点的发送产生碰撞）

以太网帧结构

发送方适配器在 以太网帧 中封装 IP 数据报或者其他的网络层协议数据单元

• 地址： 6字节 源Mac 地址，目标 Mac 地址

  

• 类型：指出高层协议（大多情况下是 IP，但也支持其他网络层协议）

• CRC：在接收方检验

  

以太网：无连接、不可靠的服务

• 无连接：帧传输前，发送方和接收方之间没有握手

• 不可靠：接收方适配器不发送 ACKs 或 NAKs 给发送方

  • 递交给网络层的 数据报流可能有 gap

    

• 以太网的 MAC 协议：采用 **二进制退避的 CSMA/CD ** 介质访问协议

Hubs

hub 本质上是物理层的中继器

• 从一个端口收，转发到其他所有端口
• 速率一致
• 没有帧的缓存
• 在 hub 端口上 没有 CSMA/CD 机制：适配器检测冲突
• 提供网络管理功能

Manchester 编码

千兆以太网

switches

Hub：集线器

• 网段（LAN segment）：可以允许一个站点发送的网络范围
  • 在一个碰撞域，同时只允许一个站点发送
  • 如果有两个节点发送，则会碰撞
  • 通常拥有相同的前缀，比 IP子网更详细的前缀
• 所有 以 hub 连在一起的站点处在一个 网段，处在一个碰撞域
  • 骨干hub 将所有网段连到了一起
• 通过 hub 可扩展节点之间的最大距离
• 通过hub，不能将 10 BaseT 和 100 BaseT 的网络连接在一起

交换机

• 链路层设备：扮演主动角色（端口执行以太网协议）
  • 对帧进行存储和转发
  • 对于到来的帧，检查帧头，根据目标 MAC 地址进行 选择性转发
  • 当 帧需要向某个（些） 网段进行 转发，需要使用 CSMA/CD 进行接入控制
  • 通常一个交换机端口一个独立网段
• 透明：主机对交换机的存在可以不关心
  • 通过交换机相连的各节点 好像这些站点是直接相连的一样
  • 有 MAC 地址；无 IP 地址
• 即插即用，自学习
  • 交换机无需配置

交换机：多路同时传输

• 主机有一个 专用 和 直接 到交换机的连接

• 交换机缓存到来的帧

• 对每个帧进入的链路使用 以太网协议，没有碰撞；全双工

  • 每条链路都是一个独立的碰撞域
  • MAC 地址在其中的作用 太弱化了

• 交换：A - to -A’ 和 B - to - B‘ 可以同时传输，没有碰撞

  

交换机转发表

交换机自学习

交换机：过滤、转发

当交换机收到一个 帧时 ：

1. 记录进入链路，发送主机 的 MAC地址

2. 使用 目标 MAC地址对交换表进行 索引

   

交换机级联

交换机 VS 路由器

VLANs

VLAN（Virtual Local Area Network）是一种虚拟局域网技术，可以将一个物理局域网划分成多个逻辑上的虚拟局域网，从而实现更好的网络管理和安全控制。

在传统的局域网中，所有设备都连接在同一个物理网络中，因此，不同的设备可以直接通信，缺乏有效的隔离和安全控制。而在VLAN中，可以将不同的设备划分到不同的虚拟网络中，各个虚拟网络之间相互隔离，从而提高网络的安全性和可管理性。

VLAN的实现方式通常是通过交换机和路由器进行管理。交换机可以将不同的端口划分到不同的VLAN中，从而实现不同VLAN之间的隔离。路由器可以对不同的VLAN进行路由转发，实现不同VLAN之间的通信。

使用VLAN技术可以带来以下优点：

1. 提高网络的安全性：VLAN可以将不同的设备划分到不同的虚拟网络中，各个虚拟网络之间相互隔离，从而提高网络的安全性。可以根据不同的安全级别对不同的设备进行划分，减少网络攻击的风险。

2. 提高网络的可管理性：使用VLAN技术可以更好地管理网络资源，可以根据不同的部门、功能或需求来划分VLAN，方便网络管理员对网络进行管理和监控。同时，VLAN可以减少广播和数据流量，提高网络的性能和可靠性。

3. 提高网络的灵活性：使用VLAN技术可以根据需要随时添加、删除或修改VLAN，方便网络的调整和扩展。同时，VLAN可以跨越多个交换机和路由器，实现更大规模的网络管理和控制。

需要注意的是，使用VLAN技术需要进行一定的规划和配置，同时需要保证交换机和路由器的兼容性和互操作性。此外，VLAN的划分需要根据实际需求和网络拓扑结构进行优化，否则可能会影响网络的性能和可靠性。

总之，VLAN是一种虚拟局域网技术，可以将一个物理局域网划分为多个逻辑上的虚拟局域网，实现更好的网络管理和安全控制。VLAN具有提高网络安全性、可管理性和灵活性等优点，是现代网络中常用的管理和控制技术。

基于端口的 VLAN

VLANs 互连多个交换机

a day in the life of web request

以一个 web 页面请求的例子： 综述

• 目标：标示、回顾和理解涉及到的协议（所有层次），以一个看似简单的场景： 请求web 页面
• 场景：学生在校园内启动一台笔记本电脑：请求和 接收www.google.com

总结

• 数据链路层服务背后的原理
  • 检错、纠错
  • 共享式广播信道：多路访问
  • 链路编址
• 各种链路层技术的实现和实例
  • Ethernet
  • 交换式 LANs、VLANs
  • 虚拟成 链路层的 网络 MPLS
• 综合 ：一个 web 页面请求的日常场景

​