基本知识

网络协议组成要素

语法
语义
同步

通信知识

分组交换

传输方式

虚电路
数据报

时延

类型

结点处理时延
排队时延
传输时延
传播时延

计算

$d_{nodal}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$

存储转发和直接转发的区别

存储转发需要收到一个完整的帧再发送，慢
直接转发收到数据就发送，快

分组丢失

分组到达速度大于发送速度，分组缓存容量有限，超出容量就会造成丢失

电路交换

实现方式

FDM（频分）
TDM（时分）
CDMA（码分）

应用层

协议数据单元（PDU）

message，中文称报文、消息

协议

HTTP(超文本传输协议)
Web
FTP(文件传输协议)
传输文件
SMTP(简单邮件传输协议)
传输邮件
POP3
查看邮件
IMAP
查看邮件
DNS（域名系统）
- 查找域名对应的IP地址
  - 迭代查询
  - 递归查询
- 根DNS服务器
- 顶级域DNS服务器
- 权威DNS服务器
- 本地DNS服务器

传输层（运输层）

协议数据单元（PDU）

segment，中文称报文段、分组、数据段等等

协议

TCP（传输控制协议）

TCP报文段结构

标志字段
- ACK
- SYN
- FIN
序号和确认号
- TCP提供累积确认

TCP报文段格式

往返时间(RTT)的估计和超时

估计往返时间

新的估计往返时间等于旧的估计往返时间和新的测量时间以一定比例相加
仅在某个时刻做一次测量，且不为重传的报文段测量RTT，只为传送一次的报文段测量

公式

RTT估算：
$EstimatedRTT(RTT_s)=(1-\alpha)\times EstimatedRTT+\alpha \times SampleRTT$
α推荐为0.125

RTT变化程度:
$DevRTT(RTT_D)=(1-\beta)\times DevRTT+\beta\times |SampleRTT-EstimatedRTT|$

设置重传超时间隔（Karn算法）

$RTO(TimeoutInteval)=EstimatedRTT+4\times DevRTT$
如果重传，RTO=2*RTO

功能

可靠数据传输

快速重传

接收方
每收到一个失序报文段，立即发送一个对上一个按序到达报文的重复确认（ACK）
发送方
一旦受到3个冗余ACK，直接重发对方要求的报文段，不过重传计时器依然有效

特点

发送和接受窗口不一定一样大
TCP标准没有规定不按序到达的数据如何处理
TCP要求接收方必须有累积确认的功能

流量控制

发送方不能淹没接收方缓存

接受窗口rwnd

利用滑动窗口实现流量控制

拥塞控制

和流量控制的区别

拥塞控制针对全网，流量控制针对一对一连接

状态变量

拥塞窗口cwnd
慢启动阈值ssthresh

拥塞的影响

时延变大
丢包

方法

慢开始和拥塞避免
发送方维持一个叫做拥塞窗口（cwnd）的状态变量。拥塞窗口的大小取决于拥塞程度，动态变化。发送方让发送窗口等于拥塞窗口。开始拥塞窗口的值设置为一个最大报文段（MSS）的数值，记为1。如果没有出现拥塞，每经过一个传输轮次，cwnd变为原来的两倍。为了防止过快增加，设置了慢开始门限状态变量（ssthresh）。当检测到超时时，将ssthresh设为原先cwnd的一半，将cwnd置为1，重新开始慢启动，这个过程中当cwnd的大小等于ssthresh时，执行拥塞避免策略，每次cwnd的大小只增加1.
快重传和快恢复
快速重传的策略已经在图中有解释。当发送方接收到3个冗余ACK时（但并没有超时），TCP对于这种事件反应没有超时那么激烈，此时执行快速恢复策略：将ssthresh设为原先cwnd的一半，再将cwnd的值减半，之后每次发送时cwnd的值再增加1。
一种称为TCP Tahoe的TCP早期版本没有快速恢复策略，不管是超时还是收到3个冗余ACK，均采用慢开始策略。而较新版本的TCP Reno，则综合了快速恢复。两者的区别如下图：

TCP连接管理

三个阶段

连接建立

1. 三次握手

三次握手的过程：

第一次握手：客户端主机向服务器发送一个特殊的TCP报文段，该报文段不包含应用层数据，但是在报文段的首部中的SYN标志位置为1，代表请求建立连接，称为SYN报文段。客户端随机选择一个初始序号，并将此编号放在SYN报文段的序号字段。该报文段被封装在一个网络层数据报中，发送给服务器。
第二次握手：服务器接收到包含SYN报文段的IP数据报，提取出SYN报文段，为该TCP连接分配TCP缓存和变量，并向客户TCP发送允许连接的报文段。该报文段也不包含应用层数据，SYN标志位置为1，确认号字段为SYN报文段的编号+1，服务器选择主机的初始序号，并将其放置到TCP报文段首部的序号字段。这个报文段被称为SYNACK报文段。
第三次握手：客户端收到SYNACK报文段后，也要给该连接分配缓存和变量。同时再向服务器发送另外一个报文段，对于SYNACK报文段给以确认，这个报文段包含了应用层数据。

三次握手的原因：

双方能确知对方的存在
允许双方协商一些参数
对运输实体资源进行分配

拓展知识：
因为第二次握手（还没有正式开始传送数据）时，服务器就已经给TCP连接分配了缓存资源，这为经典的DoS攻击即SYN洪泛攻击（SYN flood attack）提供了环境。在这种攻击中，攻击者发送大量的TCP SYN报文段，而不完成第三次握手的步骤。随着这种SYN报文段纷至沓来，服务器不断为这些半开连接分配资源（但从未使用），导致服务器的连接资源被消耗殆尽。这种SYN洪泛攻击是被记载的众多DoS攻击中的第一种。

三次握手过程

2. 数据传送

3. 连接释放

连接释放的过程：
客户端向服务器发送一个特殊的TCP报文段，该报文段FIN标志位置为1。服务器收到后，给发送方回送一个确认报文段。然后服务器发送它自己的终止报文段，其FIN比特被置为1.最后，客户端对服务器的终止报文段进行确认。

连接释放过程

UDP（用户数据报协议）

无连接的

不可靠、失序交付
不提供不必要的可靠性扩展（在网络层基础上）

UDP报文段结构

UDP校验和的计算

发送方的UDP对报文端中的所有16比特字的和进行反码运算，求和时遇到的任何溢出都被回卷。得到的结果被放在UDP报文段的校验和字段。举例来说，假定我们有下面3个16比特的字：

0110011001100000
0101010101010101
1000111100001100

前两个之和是

 0110011001100000
+0101010101010101
------------------
 1011101110110101

再将上面的和和第三个字相加，得出：

 1011101110110101
+1000111100001100
------------------ 
 0100101011000010

注意到最后一次加法有溢出，它要被回卷。反码运算就是将所有的0换成1，所有的1换成0.因此，该和0100101011000010的反码运算结果是1011010100111101，这就是校验和。在接收方，全部的4个16比特字（包括校验和）加在一起，如果该分组中没有引入差错，则显然在接收方处该和将是1111111111111111。如果有一个是0，就代表分组中出了差错。

传输层和网络层的关系

网络层针对主机之间的逻辑通信
传输层为主机上的进程提供通信，即端到端的通信，依赖于网络层

对于网络层和传输层的描述，考虑有两个家庭，一家位于辽宁沈阳，一家位于浙江宁波，每家有4口人。每个人每星期要互相写一封信，每封信都用单独的信封通过中国邮政传送。因此每个家庭每星期向另一家发送16封信。每一个家庭有个孩子负责收发邮件，浙江宁波家庭是小明，辽宁沈阳家庭是小红。每星期小红去她的家人那里收集邮件，并将这些信件投到社区的邮筒里。当新建到达沈阳的家庭时，小红也负责将信件分发给家里人。在宁波的小明家里也负责类似的工作。

在这个例子中，邮政服务为两个家庭间提供逻辑通信，邮政服务将信件从一家送到另一家，而不是从一个人送到另一个人。在另一方面，小明和小红为家人之间提供了逻辑通信，他们从家人那里收取信件或到家人那里交付信件。注意到从家人们的角度来看，小明和小红就是邮件服务，尽管他们只是端到端交付的一部分（即端系统部分）。类比关系如下：

进程 = 家人
主机（又称为端系统） = 家庭
传输层协议 = 小明和小红
网络层协议 = 邮政服务（包括邮筒）

小明和小红都是在自己家里进行工作的，他们没有参与任何一个中间邮件中心对邮件进行分拣，或者将邮件从一个邮件中心送到另一个邮件中心之类的工作。类似地，运输船协议只工作在端系统中。在端系统中，运输船协议将来自应用进程的报文移动到网络边缘（即网络层），反过来也是一样，但对有关这些报文在网络核心如何移动并不作任何规定。

多路复用（分用）和多路分解

多路复用（发送端）

从不同套接字收集数据块，为每个数据块封装上首部信息生成报文段，传递到网络层

多路分解（接收端）

将传输层报文段中的数据交付到正确的套接字，定向给进程

多路复用和多路分解的原理可以同样用上面这个家庭的例子来作类比。每一个家庭成员通过他们的名字来标识（相当于套接字）。当小明从邮递员出收到一批信件，并通过查看收信人名字而将信件交付给他的家人时，他执行的就是一个多路分解操作。当小红从家人那里收集信件并将它们投到邮筒中时，她执行的就是一个多路复用操作。

端口

熟知端口（0-1023）
不能随便用
登记端口（1023-49151）
为应用程序长期使用，必须在IANA登记，防止重复
客户端口或短暂端口（49152-65535）
客户进程短暂使用

可靠数据传输原理

可靠传输（RDT）的种类

信道无错误，无丢失

rdt1.0

信道有错误，无丢失

rdt2.0（停止等待）

rdt2.0

错误处理方法

发送端重传

新增状态

发送端检测
接收端校验
- ACK（肯定确认）
- NAK（否定确认）

存在缺陷

ACK或NAK出错时，发送方无法得知

rdt2.1

rdt2.1发送方
发送方收到含糊不清的ACK或NAK时，重传冗余分组

rdt2.1接收方

接收方需要判定数据是否重复，给每个分组加一个标签代表顺序号

rdt2.2

将两次对上个分组的ACK认为是当前分组的NAK

rdt2.2发送方

rdt2.2接收方

信道有错误，有丢失

rdt3.0

设置定时器，超时即重传

采用流水线的方式发送以提高效率

增加序号范围
发送端需要缓存没确认的分组
处理丢失、损坏和超时的分组方法
- 回退N步（GBN）
  - 滑动窗口
  - 累积确认
  - 接收端无需缓存
- 选择重传（SR）
  - 滑动窗口
  - 接收端需要缓存
  - 发送窗口不能大于接收窗口
  - 序号个数大于等于发送窗口加接收窗口的大小，这样包的序号才不会重复

网络层

协议数据单元

数据报(datagram)

转发和路由选择

区别：

转发：单个路由选择输出链路
路由选择：规划整条路径

路由器只工作到网络层

路由算法

虚电路和数据报网络

虚电路

特点：

每个路由器都要为进行中的连接维持连接状态信息
每个路由器有一张转发表记录VC号
一条完整的虚电路中每段链路有一个VC号
分组首部中包含VC号，由路由器更新

改变VC号的目的：简化虚电路建立

信令协议：用于建立、保持、拆除虚电路

数据报网络

特点：

没有连接建立的概念
转发靠识别目的主机地址
地址太多怎么办：最长前缀匹配原则
同一个端到端，不同时间，分组走的路径可能不同

路由器工作原理

路由器结构

路由转发平面（硬件实现）

1 输入端口

功能：

将输入的物理链路与路由器相连接（物理层功能）
与位于入链路远端的数据链路层交互（数据链路层功能）
查询转发表决定输出端口

2 交换结构

种类：

经内存交换

特点：

在路由选择处理器的直接控制下完成
数据报经过两次数据总线

经总线交换

特点：

不需要路由选择处理器的干预
一次只有一个分组能够跨越总线

经互联网交换

特点：

能够并行转发多个分组

3 输出端口

路由器转发控制平面（软件实现）

路由选择处理器

何处出现排队

延时溢出
线路前部阻塞

网络层三个主要组件

1. 网际协议（IP）

提供：

路由功能
决定数据报是否到达目的地，或是否要被转发，如果要转发，IP协议决定下一个转发的位置

不提供：

可信赖的保证

数据报格式

分片和重组

原因：不同的链路层有不同的MTU（最大传送单元）

特点：重组只在终点进行，路由器只做转发和选路

IPv4编址

长度32比特

CIDR（无类别域间路由选择）

network ID 网络ID
subnet ID 子网ID
host ID 主机ID

子网掩码

NAT（网络地址转换）

特点：

本地网络地址和外部地址分开
对外只有一个唯一的地址

争议：

路由器应该只工作到网络层
违背了端到端的假设
地址短缺应当用IPv6解决

2. ICMP（互联网控制报文协议）

用于主机和路由器交换信息，报错、回显请求等等

特点：通常被认为是IP的一部分，但从体系结构上讲它是位于IP之上的，因为ICMP报文承载在IP分组中

3. 路由选择

目的：给定一组路由器以及连接路由器的链路，找到一条从源路由器到目的路由器的好路径

算法

全局式路由选择算法，也称链路状态算法（LS算法）
问题：若代价计算基于所承载的流量，会产生振荡，费用反复改变

内容：详见文章

分散式路由选择算法，也称距离向量算法（DV算法）
问题：好消息传得快，坏消息传的慢，从而导致不断往复计算

解决方案：增加毒性逆转

内容：详见文章

分层路由

路由器不能保存全球所有的路由的信息

AS（自治系统）

同一个AS内部运行相同的路由协议（自治系统内部路由选择协议）
热土豆路由
所有AS之间运行相同的路由协议（自治系统间路由选择协议）
网关路由器

协议

域内协议

RIP（路由选择信息协议）

DV算法

代价和跳数对应

最大跳数15

RIP通告：30秒交换一次；180秒没有响应代表链路中断

运行在UDP之上，当作应用层进程来实现

OSPF（开放最短路径优先）

LS算法：Dijstra算法

过程：通告携带信息，广播到整个AS系统，OSPF通告包含在报文中，OSPF报文直接由IP承载

优点

安全，能够使用鉴别
不同服务类型可以用多种方式算代价
同时支持单播和多播路由（MOSPF）
在更大的范围内可以使用层次结构的OSPF

域间协议

BGP（边界网关协议）

工作手段：

从相邻AS处获得子网可达性信息
向本AS内部的所有路由器传播这些可达性信息
基于可达性信息和AS策略，决定到达子网的“好”路由

####### BGP会话

性质：半永久的TCP连接

用途：用于一堆路由器交换路由信息

分类：

外部BGP会话(eBGP)
内部BGP会话(iBGP)

特点：BGP会话并非与物理链路一一对应

广播和多播路由

IGMP（因特网组管理协议）

数据链路层

协议数据单元（PDU）

帧（frame）

简介

功能：相邻结点的传输

术语：

nodes（结点）：主机和路由器
links（链路）：沿着通信路径连接相邻结点的通信信道
frame（帧）：封装数据报

特点：

同个路径不同链路可能采用不同的协议传数据
不同的链路协议提供不同的服务

提供的服务

成帧
链路接入
可靠交付
差错检测与纠正
- 奇偶校验
- 因特网校验和
- 循环冗余检测(CRC)

多路访问协议

术语：
碰撞（collide）、争用期

信道划分协议

TDM（时分复用）
FDM（频分复用）
CDMA（码分多址）

随机访问协议

时隙ALOHA
纯ALOHA
CSMA（载波监听多路访问）
CSMA/CD（带有冲突检测的载波监听多路访问）
- 802.3即以太网中采用
- 使用二进制指数后退算法确定重传等待时间
CSMA/CA（带有冲突避免的载波监听多路访问
- 效率比ALOHA高
- 802.11即WiFi中采用

轮流协议

轮询
令牌传递

交换局域网

寻址

MAC地址：48位

ARP（地址解析协议）

以太网

以太网帧

长度在64-1518字节，其中数据部分长度在46-1500字节之间

争用期

详见文章概念

10M以太网取51.2微秒为争用期

链路层交换机

特点：

透明：主机和路由器并不能感受到它的存在
自学习：即插即用

功能：转发和过滤

性质：

消除碰撞
异质的链路
交换机使不同链路彼此隔离，不同链路能以不同速率运行
管理
易于进行网络管理

使用以太网交换机可以实现虚拟局域网VLAN，这只是一种服务，并不是新型网络

高速以太网

100BASE-T

特点：

可在全双工方式下工作而无冲突
不使用CSMA/CD
MAC帧仍是802.3标准
帧间间隔由9.6微秒，改为0.96微秒

三种不同物理层标准

100BASE-TX：2对双绞线
100BASE-FX：光纤
100BASE-T4：4对双绞线
不支持同轴电缆

吉比特以太网

特点

允许在1Gb/s下以全双工和半双工工作
使用802.3帧
半双工下使用CSMA/CD
与10Mb/s 100Mb/s兼容

物理层

1000BASE-X：光纤
1000BASE-T：4对双绞线

10Gbit以太网

特点

802.3帧
不再使用铜线，只使用光纤
只工作在全双工方式，不使用CSMA/CD

以太网的特点

可扩展
灵活
易于安装
稳健性好

点对点传输

特点：面向连接，一个发送方，一个接收方，一条链路

协议

PPP点对点协议

三个组成部分

一个将IP数据报封装到串行链路的方法
链路控制协议
网络控制协议

需要提供的服务

发送端把网络层的数据报封装成数据链路层的帧，接收端解封装
可以携带任何bit格式
差错检测（不纠正）
有链接的服务
终端可以学习并配置网络地址

不用提供的服务

纠错
流量控制
失序传送
多点链路

三个基本问题

封装成帧
透明传输
差错检测

链路层

协议数据单元

比特（bit）

拓扑种类

总线型拓扑
星型拓扑
树型拓扑
环形拓扑
网状拓扑

接入方式

拨号上网
ADSL(非对称数字用户线路)
HFC（混合光纤同轴电缆网）
光纤接入
无线网络
- 802.11b WiFi
- 蜂窝网

物理媒介

双绞线
按用途分类：

Cat 3 电话使用
Cat 5 以太网使用

按有无屏蔽分类

无屏蔽双绞线 UTP
有屏蔽双绞线 STP

同轴电缆

光纤

无线电