计算机网络复习笔记

第一章 计算机网络和因特网

1.1 什么是因特网——因特网的具体构成

两种方式回答：

1.描述因特网的具体构成(具体硬件和软件组件)

2.根据为分布式应用提供服务的联网基础设施来描述

组成描述

用因特网的术语来说，所有连入因特网的设备都叫做主机或者端系统
连接在因特网上的数十亿计的互连计算机设备:
主机 = 端系统
运行网络应用程序

连接因特网上各种设备的通信链路
光纤，铜缆，无线电，人造卫星
传输速率 = 带宽

转发分组(数据块)的分组交换机
链路层交换机
路由器

因特网服务提供商ISP ：端系统通过ISP接入因特网，ISP也彼此互联
因特网协议:控制因特网中信息的接受和发送，因特网协议统称为TCP/IP
因特网标准：定义协议，实现各个协议及其作用取得一致作用，IETF研发，其标准文档称为RFC

服务描述

向应用程序提供服务的基础设施(分布式应用程序)
网页浏览、VoIP、电子邮件、 游戏、电子商务、社交网络、…
NC、云

向应用程序提供编程接口(套接字接口)
允许应用程序连接到因特网上的钩子
提供不同级别的服务可选项：类似于邮政服务

1.2 网络边缘

网络边缘:端系统(桌面计算机、服务器、移动计算机、越来越多的非传统物品)

网络应用服务模型：C/S、P2P

接入网：将网络边缘与网络核心(通常是边缘路由器)连接起来

边缘路由器：端系统到任何其它远程端系统的路径上的第一台路由器

接入的方式

​ 家庭：Modem拨号/ADSL拨号/HFC/FTTH/卫星

​ 机构：以太网/Wi-Fi

​ 广域无线接入：3G/4G/5G/LTE

物理媒体

​ 引导性媒体(信号沿固体媒体被引导):双绞线

​ 非引导性媒体(自由传播):同轴电缆、光缆、无线电

1.3 网络核心

第一代计算机网络——电路交换网络

数据交换过程

​ 第一步：建立连接

​ 第二步：交换数据

​ 第三步：释放连接

电路交换的特性

​ 数据交换前需建立起一条从发端到收端的物理通路

​ 在数据交换的全部时间内用户始终占用端到端的固定传输信道

​ 交换双方可实时进行数据交换而不会存在任何延迟

电路交换中的复用（分类）

​ 时分复用

​ 频分复用

存在的问题

​ 计算机之间的数据交换往往具有突发性和间歇性特征，而对电路交换而言，用户支付的费用则是按用户占用线路的时间来收费的

​ 不够灵活。只要在通话双方建立的通路中的任何一点出了故障，就必须重新拨号建立新的连接，这对紧急和重要通信是很不利的。

第二代计算机网络——分组交换网络

分组交换的工作流程

1. 在发送端，先把较长的报文划分成较短的、固定长度的数据段
2. 每一个数据段前面添加上首部构成分组
3. 分组交换网以“分组”作为数据传输单元
4. 依次把各分组发送到接收端
5. 接收端收到分组后剥去首部还原成报文
6. 最后，在接收端把收到的数据恢复成为原来的报文

分组交换网络分类

​ 虚电路网络

​ 数据报网络

ISP与因特网主干

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

时延类型:

节点处理时延

​ dproc: 节点处理

​ 检查比特错误

​ 确定输出链路

​ 通常<毫秒

排队时延

​ 输出链路等待传输的时间

​ 取决于路由器的拥塞程度

传输时延:将所有分组比特推向链路的时间

​ L:分组长度 (bits)

​ R:链路带宽 (bps)
$$d_{trans}=L/R$$
传播时延:一个比特从一台路由器到另一个路由器的时间

​ d:物理链路的长度

​ s:媒体中的传播速度 (~2x108 米/秒)
$$d_{prop}=d/s$$
排队时延

假定

​ R=链路带宽 (bps)

​ L=分组长度 (bits)

​ a=平均分组到达速率

流量强度：La/R

​ La/R ~ 0: 平均排队时延很小，甚至为0

​ La/R < 1: 时延较小，且会随时间推延而变小

​ La/R = 1: 时延不会变化，具体数值取决于当时队列长度

​ La/R > 1: 平均时延较大，且随时间推延而趋于无穷!

端到端时延:

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

丢包

分组丢失的原因和后果

​ 缓存中队列的容量是有限的

​ 当分组到达时队列已满，则分组被丢弃 (丢失)

​ 丢失的分组可能会被前一个节点、源端系统重新传输，或者根本不重传

吞吐量：在发送方与接收方之间传输比特的速率（bps）

​ 瞬时吞吐量

​ 平均吞吐量（一个连接的由最小吞吐量的链路决定，这条链路也称为瓶颈链路）

1.5 协议层次及其服务模型

因特网的协议栈

​ 应用层: 支持网络应用

​ FTP, SMTP, HTTP

​ 运输层: 主机间的数据传输

​ TCP, UDP

​ 网络层:将数据报从源端传送到目的端

​ IP, 路由协议

​ 链路层: 数据在网络相邻结点之间传输

​ PPP, 以太网

​ 物理层: 在线路上传输比特流

​ (应 运 网 链 物)

ISO/OSI参考模型

​ 表示层: 允许应用程序解释数据的含义，如：加密、压缩、特定机器的数据描述方法

​ 会话层: 提供了数据交换的同步、定界、建立检查点和恢复的能力

​ (应 表 会 运 网 链 物)

基本概念

实体(Entity)

​ 实体是任何可以发送和接收信息的硬件和软件进程。通常是一个特定的软件模块

对等体(Peer)

​ 不同机器上包含对应层的实体称为对等体

协议(Protocol)

​ 语法，即数据与控制信息的结构或格式

​ 语义，即需发现何种控制信息，完成何种动作以及做出何种应答

​ 同步，即事件实现顺序的详细说明

服务(Service)

​ 为保证上层对等体之间能互相通信，下层向上层提供的功能。

服务原语

​ 服务原语是指网络相邻层间进行交互时所要交换的一些必要命令

服务访问点(SAP)

​ 服务访问点是同一系统中相邻两层的实体进行交互的地方

第二章 应用层

2.1 应用层协议原理

网络应用

网络应用所需采用的体系结构

​ 客户机/服务器体系结构（C/S）:存在一个能够向客户机提供服务的服务器，存在一个或者多个主动连接服务器，试图从服务器那里获取所需服务的客户机

​ 特别注意1：客户机之间不能互相通信

​ 特别注意2：为提高服务器的处理能力，通常采用服务器群集（Server Farm）

​ P2P体系结构:任何一方既提供服务又享受服务,结点之间可以直接通信,结点的地址以及他们之间的连接可能随时发生变化

​ 特别注意：P2P体系结构非常容易扩展，但也特别难以管理

​ 混合体系结构

应用层协议原理

​ 不同主机上的进程之间通信的规则

应用层协议定义了

​ 交换的报文类型

​ 各种报文类型的语法

​ 字段的语义

​ 进程何时、如何发送报文及对报文进行响应

使用传输层协议

​ TCP

​ 面向连接: 在客户端和服务器进程之间需要建立连接

​ 可靠传输:在发送和接受进程之间

​ 流量控制: 发送数据的速度决不超过接收的速度

​ 拥塞控制: 当网络超负荷时，束紧发送端口，减缓发送速度

​ 不提供: 实时性, 最小带宽承诺

​ UDP

​ 在客户端和服务器进程之间实现“不可靠的”数据传输

​ 不提供:连接建立, 可靠性保证,流量控制,拥塞控制,实时性, 最小带宽承诺

每个网络应用进程都有一个属于自己的套接字，该套接字在整个因特网上独一无二，进程通过套接字来接收和发送报文

套接字相当于一个通道

​ 发送进程将报文交给套接字

​ 套接字将这些报文传输到接收进程的套接字

重点讨论的网络应用

WEB 文件传输 电子邮件 目录服务 P2P

2.2WEB和HTTP

WEB的构成

​ WEB服务器：IIS、Apache、TomCat……

​ 浏览器：IE、Maxthon、Firefox

​ 协议

​ 信息表达的协议——HTML

​ web内容表达：web页面由对象组成，任何对象可以用URL来定位

​ 信息传输的协议——HTTP

​ C/S模式

​ http1.0: RFC 1945 ——非持久性连接：取对象需要2RTTs 建立TCP连接、对象请求传送

​ http1.1: RFC 2068 ——持久连接：建立TCP后不立即断开

非流水线方式：一个对象传输完成方能传输下一个

流水线方式：可以一次性发送所有请求，慢慢接收

​ http使用TCP传输，端口号为80

​ 特别说明：WEB属于C/S模式

HTTP请求报文

• 一段典型的HTTP报文

• HTTP报文格式

HTTP1.0 定义的方法

GET

​ 向服务器请求指定URL的对象

POST

​ 用于向服务器提交表单数据

​ 也可以同时请求一个WEB页面

​ 特别注意：可以不使用POST方法，而使用GET方法发送表单数据以获取新的WEB页面。e.g. 搜索引擎

HEAD

​ 请求服务器返回一个响应报文，但是该报文中并不包含请求的对象。该方法常常用来进行故障跟踪。

HTTP1.1新定义的方法

PUT

​ 上传的文件放在实体主体字段中，目标路径由URL字段标明

DELETE

​ 删除URL字段中指定的文件

HTTP响应报文

• 一段典型的HTTP响应报文

• HTTP响应报文的一般格式

常见的HTTP响应状态码和短语

200 OK

​ 请求成功, 被请求的对象在报文中

301 Moved Permanently

​ 被请求的对象被移动过, 新的位置在报文中有说明 (Location:)

400 Bad Request

​ 服务器不懂请求报文

404 Not Found

​ 服务器上找不到请求的对象

505 HTTP Version Not Supported

​ 服务器不支持请求报文使用的HTTP协议版本

用户服务器交互：Cookie

WEB站点使用Cookie的目的

​ 限制用户的访问

​ 把内容和用户身份关联起来

Cookie技术的组成部分:

​ 在HTTP响应报文中有一个Cookie首部行

​ 在HTTP请求报文中也有一个Cookie首部行

​ 在用户的端系统中保留了一个Cookie文件，由用户浏览器负责管理

​ 在Web站点有一个后端数据库

第三章 运输层

3.1 概述和运输层服务

运输层的功能

​ 为不同主机上运行的应用进程之间提供逻辑通信(logical communication)

运输层协议的工作内容

​ 发送方：把应用数据划分成报文段(segments),交给网络层

​ 接收方：把报文段重组成应用数据，交付给应用层

因特网上的运输层协议

用户数据报协议UDP（数据报）

传输控制协议TCP（报文段）

所提供的服务

​ 进程间数据交付

​ 差错检测

​ 可靠的数据传输

​ 拥塞控制

3.2 多路复用与多路分解

多路复用和多路分解是所有计算机网络都需要的。

多路复用:将运输层报文段中的数据交付到正确的套接字的工作，即从同一台主机上的不同Socket接收数据的过程

多路分解:在源主机从不同套接字中收集数据块并为每个数据块封装上首部信息从而生成报文段，然后将报文段上传到网络层的工作，即向同一台主机上的不同Socket传输数据的过程称为多路分解

传输层和应用程序进程之间通过Socket（套接字）关联，每个套接字都有一个唯一的ID，被称为端口号，端口号大小在0-65535之间，其中0-1023属于周知端口号，它们为特定的Socket而拥有。

• 无连接的多路复用与多路分解

创建的套接字具有主机本地端口；

一个UDP套接字是由一个目的IP地址和目的端口号即二元组来标志的；

当主机接收到UDP段：检查报文段目的地端口；将UDP报文段发送给端口号的套接字

如果两个UDP报文段有不同的源IP地址或者源端口号，但是有相同的目的IP和目的端口号的话，它们将通过同一个Socket到达同一个应用程序

• 面向连接的多路复用与多路连接

TCP协议中的Socket是通过一个四元组来标记的：（源IP地址，源端口号，目的IP地址，目的端口号）；

服务器主机同时支持多个并发的TCP套接字:每一个套接字都由其四元组来标识

Web服务器为每一个客户连接都产生不同的套接字

非持久HTTP对每一个请求都建立不同的套接字（会影响性能）

两个具有不同源IP地址或者源端口号，但有相同的目的IP地址和目的端口号的TCP报文段将通过两个不同的Socket进入同一应用进程；

一个应用进程可以关联多个Socket，而一个Socket将只关联一个应用进程；这样的对应关系是通过线程来实现的：一个进程有多个线程，而每个线程关联了一个Socket；这样做可以提高服务器性能。

3.3 无连接传输 : UDP

一个最简单的运输层协议即UDP必须提供

​ 多路复用/多路分解服务

​ 差错检查

• UDP处理数据的流程

​ 发送方
​ 从应用进程得到数据
​ 附加上为多路复用/多路分解所需的源和目的端口号及差错检测信息，形成报文段（数据报）
​ 递交给网络层，尽力而为的交付给接收主机

​ 接收方
​ 从网络层接收报文段（数据报）
​ 根据目的端口号，将数据交付给相应的应用进程

• UDP的优势

​ 无需建立连接——建立连接会增加时延
​ 简单——发送方和接收方无需维护连接状态
​ 段首部开销小——TCP:20Byte vs UDP:8Byte
​ 无拥塞控制——UDP 可按需要随时发送

• UDP的检查和
  目标
  检测收到的报文段的“差错” (例如, 出现突变的比特)
  发送方
  把报文段看作是16比特字的序列
  检查和：对报文段的所有16比特字的和进行1的补运算(最高有效位的进位要回卷加到结果当中)
  发送方将计算校验和的结果写入UDP校验和字段中
  接收方
  计算接收到的报文段的校验和
  检查计算结果是否与收到报文段的校验和字段中的值相同
  不同 — 检测到错误
  相同 — 没有检测到错误(但仍可能存在错误)

3.4 可靠数据传输的原理

• 可靠信道上的可靠传输—— rdt 1.0
  底层信道完全可靠
  不会产生比特错误
  不会丢失分组
  分别为发送方和接收方建立FSM
  发送方将数据发送给底层信道
  接收方从底层信道接收数据

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Orig72RK-1606530179679)(D:\素材\image-20201124110604123.png)]

• 信道可能导致比特出现差错时——rdt 2.x

• 第一个版本——rdt 2.0
  假设
  分组比特可能受损
  所有传输的分组都将按序被接收，不会丢失
  处理机制
  如何判断分组受损——差错检测
  如何通知发送方分组是否受损——接收方反馈（ACK和NAK）
  在得知分组受损后，发送方如何处理——出错重传

• 第二个版本——rdt 2.1

  问题的引入：ACK和NAK分组可能受损，而rdt 2.0没有考虑该情况

• 第三个版本——rdt 2.2
  针对rdt 2.1的改进

  ​ 只使用ACK
  ​ 取消NAK，接收方对最后一个正确收到的分组发送 ACK
  ​ 接收方必须明确指出被确认的分组的序号
  ​ 发送方收到的重复的ACK将按照NAK来进行处理
  ​ 重传正确的分组

  

• 信道不但出错，而且丢包时——rdt 3.0

因为分组序号在 0 和 1 之间交替，因此 rdt 3.0 有时被称为 比特交替协议。

rdt3.0吞吐率低---->流水线技术---->GBN与SR协议

• Go-Back-N协议

  特点
  ACK(n): 接收方对序号n之前包括n在内的所有分组进行确认 - “累积 ACK”
  对所有已发送但未确认的分组统一设置一个定时器
  超时(n): 重传分组n和窗口中所有序号大于n的分组
  失序分组:
  丢弃 (不缓存) -> 接收方无缓存!
  重发按序到达的最高序号分组的ACK

  Go-Back-N的滑动窗口大小
  发送端 ≤ 2^k-1
  接收端 ＝ 1

选择重传（SR）协议

发送方:

从上层收到数据 :
如果下一个可用于该分组的序号在窗口内，则将数据打包并发送
超时(n):
重传分组n, 重置定时器
收到确认(n) 在 [sendbase,sendbase+N-1]范围内
标记分组 n 为已接收
如果n是发送窗口基序号sendbase，则将窗口基序号前推到下一个未确认序号

接收方

分组序号n在[rcvbase, rcvbase+N-1]范围内
发送n的确认ACK(n)
如果分组序号不连续(失序)：将其缓存
按序分组: 将该分组以及以前缓存的序号连续的分组一起交付给上层, 将窗口前推到下一个未收到的分组
分组序号n 在 [rcvbase-N,rcvbase-1]范围内：
虽然曾经确认过，仍再次发送n的确认ACK(n)
其他情况: 忽略该分组

3.5 面向连接的传输 : TCP

• TCP概述—RFCs：793、1122、1323、2581(2018年）
  面向连接
  全双工服务
  点对点连接
  可靠有序的字节流
  流量控制
  拥塞控制
  流水线

• TCP报文段首部结构
  

序列号：
在报文段数据中第一个字节在字节流中的编号

确认ack：
期待得到的下一个字节的seq
ACK累积

超时重传间隔:

​ 估算RTT：

​ 估算偏差：

​ 超时间隔:

TCP编号采用按字节编号，而非按报文段编号
TCP仅采用唯一的超时定时器

快速重传: 在超时到来之前重传报文段

如果发送收到一个数据的3个重复ACK，它会认为确认数据之后的报文段丢失

• 超时间隔加倍:超时事件发生后，TCP重传，会将TimeoutInterval加倍；

定时器在收到上层应用数据或收到ACK后，TimeoutInterval变为由EstimatedRTT与DevRTT估算得到。

• TCP流量控制：接收方应用进程从缓冲区中读取数据可能很慢，为了防止发送方不会由于传得太多太快而使得接收方缓存溢出，所以当接收方在反馈时，将缓冲区剩余空间的大小填充在报文段首部的窗口字段中，通知发送方。

接收方窗口大小计算:

• TCP连接建立/断开(三次握手四次挥手):

3.6 拥塞控制原理

• 拥塞原因与代价:

​ 网络中的分组太多，而链路带宽和路由器缓存容量都是有限的

​ 当分组的到达速率接近链路容量时，分组将经历巨大的排队时延；
​ 发送方必须执行重传已补偿因为缓存溢出而丢弃的分组
​ 发送方遇到大时延时所进行的不必要重传会引起路由器利用其链路带宽来转发不必要的分组副本。
​ 当一个分组沿着一条路径被丢弃时，每个上游路由器用于转发该分组到丢弃该分组而使用的传输容量最终被浪费掉了

• 拥塞控制方法

网络辅助的拥塞控制
直接网络反馈：路由器以阻塞分组的形式通知发送方“网络拥塞了”
经由接收方的网络反馈：路由器标识从发送方流向接收方分组中的某个字段以指示 拥塞的产生，由接收方通知发送方“网络拥塞了”
端到端拥塞控制
网络层不为拥塞控制提供任何帮助和支持
端系统通过对网络行为（丢包或时延增加）的观测判断网络是否发生拥塞
目前TCP采用该种方法

3.7 TCP拥塞控制

• TCP发送方如何限制外发流量的速率
  拥塞窗口
  LastByteSent - LastByteAcked <= min{CongWin，RcvWindow}

发送速率大概是：

• 发送方如何感知拥塞

​ 超时
​ 三个冗余ACK

• 在感知到拥塞后，发送方如何调节发送速率

• TCP拥塞控制算法（Reno算法）

慢启动
建立连接时, CongWin = 1 MSS
例如: MSS = 500 bytes & RTT = 200 msec
初始速率 = 20 kbps
可用带宽 >> MSS/RTT
初始阶段以指数的速度增加发送速率
连接初始阶段，以指数的速度（2倍）增加发送速率，直到发生一个丢包事件为止
每收到一次确认则将CongWin的值增加一个MSS

对收到3个重复ACK的反应——快速重传
门限值设为当前CongWin的一半（门限值初始值65kB）
将CongWin减为新的门限值+3MSS
线性增大拥塞窗口
对超时事件的反应
门限值(ssthresh)设为当前CongWin的一半（门限值初始值65kB）
将CongWin设为1个 MSS大小;
窗口以指数速度增大
窗口增大到门限值之后，再以线性速度增大

快速恢复（TCP推荐但非必须实现）

​ 3个冗余ACK进入快速重传后
​ 每收到一个冗余ACK：CongWin++
​ 直至收到一个新的ACK：CongWin=门限值，重新进入拥塞避免
​ 在进入快速恢复之后及重新进入拥塞避免之间，如果出现超时现象，直接按照前述超时事件进行处理

​ 额外说明
​ 快速恢复和超时中，门限值并不总等于CongWin/2
​ 门限值=Max(flightSize/2 , 2MSS)
​ flightsize:当时发送窗口中已发出但未确认的报文段数目

​ 门限值=Max(min(拥塞窗口,通知窗口) , 2MSS) –微软

TCP吞吐量的进一步讨论

TCP吞吐量宏观描述:0.75 W/RTT

吞吐量是丢包率(L)的函数（经高带宽路径的TCP）:

对于一条MSS=1500字节，RTT=100ms的TCP连接而言，如果希望达到10Gbps的吞吐量，那么丢包率L不能高于2x10^(-10)

• TCP的公平性

公平性和UDP

​ 多媒体应用一般不使用 TCP
​ 不希望因为拥塞控制影响其速率
​ 多媒体应用采用UDP:
​ 恒定的速率传输音频和视频数据，可容忍丢包

公平性和并行TCP连接
无法阻止应用在两个主机之间建立多个并行的连接.
Web浏览器就是这样
例子: 速率为R 的链路当前支持9个并发连接;
应用请求一个TCP连接，获得R/10的速率
应用请求11个TCP连接，获得R/2的速率!

第四章 网络层(数据平面)

4.1 网络层概述

• 网络层的目标

​ 实现主机到主机的通信

• 网络层在计算机网络中的地位

​ 为运输层提供支持
​ 运输层实现进程到进程的通信
​ 运输层功能的实现依赖于网络层提供的服务
​ 为实现从源主机到目标主机成功的移动数据分组，整个路径上的每一台分组交换机上均需实现网络层

• 网络层的主要功能

​ 在全局范畴为主机之间的通信进行选路，选路的结果反映为分组交换机上的转发表
​ 分组交换机上的网络层根据转发表以及分组头部信息，将分组向适当链路进行转发
​ 对于面向连接的网络层服务，提供连接建立的功能
​ ATM、X.25和帧中继

​ 转发(数据平面):当一个分组到达某路由器的一条输入链路时，该路由器必须将该分组移动到适当的输出链路。

​ 路由选择(控制平面):

• 分组交换机的分类

​ 根据链路层首部信息进行转发的——链路层节点交换机
​ 根据网络层首部信息进行转发的——路由器

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

• IP 数据报格式

• 版本号（IPv4、IPv6）：不同版本对数据报不同解释
• 首部长度：数据报可包含可变数量的选项。不过大部分没有，首部固定20字节
• 服务类型：区分不同类型的IP数据报
• 数据报长度：首部+数据的长度。该字段16bit，故理论上最大长度为65535字节，然而一般数据报很少超过1500字节。
• 标识、标志、片偏移：IP分片相关。不过IPv6不允许在路由器上对分组分片
• 寿命TTL：确保数据报不会永远在网络中循环。每被一个路由器处理时，值-1。若值减到0，丢弃数据报。
• 协议号：到达最终目的地才有用，指示了IP数据报的数据部分应该交给哪个运输层协议。如6交给TCP，如17交给UDP。协议号是将网络层与运输层绑定到一起的粘合剂；端口号是将运输层和应用层绑定的粘合剂
• 首部检验和：帮忙路由器检测收到IP数据报中首部的比特错误，有错一般丢弃。每台路由器上必须重新计算检验和。IP层仅对IP首部计算检验和，而TCP/UDP检验和是对整个TCP/UDP报文段进行的。
• 源和目的IP地址：源主机通常通过DNS查找目的地址
• 选项：IPv6已抛弃选项字段
• 数据（有效载荷）：包含运输层报文段（TCP或UDP），或ICMP报文段

一个IP数据报有长为20的首部，如果数据报承载一个TCP报文段，则每个无分片数据报承载总长40的首部（还有TCP的20）以及应用层报文
IP数据报分片 more

网络链路存在MTU (最大传输单元)—链路层数据帧可封装数据的上限不同链路的MTU不同

IPv4的设计者决定把数据报的重新组装工作放在端系统而不是路由器中。

大IP分组向较小MTU链路转发时， 可以被“分片” (fragmented)

1个IP分组分为多片IP分组
IP分片到达目的主机后进行“重组”(reassembled)

IP首部的相关字段用于标识分片以及确定分片的相对顺序

总长度、标识、标志位和片偏移

假设原IP分组总长度为L，待转发链路的MTU为M
若L>M，且DF=0，则可以/需要分片
分片时每个分片的标识复制原IP分组的标识
通常分片时，除最后一个分片，其他分片均分为MTU允许的最大分片

最后一个片的标志为0，其余的为1.

例：

4000字节的数据报，在MTU1500字节的链路上

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pjyaFjnQ-1606530179688)(D:\素材\20190326135559160.png)]

数据报的有效载荷仅当在IP层已完全重构为初始IP数据报时，才会传递给目的地传输层。如果一个或多个片没有到达目的地，则该不完整的数据报被丢失。
并不是所有链路层协议都能承载相同长度的网络层分组，如以太网帧能承载不超过1500字节的数据，某些广域网链路帧不超过576字节
一个链路层帧承载的最大数据量：最大传送单元MTU
限制了IP数据报的长度，且发送方与目的路径上的每段链路可能使用不同的链路层协议，有不同的MTU。

1）如何将过大的IP分组压缩进链路层帧的有效载荷字段？
将IP数据报中的数据分片成多个较小的IP数据报，用单独的链路层帧封装这些小IP数据报，每个小数据报叫片
IPv4将数据报的重新组装放在端系统中，而不是路由器中
标识、标志、片偏移字段，帮助主机执行重组任务
一个4000字节的数据报（20+3980）到达一台路由器，转发到一条MTU为1500子节的链路上。必须分配3个独立的片，假设初始数据报的标识号是777，则前两片字节都为20+1480，第三层为20+1020
IPv6废除了分片，简化了IP分组的处理

IPV4编址

主机与路由器连入网络的方法

• ​ 一台主机通常只有一条链路连接到网络，主机IP发送数据报从该链路发送
• ​ 主机与物理链路的边界叫接口，一台路由器有多个接口
• ​ IP要求每台主机和路由器都有自己的IP地址，因此一个IP地址实际上是与每一个接口相关联的
• ​ 每个IP地址长度32bit（4字节），总共2^32个可能的IP地址，约40亿个
• ​ 点分十进制记法，如193.32.216.9
• ​ 一个接口的IP地址的一部分需要由其连接的子网决定.如互联3个主机接口与1个路由器接口的网络形成一个子网，IP编址为这个子网分配一个地址：223.1.1.0/24，/24记法称为子网掩码，指示了32bit中的最左侧24bit定义了子网地址
• ​ 为了确定子网，分开主机和路由器的每个接口，产生几个隔离的网络岛，使用接口端接这些隔离的网络的端点，这些隔离的网络中每一个都叫做一个子网
• ​ 因特网地址分配策略：无类别域间路由选择CDIR
• ​ a.b.c.d/x的地址的x最高比特构成IP地址的网络部分，称为该地址的前缀，一个组织通常被分配一块连续的地址，即具有相同前缀的一段地址。BGP路由选择协议中，该组织网络外的路由器仅考虑x，减少了转发表的长度，因为形式为a.b.c.d/x单一表项足以将数据报转发到该组织内的任何目的地
• 地址聚合（路由聚合）：使用单个网络前缀通告多个网络的能力

​ 一个ISP将8个组织连接到因特网。该ISP向外界通告：向我发送以200.23.16.0/20开始的任何内容。外部无需知道在该地址块内还有8个其他组织，每个组织有自己的子网

• 一个地址的剩余32-x比特可认为是用于区分该组织内部设备的。组织内部路由器转发分组时，才会考虑这些比特
• 在CDIR出现之前，采用分类编址，A、B、C类网络，分别具有8、16、24比特子网地址

​ E类：240.0.0.0~255.255.255.255

​ D类 224.0.0.0~239.255.255.255

​ C类（/24）仅能容纳2^8-2=254台主机（其中两个用于特殊用途）192.0.0.0~223.255.255.255

B类（/16）支持65534台主机，一个组织分配一个B类地址却只用2000个接口，造成巨大浪费 128.0.0.0~191.255.255.255

A类 （/8）0.0.0.0~127.255.255.255

IP广播地址
当一台主机发出目的地址为255.255.255.255的数据报时，报文会交付给同一个网络的所有主机，路由器也会有选择的向邻近的子网发送报文（通常不这样做）。可用于DHCP发现报文的发送，广播最小生成树

如何获取地址、分配地址？
1. 获取一块地址
子网获取IP地址：由ISP从它大块地址中分配
ISP获取IP地址：IP地址由因特网名字和编号分配机构ICANN管理（也管理DNS根服务器、AS标识号）。ICANN向区域性因特网注册机构分配地址，处理本地域内的地址分配/管理
2.获取主机地址
组织获得一块地址，就可为组织内的主机、路由器接口逐个分配IP地址
主机地址能手动配置，也能自动配置，即动态主机配置协议DHCP
3.动态主机配置协议DHCP—UDP
DHCP允许主机自动获取一个IP地址
DHCP可配置，可以使主机每次连网获得相同IP地址，也可每次分配一个临时IP地址。
DHCP还允许主机查看子网掩码、默认网关（第一跳路由器地址）、本地DNS服务器地址
DHCP能将主机连接进一个网络的自动能力，常被称为即插即用协议
DHCP是一个客户-服务器协议。新来的主机要获得自使用的IP地址等网络配置信息
每个子网都有一台DHCP服务器
若子网没有DHCP服务器，则由一个路由器做DHCP中继代理，该代理知道该网络的DHCP服务器地址

新主机到来时，DHCP协议的四个步骤

​ 1.DHCP服务器发现

​ 新到的客户通过广播DHCP发现报文，发现一个要与其交互的DHCP服务器
​ 客户在UDP分组中向端口67发送该发现报文，此时必须用广播地址255.255.255.255，源地址是0.0.0.0
​ 2.DHCP服务器提供
​ DHCP收到DHCP发现报文后，响应一个DHCP提供报文，仍然使用广播地址，因为此时新客户并没有IP地址
​ 可能有多台DHCP服务器，每台服务器提供的报文中，有向客户主机推荐的IP地址、网络掩码以及IP地址租用期（一般几天或几小时）
​ 3.DHCP请求
​ 客户从提供中选一个，向选中的服务器提供一个DHCP请求报文进行响应，回显配置参数
​ 4.DHCP ACK
​ 收到DHCP请求报文后，用DHCP ACK报文对其记性响应，证实所传参数
​ 客户收到ACK后，交互完成，在租期内使用DHCP分配的IP地址。DHCP提供了机制允许客户更新对一个IP地址的租用

当一个移动结点在子网之间移动时，就不能维持与远程应用的TCP连接。

DHCP协议并不仅仅只能获取IP地址
网关地址
DNS地址
子网掩码

网络地址转换NAT

地址10.0.0.0/8是保留的3个IP地址空间之一，这些地址用于家庭网络等专用网络或具有专用地址的地域。具有专用地址的地域是指其地址仅对还网络中的设备有意义的网络。

当ISP已经为SOHO网络当前地址范围分配过一块连续地址，而SOHO内主机越来也多时，需要用到NAT（比如电信给你家分配一个动态IP地址，家里要好几台手机电脑联网用一个IP地址，需要用NAT）。

​ NAT使能路由器
​ NAT路由器对外界来看像一个具有单一IP地址的单一设备。例如，家里有一个NAT使能路由器，其IP地址138.76.29.7，且进入和离开家庭的报文都有同样的该地址
​ NAT路由器对外隐藏了家庭网络的细节
​ NAT路由器从ISP的DHCP服务器得到它的地址，并且路由器运行一个DHCP服务器，为位于NAT-DHCP路由器控制的家庭网络地址空间中的主机提供地址

实现
发送数据报: 将每个外出报文的源IP地址,端口号替换 为NAT IP地址以及新的端口号
. . . 远程客户机/服务器将以NAT IP 地址以及新的端口号做为目的地址进行响应.
记住每一个地址转换对 (在 NAT 转换表中) ，即
源IP地址,端口号 NAT IP 地址,新的端口

​ 接收数据报:根据NAT转换表将每个进入报文的NAT IP地址,端口号替换为相应的源IP地址以及端口号

​ NAT转换表：

​ 端口号和IP地址用于路由器将分组转发给特定的内部主机（比如家里的某个手机）

​ 两类地址
​ 本地地址
​ 10/8
​ 172.16/12
​ 192.168/16
​ 全球地址
​ 三种地址转换方式
​ 静态NAT：一个本地地址对应一个全球地址
​ 动态NAT：一个全球地址对应多个本地地址
​ 端口NAT：一个本地地址的端口对应到一个全球地址的端口

​ NAT重要问题：
​ 违反各种原则:端口号是用于进程编址的，而不是用于主机编址的;路由器仅应当处理高达第三层的分组;NAT协议违反了端到端原则，即主机彼此应相互直接对话，节点不应介入修改IP地址和端口号，应该用IPv6来改进。
​ 妨碍P2P应用程序，包括P2P共享和语音。一个对等方在NAT后面，不能充当服务器并接受TCP连接，其解决办法是连接反转
​ 连接反转：A通过C与B联系，C不位于NAT之后并与B建立了TCP连接，已经被很多P2P应用用于NAT穿越
​ 若对等方A和B都在NAT之后，使用应用程序进行中继处理，如Skype中继
UPnP
​ NAT穿越由通用即插即用（UPnP）提供
​ UPnP是一种允许主机发现并配置邻接NAT的协议，要求主机和NAT都是UPnP兼容（运行在NAT使能路由器）。允许外部主机使用TCP和UDP向NAT化的主机发起通信会话。
​ 使用UPnP，在主机上运行的应用程序能为某些请求的公共端口号请求一个NAT映射**（专用IP地址，专用端口号 — 公共IP地址，公共端口号）**。如果某NAT接收请求并生成映射，来自外部的结点能发起到（公共IP地址，公共端口号）的TCP连接。

IPv6

IPv4地址耗尽，也可升级强化IPv4某些方面
IPv6数据报格式（不一样的地方）

• ​ 扩大的地址容量

  ​ 32bit —> 128bit
  ​ 除了单播多播地址，引入任播地址，使数据报交付给一组主机中的任意一个

• ​ 简化高效的40字节首部

• ​ 流标签与优先级。 如音频流、视频流、高优先级用户承载的流量

• ​ 中间结点不再负责分片和重组，由端结点负责

• ​ 选项 放到了『下一个首部』位置，使得IP首部定长40字节

• ​ 去除首部检验和

  IPv6字段

• 版本号(version)

  不同的IP协议版本使用不同的数据报格式。

• 通信量等级(Traffic Classes)

  使得源节点和路由器能够识别IPv6信息包的优先级。与IPv4服务类型TOS字段含义类似。

• 流标签(Flow Label)

  标记那些需要IPv6路由器特殊处理(如一种非默认服务质量或实时服务)的信息包顺序。

• 有效负载长度(Payload Length)

  定长40字节数据报首部后面的字节数量，包括扩展报头和负载数据，即数据报长度-40。

• 下一个首部(Next Header)

  当IPv6没有扩展报头时，该字段的作用和IPv4的上层协议字段一样。当含有扩展报头时，该字段的值即为第一个扩展报头的类型。

• 跳限制(Hop Limit)

  转发数据报的每台路由器对该字段的值减1，若减为0则丢弃该数据报。

• 源和目的IP地址(Source/Destination Address)

• 数据(Data)

  当数据报到达目的地时，该有效载荷就从IP数据报移出，并交给下一个首部字段中指定的协议。

• 源和目的IP地址(Source/Destination Address)

IPv4到IPv6的迁移

​ 设立标志日，统一迁移

​ 双栈技术：同时使用IPv4和IPv6，这种结点有两种地址。DNS可解析两种地址。如果发送方和接收方中任意一个仅为IPV4使能的，则必须使用IPv4数据报。

隧道技术 例：

结点B必须生成一个IPv4数据报发给C，IPv6数据报的数据字段可以复制到IPv4数据报的数据字段中，并且要做适当的映射。在IPv4中没有对应的部分的数据，这些字段的信息会丢失

图中B和E，要使用IPV6交互，但是它们经由中间IPv4路由器关联的，我们将两台IPv6路由器之间的Ipv4路由器的集合成为一个隧道，将整个IPv6数据报放在IPv4的有效载荷中。

第五章 网络层(控制平面)

5.1 概述

转发表和流表的计算、维护和安装：

​ 每台路由器控制:路由器选择算法

​ 逻辑集中式控制

5.2 路由选择算法

• 几个概念

​ 默认路由器：一台主机“直接”连接到的路由器
​ 源路由器：源主机的默认路由器
​ 目的路由器：目标主机的默认路由器

• 根据信息是全局性还是分散式的进行分类

全局选路算法

​ 所有路由器都知道整个网络拓扑图以及链路的费用信息
​ 链路状态算法（LS算法）
分散式选路算法

​ 每个路由器仅有与其相连链路的费用信息
​ 通过迭代计算过程与相邻节点交换信息
​ 距离向量算法（DV算法）

• 根据信息是静态还是动态的进行分类

静态选路算法
随着时间的流逝，路由的变化非常缓
动态选路算法(更容易受选择循环和路由震荡影响)
路由信息可以更快地发生变化
周期性的更新
可以响应拓扑或链路费用的变化

• 还可以根据是否负载敏感和负载迟钝划分(链路开销是否明确反映当前的拥塞水平)为负载敏感算法和负载迟钝算法(如RIP、OSPF与BGP)

• LS算法——Dijkstra’s（迪克斯特拉）算法

所有节点都知道网络拓扑和链路费用
通过链路状态广播获得信息
所有节点具有该网络的同一个完整的视图
计算从某节点到网络中所有其他节点的最低费用
为该节点提供转发表
迭代: 经算法的K次迭代后，可知道到K个目的节点的最低费用路径

c(x,y): 从节点x到节点y的链路费用; 如果x和y不是直连的，则 c(x,y) = ∞
D(v): 随着算法进行本次迭代，从源节点到目的v的最低费用路径的费用
p(v): 从源节点到v沿着当前最低费用路径的前一节点
N‘: 节点子集。v在N‘中，如果从源节点到路径的最低费用路径已知

1  Initialization: 
2    N' = {u} 
3    for all nodes v 
4      if v adjacent to u 
5          then D(v) = c(u,v) 
6      else D(v) = ∞ 
7 
8   Loop 
9     find w not in N' such that D(w) is a minimum 
10    add w to N' 
11    update D(v) for all v adjacent to w and not in N' : 
12       D(v) = min( D(v), D(w) + c(w,v) ) 
13    /* new cost to v is either old cost to v or known 
14     shortest path cost to w plus cost from w to v */ 
15  until all nodes in N' 

Dijkstra’s（迪克斯特拉）算法的复杂性

​ 对于第一次迭代: 需要搜索所有的n个节点以确定出节点w，w不在N’中且具有最低费用
​ 在所有迭代中需要搜索的节点总数为n(n+1)/2 ，所以链路状态算法在最差情况下复杂性为 O(n2)
​ 该算法的一种更复杂的实现，使用一种叫做堆的数据结构，其计算复杂性为 O(mlogn)

拥塞敏感路由选择的震荡解决的方案

​ 强制链路费用不依赖于所承载的流量
​ 无法解决高拥塞的问题，不可接受
​ 确保所有的路由器不同时运行LS算法
​ 因特网上的路由器能够自同步
​ 随机化路由器发送链路通告的时间

• 距离向量选路算法

特点：迭代、分布、自我终止、异步

思想
B-F公式：dx(y)=minv{c(x,v)+dv(y)}
每个路由器中都有一张路由表，包含三个内容：目的网络号、经过的邻居路由器、距离
路由器定期向其邻居路由器传送路由表的拷贝

路由表的更新算法
路由器X得到相邻路由器Y的路由表，从而得知：Y到网络Z的最短距离为N
如果路由器X没有到网络Z的路由条目，则添加一条经由路由器Y到网络Z距离N+1的路由条目
如果路由器X已有到网络Z的路由条目，其距离为M，如果M>N+1，则更新该条目为经由路由器Y到网络Z距离N+1，否则不更新

链路状态改变时的特点
好消息传的快
在 t0 时刻, y 检测到链路费用变化, 更新自己的距离向量, 同时将这个变化通知给它的邻居
在 t1时刻, z 收到来自 y 的更新报文并更新了自己的距离向量表，计算出到x的新的最低费用，并向邻居发送它的新距离向量
在 t2时刻，y 收到自z的更新并更新其距离向量表，Y的最低费用未变，因此y不发送任何报文给z

坏消息传播的慢
无穷计数
路由环路

解决方案——毒性逆转
如果z通过y选路到达目的地x :
z将通告y，它到x的距离是无穷大 (所以 y不会通过z到达x)
毒性逆转没有解决一般不可记数问题(三个或更多结点的环路无法检测)！

• 链路状态路由选择算法 vs 距离向量路由选择算法

报文的复杂性
LS: n 个节点, E 条链路,需要发送 O(nE)个报文
DV: 只在直连的邻居之间交换报文

收敛速度
算法收敛时间依赖于许多因素，因而是可变的
LS: 是一个要求O(nE)个报文的O(n2) 算法
可能有震荡
DV: 收敛时间不确定
可能会遇到选路环路
记数到无穷问题

健壮性
LS:
节点能够向其连接的链路广播不正确费用
每个节点只计算自己的转发表
DV
一个节点可向任意或所有目的节点通告其不正确的最低费用路径
每个节点的计算都会传递给它的邻居
错误会通过网络进行传播

• 因特网上的距离向量算法——RIP协议

​ 相邻两点间链路上的费用定义为1，即只考虑源到目标经过多少个路由器，或多少“跳”
​ 一条路径的最大费用限制为15
​ 选路更新消息每30s在邻居之间以RIP响应报文（RIP通告）的形式进行交换
​ 路由器经过180s没有收到来自某个邻居的RIP通告，则认为该邻居已离线，修改选路表，向其它邻居广播
​ RIP是一个运行在UDP上的应用层协议（端口520）

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

• 层次路由
  问题背景
  因特网规模过大——数亿个目标网络
  路由器无法存储每台主机的选路信息
  路由表更新的报文广播将导致无剩余带宽供发送数据使用
  管理自治
  因特网 = 网络的网络
  每个网络管理员可能希望能够按照自己的愿望运行和管理其网络

• 解决方法

将路由器聚合到一个区域, “自治系统” (AS)
在相同AS内的路由器可全部运行同样的选路算法
自治系统内部选路协议
内部网关协议 IGP (Interior Gateway Protocol) 目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。
在不同AS内的路由器可以运行不同的自治系统内部选路协议

转发表是由AS内部选路算法和AS间选路算法共同决定的
AS内部选路算法为内部目的地址设置转发表信息
AS内部选路算法和AS间选路算法共同为外部目的地址设置转发表信息

• 因特网中的链路状态选路——OSPF协议

​ “开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。
​ “最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法SPF
​ OSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。
​ 是分布式的链路状态协议。

​ 三个要点

​ 向本自治系统中所有路由器发送信息，使用的方法是洪泛法
​ 发送的信息就是与本路由器相邻的所有路由器的链路状态
​ 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息

​ 由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库
​ 这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的
​ OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点

​ 不强制如何设置链路权值的策略，但提供对给定链路权值集合确定最低费用路径的机制
​ 即使链路状态未发生变化，每30分钟广播一次链路状态,增加了健壮性
​ 链路状态以OSPF通告的形式封装在OSPF报文中，由IP分组承载（协议号：89）
​ OSPF路由器之间的交换都是经过鉴别的（简单的、MD5的），以确认OSPF通告的真实性，防止伪造和篡改
​ OSPF通告都是有序列号的，以防止重放攻击
​ OSPF中支持多条具有相同费用的路径

第六章 链路层和局域网

6.1 链路层概述

• 节点：主机和路由器
  链路：沿着通信路径连接相邻节点的通信信道
  有线链路
  无线链路
  帧：数据链路层的分组单元

• 链路层提供的服务

成帧 、链路访问
将数据加上头部和尾部，封装成数据帧
共享介质的信道访问
帧头部用MAC地址标识源和目的（不同于IP地址）

可靠传递
很少用于误码率低的链路（光纤、双绞线链路）
用于误码率高的链路（无线链路）

流量控制
在相邻的收发节点间限制流量

差错检测
信号衰减和电磁干扰噪声导致出错
接收方检测到错误存在：
给发送方发送信号要求重传或丢弃该数据帧

差错纠正
接收方检测和纠正帧中错误，不用重传

半双工和全双工
半双工时，链路两端的节点都能传输分组，但不能同时传输

• 链路层的实现：在每一台设备上（主机、交换机、路由器），链路层在“适配器”（网卡NIC）或者芯片上实现，直接与主机的系统总线相连，是硬件、软件和固件的结合体。

• 适配器通信

发送方
在一个帧内封装数据报
增加差错检测位，可靠交付，流量检测等

接收方
查找错误,可靠交付, 流量控制等
取出数据报，交给网络层

适配器是半自治单元
帧的接收和发送、检错、丢弃均是自主进行
向上提交数据时，需要节点干预
最终受控于节点

6.2 差错检测和纠正技术

差错检测不是100%可靠的，EDC(差错检测和纠错比特)越长，责出错的概率越低

• 单比特奇偶校验、二位奇偶校验(略)

• 因特网检查和:仅应用与TCP、UDP和IPv4协议中

• 循环冗余校验码(广泛应用，如以太网、802.11WiFi与ATM)

​ 比特的数据，D
​ 选择r＋1比特模式(生成多项式)，表示为G
​ 目标：选择r个CRC比特，R，以便
​ <D,R>恰好能被G整除（模2计算）
​ 接收方已知G，用G去除<D,R> ，若余数非0，则检测到错误
​ 能检测到所有少于r+1比特的错误

6.3 多路访问链路协议

• 点到点链路:PPP/以太网交换机和主机之间的点到点链路

• 广播链路:传统以太网/HFC/802.11无限LAN

​ 单个共享广播信道

​ 两个或多个节点同时传输:相互干扰

​ 碰撞：一个节点同时收到两个或多个信号

• 多址访问协议

分布式算法决定节点如何共享信道，如节点何时可以传输数据
特别注意：有关共享信道的通信（协商）需使用信道本身
没有额外的信道来进行协调

理想的多址访问协议需满足：
假定：信道为速率为R b/s的广播信道
当只有一个节点有数据发送时，该节点的吞吐量为R
当M个节点有数据发送时，每个节点吞吐量为R/M
全分散控制
没有特定节点用于调整传输
没有时钟同步
简单

多址访问协议分类
信道划分协议
将信道划分成小的“片”（时隙、频率、编码）
将“片”分配给节点使用
随机访问协议
信道没有被分割，允许碰撞
碰撞恢复
轮流协议
节点轮流传送，但数据量大的节点轮流更长时间

信道划分协议

TDMA：循环访问信道；每个节点在每次循环中得到固定长度的时隙（时隙长度＝传输单个分组时间）；没有数据发送的时隙空闲

FDMA：信道按频谱分成若干频段；每个节点分配固定频段；在频段不用时该部分信道被闲置和浪费

(在重负荷时，共享信道有效、公平;在轻负荷时效率低：信道访问延时，即使只有一个活动节点，也只能分配到1/N的带宽)

随机访问协议：一个传输节点总是以信道的全部速率进行发送，当有碰撞时涉及碰撞的每个节点反复重发直到该帧无碰撞(历经碰撞时等待一个随机时延)。

时隙ALOHA，最大效率为1/e

纯ALOHA，最大效率为1/（2e）

载波侦听多路访问CSMA（传输前监听，空闲则传送，否则推迟传送）：

​ 非坚持(nonpersistent)CSMA
一旦监听到信道忙（即发现有其他站在发送数据），就不再坚持听下去，而是根据协议的算法延迟一个随机的时间后重新再监听。若进行载波监听时发现信道空闲，则将准备好的帧发送出去。——不能充分利用信道刚刚转入空闲期的这段时间。
​ 时隙非坚持CSMA
采用划分时隙的随机接入CSMA协议，协议规定只能在每个时隙开始时才能发送帧。

​ 1坚持CSMA
​ 当一个站点要传送数据时，首先侦听信道，看是否有其他站点正在传送。如果信道正忙，它就持续等待直到它侦听到信道空闲时，便将数据送出。若发生冲突，站点就等待一个随机长的时间，然后重新开始。——容易在上述这段时间产生冲突。
​ P坚持CSMA
​ 当一个站点要传送数据时，首先侦听信道，看是否有其他站点正在传送。如果信道正忙，它就持续等待直到它侦听到信道空闲时，以概率P发送数据，而以概率（1－P）延迟一段时间τ(网络中最远的端到端的传播时延)，重新监听信道。若发生冲突，站点就等待一个随机长的时间，然后重新开始。——可以在一定程度上克服这些缺点，但却很难选择一个能用于各种通信量强度的P值。所以在实际网络中常选择1坚持。

​

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

在短时间内碰撞被检测
在有线LANs中比较容易:测量信号强度，比较收、发的信号
在无线LANs中比较困难: 传输时接收器是关闭的
碰撞后停止传输，减少信道浪费

强化碰撞：当发送数据的站一旦发现发生了碰撞时，除了立即停止发送数据外，还要再继续发送若干比特的人为干扰信号(jamming signal)，以便让所有用户都知道现在已经发生了碰撞。

争用期:最先发送数据帧的站，在发送数据帧后至多经过时间 2τ（两倍的端到端时延）就可知道发送的数据帧是否遭受了碰撞。以太网的端到端往返时延 2τ称为争用期，或碰撞窗口。经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

（轻负荷时效率高：只有一个节点时，能充分利用信道；在重负荷下: 碰撞的开销）

轮流协议

​ 轮询协议(如蓝牙协议、802.15协议):节点之一被指定为主节点，主节点以循环的方式轮询每个节点。其缺点是引入了轮询时延和主节点失效则信道失效的问题。

​ 令牌传递协议(FDDI、IEEE 802.5):称为令牌的小的特殊帧在节点之间以某种固定的次序交换。一个结点仅当有一些帧要发送时持有令牌，否则立即把令牌教给下一个节点。其缺点是有令牌的开销，以及一个节点的故障可能会使整个信道崩溃。

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

每个信道的下行吞吐量为40Mbps
每个信道的上行吞吐量在30 Mbps

FDM 应用在上行和下行的频率通道上
TDM 上行: 一些时隙被使用, 一些时隙有碰撞
下行信道发送 MAP 帧: 配置下行时隙
电缆乔治解调器在选定的时隙中以随机接入的方式进行传输，没有在下一个下行控制报文中收到请求分配的相应则推断出发生碰撞，它以二进制指数回退要求重新发送。

6.4 交换局域网

• MAC地址（链路层地址，又称为LAN地址、物理地址）
  作用
  在数据链路层标识每块网络适配器，使得能够在广播信道上寻址目标节点
  组成
  48bit（e.g.: 1A-2F-BB-76-09-AD）
  前24bit由IEEE分配管理——OUI号
  后24bit由厂商自行分配
  (MAC地址烧入网络适配器的ROM中，不可更改）

(IP地址在不同的网络间迁移时，需要改变以适应新的网络配置,而MAC不会改变)

• 地址解析协议（ARP）——跨越链路层与网络层的协议

目标
根据目标的IP地址获取其MAC地址
ARP高速缓存
局域网节点的IP/MAC地址映射
< IP; MAC;TTL>
TTL (Time To Live):超过TTL的地址映射会被删除 (一般为20分钟)

互联网下的ARP

• 以太网

最先被广泛应用的局域网技术

便宜
速度：10Mbps->100Mbps->1Gbps->10Gbps->200/400Gbps（2017/12/6 802.3bs）

以太网类型:

​ 总线式以太网

​ 交换式以太网

以太网的帧结构

​ 数据字段:（46字节，1500字节）

​ 前同步码:
​ 总共8字节，前7 字节的格式为 10101010 ，最后一个字节格式为10101011
用于同步发送方与接收方时钟

​ 地址: 6 字节

​ 若适配器收到以太网帧，目的地址为自己的MAC地址或广播地址（如ARP包），就将帧中的数据传给网络层。否则，适配器丢弃该帧。

​ 类型: 上层协议类型 (大多为IP协议，也支持其它协议如Novell IPX 和AppleTalk)

​ CRC: 由接收方检查,若检测到错误，就将该帧丢弃

​ 以太网提供的服务

​ 无连接服务: 在送适配器和接收适配器之间不需要握手

​ 不可靠服务: 接收适配器不发送确认帧或否认帧给发送方

​ 交给网络层的数据报可能存在间隙
​ 若应用使用TCP，间隙会被填充
​ 否则，应用就会看见间隙

以太网使用的CSMA/CD
特点
没有时隙
当适配器侦听到其它适配器在传输，则它不传输帧, 即载波侦听
正在传输的适配器若检测到其它适配器也在传输，则它中止自己的传输, 即碰撞检测
在重新传输之前，适配器要等待一段随机时间，即随机回退

​ 算法
​ 适配器收到来自网络层的数据报，创建帧
​ 若适配器检测到信道空闲，则开始传输帧；若检测到信道忙，就开始等待，直到信道空闲再开始传输该帧
​ 若适配器传输了整个帧而没有检测到其它适配器的传输，则该适配器完成该帧的传输
​ 若适配器在传输时检测到其它适配器也在传输，则停止传输，发送拥塞信号
​ 中止传输后，适配器进入指数回退阶段，在经历第m次碰撞后，适配器随机从{0,1,2,…,2m-1}中选择K值。适配器在等待 K·512比特时间后，返回第2步

拥塞信号: 用来确保所有传输者都能检测到碰撞而传输的信号；48比特长
比特时间: 传输1比特所需时间。在10Mbps的以太网中，当K=1023时，等待时间大约为50ms

指数回退算法
目的: 适配器重传时试图估计正确的负载
重载: 随机等待的时间可能会更长
第一次碰撞: 从 {0,1}中选择K; 延迟是 K· 512 比特传输时间
第二次碰撞后: 从 {0,1,2, 3}中选择K
第十次碰撞后: 从 {0,1,2,3,4,…,1023}中选择K

重要特性
使用 CSMA/CD 协议的以太网不能进行全双工通信而只能进行双向交替通信（半双工通信）。
每个站在发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。
这种发送的不确定性使整个以太网的平均通信量远小于以太网的最高数据率。

争用期长度
以太网取 51.2 μs 为争用期的长度。
对于 10 Mb/s 以太网，在争用期内可发送512 bit，即 64 字节。
以太网在发送数据时，若前 64 字节没有发生碰撞，则后续的数据就不会发生碰撞。
最短有效帧长
如果发生碰撞，就一定是在发送的前 64 字节之内。
由于一检测到碰撞就立即中止发送，这时已经发送出去的数据一定小于 64 字节。
以太网规定了最短有效帧长为 64 字节，凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。

• 以太网交换机互联
  交换机（Swtich）是一种存储—转发设备，在MAC层实现LAN互连

• 交换机的工作原理

​ 不断监听各接口是否有信号
​ 收到无差错的帧则缓存，反之将差错帧丢弃
​ 若所收帧的目的MAC地址属另一网段，则通过站表决定向何接口转发
​ 交换机不转发同一网段内通信的帧
​ 交换机不修改所转发的帧的源地址

交换机的优势
过滤通信量
扩大了局域网的物理范围
提高了可靠性
可互连不同物理层、不同MAC子层和不同速率的局域网

交换机的缺点
由于要接收和转发，增加了时延
MAC子层没有流量控制功能，网络负荷重时，交换机缓存空间可能发生溢出，产生帧丢失现象
出现广播风暴。交换机只适合用户少于几百个和通信量不太大的局域网，否则有时会因传播过多广播信息而产生网络拥塞

交换机和集线器的区别
集线器只是将网络的覆盖距离简单的延长，而且距离有限，具体实现在物理层；交换机不仅具有将LAN的覆盖距离延长的作用，而且理论上可做到无限延长，具体实现在MAC层。
集线器仅具有简单的信号整形和放大的功能；交换机则属于一种智能互连设备，它主要提供信号的存储/转发、数据过滤、路由选择等能力。
集线器仅是一种硬设备，而交换机既包括硬件又包括软件。

交换机的透明性:指局域网上的每个站并不知道所发送的帧将经过哪几个交换机，即交换机对各站来说是看不见的

交换机选路原理
① 从接口x收到帧，有差错则丢弃，否则在站表中查找目的站MAC地址；
② 找到有，则取出相应的接口d，转③，否则转⑤；
③ 如果所给MAC地址的接口d=x，则丢弃此帧（不需要转发），否则从接口d转发此帧；
④ 转到⑥；
⑤ 向除x以外的所有接口转发此帧（可保证找到目的站）
⑥ 如源站不在站表中，则将源站MAC地址写入站表，登记该帧进入交换机的接口号和时间，设置计时器，然后转⑧。否则转⑦；
⑦ 更新计时器（由于网络拓扑经常变化，因此，超时记录要删除，以反映最新状态）；
⑧ 等待新的数据帧。转①

• 以太网交换机 vs 路由器
  两者都是存储转发设备
  路由器：网络层设备 (检查网络层头部)
  交换机是链路层设备
  路由器维护路由表，实现路由算法
  交换机维护交换表，实现MAC地址过滤、学习算法

• [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oPZ65hM0-1606530179692)(D:\素材\image-20201125173908592.png)]

• 虚拟局域网 VLAN

局域网交换机是组建虚拟局域网的核心设备。
组成逻辑工作组的各结点不受物理位置的限制，换言之同一逻辑工作组的成员不一定要连接在同一个物理网段上。
当一个结点从一个逻辑工作组转移到另一个逻辑工作组时，只需要通过软件设定，而不需要改变它在网络中的物理位置。

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

略，见书

第七章 无线网络和移动网络

7.1 概述

无线特性：基于无线链路的通信

移动特性：移动用户的网络接入点是变化的

无线网络的元素:

​ 无线主机：便携机、PDA、IP电话等，本身固定或移动。

​ 无线链路：用于连接无线主机和基站，有与链路访问匹配的多址访问协议。

​ 基站：连接无线网络，向主机发送接收分组在无线网络和主机间起链路层中继作用（如蜂窝塔、802.11接入点）

无线局域网可分为有固定基础设施和自组网络(ad hoc网络)

基础设施模式：预先建立起来的、能够覆盖一定地理范围的一批固定基站。移动主机位于某个基站的无线通信覆盖范围内，通过基站接入有线网络; 切换:移动主机的移动可能会改变与之相关联的基站。

Ad hoc网络：无基站，节点向覆盖范围内其他节点传送数据，相互通信组成临时网络，在这些节点内部进行选路和地址分配。

几种标准无线网络标准的链路特性：

7.2 无线链路和网络特征

无线链路的特征

​ 递减的信号强度、来自其他源的干扰、多径传播

由于这些特征，其比特差错比有线链路更常见，无线链路采用CRC进行帧校验并采用ARQ协议重传。

信号差错指标

​ SNR——信噪比

​ BER——比特差错率

对于给定的调制方案，SNR越高，BER越低

对于给定的SNR，具有较高比特传输率的调制技术将具有较高的BER

存在隐藏终端问题：存在障碍物、信号衰减

码分多址访问(CDMA):每一个站的码片序列各不相同、相互正交

7.3 WiFi：802.11无线LAN

• 802.11协议簇概述

都是使用CSMA/CA 协议实现多路访问
都可以用于有固定基础设施模式和自组网络模式

802.11b
工作在不需要许可证的2.4~2.485 GHz的无线频谱上;
最高数据速率 11 Mbps
采用直接序列扩频(DSSS):所有主机使用相同的码片序列

802.11a
频率范围:5.1~5.8 GHz
最高数据速率: 54 Mbps

802.11g
2.4~2.485 GHz范围
最高数据速率 54 Mbps

802.11n：多天线
2.4~2.485、5.1-5.8GHz范围
单流最高数据速率 150Mbps
多流最高数据速率 600Mbps

802.11ac
5.1~5.8GHz范围
单流最高数据速率 433Mbps@80MHz信道带宽、866Mbps@160MHz信道带宽
多流最高数据速率1.73Gbps、3.47Gbps

第六代Wi-Fi：802.11ax
单流速率提升至1.2Gbps，8x8模式下提供高达9.6Gbps的传输速率
支持较窄的子载波间隔以及增加的符号持续时间，更有利于确保信号的健壮性，令Wi-Fi覆盖至更远范围
引入曾在4G LTE上使用的正交频分多址（OFDMA）技术，加之同时支持2.4GHz和5GHz频段，能创造出更多可用的数据通道，解决无线网络拥堵问题
通过在多AP多用户并发场景中引入很多LTE领域的组网特性，让信号的抗干扰性大幅提升

802.11体系结构
无线终端通过基站（AP）进行通信
基本服务集BSS包括
无线终端
基站AP
Ad hoc模式下只有终端

802.11b的信道划分
2.4GHz—2.485GHz，共85MHz
划分为11个部分重叠的信道集
两个信道仅当中间相隔4个及以上的信道时，无重叠
1、6、11三个信道不重叠，可同时工作
802.11b中主机关联AP的过程
每个AP周期性发送信标帧，包括AP的SSID和MAC
主机对11个信道进行扫描，获取所有可用的AP的信标帧
主机选择其中一个AP发送关联请求帧，AP回以关联响应帧，主机加入该AP所属子网
主机向关联AP发送DHCP发现报文，获取IP地址
可能需要身份鉴别

（无线主机也可以执行主动扫描，自主机广播探测请求帧，AP发送探测相应，主机再进行关联请求……）

802.11的MAC协议——CSMA/CA

​ 使用碰撞避免而非碰撞检测:由于隐蔽终端和衰减的问题无法检测到所有的碰撞；碰撞检测要求站点同时有发送和接收的能力，802.11适配器上接收信号强度可能远小于发送信号的强度无法被检测，实现硬件代价大。

发送方的工作流程
如果侦听到信道闲置了DIFS(分布式帧间间隔) 秒，则传输整个帧 (无冲突检测)
如果侦听到信道忙，则选择一个随机避退值作为定时器的定时时间，并在侦听信道闲置时递减该值。
定时时间一到且信道空闲就发送整个数据帧
如果收到确认，且站点要继续发送数据帧，则执行第2步；如果没有收到确认（ ACK）,则在更大范围内选取随机值, 重复第2步。若干次重传后仍未收到确认时发送方丢弃该帧。

接收方工作流程
如果帧收到则OK，等待SIFS(短帧间间隔) 秒后返回ACK (ACK是必须的因为隐蔽站问题)

• 冲突避免

​ 思路: 允许发送方“预约”信道而非随机访问 :避免长的数据帧冲突
​ 发送方在发送数据帧之前首先使用 CSMA协议发送一个短的请求发送RTS( request-to-send)帧给AP：
​ RTS也可能仍会相互冲突 (但时间很短)
​ AP广播一个允许发送 CTS（clear-to-send）帧响应 RTS
​ RTS 被所有节点侦听到
​ 发送方发送数据帧
​ 其他站点推迟发送

使用短的预约帧可以完全避免数据帧发生冲突。

RTS/CTS交换引入了时延以及消耗信道资源，因此仅仅用于为长数据帧预约信道。

• 802.11MAC帧格式

​ AP接收无线主机H1后将802.11帧转换成以太网帧时，源地址字段是H1的MAC地址(地址2)，目的地址字段是与AP相连的路由器R1的MAC地址(地址3)。

序号：使接收方区分新传输和以前帧的重传。

帧控制：扩展为协议版本、类型、子类、to/from、WEP等，其中类型和子类型字段用于区分RTS、CTS、ACK、数据帧，to/from用于定义不同地址字段的含义。

• 802.11同一子网内的移动性

​ 主机与AP：一个无线主机H1从BSS1移动到BSS2，H1检测到AP1的信号逐渐减弱并检测一个更强的信号，收到AP2的信号，并与AP1解除关联，并与AP2关联起来，同时保持其IP地址和维持正在进行的TCP会话。

​ 交换机：一种解决办法是，新关联形成后AP2以H1的源地址发送以太网广播帧，让交换机更新ARP表。

802.11速率自适应

​ 基站和移动终端之间的速度会随着移动终端的移动和SNR的变化而智能的调整

  1. 当终端向远离基站的方向移动时，SNR 减小, BER 增大2. 当 BER 增大到一定程度时，将速率切换到一个较低的水平来保障较低的 BER

• 功率管理

​ node-to-AP: “我将保持睡眠状态直到下一个信标帧”：通过将802.11帧守首部的功率管理比特置为1，节点向接入点指示它将进入睡眠模式
​ AP 知道不应当向这个节点发送任何帧
​ AP缓存所有需要发送给该节点的帧，待以后再传输
​ 节点在下一个信标帧前唤醒
​ 信标帧: 包含了帧被缓存在AP中的节点的列表
​ 如果有帧，待发送节点会保持活动状态，向AP发送探询报文，请求这些缓存帧，再转入睡眠状态
​ 如果没有帧，重新进入睡眠状态直到下一个信标帧前

• 802.15——无线个人区域网(蓝牙与ZigBee)

​ 半径小于 10 米
​ 取代那些电缆 (鼠标, 键盘, 耳机)
​ 是自组网: 无固定基础设施
​ 主/从式:
​ 从设备 请求允许向主设备发送；
​ 主设备同意请求。
​ 802.15: 从蓝牙技术规范演变而来
​ 2.4-2.5 GHz 无线电波段
​ 最大数据速率 721 kbps

撞避免而非碰撞检测:由于隐蔽终端和衰减的问题无法检测到所有的碰撞；碰撞检测要求站点同时有发送和接收的能力，802.11适配器上接收信号强度可能远小于发送信号的强度无法被检测，实现硬件代价大。

发送方的工作流程
如果侦听到信道闲置了DIFS(分布式帧间间隔) 秒，则传输整个帧 (无冲突检测)
如果侦听到信道忙，则选择一个随机避退值作为定时器的定时时间，并在侦听信道闲置时递减该值。
定时时间一到且信道空闲就发送整个数据帧
如果收到确认，且站点要继续发送数据帧，则执行第2步；如果没有收到确认（ ACK）,则在更大范围内选取随机值, 重复第2步。若干次重传后仍未收到确认时发送方丢弃该帧。

接收方工作流程
如果帧收到则OK，等待SIFS(短帧间间隔) 秒后返回ACK (ACK是必须的因为隐蔽站问题)

• 冲突避免

​ 思路: 允许发送方“预约”信道而非随机访问 :避免长的数据帧冲突
​ 发送方在发送数据帧之前首先使用 CSMA协议发送一个短的请求发送RTS( request-to-send)帧给AP：
​ RTS也可能仍会相互冲突 (但时间很短)
​ AP广播一个允许发送 CTS（clear-to-send）帧响应 RTS
​ RTS 被所有节点侦听到
​ 发送方发送数据帧
​ 其他站点推迟发送

使用短的预约帧可以完全避免数据帧发生冲突。

RTS/CTS交换引入了时延以及消耗信道资源，因此仅仅用于为长数据帧预约信道。

• 802.11MAC帧格式

[外链图片转存中…(img-VkDFW3GC-1606530179693)]

​ AP接收无线主机H1后将802.11帧转换成以太网帧时，源地址字段是H1的MAC地址(地址2)，目的地址字段是与AP相连的路由器R1的MAC地址(地址3)。

序号：使接收方区分新传输和以前帧的重传。

帧控制：扩展为协议版本、类型、子类、to/from、WEP等，其中类型和子类型字段用于区分RTS、CTS、ACK、数据帧，to/from用于定义不同地址字段的含义。

• 802.11同一子网内的移动性

​ 主机与AP：一个无线主机H1从BSS1移动到BSS2，H1检测到AP1的信号逐渐减弱并检测一个更强的信号，收到AP2的信号，并与AP1解除关联，并与AP2关联起来，同时保持其IP地址和维持正在进行的TCP会话。

​ 交换机：一种解决办法是，新关联形成后AP2以H1的源地址发送以太网广播帧，让交换机更新ARP表。

802.11速率自适应

​ 基站和移动终端之间的速度会随着移动终端的移动和SNR的变化而智能的调整

1. 当终端向远离基站的方向移动时，SNR 减小, BER 增大
   2. 当 BER 增大到一定程度时，将速率切换到一个较低的水平来保障较低的 BER

• 功率管理

​ node-to-AP: “我将保持睡眠状态直到下一个信标帧”：通过将802.11帧守首部的功率管理比特置为1，节点向接入点指示它将进入睡眠模式
​ AP 知道不应当向这个节点发送任何帧
​ AP缓存所有需要发送给该节点的帧，待以后再传输
​ 节点在下一个信标帧前唤醒
​ 信标帧: 包含了帧被缓存在AP中的节点的列表
​ 如果有帧，待发送节点会保持活动状态，向AP发送探询报文，请求这些缓存帧，再转入睡眠状态
​ 如果没有帧，重新进入睡眠状态直到下一个信标帧前

• 802.15——无线个人区域网(蓝牙与ZigBee)

​ 半径小于 10 米
​ 取代那些电缆 (鼠标, 键盘, 耳机)
​ 是自组网: 无固定基础设施
​ 主/从式:
​ 从设备 请求允许向主设备发送；
​ 主设备同意请求。
​ 802.15: 从蓝牙技术规范演变而来
​ 2.4-2.5 GHz 无线电波段
​ 最大数据速率 721 kbps