计算机网络

概论

路由交换

电路交换

要求双方建立连接后才能够交换数据。端到端连接。

分组交换

将数据包划分为一个个小的数据段，在每个数据段首部加上信息，通过这些信息将数据包进行转发，最后在目的地再把数据重组回来。

分组交换的本质是存储转发，即可以实现队列缓存。

两种交换的对比

分组交换提供了更好的贷款共享，更加简单有效、成本更低。

电路交换时延低

丢包、延迟、吞吐

当缓冲队列满时，无法将数据包加入队列就会产生丢包。

延迟可以分为四个部分：处理、队列、传输、传播

从知乎copy下

nodal processing delay:

• 检查错误位
• 选择输出链路
• 高速路由器处理延迟-微妙级

queueing delay:

• 等待被发送到输出链路上的时间
• 取决于路由器的拥塞程度

Transmission delay：

• R=链路带宽 (bps)
• L=分组长度 (bits)
• 发送分组比特流的时间 = L/R

Propagation delay:

• d = 物理链路的长度
• s = 介质的信号传播速度 (~2x108 m/sec)
• 传播延迟 = d/s
  注意: s和R是两个完全不同的速度参量!
  s 是介质的信号传播速率，取决于介质等因素
  R是链路的带宽

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

吞吐量

a: 分组到达队列的平均速率

L: 分组大小

R: 传输速率，从队列中推出比特的速率

流量强度指$\frac{L·a}{R}$

当其>1时，队列会不断增加，不考虑。

有两种特殊情况值得考虑，每L/R秒到达一个分组，则每个分组到达一个空队列里，不会有排队时延；另一种(L/R)N同时到达N个分组则第n个分组有(n-1)L/R的排队时延。

端到端时延

若两个主机之间有N-1台路由器，则$d_{end-end} = N(d_{proc}+d_{trans} + d_{prop} )$

丢包

若分组到达时队列已满，就会丢弃，导致丢包

吞吐量

单链路中的吞吐量决定于最小的（木桶效应）

而在多链路的网络场景中，往往是取决于干扰流量

协议分层

协议以分层的方式分为多层结构，每一层向它的上一层提供服务。

各层的所有协议被称为协议栈，因特网的协议栈由5个层次组成：物理层、链路层、网络层、传输层和应用层。

应用层

应用层是网络应用程序及它们的应用层协议存留的地方，有HTTP、SMTP和FTP协议，位于应用层的信息分组称为报文

传输层

有TCP和UDP协议，TCP将长报文划分为短报文，并提供拥塞控制机制，因此当网络拥塞时，源会抑制其的传输速率。UDP向应用程序提供无连接服务。

网络层

网络层负责将被称为数据报的网络层分组从一台主机移动到另一台主机，通常被称为IP层。

链路层

链路层则负责网络层主机间移动的在节点之间移动的服务，或者说将一个帧从一个网络元素移动到附近的网络元素

物理层

物理层则是负责帧中的一个个比特的移动。

应用层

应用层协议原理

网络应用程序体系结构

可以分为CS(client-server)或者P2P体系结构，CS可以是各大门户网站，P2P可以理解为端到端传输的流量密集型应用，比如QQ、迅雷。

进程通信

网络应用程序由成对的进程组成，每有一对客户端和服务器，即可以认为这是他们各自的一个进程，进程间的通信通过socket(套接字)完成。又由于socket是建立网络应用程序的可编程接口，因此socket也被称为应用程序和网络之间的API(应用程序编程接口)

进程寻址则有IP地址和端口号标识。

因特网传输服务

当创建一个新的网络应用时，需要决定使用UDP还是TCP。

TCP

TCP可以提供面向连接的服务和可靠的数据传送服务，对面向连接的服务，通过三次握手能够建立一个双向发送数据的TCP连接。此外TCP也可以将字节完好无整地在socket之间传播。

SSL是TCP的升级版，具有加密功能，HTTPS的基础便是SSL。

UDP

之前讲过，UDP向应用程序提供无连接服务，其意思为不保证数据传播的可靠性，也不保证到达时间的准确性。

Web和HTTP

HTTP使用TCP作为支撑传输协议，首先需要建立一个TCP连接，之后便可以通过套接字接口请求和接收响应报文。同时，HTTP是一种无状态协议，不保存客户的任何信息，也就是说，隔几秒重新发送请求的话，服务器还是会返回HTTP响应。

持续连接和非持续连接

根据使用的不同情况，可以建立长连接或者在传输完报文后就立即关闭TCP连接，RTT定义为短分组从客户端到服务器再返回客户端的时间。

非持续连接

发起一个TCP连接时，创建一个套接字，发送请求报文，获取响应报文，关闭TCP，检索响应报文中的HTML文件，发送有10个图片的引用，于是对每个图片重复发起TCP连接的过程，这是一个非持续连接。

这里我们可以了解到RTT，为往返时间，包括分组传播时延、分组在中间路由器和交换机上的排队时延和分组处理时延。

如果使用非持续连接，每次请求一个文件至少有两个RTT，对服务器带来眼中的负担。

持续连接

如果打开网页后保持一个TCP连接，可以在一个浏览过程中减少近一倍RTT的时间。

HTTP报文格式

请求报文由请求行、Header和Body组成，响应报文由状态行、Header和Body组成

Cookie

Cookie可以用来识别客户，其存储于Header中。

Web缓存

跟计算机中的缓存一样，通过缓存可以大大减少浏览重复网页所需要的时间。

缓存服务器作为一个中介体，在接收到请求是如果有缓存就可以快速返回给用户，反之才去源服务器请求。

通过CDN(内容分发网络)，可以使大量流量本地化，可以使用CDN来缓存css和图片文件来减少静态网站的访问时间。

电子邮件

邮件是异步的，主要有3个部分组成：用户代理、邮件服务器和SMTP。

当A端到A服务器到B服务器到B端的邮件收发过程里，前两段都是SMTP，最后的邮件接收使用IMTP。

SMTP的报文由Header和Body组成。

假如A想给B发送一封邮件，首先A将把报文发送到A的邮件服务器上，邮件服务器有处理队列，当准备发送这个报文时，创建一个和B的邮件服务器的TCP连接，发送报文，B的邮件服务器保存邮件，然后B通过代理获取邮件。

DNS

DNS(Domain Name System)是一个将主机名转换为IP地址的系统

主机

主机的标识方法有主机名和IP地址两种方式，主机名易于记忆而IP地址命名规范，DNS则提供了一种从主机名到IP地址转换的目录服务，DNS是建立在UDP服务上的。

分布式、层次数据库

DNS具有层次，分别是根DNS服务器(根域)、TLD(顶级域)服务器(顶级域)和权威DNS服务器(主域)。例如tju.edu.cn中edu.cn是TLD服务器的，又称为二级域名，tju.edu.cn就是权威DNS。

同时DNS查询有递归查询和迭代查询两种，递归就是逐层步进的查询，迭代就是在某层之间进行查询。

看一个请求的例子，主机想要获得gaia.cs.umass.edu的IP地址，首先先向本地的DNS服务器请求，本地DNS服务器向根DNS请求报文，根DNS发先edu，向本地服务器返回负责edu的TLD的IP地址列表，DNS向TLD服务器之一发送查询报文，TLD发现umass.edu，返回dns.umass.edu的IP地址，然后本地DNS向其发送查询报文，最后获得到目标主机的IP地址。

其中，18是递归查询，其他都是迭代查询，简单来说，如果发送完就返回，就是迭代，发送完有其他步骤才返回就是递归。

DNS缓存

通过DNS缓存能够减少查询次数，但是缓存也有保存时间，被称为TTL，过期后会被丢弃。

DNS记录和报文

每份DNS回答报文包含了一条或者多条资源记录

资源记录是包含了下列字段的的4元组

(Name, Value, Type, TTL)

Type分为几种类型，如下

DNS报文没有讲，大概不是很重要。

P2P文件分发

在这里研究一种从单一服务器向大量主机（对等方）分发文件的一个Sample。

令$u_s$为服务器接入链路的上传速率，$u_i$和$d_i$为第i对等方接入链路的上传和下载速率

令分发时间为所有N个对等方得到该文件副本所需要的时间。

对于CS和P2P模式分别有两种结果

$$D_{cs} = max\{\frac{NF}{u_s}, \frac{F}{d_{min}}\}$$

$$D_{p2p} = max\{\frac{F}{u_s}, \frac{F}{d_{min}}, \frac{NF}{u_s +\sum_{i=1}^{N}{u_i}}\}$$

视频流和内容分发网

因特网视频

在HTTP流里，视频作为一个文件存储在服务端，用户请求视频时，客户端和服务器会建立一个TCP连接，向客户端传输字节，当字节超过了预先设定的门限时，客户端便可以开始播放视频了，故流式视频一方面从缓存中读取视频时，另一方面也在获取数据存放到缓存中。

由于用户的带宽不同，出现了经HTTP的动态适应性流即DASH，在DASH中，视频编码为适应不同带宽的版本，客户端先请求不同版本的数据块，然后根据带宽量选取不同版本的块践行传输。

内容分发网

即CDN，CDN管理可以将每个用户的请求定向到一个体验最好的CDN位置。

传输层

传输层提供在应用的进程间的逻辑通信，传输层在端系统中实现。在发送端，运输层将从应用程序进程接收到的报文转换成传输层的分组，即运输层报文，将应用层报文分为小片段后，在首部加上运输层首部以成为一个个运输层报文，再交给网络层来处理。

传输层中主要有TCP和UDP协议。

概述

根据《自顶向下》里的分类，将TCP和UDP的分组统称为报文段，将数据报的名称保留给网络层分组。

首先了解一下网络层的IP协议，即提供主机之间的逻辑通信，他的服务模型是尽力而为交付服务，即不确保报文段的交付，不确保时序，不确保数据的完整性，因此IP又被成为不可靠服务。当然现在只需要知道每台主机有一个IP地址。

UDP和TCP的服务模型为传输层的多路复用（multiplexing）和多路分解（demultiplexing），可以在其报文段首部中放置一些内容而提供完整性检查。

UDP只有进程间的数据交付和差错检查，所以UDP也不是可靠的服务，不能保证让数据能够完整地到达目的进程。

此外TCP还有可靠数据传输和拥塞控制，从而TCP能够正确地按序地传输数据，而拥塞控制可以防止任何一条TCP连接用过多流量来淹没通信主机之间的链路和交换设备，可以为每一条通过拥塞链路的连接平等共享链路带宽。所以UDP流量是不可调节（毕竟他只有两个基本功能），使用UDP的应用程序可以以任意速率发送数据（在带宽限制内）。

多路复用和多路分解

由于主机间不可能只有一个连接，所以需要将一个到达的传输层报文段定向到合适的套接字上，为此接收端的传输层会在首部中检查字段，实现正确的交付工作，这被称为多路分解，在源主机中加上这些首部信息的过程被称为多路复用。

因此对套接字我们有两点要求

• 套接字有唯一标识符
• 每个报文段有特殊字段来指示报文段所要交付到的套接字

所以这会在首部中有一段32bit的区域存放源端口号字段和目的端口号字段。

UDP和TCP的多路复用和多路分解

在UDP中，特殊字段为源端口号和目的端口号组成的两元组

而在TCP中，由四元组(源IP，源端口号，目的IP，目的端口号)组成。因此能够辨别发送来的数据是从哪个具体IP发送而来的。

UDP

简介

由于使用UDP时，在发送报文段之前，发送方和接收方的传输层实体时间没有进行握手，所以UDP被称为无连接的。

DNS的底层是使用UDP实现的，当一台主机中的DNS应用想要进行查询的时候，会构造一个查询报文，然后交给UDP，UDP便会添加首部字段后交付给网络层，网络层又把UDP报文封装进一个IP数据报中，发送给一个名字服务器，然后DNS就等待响应了，由于可能发生丢包的情况（IP只会尽力交付），所以可能会一直等待响应，或者在超时后发生一个错误。

但尽管如此，许多开发者仍然愿意在UDP上构建应用，而不是使用TCP，原因有如下几点：

• 对于何时发送数据以及发送什么数据的控制更为精细

  由于TCP的拥塞控制(congestion control)机制的存在，数据包在发送队列存在待发送数据时，不能够及时发送。

• 无需建立连接

  TCP的三次握手导致了他即便是没有队列阻塞，也会有一定的时延，所以有些想要低时延的应用功能就不使用TCP。对于HTTP而言，他使用TCP是因为文本数据要求了传输的可靠性，所以得使用TCP，不过HTTP3的QUIC协议是使用UDP实现的，有兴趣可以看这篇

• 无连接状态

  TCP建立连接后，需要在端系统中维护这个连接状态，而UDP不维护，他发送完就走人了，所以对于机器的内存开销小，也就是说使用UDP跑满内存能够支持更多的活跃用户。

• 分组首部开销小

  这当然了，首部小，传输数据量也会变小，同样的带宽就能发送更多数据。

在现在的多媒体应用上，UDP主要应用在网络电话、视频电话上，这类应用更要求时延低而可以容忍一点丢包率。

UDP报文结构

UDP报文结构如图所示

可靠数据传输原理

可靠数据传输为上层提供的服务抽象是：数据可以通过一条可靠的信道进行传输，借助这条信道，传输的数据就不会有损坏或者丢失的现象。

实现这种服务抽象的是可靠数据传输协议（rdt）。

rdt 1.0

rdt的描述可以用有限状态机来描述

如图，这是rdt1.0的状态机，十分简单，基本上只有send和rcv的功能。

对于状态机的状态变化有如下定义：

横线上面是进行状态变化的条件，横线下面是进行状态变化时所发生的动作，当缺少一项时用向上的箭头代替，在之后会遇到。

其中rdt_send是等待来自高层（协议层）传来的数据，有数据传来时，对数据进行打包，将分组传输到接收端。

接收端在接收到后，进行拆包操作，然后将数据传给上层（协议层）。

rdt 2.0

然而实际传输过程中，分组的信息可能出现差错，即比特受损，（这时候也只考虑这种错误的存在）。

我们有两种控制报文：ACK和NAK，意味着确定接收和请求重新发送，基于这样的重传机制的协议被称为ARQ协议

ARQ协议还需要另外三种功能处理比特差错的情况：

• 差错检测：即校验和字段的作用
• 接收方反馈：ACK和NAK
• 重传，接收到有差错的分组时，发送方应该重传

在2.0中，发送端加入了一个中间状态，用来接收ACK或者NAK包，如果收到NAK包则重新进行数据的传输，知道接收到ACK包。

而对于接收端，在差错检验出现错误的时候会发送NAK包，知道没有错误时拆包发送给上层。

但是ACK包和NAK包也有差错，接收方发送的ACK或者NAK对于发送方可能无法理解，接收方也不知道新接收到分组是重传来的还是新的分组。

对于此的解决方法是增加一个新的字段，将包序号放在字段中，于是接收方只需要根据序号来判断是否需要重传即可，

对于2.1来说，突然状态就多了起来，但是还是容易学习。

首先对于发送方，先向接收方发送分组，如果控制报文检验不出错且是ACK包就发送即可。图里0到1和1到0的过程是一样的，只是有一个状态转换（seq参数是否变化，变化则转移到下一个包，反之则重传）。

对于接收方来说，如果接收到信息但是出错了，则发送一个带有差错检验的NAK包回去，如果不出错，还要看看是否为重传的分组，如果是则发送一个ACK包回去，如果不是重传，则可以到状态1了，同样的，0到1和1到0也是一样的，不叙。

对于2.2而言，接收方现在不出错时没有区别，但是在ACK包中加入了一个参数0或者1，如果发送了1，则发送端进行重传，否则这个分组发送成功，进行下一个分组的发送。发送方则是加入了一个检查ACK包中参数的步骤。

rdt 3.0

我们已经解决了包受损和包序号的问题，那我们如何确定一个包是否丢失呢。则引出了rdt 3.0，加入基于时间的重传机制。

对于发送方，每发送一个包到接收端的时候，都启用一个计时器，只要在超时且未接收到成功指令（没有出错且ACK包参数为0）时，又重新发送一次分组。

流水线可靠数据传输协议

rdt固然增强了传输数据的可靠性，但是其的停等协议导致了在网络延迟较高时，传输速率也会变慢，于是有人想出了流水线一样的传输，即可以多个数据包一起发送而不需要确认收到后再发送第二个。

发送方利用率

发送方利用率指发送数据需要的时间与得到回应所需要的时间的比率，即将数据注入信道的时间比上发送时间。

$d_{trans} = \frac L R$

所以发送方利用率为$\frac{d_{trans}}{d_{trans} + RTT}$

回退N步(GBN)

在回退N步协议中，发送方能够发送多个分组而不需要等待确认，在这里我们定义3个变量，N - 窗口长度、base - 最早未确认分组的序号、next(书中为nextseqnum) - 未发送分组的序号，因此我们可以将所有分组分为四段

[:base]已发送并确认接收

[base:next]已发送未确认

[next:N]待发送

[N:]等待

我们按照分组序号来排列分组顺序，假设分组序号字段的比特数为k，则序号范围在[0:$2^k$]中，窗口大小N小于等于$2^k-1$，不过在TCP中，序号字段是按字节流的字节进行计数的，在此暂时不叙。

GBN的FSM

• 先从入口看起，在上层发出发送指令的时候，首先判断窗口内指针next是否合理，合理的话会将数据分组打包放在缓存中，然后发送一个分组并且开始一个计时器（理解为发送一个分组即可），接下来就有两种情况，第一种是超时，如果超时就从base起重新发送一直发送到第next-1个分组，第二种是成功接收，接收到一个ack包，这个ack包带有一个参数n，参数指示了接收方已经成功接收到第n个分组，这时候我们可以更新base指针，然后继续循环，直到base和next指针相同，这时一个上层分组的结束。

• 对于接收方，做的事情就很简单了，只要把接收到的分组进行拆解然后返回一个序号，这个序号由一个变量expectedseqnum决定，当接收到的包序号和expectedseqnum相同时，才接收并且更新expectedseqnum，否则就重新发送上一个ack。

  所以如果接收方没有收到分组n直接收到n+1，它并不会接收n+1分组，而是等待发送方超时后重新发送n，直到收到n分组为止，你会发现在丢包率大的时候，发送方总是会重复发送很多分组，所以我们有了选择重传协议。

选择重传(SR)

对于SR而言，窗口长度必须小于或等于序号空间大小的一半

对于选择重传协议，更新了双方的机制。

• 发送方仍有next变量，send变为send_base，但是在[send_base:next]中的分组不一定要按序确认，而是接受到了ack包就把某个分组标记为已接收。当返回的ack包参数和当前send_base相同时，进行窗口的移动，将send_base更新到最小的未确认分组处，并且发送未发送分组(不是未确认分组)。

• 接收方也有个base变量，我们称为rcv_base，接收方在接收到不想要的分组时，不会将其丢弃，假如现在expectedseqnum为n，接收到了n+1,n+2,会将其缓存起来，并且返回对应的ack包，你可以发现，现在的ack包携带的参数n并不表示n之前的已经接受，而是表示第n个分组被接受。当然了，我们很容易想到，如果接收到了expectedseqnum，我们应该将expectedseqnum一直移动到没有接收的包处，例如在这，接收到了n+1,n+2和n，故应该将n更新为n+3。

  值得一提的是，如果[:recv_base]的分组接收到时，也应该发送一个ack包回去。

但是对于SR而言，窗口过大可能会导致接收包的不确定，比如序号空间为0123，窗口大小为3，则如果接收方接收了012，但是ack包都没有被发送方收到，则发送方重新发送012的时候，接收方此时窗口中为301，那0和1反而被缓存，但这是不应该的。

TCP

TCP是面向连接的，TCP在连接和断开时分别会有三次握手和四次挥手，在寄哪里器连接后，TCP会将数据放到连接的发送缓存（send buffer），这是三次握手中设置的缓存之一，之后TCP会不时从缓存里取出数据，并将其传递到网络层。

TCP首部

我们不难发现，TCP比UDP增加了序号字段，接收窗口字段和首部长度字段等等

注意到有SYN、ACK和FIN三个标志位，这三个在握手和挥手过程中比较重要，我们稍后讨论。

序号和确认号

TCP每次发送的最大数据量被称为MSS（最大报文段长度），TCP将数据视为一个有序的字节流，所以每次传输一段数据时，总会根据MSS分割成一个个报文段，然后给每个分配序号。

确认号是用来接收数据时用的，确认号代表TCP已经收到的连续报文段最大序号的下一位，比如已经收到了0~535，那么可以向发送主机发送一个536。

往返时间的估计与超时

一般我们理解的RTT就是SampleRTT，但是TCP要对RTT进行估计值，由于TCP具有拥塞控制以及网络问题，RTT是波动的，所以要有一个EstimatedRTT，TCP由以下公式计算

$$EstimatedRTT = (1-a)*EstimatedRTT + a*SampleRTT$$

同时还有DevRTT，用于估算SampleRTT一般会偏离EstimatedRTT偏离RTT的程度

$$DevRTT = (1-b)*DevRTT + b * |SampleRTT - EstimatedRTT|$$

超时间隔应当大于等于EstimatedRTT，否则将造成不必要的重传，但是也不能大太多，这取决于DevRTT

$$TimeoutInterval = EstimatedRTT + 4*DevRTT$$

可靠数据传输

TCP的计时器在三种情况下可以开始计时

• 收到数据且定时器没有启动
• 超时
• 收到需要更新sendbase的ACK且有未确认的序号

讨论三种情况，假设有两个包为seq 1 8字节和seq 9 8字节

1. seq1 发送，无返回，超时发送seq1
2. seq1 seq9发送，ack1 ack9超时，重发seq1，收到ack1 ack9，收到acl1
3. seq1 seq9发送，ack1丢失 收到ack9

第二种情况里，由于超时只会发送未应答的最小报文段，而且收到了ack1，ack2，所以seq9不会重传。

第三种情况里，由于收到了ack9，且TCP为累计确认，认为ack1已经收到。

超时间隔加倍

如果发生超时，会将timeout设置为之前的两倍。

快速重传

冗余ACK指再次确认的某个报文段的ACK。

发送方也可以通过检测冗余ACK来检测丢包情况。如图

一旦接受到3个冗余ACK时，便执行快速重传，发送带有sendbase的ack

流量控制

接受方会维护一个接收窗口rwnd，又有接受方有recvBuffer、lastRead、lastRecv，肯定有lastRecv-lastRead <= recvBuffer，rwnd定义为recvBuffer - (lastRecv - lastRead)，

所以在发送方维护的lastSent和lastAcked上，有lastSent-lastAcked <= rwnd

但是在rwnd=0后，如果接收方清空了缓存，主机A也不会知道B还有缓存能够发送，所以当接收方的rwnd=0时，发送方会持续发送只有一个字节数据的报文段，以获得实时的rwnd大小。

连接管理

握手

挥手

拥塞控制原理

即便发送方和接收方的吞吐量很大，也受制于网络条件和链路大小，如果发送速率很大的话，平均时延也会越来越大，同时由于丢包等意外情况，也可能导致重传还占用了一定量的带宽，因此我们需要使用拥塞控制来优化传输。

拥塞控制一般由两种方法通知，一种为采用了拥塞分组的形式（直接发送一个拥塞的分组），一种是在字段中标记。

TCP拥塞控制

在TCP中，让每个发送方感受到拥塞程度来限制发送流量的速率。有一个变量称为拥塞窗口，表示为cwnd，对一个TCP发送方而言，未被确认的数据量不会超过rwnd和cwnd的最小值，即

$$lastsent - lastacked \le min\{cwnd, rwnd\}$$

我们在此节中只讨论拥塞控制，所以假设rwnd足够大，我们只需要关注cwnd的大小即可。

如果我们对连接方和发送方的时延丢包忽略，那么在RTT的起始点，允许发送方向连接方发送cwnd个字节的数据，在RTT结束时，发送方接收对数据的ACK。

在之前提到，发送方在TCP协议下能够感受到拥塞程度，他是怎么感受到的呢，我们定义丢包事件为超时或者收到3个冗余ACK，所以这种丢包事件发生时，发送方就认为出现了拥塞。

如果网络不会出现拥塞问题，即不会有丢包的情况发生，如果发送的报文很快地到达目的地，因此rwnd就会迅速增大，相对应发送方接收到大的rwnd后，就会有更快的发送速率（发送方的发送速率由rwnd决定），相反如果很慢到达，则发送速率更慢。由于TCP使用确认来触发增大rwnd，被称为是自计时（self-clocking）的。

现在还有一个问题没有解决，虽然在上文中我们提到了rwnd能够控制发送速率，但是这是怎么实现的呢，那就是拥塞控制算法。

TCP拥塞控制算法

拥塞控制算法主要包括三个方面

• 慢启动
• 拥塞避免
• 快速恢复

慢启动

一开始发送方采用MSS/RTT的较慢速率启动，每次有一个被确认就增加一个MSS并且发送，因此会以1 2 4 8的速度指数增长，直到有超时指示拥塞发生，这时候发送方将cwnd（拥塞窗口）设置为1个MSS并重新启动慢启动过程，将ssthresh（慢启动阈值）设置为cwnd/2，在这个过程里，就会有慢启动的第二个结束标志（所以我们能够发现慢启动方式至少有两种），即当cwnd到达或超过ssthresh的值时，结束慢启动并且让TCP进入拥塞避免模式。

还有一种慢启动在冗余ACK拥塞发生的时候，TCP进行快速重传并且进入快速恢复状态。

拥塞避免

结束了指数增长后来到了线性增长，比如每次确认时将cwnd增加一个MSS*(MSS/cwnd)字节，即让其在一个RTT内发送的所有报文段都确认时，cwnd能够增加一个MSS。

拥塞避免状态有两种结束方法，一种是收到超时拥塞，重新开始慢启动；另一种是冗余拥塞，此时将cwnd值减半，将ssthresh记为cwnd/2，进入快速恢复状态。

快速恢复

进入快速恢复的条件是丢失报文段的3个冗余ack，对于这些ack的确认，每次cwnd增加一个MSS，当丢失报文段的ACK到达时，TCP在降低cwnd后进入拥塞避免状态，如果有超时，则跟另两个阶段一样进入慢启动状态，对于丢包事件，设置cwnd为1个MSS并将ssthresh设置为cwnd/2。

网络层：数据平面

概述

网络层主要执行的功能就是将分组从一台主机移动到另一台主机，有两种重要的网络层功能需要了解：转发和路由选择

转发是指将一个分组从输入链路接口到适当的输出链路接口的路由器本地动作。

路由选择是指确定分组从源到目的地所采取的端到端路径的网络范围处理过程。

每个路由器都有一个自己的转发表，路由器检查到达分组首部的字段值，然后在转发表中索引输出链路的端口。

交换机

我们定义交换机是从输入链路到输出链路转移分组的设备，有些分组交换机根链路层帧中的字段值决定转发，被称为链路层交换机，其他的根据网络层首部决定的交换机我们称为路由器

路由器

路由器包含有四个结构：输入端口、交换结构、输出端口、路由选择处理器。

输入端口

输入端口中的线路端接和链路处理处理完了各输入端口的物理层和链路层。同时也会根据转发表来查找输出端口。

在转发表中，就是对IP地址进行匹配，路由器使用最长前缀匹配规则，当前缀具有多个匹配项时，选择能够匹配最长的那条进行转发。

嵌入式片上也有一个存储设备，叫三态内容可寻址存储器（TCAM），这个了解即可。

交换

交换结构是路由器的核心部位，通过交换结构我们可以将分组从输入端口转发到输出端口。

• 经内存交换

  早期的路由器是在CPU（这里指路由选择处理器）的控制下完成的，但是类似我们电脑的CPU，在有一个分组到达输入端口时，会发出一个中断，然后将分组复制到处理器内存中，然后处理器去处理目的地址，再复制到对应的输出端口缓存里。

• 经总线交换

  让输入端口为分组设定一个标签，一个标签对应一个输出端口，每有一个分组到达总线入口时，会被传递到所有的输出端口，但是只有对应标签的输出端口能够接受分组，这就导致了多个分组到达交换结构时，需要排队转发，经总线的方法适合中小型企业。

• 经互联网络交换

  这种复杂的网络由2N条总线组成，连接N个输入端口和N个输出端口，通过交换机控制器负责连接从哪个输入到哪个输出。

  这中是非阻塞并且并行的相对来说成本更高，但是能力也更强。

输出端口

输出端口主要负责取出缓存中的分组并且发送到输出链路上，功能较为简单。

排队处理

输入端口和输出端口都需要排队，

输入排队

输入端口主要是通过FCFS策略来处理，但是会导致这样的情况：

输入两个端口我们设为A0,A1，输出两个端口为B0,B1，这时候A0中两个分组要去往B0，A1的第一个分组去B0，A1的第二个分组要去B1，而交换结构决定要先输送A0的两个分组，这样即使A1的第二个分组要去B1，与B0不冲突，也会导致等待情况的发生，我们称这种情况为HOL阻塞。

输出排队

我们在之前有提到：交换结构会把分组放到输出端口的缓存里，那么肯定会有一个上限，当输出端口的缓存不足以存入一个新的分组时，要么会弃尾（即丢弃到达的分组），要么删除已经排队的分组，也有在缓存填满前就删除分组的，总之，解决的方法很多，这些方法统称为队列管理算法，随机早期检测算法是研究实现比较广泛的算法之一。

当输出端口对排队的分组进行传输时，需要进行抉择哪一个先传输，这一步被称为输出端口的分组调度，我们将在下一节仔细讨论。

对于输出端口缓存的分配，一般认为有如下公式：

$$缓存数量B=RTT*链路容量C$$

分组调度

对于分配次序问题，与操作系统中的类似，有如下三种方法

• 先进先出

  这个就不解释了。

• 优先权排队

  有一些分组可能需要更快的传输速度，比如语音通话，有些例如电邮这种就可以是低优先权的，因此可以维护不同优先权的分组队列，要注意的是分组传输时是非抢占式的，即开始传输后到结束前不能被打断。

• 循环和加权公平排队

  循环排队就是不分出不同优先权的队列，但是在选择时按优先级选择，优先级低的先跳过，等优先级高的传完了再来传它。

  在加权公平中，仍然是对分组进行分类，不过不同的是会为每个类分配不同的吞吐量，根据该类在所有分类中的比重加权。

网际协议

IPv4

一个链路层帧能够承载的最大数据量叫做最大传送单元(MTU)，由于MTU的限制，往往IP收到的分组大小大于MTU，这时候就要对分组进行分片，这部分了解即可。

IPv4编址

主机和物理链路之间的边界叫做接口，主机和路由器都会与多个物理链路连接，因此IP要求每台主机和路由器接口都拥有自己的IP地址。

IP地址长度为32bit，每一个字节（8位）之间用一个点区分开，并且每个字节用十进制表示，这种记法叫做点分十进制记法。

子网掩码

我们在这里拿一个路由器举例，这个路由器具有三个接口，我们发现不同接口可以对应到多台IP地址左24bit相同的电脑，我们称这多台电脑（主机）和路由器端口组合起来的网络称为一个子网，他们IP地址的相同点在于223.1.1，所以称子网掩码为223.1.1.0/24，24是指左24bit定义了子网地址，任何其他要连接到223.1.1.0/24的网络都要求其地址具有223.1.1.xxx的形式。

同时这里前24位称为子网地址，后面的8位被称为主机地址。

一般来说，IP地址的网络部分被限制为8、16、24bit，分类编址的编址方案将其分为了A、B、C类网络，A类可以拥有最多的主机，有2^24-2个，C类则最小，只有2^8-2个，其中-2的原因是有特殊用途。

动态主机配置协议DHCP

一般来说，我们连上WIFI或者以太网后，就可以直接上网，而不需要手动打开网络中心为我们设置一个IP地址，这都是DHCP的功能，它允许主机来自动获取一个IP地址。

一般来说，每个子网具有一台DHCP服务器，如果没有的话则有一个DHCP代理（可以认为是路由器），这个代理知道用于该网络的DHCP服务器的地址。

DHCP实现IP分配有四个步骤：

1. DHCP服务器发现。

   主机通过发送DHCP发现报文发现一个要与其交互的DHCP服务器。使用广播地址255.255.255.255发送到子网的所有主机，这样就能发送给不知道具体地址的服务器

2. DHCP服务器提供

   当DHCP服务器接收到发现报文时，将DHCP提供报文同样通过广播地址发送给所有结点。报文含有收到发现报文的事务ID、推荐IP地址，网络掩码和IP地址租用期，即可用时间。

3. DHCP请求

   用户从DHCP服务器中选择一个并且发送请求报文。

4. DHCP ACK

   这则是对DHCP的请求进行回应。

网络地址转换

管理IP的主要方法被称为网络地址转换（即我们俗知的NAT，network address translation），我们先看一个例子。

在该图中，右边是一个家庭子网，里面的主机都有想用的网络地址10.0.0/24，对于10.0.0.0/8这样的地址，是专用网络所用的地址。只有在某一个网络中在有效，显然，在子网中，10.0.0.1主机可以和其他主机使用10.0.0/24进行通信，然而其他网络中的主机不能使用这个地址进行网络间的通信，也就是说，专用网络的地址只能在网络里通信，无法在网络间通信。

那么如何进行网络间通信，这就用到NAT使能路由器了，我们可以想象有许多家相同配置的酒店，酒店内拨打电话直接打房间号就行了，A酒店333房间的客人拨打332，只会打到A酒店的332，和B酒店的332或者其他酒店的332都没有关系。如果要跟B酒店的332通信，那就派人（也许）从A酒店的大门出去，到B酒店332去联系，反之要接收到，也得用A酒店的大门进来。这里我们的酒店的大门（或者前台），就是我们的路由器。进行消息分配（房间到房间），就要查入住记录（NAT转换表）。

这个酒店（路由器）的地址则是DHCP分配的地址。

在图中，有一个小例子，专用网络中的10.0.0.1主机想要访问128.119.40.186:80的网页，他从3345端口发送了数据报到LAN（本地网络）中，路由器接收到这个要发出去的数据报，进行改装，将原地址10.0.0.1:3345变为138.76.29.7:5001，发送到128.119.40.186:80，并且在NAT转换表中记住这个关系，然后远程的128.119.40.186的服务器响应后返回数据报到138.76.29.7:5001时，路由器又根据NAT转换表将数据报分给10.0.0.1:3345上。

IPv6

在IPv6中，IP地址长度从32bit增加到了128bit，整整4倍的增加带来的是数不尽的地址数量，确保了IP地址的用之不竭。同时首部进行了优化，仅包含40字节，并且引入了流标签。这些一笔带过即可。

不过如何协调IPv4和IPv6设备之间的兼容性呢？我们接下来主要理解建隧道的这种方法。

假设两个IPv6结点要进行IPv6数据报进行交互，但它们经由IPv4路由器互联的，我们将这样的一个集合成为隧道，IPv4路由器会对数据报进行封装，就像对待普通数据一样，然后进行传输。

通用转发和SDN

在我们之前讲到NAT的时候，这其实是一种中间盒，即对数据报进行包装转发，交换机和路由器这种中间盒使得网络间数据转发变得困难了许多，我们可以将数据报转发的过程分为两个步骤：”匹配“和”转发“。

匹配是对协议栈的首部字段进行匹配，根据不同的匹配结果如何转发给不同的输出端口进行不同的处理。

OpenFlow

这是一种网络标准，引入了SDN（软件定义网络）抽象和功能。

匹配加动作转发表在OpenFlow中称为流表(flow table)。

匹配

匹配时，我们可以跨越三层协议进行首部检查和匹配，匹配完成后，根据结果进行不同的动作，合理的动作可能有转发、丢弃（防火墙）、修改字段等动作。

网络层：控制平面

概述

数据平面的转发形式有两种：基于目的地转发（使用转发表）和通用转发（使用流表），基于目的地转发中，主要由接下来要介绍的路由转发算法决定；而通用转发是软件定义的。

关于转发表和流表是如何计算、维护和安装的，有两种可能的方法：

• 每路由器控制，由每个路由器自己根据路由选择算法计算。
• 逻辑集中式控制，根据一个单独的中间盒（CA代理）来控制。

路由选择算法

在这里我们用图来表示路由器之间的物理链路，并且使用的是一个带权无向图（不同路由器之间都可以进行分组转发），权值代表对应链路的物理开销，显然，最低开销就是我们的最短路径。

不过计算方式有两种，根据算法集中分散分为：

• 集中式路由选择算法，用全局的网络来计算最低开销，即得到的是全局最优解，这种算法被称为链路状态算法（LS算法）
• 分散式路由选择算法，每个结点只有与其直接相连链路的开销知识，使用的是距离向量算法（DV算法）

第二种分类是：静态路由选择算法和动态路由选择算法

第三种分类是：负载敏感算法和负载迟钝算法

LS算法

其实就是Dijkstra，很简单

不过在实际运用中，如果每个路由器都是用LS算法，链路中可能会出现震荡的情况，所以我们有解决方法是避开高度拥塞的链路或者让每台路由器发送链路通告的时间随机化。

DV算法

DV算法是一种迭代的、异步的和分布式的算法。令$d_x(y)$是x到y的最低开销路径的开销，有

$$d_x(y)=min_v\{c(x,v)+d_v(y)\}$$

其中v是x的所有邻居（其实应该还要包含x自己），我们设想v*为这个最低开销的邻居节点，那么我们要沿着最低开销路径向y转发分组的话，就得先向v*转发。

接着就可以讲讲DV算法的基本思想了，每个节点x都维护有一个距离向量Dx=[$D_x(y):y\in N$]，注意这里使用的是大写D，不是之前我们定义的最低开销，这只是预计开销。

在这个算法里，每个结点都知道其邻居直连的开销，然后不时地跟邻居发送自己的距离向量，如果有邻居接收到了新距离向量，便顺带更新自己的距离向量，如果自己的距离向量有变化，则跟所有邻居发送更新后的距离向量。

这样异步地迭代下去，$D_x(y)$便会收敛到$d_x(y)$

我们可以用一个图来简单地描述一个两两相连的三个路由器的DV算法更新过程

DV算法的故障

在距离发生改变时，根据开销变大或变小会出现不同的迭代情况，如图

c(x,y)从4变为1时，只需要通过两次的迭代到达静止状态，而从4变为60时，y到x的距离开销会因为上一次z告诉y的到x的开销而计算错误，从而反复迭代形成一个路由选择环路，这会有44次迭代，如果开销变得更大，也会有更多的迭代次数，这种问题称为无穷计数问题。所以我们引出一种叫毒性逆转的技术。

DV算法：毒性逆转

实际上思想比较简单：如果z以y为媒介到达x，则z告诉y到x的距离为$\infin$，这个解决了我们上面描述场景的无穷计数问题，但是涉及3个及以上节点的环路无法用它解决。

自治系统与OSPF

我们上述讨论的都是路由器之间的连接，由于不可能将全世界所有的路由器连接成一个大规模网络（那样计算量过大了），同时每个ISP下可能想有特定方法运行路由器，所以我们将路由器组织进自治系统(AS)，一个AS是由一组相同管理控制下的路由器组成。

开放最短路优先OSPF

OSPF用于AS内的路由选择，是一种链路状态协议，OSPF有以下特点

1. 每台路由器在本地运行Dijkstra最短路算法，确定自身为根节点到所有子网的最短路径树，路径开销由网络管理员配置。
2. 路由器会向AS中所有路由器广播路由选择信息。

OSPF的优点：

• 安全
• 多条相同开销的路径，允许使用多条路径来降低拥塞
• 对单播与多播路由选择的综合知识
• 支持在单个AS中的层次结构

域内路由选择RIP

RIP是一种距离协议，使用跳，跳是指从源路由器到目的路由器经过的子网数量。其他维护的RIP表其实和DV算法类似。

ISP之间的路由选择：BGP

AS内的通信协议是OSPF，AS间的为边界网关协议（BGP），同时这也是一个重点。

在AS内转发，路由器的转发表由路由选择协议决定，而需要转发到AS外的路由器时，需要由BGP来决定，由于BGP只是负责AS间，或者说子网间的通信，那么BGP决定的目的地是一个前缀，例如138.16.68/22，这跟子网掩码很像(138.16.68.0/22)，因此一台路由器的转发表具有形式为(x,I)的表项，x是前缀，I是路由器的接口号。

BGP会为每个路由器做以下事情：

1. 从邻居AS获得前缀的可达性信息
2. 确定到该前缀的”最好”陆游。

下面我们就看这两件事情具体是怎么做的

通告路由

对于每个AS，每台路由器要么是网关路由器要么是内部路由器。网关路由器是一个AS与其他AS的一个或多个网关路由器连接的路由器，而内部路由器仅和该AS的网关路由器或内部路由器连接。

如果有这三个AS，向所有路由器通告前缀x的可达性信息，那么AS2会收到"AS3 x"，AS1会收到"AS2 AS3 x"，即报文会带上路径信息和前缀信息。

BGP协议下，每对路由器都是用179端口上的半永久TCP连接交换路由选择信息，这称为BGP连接，外部的BGP连接为eBGP，而内部的为iBGP。

如图所示，iBGP并不总是和物理链路对应。

当AS3要跟AS1通告x在AS3中时，有如下步骤

BGP类型	源	目标	内容
iBGP	3a	2c	AS3 x
eBGP	2c	2?	AS3 x
iBGP	2a	1c	AS2 AS3 x
	1c	1?	AS2 AS3 x

其中?表示对AS内的其他路由都发送这个报文。

确定路由

实际上，从一个给定路由器到一个目的子网可能有多条路径，那么如何确定路径并且配置转发表呢？我们需要引入一些BGP属性，BGP前缀及其属性被称为路由，较为重要的两个属性为AS-PATH和NEXT-HOP，AS-PATH包含了已经通过AS的列表，同时，如果一台路由器在AS-PATH中看到包含了自己，他将拒绝这个通告。

NEXT-HOP是AS-PATH起始的路由器接口的IP地址，对于从2a到1c的路由"AS2 AS3 x"，NEXT-HOP指的是2a左边接口的IP地址，于是AS1中的路由器知道了到达前缀x的两台BGP路由：

1. 2a左侧接口的IP地址：AS2 AS3 x
2. 3d左侧接口的IP地址：AS3 x

所以这里我们的BGP路由有三个组件：(NEXT-HOP AS-PATH 目的前缀)

热土豆路由选择

在这个奇怪名字的算法里，路由器首先会从BGP中学习到到达前缀x的路由，然后选择路径最短的网关发送分组，例如同样是到达3d的x，1b由于到2a的开销为1，到3d的开销为2，会选择通过1c来向外发送分组，并且找到通往2a的位于最低开销路径（1b->1c->2a）上的接口I，将(x, I)加入转发表。总之，这个算法是当前AS最优的。

路由器选择算法

实际上，BGP选择了比热土豆更复杂却有其特点的的一种算法。对于任何给定的目的地前缀，如果仅有一条路由，我们肯定选择，如果有多条路由，我们使用如下规则知道只有一条路由。

1. 路由被指派一个属性为本地偏好，这个属性由一种策略决定，可能是被认为设置或者学习得到。
2. 从余下的路由中选择具有最短AS-PATH的路由，如果该规则是路由选择的唯一规则，则使用AS间的DV算法。
3. 从余下的路由中使用热土豆留有选择
4. 如果还有，则使用BGP标识符

IP任播

除了AS间路由选择协议使用BGP外，DNS的IP任播服务也会使用到，例如CDN公司为其多台服务器指派相同的IP地址，并且使用BGP来让服务器通告IP地址，当某台BGP路由器收到对于IP地址的多个路由通告时，将其处理为对相同的物理地址提供不同路径。配置路由转发表时，则通过路由选择算法挑选到IP地址最好的路由。

ICMP：因特网控制报文协议

ICMP被主机和路由器用来沟通网络层的信息，最典型的用途就是差错报告，比如不可达、未知等。linux中的ping就是通过发送ICMP报文来实现的

网络管理和SNMP

我们将在这一小节简单了解网络管理的关键组件

• 管理服务器是一个应用程序、控制网络管理信息的收集处理分析或显示
• 被管设备，可以是任意的联网设备
• 管理信息库，用于收集被管设备中被管对象的关联信息
• 网络管理代理驻留在被管设备中，是一个与管理服务器通信的进程
• 网络管理协议运行在管理服务器和被管设备中，允许管理服务器查询被管设备的状态或采取行动。

SNMP：简单网络管理协议

这是一个应用层协议，用于在管理服务器和代表管理服务器执行的代理之间传递网络管理控制和信息报文，常用的两种方式为：

1. SNMP管理服务器向SNMP代理发送一个请求，代理接收到请求执行某些动作然后响应
2. 代理向管理服务器发送一个陷阱报文，用于通知服务器异常情况导致的MIB对象值的改变。

链路层和局域网

概述

运行链路层协议的任何设备称为节点，将连接相邻节点的通信信道称为链路，为了将数据报从源主机传输到目的主机，就必须通过各段链路进行传输

链路层提供的服务（特点）有：

1. 成帧，即一个帧由数据字段和若干首部字段组成
2. 链路接入，MAC（媒体访问控制）协议规定规则
3. 可靠教父
4. 差错检验和纠正

我们还需要知道链路层是在哪里实现的，一般来说在路由器中，是在路由器的线路卡中实现，如果是在主机中，则在网络接口卡（网卡，NIC）的链路层控制器上实现。

差错检测和纠正技术

奇偶校验

当发送d个bit数据时，发送方包含一个附加比特使得这d+1个bit中1的总数为偶数，或者说，附加比特为1当d比特数据中1的个数为奇数时。显然这种方法比较简单，但是未能检验出差错的概率也比较高，于是有了二维奇偶校验

d个比特被划分为i行j列，每行每列都有一个校验bit，最后右下角还有一个校验bit，于是就有i+j+1个校验bit。

接收方检测和纠正差错的能力被称为前向纠错

检验和方法

与TCP和UDP中的类似

循环冗余检测

即CRC编码，考虑d比特数据D，要发送的话，需要协商一个r+1比特模式，称为生成多项式G，并且G的最高有效位比特为1，对于一个给定的数据段D，发送方要选择r个附加比特R，加到D的右边，使得用模2算数恰能被G整除，其实就是从左到右异或。

我们可以根据公式推出R的计算方法

$$D*2^r\ XOR\ R = nG \\ D * 2^r = nG\ XOR\ G\\ R = remainder \frac{D*2^r}{G}$$

可以写出程序：

def CRC_calc(D, G):
	d = D.bit_length()
	r = G.bit_length() - 1
	D2r = D << r
	i = 0
	while D2r.bit_length() > r:
		l = D2r.bit_length() - r - 1
		D2r = D2r & ((1 << l) - 1) | ((D2r >> l ^ G) << l)
	return D2r
		
		
print(bin(CRC_calc(0b10110011, 0b11001)))

多路访问链路和协议

链路主要有两种形式：点对点链路和广播链路。

PPP（点对点协议）和HDLC（高级数据链路控制）就是点对点协议，广播协议能够让多个发送和接收节点连接到相同的、单一的、共享的广播信道上，如何协调多个节点对一个共享广播信道的访问，就是多路访问问题。

多路访问协议可以划分为三种类型：信道划分协议、随机接入协议和轮流协议

信道划分协议

有两种在共享信道之间划分广播信道带宽的技术：时分多路复用TDM和频分多路复用FDM

TDM就是把一个时间段分成多段个不同节点用于发送，且消除了碰撞的可能，FDM则是将R bps的信道划分为不同的频段，并把每个频率分配给节点，FDM有它的好处，即一个节点能够连续发送数据而不用考虑时间的问题，但是也限制了带宽大小

还有一种神奇的信道划分协议是码分多址CDMA，CDMA为每个结点分配一种编码，如果分配得当，则不同的结点能够同时传输且接收方也能正确接收。

随机接入协议

在这个协议中，一个传输节点总是以信道的全速率进行发送，当有碰撞时，涉及碰撞的结点反复发送帧直到通过为止，并且经历碰撞后不是立即重发，而是经过一个随机时延才发送。

时隙ALOHA

这是一种最简单的随机接入协议，在描述这个协议时，需要做如下假设

• 所有帧由L比特组成
• 时间被划分为L/R秒的时隙
• 节点在时隙起点传输帧
• 节点是同步的
• 如果一个时隙里有多个节点碰撞，则所有节点在时隙结束前都知道碰撞事件
• 当一个节点有新帧要发送时，会等到下一个时隙开始并发送帧
• 如果有碰撞，则以p概率在后续的每个时隙重传帧，知道帧无碰撞传输出去

ALOHA看起来是个不错的协议，当只有一个活跃节点时，他表现优秀（废话），但当有多个节点时，我们定义时隙多路访问协议的效率为：当有大量活跃节点且每个节点总有大量帧要发送时，长期运行中成功时隙的份额（一个时隙被分类为空闲时隙、成功时隙和碰撞时隙）

经过概率论的推导，能够知道当有N个活跃节点时，时隙ALOHA的效率为$Np(1-p)^{N-1}$，并取极限能够知道概率趋近于37%

ALOHA

在这个纯ALOHA中，帧在到达时便开始传输而不要求在时隙的开始，且碰撞后立即以概率p重传，否则等待一个帧传输时间，再以概率p传输。可以得出这个纯ALOHA协议的效率为1/(2e)

CSMA(载波侦听多路访问)

在这种协议里，有两个原则：

1. 先侦听信道，如果有帧正在发送则不进行发送，这叫载波侦听
2. 如果有其他节点发送帧影响了当前节点的帧的发送，则停止发送，这叫碰撞避免

表面上，规则1决定了规则2不会发生，但是由于信道传播时延的存在，所以可以是会发送的。

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

1）适配器从网络层一条获得数据报，准备链路层帧，并将其放入帧适配器缓存中。

2）如果适配器侦听到信道空闲(即无信号能量从信道进入适配器)，它开始传输帧。

在另一方面，如果适配器侦听到信道正在忙，它将等待，直到侦听到没有信号能量时才开 始传输帧。

3）在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在。

4）如果适配器传输整个帧而未检测到来自其他适配器的信号能量，该适配器就完成 了该帧。在另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，它中止传输(即它停止了传输帧)。

5. 中止传输后，适配器等待一个随机时间量，然后返回步骤2。

选择随机时间量机制叫二进制指数后退，即在经历n次碰撞后，从0…<$2^n-1$中选择一个数

令$d_{prop}$为信号能量在任意两个适配器之间传播所需的最大时间，令$d_{trans}$为传输一个最大长度的以太网帧的时间，我们有CSMA/CD的效率公式如下

$$\frac 1 {1 + 5d_{prop}/d_{trans}}$$

CSMA/CA(带有碰撞避免的载波侦听多路访问)

挺简单的，上图，无线网中不使用CSMA/CD的主要原因是因为有信号衰减的问题，导致了难以检测碰撞。

轮流协议

如何将M个节点活跃的时，每个活跃节点的吞吐量接近R/M bps呢，这让研究人员创造了轮流协议，我们在这介绍轮询协议和令牌传递协议

轮询协议是让主节点轮询每个节点，告诉它能够传输帧的最大数量，然后对一个节点发送完后，主节点再对下一个节点进行如上操作。

但是这个协议问题在于只有单一节点的时候带宽不能跑满

令牌传输协议中，一个特殊的被称为令牌的帧在节点间交换，一个结点收到令牌时，当且仅当他有帧要发送，持有令牌，否则向下一个节点转发令牌。

交换局域网

在一个局域网内部，交换机之间使用链路层寻址

链路层寻址和ARP

MAC地址

事实上并不是主机或者路由器具有链路层地址，而是它们的适配器具有链路层地址，因此具有多个网络接口的主机或路由器也有多个与之关联的链路层地址。

链路层地址有各种不同称呼：LAN地址、物理地址、MAC地址(常用)

MAC地址长度为6字节，通常每个字节表示为一对十六进制数，用"-"号连接，MAC地址是固定且唯一的（虽然他可以被更改），当某适配器向目的适配器发送一个帧时，发送适配器将目的适配器的MAC地址插入到帧里，并将帧发送到局域网上，进行广播，目的适配器检测到与自己的MAC地址匹配的帧时，就将其接收。

如果发送适配器想让局域网上所有适配器都收到呢？与IP广播地址类似，MAC地址也有"FF-FF-FF-FF-FF-FF"这样一个广播地址来使所有设备接收到。

ARP地址解析协议

ARP可以将IP地址和MAC地址进行相互转换，在如图的局域网中，每台主机和路由器有IP地址和MAC地址。

如果220主机要向222主机发送IP数据报，则需要知道222的MAC地址，通过向ARP提供222的IP地址可以知道222的MAC地址，这有点类似DNS，不过DNS是将主机名解析为IP地址。当然了，ARP只在一个子网里能够起作用，跨子网是不行的。

每台主机或路由器在内存器中都维护一个ARP表，ARP的每个记录也有一个TTL值，表示从表中删除映射的时间。对于要读取不在ARP表中的MAC地址时，发送方会构造一个ARP分组，包括发送和接收地址及MAC地址等字段，将这个ARP分组在子网链路层中广播，目标适配器会返回带有希望映射的ARP分组，之后查询主机便能够更新其ARP表，并发送IP数据报。

如果要发送到子网之外的主机上，有趣的是，主机都只有一个MAC地址，而路由器两个端口上分别有一个MAC地址

数据报从111到222的过程里，应该是先发送到110即路由器做左端口上的适配器上，然后路由器转发到220接口上，再通过链路层发送给222。

以太网

以太网在现在的优先局域网中广泛分布。

集线器作用于每个比特，当接收到一个比特时，将其放大传输到发送接口。

比起集线器，21世纪初处实现的交换机更为重要，将在之后介绍。

当一台主机向另一台主机发送一个IP数据报时，如果主机在相同的以太局域网上，发送器会在一个以太网帧中封装一个IP数据报，并把该帧传递到物理层。

以太网帧中比较重要的是源地址和目标地址，均为6字节，记录的是MAC地址，同时以太网帧中还有一个奇妙的前同步码，共8个字节，前7个为10101010，最后一个为10101011，用于校准适配器上的时钟漂移。

以太网向网络层是无连接的、不可靠的，前者代表没有握手，后者代表无法接收帧（出错时）不会有反馈。

以太网实际上就是我们日常生活中用到的网线，根据不同传输速率和物理层，有双绞线、光纤等，每种线也有距离限制，可以通过转发器延长距离。

链路层交换机

交换机对子网中的主机和路由器是透明的，即不知道有交换机的存在，因此交换机的输出接口设置有缓存，和路由器类似。

交换机转发和过滤

过滤指应该转发帧还是丢弃。转发和过滤两个操作都是借助于交换机表完成。

一个表项包括交换机接口、接口通向的地址和生成表项的时间。

当一个帧从交换机的接口x到达，有三种可能的情况。

1. 表中有对应地址，但是接口y=x，丢弃帧
2. 表中有对应地址，接口y!=x，将帧转发到y上。
3. 表中没有对应地址，交换机向除了x外的接口转发帧。

自学习

交换机的表是自动建立的，而不需要认为干预，我们称交换机是自学习的。

自学习由以下几个步骤实现：

虚拟局域网

虚拟局域网（VLAN），允许单一的物理局域网设施定义多个虚拟局域网，通过对端口进行划分，能在每个划分出来的组中形成一个VLAN，只能在组内通信。

那么可能会有组间通信，这就需要通过一个中间的路由器转发了，需要将一个端口定义为属于EE VLAN和CS VLAN，数据报将从EE VLAN发出，路由器再发送到CS VLAN上，如果是在两个交换机，也可以将交换机上分别定义CS VLAN的端口，然后将这两个端口连接起来（对 EE VLAN）也这样做，但是当多个交换机在一起时，端口占用数量就太多了，所以有VLAN 干线连接。

在VLAN干线连接中，一个端口被配置为干线端口，发送到该端口的帧会被转发到其他的交换机上，并且以太网帧格式得到扩展–802.1Q，这个帧中在首部加入了4字节的VLAN标签，VLAN标签在发送进干线端口时加上，又在接收端上删除，VLAN标签又由标识符、标签信息和优先权构成。

回顾WEB网页请求的过程

当一台电脑用以太网电缆连接到学校的以太网交换机，交换机和学校的路由器相连，路由器连接到一个ISP（网络服务提供商），ISP提供了DNS服务。假设DHCP服务器运行在路由器中。

网络配置时

在配置电脑的网络时，数据的传输过程是这样的，首先电脑的操作系统生成一个DHCP请求报文，报文放入UDP报文段中，并且被包装入一个目的为广播地址（255.255.255.255）的IP数据报中，IP数据报被包装入一个以太网帧，目的MAC地址为（FF:FF:FF:FF:FF:FF），这个以太网帧也被广播，发送到所有交换机上，路由器也能通过某个交换机接收到以太网帧，分解出IP数据报再得到UDP报文段再得到DHCP请求报文，运行在路由器里的DHCP服务器就给他分配一个IP地址，生成一个DHCP ACK报文，包含分配的IP地址、DNS服务器报文、默认网关路由器的IP地址和子网掩码。按照之前发送来的包装顺序再包装返回给电脑。

电脑收到了ACK报文后，记录下IP地址和DNS IP，并且在IP转发表中配置默认网关，这样电脑的网络就配置好了。

请求网页时

然后请求网页时，首先浏览器生成了一个TCP套接字，套接字向www.google.com发送一个HTTP请求，为了生成套接字，首先需要知道www.google.com的IP地址，因此操作系统生成一个DNS查询报文，报文段承载着网址、DNS服务器地址、和源地址发送到53号端口上，这时候以太网帧应当发送到学校的路由器上，但是不知道路由器的MAC地址，没关系，可以通过已知的网关路由器地址，生成一个ARP查询报文，该报文会通过广播地址发送，路由器收到后会发送一个ARP回答，并且发送其的MAC地址，电脑收到这个地址后，就知道了目的地址，于是发送DNS查询报文。

注意在这里，实际上报文的发送顺序是（ARP报文，DNS报文的以太网帧）

得到网页IP地址

网关路由器获得到这个DNS查询的IP数据报后，发送到ISP的AS（自治系统）的一个路由器里，然后通过我们学过了路由器算法（域内RIP、OSPF、ISIS和域间的BGP）这些协议填写的转发表使得我们的数据报能在路由器间顺利转发到DNS服务器上，服务器根据缓存找到网址对应的IP地址，然后再返回到电脑。

终于请求网页

电脑获得到了目的IP地址，能够生成一个TCP套接字，向www.google.com发送一个HTTP GET报文，首先TCP会进行三次握手，发送一个TCP SYN报文，目标服务器生成一个TCP套接字，并返回一个TCP SYNACK，这时候电脑进入连接状态，将GET报文写入套接字，服务器再生成一个HTTP响应报文，将网页内容放入HTTP响应体中，发送进套接字，电脑收到后，终于显示出了网页的样子。