计算机网络与通信

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

1.1 什么是因特网

因特网是一个世界范围的计算机网络。其构成描述如下：

主机、端系统：因特网中互联的设备
通信链路：传输数据的物理媒介，传输速率的单位为bit/s或者bps
分组交换机：端系统之间进行数据通信是会将数据分段并加上首部字节形成信息包，这个过程称为分组。分组交换机是端系统之间的中继，用于接受通信链路中的分组并进行转发。常用的分组交换机有路由器和链路层交换机
因特网服务提供商ISP：端系统一个ISP接入因特网，ISP为端系统提供了不同类型的网络接入，如住宅宽带接入、高速局域网接入、无线接入以及拨号调制器接入
协议：端系统、分组交换机和其他因特网部件运行的规则。因特网的主要系统协议为TCP/IP协议

因特网最重要的功能是为应用程序提供服务，从服务的角度其描述如下：

分布式应用程序：即上面提到的应用程序，是因特网的服务对象，运行在端系统上
应用程序编程接口API：API规定了运行在一个端系统上的软件请求因特网基础设施想运行在另一个端系统上的特殊目的软件交付数据的方式，即规定了因特网为应用程序提供服务的方式

1.2 网络边缘

端系统位于因特网的边缘，称为网络边缘。对于主机，根据数据请求的方向，可以分为客户和服务器两大类。

网络边缘接入互联网需要通过接入网，即端系统到任何远程端系统路径上的第一台路由器之间的通信链路，其中连接到的路由器称为称为边缘路由器。接入的主要方式有：

点对点的接入：电话线（DSL），光纤到户（FTTH），卫星
以太网：有线或无线以太网
广域无线接入：3G、4G、5G

其主要的物理媒介有双绞铜线（电话线），同轴电缆（电视信号线），光纤，或使电磁波直接通过大气层或真空传播

1.3网络核心

互联网的网络核心是由分组交换机和链路构成的网状网络。其涉及的主要问题是数据的交换方式，主要有分组交换和电路交换。

在电路交换网络中，在端系统间的通信期间预留了通信需要的资源，相当于在通信的端系统间创建了一条从发端到收端的物理通路，交换双方可实时进行数据交换而不会存在任何延迟，传统电话网络使用电路交换。但是灵活性不足，且不符合计算机网络中数据交换的突发性与间接性等特征。在电路交换中，为了最大程度利用通信资源，采取频分复用（为不同的链接设置不同的频段）和时分复用（将时间分为一系列帧和时隙，所有链接交替进行通信）。

分组交换网络中，发送报文时将报文分解为若干小部分，称为分组，在接受报文时将分组重新拼接成信息。在源和目的之间，每个分组都通过通信链路和分组交换机传送，这意味着网络中每个分组的传送路径可能不同，且存在冗余路由。每个交换节点采用存储转发的技术，即当路由器接收到分组时，在没有接收到分组的所有比特时不会转发分组。同时各节点具有选择合适路由的能力，路由器中具有一个转发表将目的地址映射为输出链路，并依据输出链路选择适当的转发方向。

分组交换网络分为两类，一类是虚电路网络，即模拟电路交换建立虚电路链路，对分组进行标识以知道应走哪个虚电路，并为通信预留资源；一类是数据报网络，即纯分组交换。

分组交换具有不可预测的时延，但是由于其按需分配链路资源，具有更好的带宽共享，且比电路交换更简单有效易于实现；电路交换时延较小，但是由于其其不考虑需求而预先分配了传输链路的使用使链路使用不充分。

端系统（网络边缘）通过接入ISP与互联网链接，但接入ISP之间也需要互连，这就涉及网络核心中网络的网络的概念。

网络的网络可以采用直接连接每个接入ISP，使用条连接，显然这样费用太多，成本太高。于是采用分层的思想，如下图所示，按照结构层次安排ISP的连接。最底层为接入ISP，接入ISP先接入某个区域ISP，区域ISP或者接入第一级ISP，或者进行直接互联，或者通过IXP（因特网交换点）互联。当然并不是一定要按照这种层级结构，接入ISP同样可以直接接入第一级ISP，但是费用不同。

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

时延的类型有：

处理时延：节点检查分组首部并决定分组导向、检查差错等操作所需要的时间。
排队时延：路由器收到数据需要排队以按顺序转发，排队的时间称为排队时延
传输时延：设分组的长度为L bit，链路传输速率为R bps，传输时延为L/R，是路由器将分组推出去需要的时间。
传播时延：从链路的起点到下一个节点之间的传输时间为传播时间，传播时间与两节点之间的距离和电磁波在不同介质中的传播速率有关，是信息传播的时间。

针对排队时延，设a标识分组到达路由器传输队列的平均速率，R为传输速率，假定所有分组的长度都是L，则定义流量强度La/R。流量强度约等于0时几乎没有排队时延，小于1时时延较小且逐渐变小，等于1时时延不会变化，具体时间取决于当前队列长度，大于1时平均时延较大且趋向无穷。

总端到端时延等于所有节点上的四类时延加起来。

当传输队列已满时，再来到路由器的数据只能丢掉，就造成丢包。

吞吐量分为瞬间吞吐量和平均吞吐量，前者指接收方接收到文件的瞬时速率，后者假设文件有F bit，接收使用T秒，则为F/T。吞吐量由链路中的瓶颈链路确定。

1.5协议层次及其服务模型

为了给网络协议的涉及提供一个结构，网络设计者以分层的模式组织协议以及实现协议的软件和硬件。因特网的五层协议以及每个协议对应的功能如下，各层的所有协议称为协议栈。

协议层次化的好处时协议之间的调用关系明确，并简化了系统的维护和升级。但是不是所有的协议关系都能归结为两层之间，偶尔会出现隔层调用或下层调用下层的现象。

在协议栈中，有以下概念：

实体：发送和接受信息的软件进程或硬件
对等体：不同机器上包含对应层的实体称为对等体
服务：为保证上层对等体之间能互相通信，下层向上层提供的功能
接口：接口位于每对相邻层之间，定义了下层向上层提供的原语操作和服务。
协议数据单元(PDU)：对等层次上传送数据的单位
服务数据单元（SDU）：层与层之间交换数据的单位

上面是五层模型，还有OSI的七层模型如下

计算机网络体系中，发送方数据从上层开始向下层层包装，最终从物理层发出，接收方从物理层接收到数据后将数据层层剥去包装，最后给最高层。

第二章应用层

网络应用时计算机网络存在的理由。本章重点是套接字编程与几个具体应用层协议。

2.1 应用层协议原理

研发网络应用的核心是写出能够运行在不同端系统上并通过网络彼此通信的程序。从应用程序研发者的角度看，应用程序体系结构主要有两种，一种是客户-服务器体系结构，其中客户之间不相互通信，有一个常开的主机称为服务器，客户只向服务器发送请求与接收数据，这种结构的应用有Web，FTP，Telnet和电子邮件；一种是P2P体系结构，应用程序之间直接通信，主要应用有bitTorrent、Skype、迅雷等。P2P结构具有自扩展性，但是具有以下挑战：ISP上下行带宽不对等、安全性、用户是否愿意共享带宽和存储

无论是哪种体系结构，网络应用程序都是由成对的进程组成，我们通常将一个进程标识为客户，另一个标识为服务器。从一个进程向另一个进程发送的报文必须通过下层协议，进程通过称为套接字的接口发送和接受报文。而网络通信中一对进程之间的寻址，一方面需要知道进程运行的主机，即IP地址，另一方面需要知道进程是哪一个，即进程运行的端口，套接字即通过IP地址和端口号寻址。发送端的应用程序将套报文推进套接字，在套接字的另一端，运输层协议使报文接入进程的套接字。

包括因特网在内的很多网络提供了不止一种运输协议，因此我们需要选择适当的协议。常见的协议有TCP和UDP，具体内容在下章介绍，选择协议主要依据在数据传输的可靠性、吞吐量的保证、传输时间的保证以及安全性等方面的需求。

应用层协议规定了两个进程推入套接字或从套接字接受到的报文的格式，即定义了交换报文类型、报文语法、报文字段的语义。下面介绍5中应用及其使用的协议

2.2WEB和HTTP

Web应用采用客户服务器体系结构，其客户端一般为Web浏览器，Web服务器作为服务器提供内容。Web页面是Web服务器提供的内容。Web页面由多个对象组成并可以通过URL寻址，一个Web页面包含一个HTML基本文件以及一系列应用对象，Web浏览器接收到HTML基本文件后会根据其中对象URL依次再向服务器发送查询请求。

其应用层协议为超文本传输协议，即HTTP协议。HTTP定义了Web客户端向Web服务器请求页面的方式以及服务器向客户传递Web页面的方式，其使用的运输层协议为TCP协议。两个进程通过TCP协议进行通信，而TCP需要先建立连接，同时我们也知道一个完整的Web页面可能需要经过多次客户与服务器之间的请求与响应，于是有这样的问题：这些请求与响应是在一次TCP连接中完成，还是每请求一个对象就建立链接、响应后消除链接，前者称为持续连接的HTTP，后者称为非持续连接的HTTP。显然非持续性连接的开销较大，一般采用持续性连接以及流水线的方式（即所有报文一起发送，不必一个个发送）。

HTTP请求报文的一个样例如下

重要的是请求行，请求行由空格分隔了三个字符串，第一个是请求报文的类型，第二个是对象的URL，第三个是使用的HTTP协议版本。首部行的意义其名字说的很清楚了，不做赘述。

对于请求类型，最常用的是GET，用来向服务器请求URL对象，其余还有POST，用于向服务器提交表单数据（此功能也可以用GET方法通过设计URL实现）；HEAD，用于请求服务器发送一个空响应请求回答；PUT，用于上传文件；DELETE，用于删除文件。

HTTP响应报文格式如下

状态行第一个依然是HTTP协议类型，第二个是状态码，标识资源请求状态，常见的有200 OK，404 Not Found，301 Moved Permanently，400 Bad Request，505 HTTP Version Not Supported等

HTTP不保存任何关于用户的信息，可以通过在HTTP请求和响应报文中加入Cookie值并在客户端和服务器保留管理Cookie文件实现限制用户的访问并将内容与用户关联起来。

为了减少响应时间并降低网络中的通信量，会在Web服务器和客户端之间设立代理服务器，即Web缓存，其一般由ISP购买并安装，在安装Web缓存的网络中，客户端发送请求首先会被定向到缓存器，缓存器先检查其中有没有请求对象，有则直接返回，没有则由缓存器向本来应该访问的服务器请求对象，收到对象后缓存器本地备份并转发给客户端。但是缓存器中的内容可能是陈旧的，所以HTTP提供了一种机制允许缓存器检查对象是否过期，称为条件GET方法。其方法为在HTTP报文中包含对象上一次被修改的时间，缓存器使用条件GET方法向服务器发送请求，服务器响应报文中不包含对象而只是告诉缓存器对象上次修改时间。

2.3 文件传输协议FTP

在FTP会话中，客户端为FTP用户代理，服务器为FTP服务器。

FTP协议其类似HTTP，都是文件协议，最大不同是FTP协议使用了两个并行TCP连接，一个用于接收标识、口令以及其他命令，称为控制连接，另一个用于文件传输，而HTTP只使用一个TCP连接；其次FTP会记录用户状态，而HTTP是无状态的。其常见命令有USER username（用于传送用户标识），PASS password（发送用户口令），LIST（传送当前目录文件列表），RETR filename（当前目录get文件），STOR filename（当前目录set文件）

2.4 电子邮件

电子邮件系统由用户代理（类似web中的浏览器，需要在这里给出接收方邮件地址），邮件服务器和简单邮件传输协议组成。其中邮件服务器是核心，其充当了邮筒和邮箱的作用。一个邮件的发送过程是：发送方通过发送方用户代理将邮件传输至发送方邮件服务器，发送方邮件服务器将其分发到接收方邮件服务器，接收方想读取邮件时服务器通过用户名和口令严明身份后呈现邮件。如果邮件当时发送失败，发送方邮件服务器会保存报文并尝试重新发送一段时间，一段时间后删除该报文并通知发送方发送失败。

电子邮件的主要应用层协议为SMTP协议，用于从发送方的邮件服务器发送报文到接收方的邮件服务器。需要注意的是SMTP比较古老，其报文只能采用ASCII码标识，二进制数据和非ASCII字符也需要用ASCII码进行编码，且SMTP传输邮件时直接从发送方邮件服务器传输至接收方邮件服务器，不需要中间服务器。

SMTP客户和服务器交换报文的脚本例子如下：

总结为先握手建立连接，客户端提供发送方与接收方信息，然后提交报文，最后关闭连接。

邮件报文格式包含首部和信体。首部至少包含接收方和发送方地址。报文必须使用ASCII码

SMTP用于发送邮件，若是直接登录邮件服务器主机访问邮件则邮件问题到此为止，但是想通过用户代理来访问邮件服务器中的邮件需要其他协议，常用的由POP3，IMAP，和HTTP。

POP3协议在建立连接分为三个阶段，特许（验证身份），事务处理（取回报文，查看邮件统计信息，标记删除，取消标记删除），更新（断开连接，删除被标记删除的报文）。仅提供简单的邮件下载、状态查询和删除功能

IMAP协议更加复杂，在POP3的基础上允许用户在服务器上组织自己的邮件目录。

2.5 DNS

因特网上的主机的标识方法有主机名和ip地址。ip地址是一串数字，可以具体标识一台主机及其位置信息，但是难以记忆。主机名便于记忆，但是几乎没有提供信息，无法定位到主机。为便于使用，因特网使用DNS（域名系统）提供两者之间的转换服务。同时，DNS还提供主机别名、邮件服务器别名的替换功能（将别名映射为规范主机名），负载均衡分配（一个域名对应多个ip的主机，多个主机的负载均衡）等功能。

DNS一方面指一个分布式数据库，由多台DNS服务器按照层次结构组织起来；另一方面也指一个使得主机能够查询分布式数据库的应用层协议，运行在UDP之上，使用53号端口。

DNS服务器分为根DNS服务器，顶级域DNS服务器（TLD服务器），以及权威DNS服务器。根服务器中提供顶级域名对应的顶级域名服务器的地址，TLD服务器提供该顶级域名下的某个域名对应的权威服务器，权威服务器提供某个具体域名的ip地址。注意在TLD和权威服务器之间可能还有中间服务器，TLD先提供顶级域名下的某一级域名对应的中间服务器，中间服务器再提供权威服务器地址。

在查询过程中，每个ISP会提供一个本地DNS服务器，用于提供缓存和代理功能。所谓缓存就是将常访问的记录缓存到本地ISP的本地DNS中，之后再次访问记录可以直接从本地DNS中访问。代理则是替ISP中的用户发送DNS查询请求并向主机返会查询结果

一次常见的DNS查询过程如下图：

其中第一步是一次递归查询，之后由本地DNS进行迭代查询，当然也可以纯递归查询，本地将查询请求交给根，根再交给TLD，然后TLD交给权威，最后结果再一层层返回。但是这样会增大DNS核心的服务器的压力，所以将查询的压力交给数量较多的本地DNS。

DNS数据库的资源记录格式为(name,value,type,ttl)的四元组，ttl为记录在缓存中的生存时间，name和value的具体含义随type的不同而不同,对应了DNS提供的功能：

type为A则表示主机名和对应的ip地址
type为CNAME则为主机别名对应的规范主机名
type为MX则为邮件服务器的别名和真实邮件服务器名
type为NS则为域名对应的权威服务器的主机名

2.6 P2P应用

采用CS模式分发文件时，设有N个用户请求文件，文件大小为F，服务器上行传输带宽为，用户上行和下行带宽为，，所有用户都得到文件的时间为。

而采用P2P模式时，最大的改进在于服务器，或者说提供内容的主机的带宽大大增加，设最初的资源依然是由服务器发送至P2P社区的，则分发时间为

BitTorrent是一种用于文件分发的流行P2P协议，将参与一个特定文件分发的所有对等方的集合称为洪流，在一个洪流中的对等放彼此下载等长度的文件块（典型长度为256kb）。每个洪流具有一个基础设施节点，称为追踪器，用以跟踪正参与在洪流中的对等方。

一个对等方请求文件时，追踪器从洪流中选择一个子集，将其IP地址列表发送给请求方，请求方根据列表试图与对等方建立并行的TCP连接，然后周期性询问建立了连接的对等方（称为临近对等方）他们具有的块列表，对自己没有的块发出请求，在这个过程中，会优先请求副本最少的块，这个过程称为最稀缺优先；同时由于一个块被多个对等方拥有，为了保证传输速率的协调，请求方每10秒重新确定4个最高速率的对等方，优先响应这些邻居的传送请求，同时每30秒他会另外一个邻居发送块，这是我们的请求方与这个邻居可能同时互为前4位上载者之一，这样可以时请求方的前四位上载者在作为请求方时可以获得协调的速率。

第三章传输层

3.1概述和运输层服务

运输层的功能是为不同主机上运行的应用进程提供逻辑通信通道。其一般分为发送方和接受方，发送方的内容为将应用数据划分为报文段，交付给网络层，接收方的工作内容为将报文段重组为应用数据，交付给应用层。

不同运输层协议提供的服务不尽相同，主要表现一些细节如是否保证数据送达、是否保证提交数据有序、是否有其他控制等方面。

运输层协议依赖于网络层，故其受网络层限制，但是也能够提供一些网络层不提供的服务。

因特网为应用层提供的运输层协议主要有TCP（传输控制协议）和UDP（用户数据报协议）两种，其基于的网络层协议为IP协议（网际协议），底层的IP协议几乎不提供任何保证服务，即无法控制时延、丢包、报文到达次序等等，仅负责在不同主机之间尽量传递数据，称为尽力而为交付服务，是一种不可靠的服务

3.2多路分解与多路复用

由IP协议提供的服务内容可知，运输层协议基本责任是将主机间的交付扩展到进程间的交付，前面在应用层协议中我们知道表示主机上的进程是通过套接字完成的，所以这项工作也是依靠套接字完成。

将运输层报文段中断数据交付到正确的套接字的工作称为称为多路分解（将混在一起的一台主机上的报文分解到各个套接字对应的进程）；在源主机从不同套接字中收集数据块并分装然后将本文段传送到网络层的工作称为多路复用（将不同套接字的数据封装后以一台主机的名义发出去）

多路分解和多路复用的关键在于套接字的识别，所以在运输层报文段中都含有源端口号和目的端口号。

对于套接字，具体的，对于UDP，其套接字由一个二元组来表示，其包含一个目的IP和目的端口号；TCP套接字由四元组组成，即源IP，源端口，目的IP，目的端口。UDP和TCP套接字最大的区别是，对于UDP，目的IP，目的端口相同时只有一个套接字，由该进程的IP和端口标识，对TCP，目的IP，目的端口相同时有多个套接字，不同客户请求在不同的套接字中处理（多进程，或者更一般的，多线程）。

3.3无连接运输：UDP

UDP仅提供一个最简单运输层协议提供的服务，即多路复用/多路分解服务以及差错检查。其报文段结构如图所示

源端口和目的端口号用于多路复用以及多路分解，长度指示整个报文段的长度（首部加数据），检查和用于差错检测。差错检测的具体操作是：发送方对报文段（除检查和，因为这一步就是计算出检查和）中所有16比特字的和（溢出位要回卷到最低位参与运算）取反得到检查和，并写入报文，接收方计算接收到的报文段检验和（这时包括发送方的检查和），若不为全1则说明有错，全为1则大概率没错。

UDP的优点有：无需建立链接，实现简单，报文段空间开销小（首部很短），没有任何拥塞控制，所以对某些要求高速率且能够容忍丢包的应用可以选择UDP。但是由于UDP没有拥塞控制，大量使用UDP会使网络中数据大量增加造成丢包。

3.4 可靠数据传输原理

本节使用有限状态机描述底层信道在不同情况下，用有限状态机（FSM）描述运输层进行可靠数据传输时的行为。现对有限状态机的描述做出以下规范：

状态用圆圈表示
箭头表示发生状态变迁，箭头的描述中横线上方是引起状态变迁的事件，下面是状态转换过程中的动作
rdt前缀代表可靠传输，是运输层需要提供的服务，因此一般是事件（即上层调用rdt函数），udt是底层信道提供的功能，运输层可以使用，属于动作。

rdt1.0

本模型假设底层信道完全可靠，不会产生比特错误和丢包，则发送方和接收方的有限状态机如下图所示，只需要双方只需要像UDP一样运行就可以了（甚至不需要提供差错检测）。

rdt2.x

本模型假设底层信道可能出现比特差错，但不会有丢包，此时需要引入重传机制重新传送出错的数据，这也意味着接收方在检测完差错后要发送确认信号给发送方检测结果。首先考虑确认信号不会出错的rdt2.0，FSM如下

本模型中发送方发送一个数据包之后加入等待回复的状态，然后根据恢复决定重传还是传下一个，接收方根据接受的数据的对错，对则上交给应用层，错误则丢弃错误数据，两种情况下都要发送确认信息。

现在考虑确认信号也会出差错的情况rdt2.1，我们的解决办法是如果发送方接收到的数据包发生差错或者接收到接收方未正确接受的信号则重传，这就造成一个问题，接收方无法判断接受到数据包是重传的还是新发的，即信道中存在冗余分组。解决办法是为数据包加上编号，假设接收方本次正确接收到0号，发送确认后进入等待1号的状态，而发送方处于刚发送0的状态，如果确认数据包错误发生重传，会重传0，此时接收方可以根据序号丢弃本次收到的重复数据包，同时发送ACK让接收方鳖传了，烦不烦，FSM如下

引入序号之后，NAK就显得多余了，毕竟接收方能根据序号判断数据包对错，发送方不也能够根据序号判断一手吗，于是改进的无NAK rdt2.2，即给ACK赋予一个序号的性质（实际操作中，可以直接拿序号当ACK）以取代NAK。FSM如下

rdt3.0

本模型假设底层信道不可靠，即可能发生比特错误有可能发生丢包。若发生丢包，双方有一方什么都接收不到，因此要引入一个新的机制，即超时重传，若发送方在规定时间内没有收到接受方的确认，就进行重传。重传可能造成冗余分组，而rdt2.1已经解决了这个问题。发送方FSM如图：

接收方与rdt2.2一致。

在rdt1.0至rdt3.0中，每发送方每发送一个数据包就进入等待ACK的状态，这期间通信阻塞，效率很低，称为停等协议。实际应用过程中，为了提高效率，采用流水线技术，允许发送方以非阻塞的方式一次发送多个数据包。

流水线批处理数据包时，需要用更多的序号来标识数据包以判断需要发送了那些数据包，哪些数据包收到确认了，需要重传的是哪个数据包。由于已被传输但还未确认的分组的许可序号范围可以看作是一个序号范围大小为N的窗口，这个窗口被称为滑动窗口

针对解决差错的恢复方法，流水线技术有以下两种思路：回退N步和选择重传。

GBN

在GBN协议中，设窗口的基序号为base，即最早发出但未收到的确认的报文，窗口长度为N，下一个待发送分组的序号为nextseq。一般的，序号有一定的位数限制，意味着base有一个最大值，报文的序号需要对这个最大值取余。

GBN的FSM图如下

发送方在窗口没满的情况下，直接将上层传下来的数据包发送出去，并更新nextseqnum，若满了则拒绝数据（或是缓存起来，或是通知上层待会再发）。

对于计时器，GBN只会启动一个定时器，该定时器在窗口中发送第一个包时启动，在窗口中元素全部清空后停止，在收到窗口中某一个数据的确认时重启。能够如此设计计时器的原因是，接收方只会接受其需要的序号的数据包并发送其确认，否则发送上一次的确认，由于序号是连续的，意味着接收方发送的确认代表该序号之前的数据全部已经收到，称为累计确认。所以即使接收方没有收到1的ack但是收到了2的ack，依然可以将base更新为3，表示1、2已经接收到了，并且计时器表示窗口中所有元素是否超时，故更新base后需要重启（因为窗口改变了），由于计时器的性质，GBN重传时需要重传窗口中所有的已经发送但是没有收到确认数据，由于这个特性，所以称本协议为回退N步协议。

SR

GBN在窗口长度和带宽时延积都很大时，可能会引起大量的重传，传送效率极低，于是我们有选择重传（SR）协议。

在选择重传中，发送方发送数据的动作与GBN一样，但是会为每个分组都设置一个定时器，超时后之重传该分组。

在接收方，同样有一个窗口，若发送来的数据包序号正好在窗口内则将其缓存，若窗口首部数据包被接受则向上层交付从窗口首部开始的连续序号的数据包。只要收到的数据包没有出错就要给发送方发送一个ack（因为每个数据包都有一个定时器，不接受ack定时器就不会停下来，发送方就一直发）

在序号有一定范围的时候（比如序号只有三位，则是从0到7），为了区分一个分组是由于发送方没有接收到ack而重发的分组（这种分组应该丢弃）还是一个新的分组（这种分组应该接受），因要求窗口长度小于或等于序号空间大小的一半。

TCP

TCP被称为是面向连接的协议，其只运行在两个端系统中，是点对点的，中间网络元素不会维持TCP状态。同时TCP连接提供全双工服务，即建立了TCP连接的主机是可以相互发送数据的。我们从一下几个方面了解TCP

报文结构

TCP报文首部结构如下，首部之后跟着的数据长度通常等于MSS，即由最大链路层帧长度确定的最大报文段长度。一个应用层数据往往被分割为多个长为MSS的数据（最后一块可能小于MSS）。（这里注意MSS不包括首部，一般来说要求MSS加上TCP首部和IP首部小于最大链路层帧长度）

其中源端口和目的端口用于多路分解和多路复用，检验和用于检查数据包是否出现问题，首部长度标识20字节固定首部长度和选项长度共同构成的TCP首部长度，这些与UDP类似。

序号与确认号用于可靠传输连接，窗口字段用于流量控制，分别对应TCP的两大功能。

剩余的部分有六个比特组成的标志字段，其中ACK用于标识确认字段中的值是有效的，RST，SYN，FIN用于连接的建立和拆除（ACK也参与了连接的建立）。

UGR，PSH和十六个比特的紧急指针用于提示接收方上交数据，其中PSH被设置后指示接收方将所有数据提交给上层，URG被设置后指示接收方报文中存在紧急数据，紧急数据一般在报文前面，其最后一个字节用紧急指针指出，是否上交看接收方心情。这几个字段几乎不使用。

TCP的可靠传输原理

序号和确认号的规定：TCP把缓冲区的数据看成字节流并按字节编号，而报文段的序号是在报文段数据中第一个字节在字节流中的编号，确认号为期待收到的报文段号，由于TCP是全双工的，双方的缓冲区各自有各自的编号，所以可以这么干，这种确认被称为稍带确认。起始编号在建立连接时确定。

接收方与发送方的序号交流：TCP在确定了序号和确认号之后，接收方的TCP也使用累计确认，即接收方发送的确认号为tcp建立时确认的起始编号起，连续的报文段中最大的报文的序号。但不同与GBN，对失序到达的报文，TCP没有规定应该怎么做，常用的办法是缓存失序的报文，例如接收方接受到了0~555号报文以及888~999号报文，回复给发送方的报文中，确认号依然是556，假设之后又收到了556~887号报文，接收方的确认号就会变为1000，此时对于接受方，虽然没有收到888到999号报文，但根据累计确认的原则，依然可以确定接收方接收到了887到998的报文，并依此滑动发送窗口。

重传时间确定：针对报文的损坏或丢失，TCP也采用超时重传机制。作为实际应用中的通信协议，应该要考虑如何规定超时，首先超时时间起码要大于一次传输往返时间（RTT），TCP对RTT的估计方式为：TCP会在某个时刻测定一次RTT作为样本RTT（SampleRTT），同时维护一个平均RTT（EstimateRTT），其初始值为SampleRTT，之后会在获得新的SampleRTT时做出如下更新

值一般设为0.125，同时还会维护一个差值用于评价当前估计值的偏差

值一般为0.25。依据上面两项指标，超时时间被设定为

有了上面的规定，我们可以描述TCP的可靠数据传输。当数据没有问题时，按照序号与确定号的规则进行窗口的滑动。当出错时，使用超时重传和冗余确认技术进行重传。

TCP的发送端维护一个定时器，当定时器未启动且需要发送数据时启动定时器（换言之，对于一批发送的数据，只在发送第一个数据时启动定时器）。如果收到正确的确认，则将窗口的base移动到确认号的位置（累计确认）如果窗口中依然有未确认的报文，重启定时器。如果定时器超时，重传最近未接收到确认的数据。

TCP的接收方的行为在上面序号交流的部分论述过了。在超时重传中需要注意的是当超时事件发生时，考虑到很可能是发生了网络拥塞，TCP会将超时时间间隔延长一倍而不是按照上面的公式计算超时时间间隔，直至收到了确认或收到上层数据需要发送，称为超时间隔加倍。

由于超时重传的时间间隔可能比较长，为了提高重传效率，TCP还使用冗余重传技术，又称快速重传，即收到3个冗余的ACK后立即重传这个ACK期待的报文段。（一个显然不行，因为很有可能乱序到达，当然当窗口很大时无论收到多少个冗余ack都可能是乱序到达，但是设置接受太多冗余ack有违快速重传的目的，于是设置3个冗余ack这样一个比较合适的数字）

TCP连接管理

TCP连接的建立需要经过三次握手：

第一步：客户端TCP向服务器端TCP发送一个不承载数据的特殊报文段，该报文段中SYN置为1，并设置起始序号告知服务器端，（此时ACK没有意义，所以标志位中的ACK为0）。该报文段被称为SYN报文段
第二步：服务器端接收到SYN报文段后会为TCP连接分配TCP的缓存和变量，然后向客户端发送一个不承载数据的特殊报文段，其中SYN置为1，同时设置自己的序号，将接收到的序号加1作为确认号（此时ACK有意义，标志位中的ACK变为1）。该报文段被称为SYNACK报文段
第三步：客户端收到SYNACK报文段后，也为TCP分配缓存和变量，并向服务器端发送一个报文段，该报文段可以承载数据，序号为报文序号，确认号为收到的确认号加1，SYN置为0表示连接已经建立，当然ACK也为1，这个报文段和后面的普通报文段一样。

类似人类的交流，比如A，B要开始交流，首先A向B提出交流的申请（SYN为1），通报自己的信息（设置初始序号），这是第一次握手；然后B回应申请（SYN为1），通报自己的信息（设置初始序号），并告知自己知道了对方的信息（ACK为1），这是第二次握手；之后A告诉B自己也知道了B的信息（ACK为1），可以开始交流了（承载数据，并设SYN为0表示憋客气了，咱俩谁跟谁），这是第三次握手。

TCP连接的终止需要经过四次挥手。四次挥手是两轮一样的过程，提出结束TCP连接的A发送FIN为1的报文段（FIN平时为0）给B，B接收到后发送一个ACK给A，然后B也发送FIN为1的报文给A，A返回一个ACK给B，经过一个定时等待之后（防止B没收到ACK而重传FIN但是没人理他）A关闭资源，B收到ACK后关闭资源。

以上讨论的是客户端向服务器发送请求后服务器也会应答的情况，假设服务器不会应答，比如客户端向服务器的80端口套接字发出建立TCP的请求，但服务器在80端口没有运行相应的程序，则服务器会发送一个RST置为1的报文告诉客户端憋发了。（如果是UDP，服务器会发送一个特殊的ICMP报文）

TCP的流量控制

TCP连接每一侧主机都为该连接设置了接受缓存，为消除接收缓存溢出的可能性，TCP为应用进程提供流量控制服务。其基本思路是对发送方进行遏制。

TCP通过让发送方维护一个称为接收窗口的变量来提供流量控制，记为rwnd。现设接收方缓存大小为RcvBuffer，接收方应用进程从缓存中读取的数据流最后一个字节的编号为LastByteRead，从网络中到达且放入缓存的最后一个字节编号为LastByteRcvd，则有以下关系

发送方rwnd的值通过接收方发来的TCP报文中的窗口字段调整。同时发送方会跟踪最后一个发送的数据编号LastByteSent和最后接收到ACK的数据编号LastByteAcked，显然这两个字段应保证

显然不等式左边的值其实就是流水线滑动窗口的大小。

最后一个问题是假设发送方主机rwnd变为0以后，发送方和接收方之间不会再有数据的交换，那么假设发送方的数据还没发完，发送方如何知道接收方的缓冲区已经有空闲可以继续发了呢，方式是TCP规定当接收方接收窗口为0时，发送方继续发送只有一个字节数据的报文段，如果接收方缓存依然是满的则这个报文段会被忽略，否则会返回发送方一个rwnd不为0的报文，此时通信可以继续进行。

TCP拥塞控制

由于网络变得拥塞时会使数据包的传输产生较大时延甚至丢包，因此需要进行网络的拥塞控制。其基本思路和流量控制类似，也是对发送方进行遏制。

网络拥塞的代价有以下几点

当分组的到达速率接近链路容量时会产生较大的排队时延
当由于路由器缓存溢出产生丢包时，在超时时间间隔过短时，可能会造成一些不必要从重传来占用链路带宽
当下游路由器丢弃数据包时，上游路由器的工作就被浪费掉了（即当下游路由器阻塞严重时，上有路由器不如直接把数据包丢掉，毕竟到了下游也会被丢掉，而且转发数据包是有开销的）

拥塞控制主要有两种方法，一种是端到端的拥塞控制，即网络层不提供拥塞控制的显式支持，TCP采用这种形式；一种式网络辅助拥塞控制，即网络层构件会向发送方提供关于网络中拥塞控制状态的显式反馈信息，或是通过网络路由器直接反馈，或是路由器对发送的信息进行标记然后经由接收方反馈，网络辅助拥塞控制的例子有ATM ABR拥塞控制，其通过在数据信元（ATM术语，就是分组）中夹杂资源管理信元，资源管理信源用于承载拥塞控制反馈信息，既可以通过网络直接反馈也可以经由接收方反馈。

对于TCP的拥塞控制，和流量控制类似，让发送方跟踪一个变量，拥塞窗口，记为cwnd，用以限制发送速率，显然结合流量控制，我们有

对于TCP，由于采用端到端的拥塞控制，其判断拥塞的方法为：要么出现超时，要么接收到三个冗余ACK。为了尽可能利用网络带宽又避免出现拥塞，TCP采用如下的拥塞控制算法

慢启动：当TCP连接开始时，cwnd设置为1个MSS值，一旦收到一个确认，就将cwnd更新为2个MSS，收到两个确认后再将cwnd更新为4，以此类推，即在慢启动过程中，cwnd与发送的轮回成指数增长，第n个轮回（n从0开始计算）窗口长度为2ⁿ个MSS。慢启动结束条件有三个：
- 发生超时：说明发生重度拥塞，此时将cwnd设置为1并重新开始慢启动，并设置慢启动阈值（ssthresh）为发生超时时cwnd值的一半。
- 达到或超过ssthresh值：进入拥塞避免状态
- 检测到3个冗余ACK：发生轻度拥塞，进入快速恢复状态
拥塞避免：进入拥塞避免状态后cwnd每次增加一个MSS。拥塞避免结束的条件有两个：
- 发生超时：说明出现了严重拥塞，将cwnd设为1，ssthresh变为发生超时时cwnd的一半，进入慢启动。
- 检测到三个冗余ACK：发生了轻度拥塞，进入快速恢复状态
快速恢复：快速恢复是TCP推荐而非必须的构件，在TCP Tahoe中无论若出现3个冗余ACK同样是将ssthresh设为cwnd的一般，cwnd设为1，进入慢启动，而在TCP Reno中，发生快速恢复时ssthresh设为cwnd的一半，但是cwnd设为原来cwnd的一般加3进入拥塞避免状态。

由于慢启动过程中cwnd指数增长，很快就会进入拥塞避免状态，所以TCP的拥塞控制可以看成一个加性增，乘性减的过程，即超过ssthresh后线性增，超时或快速重传发生时减半（忽略慢启动从1到ssthresh的过程，将快速回复的加3近似为没加）。假设发生丢包时的窗口大小为W，往返时间为RTT，则高度理想的情况下，一条连接的平均吞吐量为

由于拥塞控制，假设所有用户的RTT是相同的，TCP可以使用户获得公平的带宽，这是UDP做不到的，但实际上公平是很难做到的，特别是TCP还可以并行链接抢占带宽。

第四章网络层

4.1网络层概述

在一个网络中，一般路由器都只有从网络层开始往下的协议栈。网络层的目标是实现主机到主机之间的通信（运输层则是实现进程之间的通信），其最重要的功能是实现转发和路由选择，对于面向连接的网络层可能还要求建立连接（如ATM，帧中继，MPLS等）。本章重要的网际协议（IP协议）主要要求实现转发和路由，转发和路由有时可以混用，其区别在于看待问题的角度，转发是路由器本地动作，而路由是在网络范围的动作。

转发是指当分组到达路由器的一条入链路时，路由器将分组移动到适当的出链路，其主要涉及路由器的内部结构。
路由选择是指分组从发送方流向接收方时决定采用路径的方法，主要涉及路由选择算法。

每台路由器有一张转发表，路由器通过检查到达分组的首部字段的值，并通过该值在转发表中索引查询以确定转发路径，分组首部和转发表的内容确定的规则取决于网络层协议，本章主要讨论IP协议

接下来确定几个术语，分组交换机是指通用分组设备，根据分组首部字段确定如何转发分组，其中根据链路层字段值做转发决定的交换机称为链路层交换机，根据网络层协议做转发决定的称为路由器。

能由网络层提供的服务有：确保交付，确保时延，确保交付顺序，确保带宽，确保安全性等，好消息是因特网的网络层几乎啥都不干（指不用学ATM这些复杂的网络层协议），称为尽力而为的服务。几种实际使用的网络层服务模型如下表所示

网络体系结构	服务模型	带宽	无丢失保证	排序	定时	拥塞指示
因特网	尽力而为	无	无	无	不维持	无
ATM	CBR	保证恒定速率	有	有序	维持	无拥塞
ATM	ABR	保证最小速率	无	有序	维持	提供指示

4.2 虚电路和数据报网络

两者在第一章中已经提到过。虚电路网络属于提供连接服务的网络，而数据报网络属于提供无连接服务的网络。因特网属于数据包网络，前面提到过的提供连接服务的ATM，帧中继属于虚电路网络（纯废话）

一条虚电路的组成包括：源和目的主机之间的路径，VC号，沿着该路径每台路由器中的转发表表项。其在数据开始流动之前要先呼叫建立,每一个分组携带一个虚电路的标识，同时路由器必须为连接维持连接状态信息，链路和路由器资源会被分配给虚电路以达到类似线路交换的性能，最后流动结束后要断开虚电路的连接。端系统向网络发送指示虚电路启动与终止的报文以及路由器之间传递的用于建立虚电路的报文称为信令报文，交换报文的协议称为信令协议。

在数据包网络中，网络层不存在连接的概念，传输报文使用目的主机的地址信息（虚电路中使用VC号）。路由器使用分组的目的地址在转发表中查找输出链路接口，，查找使用最长前缀匹配规则，即路由器转发表中只有一系列前缀，一个分组的目的地址和这些前缀进行比较，若匹配上则在相应端口转发，若有多个匹配上则按最长匹配项操作

4.3 路由器工作原理

路由器工作原理设计网络层的转发功能。路由器的体系结构如下图所示

图中上半部分称为路由器控制平面，用于执行路由选择，一般由软件实现，在毫秒或者秒的时间尺度上运行。下半部分由输入端口，输出端口，交换结构组成的部分称为路由器转发平面，实现转发功能，一般由硬件实现，在纳秒的时间尺度上运行。下面介绍转发平面的几个部件

输入端口：将输入的物理链路与路由器相连接（物理层），进行数据链路处理（链路层，对数据进行拆封），并按照规则查找数据输出链路并转发。
交换结构：一个连接输入端口和输出端口的网络，可以是一个互联网络，可以是一条总线，也可以是一个内存。
输出端口：将交换结构中的分组取出，进行链路层处理，通过端接链路发送。

在输入端口和输出端口中靠经交换结构的部分都有一个缓存，会形成分组队列。当交换结构的速度过快，会导致输出端口排队，此时需要决定先发出哪个分组，决定的策略有先来先到调度（FCFS）或其他复杂的加权公平排队（WFQ），而交换结构的速度过慢又会导致输入端口排队，输入端口一般就按照FCFS的方式处理分组，这种情况下的阻塞称为线头阻塞。

排队会造成高时延，在排队过长缓冲区溢出后会出现丢包。丢包同样需要采取一定策略，被动策略有弃尾策略或者删除一个或多个以排队分组，主动队列管理主要有随机早期检测算法，该算法随时计算平均队列长度，同时维护一个最小阈值和最大阈值，平均队列长度小于最小阈值时允许分组入列，大于最大阈值时标记分组或者直接丢弃，其他情况按照概率标记或丢弃分组。

4.4 网际协议

因特网网络层有三个组件，分别是IP协议，路由选择部分和报告数据报的差错以及对某些网络层信息请求进行响应的设施。本节主要讨论IPV4和IPV6。

IPV4的报文格式

IPV4的数据报格式如下

版本号标识IP协议版本，不同版本的数据报格式不同；首部长度根据可变部分不同而不同，固定部分的长度为20字节；服务类型标明流量类型或优先级；总长度是首部加上数据的长度；标识标志和片偏移用于IP分片；生存时间（TTL）用于保证数据报不会永远在网络中，是数据报能经历的最大跳数；协议用于指定数据向哪个运输层协议交付；首部检验和用于检验报文是否出错，每个路由器都要算；地址用于通信，选项很少使用。

由于一个链路层帧能承载的最大数据量（最大传送单元，MTU）有限，一次通信会经过不同的链路层，我们无法知道这些链路层的MTU，当某个链路的MTU大于某个IP数据报时，需要对数据报进行分片为更小的数据报，用单独的链路层帧进行封装。

切片虽然由路由器进行，但是组装由端系统进行。端系统在处理IP数据报时首先需要确定该报文是否是片，然后需要知道片的序号以及是否收到最后一片，这就有标识，标志和片偏移负责。发送IP报文的主机会为他发送的每个数据报标识号加1，如果有分片，分片的标识号应该是相同的；为了识别分片的序号，使用偏移插入数据开始的位置；为了知道是否收到最后一片，不是最后一片的标志位为0，其余为1。

IPV4地址分配

连接主机、路由器之间的物理链路与主机的边界称为接口，IP地址是与接口关联的32位标识符，一般用点分十进制表示。

IP地址由网络号和主机号构成，网络号在前面，主机号在后面。在如图所示的网络中

可以看到LAN1中，两台主机和一个路由器接口前24位IP地址相同，像这样一个局域网称为一个子网，一个子网中的接口的IP的网络号相同。该子网可以记作222.1.3.0/24表示前24位是子网，也可以给出子网掩码255.255.255.0，一个子网中任意一个接口的IP地址与子网掩码按位与即可得到子网地址。注意除了途中LAN1，LAN2，LAN3是子网两个路由器之间也是子网。

因特网地址分配策略称为无类别域间路由选择（CIDR），其本质是将子网寻址的概念一般化，即将一个组织看作一个子网，一个组织有相同的前缀类似于一个子网中的IP有相同的网络号，将网络地址层次化便于路由寻址，即可以采用最长前缀匹配，因为前缀越长子网范围越小。

在CIDR采用之前，IP地址的网络部分被限制为长度为8，16或24比特，称为A、B、C类网络分给不同的组织。

DHCP

当一个组织获得一块地址之后，它可以手动为组织内的主机和路由器分配IP地址。但是要为手动为主机分配IP地址不现实，毕竟主机可能移动，可以使用动态主机配置协议（DHCP）来完成自动分配IP地址。

DHCP是一个客户-服务器协议，客户是新到达子网的主机，服务器则是DHCP服务器，在最简单的场合下，一个子网拥有一个DHCP服务器或一个DHCP服务器代理（通常是一台路由器）。主机通过DHCP自动获得IP地址的过程是：

DHCP服务器发现：新到来的主机将0.0.0.0作为自己的IP地址，广播地址255.255.255.255作为目的地址向67号端口发送DHCP发现报文
DHCP服务器提供：DHCP服务器收到发现报文后依然通过广播地址对客户做出响应（依然使用广播，因为主机还没有IP地址），响应包括收到发现报文的事务ID，向客户端推荐的IP，网络掩码以及IP地址有效的时间
DHCP请求：客户会收到一个或多个服务器提供响应，客户会从中选择一个服务器提供，并回应一个DHCP请求报文，回显配置参数
DHCP ACK：服务器用DHCP ACK报文对DHCP请求报文响应，证实参数

NAT

当某一区域IP地址不够用时，可以采用网络地址转换（NAT）技术，使本地网络只要使用一个IP地址就可以和外部网络相连。

NAT的具体实现需要一台NAT是能路由器。以一个家庭网络为例，家庭网络中的所有设备连接一个NAT使能路由器，家庭网络中的设备可以有自己的IP地址，但是在向外界发送数据时，数据经过NAT使能路由器时每个外出报文的源IP地址,端口号会被替换为NAT IP地址以及新的端口号，同时路由器记住每一个地址转换对 (在 NAT 转换表中，NAT的一个端口号对应家庭网络中一个主机的一个端口) ；同理接收数据报时根据收到数据的端口号（IP地址必然是NAT路由器的地址）将数据派送到对应主机的端口。

NAT对外表现就是一个具有单一IP的单一设备，隐藏了其背后的网络，所以其背后的网络可以随意编址，有效解决了地址不够用的问题。但是NAT使用端口号进行主机编制，且需要改变主机运输层报文的内容，违反了端到端原则。同时NAT会妨碍P2P程序（因为一方若在NAT背后时无法充当服务器角色），解决方法有连接反转（假设A在NAT背后，但是有一台不在NAT背后的B与A有TCP连接，C想和A进行P2P，可以通过B向C发起建立TCP连接的请求）。

NAT还可以有UPnP提供，即允许主机配置临近NAT，类似DHCP分配IP地址，UPnP允许主机请求NAT上一个端口绑定主机

ICMP

因特网控制报文协议（ICMP）是前面所说的网络层三组件之一，用于用于主机、路由器、网关之间交换网络层信息，如返回错误报告或进行回声请求，应答（ping）等。

ICMP报文封装在IP报文之中，包含一个类型字段和一个编码字段格式如下

不同类型和编码的功能如下

IPV6

IPV4的地址已经被分配完，同时考虑到IPV4的设计不合理之处（如首部长度不固定，安全性不够高等），人们设计了IPV6，其报文格式如下：

IPV6最大的改变就是地址扩容为128位，同时不设检查和，检查交给运输层和链路层，不允许分片，如果路由器收到的IPV6数据报太大就直接丢掉并回复发送方让发送方用较小的数据报重发报文。删除选项字段，增加下一个首部字段，下一个首部可以是运输层首部，也可以是一个选项。当然下一个首部中一般是指出运输层协议（IPV4的协议字段）。剩下的流标签用于指出特殊流。

从IPV4到IPV6的迁移有以下几种建议

设立标志日统一迁移（不太可行）
双栈技术：新加入设备同时支持IPv4和IPv6，一段链路上，如果源和目标均支持IPv6，则使用IPv6进行通信如果任一方不支持IPv6，则使用IPv4进行通信可能会出现信息的丢失（IPv4和IPv6报文字段不完全对应）
隧道技术：IPv6报文在IPv4链路上传输时，将IPv6报文封装在IPv4报文中，接收方接收到IPv4报文后可以知道其中封装了IPv6报文，取出即可。

4.5 选路算法

将一台主机直接连接到的路由器称为主机的默认路由器，在一次通信过程中，将源主机的默认路由器称为源路由器，将目的路由器的主机称为目的路由器。选路算法的目的是找到一条从源路由器到目的路由器的好的路径（指满足所有规则的同时花费最小的路径）

可以用图来形式化描述路由选择问题，节点为路由器，边为路由器之间的链路，边的权重可以用来表示路径费用，那么路由选择问题相当于求源节点到目的节点的最短路径。

路由选择算法根据算法是全局式的还是分布式的可以分为全局式路由选择算法和分散式路由选择算法。根据是静态的还是动态的可以分为静态路由算法和动态路由算法。根据是否与负载有关可以分为负载敏感算法和负载迟钝算法。

链路状态路由选择算法（LS算法）

在链路状态路由选择算法中，网络拓扑和所有链路的费用是已知的，这些信息通过每个节点向网络中其他所有节点广播得到。常用的链路状态路由算法有Dijkstra算法。算法伪代码如下：

Initialization: 
	N' = {u} //N'为已确定最短路径的节点集，初始只有源节点
	for all nodes v 
	if v adjacent to u 
		then D(v) = c(u,v) 
	else D(v) = ∞ //更新初始所有点到源节点的距离D(v)，即与源节点点相邻的距离为c(u,v),不相邻的为无穷
//开始迭代
Loop 
	find w not in N' such that D(w) is a minimum //对当前距离源节点最近的点w，认为其找到了最短路径，加入N'
	add w to N' 
	update D(v) for all v adjacent to w and not in N' : //更新D，D要么不变，要么更新为从w再到源节点的距离
	D(v) = min( D(v), D(w) + c(w,v) ) 
until all nodes in N' 

该算法的时间复杂度为O(n²)，可以用堆将其复杂度降低为O(mlogn)。

对LS算法，假设链路费用于其负载相关，路由选择可能会出现震荡（因为代价一直在变，可能会出现第一次运行LS选A路，第二次选B路，第三次又选A路），解决的方法之一是强制链路费用不依赖于所承载的流量，这是不可行的。解决方法之二是保证不是所有路由器同时运行LS算法，由于因特网上路由器能够自同步，还需要随机化路由器发送链路通告的时间

距离向量路由算法（DV算法）

DV算法基于Bellman-Ford公式，设x到y的最低费用为d_x(y)，邻居集合为V，则。DV算法的基本思想如下：

对N中的所有节点，估计从他自己到其他所有节点的费用，构成距离向量（一开始到不了的距离是无穷），然后对每个节点，维护下列路由选择信息：

对每个邻居，从x直连邻居的费用
邻居发送自己的距离向量
根据邻居的距离向量以及自己的距离向量，利用Bellman-Ford公式更新距离向量

DV算法对链路费用的变小的敏感度大于变大的敏感度，这个特性称为好消息传的快，坏消息传的慢。因为A节点的某个链路费用变大时，其依然会选择费用最小的链路，即使这个费用最小的链路需要经过B节点，而B节点达到最小链路需要经过A节点费用变大的链路，这样会造成多次迭代路由表才能稳定下来，这个问题称为无穷计数问题。为了解决这个问题，可以增加毒性逆转技术。假设有x,y,z三个节点互联，假设z到x的最短路径需要经过y节点，那么z会告诉y其到x的距离是无穷。需要注意的是当设计到3个或更多节点时，毒性逆转技术无法检测环路。

LS与DV比较

报文复杂性：LS要求发送的报文多，DV每次只需要向邻居发送报文
收敛速度：LS收敛速度快，DV收敛速度慢，甚至可能碰到无穷计数问题
健壮性：LS有一定健壮性，而DV一个不正确的结点计算值会扩散到整个网络

层次路由选择

当网络规模越来越大时我们无法采取上述将所有路由器放在一起运行选路算法，同时由于某些组织要求管理自治，应该允许这些组织自己决定路由选择算法而不是ISP统一安排。

解决的办法是将路由器聚合到一个自治系统（AS）内，在相同AS的路由器可全部运行同样的选路算法，称为自治系统内部路由选择协议，AS之间互联通过网关路由器。AS内部选路算法为内部目的地址设置转发表信息，AS内部选路算法和AS间选路算法共同为外部目的地址设置转发表信息。

AS内部的转发很好解决，要解决AS间的路由，显然需要该AS知道通过其相邻的AS可以到达那些目的地，并向该AS中所有路由器传播这些可到达性信息，这由AS间路由选择协议处理。

当一个目的地为子网x的分组到达一个AS时，假设已知可以通过多个其他AS使x达到目的地，为选择一个路径，采用热土豆路由选择，即该AS会尽可能快的扔掉分组。

4.6 因特网的路由选择

AS内路由选择

又被称为内部网关协议，主要有路由信息选择协议（RIP协议）和开放最短路优先协议（OSPF）。

RIP协议将相邻两点间的链路上的费用定义为1，经过一个路由器称为一跳，一条路径的最大费用限制为15跳，采用DV算法，选路信息每30S在邻居之间以RIP响应报文的形式进行交换，180S未收到邻居信息则认为邻居已经离线。运行在UDP上，端口号520

OSPF协议各条链路费用不固定，由管理员设置，采用Dijkstra算法，链路状态发生改变时立即改变链路状态，即使链路状态不改变也会30分钟广播一次链路状态。OSPF链路状态以OSPF通告的形式封装在OSPF报文中，由IP分组承载，上层协议值为89（）意味着OSPF协议必须自己实现可靠报文传输、链路状态广播等功能。OSPF有以下优点：OSPF路由器之间的交换都是经过鉴别的（简单的、MD5的），以确认OSPF通告的真实性，防止伪造和篡改OSPF通告都是有序列号的，以防止重放攻击；OSPF中支持多条具有相同费用的路径；OSPF支持多播选路和层次路由。

AS间路由选择

AS间路由选择使用边界网关协议（BGP协议） _{一开始看第六版教材嗯是没看懂，后来找的第七版}

BGP为每个AS提供一种手段以进行以下工作：

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

在BGP中，路由器会通过运行在179号端口的半永久TCP交换信息，这些TCP根据是连接AS内路由器还是网关路由器分为iBGP和eBGP，如下图所示

交换的信息主要包括：某个AS的前缀x（现在因特网一般采用CIDR编制，若AS有多个完全不同CIDR前缀则再通知一条即可，反正是最长前缀匹配），ASPATH（性包含了通告已经通过的AS的列表），NEXT-HOP（是AS PATH起始的路由器接口的IP地址，如AS2向AS1通报，则其NEXT-HOP为路由器2a连接1c的端口的IP地址）。当然还有其他属性，但是最重要的就是前缀，ASPATH和NEXT-HOP。

一台路由器可能知道到一条前缀的多条路由路，路由器必须在可能的路由中选择一条，常用的选择策略有：本地偏好值设定（比如固定不接收来自某AS的路由或者不向某AS通告路由），最短AS-PATH，热土豆路由（选最靠近NEXT-HOP的路由），使用BGP标识。

第五章链路层

5.1 概述

再本章中，将运行链路层的协议任何设备全部称为结点，将沿着通信路径连接相邻节点的通信信道称为链路，在特定链路上数据报被封装在链路层帧中。

链路层的基本服务是将数据报通过单一通信链路从一个节点移动到相邻节点，其还能提供下可能服务包括：

成帧：将网络层数据用链路层帧封装起来，根据链路层协议不同，帧的格式不同。
链路接入：媒体访问控制（MAC）协议规定了帧在链路上传输的规则，其主要用于协调多个节点的帧传输
可靠交付：用于误码率高的链路，保证无差错地经链路层移动到网络层，其可靠交付也是通过确认和重传完成的。
流量控制：在相邻的收发节点间限制流量
差错检测和纠正：链路层的差错检测比运输层和网络层更复杂且通过硬件实现，并且可以进行一定程度的纠错。

链路层的主体部分实在网络适配器（也称为网络接口卡NIC）中实现的，网络适配器是一个半自治的单元，其对帧的发送和检错都是自主进行的，而向上提交数据则需要节点干预位于网络适配器核心的是链路层控制器，该控制器一般是实现了许多链路层服务的专用芯片，即链路层的许多功能是通过硬件实现的，还有一部分是在运行与主机CPU上的软件实现的，所以链路层是硬件和软件的结合体。

5.2 差错检测和纠正技术

首先需要明确的是差错检测都不是完全可靠，但是一般码距越大（差错检测位）越多，出错的概率越低，但开销也越大。下面介绍常见的三种检测方法：

奇偶校验

通过检验数据中1的总数是奇数还是偶数判断数据是否出错。最简单的是设置一个奇偶校验位，可以检查出现了奇数个错误情况，但无法纠错，无法检验出现偶数个错误的情况。

改进的方法有二维奇偶校验，即将数据排成矩阵，并对矩阵每一行每一列设置校验位。还有海明校验等

因特网检验和

将数据段的内容作为16比特的整数对待并求和，进位回卷，和的反码作为校验和包含在报文里，接收方将接收到的数据的和取反码并检测其结果是否为全1，是则没错，否则出现错误

循环冗余校验（CRC）

链路层常用的差错检测技术，其实现较为复杂故在使用软件进行校验的运输层中没有使用，而链路层使用硬件进行差错检测故可以快速执行CRC算法。考虑d比特的数据D，CRC的操作如下

发送方和接收方先协商一个r+1比特的生成多项式，设为G，最后数据中的差错检测位R的位数为r，且d+r拼接而成的序列能够被G模2整除，发送方生成R的方法为将D右边接上r个0，然后除以G，得到的r位余数就是R。
接收方接收到数据后同样除以G，若余数为0则大概率没错，否则可以根据余数知道是哪一位出错了

5.3多路访问链路和协议

网络链路类型有两种，一是点对点链路，二是广播链路。本届讨论如何协调多个发送和接收节点对一个共享广播信道的访问，即多路访问问题。由于所有结点都能够传输帧，当接收方同时收到多个帧，称为传输的帧在所有的接收方处碰撞，碰撞发生时涉及碰撞的帧都丢失了，造成信道带宽的浪费，因此在多个节点处于活跃状态时需要协调活跃结点的传输。结点通过多路访问协议来规范他们在共享的广播信道上的传输行为。

理想情况下，对于速率为R bps的广播信道，多路访问协议应该具有以下特性：

当只有一个节点有数据发送时，该节点的吞吐量为R
当M个节点有数据发送时，每个节点吞吐量为R/M（指平均值）
协议是分散的
协议是简单的

多路访问协议（MAC协议）有三种类型：信道划分协议，随机接入协议和轮流协议

信道划分协议

信道划分协议指将信道划分成小的片（按照时间、频率或者编码），并将片分配给结点使用。常用的方法有：

时分复用（TDM）：将时间划分为时间帧，并将时间帧划分为N个时隙，把每个时隙分配给N个结点中的一个。好处是消除了碰撞，坏处是每个结点的速率被限制在R/N，没有数据发送的时隙是空闲的，造成了速率的浪费，
频分复用（FDM）：将带宽平分给结点，优点同样是避免了浪费，缺点同样是没有数据的带宽空闲造成了浪费
码分多址（CDMA）：为每个结点分配一种编码，结点利用自己的编码对数据进行编码，如果编码设计巧妙可以左到消除干扰。

随机接入协议

随机接入协议种所有节点以全部速率进行发送，当发生碰撞时，涉及碰撞的结点反复重发它的帧直到无碰撞，重发不是立即进行的，而是经过一个时延，各个结点选择时延是独立的。常用的随机接入协议有ALOHA，时隙ALOHA，CSMA，CSMA/CD，CSMA/CA。

时隙ALOHA：设所有帧的长度一样，一个时隙的长度为传输一个帧需要的时间，结点只在时隙的起点开始传输帧，且所有结点的时隙是同步的，当一个时隙发生碰撞时所有节点可在时隙结束前检测到碰撞事件。在这些假设下，时隙ALOHA发生碰撞时结点以概率p在后续的每个时隙种重传它的帧。假设有N个结点，每个节点在每个时隙以概率p传输一帧，则传输成功的概率（在本时隙只有一个节点传输）的概率为,趋于无限时，取适当的p其最大概率为0.37。还可以分析出空闲概率时0.37，碰撞概率是0.26。
ALOHA：纯ALOHA没有时隙和时隙同步。所有结点全速发送帧，发生碰撞时以p的概率立即重传，若没有重传则等待一个帧的传输时间，再以p的概率重传，直至传输成功。由于没有时隙同步，一个结点成功传输的概率为，总的概率乘以N，其最大成功概率为时隙ALOHA的一半
载波侦听多路访问（CSMA）：即在发送帧前先监听信道是否在传输帧，确认信道未在传输帧时才发送。根据信道忙时的表现可以分为非坚持CSMA和坚持CSMA。非坚持CSMA在信道忙时会根据算法随机延迟一段时间后再监听信道，或者引入时隙概念只在时隙开始时发送帧。坚持CSMA在信道忙时持续监听信道，一旦信道空闲就按概率发送帧，当概率为1时称为1坚持CSMA，否则称为p坚持CSMA（p为概率）。CSMA在发生冲突后会重传，重传视为发送新的帧处理。
具有冲突检测的载波侦听多路访问（CSMA/CD）：在CSMA的基础上加入碰撞检测，一旦检测到会出现碰撞立刻停止传输，通过丢弃无用帧来提高信道利用率。丢弃一个帧后结点会等待一个随机时间再重传

轮流协议

由于信道划分协议在轻负荷时效率低，随机访问协议在重负荷时有碰撞开销，于是人们设计了轮流协议。常见的轮流协议很多，这里介绍轮询协议和流派传递协议。

轮询协议：指定一个结点为主节点，主节点以循环的方式轮询结点，告诉结点能够使用的开销。其消除了随机接入协议的碰撞和时空间隙，但是引入了轮询时延，降低了轻负载下的效率，并且一旦主节点瘫痪，所有节点将都不能工作。
令牌传递协议：节点之间按照固定的次序交换令牌（一个小的特殊帧），只有有数据发送的时才可以继续持有令牌，否则需要将令牌交给下一位。有令牌的结点可以发送最大数目帧数。但是一个结点故障可能会使信道崩溃。

5.4 交换局域网

本节首先讨论链路层寻址，然后讨论以太网

链路层寻址和ARP

主机或者路由器的链路层地址其实是它们适配器的地址，注意链路层交换机没有链路层地址。链路层地址又多种不同的称呼，如LAN、地址，物理地址 MAC地址。MAC地址最为常用。

MAC地址由6个字节48位组成，一般用十二个（六对）十六进制数表示。每个适配器都有一个独一无二的MAC地址，且被烧入网络适配器的ROM中，不可更改（其实是可以的，但是我们一般默认不可更改），这一点与IP地址不同，一台主机的IP地址移动时可能会发生改变，而其MAC地址永远不变。由于适配器生产厂家有很多，为了做到MAC地址不重复，前24bit由IEEE分配管理，后24位由厂家分配保证不重复。其作用是在数据链路层标识每块网络适配器，使得能够在广播信道上寻址目标节点。

在链路层，当网络适配器要向目的适配器发送一个帧时，需要将目的适配器的MAC地址插入帧中；适配器收到一个帧时，检查目的MAC地址是否是自己的MAC地址，是则向上提交，否则丢弃。有些帧需要局域网上所有适配器处理，此时使用广播地址（FF-FF-FF-FF-FF-FF）。

为了确定目的适配器的MAC地址，因特网采用地址解析协议（ARP）。局域网中每台主机或路由器中有一个ARP表，其格式为IP;MAC;TTL，即IP地址，IP对应MAC地址，记录有效时间。若目的IP地址在表中且未过期则取出MAC，否则发送方构造一个ARP查询分组，其包括发送方和接收方的IP地址以及发送方的MAC地址，广播出去。子网内所有主机和路由器都会收到这个分组，IP地址和报文中目的IP地址相同的主机会回复一个ARP响应报文告诉发送方自己的IP地址。这是发送方就可以更新ARP表并发送帧。

若要发送到子网以外的主机，目的MAC地址选择网关接口，网关接口收到后根据IP协议转发至对应端口，输出端口再根据ARP寻找MAC地址。

以太网

以太网几乎占领着现有的有限局域网市场。以太网的帧结构如下：

前同步码有八个字节，前七个字节的值都一样，用于同步时钟，第八个字节最后两个字节用于标识重要内容。目的地址和源地址是MAC地址，类型指明上层的网络层协议或者指明ARP协议。数据字段用于承载网络层报文段，大小不超过以太网MTU（1500字节），也不能小于46字节。CRC是校验码。以太网提供无连接服务，接收方对CRC校验后若有错误直接丢掉。

以太网有多种标准，如10BASE-T，10GBASE-T等，命名规则基本为速率基带以太网-物理媒介。以太网早期使用同轴电缆使用总线拓扑互联节点，之后使用集线器使用星形拓扑互联节点，一个集线器有多个端口，一个端口收到比特时就将其放大向所有接口传输，没有存储转发的概念。现代以太网使用交换机代替集线器。

以太网使用CSMA/CD多路访问协议，需要指出的是在发生碰撞决定等待时间时使用二进制指数回退，即结果第m次碰撞时，适配器从中选择一个值，记为K，等待时间为传输个比特的时间。信号的编码方式包括不归零码，曼彻斯特编码和差分曼彻斯特编码。不归零码（NRZ）就是高电平为1，低电平为0；曼彻斯特编码很好理解，即用信号的跳变标识1和0，上升沿为1，下降沿为0，如下图。

差分曼彻斯特编码的第一位确定方式和曼彻斯特编码一样，后面位的确定方式为电平与之前保持不变表示1，变了表示0，同时每一位跳变一次，如下图：

上图中最开始的0就是曼彻斯特编码的0，第二个周期最开始的电平和钱一个周期最后的电平一致，所以是1，第三个周期开始的电平和第二个周期结束的电平不一致所以是0。

链路层交换机

现代以太网使用交换机代替集线器。交换机对于主机和路由器是透明的，其只负责接收链路层帧并转发至相应出口，为了平衡接收速率，交换机的输出接口设有缓存，故交换机也被称为多接口网桥。

交换机的主要功能为过滤和转发，使用交换机表完成，交换机表中记录了MAC地址和应该转发的接口以及记录时间。对于一个接口，其收到一个分组时，若发现分组应该转发至其发过来的子网，则将其丢掉，这个操作称为过滤；若发现分组的MAC地址有其他接口，则向该接口转发；否则，向所有除该接口的其他所有接口广播。

交换机表不需要管理员配置，其是自学习的，因为只要一个接口接收到一个帧，就可以生成一条交换机表记录。交换机是一个即插即用的设备。

由于MAC地址是扁平化的，很可能出现一个链路层帧在交换机网络中绕圈子的情况，所以需要在交换机互相连接的时候将其路径设置为一个支撑树，避免出现环路。这个做法只适合小一些的局域网。

使用交换机后链路中不会再出现碰撞（因为交换机接口有缓存，不会同时发送两个数据，而一入接口一般也只会接一台机器，接收数据时也发生不了冲突）

交换机和路由器的对比如下图：

虚拟局域网VLAN

虚拟局域网VLAN（Virtual LAN）是指以软件方式来实现逻辑工作组划分与管理的一种网络工作组组建技术。交换机的端口通过软件分成多个分组，这样的话就可以将单个物理交换机划分为多个虚拟交换机实现流量隔离，或将不同交换机上的接口看作逻辑上的同一交换机。

现在考虑两种情况：

同一个交换机上分开的两个VLAN之间如何互联？答案是接一个路由器。通过路由器进行转发
现有两台交换机，每个上面都有VLAN1和VLAN2，两台机器上的VLAN1之间如何交流？答案是通过VLAN干线连接，记载每台交换机上的一个特殊端口设置为干线端口来互联交换机，干线端口转发相应的帧到相应的VLAN，这需要用到802.1.Q以太网帧格式，其在原始以太网帧中加入了首部四字节的VLAN标签用以表示VLAN帧

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

6.1 概述

首先无线性和移动性是两个概念。无线性是基础，指基于无线链路的通信，而移动性除了这一点外还要求解决用户网络接入点变化时产生的问题，显然家用WIFI具有无线性而不具有移动性，蜂窝数据网络则兼而有之。

一个无线网络有以下要素：无线主机（即我们的上网设备）、无线链路（用于连接无线主机和基站）、基站（）用于连接无线网络。

无线局域网分为两大类，一类是有固定基础设施的，其中所有网络服务由网络通过基站相连的主机提供；另一类是自组织网络，网络服务由网络中的主机自己提供。在这两种类型的基础上，根据分组是否跨越多个无线跳可分为单跳网络和多跳网络（毕竟网络以有线居多，大部分无线数据经过几跳后会接入有线网）

6.2 无线链路和网络特征

无线链路的特征有：

信号强度随距离递减，会被障碍物阻挡
由于都在大气中传播，存在来自其他源的干扰
由于存在反射，有多径传播的现象。

与有线链路相比，无线链路很不可靠，不仅需要进行CRC错误检测，还需要使用链路层的ARQ协议来重传。

描述无线信道的质量的量有信噪比（SNR）和比特差错率（BER），前者是信号强度和噪声强度的相对测量，后者是接收方收到有错传输比特的概率。两者具有以下关系

给定调制方案（给定传输速率），SNR越高，BER越低
给定SNR，传输速率越快BER越高

无线链路是一个广播链路，其常用的多路访问协议是属于信道划分协议的码分多址协议（CDMA）。为了数学处理方便，这里约定信息中的0表示为-1，1标识为+1，CDMA的工作方式为：为每个结点分配一个定长码片（一个比特序列，或者为了和后面正交的概念向呼应将其视为一个比特向量），不同结点的码片正交。当节点要发送1时发送码片，结点要发送发送-1时发送-1乘以码片。发送时信道中的数据进行向量的叠加。当一个结点收到信息后，由于不同结点码片正交，而收到的信息时所有节点信息的向量和，所以用其希望收到的发送结点的码片乘以收到的序列即可。

6.3 WiFi：802.11 无线LAN

802.11包括802.11b、802.11a、802.11g802.11n以及802.11ac。区别主要在于频率范围和速率。802.11协议族都是用CSMA/CA协议实现多路访问（注意不是CSMA/CD），并且都可以用于有固定基础设施模式和自组网络模式。

802.11的体系结构为：无线终端通过基站通信，一个基站的基本服务范围称为基本服务集BSS，其中包括无线终端和基站（自组网络模式下没有单独的基站）。与以太网类似，每个无限站点和AP的适配器都有一个MAC地址。本节主要关注基础设施无线LAN。

一台无线主机要能上网之前必须先和一个IP关联。关联的过程以802.11b为例。首先管理员再安装AP时要为接入点分配服务集标识（SSID）以及通道号，802.11定义了11个通道号但只有1，6，11号信道是非重叠的，可以同时工作，其他信道要注意重叠问题。每个AP会周期性发送信标帧，广播自己的SSID和MAC，主机扫描11个信道获取可用的信标帧，选择一个AP进行关联（加入子网，通过DHCP获得IP地址。可能需要身份鉴别，最常见的是输WiFi密码）

802.11采用的MAC协议为CSMA/CA，称为带碰撞避免的CSMA，同时使用ARQ重传机制，两者结合的基本操作方法如下：

初始时若信道空闲，则节点再一个称作分布式帧间间隔（DIFS）的短时间后发送该帧
信道忙碌则选择一个随机回退值，再侦听信道空闲时递减该值，若信道忙碌则保持该值
计数值减为0时发送帧并等待确认。如果收到确认则回到第2步发送新帧，否则回到第二部选一个更大的随机值发送旧帧

上面是发送方，接收方只需接收并在正确接收时返回ACK即可，但是返回ACK也需要经过短帧间间隔（SIFS）秒

由于采用了倒计时计数抑制传输，可以避免一部分碰撞，但是当两个站点相互隐藏无法侦听（由于无线网络特性很可能发生）或者两个结点选择了接近的随机回退值依然可能发生碰撞。解决方法是使用请求发送帧（RTS）和允许发送帧（CTS）来预约信道而非随机访问。虽然RTS和CTS也会碰撞，但这俩玩意很小，冲突事件很短。具体行为是要发送数据的结点广播一个RTS，AP收到RTS后广播一个CTS，CTS必然可以被BSS中所有主机收到，除了发送RTS的结点其他结点在CTS指明的时间内将被抑制发送。

802.11的帧格式如下

帧控制部分的格式如下

为了增加无线LAN的物理范围，一些组织经常会在同一子网中部署多个BSS（即部署多个AP）。当一台主机从子网中一个BSS移动到另一个BSS时，主机会自动解除与前一个AP的关键并与后一个AP建立关联，并保持IP地址和正在进行的TCP会话。而对于交换机，如果主机的移动是偶尔的，则可以通过交换机的自学习建立对应的交换机表。如果移动是频繁的，交换机表项更新不会那么及时，可能导致帧被转发到错误的端口。一种解决方法是在新的关联形成后，让新的AP以H1的源地址向就熬还击发送广播帧让交换机更新表项。关于主机在不同子网间保持TCP连接的移动，因为不考所以没看😊😊

最后，802.11有一些高级高级特性，比如基站和移动终端之间的传输速度会随着移动终端的移动和SNR的变化而智能的调整（参考前面传输速率和BER，SNR的关系），以及功率管理能力，即让一个结点在睡眠和唤醒状态之间交替（通过帧控制部分的功率管理比特向AP指示自己将睡眠，并设置一个定时器在下一个信标帧到来前唤醒。AP会缓存要发送给睡眠结点的帧，而不是立即发送，并通过信标帧通报缓存列表。睡眠节点在信标帧到来前唤醒，检查信标帧缓存列表，如果为空则接着睡，否则请求AP发送缓存的帧，处理完再睡）

最后介绍802.15，包括蓝牙协议802.15.1和ZigBee协议802.15.4.两者的通信半径都小于十米，速率不高，采用自组网，常用于取代电缆。

纯路人的博客