应付期末考试而写，不详细的地方需要亲自去看书

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

---

---

1.1 因特网

因特网由硬件和软件构成

硬件

硬件由主机，通信链路，分组交换机构成

主机：也叫端系统，主要是运行各种网络应用程序，为用户提供服务

通信链路：连接因特网上各种设备，保证正常通信

• 光纤，铜缆，无线电，人造卫星
• 传输速率 = 带宽

分组交换机

• 由于不可能每对主机之间均连接通信链路，所以需要有中间点转发数据
• 转发数据的分组交换机：转发分组（数据块），包括链路层交换机和路由器

端系统通过因特网服务提供商ISP接入Internet：ISP互联

软件

在因特网上运行的网络应用程序

协议：在硬件的基础上提供控制数据传输的规范 TCP,IP,HTTP,FTP,PPP

• 一个协议定义了在两个或者多个通信实体之间交换的报文格式和次序，以及报文发送和/或接收一条报文或其他事 件所采取的动作
• 协议的书面文档，因特网标准：RFC：请求评论， IETF：因特网工程部

因特网能提供的服务：

• 为应用程序提供服务的基础设施：Web, VoIP, email, games, e-commerce, social nets
• 为应用程序提供编程接口（API）
  • 应用程序连接到因特网上的通道
  • 提供不同级别的服务选项：服务方式，服务质量

1.2 网络结构

网络边缘

构成：端系统(主机：客户端和服务器)、数据中心的服务器

接入网

将端系统连接到其边缘路由器的物理链路

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

方式

• 家庭：Modem拨号/ADSL拨号/HFC/FTTH/卫星
• 以太网/Wi-Fi
• 广域无线接入：3G/LTE/5G

Modem拨号

• 通过本地电话回路点对点连接ISP的拨号池（通常是路由器）
• 速度最高可达56kbps
• 无法实现在上网的同时拨打电话

DSL：数字用户线

• 下行/上行速率最高可达55Mbps/15Mbps
• 频分复用：0kHz—4kHz语音 4kHz—50kHz上行 50kHz—1MHz下行
• 带宽独享

HFC：光纤同轴电缆混合网络

• 下行/上行速率最高可达40Mbps/30Mbps
• 通过有线电视网络部署
• 带宽共享

局域网接入

• 公司/大学的局域网(LAN)将端系统连接到边缘路由器
• 以太网：通过共享或专用的链路来连接端系统和路由器，10Mbps、100Mbps、1000Mbps、10Gbps以太网

无线接入

• 共享的无线接入网络连接端系统和路由器：通过基站
• 无线局域网：802.11:最高1Gbps (802.11ac)
• 广域无线网：电信运营商提供：3G,4G,4G+,5G(802.16 WiMax)

物理媒体

物理媒体

• 导引型媒体：信号沿着固体媒体被导引
• 非导引型媒体：信号自由传播

导引型媒体

• 双绞线：两根互相绝缘的铜导线(3类即传统电话线10Mbps，5类100Mbps，6类1Gbps)
• 同轴电缆：双向传输
  • 基带：电缆上单信道、以太网
  • 宽带：电缆上多信道、HFC
• 光缆：在玻璃光纤传播光脉冲 ，每一个脉冲一比特。高速运行且低误码率(中继器相隔很远，不受电磁干扰)

非导引型媒体：

• 特点：通过电磁频谱传播信号；没有物理线路；双向传播；传播环境影响(反射，障碍物阻隔，干扰)

• 地面微波：45Mbps

• 无线局域网：2/11/54Mbps

• 无线广域网：3G/4G

• 卫星：可达45Mbps的信道（或多个较小的信导）；270ms端到端延迟

网络核心

电路交换网络

• 数据交换过程：建立连接——交换数据——释放连接
• 特性
  • 电路是一条连接(信道)，而链路是本可以通过复用手段容纳多条电路
  • 数据交换前需建立起一条从发端到收端的电路（预留资源）
  • 在数据交换的全部时间内用户始终占用端到端的固定传输信道
  • 交换双方可实时进行数据交换而不会存在任何延迟
• 如果一个电路独占整个链路，那么链路利用率太低
• 电路交换中的复用：时分复用TDM、频分复用FDM
  • 例 TDM为复用分时的个数，答案为0.5s+640k/(1536kbps/24) = 10.5s
    

分组交换网络

真正意义上的计算机网络必须满足

• 不是为了打电话，而是用于计算机之间的数据传送
• 能够连接不同类型的计算机
• 所有的网络结点同等重要，不能有特别重要的结点
• 必须有冗余路由
• 网络结构尽可能简单，能够可靠传送数据

路由器互联构建路由器网路

分组交换

• 数据截断划分成分组
• **分组交换机(链路交换机或路由器)**转发分组
• 使用链路最大传输速率传输

分组的好处：提高传输效率；提高传输质量；链路利用率高

分组方法：

• 发送端

  • 先把较长的报文划分成较短的、固定长度的数据段

  • 给每一个数据段前面添加上首部构成分组，依次发送给接收端

• 接收端

  • 把接收到的分组剥离首部还原成报文段
  • 报文段连接起来恢复为原报文

分组转发的路径

• 分组首部包含目的地址
• 路由器里有转发表 在转发表里检索目的地址获取转发的链路
• 转发表通过路由选择协议自动形成

分组传输模式：

• 存储转发模式：分组交换机将整个分组收下并存储，存储校验后，再发出去

分组交换网络特征

• 数据分成若干分组分别传送
• 不必预先确定分组的传输路径
• 交换结点均为共享结点，选择路径
• 存储/转发：要校验
• 断续(动态)分配传输带宽
• 网状拓扑结构——提高可靠性
• 主干线路常由高速链路构成

分组交换网络VS电路交换

• 每个用户获得大致相同带宽的情况下，分组交换比电路交换支持更多用户
  
• 用户较少的情况下，分组交换比电路交换获得更大的带宽
  
• 分组在各结点存储转发时因要排队总会造成一定的时延。当网络通信量过大时，这种时延可能会很大
• 各分组必须携带一定的控制信息（说明信息），从而带来额外开销
• 整个分组交换网的管理和控制比较复杂
• 结论
  • 若要连续传送大量数据，且其传送时间远大于呼叫建立时间，则采用在数据通信之前预先分配传输带宽的电路交换较为合适
  • 分组交换不需要预先分配传输带宽，在传送突发数据时可提高整个网络的信道利用率

网络的网络

端系统通过ISP连接到网络而ISP间必须互联，所以构建因特网非常复杂

网络应用的通信模型

• 客户/服务器模型(C/S)：客户使用服务，服务器提供服务
• 对等模型(P2P)：所有的主机同时承担服务器和客户机的双重身份

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

时延和丢包

传输时延和排队时延占大头

• 节点处理时延：校验、选择输出链路、毫秒微秒级别
• 传播时延：物理线路上传播的时间
  • d：物理链路的长度 s：传播介质的传播速度
  • d/s 很短可忽略
• 传输时延：将分组推向链路的时间
  • L：分组长度(bit) R:连接设备链路的速率(bps)或者链路带宽
  • N 条链路的传输时间 = N * (L/R)
• 排队时延：存储需要缓存，缓存过程中可能需要排队(等待前面的分组处理)
  • 取决于路由器的拥塞程度
  • 分组到达输入链路的速率 a 远超于输出链路的能力 R/L 时产生(流量强度 aL/R)
    • La/R ~ 0 平均排队时延很小，甚至为0
    • La/R < 0 时延较小，且会随时间推延而变小
    • La/R = 1 时延不会变化，具体数值取决于当时队列长度
    • La/R > 1 平均时延较大，且会随时间推延而趋于无穷
  • 队列满时丢包，丢包可能被重传或不重传

吞吐量

瞬时吞吐量，平均吞吐量

• 吞吐量 = min{Rc, Rs, R/10} （木桶原理）

  

1.5 协议层次及其服务模型

分层的优点：结构化使得系统组件更新更为容易，每一层对其他层透明

分层的缺点：冗余：功能重叠；信息关联：某层需要其他层的信息

协议层次

因特网协议栈

OSI	功能	TCP/IP	信息分组名
应用层	网络应用程序及他们的应用层协议留存的地方	HTTP,FTP,SMTP,DNS	报文
运输层	在应用程序进程之间通信	TCP,UDP	报文段
网络层	将数据报从源端传送到目的端	IP, ICMP	数据报
链路层	数据在网络相邻结点之间传输	以太网、WiFi、DOCSIS，PPP	帧
物理层	在线路上传播比特		比特

OSI参考模型：因特网没有表示层和会话层，因为可以由应用层实现

• 应用层: 支持网络应用 FTP, SMTP, STTP
• 表示层: 允许应用程序解释数据的含义，如：加密、压缩、特定机器的数据描述方法
• 会话层: 提供了数据交换的同步、定界、建立检查点和恢复的能力
• …

服务模型

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

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

协议

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

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

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

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

协议数据单元：协议数据单元是对等层次上传送数据的单位

服务数据单元服务数据单元是层与层之间交换数据的单位

网络体系结构：网络体系结构就是层和协议的集合

协议栈：一个特定的系统所使用的一组协议（每层一个协议）称为协议栈

协议和服务的关系:

i层传递到i-1层：加上i-1层的首部（如果有尾部也加，一般是链路层），称为i-1层PDU

i-1层传递到i层：去掉i-1层首部（如果有尾部也去，一般是链路层），把数据部分交给i层

---

第2章 应用层

2.1 应用层协议原理

网络应用需要：可以运行在不同端系统；通过网络交流

网路应用不需要：运行在网络核心设备上

网络应用架构

客户/服务器 C/S，对等网 P2P, 混合体系结构， C/S+P2P

c/s

服务器：

• 总是打开

• 拥有固定地址

• 缩放的数据中心

客户端：

• 与服务器通信
• 可能是间歇性连接
• 可能有动态的IP地址
• 客户端之间不能互相通信

p2p

• 不一定总在线
• 任意结点之间可以直接通信
• 结点的地址以及他们之间的连接可能随时发生变化
• 任何一方既提供服务又享受服务：自扩展 新的节点带来新的服务能力，同时也带来新的服务需求
• 节点之间是间歇性连接、地址也是变化的：管理非常复杂

进程通信

进程：在端系统运行起来的程序（操作系统术语）

• 一个程序可能产生多个进程
• 同一台主机上的不同多个进程之间的通信采用的是内部进程通信方式（OS决定）
• 不同主机之间的进程通信采用报文交换方式(应用层协议)

C/S：客户端进程：通信启动 服务端进程：等待连接

P2P：客户端进程 = 服务器进程

套接字Socket：每个网络应用进程都有一个属于自己的套接字，该套接字在整个因特网上独一无二

• 主机地址：标识该网络应用进程运行在因特网上哪一台主机上，通常使用32位的IP地址进行标识
• 端口地址：在该主机上标示该网络应用进程，通常使用16位的端口号进行标识
• 套接字长度48位 122.205.11.1：80
• 进程通过套接字来接收和发送报文

网路应用的所需服务

数据可靠传输、吞吐量、传输和反馈的实时性、安全性

传输层可提供的服务：前三者

• TCP

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

  • 可靠传输：在发送和接受进程之间

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

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

  • 不提供：实时性，最小带宽承诺

• UDP

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

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

安全性：TCP/UDP天生不具备安全性，安全套接字层SSL可以解决，SSL位语应用层和TCP之间

• 提供加密的TCP连接
• 数据的完整性检查
• 端点身份鉴别

2.2 Web应用和HTTP协议

Web应用

HTML：信息表达的协议

HTTP：信息传输的协议 http1.0 RFC 1945 http1.1 RFC2068

Web页面由一些对象组成，每一个对象都可以用URL定位 www.haha.com/cs/picture.gif

Web属于C/S模式

• 客户端：浏览器请求、接收、展示Web对象
• 服务器：Web服务器发送对象对请求进行相应

HTTP工作方式

• 客户端启动TCP连接(创建套接字)到服务器(默认端口 80)
• 服务器接收来自客户端的TCP连接
• http报文(应用层协议报文) 在浏览器 (http client)和Web服务器 (http server)之间进行交换
• 关闭TCP连接
• HTTP是“无状态”的，服务器不保留任何访问过的请求信息

HTTP1.0 非持久连接 取对象需要 2 RTT，浏览器可以同时打开多个并行的连接来改善性能

2RTT的来源：

HTTP1.1 持久连接

• 服务器在发送响应后，不再断开TCP连接，而是保持该连接，用于后续对象的传送
• 直至该连接“休息”了一个较长的时间后，方断开该连接
• 减少了对服务器端连接数的需要，从而减少了对服务器端套接字资源的占用，提高了服务器的负载能力
• 划分
  • 非流水线方式：一个对象传输完成才能传输下一个
  • 流水线方式：一次性发送所有请求，慢慢接收

HTTP请求报文格式

请求行	方法	空格	URL	空格	HTTP版本	回车换行
首部行1	首部字段名1	冒号	值	回车换行
…	…	…	…	…
首部行n	首部字段名n	冒号	值	回车换行
空行
实体主体	…

HTTP1.0定义方法

• GET：向服务器请求指定URL的对象
• POST：用于向服务器提交表单数据，也可以同时请求一个WEB页面；也使用GET方法发送表单数据以获取新的WEB页面
• HEAD：请求服务器返回一个响应报文，但是该报文中并不包含请求的对象。该方法常常用来进行故障跟踪

HTTP1.1新方法

• PUT：上传的文件放在实体主体字段中，目标路径由URL字段标明
• DELETE：删除URL字段中指定的文件
• 另一种上传数据的方法GET：将需要上传的数据放到URL中，如www.somesite.com/animalsearch**?monkeys&banana**

HTTP响应报文格式

状态行	版本	空格	状态编码	空格	短语	回车换行
首部行1	首部字段名1	冒号	值	回车换行
…	…	…	…	…
首部行n	首部字段名n	冒号	值	回车换行
空行
实体主体	…

常见HTTP响应状态码和短语

• 200 OK 请求成功, 被请求的对象在报文中
• 301 Moved Permanently 被请求的对象被移动过, 新的位置在报文中有说明
• 400 Bad Request 服务器不懂请求报文
• 404 Not Found 服务器上找不到请求的对象
• 505 HTTP Version Not Supported 服务器不支持请求报文使用的HTTP协议版本

Cookie

Web站点使用Cooke的目的

• 限制用户的访问
• 把内容和用户身份关联起来

Cookie技术的组成部分

• 在HTTP响应报文中有一个Cookie首部行
• 在HTTP请求报文中也有一个Cookie首部行
• 在用户的端系统中保留了一个Cookie文件，由用户浏览器负责管理
• 在Web站点有一个后端数据库

2.3 文件传输协议FTP

使用TCP协议传输数据，C/S模式，端口21/20

与http共同点：均TCP

与http不同点：

• FTP的控制信息是带外传送的，而HTTP的控制信息则是带内传送的。
  • FTP存在控制连接和数据连接两个并行连接
• FTP连接有状态，HTTP无状态：FTP会在整个会话期间维护用户的状态信息
  • 把用户帐户和控制连接联系起来
  • 追踪用户在远程目录树上的位置
  • 对活动着的用户会话的状态进行追踪，以限制FTP会话总数

2.4 因特网的电子邮件（略）

2.5 DNS

DNS概念

因特网的目录服务，用于IP和域名之间的转换

DNS是一个分布式数据库，由很多台DNS服务器按照层次结构组织起来

DNS运行在端到端系统上，且使用UDP协议（53号端口）进行报文传输，因此DNS是应用层协议

DNS以C/S的模式工作

DNS不直接和用户打交道，而是因特网的核心功能

假设A通过浏览器访问www.yahya.com/index.html

1. 浏览器将URL的域名抽取出来www.yahya.com，传给A主机上的DNS客户端
2. DNS客户端向DNS服务器发送一个包含域名www.yahya.com的查询请求报文
3. DNS服务器向DNS客户端送回包含对应IP地址的响应报文
4. DNS客户端将该IP地址传给浏览器
5. 浏览器向该IP地址所在的Web服务器发起TCP连接

单DNS服务器的弊端

• 单点故障的问题：一旦崩溃，因特网何以堪
• 数据的流通量：使得DNS服务器不堪重负
• 远程的集中式数据库：带来严重的延时
• 维护量巨大：DNS服务器不得不拼命的更新以适应因特 网上主机的增加与减少

真正实现

顶级域DNS服务器：负责顶级域名和所有国家的顶级域名解析工作，com，org，net，gov，uk，cb，edu

权威DNS服务器：属于某个组织的DNS服务器, 为组织的服务器提供一个权威的域名到IP地址的映射服务

本地DNS服务器：严格意义上，其并不属于DNS层次结构中的一层

• 每一个网络服务提供商都会提供一个本地DNS服务器，默认DNS服务器
• 当一台主机需要做一个域名查询的时候，查询请求首先被发送到本地域名服务器，本地域名服务器的行为就像一个代理，它会向域名的层次体系中进行进一步的域名查询

DNS解析

1. 发起请求使用递归查询，后续解析为迭代查询。负担交给本地DNS
   
2. 另一种纯递归查询，负担交给每一级
   

一旦 (任何) 域名服务器得知了某个映射, 就将其缓存

• 在一定的时间间隔后缓存的条目将会过期(自动消除)
• 顶级域DNS服务器通常被缓存在本地DNS服务器中
• 这样可以减少根DNS的负载

DNS可提供的服务

• 域名到IP地址的转换
• 主机/邮件服务器别名：为不好记的规范主机/邮件服务器提供一个容易记的别名
• 均衡负载：一个域名对应多个IP；DNS服务器在多个IP中进行轮转

DNS记录的格式

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

• type==A：name=主机名，value=ip地址
• type==NS：name=域(foo.com)，value=该域权威域名服务器的主机名
• type==NAME： name=别名， value=真名
• type==MX： value=与name相关的邮件服务器域名

DNS报文

查询和回答报文格式一致

2.6 P2P（略）

---

第3章 运输层

3.1 概述和运输层服务

运输层的功能：为不同主机上运行的应用进程之间提供逻辑通信

运输层协议的工作内容：

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

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

运输层和网络层的区别：

• 网络层: 不同主机之间的逻辑通信
• 运输层: 应用进程之间的逻辑通信

因特网上的运输层协议

• 用户数据报协议UDP(数据报)
• 传输控制协议TCP(报文段)

运输层所提供的服务

• 进程间数据交付
• 差错检测
• 可靠的数据传输
• 拥塞控制

3.2 多路复用和多路分解

端口

• 向下：让应用层的各种应用进程都能将其数据通过端口交付给运输层
• 向上：让运输层知道应当将其报文段中的数据通过端口交付给应用层相应的进程（或者线程）
• 端口是用来标志应用层的进程（或者线程）
• 16bit标志

套接字：TCP使用“连接”(而不仅仅是“端口”)作为最基本的抽象，同时将TCP连接的端点称为套接字

套接字和端口的关系：

这里容易出现概念混淆，按照下图解释

• 报文包含了应用层的完整的数据信息

• 报文段是传输层的信息单元，udp由于和ip基本提供的类似的服务，有时也叫数据报，但层次是不一样

• 数据报是网络层传输的传输基本单位，数据包时IP协议中完整的数据单元，由一个或多个数据报组成

• 帧是数据链路层的传输单元

• bit是在物理层的介质上直接实现无结构bit流传送的

多路复用：在数据的发送端，传输层收集各个套接字中需要发送的数据，将它们封装上首部信息后（之后用于分解），交给网络层

多路分解：在数据的接收端，传输层接收到网络层的报文后，将它交付到正确的套接字上；

报文段（数据报）的投送

• 主机收到IP包
  • 每个数据包都有源IP地址和目的IP地址
  • 每个数据包都携带一个传输层的报文段
    
  • 每个数据报文段都有源、目的端口号
  • 主机根据“IP地址＋端口号”将 报文段定向到相应的套接字

无连接的情形：

发送方A<–>接收方B

• 发送方：
  1. 应用层创建套接字new DatagramSocket(port_A)，ip不填的画默认为本地，将套接字传递到运输层
  2. 运输层为数据加上源端口号port_A以及目的端口号port_B，封装成报文段后交给网络层
  3. 网络层为报文段封装上源IP ip_A以及目的IP ip_B
• 接收方
  1. 主机拆开ip数据报得到报文段
  2. 检查报文段目的地址端口，将UDP报文段发送给端口号
  3. 如果要回复，从UDP报文中的获取相应的信息ip_A, port_A即可

面向连接的复用和分用

• TCP套接字用四元组表示(源IP地址，源端口号，目标IP地址，目的端口号)
• 接收方主机根据这四个值将报文段定向到相应的套接字
• 服务器主机同时支持多个并发的TCP套接字
• Web服务器为每一个客户连接都产生不同的套接字

TCP Socket

服务器：server_socket(server_ip, server_port, , )

1. 创建一个socket，用函数socket()；
2. 设置socket属性，用函数setsockopt(); * 可选
3. 绑定IP地址、端口等信息到socket上，用函数bind();
4. 开启监听，用函数listen()；
5. 接收客户端上来的连接，用函数accept()；
6. 收发数据，用函数send()和recv()，或者read()和write();
7. 关闭网络连接；
8. 关闭监听

客户端：client_socket([client_ip], [client_port], server_ip, server_port)

1. 创建一个socket，用函数socket()；
2. 设置socket属性，用函数setsockopt();* 可选
3. 绑定IP地址、端口等信息到socket上，用函数bind();* 可选
4. 设置要连接的对方的IP地址和端口等属性；
5. 连接服务器，用函数connect()；
6. 收发数据，用函数send()和recv()，或者read()和write();
7. 关闭网络连接

UDP Socket

服务器：server_socket(server_ip, server_port, , )

1. 创建一个socket，用函数socket()；
2. 设置socket属性，用函数setsockopt(); * 可选
3. 绑定IP地址、端口等信息到socket上，用函数bind();
4. 循环接收数据，用函数recvfrom();
5. 关闭网络连接；

客户端：client_socket([client_ip], [client_port], server_ip, server_port)

1. 创建一个socket，用函数socket()；
2. 设置socket属性，用函数setsockopt();* 可选
3. 绑定IP地址、端口等信息到socket上，用函数bind();* 可选
4. 设置要连接的对方的IP地址和端口等属性；
5. 发送数据，用函数sendto();
6. 关闭网络连接；

3.3 无连接传输：UDP

一个最简单的运输层协议必须提供：多路复用/多路分解；差错检测。实际上也就是和UDP提供的功能

UDP处理数据的流程

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

UDP的优势

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

采用UDP协议的应用：远程文件服务器(NFS)、流式多媒体、因特网电话、网络管理(SNMP)、选路协议(RIP)、域名解析(DNS)

UDP大量应用可能导致的后果：路由器中大量的分组溢出；显著减小TCP通信的速率，甚至挤垮TCP会话

使用UDP的可靠数据传输：在应用层实现数据的可靠传输；应用程序特定的错误恢复(增加了应用进程的实现难度)

UDP报文段的结构：

UDP差错检测

UDP的检验和：检测收到的报文段的“差错” (例如, 出现突变的比特)

• 发送方
  • 把报文段看成16bit一段的序列
  • 检验和：对报文段每一段1.求和(最高进位放在末位) 2.总和求反码
  • 校验和写入UDP检验和字段
• 接收方
  • 计算校验和，与发送方的检验和相加，全为1，没有检测出错误(不代表没错误)；不全为1，检测出错误

3.4 可靠数据传输的原理

可靠数据传输：数据可以通过一条可靠信道来传输。传输的数据不会受到损失或者丢失，而且所有数据都是按照其发送顺序进行交付。

rdt_send()：上层调用，产生一个分组(make_pkt()产生)，发送到信道(udt_send())

rdt_rcv()：当分组到达接收方时调用,从分组中取出数据(extract()), 将数据传输到上层(deliver_data())

rdt1.0

假设：底层信道完全可靠（不会产生错误比特，不会丢失分组），接收方和发送方的数据传输速率一致

rdt2.0

假设：分组比特可能受损，不会丢失

解决方案：

• 差错检测：接收方使用检验和checksum等方法，检验是否受损corrupt(),notcorrupt();

• 接收方反馈：接收方通知发送方是否受损(ACK NAK)

• 出错重传：发送方isNak(rcvpkt)则重传udt_send(sndpkt)

实现重传的方法：使用缓冲区缓存已发出但未收到反馈的报文段，接收方和发送方各一个报文段大小的缓存区就可

rdt2.1

假设：分组比特可能受损，ACK和NAK分组也可能受损，但都不会丢失

解决方案：

1. 增加足够的检验和比特，使得发送方不仅可以检测差错，还可以恢复差错。受损也可以恢复
2. (TCP)用法收到模糊的反馈，直接重传当前分组。但需要编号，只需要1bit区别是否在发新分组还是在重传即可

特殊情况理解（囊括了NAK，和ACK出错两种情况，注意点在接收方的状态）

发送方	接收方
[等待来自上层的调用0]
…
发送分组0[等待ACK或NAK 0]
	接收分组0，返回ACK（ACK出错）[等待来自下层的1]
模糊反馈重传分组0[等待ACK或NAK 0]
	接收到分组0，重新发送ACK[等待来自下层的1]
接收到ACK[等待来自上层的调用1]
…
发送分组1（分组1出错）[等待ACK或NAK 1]
	分组1检验出错，返回NAK[等待来自下层的1]
接收到NAK 1重传分组1[等待ACK或NAK 1]
	接收到分组1，返回ACK[等待来自下层的0]
接收到ACK[等待来自上层的调用0]
…

rdt2.2

假设与2.1一致，进行改进，合并状态转换条件

改进方案：

1. 只使用ACK（对 和 不对）
2. 通告不对：取消NAK，接收方对最后一个正确收到的分组发送ACK，且必须明确指出被确认的分组编号
3. 发送方收到重复的ACK按照NAK来处理：重传正确分组

特殊情况理解

发送方	接收方
[等待来自上层的调用0]
…
发送分组0[等待ACK0]
	接收分组0，返回ACK0（ACK出错）[等待来自下层的1]
模糊反馈重传分组0[等待ACK0]
	接收到分组0，重新发送ACK0[等待来自下层的1]
接收到ACK0[等待来自上层的调用1]
…
发送分组1（分组1出错）[等待ACK1]
	分组1检验出错，返回ACK0[等待来自下层的1]
接收到ACK0, 重传分组1[等待ACK1]
	接收到分组1，返回ACK1 [等待来自下层的0]
接收到ACK1[等待来自上层的调用0]
…

rdt3.0

假设：分组比特可能受损，确认分组也可能受损，也可能丢失

目前已经有了重传的方法，但是需要判断丢包的方法

解决方案：丢包超时重传

特殊情况理解（发送分组丢失和确认分组丢失）

发送方	接收方
[等待来自上层的调用0]
…
发送分组0，计时器开始计时[等待ACK0]
	接收分组0，返回ACK0（丢失）[等待来自下层的1]
计时增加[等待ACK0]
…[等待ACK0]
超时重传分组0，重新计时[等待ACK0]
	接收到分组0，重新发送ACK0[等待来自下层的1]
接收到ACK0计时停止[等待来自上层的调用1]
…
发送分组1(丢失)计时器开始计时[等待ACK1]
计时增加[等待ACK1]
…[等待ACK1]
超时重传分组1，重新计时[等待ACK1]
	接收分组1，返回ACK1[等待来自下层的0]
接收到ACK1计时停止[等待来自上层的调用1]
…

特殊情况理解（过早超时）

发送方	接收方
[等待来自上层的调用0]
…
发送分组0，计时器开始计时[等待ACK0]
	接收分组0，返回ACK0(a)（发送时间比超时阈值长）[等待来自下层的1]
计时增加[等待ACK0]
…[等待ACK0]
超时重传分组0，重新计时[等待ACK0]
	接收到分组0，重新发送ACK0(b)[等待来自下层的1]
接收到ACK0(a)计时停止[等待来自上层的调用1]
…
发送分组1，计时器开始计时[等待ACK1]
接收到ACK0(b),发送分组1
…

流水线技术

rdt3.0性能低下

1次RTT却只发送8kb

原因:停等操作

解决方案：流水线技术，允许发送方一次发送多个分组而无需等待确认

• seq序号0，1不够，需要扩大序号范围
• 发送方最低限度应当能缓存那些已发送但未被确认的分组
• 接收方或许需要缓存已经正确接收的分组
• 缓存的量和序号长度有关

分组交换网路是多个主机，这里是两个主机，注意区别

流水线技术工作原理

• 分组首部用k-比特字段表示序号
• 未被传输的和已被传输还未确认的分组的序号范围可以看作是一个在序号范围内大小的为N的窗口
• 

流水线技术中的丢失重传问题需要解决

Go-Back-N(GBN)协议：其后全部分组全部重传

解决方案

• ACK(n):接收方对序号n之前包括n在内的所有分组进行确认——“累计确认ACK”
• 允许发送方能且只能连续发送n个数据包，若窗口大小为n，同时，窗口中未被确认的分组数不能超过n
• 对所有已发送但未确认的分组统一设置一个定时器，从一次流水的最“老”分组开始计时
• 超时(n): 重传分组n和窗口中所有序号大于n的分组
• 重复的分组丢弃重发（出现超时重传）
• 接收的分组失序（有分组丢失，后面的分组却正确到达）
  • 丢弃，接收方不缓存
  • 重发按序到达的最高序号分组ACK(重发该序号以后的分组)

特殊情况理解：假设窗口大小为4

考虑极端情况，发送窗口的所有分组都正确接收，但ACK都丢失，无法前移；下一次移动接收窗口移动到下一轮第一个分组。 那么发送窗口+接收窗口 <= k位bit最大的表示空间

由于接收窗口 = 1， 那么有 N + 1 <= 2^k N = 发送窗口大小

发送方	接收方
发送分组0，开始计时
发送分组1	接收分组0发送ACK0
发送分组2(丢失)	接收分组1发送ACK1
发送分组3
等待…	接收分组3，丢弃，发送ACK1
…
接收ACK0,发送分组4，重新开始计时
接收ACK1,发送分组5，重新开始计时	接收分组4，丢弃，发送ACK1
…	接收分组5，丢弃，发送ACK1
…
超时，发送分组2，开始计时
发送分组3	接收分组2发送ACK2
发送分组4	接收分组3发送ACK3

选择重传(SR)协议：仅重传该分组

解决方案：

• 发送方

  • 从上层收到数据，如果下一个可用于该分组的序号在窗口内，则将数据打包并发送

  • 为每一个分组定义定时器，重传分组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)
  • 其他情况 忽略该分组

特殊情况理解

发送方	接收方
发送分组0，窗口0123
发送分组1，窗口0123	接收分组0，交付，发送ACK0，窗口1234
发送分组2(丢失)，窗口0123	接收分组1，交付，发送ACK1，窗口2345
发送分组3，窗口0123，窗口满
等待…	接收分组3，缓存，发送ACK3，窗口2345
…
接收ACK0,发送分组4，窗口1234
接收ACK1,发送分组5，窗口2345	接收分组4，缓存，发送ACK4，窗口2345
分组2超时，重发分组2，窗口2345	接收分组5，缓存，发送ACK5，窗口2345
接收ACK3，窗口2345，窗口满	接收分组2，上交，发送ACK2，窗口6789
…
接收ACK2，发送分组6，窗口6789
…

窗口大小

接收端的滑动窗口<=序号空间大小的一半 2^k-1

假设序号字段长k位	GBN	SR	TCP
正常发送分组i	接收方回ACKi（累计确认）	接收方回ACKi	接收方回ACKi+1（累计确认）
计时器	最早分组	每个	最早分组
分组i超时重传	所有i及窗口中在i之后的	分组i	分组i
接收分组i失序	丢弃，发送最近已确认ACK	接收缓存，发送ACKi	接收缓存，发送最近已确认ACK(3个会触发快速重传)
发送窗口移动	收到ACKi,sendBase==i，sendBase++	收到ACKi,sendBase=i，sendBase=第一个未确认	收到ACKi,i>sendBae，sendBase=i
接收窗口移动		如果不失序，则将序号连续的分组上交，并移动到第一个未接收
发送窗口大小	<=2k-1
接收窗口大小	1	<=2k-1

3.5 面向连接的传输：TCP

TCP的特点

• 面向连接：TCP连接仅存于端系统，中间路由器对此毫不知情
• 全双工服务：课双向同时传输
• 点对点连接：仅存在于两个端系统之间
• 三次握手：建立连接，协商参数
• 可靠的字节流：最大报文段长MSS，典型值1460 = MTU（最大传输单元，以太网1500）-40链路层首部

TCP报文首部结构

• 端口：各2字节。端口是运输层与应用层的服务接口。运输层的复用和分用功能都要通过端口才能实现
• 序号：4字节，TCP数据流每一个字节都有序号，序号字段是指本报文段发送数据的第一个字节的序号
• 确认号：4字节，是期望收到对方的下一个报文段的数据的第一个字节的序号

主机A	主机B
发送Seq=42,ACK=79, data=“foo”
	发送Seq=79,ACK=43, data=“foo”
发送Seq=43,ACK=80, data=“bar”

• 首部长度：4bit，指示以字为单位的长度；为空则TCP典型首部长度20字节
• 保留：6bit，今后使用，目前为0
• 紧急URG：1时，此报文段中有紧急数据，尽快传送
• 确认ACK：1时，确认号才有效
• 推送PSH：1时，尽快交付，不等缓存填满
• 复位RST：1时，TCP出现严重差错，必须释放连接重连
• 同步SYN：1时，表示连接请求或连接接收报文
• 终止FIN：1时，表明报文段发送端已经发送完，可以释放连接
• 窗口：2字节，控制对方发送的数据量单位为字节，TCP一端根据此端缓存空间大小确认接收窗口大小，然后通知对方以确定对方的发送窗口的上限
• 检验和：2字节，检验和检验包括首部和数据还要在TCP报文段前加上12字节伪首部
• 紧急指针：2字节，指出本报文段种紧急数据的最后一个字节序号
• 填充：为了4字节整数倍

MSS是TCP报文段种的数据字段的最大长度。MSS+首部长度=TCP整个报文段长度

TCP超时设置

至少大于RTT，但RTT变化，太短的话又会造成不必要的重传，太长对丢包反应太慢

类型	简单解释	公式	参考值
SampleRTT	样本RTT
EstimatedRTT	估计RTT	EstimatedRTT=(1-α)×EstimatedRTT+α×SampleRTT	α=0.125
DevRTT	样本与估计偏差	DevRTT=(1-β)×DevRTT+β×|SampleRTT-EstimetedRTT|	β=0.25
TimeoutInterval	估算的RTT	TimeoutInterval=u×EstimatedRTT+v×DevRTT	u=1 v=4

可靠的TCP传输

ip协议不可靠，TCP采用了前文提到的的可靠传输的方法

差别

• TCP编号采用按字节编号，而非按报文段编号
• TCP仅采用唯一的超时定时器：减少定时器开销

解决方案

• 从应用程序接收数据
  • 将数据封装入报文段中，每个报文段都包含一个序号，序号是该报文段第一个数据字节的字节流编号
  • 启动定时器， 超时间隔为计算的TimeOutInterval
• 超时
  • 重传报文，重启定时器
  • 超时间隔×2：若持续传输分组，会加剧拥塞；指数增长；完成了形式受限得拥塞控制
  • 超时间隔重新计算，收到上层应用的数据，收到对未确认数据的ACK
• 收到ACK：如果是对未确认过的报文段的确认，更新SendBase，如果当前还有未确认的报文段重启定时器

特殊情况理解

ACK丢失而重传

主机A	主机B
发送Seq=92, 8bytes
	发送确认ACK=100(丢失)
等待…
超时重传Seq=92, 8bytes
	发送确认ACK=100

超时过短而重传（累计确认避免了ACK100重传

主机A	主机B
发送Seq=92, 8bytes
发送Seq=100, 20bytes
	发送确认ACK=100
	发送确认ACK=120
等待…
超时重传Seq=92, 8bytes
接收ACK=100,SendBase=100	重复发送确认ACK=120（累计确认）
接收ACK=120,SendBase=120
等待…
接收ACK=120,SendBase=120

介绍

TCP快速重传

新增重传条件，不仅仅取决于Timeoutinterval

• 超时周期往往太长：增加重发丢失分组的延时
• 发送重复的ACK检测丢失报文段：发送方常常要连续发送连续报文，如果中间有一个报文丢失，因为TCP累计确认机制，接收方会反馈同一个ACK多次
• 如果连续接收到3个冗余ACK，发送方重传响应数据

主机A	主机B
发送Seq=92, 8bytes
发送Seq=100, 20bytes（丢失）	发送确认ACK=100
发送seq=120，20bytes	发送确认ACK=100
发送seq=140，20bytes	发送确认ACK=100
等待…	发送确认ACK=100
接收ACK=100,SendBase=100
（冗余1）接收ACK=100,SendBase=100
（冗余2）接收ACK=100,SendBase=100
（冗余3）接收ACK=100,SendBase=100，发送Seq=100, 20bytes

TCP流量控制

背景

• TCP接收方有一个缓存，所有上交的数据全部缓存在里面
• 应用进程从缓冲区中读取数据可能很慢

目标：发送方不会由于传得太多太快而使得接收方缓存溢出

解决方案：接收方在反馈时，将缓冲区剩余空间的大小填充在报文段首部的窗口字段中，通知发送方

窗口值计算

发送方持续向接受方发送只有一个字节数据的报文段，目的是试探

为了避免接收方缓存满了且恰好接收方不发送数据给发送方后，因为窗口值始终没有更新而再也不发的情况

TCP连接

三次握手连接

主机A	主机B
SYN比特=1，SEQ=x
	SYN比特=1,ACK比特=1,SEQ=y,ACK=x+1
ACK比特=1，SEQ=x+1,ACK=y+1
请求数据（可以与第三次握手无间隔发送）

四次挥手

主机A	主机B
FIN比特=1，SEQ=x
	ACK比特=1,SEQ=y,ACK=x+1
	通知主机B进程，等到进程接收结束…
	…
	FIN比特=1，SEQ=y, ACK=x+1
ACK比特=1，SEQ=x+1, ACK=y+1

3.6 拥塞控制原理

情景1

• 两个发送方，两个接收方
• 一个具有无限大缓存的路由器
• 没有重传
• 链路容量为R

情景2

• 一个具有有限缓存的路由器
• 发送方对丢失的分组进行重传，理想情况是丢包才重传
• 设计期望λ_int=λ_out
• 延迟到达的分组使得λ_int`>λ_out

拥塞的开销

• 重传以补偿因为缓存溢出而丢失的分组
• 发送方在遇到大时延时所进行的不必要重传会引起路由器转发不必要的分组拷贝而占用其链路带宽

情景3

• 四个发送方，每个主机都有相同的λ_i值
• 多条路径
• 超时/重传

拥塞开销新增：当分组被丢弃时，“上游”传输容量全部浪费

拥塞崩溃

拥塞控制方法

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

3.7 TCP拥塞控制

TCP拥塞控制为端到端拥塞控制

• 每个发送方自动感知网络拥塞程度
• 发送方根据感知的结果限制外发的流量：拥塞则减速，没有拥塞则加速

拥塞窗口

• LastByteSent-LastByteAcked<=Congwin
• rate=Congwin/RTT byte/s
• 发送端窗口 <= min{CongWin, RcvWin}

TCP拥塞控制算法

阶段	操作(门限值ssthresh,拥塞窗口CongWin)
初始	ssthresh=典型值32KB，CongWin=1MSS
慢启动	每个ACK，CongWin+=1MSS
拥塞避免	每个RTT，CongWin+=1MSS
超时	ssthresh>>=1,CongWin=1MSS
3个冗余ACK	ssthresh>>=1,CongWin>>=1,CongWin+3MSS
快速回复	每个冗余ACK，CongWin+=1MSS，直到收到新ACK，CongWin=ssthresh

• 慢启动

  • 建立连接时，CongWin = 1 MSS
    • 例如，MSS = 500bytes RTT = 200 msec
    • rate = 500 * 8 / 200 * 1000 = 20kbps
  • 可用带宽 >> rate ：有较大增长空间
  • 连接初始阶段，指数增长，每个ACK CongWin += 1 MSS
  • 直到CongWin == 门限值（进入拥塞避免） 或 超时拥塞 或3个冗余ACK事件（进入快速重传）

• 拥塞避免

  • 窗口线性增长：每个RTT CongWin += 1MSS
  • 直到超时拥塞 或3个冗余ACK（进入快速重传）

• 若超时

  • 门限值ssthresh = Congwin/2（初始ssthresh = 65KB）
  • CongWin = 1 MSS
  • 窗口指数增长，超过门限值后线性增长

• 若收到三个冗余ACK

  • 门限值ssthresh = Congwin/2（初始ssthresh = 65KB）
  • CongWin = CongWin / 2 + 3MSS
  • 是否进行快速恢复,不进行的话直接进入拥塞避免

• 快速恢复

  • 每收到一冗余ACK CongWin += 1 MSS（第4，5，6个冗余ACK）
  • 直到收到一个新的ACK， CongWin = 门限值，重新拥塞避免。

主机A	主机B
seq=10，data=20bytes
	ack=30
…
seq=30，data=20bytes
seq=50，data=20bytes	ack=50
	ack=70
…
seq=70，data=20bytes
seq=90，data=20bytes
seq=110，data=20bytes
seq=130，data=20bytes

TCP吞吐量

假设：

• 因为慢启动指数增长，时间很短，忽略；

• 假定丢包时间发生时窗口大小为W， 此时吞吐量为W/RTT

• 丢包事件发生后，窗口大小W/2，吞吐量为W/2RTT

• 宏观且高度理想吞吐量在[W/2RTT, W/RTT]之间线性变换，平均吞吐量为3W/4RTT

吞吐量又是丢包率(L)的函数 1.22MSS/(RTT*L^1/2)

TCP拥塞控制的公平性分析

目标：K个TCP， 平均速率为R/K

从最靠下的点开始，会不断向交点收敛

UDP公平性：多媒体不采用TCP而用UDP，不希望拥塞控制控制速率，恒定速率传输音频数据，可以容忍丢包

TCP公平性：无法阻止应用在两个主机之间建立多个并行的连接

• R的链路支持9个并发连接，1个应用1个连接，应用得到R/10的速率；1个应用11个连接，应用获得大于R/2的速率

---

第4章 网络层

4.1 网络层概述

目标：实现主机到主机的通信

地位

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

主要功能

• 选路：在全局范畴为主机之间的通信进行选路，选路的结果反映为分组交换机上的转发表
• 转发：分组交换机上的网络层根据转发表以及分组头部信息，将分组向适当链路进行转发

分组交换机

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

服务

• 确保交付：确保分组最终到达目的地
• 具有时延上界的确保交付：时延上限内交付
• 有序分组交付：以发送顺序到达
• 确保最小带宽：以低于特定比特率速率传输，分组不会丢失且会在预定时延内到达
• 确保最大时延抖动：连续分组间隔时间不超过特定值
• 安全性服务：机密性、完整性和源鉴别
• …

4.2 路由器工作原理

路由器两个关键组成：路由选择、分组转发

输入端口

线路	输入端口物理层处理	输入端口链路层处理	输入端口网络层处理	交换结构
	比特流级接受	链路处理(协议、拆封)	网络层处理，排队查表转发

最长前缀匹配：查找给定目标地址的转发表项时，请使用与目标 地址匹配的最长地址前缀

转发表示例

目的地址范围	链路接口
11001000 00010111 00010*** ********	0
11001000 00010111 00011000 ********	1
11001000 00010111 00011*** ********	2
其他	3

11001000 00010111 00010110 10100001 去 0接口

11001000 00010111 00011000 10101010 去 1接口

输入端口排队

• 如果数据报到达的速度超过了输入端口将数据报转交给交换结构的速度，则后到的分组会暂时阻塞
• 输入缓冲区溢出可导致排队时延和丢包

交换结构

经内存交换、经总线交换、经内联网络交换

经内存交换

• 在输入端口和输出端口之间的交换是在CPU（路由处理器）的直接控制下完成的
• 分组被拷贝到系统内存中，CPU提出报头中的目标地址，查找路由表中的输出接口，将数据包拷贝到输出接口
• 转发速度受限于内存的带宽（吞吐量<带宽/2）
• 一次转发一个分组

经总线交换

• 输入端口经一根共享总线将分组直接传送到输出端口
• 总线交换的问题：交换速度受限于总线的带宽
• 一次一个分组：一次多个分组，会使得链路上的信号冲突，导致数据损坏
• 对于运行在接入网或企业网的路由器，通过总线交换的转发速度是足够的。(区域网和主干网则不行)

经内联网络交换

• 克服总线带宽限制
• 设计先进：将长度变化的IP分组分片成固定尺寸的信元，通过交换结构对信元进行转发

输出端口

缓存管理：当交换结构将分组交付给输出端口的速率超过输出链路速率时

调度原则：在数据报队列中选择数据报进行传输

• 先来先服务FIFO
  • 队列满，丢弃策略：丢尾部、按优先级丢弃、随机丢弃
• 优先级队列：发送最高优先级排队数据包
  • 多个类，具有不同的优先级 类别可能取决于标记或其他首部信息，例如 IP、端口等
• 循环调度RR：也是多个类
  • 循环扫描不同类的队列，轮流给每个类发送数据包（如果有可用的数据包）（轮询）
• 加权公平排队WFQ：类似RR排队
  • 每个类在每个周期中获得一定数量的服务（根据权值）

分组丢弃策略

• 被动队列管理
  • 弃尾策略
  • 删除一个或者多个已排队分组
• 主动队列管理——随机早期检测RED
  • 随时计算平均队列长度avgth
  • 最小阈值minth、最大阈值maxth
  • avgth小于minth ，允许分组入列
  • avgth大于maxth ，分组被标记或丢弃
  • avgth在minth和maxth之间，按照概率标记或丢弃分组

交换结构	输入端口网络层处理	输入端口链路层处理	输入端口物理层处理	线路
	网络层处理，排队查表转发	链路处理(协议、拆封)	比特流级输出

输入端口排队

• 当通过交换结构到达的分组速率超过了输出链路的速率时，需要对分组进行缓存
• 输出端口缓冲区溢出会导致分组的排队和丢失

路由器拥塞解决

缓存区设置

• RFC 3439： B = RTT × R
• 最近理论和试验 对有N条TCP连接的链路 B = RTT × R / N^1/2

4.3 网际协议

网络层协议套件：选路协议、IP协议、ICMP协议

• 选路协议：路径选择，RIP OSPF BGP

• IP协议：编址规则、数据报格式、分组处理规则

• ICMP：错误报告、路由器信令

IP数据报

• 版本号：4bit，IP版本号，4为Ipv4，6为Ipv6
• 首部长度：4bit，以四个字节为单位，值为5表示首部20个字节
• 服务类型：1字节，期望获得服务类型，现在基本不用为00H
• 总长度：2字节，意味着最大IP分组总长度为65535，那么IP可封装的最大数据：65535-20(最短首部)
• 标识：2字节，标识一个IP分组
• 标志：3bit
  • 保留
  • DF：为1时，禁止分片
  • MF：为1时，该数据报不是最后一片
• 片偏移：13bit，片偏移以8字节为单位
• TTL：1字节，指示IP分组可以通过的路由器数，TTL=0，丢弃分组
• 协议：1字节，指示是哪一个运输层协议的数据报，6为TCP，4为UDP
• 首部检验和：2字节对首部进行差错检测，每一跳都需要计算并校验
• 源地址，目的地址：各4字节，标识主机IP或路由器接口IP

IP分片和重组

• 链路具有MTU(最大传输单位)属性，由链路层最大帧的限制决定
• 大IP数据报会被分片
  • 重组只在目的主机进行
  • 数据报首部：标识、标志、片偏移字段用于目的主机对接收的分片进行重组
• 举例解释
  • 同一个分组，不同分片ID相同 ID = 100
  • 前两个MF = 1, 不是最后一片，最后一个分片MF = 0
  • 第一个FO = 0，第二个FO = 此分片传输的第一个字节的序号/8 = 1480/8 = 185，第三个同理

IPv4

32位主机或路由器的接口标志符

接口：连接主机，路由器之间的物理链路

• 一般说来，路由器有多个接口
• 主机也有可能有多个接口
• IP 地址只和接口有关，而与主机、路由器却没有太多关联

IP地址的结构： 高位(子网号)+低位(主机号)

子网：设备接口具有相同子网号，能够直接互访，无需中间路由器

	网络号Net-id	主机号host-id
A	0*******	******** ******** ********
B	10****** ********	******** ********
C	110***** ******** ********	********

D	1110	**** ******** ********
E	11110	*** ******** ********

同一局域网下主机和路由器的IP地址的网络号必须一样

路由器总具有2个或2个以上的IP，每个接口的网络号不同

子网划分

从主机号借位 为子网号

作用：对外隐藏子网的存在，对内指示网络号和子网号的位置

获得方法：通过在网络号的子网号相应的位置全置1，主机号相应的位置 全置0，即可得到子网掩码

引入子网掩码后的寻址

• 采用子网掩码后，路由器的寻址过程将演变成一个两级寻址过程
• 检查分组目的IP地址中的网络号：若网络号不是本网络，则从路由表中找出相应的转发结点地址将其转发
• 检查子网号：当网络号是本网络时，路由器将检查子网号，向相应的子网转发

例

H1先检查是否与H2属于同一网络，属于同一网络则直接链路交付；否则交给R1，逐项检查路由表

• (128.30.33.13 & 255.255.255.128) != (128.30.33.138 & 255.255.255.128)
• 查路由表找到(128.30.33.138 & 128.30.33.128) == 255.255.255.128 跳1

超网：有多个网络号的情况下可以构造超网满足需求

CIDR

背景：地址空间的利用率低，地址空间面临耗尽（一个B类网址可以容纳65K台主机，但可能被一个只有2K台主机的单位占据）

CIDR意思就是无类别域间路由，就是在区域之间（路由器可以把网络分成多个区域）使用不按ABCDE类划分的路由，主要作用就是把多个路由（有类路由）汇总成一个无类路由，这样可以减少路由表条目，起到优化路由表的作用，从而减少路由设备的负担，提高路由表查询速度，相对提高网络性能。

CIDR编址格式

• IP地址：网络地址+主机号
• 斜线记法：192.168.0.1/24
• 简写记法：10.0.0.0/10 = 10/10

CIDR也是最长前缀匹配

主机获取IP方法：手工配置 或 DHCP 动态主机配置协议

DHCP（应用层）

• 允许主机在加入网络时动态地从网络服务器中获取其网络地址
  • 能够在使用过程中更新地址
  • 允许地址重用（地址持有）
  • 支持移动用
• 获取过程（均为广播UDP）
  • 客户机请求IP（客户机发DHCPDISCOVER广播包）；
  • 服务器响应（服务器发DHCPOFFER广播包）
  • 客户机选择IP（客户机发DHCPREQUEST广播包）
  • 服务器确定租约（服务器发DHCPACK/DHCPNAK广播包）。

DHCP还能获取网关、DNS、子网掩码

NAT(网路层×运输层)

目标：本地网络只要使用一个IP地址就可以和外部网络相连

• 不需要从 ISP处获得大批IP地址：所有设备可以使用同一个 IP地址
• 可以在不通知外部网络的情况下改变内网主机的IP地址
• 即使改变了ISP也无须改变内网主机的IP地址
• 内网主机对外网主机而言是不可见的、不可寻址的。 (这也算是一项安全措施)

解决方案

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

NAT本地地址：10/8, 172.16/12 192.168/16

静态NAT：一个本地地址对应一个全球地址

动态NAT：一个全球地址对应多个本地地址

端口NAT：一个本地地址的端口对应到一个全球地址的端口

争议

• 端口号是用于进程编址的，而不是用于主机编址的
• 路由器仅应当处理高达第三层的分组
• NAT协议违反了端到端原则，即主机彼此应相互直接对话，节点不应介入修改IP地址和端口号

应使用IPv6来解决IP地址短缺问题

通信问题

客户端希望与10.0.0.1服务器通信

1. 采用端口NAT，在路由器中静态的为服务器配置一条记录(123.74.29.7, 80) (10.0.0.1, 80)
2. 通用即插即用UPnp：内部主机通过IGD协议了解公共IP地址，主动向路由器注册/移除映射记录，即内部主机主动通过某种渠道向外部应用程序公开（适用于P2P）
   
3. 中继：内网中程序将自己的映射发给中继服务器，形成在线用户列表；通信时，客户端向用户列表中的用户发出通信，通信请求由中继转发，当用户接收后，两者可以直接通信，不再经由中继服务器

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V4iD03bY-1640777135512)(C:/Users/Lenovo/AppData/Roaming/Typora/typora-user-images/image-20211227160458610.png)]

ICMP

• 用于主机、路由器、网关之间交换网络层信息
  • 错误报告：如主机、网络、端口、协议不可达等。
  • 回声请求/回答 (用于ping应用程序)
• 从体系结构而言，位于网络层
• ICMP消息：包括一个类型字段和一个编码字段
• ICMP 报文的种类有两种，即ICMP差错报告报文和ICMP询问报文

IPv6

Ipv4的问题

• 地址空间消耗很快
• 首部长度不定（20-40字节），中间结点（路由器）需要消耗相当资源用于分组处理
• 缺少QoS：抖动控制
• 安全性不够高

IPv6数据报的格式

• 无检查和，中间结点无需计算
• 中间结点不再负责分片和重组，由端结点负责
• 首部长度固定，加速中间结点转发速度

IPv4→IPv6

双栈技术：一段链路上，如果源和目标均支持IPv6，则使用IPv6进行通信

• 一段链路上，如果源和目标均支持IPv6，则使用IPv6进行通信
• 如果任一方不支持IPv6，则使用IPv4进行通信
• 可能会出现信息的丢失

4.4 路由选择算法

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

源路由器：源主机的默认路由器

目的路由器：目标主机的默认路由器

选路算法的目的：给定一组路由器以及连接路由器的链路，从中找到一条从源路由器到目标路由器合适路径

选路算法分类：

• 根据信息是全局性还是分散式的进行分类
• 根据信息是静态还是动态的进行分类
  • 静态选路算法
    • 随着时间的流逝，路由的变化非常缓
  • 动态选路算法
    • 路由信息可以更快地发生变化
    • 周期性的更新
    • 可以响应拓扑或链路费用的变化
• 根据是否对负载敏感进行分类
  • 负载敏感算法：链路费用会动态地变化以反映出链路的当前状况
  • 负载迟钝算法：链路费用不明显地反映链路的当前状况

全局性还是分散式

• 全局选路算法

  • 所有路由器都知道整个网络拓扑图以及链路的费用信息
  • 链路状态算法 Dijkstra(ospf)

• 分散式选路算法

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

LS

可能出现的问题

假设：(z->w,1), (x->w, 1), (y->w, e)

1. 开始y两套路都可以选，y决定走xw，导致xw间负载变为e+1, xy间负载e
2. 重新计算路由，x决定走xyzw路，y决定走zw路，z不变，导致图中左部路线也负载过重
3. 重新计算路由，x决定走xw路，y决定走yxw路，z决定走zyxw，导致图中右部路线也负载过重
4. 重新计算路由，x决定走xyzw路，y决定走zw路，z决定走zw，导致图中左部路线再次负载过重

造成震荡

解决方案

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

OSPF 用以改善单纯的Dijkstra

是分布式的链路状态协议

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

链路状态数据库

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

具体特点

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

DV

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

思想

• 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
• 坏消息传播的慢
  
  • 无穷计数
  • 路由环路
  • 在t0时刻，y检测到链路费用变化，更新自己的距离向量yx=6（因为z仍旧认为zx=5），同时将这个变化通知给它的邻居
  • 在t1时刻，z收到来自y的更新报文并更新了自己的距离向量表zx=7，并向邻居发送它的新距离向量
  • 在t2时刻，y检测到链路费用变化，更新自己的距离向量yx=8（zx=7），同时将这个变化通知给它的邻居
  • …
  • 在ti时刻，z收到来自y的更新报文并更新了自己的距离向量表zx=49，并向邻居发送它的新距离向量
  • 在ti+1时刻，y检测到链路费用变化，更新自己的距离向量yx=50（zx=49），同时将这个变化通知给它的邻居
  • 在ti+2时刻，z收到来自y的更新报文并更新了自己的距离向量表zx=50，并向邻居发送它的新距离向量
  • 在ti+3时刻，y检测到链路费用变化，更新自己的距离向量yx=51同时将这个变化通知给它的邻居
  • 不再改变
  • e.g.例：需51-6次才能迭代完

解决方案

毒性逆转：如果z通过y选路到达目的地x：z将通告y，它到x的距离是无穷大 (所以 y不会通过z到达x)

但毒性逆转没有解决不可记数问题

LS与DV的对比

报文的复杂性

• LS：n 个节点，E 条链路，需要发送 O(nE)个报文
• DV：只在直连的邻居之间交换报文

收敛速度：算法收敛时间依赖于许多因素，因而是可变的

• LS：是一个要求O(nE)个报文的O(n2)算法，可能有震荡
• DV：收敛时间不确定，可能会遇到选路环路，记数到无穷问题

健壮性

• LS：节点能够向其连接的链路广播不正确费用，每个节点只计算自己的转发表

• DV：一个节点可向任意或所有目的节点通告其不正确的最低费用路径，每个节点的计算都会传递给它的邻居（错误会通过网络进行传播）

4.5 层次路由

问题背景

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

解决方案

• 将路由器聚合到一个区域，“自治系统” (AS)
• 在相同AS内的路由器可全部运行同样的选路算法
• 自治系统内部选路协议
  • 内部网关协议IGP，目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。
• 在不同AS内的路由器可以运行不同的自治系统内部选路协议
• 转发表是由AS内部选路算法和AS间选路算法共同决定的
  • AS内部选路算法为内部目的地址设置转发表信息
  • AS内部选路算法和AS间选路算法共同为外部目的地址设置转发表信息

自治系统间路由器的任务

• 假设AS1中的路由器收到一个数据报，其目的地址在AS1之外
  • 需要知道通过AS2可以到达哪些目的地，通过AS3可以到达哪些目的地
  • 将这些可达性信息向AS1中的所有路由器传播

场景1

• 假设AS1从AS间选路协议知道子网x经AS3(网关1c)可达，但是通过AS2不可达
• AS1向它的所有路由器广播该可达信息
• 路由器1d 知道，它的接口 I 在到路由器1c的最低费用路径上
• 从而路由器1d将表项 (x,I)放入其转发表。

场景2

• 现在假设AS1知道子网x可以通过AS3和AS2到达.
• 为了配置转发表，路由器1d必须决定通过哪个网关路由器转发报文（1b或1c）
• 这也是自治系统间选路协议必须解决的问题!
• 热土豆选路：将报文发送到最近的路由器(贪心)

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

• 为了使 OSPF 能够用于规模很大的网络，OSPF将一个自治系统再划分为若干个更小的范围，叫作区域
• 每一个区域都有一个32bit的区域标识符
• 区域也不能太大，在一个区域内的路由器最好不超过200个

划分区域

• 划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量
• 在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况
• OSPF 使用层次结构的区域划分。在上层的区域叫作主干区域。主干区域的标识符规定为0.0.0.0。主干区域的作用是用来连通其他在下层的区域

ISP之间的路由选择：BGP

问题背景

• 因特网的规模太大，使得自治系统之间路由选择非常困难
  • 对于自治系统之间的路由选择，要寻找最佳路由是很不现实的。
  • 自治系统之间的路由选择必须考虑有关策略
• BGP为每个AS提供一种手段，以处理
  • 从相邻AS获取子网可达性信息
  • 向该AS内部的所有路由器传播这些可达性信息
  • 基于该可达性信息和AS策略，决定到达子网的“好”路由
  • 边界网关协议BGP只能是力求寻找一条能够到达目的网络且比较好的路由而并非要寻找一条最佳路由

BGP发言人

• 每一个自治系统的管理员要选择至少一个路由器作为该自治系统的BGP发言人 。
• 一般说来，两个BGP发言人都是通过一个共享网络连接在一起的，而BGP发言人往往就是BGP边界路由器，但 也可以不是BGP边界路由器。
• 一个BGP发言人与其他自治系统中的BGP发言人要交换路由信息，就要先建立TCP连接，然后在此连接上交换 BGP报文以建立BGP会话(session)，利用BGP会话交换路由信息。
• 使用TCP连接能提供可靠的服务，也简化了路由选择协议

BGP路由通告

• AS2可以聚合多个前缀为一个，并使用BGP向AS1通告单一前缀，则AS2承诺它将沿着朝向该前缀的路径，转发指向该前缀的任何数据报

• 发布前缀可达性消息

  • 在网关路由器3a和1c之间使用eBGP，AS3向AS1发送一个自AS3可达的前缀列表.
  • 1c 则使用iBGP会话向AS1中的其他路由器发布这些前缀
  • 1b 则将和路由器2a间使用eBGP会话学习到的前缀信息发布到AS2
  • 当一个路由器得知一个新前缀，它为该前缀在其转发表中创建一个表项
  • 前缀信息的组成 = 前缀+属性
    • 前缀，聚合路由子网号
    • 属性AS-PATH：包含了已经通知过的AS
    • 属性NEXT-HOP：指明下一跳AS的具体路由器（网关路由器间可能有多条链路）
  • 网关路由器收到路由通告时，根据自己的输入策略决定是否接收或过滤
    • 本地偏好值：策略决定。具有最高本地偏好值的路由将被选择。
    • 最短AS-PATH：在余下的路由中，具有最短AS-PATH的路由将被选择。
    • 从余下的路由中，选择具有最靠近NEXT-HOP路由器的路由：热土豆路由。
    • 如果仍余下多条路由，该路由器使用BGP标识以选择路由
  • 总结
    • 路由器知晓前缀的存在性
      • 通过BGP通告得知（前缀+属性）
    • 确定此前缀的转发端口
      • 使用eBGP路由选择确定最佳域间路由
      • 使用IGP路由选择确定最佳域内路由
      • 确定最佳路由的转发端口
      • 将（前缀/掩码,端口）表项放入转发表中

  

---

第5章 链路层

6.1 概述

节点：主机和路由器

链路：沿着通信路径连接相邻节点的通信信道

• 有线链路
• 无线链路

链路层的主要功能：负责将数据报通过链路从一个节点传输到物理上相邻的节点

特别说明

• 数据报在不同链路上可能由不同的链路层协议进行处理：一段以太网，一段PPP
• 不同的链路层协议可能提供不同的服务：可靠或不可靠

链路层服务

• 链路层帧：链路层的PDU

  • 将数据加上头部和尾部，封装成数据帧

  • 帧头部用MAC地址标识源和目的（不同于IP地址）

• 链路接入：共享介质的信道访问

• 可靠交付：很少用于误码率低的链路（光纤、双绞线链路），用于误码率高的链路（无线链路）

• 差错检测和纠正

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

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

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

链路层实现：

• 适配器通信

  • 链路层在“适配器”（网卡NIC） 或者芯片上实现

  • 直接与主机的系统总线相连：和其它连接主机的I/O设备相同

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

• 适配器是半自治单元

  • 网络接口卡或芯片：以太网卡、802网卡、以太网芯片组
  • 帧的接收和发送、检错、丢弃：均是自主进行
  • 向上提交数据时，需要节点干预
  • 最终受控于节点

• 发送方

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

• 接收方

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

6.2 差错检测和纠正技术

EDC：差错检测和纠错比特，EDC越长出错的概率越低，但无法防止信息一定正确

奇偶校验：奇校验，使得D+DEC每位和为奇数；偶校验为偶数

二维奇偶校验：可纠正单bit差错

因特网检验和

• 发送方

  • 将数据段的内容作为16比特的整数序列
  • 校验和：累加求和，进位返回补最低位，计算反码
  • 发送方将得到的校验和值放入PDU校验和字段

• 接收方

  • 计算收到的数据段的校验和
  • 检查计算出的校验和与校验和字段中的值相加如果都是1则未检验出错误

循环冗余校验码

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

6.3 多路访问链路和协议

两种链路

• 点到点链路：PPP、HDLC 以太网交换机和主机之间的点到点链路
• 广播链路（共享线路或介质）：传统以太网、802.11无线LAN、HFC
  • 特点
    • 单个共享广播信道
    • 两个或多个节点同时传输：相互干扰 (碰撞：一个节点同时收到两个或多个信号)

多路访问协议

• 分布式算法决定节点如何共享信道，如节点何时可以传输数据
• 特别注意：有关共享信道的通信（协商）需使用信道本身 因为没有额外的信道来进行协调
• 分类
  • 信道划分协议
    • 将信道划分成小的“片”（时隙、频率、编码）
    • 将“片”分配给节点使用
  • 随机接入（访问）协议
    • 信道没有被分割，允许碰撞
    • 碰撞恢复
  • 轮流协议
    • 节点轮流传送，但数据量大的节点轮流更长时间

理想的多址访问协议需满足

假设：信道为速率为R b/s的广播信道

• 当只有一个节点有数据发送时，该节点的吞吐量为R
• 当M个节点有数据发送时，每个节点吞吐量为R/M
• 分散：没有特定的结点用于调整传输，没有时钟同步
• 简单

信道划分协议

时分复用TDMA

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

统计时分复用STDM

动态分配线路资源的时分复用方法，只有当用户有数据要传输时才给他分配线路资源，当用户暂停发送数据时，不给他分配线路资源，线路的传输能力可以被其他用户使用

频分复用FDMA

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

随机接入（访问）协议

• 当节点有数据发送时
  • 以信道全部速率R传输
  • 没有主节点起协调作用
• 两个或多个节点传送时——碰撞
• 随机访问协议解决
  • 如何检测碰撞
  • 如何从碰撞中恢复（如：延时后重传）
• 随机访问协议举例：ALOHA、时隙ALOHA、CSMA，CSMA/CD，CSMA/CA

纯ALOHA

• 简单，不需同步
• 当帧首次到达，节点立刻传送
• 碰撞可能增加
• t₀时刻发送的帧与[t₀-1, t₀+1]之内发送的帧碰撞

效率：P(t₀结点成功概率) = P(t₀传送)×P(在[t₀-1, t₀]没有其他结点传送)×P(在[t₀-1, t₀]没有其他结点传送) = p × (1-p)^N-1×(1-p)^N-1=p×(1-p)^2(N-1)

选择最合适的p，n趋于无穷,结果 = 1/2e = 0.18

时隙ALOHA

假设

• 所有的帧大小相同
• 时间被划分为相同大小的时隙，一个时隙等于传输一帧的时间
• 节点只在时隙的开始传输帧
• 节点被同步
• 若有两个或多个节点在一个时隙内传送，则所有节点都能在该时隙内检测到冲突

操作

• 当节点有新的帧发送，它等到下一个时隙发送
• 若没有碰撞，节点能在下一时隙传送完新帧
• 若有碰撞，节点以概率p在后续的每一个时隙重传该帧

优点

• 单个活动节点能以全速R连续传输
• 高度分散：时隙只在节点同步
• 简单

缺点

• 碰撞，浪费时隙
• 时隙空闲
• 节点需要在分组传送时间以内检测到碰撞
• 时钟同步

效率

• N个节点有大量帧发送，每个节点在每个时隙传送帧的概率为p
• P(给定节点成功概率)=P(给定节点传送)×P(没有其它节点传送)=p(1-p)^N-1
• 任一个节点成功的概率=Np(1-p)^N-1
• 为获得N个节点的最大效率，需要找到使Np(1-p)^N-1最大化的p’
• 当N趋于无穷时，求Np’(1-p’)^N-1的极限，得到最大效率为 1/e = 0.3

CSMA（载波监听多路访问）

传输前监听：如果信道空闲，传送整个帧；如果信道忙，推迟传送

• 碰撞依然可能发生
  • 传播延迟意味着2个节点可能没有听到对方的传输
• 碰撞发生
  • 数据包整个传送时间浪费
  • 距离和传播延迟在确定碰撞概率中的作用

分类

• 非坚持CSMA：信道忙则不再坚持监听，而是根据协议的算法延迟一个随机的时间后重新再监听。若进行载波监听时发现信道空闲，则将准备好的帧发送出去
• 时隙非坚持CSMA：采用划分时隙的随机接入CSMA协议，协议规定只能在每个时隙开始时才能发送帧
• 1坚持CSMA：信道忙则坚持监听到信道空闲时，将数据送出。若发生冲突，站点就等待一个随机长的时间，然后重新开始
• P坚持CSMA：信道忙则坚持监听到信道空闲时，以概率P将数据送出，以概率(1-P)延迟一段时间t(网络中最远的端到端的传播时延)重新监听。若发生冲突，站点就等待一个随机长的时间，然后重新开始

CSMA比较

• 非坚持：不能充分利用信道刚刚转入空闲期的这段时间
• 1坚持：容易在上述这段时间产生冲突（实际常用）
• P坚持：可以在一定程度上克服这些缺点，但却很难选择一个能 用于各种通信量强度的P值

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

碰撞检测操作

• 在短时间内碰撞被检测

  • 在有线LANs中比较容易：测量信号强度，比较收、发的信号

  • 在无线LANs中比较困难：传输时接收器是关闭的；接收的信号强度远小于发送信号强度

• 碰撞和停止传输，减少信道浪费

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

争用期

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

以太网CSMA/CD算法

1. 网卡从网络层接收数据报，创建数据帧
2. 如果网卡检测信道空闲，开始帧传输
3. 如果网卡的检测信道忙，等待直到信道空闲，然后发送
4. 如果网卡发送整个帧没有探测到另一个传输，网卡完成帧发送！
5. 如果网卡检测到另一个传输，传输终止并发送干扰信号
6. 传输终止后，进入二进制（指数）退避
   • 第m次碰撞后，网卡随机从{0，1，2，…，2m-1}选择K。网卡等待K×512bit时 间。返回第2步
   • 越多的碰撞，越大的退避间隔

效率：

• dprop：信号在任意2个节点间的最大传播时间

• dtrans：最大帧的传输时间

• 效率 = 1 / (1 + 5d_prop/d_trans)

• dprop →0，效率→1

• dtrans →∞，效率→1

• 性能优于ALOHA，且简单、便宜、非中心化

轮流协议

背景

• 信道划分协议
  • 在重负荷时，共享信道有效、公平
  • 在轻负荷时效率低：信道访问延时，即使只有一个活动节点，也只能分配到1/N 的带宽
• 随机访问协议
  • 轻负荷时效率高：只有一个节点时，能充分利用信道
  • 在重负荷下：碰撞的开销
• 轮流协议：在两个方面寻求最佳的解决方案

轮询协议

• “主”节点邀请”从”节点轮流传输
• 通常用于“哑”的“从”节点
• 关注： 轮询开销、等待时间、单点失效（主节点）

令牌传递协议

• 控制令牌依次通过各个结点
• 令牌报文
• 关注：令牌的开销、等待时间、单点失效(token)

6.4 交换局域网

MAC地址，也叫LAN地址，物理地址

• 作用：在数据链路层标识每块网络适配器，使得能够在广播信道上寻址目标节点
• 组成：48bit（6个字节）
• 前24bit由IEEE分配管理——OUI号
• 后24bit由厂商自行分配
• IEEE管理MAC地址空间（象征性收费）
• 特别注意：MAC地址烧入网络适配器的ROM中，不可更改（软件可改）

IP与MAC的差异

• MAC地址是平面地址，类似于身份证号；IP地址是层次地址，类似于邮政通信地址
• MAC地址在不同的网络间迁移时，不会改变；IP地址在不同的网络间迁移时，需要改变以适应新的网络配置

地址解析协议ARP

根据IP获得MAC地址

每个IP结点都有ARP表，存储局域网结点IP/MAC的映射

同一局域网工作流程

1. 建立ARP请求包
2. 广播发送该ARP请求包
3. 目的197.15.22.126接收到ARP请求包，建立自己包含自己MAC地址的ARP应答包
4. 向源197.15.22.33发送该ARP应答包
5. 197.15.22.33更新ARP高速缓存

MAC报头	IP报头	语义
目标FF-FF-FF-FF-FF-FF 源02-60-8C-01-02-03	目标197.15.22.126 源197.15.22.33	你的MAC地址是什么

MAC报头	IP报头	语义
目标02-60-8C-01-02-03 源08-00-02-89-90-80	目标197.15.22.33 源197.15.22.126	我的MAC地址是…

互联网环境下工作流程

要点:

• IP报头始终不变
• 根据链路两端判断MAC地址

以太网

总线式以太网：

交换式以太网

以太网的帧结构

• 前同步码：8字节，前7字节格式为10101010，最后字节格式为10101011，用于同步发送方与接收方时钟
• 目的地址，源地址：各6字节，若适配器收到以太网帧，目的地址为自己的MAC地址或广播地址（如ARP包），就将帧中的数据传给网络层
• 类型：2字节，上层协议类型（大多为IP协议，也支持其它协议如Novell IPX 和AppleTalk）
• 数据：46字节~1500字节
• CRC：循环冗余校验码

以太网提供的服务

• 无连接服务：在发送适配器和接收适配器之间不需要握手
• 不可靠服务：接收适配器不发送确认帧或否认帧给发送方
  • 交给网络层的数据报可能存在间隙
  • 若应用使用TCP，间隙会被填充
  • 否则，应用就会看见间隙

以太网使用的CSMA/CD

拥塞信号：用来确保所有传输者都能检测到碰撞而传输的信号 ；48比特长

比特时间：传输1比特所需时间。在10Mbps的以太网中，当 K=1023时，等待时间大约为50ms

• 没有时隙
• 当适配器侦听到其它适配器在传输，则不传输帧，即载波侦听
• 正在传输的适配器若检测到其它适配器也在传输，则它中止自己的传输，即碰撞检测
• 在重新传输之前，适配器要等待一段随机时间，即随机访问

算法

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

特点

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

争用期长度

• 10Mb/s以太网取51.2us为争用期的长度（100M是5.12us）
• 对于10Mb/s以太网，在争用期内可发送512bit，即 64 字节
• 以太网在发送数据时，若前 64 字节没有发生碰撞，则后续的数据就不会发生碰撞

最短有效帧长

• 如果发生碰撞，就一定是在发送的前64字节之内
• 由于一检测到碰撞就立即中止发送，这时已经发送出去的数据一定小于64字节
• 以太网规定了最短有效帧长为64字节，凡长度小于64字节的帧都是由于冲突而异常中止的无效帧

以太网传统物理层

10BASE5粗缆

• 粗同轴电缆，可靠性好，抗干扰能力强
• 收发器：发送/接收，冲突检测，电气隔离
• AUI：连接件单元接口
• 总线型拓扑
• 用于网络骨干连接

10BASE2细缆

• 细同轴电缆，可靠性稍差
• BNC T型接头连接
• 总线型拓扑
• 用于办公室LAN

10BASE-T双绞线

• 节点连接到集线器：“星形拓扑”; 在节点和集线器之间的最大距离为100米

10BASE-F光缆：略

以太网信号编码

曼彻斯特编码

差分曼彻斯特编码

集线器

• 集线器本质上是物理层的中继器：从一个接口收到的比特流会传给其它所有接口
• 同样速率
• 没有帧缓存
• 集线器没有CSMA/CD：由适配器检测碰撞
• 提供网络管理功能（可网管、智能、网络分段）

特点

• 主干集线器将LAN网段互联起来
• 扩展了节点间的最大距离
• 原先独立的网段碰撞域变成了一个大的碰撞域
• 不能将10BaseT 和 100BaseT以太网互联

链路层设备

• 存储、转发以太网帧
• 查看输入帧的MAC地址，选择性的将帧输出到一个或多个输出链路，使用CSMA/CD
• 透明：主机不知道交换机的存在
• 即插即用，自学习：交换机不需要配置

交换机

• 主机直接连接到交换机
• 交换机缓存数据包
• 每一条链路都采用了以太网协议，但之间没有冲突，全双工通信
• 每一条链路是其自身的冲突碰撞域 A<–>A’，B<–>B’能够同时传输而不会碰撞
• 交换机中存在一个交换表：表结构：主机MAC地址，连接主机的接口，时间戳（产生表项的时间）
• 自学习：当数据帧进入交换机时，交换机学习发送方所连接的接口，将“发送方/接口”对记录到交换表

自学习：帧过滤/转发

1. 记录发送方输入接口和MAC地址
2. 使用目标MAC地址检索交换表
3. 如果目标地址可以找到：发给自己的丢掉，不是发给自己的则转发
4. 如果找不到则广播

交换机互联

交换机间也不了解互相的存在，但通过自学习即可完成数据转发

网桥

可以理解为2接口交换机

工作原理

• 不断监听各端口是否有信号
• 收到无差错的帧则缓存，反之将差错帧丢弃
• 若所收帧的目的MAC地址属另一网段，则通过站表决定向何端口转发
• 网桥不转发同一“网段”内通信的帧 目的主机和源主机不连接在网桥的同一接口上才会转发
• 网桥不修改所转发的帧的源地址

优势

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

缺点

• 由于要接收和转发，增加了时延
• MAC子层没有流量控制功能，网络负荷重时，网桥缓存空间可能发生溢出，产生帧丢失现象
• 不同MAC子层的网段桥接时，在转发帧之前要修改帧的某些字段，这也需要耗费时间
• 出现广播风暴。网桥只适合用户少于几百个和通信量不太大的局域网，否 则有时会因传播过多广播信息而产生网络拥塞

与集线器区别

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

网桥的透明性导致的问题

解决方案：支撑树算法

• 互连在一起的网桥彼此通信后，就能找出原来的网络拓扑的一个子集，在这个子集里整个连通的网络中不存在回路。一旦支撑树确定了网桥就会将某些端口断开，以确保从原来的拓扑得出一个支撑树
• 支撑树算法选择一个网桥为树的根，然后以最短路径为依据，找到树上的每一个结点
• 为了让支撑树能反映网络拓扑的变化，每隔几秒钟每个网桥要广播其标识号，和它所知道的所有其他网桥
• 缺点：互连局域网数目非常大时，支撑树算法可能花很多时间

以太网路由器和交换机

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

虚拟局域网

基于接口的VLAN

• 流量隔离：来自接口1-8的帧就只能从1-8转发也可根据终端MAC地址定义
• 动态分组：接口可动态的分配VLAN
• VLAN间数据转发 通过VLAN间路由（就像多个独立的交换机一样）实际中销售商是打包（捆绑）销售

多交换机的VLAN

trunk接口：多个物理交换机上多个VLAN中的帧发送

• VLAN中跨交换机进行转发的帧不能简单的使用802.1（局域网协 议）帧格式（必须携带VLAN ID信息）
• 802.1q协议（VLAN标记协议）是在trunk接口处增加/删除附加的帧的首部字段

vlan标记协议

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

电脑访问Google

1. DHCP服务获取笔记本的IP、网关、DNS服务器

   笔记本	操作
   应用层	DHCP请求
   传输层	UDP封装
   网络层	IP封装
   链路层	以太网帧封装广播发送给DHCP服务器网关路由器
   物理层	物理介质传输

   DHCP服务器接收请求后应答	操作
   应用层	客户端IP，掩码、网关、DNS服务器信息
   传输层	UDP封装
   网络层	IP拆封
   链路层	局域网转发(交换机自学习)
   物理层	物理介质接收

2. ARP：广播发送ARP请求获取DNS服务器的MAC地址

3. DNS服务将Google域名转换为IP地址，IP数据报被网关服务器按照路由器中的路由表导向DNS服务器所在AS，多路分解到DNS server， DNS server向客户端发送包含IP的DNS应答

   笔记本	操作
   应用层	DNS请求
   传输层	UDP封装
   网络层	IP封装
   链路层	以太网帧封装发送给DNS服务器
   物理层	物理介质传输

   DNS服务器	操作
   应用层	DNS应答
   传输层	UDP封装
   网络层	IP封装
   链路层	以太网帧封装发送给笔记本
   物理层	物理介质传输

4. HTTP服务访问Google网页，客户端创建TCP套接字，三次握手与Google服务器建立连接

   笔记本	操作
   应用层	HTTP请求
   传输层	TCP封装，SYN=1
   网络层	IP封装
   链路层	以太网帧封装发送给Google服务器
   物理层	物理介质传输

   Google	操作
   应用层	HTTP应答
   传输层	TCP封装，SYN=1，ACK=1
   网络层	IP封装
   链路层	以太网帧封装发送给笔记本
   物理层	物理介质传输

   笔记本	操作
   应用层	HTTP访问内容
   传输层	TCP封装，ACK=1
   网络层	IP封装
   链路层	以太网帧封装发送给Google服务器
   物理层	物理介质传输

OVER