计算机网络

计算机网络概述

计算机网络是由若干结点和连接这些结点的链路组成,计算机网络是互联互通的,无主从关系的计算机集合.网络之间可以通过路由器连接起来,组成一个更大的计算机网络,称为互连网.即网络的网络.网络许多计算机连接在一起,互连网把许多计算机网络通过路由器连接在一起.与网络相连的计算机通常称为主机.

互连网(internet)是一个通用名词,它泛指由多个计算机网络互连形成的计算机网络.而大写的Internet(互联网)则泛指当前世界最大的,最开放的,由众多网络相互连接而形成的特定互联网,采用TCP/IP协议族作为通信的规则,前身是美国的ARPANET.

互联网的组成

互联网从其工作范围分为两个部分,一部分为边缘部分,一部分为核心部分.边缘部分是所有连接在互联网的主机组的,这部分是由用户直接使用的.另一部分是核心部分,由大量网络和大量路由器构成,为边缘部分提供服务.

我们实现互联网的目的就是为了不同的主机之间可以进行通信,即主机A上的某个进程a要和主机B的某个进程b进行通信,即计算机之间通信.

在网络边缘部分进行通信通常划分为两种方式:客户端(Client)/服务器(Server)与对等方式(P2P).

网络边缘部分

C/S方式

客户端-服务器方式即我们耳熟能详的Client/Server结构,这种方式是互联网最常用的,最传统的方式.服务器为提供服务方,客户端为请求服务方.

• 客户端向服务器请求服务.
• 服务器响应客户端的请求.

P2P对等方式

对等方式P2P方式是指两台主机在通信时并不区分哪一个是服务请求方,哪一个是服务提供方.只要这些设备都安装了P2P软件,就可以互相进行通信.

网络核心部分

在网络核心部分起到核心作用的是路由器,路由器是实现分组交换的关键构件,任务是转发收到的分组.

电路交换

为了弄清分组交换,我们先简单介绍一下电路交换.在电话问世不久后,所有的电话机都需要互相连接,但是所以电话机之间两两相连接是不现实的,有N个电话机需要连接则需要构建N*(N-1) / 2条线路.所以为了解决这一问题,出现了交换机,每一个电话机只需要连接到交换机,由交换机负责电路通信.

从资源的分配角度看,交换是按照某种方式动态的分配传输线路的资源.双方通信需要建立一条专用的物理通路,在双方通信时,资源不会被释放,分为建立连接-占用资源-释放连接三个步骤.这三个步骤的交换方式称为电路交换.

我们注意到当两个电话机进行通信时需要一直占用资源,当电路用来传输计算机数据时, 传输效率会很低.电路交换为了提供工作效率的其他内容如多路复用技术等内容则不做过多介绍.

分组交换

分组交换采用的是存储-转发的方式.我们将要发送的整块数据称为报文,在发送报文之前会将报文分割成若干份,在每一份数据上加一些必要的控制信息组成头部,就形成了一个分组,相比于直接发送报文,分组是互联网中最常见的传送数据单元内,分组的优势在于可以不用等待一个报文接收完毕再去发送下一个报文,利用分组加上路由器转发的特点,就像流水线一样并行进行,极大地提高了信道利用效率.每个分组的传输利用链路的全部带宽.

报文交换

与之相对应的,报文交换也采用的是存储-转发的方式.假如我们不是每次去发送一个个的分组,而是一次性发送一整个报文,整个报文先传送到相邻结点,全部存储下来再去查找转发表,转发到下一个结点,这样的方式就是报文交换.

传输延时

传输延时是指一个分组从一端到另一端所需要的时间,网络中的时延是由不同的部分组成的.

具体可以分为以下四种类型:发送时延、传播时延、处理时延、排队时延.

发送时延:发送时延是主机或路由器发送数据帧所花费的时间.

发送时延=数据帧长度/发送速率.

传播时延:

传播时延是数据帧在传输过程中所产生的延迟.

传播时延=信道距离/电磁波在信道上的速率.

处理时延:

主机或者路由器接受到分组需要花费一定的时间进行转发,这样就产生了处理时延.

排队延时:

分组在进行网络传输时,要经过许多的路由器,在分组进入路由器中要先在路由器队列中等待处理,就产生了排队时延.

计算机网络体系概述

OSI七层模型

OSI七层模型 （Open System Interconnect），全称为开放系统互连参考模型，是国际标准化组织(ISO)和国际电报电话咨询委员会(CCITT)1984年联合制定的开放系统互联参考模型，为开放式互联信息系统提供了一种功能结构的框架。

• 同一层中的各网络节点都有相同的层次结构，具有同样的功能。
• 同一节点内相邻层之间通过接口进行通信。
• 七层结构中的每一层使用下一层提供的服务，并且向其上层提供服务。
• 不同节点的同等层按照协议实现对等层之间的通信。

TCP/IP四层协议模型

OSI的七层协议体系结构的概念非常清楚,理论比较完善,但是它即复杂同时也不实用,TCP/IP的体系结构则完全不同,只保留了应用层,传输层,网际层和网络接口层.虽然OSI七层模型也有很大的研究价值,但是实际上TCP/IP现在在我们的网络世界中得到了非常广泛的应用.

我们将TCP/IP四层协议模型网络接口层拆开,形成五层模型.本篇笔记将以五层模型的视角来一层一层概述,了解到每一层所负责的功能和具体实现.实际应用还是TCP/IP的体系结构设计.

应用层

网络应用的三种体系结构

本文将采用自顶向下的方向依次来描述计算机网络中,各个层之间功能的划分和简单了解具体的实现算法.我们在学习计算机网络前接触最多的应该就是应用层相关的内容,比如DNS域名解析,HTTP以及HTTPS等等协议.在这之前,我们需要先复习一下,常见的网络应用的三种架构.

分别为客户机/服务器结构(C/S),点对点结构(P2P),混合结构(Hybrid),与之前的网络边缘部分常见的两种体系结构相比,多了一个混合结构,也就是将两种结构混合在一起,那么两种混合在一起可以利用两者的优点规避两者的缺点吗?

C/S结构中,服务器提供不间断的服务,在客户端中需要与服务器进行通信,使用服务器提供的服务,不能和其他的客户机直接通信.在P2P结构中则没有一直在线的服务器,任意端系统/结点之间可以直接通信,可自由伸缩,但是难以管理.

所以在混合结构中,我们需要尽可能地利用两者的优点,规避两者的缺点,比如在文件传输时可以采用P2P结构,在文件搜索时可以采用高效的C/S结构.

Web应用

HTTP协议

在我们使用浏览器搜索网络中的资源时,见过最多的应该就是万维网WWW,即World Wide Web,在Web中所遵循的协议就是超文本传输协议,HTTP.在C/S结构中,客户机向服务端请求服务,服务器收到客户机的请求后,响应客户机的请求,发送对应的报文.

在HTTP早期1.0版本中,使用的是非持久性连接,浏览器每次请求都需要与服务器建立一个 TCP 连接，服务器处理完成后立即断开 TCP 连接（无连接），服务器不跟踪每个客户端也不记录过去的请求(无状态),所以每个TCP连接中只允许传输一个对象.

HTTP是一种无状态协议，即服务器不保留与客户交易时的任何状态。

也就是说，上一次的请求对这次的请求没有任何影响，服务端也不会对客户端上一次的请求进行任何记录处理。

一个无状态连接的过程:

• 在HTTP1.0中,假设客户机在浏览器中输入一个URL,包含了文本和十个jpeg图片的链接.
• HTTP客户端需要向URL的服务器发起HTTP请求,端口80
• HTTP服务器在80端口等待TCP连接请求,接受连接并通知客户端
• HTTP客户端将请求消息通过TCP连接的套接字发出
• HTTP服务器收到请求消息,产生响应消息,通过套接字发给客户端
• HTTP服务器关闭TCP连接
• HTTP收到响应消息,发现还有十张图片需要解析,则为每个图片重复以上流程…

我们可以看到,每次都解析都需要进行TCP的重新连接,在这个过程中消耗了大量的资源.如果可以减少连接就可以减轻服务器的负担,所以为了解决这一问题出现了持久性HTTP(HTTP1.1).

HTTP1.1避免了连接建立和释放的开销；通过 Content-Length 字段来判断当前请求的数据是否已经全部接受。不允许同时存在两个并行的响应。

从客户端发送一个很小的数据包到服务器并返回的时间称为RTT(Round Trip Time).在非持久性连接中,每个对象需要2个RTT的参数时间.在持久性连接中,发送响应后,TCP保持TCP连接,后续的HTTP消息可以通过这个连接发送,所以每个被引用的对象耗时为1个RTT.

HTTP消息格式

HTTP协议有两类消息,请求消息和响应消息

HTTP请求消息

请求消息的格式如图所示,由请求行+请求头+请求空行+请求主题构成

上传输入方法

在HTTP1.0中只有POST,GET和HEAD方法,在软件开发中GET和POST方法很常见,所以不做过多叙述,本文只是简单的描述一下HEAD方法.

POST:在请求消息的消息体中上床客户的输入,例如网页需要提交表格单元的内容

GET:输入信息在请求行的URL字段上传

HEAD:是让服务器端不要将所请求的对象放入响应消息中

在HTTP1.1中新增了两个方法,分别为PUT和DELETE方法

PUT:将消息体中的文件上传到URL字段所指定的路径

DELETE:删除URL字段所指定的文件

HTTP响应消息

HTTP的响应消息与请求消息格式相似,HTTP响应消息由状态行+头部行+空行+响应消息主体构成.

常见的状态码	状态码的对应状态
200	客户端请求成功
304	客户端发送了一个带条件的GET 请求且该请求已被允许，而文档的内容（自上次访问以来或者根据请求的条件）并没有改变，则服务器应当返回这个304状态码
400	客户端请求有语法错误，不能被服务器所理解
401	请求未经授权，这个状态代码必须和WWW-Authenticate报头域一起使用
403	服务器收到请求，但是拒绝提供服务
404	请求资源不存在，举个例子：输入了错误的URL
500	服务器发生不可预期的错误
503	服务器当前不能处理客户端的请求，一段时间后可能恢复正常

Cookie与Session

HTTP协议本身是一种无状态的协议,当一个客户机多次向服务器发起请求,服务器并不能分辨是否为同一用户,但是我们在使用网络应用时又需要实现一种有状态的会话,Cookie与Session技术解决了这一问题.

Cookie:

cookie机制采用的是在客户端保持 HTTP 状态信息的方案。当浏览器访问WEB服务器的某个资源时，WEB服务器会在HTTP响应头中添加一个键值对传送给浏览器，再由浏览器将该cookie放到客户端磁盘的一个文件中，该文件可理解为cookie域(键值对的集合)，往后每次访问某个网站时，都会在请求头中带着这个网站的所有cookie值。

每一个cookie都有一个name和一个value，且name是唯一的。相同名字时，后者会覆盖掉前者

Session:

session机制采用的是在服务器端保持 HTTP 状态信息的方案。为了加速session的读取和存储，web服务器中会开辟一块内存用来保存服务器端所有的session，每个session都会有一个唯一标识sessionid，根据客户端传过来的jsessionid(cookie中)，找到对应的服务器端的session。为了防止服务器端的session过多导致内存溢出，web服务器默认会给每个session设置一个有效期, 若有效期内客户端没有访问过该session，服务器就认为该客户端已离线并删除该session。

Web缓存/代理服务器技术

我们知道http协议是无状态的，所以如果有连续的请求访问同一个网页，他就会一直重复发送，这个时候，如果有一个“有状态”的服务器，对之前的请求有记录，那么它在第二次以后的请求中，就可以在缓存中直接发送给客户。

一个使用代理服务器情况下的流程

• 用户浏览器向浏览器的互联网发送请求时,先和代理服务器中及建立TCP连接,并向代理服务器发送HTTP报文
• 若代理服务器中有请求的对象,代理服务器就将这个对象放入HTTP响应报文中返回
• 否则,代理服务器就代表请求的用户浏览器与互联网上的源点服务器进行TCP连接,发送HTTP报文
• 源点服务器就将这个对象放入HTTP响应报文中返回
• 代理服务器收到对象后,先复制在自己的本地存储器中,然后将对象返回给请求该对象的浏览器

采用了缓存服务器的结构降低了链路通信的流量,但是存在请求内容在缓存服务器中已经被更改的情况,即服务器是更改后的最新数据,缓存中还是之前的数据,所以通过HTTP请求头标签If-Modified-Since来解决.

If-Modified-Since是标准的HTTP请求头标签，在发送HTTP请求时，把浏览器端缓存页面的最后修改时间一起发到服务器去，服务器会把这个时间与服务器上实际文件的最后修改时间进行比较。

如果时间一致，那么返回HTTP状态码304（不返回文件内容），客户端接到之后，就直接把本地缓存文件显示到浏览器中。

如果时间不一致，就返回HTTP状态码200和新的文件内容，客户端接到之后，会丢弃旧文件，把新文件缓存起来，并显示到浏览器中。

DNS解析

分布式层次式数据库

域名系统DNS用来便于人们使用的URl地址转换为IP地址,可以采用分布式层次式数据库,比如查询一个edu结尾的URL,需要先从跟服务器解析到对应的eduDNS服务器,在解析到对应的IP地址.

DNS迭代查询

• 客户机向DNS根服务器进行请求
• DNS返回给客户机对应的顶级域名DNS解析服务器地址
• 客户机向顶级域名DNS解析服务器发起请求
• DNS返回给客户机权威DNS解析服务器地址
• 客户机向权威DNS解析服务器发起请求
• 返回对应的IP地址

DNS递归查询

• 客户机向DNS根服务器进行请求
• DNS根服务器向顶级域名DNS解析服务器发起请求
• 顶级域名DNS解析服务器向顶级域名DNS解析服务器发起请求
• 权威服务器给顶级域名DNS服务器返回对应的IP地址
• 顶级域名DNS服务器向DNS根服务器返回IP地址
• DNS根服务器向客户机返回对应的IP地址

Socket套接字

Socket是应用层与TCP/IP协议族通信的中间软件抽象层，是一组接口。在设计模式中，Socket其实就是一个门面模式，它把复杂的TCP/IP协议族隐藏在Socket接口后面，对用户来说，一组简单的接口就是全部，让Socket去组织数据，以符合指定的协议。

在两个不同设备上的应用要进行网络通信就需要用到Socket套接字来完成,需要注意的是这些方法都是由操作系统内核来完成,不同的操作系统的具体实现可能略有差异,但是核心函数依然为下图所示:

socket函数

//返回sockfd

 int  socket(int protofamily, int type, int protocol);

socket函数对应于普通文件的打开操作。普通文件的打开操作返回一个文件描述字，而socket()用于创建一个socket描述符（socket descriptor），它唯一标识一个socket。这个socket描述字跟文件描述字一样，后续的操作都有用到它，把它作为参数，通过它来进行一些读写操作。

• protofamily：即协议域，又称为协议族（family）。常用的协议族有，AF_INET(IPV4)、AF_INET6(IPV6)、AF_LOCAL（或称AF_UNIX，Unix域socket）、AF_ROUTE等等。协议族决定了socket的地址类型，在通信中必须采用对应的地址，如AF_INET决定了要用ipv4地址（32位的）与端口号（16位的）的组合、AF_UNIX决定了要用一个绝对路径名作为地址。
• type：指定socket类型。常用的socket类型有，SOCK_STREAM、SOCK_DGRAM、SOCK_RAW、SOCK_PACKET、SOCK_SEQPACKET等等（socket的类型有哪些？）。
• protocol：故名思意，就是指定协议。常用的协议有，IPPROTO_TCP、IPPTOTO_UDP，它们分别对应TCP传输协议、UDP传输协议等。

bind函数

//把一个地址族中的特定地址赋给socket
int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen);

对应的参数类型为:

• sockfd：即socket描述字，它是通过socket()函数创建了，唯一标识一个socket。bind()函数就是将给这个描述字绑定一个名字
• addr：一个const struct sockaddr *指针，指向要绑定给sockfd的协议地址。这个地址结构根据地址创建socket时的地址协议族的不同而不同
• addrlen:对应的是地址的长度

通常服务器在启动的时候都会绑定一个众所周知的地址（如ip地址+端口号），用于提供服务，客户就可以通过它来接连服务器；而客户端就不用指定，有系统自动分配一个端口号和自身的ip地址组合。这就是为什么通常服务器端在listen之前会调用bind()，而客户端就不会调用，而是在connect()时由系统随机生成一个。

网络字节序与主机字节序
主机字节序就是我们平常说的大端和小端模式：不同的CPU有不同的字节序类型，这些字节序是指整数在内存中保存的顺序，这个叫做主机序。引用标准的Big-Endian和Little-Endian的定义如下：

a) Little-Endian就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。

b) Big-Endian就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。

网络字节序：4个字节的32 bit值以下面的次序传输：首先是0～7bit，其次8～15bit，然后16～23bit，最后是24~31bit。这种传输次序称作大端字节序。**由于TCP/IP首部中所有的二进制整数在网络中传输时都要求以这种次序，因此它又称作网络字节序。**字节序，顾名思义字节的顺序，就是大于一个字节类型的数据在内存中的存放顺序，一个字节的数据没有顺序的问题了。

注意：在将一个地址绑定到socket的时候，请先将主机字节序转换成为网络字节序，而不要假定主机字节序跟网络字节序一样使用的是Big-Endian。由于这个问题曾引发过血案！公司项目代码中由于存在这个问题，导致了很多莫名其妙的问题，所以请谨记对主机字节序不要做任何假定，务必将其转化为网络字节序再赋给socket。

listen函数与connect函数

如果作为一个服务器，在调用socket()、bind()之后就会调用listen()来监听这个socket，如果客户端这时调用connect()发出连接请求，服务器端就会接收到这个请求。

int listen(int sockfd, int backlog);
int connect(int sockfd, const struct sockaddr *addr, socklen_t addrlen);

listen函数参数类型:

• sockfd：要监听的socket描述字
• backlog：相应socket可以排队的最大连接个数

connect函数参数类型:

• sockfd：客户端的socket描述字
• addr：服务器的socket地址
• addrlen：socket地址的长度

accept函数

int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen); 
//返回连接connect_fd

TCP服务器端依次调用socket()、bind()、listen()之后，就会监听指定的socket地址了。TCP客户端依次调用socket()、connect()之后就向TCP服务器发送了一个连接请求。TCP服务器监听到这个请求之后，就会调用accept()函数取接收请求，这样连接就建立好了。之后就可以开始网络I/O操作了。

• sockfd：参数sockfd就是上面解释中的监听套接字，这个套接字用来监听一个端口，当有一个客户与服务器连接时，它使用这个一个端口号，而此时这个端口号正与这个套接字关联。当然客户不知道套接字这些细节，它只知道一个地址和一个端口号

• addr：这是一个结果参数，它用来接受一个返回值，这返回值指定客户端的地址，当然这个地址是通过某个地址结构来描述的，用户应该知道这一个什么样的地址结构。如果对客户的地址不感兴趣，那么可以把这个值设置为NULL。

• addrlen：它也是结果的参数，用来接受上述addr的结构的大小的，它指明addr结构所占有的字节个数。同样的，它也可以被设置为NULL。

  accept默认会阻塞进程，直到有一个客户连接建立后返回，它返回的是一个新可用的套接字，这个套接字是连接套接字。此时我们需要区分两种套接字：

 监听套接字: 监听套接字正如accept的参数sockfd，它是监听套接字，在调用listen函数之后，是服务器开始调用socket()函数生成的，称为监听socket描述字(监听套接字)

   连接套接字：一个套接字会从主动连接的套接字变身为一个监听套接字；而accept函数返回的是已连接socket描述字(一个连接套接字)，它代表着一个网络已经存在的点点连接。

​ 一个服务器通常通常仅仅只创建一个监听socket描述字，它在该服务器的生命周期内一直存在。内核为每个由服务器进程接受的客户连接创建了一个已连接socket描述字，当服务器完成了对某个客户的服务，相应的已连接socket描述字就被关闭。

连接套接字socketfd_new 并没有占用新的端口与客户端通信，依然使用的是与监听套接字socketfd一样的端口号。如果我们只采用一个套接字的话,那么在同一时刻只能有一个进程在被服务,显然不是我们所希望的。

recvmsg()/sendmsg()等函数

至此服务器与客户已经建立好连接了。可以调用网络I/O进行读写操作了，即实现了网络中不同进程之间的通信,网络I/O操作常用的一般为recvmsg()/sendmsg().具体的细节就不做过多描述了。

 ssize_t sendmsg(int sockfd, const struct msghdr *msg, int flags);
 ssize_t recvmsg(int sockfd, struct msghdr *msg, int flags);

close函数

在服务器与客户端建立连接之后，会进行一些读写操作，完成了读写操作就要关闭相应的socket描述字，好比操作完打开的文件要调用fclose关闭打开的文件。

close操作只是使相应socket描述字的引用计数-1，只有当引用计数为0的时候，才会触发TCP客户端向服务器发送终止连接请求。

int close(int fd);

传输层

传输层协议为运行在不同Host上的进程提供了一种逻辑通信机制,是端对端之间的,在下一层的网络层则是主机之间进行逻辑通信.在传输层中一般采用TCP或者DUP来实现.

TCP协议全称是传输控制协议是一种面向连接的、可靠的、基于字节流的传输层通信协议.

UDP协议全称是用户数据报协议，在网络中它与TCP协议一样用于处理数据包，是一种无连接的协议.

在传输层中,是应用进程之间的，一个主机会有多个进程；因此会需要多路复用和多路分用.

也就是在网络层中可能会接收来自其他不同的主机的请求,而每一个主机又会有不同的进程等待处理,所以需要在传输层进行多路复用技术和多路分用技术,来缓解这一问题.

接收端采用多路分用技术,依据收到的Segment交给正确的Socket,即不同的进程.

发送端采用多路复用技术,为每个数据块封装上头部信息,生成Segment交给网络层.

UDP协议的无连接分用:

• 利用端口号创建Socket
• UDP的socket使用二元组标识: 源端口号，目的端口号
• 当主机收到UDP段后会检查段中的目的端口号,将UDP段导向绑定在该端口号的Socket
• 来自不同源IP地址和/或源端口号的IP数据包被导向同一个Socket

TCP协议面向连接的分用:

• TCP的Socket使用四元组标识: 源IP地址,源端口号,目的IP地址,目的端口号
• 接收端利用所有的四个值将Segment导向合适的Socket
• 服务器可能同时支持多个TCP Socket
• Web服务器为每个客户端开不同的Socket

TCP协议面向连接的多线程分用:

注意在上图中P2-P6和P3-P5，它们仅仅只有源端口号不同

而在下图中服务器用一个进程创建多个线程即P4创建了多个线程

UDP协议

UDP协议是基于网络层的IP协议,能够进行简单的错误校验.但是是一种Best effort的服务,也就是尽力而为的策略,可能出现丢包,非按序到达等情况.

虽然UDP传输可能会出现一些情况但是因为UDP是一种无连接的协议,所以实现简单,无需维护连接状态,头部开销小,也没有拥塞控制,可以更好的控制发送时间和速率.常用于一些容忍一定的数据丢失并且对速率敏感的应用如流媒体应用等.

既然UDP是一种尽力而为的协议,那么如何在UDP如何实现可靠的数据传输?

在UDP中有一种简单的检测方式,就是利用校验和来检测UDP段在传输中是否发生错误(如位反转)

发送方:

• 将段的内容视为16进制整数
• 校验和计算,计算所有整数的和,进位加在和的最后,将得到的值按位取反得到校验和
• 发送方将校验和放入校验和字段

接收方:

• 计算收到的段的校验和
• 将其与校验和字段进行对比,检测是否错误
• 需要注意的是没有检测出错误不一定代表没有错误

校验和计算示例:

1110 0110 0110 0110

1101 0101 0101 0101

---

11011 1011 1011 1011

将进位1加入16位中得到1011 1011 1011 1011+1=1011 1011 1011 1100

再将16位sum求反得0100 0100 0100 0011

可靠传输协议RDT

为了保证数据的可靠性,我们就需要做到不错,不乱,不丢.可靠传输协议对应用层,传输层,网络层都很重要,但是信道的不可靠特性决定了可靠传输协议RDT的复杂性.

在应用层中,我们只需要关注数据的发送而不用关心数据是如何传递的,对于应用层来说下面的所有层都是透明的,不可见的,而传输的信道是一种不可靠的,

• rdt_send() 和deliver_data() 都是单向的
• udt_send() 和rdt_rcv() 都是双向的，跟不可靠信道数据交互时，双向传送控制信息

RDT1.0

在RDT1.0版本中,我们假设在不可靠的信道中传输的数据是不会发生错误的,同时也不会丢弃分组,在RDT各个版本的状态描述中,本文采用的用状态机来描述不同状态下的处理过程.

因为在RDT1.0中假设没有错误,所以发送方和接受方只需要发送数据/接受数据就可以,是一种理想的参数模型.

RDT2.0

我们之前提到了RDT1.0版本中,假设信道是不会出错的,但是在实际的信道中,可能在传输中产生位错误的信道,所以在2.0版本中,增加了一些简单的纠错机制.

• 增加了校验和,用于检测信道中可能反转的位
• 接收方返回发送方的控制确认消息ACK\NAK,接受方用来返回给发送方分组是否有问题
• 重传机制,如果收到接受方发送的NAK,那么发送方重新给接受方发送分组

在RDT2.0中,发送方新增了一个状态用来接收ACK/NAK信号,而接受方根据分组是否损坏来判断给发送方ACK或NAK信号.

RDT2.0无错误场景:

RDT2.0有错误情景:

RDT2.1

rdt2.0有着一个致命的缺点，只考虑了发送方到接收方的数据传输，如果ACK/NAK信号出现了位反转,那么就离我们所预期的情况相距很远.

由此rdt2.1应运而生，在rdt2.0的基础之上，发送方在打包数据包时添加了0或者1编号，同样ACK,NAK字段上也添加了0，1字段，表示0.1号字段的确认或者否定。发送方就有了2种状态发送0号数据包，1号数据包，接收方也有了2种状态等待0号数据包和等待1号数据包。现在假设情景发送方向接收方发送0号数据包，如果接收方接收到0号数据包，返回ACK，但是ACK出现翻转，接收方处于等待1号数据状态，发送方重复发送0号数据，接收方会拒绝0号数据，避免重复。如果接收方接收到0号数据包出现错误，返回NAK，但是NAK出现翻转，接收方处于等待0号数据状态，发送方继续发送1号数据，接收方会拒绝1号数据，避免错序.

• 为ACK/NAK增加校验和,检错并纠错
• 如果ACK/NAK出现错误,发送方重传
• 为了防止出现重复分组,发送方为每个分组增加序列号
• 接受方丢弃重复分组

RDT2.1发送方,对应ACK/NAK破坏:

RDT2.1接收方,对应ACK/NAK破坏:

为什么0,1两个序号就可以实现?

答案很简单,因为是SW协议,两个进程需要保持同步状态后才进行下一次操作,只需要保留当前的序号包以及下一次的序号包就可以,所以不需要保留更多的状态.

为什么当ACK信号产生位反转,接受方收到后为什么发送一个ACK状态?

当ACK信号产生位反转后,发送方会重新发送0号分组,说明我们之前发送的ACK状态产生了错误,所以我们需要告诉发送方已经成功接受到了,重新ACK,保持两个进程的同步状态.

RDT2.2

RDT2.2是基于RDT2.1的一种没有NAK消息的协议,我们一定需要ACK/NAk两个状态来表示信息的状态吗,可不可以只采用一个ACK来代表两个状态?

RDT3.0

信道传输中,既可能发生错误,同时在路由器转发中可能会出现分组丢失的情况,如果ACK状态在存储-转发的过程中被丢失了,这样两个进程之间都不能进行同步,会一直等待对方的状态信息,因此RDT3.0中新增了一个超时重传的机制.

虽然有了timeout这个重要的机制,但是如何设置timeout的时间就成为了我们的问题

如下图所示,根据timeout设置的不同,可能会出现各种的问题:

• 比如当丢包后需要一直等待timeout超时重新发送,信道利用率不高

• 当ACK状态信息丢失时也需要等待timeout超时后重新发送,信道利用率不高
• 如果ACK状态没有丢失,只是在路由中阻塞了,但是timeout设置时间过短,发送方重新发送分组后就接受到了之前分组的ACK状态,就会出现早熟的问题…

滑动窗口协议

GBN协议

GBN协议(Go-Back-N回滚N帧协议),中采用了流水线技术,为了解决RDT3.0中效率底下的问题,因为RDT3.0采用了Stop-Wait协议,所以需要一直等待一个分组被正确接受后才开始下一个.

也就是在RDT协议中,不管是发送方还是接受方,双方都只有一个缓存用来接受数据

在流水线协议中,我们希望可以缓存扩充,同时序列号也扩充,允许发送方在收到ACK之前连续发送多个分组.

• 在GBN协议中将发送方的缓存空间称为窗口,窗口的尺寸设为N,即最多允许N个分组未确认,GBN是一种累积确认的机制,接受到ACK(n)说明序列号n(包含n)的分组已经被正确接受

• 为空中的分组设置计时器

• 超时Timeout(n)事件:重传序号大于等于n,还未收到ACK的所有分组.

• 因为发生超时事件后，会重传所有序列号大于等于n的，因此存在资源浪费的情况

• 在GBN协议中,发送方有缓存空间,而接收方只有一个分组的空间,如果没有接受到就一直发送对于的ACK信号,希望发送方重新发送

  

GBN例题

数据链路层采用后退N帧(GBN)协议，发送方已经发送了编号为0~ 7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认则发送方需要重发的帧数是多少?分别是那几个帧?

解:根据GBN协议工作原理，GBN协议的确认是累积确认，所以此时发送端需要重发的帧数是4个,依次分别是4、5、6、7号帧.

假如某一层采用了GBN协议中,假如pkt2分组发送中丢失了,那么在发送方何时重新发送,接受方会是什么状态?

如图所示,会在超时后重新发送pkt2及后面的分组,而接受方在收到其他的分组时会丢弃,一直发送ACK1(上一个的ACK状态),告诉发送方pkt2丢失了,直到成功接收pkt2后发送ACK2状态.

SR协议

GBN协议后我们发现当一个分组丢失后,后面的所有分组都需要重新发送,就会产生大量的重复分组,因为在接受方每次只能接受一个分组,所以SR(Selective Repeat)协议相比于GBN协议,多了一个接受方的窗口.SR单独确认，可以接收乱序到达的分组.

如果收到ACK，假如该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧.

每个帧都有自己的定时器，一个超时事件发生后只重传一个帧.

SR接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧（收到谁确认谁），直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前移动滑动窗口.

如果收到了窗口下界之前的帧，就返回一个ACK。其他情况，就忽略该帧.

TCP协议

TCP协议也是在传输层中常用的协议之一,TCP协议是一种可靠的传输方式.TCP协议在通信双方发送数据之前要先创建连接,TCP连接包括Socket,连接控制变量,缓存等内容.下图为TCP报文段的格式,可以看到,相比于UDP,TCP的头部更为复杂.

• 序号: 在其他的文章中也可以用Seq描述,指的是数据段中第一个字节的编号,而不是数据段的编号,在建立TCP连接时,双方随机选择序列号.
  • 假如有1K的数据，拆分成两个segment,那么第二个segment的序号号通常是501或者500,是segment中第一个字节的编号；并不是segment个数的编号
• 确认号: 即ACK信号,是希望接收的下一个字节的序列号.
  • 与GBN协议相同采用了累计确认,即收到序列号之前的所有字节都已经被正确接收.

TCP可靠数据传输

TCP的实现中,如果发送超时事件,超时时间间隔将重新设置,将超时时间间隔加倍,会导致超时时间很大,重发丢失的分组之前要等待很长时间.

为了解决这一问题,TCP采用了快速重传机制,通过重复的ACK来检测分组丢失,如果发送方收到同一数据的3个ACK,则假定该数据之后的段已经丢失,在超时之前进行重传.

因此TCP在IP层提供的不可靠服务基础上实现了可靠数据传输,采用了流水线机制,累计确认机制等.触发重传的事件不只是超时了,当收到3个重复ACK,TCP就会启动快速重传机制.

TCP流量控制

在TCP中需要进行流量控制,防止发送方传输的数据大于接受方接收的速度,会导致溢出.

接受方需要在数据段的头部字段将可用窗口大小告诉发送方,发送方接收到后需要限制自己已经发送的未收到ACK的数据不超过接受方可用窗口大小.

可用窗口大小可用粗略的计算为接受方窗口大小-[最后接收到的数据-最后读到的数据].

当可用窗口等于0时,说明接受方已经不能接受数据了,所以双方不能再继续进行信息互相发送,

所以在可用窗口等于0时,依然可用给发送方发送很小的数据,以便携带信息.

TCP连接管理

• 三次握手：
  • 1、发送方首先第一次请求，SYN标志位置一，发送初始自己的初始序列号.
  • 2、接收方返回一个SYNACK，返回自己的初始序列号.
  • 3、发送方（客户端）收到SYNACK，同时SYN不再置一，回复一个ACK；表示客户端收到了服务端允许建立连接的信息，可以包含信息.

为什么三次握手?

三次握手的目的是建立可靠的通信通道，说到通信，简单来说就是数据的发生与接收，而三次握手最主要的目的就是双方确认自己与对方的发送与接收是否正常.

第一次握手：Client什么都不能确认，Server确认了对方发送正常，自己接收正常

第二次握手：Client确认了：自己发送、接收正常，对方发送正常、接收正常；Server确认了：对方发送正常，自己接收正常

第三次握手：Client确认了：自己发送、接收正常，对方发送正常接收正常；Server 确认了：对方发送正常，接收正常，自己发送正常，接收正常。

下面解释明明两次就可以建立连接的为什么还要加第三次的确认。

如果发送两次就可以建立连接话，那么只要客户端发送一个连接请求，服务端接收到并发送了确认，就会建立一个连接。

可能出现的问题：如果一个连接请求在网络中跑的慢，超时了，这时客户端会从发请求，但是这个跑的慢的请求最后还是跑到了，然后服务端就接收了两个连接请求，然后全部回应就会创建两个连接，浪费资源！

如果加了第三次客户端确认，客户端在接受到一个服务端连接确认请求后，后面再接收到的连接确认请求就可以抛弃不管了

TCP拥塞控制

当在一个计算机网络中,有太多的主机发送了太多的数据导致网络瘫痪.当数据被丢失后,发送方会重新发送数据,导致不断有新增的数据以及新增的重传数据.在一个有多个路由器转发的计算机网络中,一个分组被丢弃,那么上游的路由资源都会被浪费.

为了解决这一问题,我们采用了两种拥塞控制机制:端对端的拥塞控制和网络辅助的拥塞控制.

网络辅助的拥塞控制

• 信息经过的一路的路由转发，期间的路由器都可以改变状态，接收方就可以通过这个信息知道拥塞情况.
• 这个拥塞控制由接收方返回给发送方的.
• 还有一种是中间网络设备直接向发送方发送控制信息分组的.当前讨论是ATM ABR

这里我们只描述一下ATM ABR拥塞控制:

在交换机中设置RM cell位(网络辅助),分别为NI 不允许增长,CI拥塞指示.在数据传输中随机插入几个网络辅助位,如果发生了拥塞,将cell中的EFCI位置1,前面的EFCI位被置1,那么在发送方返回的RM cell中置CI位.

端对端的拥塞控制

在端对端的拥塞控制中,如果发生了超时事件或者接收到三个重复的ACK,就可以感知到网络拥塞,发生丢失事件后,发送方应该降低速率.常见的有以下几种中调整速率的算法.

加性增-乘性减AIMD

• 线性加（一个一个的加），乘性减（直接减半，快速减）

• 逐渐增加发送速率,只到发送丢包,当发送loss后将发送窗口大小减半,即乘性减,快速的减少发送量

慢启动SS

• 在连接建立时,将窗口大小设置为1

• 每收到一个RTT就将窗口大小翻倍,初始速率很慢,但是会指数级增长

Threshold变量

线性增长与指数型增长的各有自己的优点，何时使用切换规避掉相应的弊端？

• 设Threshold变量为界限,前期采用慢启动SS算法.
• 当发送丢包后,Threshold更新为前窗口大小的1/2.
• 以Threshold为界限，指数增长到Threshold后开始线性增长.

为什么拥塞控制在传输层?

因为数据会在传输层进行汇总,其他的应用程序无法知道网络是否阻塞,不能去调整自己的流量.