计算机网络

计算机网络

本课程的考试题面为英文，可以用中英文作答，因此对计网中各类概念的英文理解还是非常必要的

计算机网络的分层结构：沙漏结构

网络层不可靠传递：尽力而为，可能丢包

第一章：引论 Introduction

重要概念

• Protocol：协议
• Service：服务
• Interface：接口
• Entity：实体，表示任何可发送或接收信息的硬件或软件进程
• Peer：对等实体
• Addressing：寻址
• Error control：差错控制
• Sequencing：按序
• Flow control：流量控制
• Reliable：可靠的（通常意味着有确认）
• 资源子网：Resource subnet
• 通信子网：Communication subnet

计算机网络与互联网

计算机网络：通过通信技术连接的独立计算机的互连集合

计算机网络提供的服务：数据通信（最基础）、资源共享

从“螺栓螺母”视角看互联网：

1. 设备：主机、终端
2. 连接：光纤、铜、无线电、卫星
3. 路由器：通过网络转发数据包
4. 协议：控制收发消息的规定

从服务视角看互联网：

1. 使用通信设施进行通讯的分布式应用
2. 通信服务分为无连接与面向连接的服务

网络边缘与网络核心

互联网结构：

• 网络边缘：应用程序、主机、资源
• 网络核心：路由器、通讯设备等网络交换节点
• 接入网和物理媒体

网络边缘：

• 端系统（主机）：运行应用程序

• 端对端通信

  • 客户/服务器模式（C/S）（Client / Server ）：客户端向服务器发送请求，服务器为客户端提供服务

    

  • 对等模式（P2P）：无固定的客户端或服务器

    

网络核心：

• 结构：网状结构的互联路由器

• 功能：支持终端通讯

• 信息传输方式：线路交换(circuit switch)、报文交换(message switch)、分组交换(packet switch)

  

1. 线路交换：

   • 端到端的资源被分配给从源端到目标端的呼叫

   • 优点：性能好

   • 缺点：资源独占，不共享；不适合计算机之间的通信（呼叫方式建立连接时间长，计算机之间的通信由突发性，如果使用电路交换，则浪费的片多）

   • 电话网络中的线路交换：直接建立线路连接、交换机

   • 计算机网络中的线路交换：

     • 三阶段：建立线路连接、数据传输、线路释放

     

   • 共享连接：将连接的片段分给呼叫，以减少叫后不用带来的浪费

     • 频分FDM
     • 时分TDM
     • 空分

     

2. 分组交换：将端到端的数据流分组，每组按固定格式传输

   

   • 分组是定长的，且必须加上报头（Header）

     • 报头（Header）中包含控制信息，包括：源地址与目的地址、序列号、协议版本、分组总长等

   • 传输：每个分组在网络中按照报头（Header）中路线传输，每次传一跳（hop，即一个路由器）

   • 存储转发网络（store and forward）：路由器接收到完整分组后，先存储，再转发

     • 时延：

       传输时延（Transmission delay）：一个站点从开始发送数据到数据发送完毕所需要的全部时间

       传播时延（Propagation delay）：发送端开始发送数据到接收端收到数据所需要的全部时间

     • 分类：

       数据包网络：每个分组的目的地址决定下一跳（hop），通信前无需建立连接，路由器根据当前分组的目的地址路由，类似问路，动态可变

       虚电路网络：每个分组自带标签（虚电路标识 virtual circuit），建立呼叫时确定路径，不可改变，由路由器维持呼叫状态信息，静态不可变

     • 流水线技术：每个环节并行工作

       

   • 优点：分组传输时采用链路最大带宽传输

   • 统计多路复用技术：在一条线路上同时传递多个包时，包间没有固定顺序

     

3. 线路交换与分组交换的对比

   	优点	缺点	适用场景
   线路交换	带宽有保证，通信性能可靠简单抽象，无需担心数据包无序或丢失转发简单，开销少	带宽浪费连接阻塞，资源不足无法服务网络节点需存储所有连接的信息存在连接延迟
   分组交换	可靠性优势，错误不传递统计多路复用提高效率可部署性优势，更容易建立网络	存在阻塞问题，路由器结构更复杂，难以提供良好的网络服务难以保证可靠数据传输	突发式数据传输

网络接入与物理媒体

端系统与边缘路由器的连接方式

• 住宅接入网络：

  • 点对点传输：调制解调器拨号（不能同时启动多个设备）、非对称数字用户线路ADSL（上行下行速度不同）
  • 电缆调制解调器：混合光纤同轴电缆HFC
  • 光纤到户FTTP：结构：光线分配中心FDH - 光线分配终端FDT - 光纤线路中断OLT，FTTP有单位用户的最高理论容量：1G bps

• 单位接入网络：有线局域网，仍为电缆连接

• 无线接入网络：无线局域网

物理媒体

• 分类：引导型媒体（有线，如同轴电缆、光纤、双绞线）、非引导型媒体（无线，如无线电）

  • 双绞线：两根绝缘铜线拧合

    • 通用标准：T568A、T568B

      

    • 连接方式：直通线（对应位相连，计算机-交换机/设备）、交叉线（12-36，45-78，设备-设备）

      

  • 同轴电缆：两根同轴铜导线

  • 光缆：高速、低误码率

  • 无线电：用开放空间的电磁波传输数据，双向

    • 地面微波：直线传播，中继站转发
    • 局域网LAN
    • 广域wide-area，eg：蜂窝
    • 卫星：适合广播通信

• 对比：

  

• 理论极限容量：香农定理：$C=B\log_2(1+\frac{S}{N})$，其中$\frac{S}{N}$为信噪比，$1dB=10\log_{10}\frac{S}{N}$

  传播速度极限：光纤理论最高速度为$0.66c$

类型与拓扑结构

按地理分类：局域网LAN、城域网MAN、广域网WAN

• 局域网：使用广播技术，拓扑结构简单：总线、环形、星形、树形拓扑结构

• 城域网：使用广播技术，可拓展性好：分布式队列，双总线结构DQDB（Distributed Queue, Dual Bus）

  

• 广域网：网状拓扑结构，包括两个子网络：资源子网、通信子网

  • 资源子网：负责信息加工，包括计算机、终端、程序等
  • 通信子网：负责信息传递与分发，包括路由与交换机

计算机网络拓扑结构：网络中各种组件的排列方式

• 总线拓扑：所有网络设备连接到公共电缆，一个主机故障则整个网络故障
• 星形拓扑：所有设备连接到交换机，一条电缆故障不会影响整个网络

因特网拓扑结构：网络的网络

• 特点：分层，每层由运营商ISP构成，层内彼此平等，低层ISP可视为高层ISP的用户

网络性能

1. 连接的属性：

   • 延迟Latency：数据在连接上传输的时间

   • 带宽Bandwidth：单位时间传送数据量

   • 带宽延迟积BDP Bandwidth-delay product：单位时间线路上的总比特数$BDP=delay \times bandwidth$

   • 利用率 Utilization：单位时间到达比特数Arrival除以传输比特数Bandwidth，$\rho=\frac{A}{B}$

2. 延迟：数据包到达链路的速度超过输出链路速度

   丢包：路由器中自由缓冲区满时到达的数据包丢掉

3. 数据包延迟 = 节点处理时间Nodal processing + 排队时间Queuing + 传输时间Transmission + 传播时间Propagation

   

4. 往返时间RTT：从发送方发送完数据，到发送方收到来自接收方的确认总共经历的时间

   

计算机网络体系结构

协议 Protocol

议**：规定同层之间如何通信，包括语法Syntax（协议结构）和语义semantics（表示信息）

• 特点：分层结构

• 优点：模块化、抽象方法、可重用

• 层封装：

为对等实体建立，是水平的

三要素

• 语法：数据与控制信息的结构或格式。
• 语义：需要发出何种控制信息，完成何种动作以及做出何种响应。
• 同步：事件实现顺序的详细说明

协议层次 Protocol Hierarchies

• 把整个网络的功能划分为若干独立的层次。
• 每层完成独立的功能。
• 每层功能的实现需借助下层的服务来完成，同时向上层提供更高级的服务。
• 通信只在相邻层之间进行，不允许跨层调用。

服务 Service

由低层提供给高层的一组通信能力和操作，通过服务原语定义

类型：面向连接服务（eg：线路交换、虚电路分组交换）、无连接服务（eg：数据包分组交换）

接口：进行相邻层间的数据的解析与封装

下层为上层提供的通信支持，是垂直的

可分为

• 面向连接的服务 Connection-oriented
• 无连接服务 Connectionless
• 可靠服务

服务vs协议：

• 服务：低层实体向上层实体提供它们之间的通信的能力，是通过原语(primitive)来操作的，垂直关系

  协议：对等层实体(peer entity)之间在相互通信的过程中，需要遵循的规则的集合，水平关系

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

接口

• 数据单元
  • IDU：接口数据单元
  • SDU：服务数据单元
  • ICI：接口控制信息
  • PDU：协议数据单元
• 服务访问点 SAP

ISO/OSI

自底向上

• 物理层 Physical Layer：描述原始比特位的传输
• 数据链路层 Data link Layer：进行差错控制，物理寻址（MAC子层），传输帧（frame）
• 网络层Network Layer：在子网间进行路由，传输数据报
• 传输层Transport Layer：提供端到端（end-to-end）服务
• 会话层Session Layer：提供对话控制、令牌管理、同步
• 表示层Presentation Layer：关心信息的语法和语义和表示方式
• 应用层Application Layer

TCP/IP

IP（Internet Protocol）协议提供了主机和主机间的通信，为了完成不同主机的通信，我们需要某种方式来唯一标识一台主机，这个标识，就是著名的 IP 地址。通过IP地址，IP 协议就能够帮我们把一个数据包发送给对方。

TCP 的全称是 Transmission Control Protocol，TCP 协议在 IP 协议提供的主机间通信功能的基础上，完成这两个主机上进程对进程的通信。

第二章：物理层 The Physical Layer

关键词记忆

基本特性

• 机械特性mechanical
• 电气特性electrical
• 功能特性functional
• 过程特性timing

重要概念

• 信号 signal

  • 模拟信号 analogous：参数取值连续
  • 数字信号 digital：参数取值离散

• 码元

• 信道 channel

• 带宽bandwidth：体现为传输信道的最高频率和最低频率之差，单位是赫兹（Hz）

• 波特率 baud rate：线路上单位时间内传送的波形个数

• 比特率 bit rate：单位时间内传送比特的位数（bps）

• 工作方式

  • 半双工 Half-duplex link
  • 全双工 Full-duplex link
  • 单工 Simplex link

• 奈奎斯特（Nyquist）准则

  无噪声情况下，理想低通信道的最高码元传输速率 = 2H Baud = 2H log2V

  其中H是理想低通信道的带宽，V是码元的离散信号数

• 香农（Shannon）公式

  最大数据传输率 = H log2(1 + S/N) bit/s

  其中 S/N为信噪比

• 编码encode：将数字数据转换成数字信号的过程

  • 归零制RZ：正脉冲代表1，负脉冲代表0。
  • 不归零制NRZ：正电平代表1，负电平代表0。
  • 不归零反相制NRZI：不是用电平本身表示比特，而是用是否发生电平翻转表示比特；本笔记按 1 翻转、0 不变记。
  • 曼彻斯特编码Manchester：位周期中心的上跳变代表0，位周期中心的下跳变代表1。
  • 差分曼彻斯特编码：一位的开始边界有跳变代表0，位边界没有跳变代表1，在位周期中心处始终都有跳变。

  需要注意：

  • 曼彻斯特编码产生信号的频率比不归零制高。
  • 从自同步能力来看，归零制和不归零制没有自同步能力，NRZI 长时间无翻转时也不利于同步，而曼彻斯特编码和差分曼彻斯特编码具有自同步能力

• 解码decode：将编码后的数字信号还原为数字数据的过程

• 调制modulate：将数字数据转换成模拟信号的过程

  • 移幅键控法（ASK）amplitude

  • 移频键控法（FSK）frequency

  • 移相键控法（PSK）phase

  • QAM：三种方法的结合

• 解调demodulate：将调制后的模拟信号还原为数字数据的过程。

• 基带信号 Baseband：来自信源的数字信号。基带传输

• 带通信号 Passband：基带信号经过载波调制后的模拟信号。通带传输

信道多路复用 Multiplexing：使用一个信道传送多个数据流

• 频分复用FDM
• 时分复用TDM
• 波分复用WDM
• 码分复用CDM

物理层设备

• 中继器Repeater
• 集线器Hub

物理层介绍

功能：在传输线路上进行透明的、可靠的比特流收发

物理特性：机械特性mechanical、电气特性electrical、功能特性functional、过程特性timing

数据通信基础

两种转换：信源编码、信道编码

物理层传输的问题：衰减attenuation、失真distortion、噪声noise

带宽B：信道允许通过的频率范围、每秒传输的比特数

波特率/码元速率/信号率baud rate：信号每秒变化的次数，单位$Baud/s$

比特率bit rate：每秒传输的比特数，单位$bps$

$S=B*\log _2v=\frac{1}{T}*\log_2v$，S为比特率，B为波特率，T为频率周期，v为码元数

• 奈奎斯特准则：对无噪声干扰的低通信道，带宽$H$Hz，进行$2H$采样时可以重建信号

$最高波特率=2H$，$最高比特率=2H\log_2v$

• 香农公式：对有噪声信道，$最高比特率=H\log_2(1+\frac{S}{N})$

传输介质

部分物理媒介

• 双绞线 Twisted pair wire

  • 屏蔽双绞线 STP
  • 非屏蔽双绞线 UTP

• 同轴电缆 Coaxial Cable

• 光纤 Fiber Optic： $c=\lambda*f$

• 无线传输：

  • 微波信号：视线传输，需中继站，受自然环境影响大

  • 卫星通信

调制与数据编码

信号类型：模拟信号（调制-解调）、数字信号（编码-解码）

数字数据传输：

• 基带数据传输base-band：不改变数字信号直接传输，要求低通信道，0~HHz
• 通带数据传输pass-band：高频载波信号传输数据

数字数据-数字信号编码：

• 传输方式：

  • 不归零编码 NRZ-L： 0低电平，1高电平

  • 不归零翻转编码 NRZI： 0不变，1翻转

  • 曼彻斯特编码： 中心跳变，周期内0由低到高，1由高到低

  • 差分曼彻斯特编码：中心跳变，0边界翻转，1边界不翻转

  • 块编码 mB/nB ：将mB块组映射为nB块组，一般与前面的编码方式联合使用，eg： 4B/5B encoding -> NRZ-I encoding -> transmit -> NRZ-I decoding -> 4B/5B decoding

    

• 对比：曼彻斯特编码产生信号的频率高于不归零制，曼彻斯特编码有自同步能力（中间位用于时钟同步）

NRZ、NRZI、曼彻斯特编码的关系：

记忆：

• NRZ-L 看电平：高/低电平本身代表比特。
• NRZI 看变化：有没有翻转代表比特。
• Manchester 看中间跳变：每个 bit 中间一定跳，用跳变方向代表比特。
• 差分曼彻斯特 = NRZI 的“看是否翻转”思想 + 曼彻斯特的“中间必跳变”同步能力。

带通传输：

• 用特定频率做载波信号传输，需要调制，传输数字信号

• 数字信号调制：

  • 调幅 ASK、调频 FSK、调相 PSK

    

  • $M_{ary}$调制，增加码元信号值：$M_{ary}ASK$、$M_{ary}PSK$、$M_{ary}FSK$，$M=2^k$

    

  • 正交幅度调制 QAM

模数转换：

• 数字信号抗噪声效果更好，易恢复、校正、放大，因此一般将模拟信号转化成数字信号传输
• 脉冲编码调制 PCM ：采样-量化-编码
  • 采样：对原始模拟信号采样，采样频率$f_s \geqslant 2f$
  • 量化：均匀量化
  • 编码：对每个量化值分配编码，码元比特数$n_b=\log_2L$
  • $Bit\space rate = n_b \times f_s$
• 增量传输 Delta Modulation ：DPCM

数据传输：

• 并行：所有比特位同时传出
• 串行：异步（按字节传输，每个字节需要start/stop位）、同步（按帧传输，每个帧需要start/stop位）、等时（固定间隔，不需要start/stop位）

多路复用

分类：

• 模拟信号：
  • FDM：频分多路复用，多个信号在不相交的频段上传输
  • WDM：波分多路复用
• 数字信号：
  • TDM：时分多路复用，每个时间框分成多个时间槽，分配给每个通道使用
    • 同步时分多路复用 Synchronous ：每个通道划分固定时间槽，每个时间框同时传输
    • 统计时分多路复用 Statistical ：根据需求动态分配时间槽
    • 异步时分多路复用 Asynchronous
  • CDMA：码分多路复用，每个bit位对应一个k位码片，码片互相正交

扩频技术：

• 跳频扩频 FHSS ：一个码元一个传输频率
• 直接序列扩频 DSSS ：将数字信号与更高数据速率的位序列（伪随机数 PN ）组合（称为削片码）来传播信号
• 跳时扩频 THSS
• 宽带线性调频 CSS

第三章：数据链路层 Data Link Layer

• 链路
• 数据链路：使用了复用技术时，一条链路上可以有多个数据链路

功能

• 为网络层提供服务

  在两台物理连接（相邻）的机器之间传送数据链路帧，在不可靠的物理层连接上实现可靠传输

  • 提供无确认的无连接服务 Unacknowledged connectionless service
  • 提供有确认的无连接服务 Acknowledged connectionless service
  • 提供有确认的面向连接服务 Acknowledged connection-oriented service

• 链路管理：链路层连接建立、维持、释放的过程

  提供物理地址寻址 Addressing

• 组帧 Framing

  包括帧定界、帧同步、透明传输

• 流量控制 Flow Control

  发送方能力大于接收方能力，发送方需要控制速度

• 差错控制 Error Control

  通常采用循环冗余校验CRC发现位错，用自动重传请求ARQ重传出错帧

• 连接类型：点对点链路、广播链路

• 向网络层提供的服务类型：

  • 不确认的无连接的服务：不建立连接，源计算机发送给目的计算机，目的计算机不确认，传输失败不恢复
  • 确认的无连接的服务：不建立连接，需确认，失败重传
  • 确认的面向连接的服务：建立连接，传输的每个帧都编号，需确认

帧

帧 Frame：链路层的传输单元

帧同步 Frame synchronization：从二进制比特流中区分出帧的开始与终止

• 字符计数：每一帧的开头指出字符数
• 用字节或字符填充标记字节：特殊ASCII码字符序列标记帧的开始和结束，透明传输，eg：ESC
• 带位填充的起始和结束标志：使用特定比特序列标记帧的开始和结束，eg：01111110
• 物理层编码冲突
• 帧间插入时间间隔

集中成帧的方法

• 字符计数法Character Count

  在帧首指出帧的长度，但如果计数字段出错则之后会一直出错

  

• 字符填充的首尾定界符法 Flag byte with byte/Char stuffing

  定界符表示一帧的开始与结束，需要转义字符ESC

  

• 零比特填充的首尾标志法 Starting and ending flags with bit stuffing

  用01111110表示一个帧的开始与结束，当信息位存在连续5个1时，自动在其后插入0

  

差错控制 Error Detection and Correction

差错类型

比特错误、传输错误（帧损坏、帧丢失）

比特错误纠正方法：

• 纠错码：向前纠错FEC(forward error correction)
• 检错码 + 纠错技术

纠错码 error-correcting codes

能够检测与纠正错误，依靠发送端的冗余信息

• 海明码（汉明码 Hamming Code）：
  • m位信息码，r位纠错码，码字n=m+r位，海明码有1位纠错能力条件：$m+r+1 \leq 2^r$
  • 海明距离：两个二进制数不同位的个数
  • d个错，海明码检错条件：海明距离至少d+1，海明码纠错条件：海明距离至少2d+1
• 二进制卷积码 binary convolution code

检错码 error-detecting codes

• 奇偶校验 Parity check ：奇数位错误可检出，偶数位错误不可检出，无校验能力

  • 二维奇偶校验：1位纠错能力，2/3位检错能力，4及以上无法检错

• 循环冗余校验 CRC Cyclic Redundancy Check

  • 基本原理：在p位二进制数据序列后面附加r位二进制检验码，检验码由原始数据与生成多项式做除法生成，可检测传输错误，生成多项式是二进制数，由发送方和接收方约定

  • 接收方用收到的二进制数除生成多项式，等于0则没有错误

    

    计算方法：

    通过生成多项式的系数得到生成码，冗余码的个数是（ 生成码个数-1）

• 校验和 Checksum

错误控制

• 纠错码 FEC ：不保证可靠传输
• 错误检测+自动重传请求 Error Detection + ARQ Automatic Repeat Request ：
  • ED：二维奇偶校验、循环冗余校验、校验和、确认、序列
  • ARQ作用：无差错、无冗余、无损失、顺序不变 -> 将数据链路由不可靠转化为可靠
    • 类型：Stop-and-Wait ARQ、Go-Back-N ARQ、Selective Repeat ARQ

流量控制

• 停止等待协议：发送方收到接收方确认后传输下一帧
• 滑动窗口协议：发送方一次发W帧

• 帧出错：

  • 二维奇偶校验，checksum，CRC
  • 确认机制 Ackonwlegement
  • 序列号 Sequence

• 帧丢失：超时

• 修正：重传

  ARQ 自动重传请求

停等协议 Stop-and-Wait Protocols

利用率utilization

带宽延迟乘积 bandwidth-delay product

协议定义：发送一帧之后需等待确认，之后发下一帧。发送窗口$W_T$=接受窗口$W_R$=1

只用一个bits来给帧编号，$W_T$+$W_R$ <= $2^n$

正常情况：

超时重传：

乌托邦单工协议：

• 假设：数据单向传递，信道无差错，无限缓存空间，发送方接收方始终在线，处理时间可以忽略
• 特点：无Ack、Seq，无差错控制、流量控制，唯一事件是 frame_arrival

无差错信道上的单工停止等待协议:

• 假设：数据单向传递，信道无差错，接收方缓存有限，发送方需确认Ack，超时重传
• 特点：有Ack、无Seq，帧损坏或帧丢失接收方不反馈Ack，重传
• 过程：发送方发送帧 -> 接收方收到并发送Ack -> 发送发收到Ack后发送下一帧

有噪声信道上的单工停止等待协议：

• 假设：数据单向传递，信道不可靠，接收方缓存有限，需确认Ack、Seq，超时重传
• 特点：有Ack、Seq，Seq只有0/1，帧损坏、帧丢失、乱序帧需重传
• 过程：发送方发送帧 -> 接收方收到并发送Ack+Seq -> 发送发收到Ack+Seq后发送下一帧

链路利用率$U=\frac{t_f}{t_T}=\frac{T_{trans}}{2\times T_{prop}+T_{trans}}=\frac{1}{2\times \alpha+1}, \alpha=\frac{t_{prop}}{t_{trans}}$，忽略处理时间、接收方Ack传输时间

提升效率：滑动窗口协议，流水线

滑动窗口协议 Sliding Window Protocol

允许多帧同时发送，帧需要编号

发送窗口 sending window

接收窗口 Receiving Window

1. 内容：允许一次传输多帧，发送方与接收方各维护一个等大缓冲区（滑动窗口），帧有编号

   • 发送窗口维护允许发送的帧的范围，包括发送指针（右）和接收确认指针（左），大小不固定

   • 接收窗口维护允许接收的帧的范围，包括接收指针（右）和发送确认指针（左），大小固定

2. 累计确认：Ack n 表示已累计收到n帧，即一次Ack可确认多帧

3. 全双工通信：两个独立信道，可同时在两个方向传输

4. 滑动窗口协议分类：

   • 1 bit sliding window protocol ARQ：发送窗口大小为1，接收窗口大小为1

     • 链路利用率：$U=\frac{L/R}{RTT+L/R}$
     • 改进：流水线技术，一次传w帧，$U=\frac{w\times L/R}{RTT+L/R}$

   • go back n ARQ（GBN）：发送窗口大小大于1（$< 2^n-1$），接收窗口大小为1，接受方必须按发送顺序确认

     出错处理：接收方丢弃从出错帧开始的所有帧，直到出错帧正确传输；发送方回退至出错帧全部重传

   • Selective Repeat ARQ：发送窗口大小大于1（$< 2^n-1$），接收窗口大小大于1，只有出错帧重传

     • 接收端发出Ack i后窗口移动到第i位，Ack i表示前i帧已收到

       

     • 流水线技术：提高信道利用率

5. 序列字段大小n、滑动窗口最大尺寸W、通道最大利用率U的关系

   • $W=2^n-1$，$W=2\times BD(带宽延时积)+1=\frac{1}{U}$，$BD=\frac{T_{prop}}{T_{trans}}$

HDLC 与 PPP 协议

HDLC

高级数据链路控制HDLC, High-Level Data Link Control：ISO标准的数据链路协议，针对点对点链路

• 数据帧格式：

  • 标志字段：01111110(7EH)
  • 控制字段：前两位帧类型：信息帧、监督帧、无编号帧，后六位根据帧类型定义
  • 帧校验序列：16位CRC校验，多项式为$x^{16}+x^{12}+x^5+1$

PPP

点对点协议PPP, Point-to-Point Protocol，为因特网数据链路层协议，针对点对点链路

• 将IP数据包封装到串行链路的方法

• 子协议：

  • 链路控制协议LCP(link control protocol)：发送端和接收端通过发送LCP包来确定在数据传输中的必要信息，用于建立点对点链路
  • 网络控制协议NCP(Network Control Protocol)：用于对多种网络协议进行配置协商

• 帧格式：

  首尾是帧标识符

  

  

• 不提供的功能：无错误控制与恢复、无流量控制、无序传输、不支持多点链路

实现链路点到点通信

三个组成部分

• 链路控制协议LCP

  用于启动、测试线路、协商选项，并在不再需要时再次关闭线路。它支持同步和异步电路以及面向字节和面向位的编码。

• 网络控制协议NCP：配置网络层协议的逻辑链接

  一种以独立于要使用的网络层协议的方式协商网络层选项的方法。

• 一个将IP数据报封装到串行链路的方法

帧格式

第四章：介质访问控制子层 MAC Medium Access Control

Medium Access Control

介质访问控制子层需要决定广播信道中信道分配，主要在 LAN 中使用 关键技术：信道分配（效率、公平、浪费时间最小）

• 静态信道分配：用户静态分配带宽 FDM 或时间槽 TDM，低效、性能差

• 动态信道分配：MAC

  • 分类：信道划分、随机接入、受控接入协议
    • 信道划分介质访问控制 Channel partitioning：时分、频分、码分
    • 随机访问介质访问控制 Random access：不划分信道，允许冲突，冲突时恢复
    • 轮询访问介质访问控制 Controlled-access protocols：节点按顺序共享介质，公平

PPP 提供检错但不提供纠错，同时也是不可靠的协议，不使用序号和确认机制，只支持全双工链路，面向字节

信道分类

广播信道

一对多通信，一个节点发送的数据能够被广播信道上所有的节点接收到。 所有的节点都在同一个广播信道上发送数据，因此需要有专门的控制方法进行协调，避免发生冲突（冲突也叫碰撞）。 主要有两种控制方法进行协调，一个是使用信道复用技术，一是使用 CSMA/CD 协议。

点对点信道

一对一通信。 因为不会发生碰撞，因此也比较简单，使用 PPP 协议进行控制。

信道划分技术

1. 频分复用 FDM

频分复用的所有主机在相同的时间占用不同的频率带宽资源。

2. 时分复用 TDM

Time Division Multiplexing 时分复用的所有主机在不同的时间占用相同的频率带宽资源。

将时间分为等长的 TDM 帧，每个 TDM 帧被分为等长的 m 个“时隙”，将 m 个时隙分配给 m 个用户（节点）使用。

使用频分复用和时分复用进行通信，在通信的过程中主机会一直占用一部分信道资源。但是由于计算机数据的突发性质，通信过程没必要一直占用信道资源而不让出给其它用户使用，因此这两种方式对信道的利用率都不高。

3. 统计时分复用 STDM

是对时分复用的一种改进，不固定每个用户在时分复用帧中的位置，只要有数据就集中起来组成统计时分复用帧然后发送。

4. 波分复用 WDM

光的频分复用。由于光的频率很高，因此习惯上用波长而不是频率来表示所使用的光载波。

5. 码分复用 CDM

为每个用户分配 m bit 的码片，并且所有的码片正交，对于任意两个码片 和 有

为了讨论方便，取 m=8，设码片 为 00011011。在拥有该码片的用户发送比特 1 时就发送该码片，发送比特 0 时就发送该码片的反码 11100100。

在计算时将 00011011 记作 (-1 -1 -1 +1 +1 -1 +1 +1)，可以得到

其中 为 的反码。

利用上面的式子我们知道，当接收端使用码片 对接收到的数据进行内积运算时，结果为 0 的是其它用户发送的数据，结果为 1 的是用户发送的比特 1，结果为 -1 的是用户发送的比特 0。

码分复用需要发送的数据量为原先的 m 倍。

随机访问 Random Access

核心思想：争用信道，胜利者获得信息发送权

纯ALOHA协议 pure ALOHA

当网络中任意站点需要发送数据时，可以不进行任意检测就发送，如果在一段时间内发送节点未收到确认，则该站点认为传输过程中发生了冲突，等待一段时间后再重传数据

假设网络负载为G（T0时间内所有站点发送成功和未成功而重传的帧数），吞吐量S（T0时间内发送成功的平均帧数）为

吞吐率：$S=G \times e^{-2G}$，$S_{max}=0.184,G=\frac{1}{2}$，G 是每秒发送帧的个数，实际发送成功的帧的个数等于 G * S

当G=0.5时，S最大

时隙ALOHA协议 slotted ALOHA

从吞吐量来看，纯ALOHA协议效率很低，设计间隙ALOHA协议

将时间划分为当长的时隙 slot，规定只有在时隙开始时才能发送数据，控制每个真可以在一个时隙内发送完毕。时隙 aloha 也会发生冲突，但是发生冲突的概率比纯 ALOHA 小。

吞吐率：$S=G \times e^{-G}$，$S_{max}=0.368,G=1$，G 是每秒发送帧的个数，实际发送成功的帧的个数等于 G * S

CSMA 协议 Carrier Sense Multiple Access

载波侦听多路访问，每个站点发送前都先侦听一下公共信道，发现信道空闲后才发送

可分为 冲突原因：传播时延，传播时延越长性能越差 $易受攻击时间=t_{prop}$

不坚持型 CSMA

• 如果忙，等待一段随机时间后再次侦听
• 如果空闲，立刻发送
• 冲突减少但延迟增多
  • ==优点==：可以减少冲突的发生
  • ==缺点==：信道利用率变低

1 -坚持型 CSMA

• 如果忙，继续坚持侦听信道
• 如果空闲，立刻发送
• 如果检测到冲突，等待随机一段时间后发送
  • ==缺点==：如果多个节点已经准备好数据，一旦信道空闲，会有多个节点同时发送数据，冲突概率大。

p -坚持型 CSMA

• 如果忙，继续坚持侦听信道
• 如果空闲，则以p概率发送数据，1-p概率推迟到下一时隙，在下一时隙也以相同概率判断

CSMA/CD协议 Collision detect

CSMA 协议改进方案，适用于总线形网络或半双工网络（如同轴电缆连接多个节点组成的有线局域网，用集线器连接多个节点组成的有线局域网）。不工作在无线 LAN

先听后发，边听边发，冲突停发，随机重发

• 适配器从网络层获得一个分组，封装成以太网帧，放入适配器缓存，准备发送
• 持续侦听信道，如果信道忙则持续侦听
• 如果信道空闲，则发送该帧，发送过程中持续侦听，如果检测到冲突，则终止数据发送
• 中止发送后，随机等待一段时间后继续侦听信道
• 终止 k 次后传输失败，放弃传输，把情况报告给网络层

$帧传输时间\geq 冲突检测时间=2*t_{prop}+jam \space sequence \space transmission \space time$ 最小帧长 $L_{min}=Ra=2R(\frac{S}{0.7c}+T_{phy})$，R 为数据传输速率，$T_{phy}$ 为物理层延迟

争用期：最差情况下需要两倍传播时延才能检出冲突，节点检测到冲突的最长时间：2 * 最远单项传播时延 经过这个时间才能确定自己节点占领整个信道

CSMA/CA协议 collision avoidance

可使用在无线LAN，处理了隐蔽站问题（hidden terminal）

• 源发送帧前侦听
  • 侦听直到空闲
  • 等待一段DIFS时间，然后发送一个控制帧RTS
• 目标接受到RTS后等待一段SIFS时间，发送一个控制帧CTS到源表示已经准备好接收数据
• 源接受到CTS后等待SIFS后发送数据
• 目标接收数据后等待SIFS后发送ACK给源

LANs and IEEE 802

使用广播信道，局域网特性由三个要素决定：拓扑结构、传输介质、介质访问控制方式

拓扑结构

• 物理拓扑：物理连接的位置与布局
• 逻辑拓扑：
  • 总线型
  • 树形
  • 星型
  • 环型 IEEE 802 参考模型：规定了数据链路层分 2 层协议层次结构，MAC、LLC（logical link control）

以太网 Ethernet

拓扑 Ptopologies：总线形、星型、树型拓扑

信号 Signaling：数字信号，基带传输，曼彻斯特编码

访问控制：CSMA/CD，IEEE802.3 MAC

传输速度：10 Mbps, 100 Mbps, or above

传输媒体：同轴电缆、双绞线、光缆

以太网MAC帧结构

一帧大小是 64B ~ 1518B

• Preamble 前置字段，用于帧同步
• Type：指出更高一层的协议类型
• PAD：填充字段，当Data不足46时进行补充

冲突域、广播域

冲突域 collision domain：如果两个节点同时发送数据，会导致冲突，则二者处于同一个冲突域

广播域 broadcast domain：如果一个节点发送广播帧 broadcast frame，可以被另一个节点接收，则二者处于同一个广播域。（同一个局域网内的各节点属于同一个广播域，如连接同一个集线器的节点）

集线器 hub：不隔离冲突域 collision domain，不隔离广播域 broadcast domain

以太网交换机 Ethernet switch：隔离冲突域 collision domain，不隔离广播域 broadcast domain

路由器 router：隔离冲突域 collision domain，隔离广播域 broadcast domain

指数回退算法

太网使用1-persistent CSMA/CD：线路理想则立即发送，线路忙则等待随机时间后再检测，发生冲突则广播 jam 信号，等待随机时间后恢复，等待时间由指数回退算法确定

• 指数回退算法：$R=random[0,2^{k-1}],WaitingTime=R\times SlotTime$

  $k=\min(retransmission,10)$

  $SlotTime=2*propagation \space delay+Jam \space sequence \space transmission \space time \\=51.2us(以太网10Mbps)$

• 失败 16 次后会放弃，并报告失败

• 无冲突时最大吞吐率 $T=\frac{L}{t_{prop}+t_{trans}}$，最大效率 $U=\frac{T}{R}=\frac{1}{\alpha+1},\alpha=\frac{t_{prop}}{t_{trans}}$，R 为数据传输速率

无线局域网 Wireless LAN

MAC 功能：

• 可靠数据传输：

• 帧交换协议：Ack

• 一次交换 4 帧

• 访问控制：

• 分布式协调功能 DCF：基于竞争，CSMA/CA

• 点协调功能 PCF：无争用，集中式访问协议 DCF、PCF 被集成在一个超帧中

• 安全

局域网互联 LAN Interconnection

网络互连：不同设备在不同层次进行交换

• 物理层：电信号，中继器 repeater 和集线器 hub
• 数据链路层：帧，网桥 bridge 和交换机 switch
• 网络层：数据包，路由器 router
• 传输层及以上：消息，网关 gateway

中继器 Repeater 和集线器 Hub：存在冲突传播，不支持不同局域网设备，对最大节点数和距离有限制

网桥 Bridge：通过 MAC 连接两个或多个局域网，并传输帧

路由器 Router：连接不同子网，对主机不透明

网关 Gateway：连接不同体系结构的网络，进行地址映射、报文格式转换、网络协议转换

网桥/交换机和路由器的结合：网桥自学习算法 learning bridge algorithm、生成树算法 spanning tree algorithm

LAN Switching 局域网交换

方法：网桥（Bridge）和交换机（Switch）

网桥：连接两个或多个局域网，并传输帧，每个局域网有自己的冲突域，网桥连接的局域网称为扩展局域网

交换机：基于硬件的交换结构构成专用通道，分割冲突域

交通隔离：交换机将子网划分为局域网段，每个局域网段为一个冲突域 （collision domain），不同网段间通常不传输帧

直通交换 Cut-Through Switching：

• 提出原因：缓冲帧花费的时间占总延迟的很大一部分
• 要求：尽早开始传输，重叠传输
• 特点：延迟为传输帧头的时间，即检查帧头后开始传输

自学习机制：辅助确定帧传播路径

交换机维护一个交换机表 switch table (MAC Address, Port, Age)

MAC address：目标地址，Port：输出端口，Age：该条记录存在的时间

当交换表接收到帧时

• 如果在表中找到了目标MAC地址对应的表项
  • 如果目标地址与源地址相同，则丢弃
  • 否则根据表项进行转发
• 否则进行泛洪
• 交换机根据目标的返回端口记录更新MAC表

缺点：洪泛会导致消息循环 loop -> 生成树算法 Spanning Trees

IEEE 802.1 d 规定生成树协议 STP，网桥通过网桥协议数据单元 BPDU构建生成树，称为透明网桥

• 网桥 ID BID：标识每个网桥，包括（Bridge Priority (2 B), MAC Address (6 B)），优先级越小越容易选中
• 根网桥 Root Bridge：最小 ID 的网桥，ID 相同时选 MAC 地址最小的
• 根端口 root port：非根网桥到根网桥距离最小的端口
• 工作原理：选出根网桥，所有非根网桥选择到达根网桥的最短路径，之后选择根端口和指定端口，完成生成树建立，当网络拓扑结构变化时，交换机自动启动备份链路
• 无广播风暴，无 MAC 表震荡，无多帧复制

虚拟局域网 VLAN

背景：大型局域网(如校园网)，一个节点发出的广播帧可能会被广播到所有节点，产生“广播风暴”。不安全，敏感节点没有被隔离

• 可以将大型局域网分割成若干个较小的VLAN，每个VLAN是一个广播域
• 每个VLAN对应一个VID

• 可划分广播域
• 更高的安全性
• 通过软件配置

VLAN划分方法

1. 基于接口

   在交换机后台根据交换机的端口号划分

   

2. 基于MAC地址

   在交换机中将节点的MAC地址和VID进行绑定，这样即使节点改变了接口，还是属于原来的VLAN

   

3. 基于IP地址

   不只是物理层和数据链路层，需要网络层功能支持。可以让VLAN范围跨越路由器，让多个局域网的主机组成一个VLAN

   

802.1Q帧结构

VLAN Trunk：VLAN中继，以太网中级可以在一个链路上承载多个VLAN的流量

使用帧标记（VLAN tagging）来区分不同VLAN的流量

VTP：VLAN Trunking Protocol

帧结构增加4字节在中间，作为VLAN标签。VLAN标签指明发送方所属的VLAN的VID。

第五章：网络层 Network Layer

图片文字版（网络层封装、路由器转发与解封装）：

发送主机
应用层：报文
  ↓
传输层：给报文加传输层首部，形成报文段
  ↓
网络层：给报文段加 IP 数据报首部 H3，形成 IP 数据报/分组
  ↓
数据链路层：加链路层首部 H2 和尾部 T2，形成帧
  ↓
物理层：转换为比特流发送

中间路由器
只处理物理层、数据链路层、网络层：
接收帧 -> 去掉链路层 H2/T2 -> 查看 IP 数据报首部 -> 选择下一跳/输出接口 -> 重新封装成新的链路层帧转发。

接收主机
按相反方向逐层解封装：
比特流 -> 帧 -> IP 数据报 -> 报文段 -> 应用层报文。

网络层功能

网络层必须了解子网的拓扑结构并且选择正确的路径传递数据，当源与目的处于不同网络时，需要处理不同

图片文字版（网络层的功能）：

网络层的功能
├─ 异构网络互联
│  ├─ 异构：不同网络的拓扑结构、物理层/链路层实现、主机类型可能不同
│  ├─ 关键设备：路由器 Router
│  └─ 在 TCP/IP 文献中，路由器也称为网关 Gateway
├─ 路由与转发
│  ├─ 路由：多个路由器相互配合，规划 IP 数据报/分组的最佳转发路径
│  │  └─ 各路由器运行路由协议，最终生成自己的路由表
│  └─ 转发：单台路由器根据转发表，把收到的 IP 数据报从合适接口转发出去
│     └─ 转发表是精简版路由表，便于快速检索
└─ 拥塞控制
   ├─ 原因：网络中分组过量、负载过高，导致性能下降
   ├─ 现象：网络分组数增加，但吞吐量反而降低
   ├─ 类比：道路车辆太多时，收费站吞吐量下降
   └─ 方法
      ├─ 开环控制：静态方法，部署前预设防拥塞策略，运行后不再修改
      └─ 闭环控制：动态方法，监视网络状态，发现拥塞后通知相关路由器调整

作用：

• 异构网络的互联（在网络层），形成互联网络
• 转发与路由
• 阻塞控制

交换技术：采用分组交换，包括虚电路分组交换（面向连接）、数据报分组交换（无连接）

两种提供给传输层的服务（分组交换packet）

• 面向连接的服务：虚电路（virtual circuit）
• 无连接的服务：数据报（datagram）

功能

• 转发：将分组从路由器的输入移动到适当的路由器输出
• 路由：决定分组从源到目的地所采用的路由

虚电路分组交换 virtual circuit：建立虚电路表（入端口，入虚电路号，出端口，出虚电路号），第一个分组探索、建立虚电路表，后续分组按虚电路表传输而不需要目的地址，传输路径固定

• 数据包分组交换 datagram：路由表（目的地址，输出端口），不需要建立连接，传输路径不固定，可能乱序到达
  • 目的地址选择：最长前缀匹配

异构网络互联

异构：每个网络拓扑结构不同，物理层和数据层的实现不同，主机类型也各不相同

拥塞控制 congestion control（不在考纲内）

在通信子网中出现过量分组引起网络功能下降的现象称为拥塞

两种方法

• 开环控制：部署网络时就设计好预防拥塞的方法
• 闭环控制 Closed Loop：动态监视网络状态

路由算法

路由算法：确定与维护路由表，决定源地址到目的地址的最佳路径

路由和转发

转发：将包从设备（路由器或者交换机）输入端口传输到合适的端口输出，本地动作（单台路由器）

路由：建立与维护源地址到目的地址的路由表，由路由算法决定，全局规划（多台路由器）

路由器转发分组是通过路由表（Routing Table）实现的，路由算法可划分为：

• 分类：非自适应路由选择算法（静态路由）、自适应路由选择算法（动态路由）
  • 非自适应路由选择算法：最短路径优先算法 Dijkstra、洪泛算法 flooding
  • 自适应路由选择算法：距离向量路由算法 Distance Vector Routing、链路状态路由算法 Link State Routing、层次化路由算法
• 自适应路由选择算法分类：集中的、独立的、分布式的
  • 汇集树：从源到给定目的地的一组最优路由形成的树

洪泛算法 Flooding：广播，利用跳步计数器/生存期限制一个包的广播次数，避免广播风暴（在数据链路层，交换机无法使用这一技术，必须预先去除环结构）

距离向量路由算法：基于Bellman-Ford 算法，每个结点维护一个距离向量表（目的地，下一跳，距离）

• Bellman-Ford 算法：$d_x(y)=\min_{z}(d_z(y)+w(x,z))$

• 特点：迭代、异步、分布式

• 距离向量表更新：每个结点周期性地将自己的距离向量表发送给相邻结点，用于更新距离

• 存在无穷计数问题：一个节点断开后，其他节点距离会逐渐增大到无穷大

• 慢收敛问题的解决：

• 有限计数：使用有限数代表无穷大（不可达）

• 水平分割 split horizon：如果 Z 通过 Y 到达 X，则 Z 不将 X 通告给 Y

• 毒性逆转 poisoned reverse：如果 Z 通过 Y 到达 X，则 Z 将 X 通告给 Y，但 X 的距离为无穷大

  • 不能完全消除路由回路问题

链路状态路由算法 Link State Routing：每个路由器维护整个网络的拓扑图，将直接连接信息定期洪泛，在收到距离向量后，路由器更新本地拓扑图并重新计算最短路径

层次化路由算法：路由器分区，每个路由器维护包括区内路由器与其他区域距离的路由表

IPV4

IP数据报

因特网可被视作异构网络（自治系统Autonomous Systems）的集合，网络层的IP协议将这些网络连接在一起

IP协议栈可以参考如下

应用层：HTTP、FTP、SMTP、TELNET、DNS、...
传输层：TCP、UDP
网络层：ICMP、ARP、IP、IGMP、RARP
链路/物理相关技术：IEEE 802、FDDI、PPP、X.25、ATM、...

IP协议格式栈参考如下 IP datagram format

首部固定部 分为 20B；首部最短 20B，最长 2^4 * 4B = 60B。

字段含义：

• ver：IP 协议版本。

• hlen：首部长度。

• type of service：服务类型/数据类型。

• length：IP 数据报总长度。

• identifier / flags / fragment offset：用于分片和重组。

• time to live：剩余可经过路由器数，每到一个路由器减 1。

• upper layer：数据部分应交付给的上层协议。

• Internet checksum：首部校验和。

• options：可选项，如时间戳、记录已走路由、指定必须访问的路由器列表等。

• head length：首部长度，占4位，以4bytes为单位，通常表示20bytes，最大60bytes

• length：总长度，占16为，以1bytes为单位

• identifier：标识，占16位，用于重组分片后的数据报

• flgs：标志，占3位，其中两位有用，分别是中间位DF和末位MF，DF=0表示允许分片，MF=1表示还存在后续分片

• offset：片偏移，占13位，以8bytes为单位

• time to live（TTL）：生存时间，表示可通过路由器的最大值，超过则数据报无效，每经过一个就减一

• 协议，占8位，指出下一协议是什么，6表示TCP，17表示UDP

• Internet checksum：占16位，只校验首部

例题：

最大传输长度MTU：比较大的IP数据包会被划分，在最终目的地重组，示例如下

图片文字版（4000B 数据报按 MTU=1500B 分片）：

原始 IP 数据报：
总长度 = 4000B
首部 = 20B
数据部分 = 4000 - 20 = 3980B
ID = x，fragflag/MF = 0，offset = 0

链路 MTU = 1500B：
每个满载分片的数据部分 = 1500 - 20 = 1480B
片偏移单位 = 8B
offset = 1480 / 8 = 185

分片结果：
1. length = 1500，ID = x，MF = 1，offset = 0，数据 = 1480B
2. length = 1500，ID = x，MF = 1，offset = 185，数据 = 1480B
3. length = 1040，ID = x，MF = 0，offset = 370，数据 = 1020B

IP数据报分片

因为路由器的MTU大小限制，可能无法一次性发送整个ip数据报，所以需要进行分片。

• flgs：标志，占3位，其中两位有用，分别是中间位DF和末位MF，DF=0表示允许分片，MF=1表示还存在后续分片
• offset：片偏移，占13位，以8bytes为单位

IP地址

32位，以“.”分隔，对主机、路由器的**接口（和链路层）**进行标识

地址分类

图片文字版（最初的 IP 地址分类方案）：

32 bit IP 地址的两级结构：<网络号>, <主机号>。网络号不定长，可根据前几个比特判断类别，从而推测网络号占多少位。

要到达一个host

• 先找到NetworkID
• 再查找HostID，当主机号为全1时表示广播

几个被保留做私有地址的网段

• A类 1个，10.0.0.0-
• B类 180.8..
• C类

同一局域网上的主机或者路由器IP地址中的网络号必须是一样的

路由器总是具有两个或两个以上的IP 地址。路由器的每一个接口都有一个不同网络号的IP 地址。

特殊用途的IP地址：

目的地址全1：向本网络全部设备广播IP分组。

源地址全0：（DHCP协议）一台新接入网络的设备，无IP地址时，只能先写成全0，目的地址全1

子网

• 子网划分前：IP地址为两级结构 = <网络号，主机号>

• 子网划分后：IP地址为三级结构 = <网络号，子网号，主机号>

注意：每个子网地址中，主机号不能分配为全0/全1 ---全0表示子网本身，全1表示子网广播地址

作用：将一个很大的IP地址块拆分成多个更小的子网（独立网络），比如一个学校开设多个校区，可以在一个地址段下设置多个子网。

地址分类问题：所有在同一网络下的主机必须有同样的网络号

解决方案：将一个网络划分为子网，使世界只知道主网络，不知道子网

子网内的主机交流无需路由器转发

掩码mask

子网掩码的作用与注意点：

作用：

1. 用子网掩码和 IP 地址逐位与，算出 <网络号, 子网号>。 <网络号, 子网号> 也可以合称为“网络前缀”。
2. 只有网络前缀相同的 IP 地址，才归属于同一个网络/子网。

注意：

1. 如果一个网络内部进行了子网划分，那么该网络中的每台主机、每个路由器接口都需要配置： IP 地址、默认网关、子网掩码。
2. 如果一台路由器支持子网划分技术，那么在它的转发表中，需要包含： <目的网络号, 子网掩码, 转发接口>。

子网设备出了配置自己的IP地址、默认网关外，还需要配置子网掩码

路由器在一个网络外通过网络地址路由，在网络内通过子网地址路由，路由器使用32位掩码来对网络地址进行认证

• 位=1：表示该位属于网络号+子网号（合称为网络前缀）
• 位=0：表示该位属于主机号

网络号= IP地址 AND 掩码

子网路由方式：

路由表的表项结构为<Subnet, Mask, NextHop>

• 对于每一个表项计算D1=D&Mask，如果D1=Subnet
  • 如果下一跳为接口，则直接交付给D
  • 否则传送给下一跳路由器

无分类编址CIDR

CIDR（Classless InterDomain Routing）：无分类域间路由选择，使用任意长度的子网部分，可讲几个网络构建一个更大范围的地址的网络（超级网supernetwork），是一种归并（aggregation）技术

• 目标：在最小化路由器需要知道的路由数量与高效分发地址之间取得平衡
• 内容：不再按5类划分网络，IP地址子网长度任意，地址格式：a.b.c.d/x，x表示IP地址中子网位数
  • IP地址根据x划分为Prefix+Suffix，总长32位，Prefix：块中所有地址共用，用于区分块，Suffix：区分块中地址
• 作用：将多个网络合并成一个大的网络，称为超网
• 路由汇聚route aggregation：将路由表中prefix相同且nextHop相同的地址合并成一个CIDR地址，以减小路由表大小
  • 当一个IP在路由表中有多个prefix匹配时，按最长匹配原则选择
  • 分层寻址：prefix逐层汇聚，形成树状结构
• 优点：灵活分配不同块的大小

网络前缀可变长

32 bit 地址 = Prefix + Suffix

CIDR notation:
a.b.c.d / x

x 表示网络前缀 Prefix 的长度。

Prefix：地址块中所有地址共同拥有的部分。
Suffix：区分地址块内唯一地址的部分。

默认前缀长度：
Class A：a.b.c.d/8
Class B：a.b.c.d/16
Class C：a.b.c.d/24

定长子网划分FLSM

前面子网板块讲的，每个CIDR把主机号前k bit抠出来作为定长子网号，这样可以划分出$2^k$个子网（每个子网包含的IP地址块大小相等，都包含 $2^{n-k}$ 个IP地址） 缺点：不够灵活，IP地址利用率低，，浪费有限的IP地址资源

变长子网划分VLSM

变长网划分，比子网更灵活，在一个CIDR地址块中，划分子网时，子网号长度不固定（每个子网包含的IP地址块大小不同）

哈夫曼树

路由聚合

对于路由转发表，如果几条路由表项的转发接口相同，部分网络前缀也相同，那么可以将这几条路由表项聚合成一条。这种地址的聚合成为路由聚合，也成为超网

NAT

Network Address Translation，网络地址转换，是一种缓解 IP 地址耗尽的方法：将专用网络地址转换为公用网络地址，对外隐藏内部主机的真实 IP 地址。专用网本地 IP 地址可以重用。

NAT 要点总结

• 私有 IP 地址（内网 IP）：只允许分配给局域网内部的节点，不允许分配给互联网上的节点。
  • 10.0.0.0 ~ 10.255.255.255
  • 172.16.0.0 ~ 172.31.255.255
  • 192.168.0.0 ~ 192.168.255.255
  • 每个局域网内部都可以自行分配这些私有 IP 地址。
  • 私有 IP 地址是可复用的，只要求局域网内唯一，不要求全球唯一。
• 全球 IP 地址（外网 IP）：通常由 ISP 提供，全球唯一。
  • 外网 IP 是一个局域网与外界通信时所需使用的 IP 地址。
  • 对外部世界，公司或家庭内部的 IP 分配不可见；内部主机访问外网时，对外表现为 NAT 路由器的外网 IP，但会使用不同端口区分连接。
• NAT 路由器的作用：转发 IP 数据报时，进行内网 IP、外网 IP 的相互转换。
  • NAT 表记录地址转换关系：<内网 IP:端口号> <-> <外网 IP:端口号>。
  • 从内网转发到外网：更改源 IP 地址、源端口号。
  • 从外网转发到内网：更改目的 IP 地址、目的端口号。
  • NAT 路由器包含传输层的功能，因为端口号是传输层的概念。

网络地址转换 NAT
├─ 私有 IP 地址（内网 IP）
│  ├─ 10.0.0.0 ~ 10.255.255.255
│  ├─ 172.16.0.0 ~ 172.31.255.255
│  ├─ 192.168.0.0 ~ 192.168.255.255
│  ├─ 只允许分配给局域网内部节点
│  ├─ 每个局域网内部可以自行分配
│  └─ 可复用：局域网内唯一即可，不要求全球唯一
├─ 全球 IP 地址（外网 IP）
│  ├─ 通常由 ISP 提供，全球唯一
│  └─ 局域网与外界通信时使用
└─ NAT 路由器
   ├─ 作用：转发 IP 数据报时转换内网 IP 与外网 IP
   ├─ NAT 表：记录 <内网 IP:端口号> <-> <外网 IP:端口号>
   ├─ 内网 -> 外网：改源 IP、源端口
   ├─ 外网 -> 内网：改目的 IP、目的端口
   └─ 包含传输层功能：端口号属于传输层

NAT 与普通路由器的区别

• 普通路由器转发 IP 数据报时，不会改变源 IP 地址和目的 IP 地址。
• 普通路由器通常只包含网络层及以下功能。
• NAT 路由器会改写 IP 地址和端口号，因此除了网络层功能，还涉及传输层功能。

NAT 并不能真正解决地址短缺问题。

• 缺点：违反端到端的观点，两个 NAT 主机难以建立连接。

网际控制报文协议 ICMP

Internet Control Message Protocol，在路由器和主机间交流IP数据和错误信息，在通过IP实现，作为IP报文的数据发送 ICMP 属于网络层，ICMP 报文封装在 IP 数据报中。ICMP 可以让主机或路由器互相报告网络中发生的差错和异常情况。

产生的原因不包括

• 对ICMP差错报文再产生差错报文
• 广播、多播
• 对分片报文的第一个以外的报文

• ICMP 协议属于网络层。
• IP 协议为 ICMP 协议提供服务。
• ICMP 协议用于主机、路由器之间相互通知网络中发生的“异常事件”。

flowchart TB
  subgraph APP["应用层协议"]
    SMTP["SMTP、POP3协议<br/>（电子邮件）"]
    HTTP["HTTP"]
    FTP["FTP"]
    DNS["DNS"]
    DHCP["DHCP"]
  end

  subgraph TRANS["传输层协议"]
    TCP["TCP协议"]
    UDP["UDP协议"]
  end

  subgraph NET["网络层协议"]
    ARP["ARP"]
    IP["IP"]
    ICMP["ICMP"]
    IGMP["IGMP"]
  end

  subgraph LINK["数据链路层 & 物理层协议"]
    E8023["802.3<br/>（CSMA/CD）"]
    E80211["802.11<br/>（CSMA/CA）"]
    E8025["802.5<br/>（令牌传递协议）"]
  end

  SMTP --> TCP
  HTTP --> TCP
  FTP --> TCP

  DNS --> UDP
  DHCP --> UDP

  TCP --> IP
  UDP --> IP

  ICMP --> IP
  IGMP --> IP
  IP -.-> ARP

  IP --> E8023
  IP --> E80211
  IP --> E8025

ICMP 报文类型

• 差错报告报文：

  • Destination Unreachable：终点不可达，当路由器或主机不可交付数据包时

    • 路由器告诉发送方：目的 IP 不可达（道路不通）
    • 目的主机告诉发送方：目的端口号不存在，没有对应进程）

  • Redirect：重定向（改变路由）

    • 路由器告诉发送方：对于这个目的网络，下次选择另一个更短的路由器。

  • Time Exceeded：超时

    • 路由器告诉发送方：路由器接收到 TTL 为 0 的数据报时（路程太远）
    • 目的主机告诉发送方：你的 IP 数据报备分片了，规定时间内没到齐，我已全部丢弃。

  • ：参数问题

    • 告诉发送方：你的 IP 数据报首部参数不合法，胡总首部校验出错。

  • Source Quench：源点抑制（2012 年后已废弃），当路由器或主机因为拥塞丢弃数据报时

• 请求报文
  • Echo Request：回送请求： A->B: 在吗
  • Echo Reply：回送回答：B->A：在
  • Timestamp Request：时间戳请求：A->B: 我这边时间是 xxxx，你那边几点
  • Timestamp Reply：时间戳回答：B->A: 我接收到请求的时间是 yyyy，我发出回答的时间是 zzzz

不需要反馈 ICMP 差错报告保温的情况

• 若携带 ICMP 差错报告报文的 IP 数据报出错，不再反馈 ICMP 差错
• 若 IP 数据报被分片，则无论几个分片出错，都只反馈一次 ICMP 差错
• 若 IP 数据报的目的地址为多播地址，不反馈 ICMP 差错
• 若 IP 数据报的原地址为特殊地址（如 127. x.x.x 0.0.0.0），即使发生 IP 数据报异常也不反馈

典型应用

ping 基于 回送请求报文，回答请求报文 实现功能 traceroute（tracert） 基于 时间超过报文 实现功能

地址解析协议 ARP

Address Resolution Protocol,在IP和Mac地址间进行转换，运行在网络层

每个在LAN中的IP节点都有ARP表，表项的格式为< IP address; MAC address; TTL>

ARP提供动态映射，表项的建立需要经过

• ARP请求： 如果IP包发送方不知道接收方IP地址，则广播ARP请求，向所有 LAN 中结点发送 ARP 请求包，询问目的 IP 主机的 MAC 地址

• ARP回复 拥有目的 IP 的 MAC 地址的主机单播返回该主机目的 IP 的 MAC 地址

需要注意的是，ARP解决是位于一个自我网内的地址转换问题，对于不在一个子网的情况，需要发送给路由器，转交到下一个网络解决

反向地址解析协议 RARP

Reverse Address Resolution Protocol，反向地址解析协议，与 ARP 的解析方向相反：

ARP：  已知 IP 地址，查询对应的 MAC 地址
RARP： 已知 MAC 地址，查询对应的 IP 地址

RARP 主要用于早期无盘工作站启动时获取自己的 IP 地址。主机刚启动时通常只知道自己的网卡 MAC 地址，还没有 IP 地址，因此向局域网中的 RARP 服务器发送请求：

• RARP 请求： 主机广播自己的 MAC 地址，请求服务器告知该 MAC 地址对应的 IP 地址

• RARP 回复： RARP 服务器返回该主机应该使用的 IP 地址

RARP 和 ARP 一样，不基于 TCP/UDP，也不封装在 IP 数据报中，而是直接封装在链路层帧中发送。在以太网中，ARP 的类型字段为 0x0806，RARP 的类型字段为 0x8035。

需要注意的是，RARP 功能较单一，只能根据 MAC 地址返回 IP 地址，不能提供默认网关、DNS、租约时间等信息，因此现在基本已被 BOOTP 和 DHCP 取代。

动态主机配置协议 DHCP

Dynamic Host Configuration Protocol，动态主机配置协议，用于让主机自动获取 IP 地址和其他网络配置参数。

DHCP 与 RARP 的核心用途有重合，都可以解决“主机刚接入网络时还没有 IP 地址，需要获取自己的 IP 地址”的问题；但 DHCP 功能更完整：

• RARP：主要根据 MAC 地址返回 IP 地址
• DHCP：可以分配 IP 地址，并同时下发子网掩码、默认网关、DNS 服务器、租约时间等参数

DHCP 属于应用层协议，基于 UDP 发送：

DHCP 客户端端口：UDP 68
DHCP 服务器端口：UDP 67

主机刚启动时还没有 IP 地址，因此 DHCP 初始请求通常使用特殊地址：

源 IP 地址：0.0.0.0
目的 IP 地址：255.255.255.255

DHCP 获取地址的典型过程可以概括为 DORA：

Discover：客户端广播寻找 DHCP 服务器
Offer：服务器提供可用 IP 地址和配置
Request：客户端请求使用某个服务器提供的配置
ACK：服务器确认分配，客户端正式使用该配置

DHCP 分配的是带租约的地址。租约到期前，客户端需要续租；如果不再使用，地址可以被服务器回收并重新分配。

需要注意的是，DHCP 请求一开始也常使用广播，但 DHCP 可以通过 DHCP Relay Agent 中继跨网段转发，因此比只能在本地链路内工作的 RARP 更适合现代网络。

IP分组路由和转发

分组的交付可分为

• 直接交付：交付给直接连接的网络的目标主机时，在同一子网内
• 间接交付：转发到中间路由器时，不在同一子网内

路由协议

Internet 由多个自治系统 Autonomous Systems（AS）组成。一个 AS 是由同一组织管理、使用统一路由策略的一组网络和路由器。

路由协议按使用范围分为：

路由协议
├─ IGP：AS 内部路由
│  ├─ RIP
│  ├─ OSPF
│  └─ IGRP
└─ EGP：AS 之间路由
   └─ BGP

RIP路由信息协议

RIP（Routing Information Protocol）属于 IGP，基于距离向量算法 Distance Vector。

基本特点

• 基于距离向量算法，距离跳数 hop count来计算，最大有效跳数为 15，16 表示不可达。
• 维护方式：每 30s 和相邻路由器通过 UDP 交换一次通告 advertisement。
• 承载方式：应用层协议，使用 UDP，端口号 520。
• 通告内容：最多包含 25 个目的子网的路由信息。
• 链路失效：超过 180 秒未收到邻居 advertisement 时认为邻居失效，将该信息通过 advertisement 迅速广播，使用毒性逆转技术避免环路
• 路由表：每个路由器维护 RIP 表，常见格式为：

<目的网络, 下一跳路由器, 跳数>

工作过程

1. 路由器刚启动时，只知道自己直接连接的网络。
2. 每 30s 向相邻路由器发送自己的路由表 advertisement。
3. 收到邻居的路由表后，将邻居通告的跳数加 1，再与本地 RIP 表比较。
4. 若发现更短路径，或原路径来自该邻居，则更新 RIP 表。
5. 若 180s 未收到某邻居的 advertisement，则认为邻居失效，把相关路由标记为不可达。

RIP 的本质是：每个路由器只知道“邻居告诉我的距离”，通过不断交换距离向量，逐步收敛到稳定路由。

优缺点

优点：

• 实现简单，配置和维护成本低。
• 小型网络中新设备收敛较快。
• 协议开销相对小。

缺点：

• 最大有效跳数只有 15，不适合大型网络。
• 周期性交换路由表，网络变大后开销增加。
• 距离向量算法容易产生路由环路。
• 设备离线收敛慢

常见防环思路包括水平分割、毒性逆转、触发更新等。毒性逆转 Poison Reverse 的基本思想是：如果路由器 A 通过邻居 B 学到某条路由，那么 A 再向 B 通告这条路由时，把距离通告为 16，表示不可达，从而减少路由环路。

OSPF开放最短路径优先协议

OSPF（Open Shortest Path First）属于 IGP，基于链路状态算法 Link State。

基本特点

• 核心算法：每台路由器根据链路状态数据库，使用 Dijkstra 算法计算以自己为根的最短路径树。
• 更新方式：链路状态变化时，使用洪泛 flooding 传播链路状态信息。
• 承载方式：直接封装在 IP 中，IP 协议号为 89，通常归为网络层协议。
• 度量：链路代价 cost，可以综合反映带宽、时延等因素。
• 层次结构：可把 AS 划分为多个区域 Area，包括局部区域 local area 和主干区域 backbone，主干区域通常为 Area 0。

实现过程

1. 建立邻接关系，发现直接相连的邻居和链路代价 cost。
2. 生成链路状态通告 LSA。
3. 使用洪泛法把 LSA 发送给区域内其他路由器。
4. 每台路由器根据收到的 LSA 构建链路状态数据库 LSDB。
5. 每台路由器独立运行 Dijkstra 算法，计算最短路径树。
6. 根据最短路径树生成路由表。

OSPF 与 RIP 的关键区别是：RIP 只知道“邻居告诉我的距离”，而 OSPF 会在区域内形成较完整的拓扑视图，再自己计算最短路径。

LSA 与 LSDB

区域结构

为了适应大规模网络，OSPF 可以把一个 AS 划分为多个区域：

优缺点

优点：

• 收敛速度通常快于 RIP。
• 支持层次化区域划分，适合中大型网络。
• 度量比跳数更灵活，可考虑带宽、时延等因素。
• 支持 CIDR/VLSM。

缺点：

• 实现和配置复杂度高于 RIP。
• 需要维护 LSDB，并运行 Dijkstra 算法，对路由器资源要求更高。

IGRP内部网关路由协议

IGRP（Interior Gateway Routing Protocol）属于 IGP，是 Cisco 早期提出的内部网关路由协议，基于距离向量算法。

• 与 RIP 类似，都是距离向量协议。
• 与 RIP 不同，IGRP 不只用跳数作为度量，还可综合带宽、时延、可靠性、负载等因素。
• 相比 RIP，IGRP 更适合较大的自治系统，但它是 Cisco 私有协议，后来被 EIGRP 取代。
• 应用层协议，通过 TCP 维护

BGP边界网关协议

BGP（Border Gateway Protocol）属于 EGP，用于在不同 AS 之间交换路由信息，基于路径向量协议 Path Vector Protocol。

• 作用：获取相邻 AS 的可达信息，并把可达信息传播给其他 AS。
• 目标：找到一条能够到达目的网络且较好的路由，而不是严格意义上的最短路径。
• 原因：AS 之间的路由选择还要考虑策略、商业关系、安全等因素。
• 承载方式：应用层协议，基于 TCP，端口号 179。
• 防环方式：通告中包含 AS_PATH，如果某 AS 发现路径中已经有自己，则拒绝该路由。

BGP 路由信息

BGP 通告的路由信息通常包含：

<网络前缀, 下一跳, AS_PATH, 路由属性>

常见报文

特点

• BGP 更重视策略，而不是单纯最短路径。
• 使用 TCP 保证 BGP 对等方之间通信可靠。
• 通过 AS_PATH 防止 AS 级别的路由环路。
• 适用于互联网级别的 AS 间路由。

RIP、OSPF、IGRP、BGP 对比

IPv6

• 采用 128 bit IP 地址，从根本上缓解 IPv4 地址耗尽问题。
• 支持无分类编址 CIDR，各级地址管理机构可以更灵活地划分子网大小。
• 地址空间很大，因此可以划分出更多层次，便于地址聚合和层次化管理。

IPv6 地址格式

IPv6 地址采用冒号十六进制记法：

128 bit = 8 组 * 16 bit
每组用十六进制表示，组与组之间用冒号分隔

例如：

2001:0db8:abcd:0012:0000:0000:0000:0001

压缩规则：

1. 每个 16 bit 分段内的前导 0可以省略。
2. 连续出现的一组或多组 0 可以用双冒号 :: 代替。
3. 一个 IPv6 地址中 :: 只能出现一次，否则无法判断省略了多少组 0。

例如：

2001:0db8:0000:0000:0000:ff00:0042:8329
= 2001:db8:0:0:0:ff00:42:8329
= 2001:db8::ff00:42:8329

一台主机的 IPv6 地址可理解为：

n bit 前缀 + 128-n bit 接口标识符

IPv6 地址资源的分配

IPv6 地址也可以用 CIDR 记法表示，例如：

2001:0db8:abcd:0012::/64

课件中的典型划分方式：

网络地址块前缀：64 bit
接口标识符：    64 bit

更一般地说：

IPv6 地址 = 前缀 n bit + 子网标识符 m bit + 接口标识符 128-n-m bit

其中接口标识符类似 IPv4 中的主机号。由于 IPv6 局域网接口标识符位数通常较长，主机可以在获得网络前缀后自动生成自己的地址。

即插即用与 DHCPv6

IPv6 支持即插即用，也就是 IP 地址自动配置：

• 主机接入网络后，可向路由器确认本网络前缀。
• 主机获得网络前缀后，可以自己生成接口标识符，组成 IPv6 地址。
• 接口标识符可以根据主机网卡 MAC 地址生成，也可以使用随机/临时接口标识符以增强隐私。

因此 IPv6 可以不使用 DHCP 也完成地址配置。

但在需要统一管理地址、DNS、租约等网络参数时，也可以使用 DHCPv6。

IPv6 地址分类

IPv6 目的地址的三种基本类型

注意：任播地址没有固定的专用前缀，通常由地址管理机构预先统一分配。

IP 多播

IP 多播 multicast 用于实现一对多通信：源主机只发送一份 IP 数据报，网络中的多播路由器负责把数据报复制并转发给加入该多播组的主机。本节主要讨论 IPv4 多播；IPv6 多播地址使用 FF00::/8，已在 IPv6 地址分类中说明。

可以类比为：

IP 单播地址：个人 QQ 号，只对应一台主机/一个接口
IP 多播地址：QQ群号，对应一个多播组，组内可能有多台主机

相关概念

IGMP 协议

IGMP 用于管理主机对多播组的加入和离开，类似“加入 QQ 群、退出 QQ 群”。

• 作用范围：主机与其直接相连的多播路由器之间。
• 作用：让本地多播路由器知道本网络中是否有主机属于某个多播组。
• 所属层次：网络层。
• 承载方式：使用 IP 协议提供服务，IP 首部中的协议字段为 2。

需要注意的是，IGMP 只负责本地网络内的组成员管理；跨路由器的多播转发路径，需要多播路由协议完成。

IP 多播地址

一个多播地址对应一个多播组，组内可以包含多台主机。

IPv4 多播地址使用 D 类地址：

范围：224.0.0.0 ~ 239.255.255.255
前四位：1110

D 类地址不再划分网络号和主机号，而是作为多播组标识使用。

IP 多播工作过程

1. 主机通过 IGMP 加入某个多播组。
2. 本地多播路由器记录本网络中存在该多播组成员。
3. 源主机向该多播组地址发送一份 IP 多播数据报。
4. 多播路由器根据多播路由协议建立的转发信息，把数据报转发到有组成员的网络方向。
5. 到达目的局域网后，组内主机接收该多播数据报。

核心思想：源主机不需要给每个接收者单独发送一份数据，而是发送给“多播组地址”，由网络在需要分叉的位置复制数据报。

IP 多播特点

1. 多播 IP 数据报仍然是“尽最大努力交付”，不提供可靠交付。
2. 多播地址只能作为目的地址，不能作为源地址。
3. 对多播数据报不产生 ICMP 差错报告报文。
4. 多播适合网络会议、视频直播、软件分发等一对多场景。

单播、广播、多播对比

第六章：传输层 Transport Layer

传输服务 Transport Service

传输层 Transport Layer 为不同主机上的进程 process 间提供逻辑通信，主要解决“端到端 end-to-end（进程到进程 process-to-process）”的数据传输问题。

• 面向连接的服务 connection-oriented service：TCP
• 无连接的、不可靠服务 connectionless and unreliable service：UDP

UDP 和 TCP 的特点

• 用户数据报协议 UDP（User Datagram Protocol）是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信。

• 传输控制协议 TCP（Transmission Control Protocol）是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块），每一条 TCP 连接只能是点对点的（一对一）。

UDP 首部格式

首部字段只有 8 个字节，包括源端口、目的端口、长度、检验和。12 字节的伪首部是为了计算检验和临时添加的。

TCP 首部格式

• 序号 ：用于对字节流进行编号，例如序号为 301，表示第一个字节的编号为 301，如果携带的数据长度为 100 字节，那么下一个报文段的序号应为 401。

• 确认号 ：期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段，序号为 501，携带的数据长度为 200 字节，因此 B 期望下一个报文段的序号为 701，B 发送给 A 的确认报文段中确认号就为 701。

• 数据偏移 ：指的是数据部分距离报文段起始处的偏移量，实际上指的是首部的长度。

• 确认 ACK ：当 ACK=1 时确认号字段有效，否则无效。TCP 规定，在连接建立后所有传送的报文段都必须把 ACK 置 1。

• 同步 SYN ：在连接建立时用来同步序号。当 SYN=1，ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接，则响应报文中 SYN=1，ACK=1。

• 终止 FIN ：用来释放一个连接，当 FIN=1 时，表示此报文段的发送方的数据已发送完毕，并要求释放连接。

• 窗口 ：窗口值作为接收方让发送方设置其发送窗口的依据。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。

TCP vs UDP

传输协议元素 Transport Protocol Elements

寻址 Addressing

寻址 addressing：对于网络层提交上来的报文段 segment/datagram，传输层根据报文段首部中的目的端口号 destination port number 将数据交付给相应的应用进程。

• 传输服务访问点 TSAP Transport Service Access Point：面向应用层，通常指端口 port，用于区分同一主机上的不同进程，用 16 bit 标识。
• 网络服务访问点 NSAP Network Service Access Point：面向网络层，通常对应 IP 地址，用于标识网络中的主机/接口。

IP address：标识网络中的一台主机/接口 host/interface
port number：标识该主机上的一个应用进程 application process

建立连接 Connection Establishment

面向连接的传输协议需要在数据传输前建立连接。TCP 使用三次握手 three-way handshake 来同步双方初始序号，并避免旧的、延迟到达的连接请求造成混乱。

遗忘域 Forbidden Region：指旧分组可能仍在网络中存活的时间/序号范围。连接建立时要避免新连接与旧连接中的迟到报文混淆，因此需要握手确认和初始序号 ISN。

连接释放 Connection Release

TCP 连接可以视为两个方向相反的单向连接，因此释放连接时两个方向需要分别关闭。一个方向关闭只表示本方向不再发送数据，另一方向仍可继续发送。

流量控制与缓存 Flow Control and Buffering

传输层需要处理发送端、接收端速率不匹配的问题。接收方通常设置接收缓存 buffer，并通过窗口 window 告诉发送方自己还能接收多少数据。

flow control：防止发送方发送过快，压垮接收方缓存
buffering：在发送端或接收端临时保存还未发送、未确认或未交付的数据

错误恢复 Error Recovery

错误恢复 error recovery 用于处理数据丢失、损坏、重复、乱序等问题。TCP 通过 checksum、sequence number、ACK、timeout、retransmission 实现可靠传输；UDP 通常只做差错检测，出错后直接丢弃。

复用与分用 Multiplexing and Demultiplexing

• 复用 Multiplexing（从上到下）： 发送数据时，同一台主机上的多个应用进程可以使用同一个传输层协议。传输层给数据加上源端口号 source port number、目的端口号 destination port number 等首部信息后交给网络层。

• 分用 Demultiplexing（从下到上）： 接收数据时，传输层根据目的端口号和协议类型 protocol type，把数据正确交付给对应的应用进程。

sender：多个进程 -> TCP/UDP -> IP        （复用 multiplexing）
receiver：IP -> TCP/UDP -> 对应进程      （分用 demultiplexing）

简单传输协议 Simple Transport Protocol

简单传输协议通常用于说明传输层协议的基本机制：基于连接 connection-oriented，使用服务原语 primitives 完成连接建立、数据传输和连接释放。

常见原语 primitives：

因特网传输层 Internet Transport Layer

传输层寻址 Transport Addressing

端口号 port number 用 16 bit 标识，因此范围为 0 ~ 65535。

套接字地址 socket address：

socket address = (IP address, port number)

更严谨地说，通信端点 endpoint 还要区分传输层协议：

endpoint = (transport protocol, IP address, port number)

TCP 和 UDP 的端口号空间 port number space 相互独立，所以同一台主机上可以同时存在：

TCP 53
UDP 53

操作系统先根据 IP 首部的协议字段 protocol field 区分 TCP/UDP，再在对应协议的端口空间中查找目的端口。因此同一个端口号可以分别被 TCP 和 UDP 使用而不冲突。

TCP 连接通常由四元组或五元组标识：

四元组：<local IP, local port, remote IP, remote port>
五元组：<protocol, local IP, local port, remote IP, remote port>

用户数据报协议 UDP User Datagram Protocol

UDP 特点

• 基于数据报 datagram。
• 无连接 connectionless，发送前不建立连接。
• 不可靠 unreliable，不保证交付、不保证按序、不提供重传。
• 支持单播 unicast、多播 multicast。
• 支持复用 multiplexing 和分用 demultiplexing。
• 在 IP 数据报服务基础上增加：端口寻址、校验和 checksum。
• 典型应用：DNS（Domain Name System）、SNMP（Simple Network Management Protocol）、实时音视频等。

UDP 数据报格式 UDP Datagram Format

UDP 首部 header 固定 8 bytes，UDP 数据报总长度字段为 16 bit，因此最大长度为 65535 bytes。

UDP 首部字段：

如果目标端口不可达，由 ICMP 发送端口不可达差错报文 port unreachable。

UDP 校验和 Checksum

计算 UDP checksum 时，需要在 UDP 数据报前添加 12 bytes 伪首部 pseudo header。如果数据部分不是偶数个字节，还要在尾部填充一个全 0 字节。然后对整个 UDP 序列计算每 16 bit 和的反码。

传输控制协议 TCP Transmission Control Protocol

TCP 特点

• 基于字节流 byte stream，传输基本单位是 TCP 报文段 segment。
• 面向连接 connection-oriented，传输前需要建立连接。
• 可靠 reliable、有序 in-order。
• 全双工 full-duplex。
• 只支持单播 unicast。
• 使用端口进行复用 multiplexing 与分用 demultiplexing。
• TCP 连接的端点 endpoint 可表示为 socket (host, port)。
• TCP 连接通常用四元组表示：(src IP, src port, dest IP, dest port)。

TCP 报文段格式 TCP Segment Format

TCP 首部最短 20 bytes。

常见字段：

控制字段 flags：

TCP checksum 计算时也要添加 12 bytes 伪首部 pseudo header。

TCP 可靠传输 Reliable Data Transfer

TCP 支持可靠传输的核心机制：

TCP 将应用层交给它的数据流划分为报文段，对字节 byte 编号。报文段的 seq 通常是该段第一个数据字节的编号。

SYN：控制位，表示请求建立连接、同步序号
ACK：控制位，表示确认号 ack 字段有效
seq：序号字段，表示本报文段发送方自己的序号
ack：确认号字段，表示“我下一次希望收到你的哪个序号”

TCP 连接建立 Connection Establishment

TCP 使用三次握手 three-way handshake 建立连接：

• 握手 1：Client -> Server SYN = 1, ACK = 0, seq = x, ack 无效

• 握手 2：Server -> Client SYN = 1, ACK = 1, ==seq = y==, ack = x + 1

• 握手 3：Client -> Server SYN = 0, ACK = 1, seq = x + 1, ==ack = y + 1==

关键点：

• ACTIVE OPEN：client 主动打开连接，发送 SYN，初始化 client 的 ISN。SYN 不携带数据，但消耗一个序列号。
• PASSIVE OPEN：server 被动打开连接，收到 SYN 后发送 SYN+ACK，初始化 server 的 ISN，并确认 client 的 ISN。SYN+ACK 不携带数据，但消耗一个序列号。
• Client ACK：client 确认 server 的 ISN。若 ACK 不携带数据，通常不消耗序列号。

考试要点： 在 TCP 全过程中，只有握手 1 和握手 2 的 SYN=1 在 TCP 全过程中，只有握手 1 的 ACK=0 握手 1 和握手 2 不能携带数据，只有 TCP 首部，但是仍要消耗一个序号 握手 3 如果不携带数据，就不消耗序号

TCP 数据传输 Data Transfer

进程在建立连接时就确定起始序号，数据传输过程中，每个字节对应一个序号。 TCP 传输时双方不断交换 SEQ 和 ACK：

发送方 SEQ：本报文段第一个数据字节的序号
接收方 ACK：期望收到的下一个字节序号 = 已收到对方 SEQ + data length

TCP 连接释放 Connection Termination

TCP 把一条连接看成两个方向的单向数据流，因此常用四次挥手 four-way handshake 分别关闭两个方向（双向确认结束）： 客户端进程 A ，服务器进程 B

• 挥手 1： A -> B：SYN=0, FIN=1, ACK=1, seq=y, ==ack=x==

• 挥手 2： B -> A：SYN=0, FIN=0, ACK=1, ==seq=x==, ack=y+1

• 挥手 3： B -> A：SYN=0, FIN=1, ACK=1, ==seq=x+n==, ack=y+1

• 挥手 4： A -> B：SYN=0, FIN=0, ACK=1, seq=y+1, ==ack=x+n+1==

• FIN = 1：finish，表示本方向已经没有数据要发送，请求关闭本方向连接。

• ACK = 1：acknowledgement，表示确认号字段有效。

• seq：本报文段发送方自己的序号。

• ack：期望对方下一次发送的序号。

考试要点：

• 在四次挥手中，只有挥手 1、挥手 3 的 FIN = 1。
• 挥手 1、挥手 3 即使不携带数据，也会消耗一个序号。
• 挥手 2 可以携带数据，因为 B 只是确认 A 不再发送，B -> A 方向还没关闭。
• 挥手 4 通常不能携带数据，因为 A -> B 方向在挥手 1 后已经关闭。
• SYN = 0 通常不再特别写出，因为连接释放阶段不再同步初始序号。

为什么是四次而不是三次：

TCP 是全双工 full-duplex 的。
A 说“我不发了”，不代表 B 也已经发完。
所以 A -> B 和 B -> A 两个方向要分别关闭、分别确认。

TIME_WAIT 与 2MSL：

• 主动关闭方进入 TIME_WAIT 状态，等待 2MSL 后才真正释放连接。
• 2MSL = 2 * Maximum Segment Lifetime，用于避免最后一个 ACK 丢失，也让旧连接中的迟到报文在网络中消失。
• 连接异常时可以发送 RST reset 标志复位连接。

TCP 超时重传时间 Timeout

TCP 需要根据 RTT 动态估计超时时间 timeout interval。

SampleRTT：某个报文段发出到收到对应 ACK 的时间
EstimatedRTT = (1 - alpha) * EstimatedRTT + alpha * SampleRTT
alpha = 0.125

DevRTT = (1 - beta) * DevRTT + beta * |SampleRTT - EstimatedRTT|
beta = 0.25

Timeout = EstimatedRTT + 4 * DevRTT

滑动窗口 Sliding Window

TCP 使用滑动窗口 sliding window 实现错误控制、流量控制和拥塞控制。

一个方向的数据传输涉及：

发送窗口 send window
接收窗口 receive window / advertised window
拥塞窗口 congestion window, cwnd

实际发送窗口：

send window = min(flow control window, congestion window)
            = min(rwnd, cwnd)

其中：

• rwnd receiver window / advertised window：接收方根据接收缓存大小通告，用于流量控制 flow control。
• cwnd congestion window：发送方根据网络拥塞情况维护，用于拥塞控制 congestion control。

流量控制 Flow Control

流量控制的目标：防止发送方发送过快，超过接收方接收缓存能力。

• 接收方在 TCP 首部的 Window size 字段中通告接收窗口。
• 发送方根据接收窗口限制发送窗口。
• 流量控制是端到端 end-to-end 的控制。

糊涂窗口综合症 Silly Window Syndrome

糊涂窗口综合症 Silly Window Syndrome 指发送端和接收端速度不匹配，导致网络中出现大量小包，报头开销大、有效数据少，传输效率低。

解决方法：

拥塞控制 Congestion Control

拥塞控制的目标：防止发送方发送过快，超过网络承载能力。

核心参数：

拥塞检测：

• 超时 timeout。
• 收到三个重复 ACK three duplicate ACKs。

拥塞控制总体思想：AIMD, Additive Increase Multiplicative Decrease，加性增、乘性减。

TCP 拥塞控制不是单独一种方法，而是一组配合使用的机制：

两个基本增长阶段：

发生拥塞后的典型处理：

• ssthresh 更新为当前 cwnd 的一半。
• 超时 timeout：cwnd 通常降为 1，重新慢启动。
• 三个重复 ACK：触发快重传 fast retransmit，不必等待超时，直接重传疑似丢失的段。
• 快恢复 fast recovery：将 cwnd 调整到 ssthresh 附近，然后进入拥塞避免，避免从 1 重新开始。

常考版本区别：

图像判断口诀：

• cwnd 指数增长：慢启动。
• cwnd 线性增长：拥塞避免。
• cwnd 直接降到 1：通常是 timeout。
• cwnd 大约减半但没有降到 1：通常是三个重复 ACK；在 TCP Reno 中还会进入快恢复。

应用层 Application Layer

应用与应用层

应用层是用户与网络的接口，定义了不同主机上的应用进程 process 如何发送和回应报文 message。

• 应用层通过 API, Application Programming Interface 访问传输层服务，典型接口是 socket。
• 开放域协议 open protocols：协议公开、可互操作，例如 HTTP、SMTP。
• 专有协议 proprietary protocols：由特定厂商或应用定义，例如 Skype。

C/S and P2P Application Architectures

应用层模型可分为

• Client-Server（C/S）

  客户从服务器请求数据，比如 WWW、FTP、Web service。

  服务器 server 通常具有固定 IP 地址，长期在线，负责响应客户请求。

  客户 client 通常使用动态 IP 地址，客户机之间一般不直接通信，而是通过 server 交流。

• P2P

  所有节点都可以发起连接，可以提供数据，也可以消费数据，比如 Skype。

DNS

将主机名和电子邮件目的地址映射到 IP 地址上。

• 主机名可映射到多个IP地址上
• 多个主机名也可以映射到一个IP地址上

域名系统 DNS, Domain Name System，是一种基于域的分层命名方案和分布式数据库系统。

• 主机名 hostname：便于人记忆的名称，例如 www.baidu.com。
• IP 地址：路由器能够识别的设备数字地址。

由3部分组成

• 名称空间Namespace
• 服务器Server
• 解析器Resolver（客户端）

树状命名空间

域是指这一命名空间中的子树，域名是从叶子节点到根的路径——唯一的名称。

全称域名 FQDN：Fully Qualified Domain Name

区域Zones：可以被直接管理的命名空间

授权Delegation：给区域设置一个命名服务器，可以管理主机名和子域

DNS服务器的层次结构

• Root Server
• Top-Level domain Server：顶级域名服务器
• Authoritative DNS servers：授权域名服务器

每个服务器都知道根服务器地址，每个服务器都知道其直接子节点的地址

使用方式

• 本地DNS服务器，是指主机上发送DNS请求时的首要目标

• 请求方式

  • 递归请求

    简单来说会从本地DNS服务器经过根服务器沿着链状传递请求和地址解析结果

  • 迭代请求（更常用）

    简单来说由本地DNS服务器直接进行多次查询，根据查询结果迭代查找下一个路由器

服务器的缓存机制可以减少负担，但每一个缓存项都存在TTL

DNS 数据库资源记录 resource record 结构：

(name, TTL, class, type, value)

常见记录类型：

优秀特点

• 层次授权：避免了中心化
• 冗余服务器：增强了鲁棒性
• Caching：减少了负载

FTP

文件传输协议 FTP, File Transfer Protocol。

C/S 模型，使用 TCP，共需要两个 TCP 连接。

• 端口21：控制连接，持久的
• 端口20：数据连接，非持久的，每次文件传输都要建立连接

服务器控制连接打开过程

• 打开21端口
• 被动等待客户进程发起连接请求
• 处理请求，并行开启数据连接
• 关闭数据连接，回到等待状态

数据连接建立过程（此时已经建立了控制连接）

• 客户端打开临时端口（ephemeral port）x
• 客户端发送PORT请求告知服务端x
• 服务端通过20端口与客户端x端口建立数据连接

匿名FTP：可使用匿名FTP登陆获取公共文件

• 用户名：anonymous

• 口令：guest或邮件地址

E-Mail and SMTP/POP/IMAP

三个主要组成部分

• 用户代理UA

  给用户提供发送和接收邮件的接口

• 邮件传输代理MTA

  邮件服务器，核心组件，发送和接收邮件

  可分为client MTA（发送端邮件服务器）和server MTA（接收端邮件服务器），

• 邮件访问代理MAA

  从邮件服务器取邮件，例如 POP3、IMAP。

SMTP

简单邮件传输协议 SMTP, Simple Mail Transfer Protocol，是 C/S 协议。

发送路径：

发送方 -> 发送方邮件服务器 -> 接收方邮件服务器 -> 接收方

SMTP 负责发送方到发送方邮件服务器、发送方邮件服务器到接收方邮件服务器，采用 TCP 端口 25，也可能使用 2525，负责邮件的 PUSH。

• 连接建立

  发信方定期扫描邮件缓存，如果有邮件，则使用 SMTP 的 25 端口号与接收方的 SMTP 服务器建立连接。建立完成后，接收方发送服务就绪，发送方发送 HELO 指令。

• 邮件传送

  发送方 SMTP 发送 MAIL 命令，若接收方准备好，则返回 250 OK，开始发送邮件内容。

  CRLF.CRLF 表示邮件内容结束。

• 连接释放

  SMTP 客户发送 QUIT 命令，服务器返回 221 服务器关闭，释放 TCP 连接。

POP3

邮局协议 POP3, Post Office Protocol version 3。

负责 PULL，用户代理向邮件服务器发送请求，获取邮箱内的邮件，采用 TCP 端口号 110。

两个阶段

• 认证（客户端与服务器之间需要身份认证）
• 下载

IMAP

因特网邮件访问协议 IMAP, Internet Mail Access Protocol，基于 TCP 协议。

• 用户可以在服务器上管理邮件，不一定把邮件全部下载到本地。
• 支持有连接和无连接的模式。

MIME

多用途 Internet 邮件扩展 MIME, Multipurpose Internet Mail Extensions。

• 用于发送非文本数据，例如图片、音频、附件等。
• 用于非 ASCII 码到 ASCII 码的转换，方便通过邮件系统传输。

WWW and HTTP

World Wide Web万维网

使用超文本传输协议（HyperText Transfer Protocol，HTTP）进行连接。

每个 Web 页由对象 object 组成，通常包含一个基本 HTML 文件，HTML 文件定义文本格式并引用其他对象。

几个概念

• Web

• Website：网页的集合

• Web browser：浏览器

• Web server：服务器

• URL（Uniform Resource Locator）：指定网页的资源，用/分割

  格式：

  text复制代码

  protocol://hostname[:port]/directorypath/resource
  

  

• Links：连接

• Hyperlink：超链接，

• HTML：超文本标记语言

HTTP

HTTP 用于访问万维网数据，定义了浏览器如何请求万维网文档。

使用 C/S 模型，采用 TCP 建立连接，默认端口为 80。

基本工作过程：

1. 客户端向服务器 80 端口初始化 TCP 连接，服务器接受客户端连接。
2. 客户端发送 HTTP 请求，服务器返回 HTTP 响应。
3. 释放 TCP 连接，或在持久连接中继续复用该连接。

报文有两类

• 请求报文

  分三部分：请求行，首部行和实体主体

  请求行的方法包括（GET、POST、HEAD、PUT、DELETE）

• 响应报文

可以分为

• 非持久 HTTP

  每个 HTTP 连接至多发送一个对象（包括网络图形等）。

• 持久 HTTP

  在 HTTP 响应后仍保持 TCP 连接，在一个连接内可以发送多个对象。

  又可以分为流水线和非流水线。对于流水线方式，客户可以连续发出对各个对象的请求而不必逐个等待响应。

HTTP 是无状态协议，不会保留客户机过去请求的任何信息。

DHCP

动态主机配置协议 DHCP, Dynamic Host Configuration Protocol，属于应用层协议，基于 UDP 协议。

功能：自动配置主机连接所需的网络参数。

• IP 地址
• 子网掩码
• 默认网关
• DNS 服务器 IP 地址
• 租约时间

常用端口：

典型过程 DORA：

Discover -> Offer -> Request -> ACK