记录了计算机网络相关基础知识，参考书是谢希仁教授的《计算机网络》（第八版）以及美国Jim Kurose和Keith Ross所著的《计算机网络：自顶向下方法》（陈铭 译），前者是国内大学常用的计算机网络教材，注重历史发展、基础理论、常用的协议细节等描述，后者是网络应用领域的权威教材，横向技术内容比较全面，在国内也很受欢迎，贴两个大佬整理好的读书笔记：

计算机网络-自顶向下方法

GuoYi:《计算机网络-自顶向下方法》笔记

无论是哪本教材，经典的网络协议和理论是绕不开的，因为初次接触计算机网络是自底向上的逻辑，这个影响了笔者的一些逻辑接受方式。本文旨在从网络底层开始记录这些重要的理论，计算机网络发展的近半个世纪，各层的协议已经比较垄断，了解太多古老且边缘协议帮助不大，本文对于计网的入门应该是比较完整的体系。

计算机网络概述

互联网两个基本特点：连接性与共享

发展三个阶段

  1. ARPANET向互连网发展；单个分组交换到互连网络；1983年TCP/IP成为阿帕网标准协议，不同系统可以在该协议上进行通信，形成互联网。

  2. 形成三级结构互联网；主干网、地区网、企业网（校园网）；

  3. 形成全球多层次的ISP结构的互联网；服务提供商分为主干ISP（服务面积最大、自有高速主干网）、地区ISP（通过一个或者多个主干ISP连接）、本地ISP（直接面向用户服务，连接到地区/主干ISP）。

计算机网络构成

  1. 网络核心：分组交换机(packet switch)；包括路由器（router）、链路层交换机（link-layer switch）。

  2. 接入网：通信链路（communication link）；包括同轴电缆、光纤、无线电频谱等物理媒介；

  • 数字用户线（Digital subscriber line,DSL）：电话线路（铜线）接入，独占的频分多路复用，因下行数据远大于上行数据，故采用ADSL非对称链路；信号衰减，传输率低；

  • 电缆（cable Internet access）：有线电视网接入，社区粗同轴电缆接入、家庭使用细同轴电缆接入社区，共享的频分多路复用；带宽大，但共享带宽，会出现拥堵；

  • 混合光纤同轴电缆（HFC）：长途传输使用光纤，家庭传输使用电缆，带宽速率进一步增加，但仍存在共享带宽问题；

  • 以太网/WIFI/4G/5G/卫星接入：以太网交换机、局域网LAN、蜂窝网络等技术接入；

  1. 网络边缘：主机（host）或称端系统（end system）；包括一般客户端/服务器端、联网app等；

  2. 协议：发送/接受信息协议，每个层次都有不同的协议。

  3. 网络标准；

网络核心——分组交换

三种交换方式

电路交换：必须通过建立连接——通话——释放连接三个过程，通话过程双方持续占用资源，效率低但保证端到端带宽。

报文交换：存储——转发机制，通信双方通过各种节点传递信息，节点接收到完整报文才会进行路径规划，并且进行发送；灵活性增加，无需持续建立连接，但延迟大、存储需求大，效率低；

分组交换：同样基于存储——转发机制，但分组交换将一个报文分组再进行发送，每个报文加入首部控制信息用于识别报文顺序、目标等；动态分配带宽，高效，各个报文自动规划路径，灵活，无需建立连接，迅速，有上层协议确保报文的无误性，可靠。但首部控制信息带来额外开销、存储转发存在排队时延，无事先建立连接带宽无法保证。

性能指标

  • 速率：数据率、比特率（bps）

  • 带宽：最高的数据率（bps）

  • 吞吐量：单位时间通过的数据量（bps）

  • 往返时间RTT：数据发送、接受确认信息的时间；

  • 时延：数据从一端到另一端的时间；包括发送、传播、处理、排队时延：

      发送时延=数据帧长度（bit）/发送速率（bps）；

  传播时延= 信道长度（m）/电磁波在信道的传播速率（m/s）

  处理时延：主机、路由器处理（提取信息、差错检验、查找表转发）等时延；

  排队时延：在路由器等排队等待转发的时延。

  • 时延带宽积：时延是时间，带宽是最高速率，时延带宽积是链路上理论的最大数据量（bit），也是最大未经确认的数据量；

  • 利用率：分为网络利用率和信道利用率，网络利用率=吞吐量/带宽，实际传输数据量和理论最大数据量的比值；信道利用率=信道有效时间/总时间；

列一些公式： 数据发送时间: 发送时间数据长度发送速率

其中有效的数据率： 有效数据率数据长度发送时间

与此同时，有效数据率实际上是实际传输速率，它可以认为是带宽在有效时间的数据量，因此： 有效数据率带宽有效时间总时间 因此，信道利用率近似也可以是 信道利用率有效数据率带宽

网络利用率和时延有着密切的关系，如果一个网络利用率超过50%，排队时延会大大增加，表现在丢包率急剧恶化，满足： 时延空闲时延网络利用率 时延与利用率关系 （曲线应该向上平移一点，利用率为0时时延不应为0）

网络协议

网络协议根据网络层次分类，后面再讨论具体层次协议，这里主要是区分几个层次划分，分别是OSI七层协议、Internet五层协议、还有后面TCP用到的TCP四层协议； 协议层次关系

  • 物理层：关注的是传输媒体以及相关物理特性，包括机械特性（接口形状、引脚排列等）、电气特性（线电压范围）、功能特性（电平意义）、过程特性（不同功能的事件顺序）等；

  • 数据链路层：关注点对点的数据帧传输问题，引入简单的差错检验机制纠正物理层的传输错误。

  • 网络层：为地理位置不同的主机提供连接，例如路由转发、路径选择等；

  • 传输层：关注端到端通信的实现，实现数据的分割、传输、重组。

  • 会话层/表示层/应用层：OSI是1984年提出的一种互联网理论模型，会话层负责处理系统的会话请求，维持和恢复系统的会话；表示层用于实现通信的数据格式转换，对通信数据进行加密、解密、解析等；应用层直接面向用户提供互联网服务，例如访问网站的http、邮件通信的smtp，文件传输ftp等；

随着互联网发展，OSI七层模型划分过于严苛，尤其是应用层、表示层、会话层的协议几乎没有严格的界限，许多应用层协议已经集成了会话层、表示层的功能，因此现代多数协议和操作实际都是面向Internet五层协议。

数据链路层

三个基本问题

数据链路层需要处理三个基本问题，它们是：

  • 封装成帧：文本/ASCII码数据如何被封装成数据帧？

  • 透明传输：无论是什么数据，都能够正确无误地传输；

  • 差错检测：链路层有哪些错误检测机制？

封装成帧

基于帧定界符的方法： 帧定界符

帧的数据部分是来自上层（网络层）的封装数据，各种数据链路层协议定义了数据的最大传输单元（Maximum Transmission Unit，MTU），在数据的前面插入帧首部，定义数据帧的开始，为控制ASCII码SOH（Start of Header，二进制编码01），数据的末尾插入帧尾部，定义数据帧的结束，为控制ASCII码EOT（End of Transmission，二进制编码04）；

接收端只有同时接收到SOH和EOT，才会认为该数据帧有效，任何不完整数据帧都会被丢弃；

透明传输

这是一个专业名词，所谓“透明”，实际上是一种“不透明的黑盒”：意思是数据链路层不会关心数据具体内容是什么，这些数据对链路层本身是不可见的，可称为数据对链路层是“透明的”。但是链路层总需要保证都能将它们无误地传输出去。

例如，假设数据内容含有二进制04，对应一个EOT，说明该位置会被意外地误认成数据帧的结束位置，这就违背了透明传输的意义。这时就需要使用相关决策来保证数据的透明传输，例如最常使用的字节填充（Byte suffing），任何和SOH、EOT等控制字符冲突的字符，前面都应该添加转义字符ESC（十六进制编码1B）；

差错检验

一般方法

实现差错检验的方法有很多，例如一些基本方法：

  1. 冗余位（EDC）检测：在数据的末尾增加1bit，约定该字符为某个特定字符，如果接收到异常数据，说明数据帧错误；
    特点：简单，但是可靠性略低，无法定位出错位置；

  2. 奇偶校验（Parity Checking）：同样采取了一位冗余位，分为奇校验和偶校验；

  • 奇校验：控制冗余位的值，需要保证这n+1位数据（n个数据+冗余位）一共拥有奇数个1；

  • 偶校验：控制冗余位的值，需要保证这n+1位一共拥有偶数个1；
    特点：简单，但是只能检出奇数个bit出错的情况，且无法定位出错位置；

  1. 二维的奇偶差错检验：将数据划分成i行、j列，每一行、每一列都需要计算冗余位，这种情况能够定位某行、某列出错，且能够定位出错的具体位置。

数据链路层一种广泛使用的方法是：循环冗余检验（Cyclic Redundancy Check，CRC）；

循环冗余检验CRC

此时需要的冗余位就不只是一位了，而是多位构成的n位序列，称为帧检验序列（Frame Check Sequence，FCS），它们一样会被附着在数据的末尾一起发送出去，现在描述发送101001数据（k=6位）时，如何得到FCS：

  • 发送和接收双方需要约定FCS的位数n（例如3），并且约定一个n+1位的除数，例如1101，发送方会将数据除以这个除数，得到的余数作为FCS，此时发送的数据就是k+n位，即101001001； 计算FCS

  • 接收方对这个数进行检验，同样使用接收到的数据（101001001）除以这个除数1101，如果数据无误，得到的余数必然为0，正确接收；如果得到非0余数，丢弃这个数据。

另外的细节说明：

  1. 除数的约定在一些协议已经约定好了，通过生成多项式的概念，没什么新奇的，实际上就是第几位为1，则对应多项式项系数为1，否则为0。例如刚刚的除数1101可以表示的生成多项式为

  2. FCS的生成、CRC的检验都是二进制的除法，实际上是一种右移操作，所以很容易通过硬件实现，不会影响传输的效率。

  3. 数学概率证明，CRC检验不能完全保证数据的正确性。但只有很低概率下会出现余数为0，但出错的情况。

这里的出错仅针对是否出现帧比特出错的情况，对于另外一些传输差错，例如帧丢失、帧重复、帧失序，都没有进行讨论；数据链路层过去使用了帧编号、重传等机制来应对这些出错情况，但是如今通信线路状况大大改善，无需这些机制也能很好地提供通信服务，可靠传输将依靠上层的协议（传输层的TCP）实现，这种做法也提高了通信的效率。

总而言之，一般情况下数据链路层没有实现可靠传输，只是针对比特出错情况进行了差错检验，差错检验也不能100%保证数据是完全正确的，但我们以非常接近1的概率认为这些帧在传输过程没有产生差错，表述为"凡是接收端数据链路层接收的帧均无差错"，是OK的。

数据链路层的通信协议

用户通过ISP服务接入互联网，根据接入的类型不同，可以分成两种通信方式：

  • 点对点通信：通过拨号建立通信链路，实现的是点对点的通信，如PPP协议；

  • 广播信道通信：多个节点连接到一个局域网内，实现数据的共享和通信，如以太网协议；

PPP协议

PPP协议（Point-to-Point Protocol）是最广泛使用的点对点链路通信协议，但点对点通信已经很少使用了，一般只用于特殊的场景，例如一些VPN远程访问协议、工业系统等；

用户拨号向ISP发送请求（PPP帧）以建立LCP（链路控制协议，Link Control Protocol）连接，ISP会为用户临时分配一个IP地址用于网络通信，通信结束回收IP，LCP连接断开。

没用过，略掉

以太网协议

局域网是计算机网络重要的一种技术，所谓局域网，是网络为某一个单位拥有，地理位置和站点数目都是局限在某个区域范围。各种主机连接在上面，可以灵活地访问和利用各种硬件和软件资源，这是一种一对多关系。其中以太网在局域网中具有垄断性的地位。

以太网发展

  • 总线结构到星形结构：过去的以太网设备是总线结构，主机连接在总线上，总线末端配备匹配电阻吸收有害的电磁波反射；集线器（hub）+双绞线改变了这个格局，连接到集线器上形成的星形网络，提高了可靠性（无总线干扰），成本低且能够实现高速传输。

  • 传统以太网至高速以太网：从最早的10Mbps演化至成百上千Gbps以太网，10Gbps以下使用双绞线传输，以上需要使用光纤作为媒体。

以太网标准

两个主要标准：

  • 1982年的DIX Ethernet V2，是世界上第一个局域网产品规约；

  • 1983年的IEEE 802.3标准，是IEEE制定的第一个以太网标准。

它们都将速率定义在10Mbps，802.3将以太网划分成逻辑链路控制（Logical Link Control，LLC）和媒体接入控制（Medium Access Control，MAC）两个子层（LLC在上靠近网络层，MAC在下靠近物理层），MAC的选择对LLC是透明的；

随着以太网发展，以太网在局域网领域处于垄断地位（成为同义词），LLC子层也逐渐失去作用，目前提到的以太网多数是DIX Ethernet V2规约的以太网。

网卡/适配器

负责以太网信息传输的是网卡（集成在计算机中），或者额外的网络适配器，这个适配器完全负责以太网信息的接收和发送，当从局域网接收信息，适配器查看自己的ROM（非计算机ROM）中存储的Mac地址和帧头mac信息是否匹配，如果匹配会解析出IP数据报通过中断通知计算机读取，计算机接收再查看IP数据与自己的ROM中的IP地址是否匹配，再进行上一层交付。发送时计算机将IP数据交付给网络适配器，网络适配器封装成帧再发送。

以太网交付有两个特点：

  1. 不可靠的交付：网络适配器只会对帧进行封装和解封装，不会编号也不会要求对方重传，可靠交付由上层决定，上层（TCP）让对方重传以太网本身也不会知道这是重传的数据。

  2. 使用曼彻斯特编码：计算机和网络适配器的数据是一种并行通信，而网络适配器和局域网是一种串行通信，曼彻斯特编码每个码元中间都会出现一个跳变（0发01，1发10），接收端容易得到位同步信号；差分曼彻斯特的0代表电平需要跳变，1代表电平不会跳变，解决了曼彻斯特长0或者长1产生的直流偏移；二者都利于接收端信号解析，但频带占用也需要翻倍（发送码元数量翻倍）。 曼彻斯特编码

CSMA/CD协议

CSMA/CD（Carrier Sence Multiple Access with Collision Detection，载波监听多点接入/碰撞检测）协议是传统总线型以太网的一个重要协议，尽管星形以太网、高速以太网发展，但集线器、半双工通信等内部仍然使用，因此它仍然活跃。

协议主要存在3个要点：

  1. 多点接入：一个总线上连接了多个主机，主机间可能通过总线互相干扰。

  2. 载波监听：防止本主机信号干扰别的主机发送，在两个契机都要监听信道：

  • 发送前监听：有人发就不要发，以免碰撞

  • 发生时监听：检测是否出现碰撞，检测到立刻停止发送。

  1. 碰撞检测：电磁波的传输是有时延的，1km传播时延大概5μs，尽管发送前是空闲的，刚刚发完就产生碰撞了。终止发送还要考虑什么时候重新发送（处理不好就是一撞再撞）。

因为碰撞检测的存在，因此最初的以太网(10Mbps以太网)是一种半双工通信，不能同时发送和接收数据。而后面发展的以太网没有这个问题。

争用期与截断二进制指数退避算法

我们关注总线上两台端到端主机，假设从一个主机到另一个主机的数据时间是，那么我们定义争用期（contention period）为，或称碰撞窗口（collision window），意味着一个主机发送数据，最多经过的时间就能够确定这次发送是否产生碰撞，例如如果发生碰撞： 争用期碰撞 B会在A发送的时间内发送数据，才有可能产生碰撞。

每当遇到碰撞时，双方都会“退避”一段时间后再进行重传，间隔时间会随着重传次数改变，因为重传次数增加（碰撞多次发生），意味着算法仍不能很好规避碰撞，间隔时间应该相应调整，利用争用期的截断二进制指数退避算法如下：

  1. 定义一个常数k，k的取值为：重传次数，

    主机退避时间就被定义为r倍的争用期，其中

    即r是随机从这个集合取出一个数字。

  2. 当重传次数达16次时，说明碰撞是因为数据严重碰撞引起的，再使用算法退避效果也不会太好，因此应该放弃发送和丢弃该帧，并且向高层报告。

512比特/64字节争用期

争用期一般被定义成发送512比特（64字节）所需要的时间，例如最早的10Mbps以太网，发送512bit需要51.2μs；因此r倍的争用期就是r倍的512比特时间。

为什么有这个约定，是因为发送太短的比特数据，碰撞检测是无法检出的。例如A发送了2bit数据，这2bit数据很快就到达总线上，同理B此时也发送足够短的数据，例如还是2bit，那么A、B最后都会因为碰撞收到差错数据而丢弃该数据，也即双方都不能收到正确的帧。另一种说法，实际上就是发送数据远低于时延带宽积，数据停留在总线上，导致碰撞没有被及时发现。

因此以太网定义了最短帧长为512bit，即64字节，短于64字节的帧都被认为是无效帧。

这个最短帧长又是如何确定呢？实际上是考虑了以太网覆盖范围以及强化碰撞干扰信号、时延等因素。从范围上讲，最初的10Mbps传输512字节需要51.2μs时间，也即端到端时延是25.6μs（争用期一半），传输的距离在5km左右，这个范围已经远远超过了局域网覆盖的范围，因此这个定义从实践而言是科学的。

其他细节

  1. 强化碰撞：当检测到碰撞时，除了立刻终止数据发送，还会立刻发送32bit/48bit的人为干扰信号，让所有主机都知道已经发生碰撞。

  2. 帧间最短间隔：96比特时间，让接收方有时间将缓冲区数据读走以及做好下一帧的接收准备。

以太网的MAC硬件地址

LLC子层被淘汰，MAC层负责辨别数据链路层的不同设备。MAC地址我们并不陌生，它是网卡/网络适配器唯一的硬件地址，IEEE 802规定为48bit（6字节）的全球唯一地址，这个地址被固化在计算机网卡的ROM或者网络适配器的ROM中，高三字节由IEEE以及下级组织派发（厂家购买），后三字节由厂家进行不重复指派。

不同设备接收MAC帧，会校对MAC帧目的地址与本地地址是否正确，因此MAC帧也被划分成单播、广播（一对局域网全部主机）、多播（一对局域网部分主机）三种帧，所有适配器都能识别单播和广播帧，多播帧需要额外的编程实现。

MAC帧结构

前面简单介绍数据链路层帧定界符、FCS等，现在具体描述一下以太网使用的数据链路帧结构，称MAC帧： MAC帧结构

MAC帧在IP数据报的基础上，插入了7字节的前同步码+1字节的帧开始定界符+18字节的首尾部控制信息，总长度范围为64字节——1518字节：

  • 7字节前同步码：6字节的10交替码，曼彻斯特斯特编码让对方从中提取位同步时钟，从而实现比特同步。

  • 1字节帧开始定界符：0xAB（注意，不同的协议帧定界符二进制可能不同，以太网是AB），实际上这个AB也有说法，10101011的前6位仍然是一种前同步码，后面11告知帧的正式信息真来了。

  • 18字节控制信息：6字节目的地址+6字节源地址+2字节类型标识+尾部4字节FCS校验码；

      以太网的IP数据报长度在46字节———1500字节之间，其中46字节是为了保证46字节加上18字节的控制信息满足以太网最小帧长要求（见前文）；1500字节是综合网络吞吐量、传输效率考虑约定的

一些细节：

  1. MAC帧没有使用帧结束定界符：因为以太网规定了帧间隔至少是96比特时间，因此一个帧传输完成，必然会有96比特时间的空闲电压。以太网的串行传输使用的是曼彻斯特编码，也即无论发1还是发0一个码元，必然产生电压跳变，当识别没有电压跳变，实际上就知道了帧结束的位置了。

  2. MAC帧没有控制信息来说明帧长度和数据长度：首先上面解释了数据链路层获得首部和尾部的效果，就能获得帧长度，控制信息长度是固定的18字节，因此数据长度也是确定的。

  3. 当IP下发数据报确实不够46字节：这种情况MAC层会进行字节填充，填足46字节，与MAC不同，IP数据报头会有相关信息指示数据长度（后文网络层内容），因此字节填充不会影响原来的数据。

以太网交换设备

现代互联网技术是一种基于局域网发展的技术，不同的局域网需要通过设备连接起来，或者新的网络需要接入某个局域网，称以太网的扩展，随着发展出现不同扩展方式，包括集线器（hub）、网桥（bridge）、以太网交换机（switch）等。

双绞线（光纤）+集线器

以太网最初的细电缆、粗电缆+转发器的总线结构，迅速被成本极低且可靠的双绞线+集线器组合取代，光纤的出现使得以太网的覆盖范围进一步加大。

但集线器本身还是一种端口转发设备，它本身并不存储数据帧，它收到了什么比特就向所有端口立即转发该比特，因此它会导致碰撞域（collision domain）的问题。所谓碰撞域，实际上是基于CSMA/CD协议产生的问题，在总线上一个时刻最多允许一个主机发送数据，因此称这个总线的所有主机都处于同一个碰撞域。而集线器本身也是具有总线结构的局限，同一个时刻集线器只能进行一次端口转发。 碰撞域 如图，假如使用集线器，原来三个碰撞域就成为了一个碰撞域。从数据上而言，如果原来的吞吐量是30Mbps，则连接后就变成了10Mbps。

另一个问题是，由于集线器是一种即时转发设备，不同速率的网络适配器通过集线器相接，网络速率取决于最低速率的网络适配器。

网桥与以太网交换机

更常用的方法是在数据链路层扩展以太网，例如网桥和以太网交换机；网桥也是一种端口转发设备，但它不是向所有端口转发数据，而是内部维护一个地址表，根据该表查找MAC帧的转发地址，其他端口会过滤这个地址。

后来出现的以太网交换机进一步扩展了以太网。以太网交换机本质也是一种多端口的网桥，每个端口连接着主机或者另一台以太网交换机，其主要特点是：

  1. 全双工工作，不使用CSMA/CD协议；端口转发可以实现并行转发，多对主机可以实现同时通信，无碰撞传输数据；

  2. 端口具有存储器，在繁忙时刻能够暂时缓存帧数据，等待空闲时再转发出去。

  3. 多个主机可以独享通信传输媒体，独享带宽。例如网络10个端口链接了10个10Mbps带宽设备，整体吞吐量就是100Mbps，这是以太网交换机的最大优点。

  4. 交换机允许不同速率的设备接入。

  5. 以太网交换机内部同样维护了一个地址表（交换表），以太网是即插即用设备，这个交换表是通过以太网本身的自学习算法建立起来的，无需人为干预，如下；

以太网交换机自学习算法

假设以太网端口1连接主机A，端口2连接主机B，开始时转发表为空；A向B发送数据，以太网交换机交换表会首先记录A，记录项为[A的MAC地址,端口1,TTL]，然后查询B的转发地址，没有找到向所有端口进行转发，其他端口转发出去会因为MAC不符合而过滤该帧数据，只有B会接收到；同理，当B向A或者其他端口发送数据，才会加入到交换表。所谓TTL，是记录项的有效时间，超过该时间（几分钟）以太网交换机会自动删除该项，使用同样的方法重新建立转发项，确保转发是实时可靠的。

所以规则很简单：谁发就是记录谁，无记录先广播。

另一个问题是以太网交换机转发可能形成环路，IEEE具有相关协议（生成树（STP）协议）能够阻塞某些冗余链路（环路变成树结构）来解决这个问题。

以太网的交换机成本也很低，性能却远远高于集线器，市场上进一步取代了集线器成为星形拓扑网络的首选。

虚拟局域网（VLAN）

以太网交换机没有解决以下问题：

  1. 广播风暴：一个以太网内如果存在很多主机，需要耗费大量的广播帧，而且网络一旦出现某些配置错误，可能产生严重环路，瘫痪整个网络；

  2. 单个以太网内并不是所有主机都愿意向该局域网所有主机暴露资源，这样缺乏一定的安全性。

因此常常的做法是将以太网再进行分割，分割成一个一个的小局域网，称为虚拟局域网；1988年IEEE引入了协议支持虚拟局域网，定义了一种支持VLAN的帧结构如下： 支持VLAN以太网帧 在以太网帧的基础上增加了4字节的VLAN标签，重要的是后面12位的VID，标识了每个VLAN的标识符，意味着一个以太网（广播域）能够标识4096个VLAN；

此时要讨论基于VLAN的以太网交换机的工作是如何进行的： 支持VLAN以太网交换机 按照复杂程度，依次分为A向B、A向E、A向C、A向F转发数据帧四种情况，其中注意A、B、C、D等七台主机在同一台交换机下，称为同一个广播域；A、B、E处在同一个局域网下（不同交换机下主机可以划分同一个局域网）；

  1. A向B转发：这是最简单的情况，此时MAC帧仍然沿用传统的MAC帧，无需插入VLAN标签，交换机还是按原来的方式将A数据转发到B；

  2. A向E转发:同一个局域网内但不同广播域下，A发送的MAC帧需要在交换机中插入VLAN标签，然后转发到另一个交换机，这条链路称为干线链路（或称汇聚链路），另一台交换机接收到且发现目的地址在本交换机下，会拿掉VLAN标签，再将帧转发到E；

第三、第四两种情况是跨越VLAN的传输，这种情况已经超出数据链路层范围了，需要通过网关和路由的转发；或者一些特殊支持VLAN转发的交换机，称为第3层交换机（L2/L3交换机）。

  1. A发送MAC帧，其中的目标地址不是任何交换机或者主机的直接的MAC地址，而是网关的MAC地址；帧在交换机1中插入VLAN标签，并且经过路由转发，MAC帧的源地址、目的地址、VLAN标签都会相应改变，最后重新下发到交换机，拿掉VLAN标签并且转发到B。

第四种情况也是和第三种情况大致类似，第三层的技术细节将在网络层的ARP地址解析协议具体描述。

高速以太网

传统10Mbps以太网在出现后就迅速迭代出100Mbps、吉比特以太网等，它们在二十年前就已经发展成熟并且称为一门重要的计算机网络技术，这里仅是特征描述，更专业的应该参考协议和其他著作。

100Mbps以太网：数据率提高了十倍，但争用期、帧最小间隔仍然沿用512bit、96比特，但是时间缩短了十倍，即5.12μs、0.96μs，意味着其使用CSMA/CD协议的半双工工作范围在几百米以内，而且百兆以太网在IEEE 802.3中不再支持同轴电缆，布线需要重新更换成双绞线。但同时，100Mbps以太网支持使用光纤进行传输，网段在2km左右，同时也支持全双工通信。

吉比特以太网：1998年形成了正式的吉比特以太网标准，吉比特以太网也是同时支持半双工和全双工两种工作方式。半双工情况下仍然沿用CSMA/CD协议，但是如果保持512比特（64字节）的争用期，覆盖范围就在几十米以下了，因此吉比特以太网将争用期扩展到512字节(512比特的8倍)，但是如果定义最短帧长为512字节，那么字节填充的开销将会很大，因此吉比特以太网还引入了载波延申（carrier extension）、分组突发（packet bursting）的方法，第一个短帧使用载波延伸，将无用数据填入数据直至512字节，后面的短帧不再使用字节填充，而是保留最小帧间隔，直至多于1500字节时一并发送，减小了半双工工作方式发送短帧数据的开销。

10吉比特/100吉比特以太网：这是近10年的成果（2010、2015），它们放弃了CSMA/CD协议，只工作在全双工工作方式下，结合光纤波分复用技术实现了更高速率，传输范围100m——10km；

目前以太网的最高速率朝着太比特以太网演进，例如2020年的400Gbps以太网、800Gbps以太网等。

网络层

数据链路层表达了如何实现主机端到端连接的基本雏形，向下它需要兼容物理层的各种特性，向上它需要抽象出更灵活的网络服务，这种服务在我的理解是一种虚拟化、逻辑化的抽象，VLAN中同一个交换机网络可以划分成各种不同的局域网，一个设备可以随时接入不同的局域网，而不受Mac地址限制、在上层实现数据分组与重组，这些都要求更加灵活的网络环境，大概就是网络层的意义。

网络层概述

计算机网络设计之初，有一些观点认为应该学习电话网络的经验，建立面向连接的服务，这种逻辑连接（非物理）称虚电路服务，每一个分组的数据报通过一条虚电路路由转发，并且实现按序、无差错的网络服务，从而实现网络层的可靠传输。

但后来互联网的发展思路更倾向于一种无连接、尽最大努力（即不可靠）的数据交付服务，称数据报服务，更加灵活、低成本，可靠通信通过上层实现，且能够适应应用。实践证明，这是一条正确的路线。

网络层的重点集中于路由转发、IP及其配套协议等问题。目前的网络层大致分成控制层和数据层，控制层关注路由转发的路径规划，数据层关注分组转发任务本身，后者分组转发由硬件完成，时延在纳秒级内，但前者的路径规划使用软件完成，时延在秒级左右。

网际协议IP

路由器一个任务是连接各种异构网络（不同寻值方案、不同接入机制、不同分组长度、不同差错恢复等），在路由器上使用IP协议，能够使它们抽象出一种统一的网络，称虚拟互连网络（统一的IP网络），如果在此以上应用TCP协议，就是全球最大互连网——互联网的基本体系。

五类IP地址

由于网络层被抽象出来，而且48位的mac地址冗长复杂，难以记忆，互联网习惯使用IP地址来区别不同的主机或者路由器接口。

IP地址由网络号+主机号组成的32位二进制地址，为了增强可读性，每隔八位二进制数插入一个分隔符点（称点分十进制记法），根据网络号、主机号长度不同，分成A、B、C、D、E五类地址，如下： 五类IP地址 A类地址：网络号占8位，第一位固定为0；这里的网络号是一个有趣的事情，因为它涉及了我们开发常用的两个地址，一个是网络号全0时，即0.x.x.x（可全0），或者网络号后七位为1时，即127.x.x.x（非0），前者在主机中，代表是一种通配符，代表是主机任意的IPv4地址，例如在TCP绑定时使用INADDR_ANY绑定IP，此时通过局域网的ip地址都能够访问主机的服务；而在路由器中，这个IP是默认路由，如果数据报没有指定IP，数据报会被发送到默认路由；而127.x.x.x更加常见，也就是我们平时使用的localhost服务，它允许主机通过这个IP访问主机本地的服务，一般用于本地的环回测试，内部就像有一条主机自己和自己连接的网线一样（而实际上根本不依赖网卡工作）；主机号占24位，全0代表网络地址，全1代表所有主机，全0和全1一般不指派；

B类地址：网络号为16位，高两位固定为10（128.x.x.x——191.x.x.x），主机号占16位；

C类地址：网络号占24位，高三位固定110（192.x.x.x——223.x.x.x）,主机号占8位；这也是用户局域网最常用的IP地址；

D/E类地址：见图；

一些特殊的IP指派规则： 特殊的IP指派规则

然而，五类分类地址方法带来了很多不方便，首先就是面临枯竭的IP地址耗尽问题；作为欧美这些早期接入互联网国家，A类地址有(约1677万个)主机，而一些后来居上的发展中国家，个人、企业的C类地址，只能接入（254个）主机，无论哪一种都不能满足现在互联网的发展需求。

于是IP分类指派成为了历史，无分类编址，以及后来的IPv6应运而生。

无分类编址CIDR

32位的IP地址不再使用固定位数的网络号，而是换成了任意位数的网络前缀，剩余部分仍称主机号；它们中间使用斜线分割；

例如一个普通的IP地址可以记为128.34.32.7/24，代表IP地址前3字节（24位）是网络地址，剩下为主机地址；如果不是24，是20，则应展开成二进制再计算网络地址，因此一些容易混淆的记法应该区分：

  • 128.34.32.7：是一个IP地址，但不知道网络地址，能访问网络资源，但是你不知道如何获得与它同一个网络的其他IP资源；

  • 128.34.32.7/24：是一个IP地址，能访问网络资源，且能获得其网络地址；**

  • 128.34.32.0/24：主机号为0，通常描述一个ip集群（称CIDR地址块）；

子网掩码（地址掩码）

从IP地址获得网络前缀（网络地址）有时候是重要的，我们知道斜线后的数据就代表前缀的长度，这种说法表现在计算机计算中就是一种AND计算，才有了子网掩码这种定义；斜线数字是多少，那么就是32位二进制前面占几个1，这就是子网掩码，例如128.34.32.7/24，其子网掩码就是24个1，即255.255.255.0/24，对子网掩码而言，省略斜线写成255.255.255.0也可；IP和子网掩码进行AND计算，就是网络地址。

CIDR特殊地址块

  • 网络前缀占32位（x.x.x.x/32）：无主机号，主机路由，这是优先级最高的路由转发，如果数据报的目的路由就是该主机路由，会按照其端口直接转发；

  • 网络前缀占31位（x.x.x.x/31）：点对点链路，仅一对主机

  • 无网络前缀、IP全0（0.0.0.0/0）：默认路由，最长前缀匹配失败才会执行默认转发操作；

路由聚合

路由聚合 路由聚合指的是将某个长度的前缀分发给一个大的组织，例如20，再由大组织下的小组织继续划分，例如一个大学有接近1000台计算机，那么需要至少分配22个前缀，主机数约为(不详细讨论特殊地址)，然后可以按院系继续划分，例如某学院需要200台，就在某个段继续划分出24前缀，体现了CIDR编制的灵活性，减缓了固定编址对IP地址的浪费；

另一方面，路由聚合在路由转发表中使用，需要使用最长前缀匹配的方法，例如发送至某个学院的数据报一定也是匹配学校本身的前缀，但是一定需要转发到最匹配的一个对象，算法上实现并不难，按块寻值也提高了转发速率。侧面上强调了路由的作用，连接前缀不同的异构网络（这是物理层转发器、链路层集线器、网桥或交换机都无法做到的），并且做好路径规划。

IP数据报结构

IP数据报结构 IP数据报划分成首部控制信息和数据部分，首部长度为20——60字节，其中20字节是固定内容，另外40字节是来自额外字段、数据填充；数据部分取决于总长度字段限制，最大是65535字节（字节）-首部长度；

  1. 版本：4位，ipv4或ipv6

  2. 首部长度：4位，0101（5）——1111（15），量化的单位是32字长（4字节），因为首部长度的范围是20字节——60字节；

  3. 区分服务：8位，少用；

  4. 总长度：16位，IP数据报总长度，包括首部长度+数据长度，最大表示65535字节**，但数据链路层以太网帧约定MTU小于1500字节，大于1500需要进行分片传输；

  5. 标识（identification）：16位，IP数据报发送时内部维护一个计数器，并且发送一个数据报更新计数值到标识区中，分片发送、接收后根据计数值重新组装成完整数据报；

  6. 标志（flag）：3位，仅使用了两位，最低位为MF（More Fragment），为1表示后面还有分片，为0表示已是最后分片；中间位为DF（Don't Fragment），为0代表允许分片，为1代表不能分片；

  7. 片偏移：13位，代表分片的IP数据报在原来数据报的相对偏移量，单位是8字节（64位），除最后一个分片，其他分片的偏移量是8字节的整数倍；

  8. 生存时间：8位，初始时为TTL，后面成为跳数限制，经过一个路由转发，跳数-1，为0该数据报会被路由/主机丢弃。

  9. 协议：8位，一些IP相关协议，ICMP/IGMP/TCP/UDP/ESP/IPV6/OSPF等；

  10. 首部检验和：16位，数据首部（不含数据）的差错检验；方法如下：

  • 首部检验和使用简单的校验方法提高效率：数据首部的检验和开始设置成全0，数据首部按字划分（这里一个字=16位=2字节，注意字不是一个固定单位，它的大小取决于计算机字长定义），划分完成进行反码算术运算（1+0=0；0+0=0；1+1=0但向前进位，最高位进位最低位+1），得到的结果再取反码作为检验和发送；接收方按照同样的方法划分，计算反码算术运算再取反，如果首部没有差错结果必然全0；否则认为首部出错；

  1. 源地址：32位，源地址IP

  2. 目的地址：32位，目的地址IP

  3. 可变/数据填充：最大40字节，用于排错/测量，填充需要确保该字段为4字节整数倍；

路由转发

按CIDR编址的路由转发表都是网络地址结构，例如一个转发表：

前缀匹配 下一跳
128.1.24.133/32 接口A
128.1.24.0/24 接口B
128.1.24.0/22 接口C
0.0.0.0/0 接口D

路由的第一件事就是提取路由表项的网络前缀长度（即子网掩码），然后和数据报的目的地址相AND，然后与路由表项的网络前缀匹配，如果匹配从相应的接口发出；

最前面的是主机路由，其次是前缀长度较长的IP（代表更具体、主机数更少的网络），最后是默认路由，这种策略提高了数据层的工作效率；

地址解析协议ARP

有三个协议和IP协议配合使用，它们是ARP、ICMP、IGMP；

地址解析协议（Address Resolution Protocol,ARP）的核心问题是：如何通过IP地址，得到主机的MAC地址；另一方面，这也补充了链路层没有完成跨局域网传输的问题；

首先，得到MAC地址也是一种泛洪广播的过程，例如：

  • A、B同处于一个局域网：A需要获知B的mac地址，会发送ARP请求分组，表明我的IP地址是XXX，MAC地址是XXX，需要获知IP地址为XXX的MAC地址，这个数据报会再链路层封装并且广播发送（因为不知道B的MAC地址），至于插不插入VLAN标签就取决于它们是否工作于同一台以太网交换机；B收到会回应自己的MAC地址（单播到A），其他因为目的IP地址不同，会丢弃这个IP数据报；

  • A、B处于不同的局域网：这时候就要经过路由器了，A发送同样的信息在局域网内广播，局域网内的一个路由器进行IP的前缀匹配，要么下跳到下一个路由器，要么直接是B的局域网，B再进行相同的回应；

最后使用ARP协议进行过通信回应的IP——MAC地址映射关系都会被存储至主机的ARP高速缓存中，生存时间大概是几分钟——几十分钟，过期经过同样的方法更新缓存；

网际控制报文协议ICMP

不算重点协议，仅为了提高IP数据报成功交付机会，允许主机、路由报告差错或者相关异常情况，IP报文数据会被装入IP数据报中一并封装发送。

ICMP报文分为ICMP差错报文（终点不可达、时间超过、参数问题、改变路由等）、ICMP询问报文（回送请求、回送回答、时间戳请求、时间戳回答）。

ICMP不应该再发送报文的几种情况：

  • 对ICMP报文不应该再发送ICMP报文；

  • 对第一个分片的数据报片后的所有数据报片不应该再发送ICMP报文；

  • 数据报地址是多播的，不应该发送ICMP报文；

  • 特殊数据报地址（0.0.0.0、127.0.0.0）,不应该发送ICMP报文；

ping

在测试网络联通中，经常使用的命令是ping，ping不是应用层的联通测试，它直接使用了网络的ICMP报文，它向目标主机发送ICMP报文，并且计算时间戳，计算TTL往返时间，如果接收到主机的ICMP回送报文，说明网络是联通的。（网络层和应用层是不同协议的流量，这也说明了为什么应用层http能访问google，而ping不通的原因）

互联网组管理协议IGMP

IGMP（Internet Group Management Protocol）更是很少介绍，它是一个应用于多播的协议，用于主机向路由等报告其多播组成员身份的一个协议，帮助路由更好地管理多播流量。

路由选择算法

路由的网络实际上是一种图论问题，也即带权的有向图，权值记为cost，表明延时、拥塞等带来的链路代价，路由选择算法就是为了找到一条cost最小的路径。

算法分类：

全局/分散信息：知道全局路由信息/只知道邻居路由信息；

静态/动态：手动配置路由信息，路由更新慢（泛洪、随机、最短路径等）/周期更新路由信息，路由变化快。

LS算法：泛洪算法+Dijkstra算法

LS（Link State，链路状态）算法综合了两方面的内容：

泛洪算法：从源路由向所有路由按最短路径发送信息，是为了建立一个全局路由网络，因为Dijkstra需要根据全局图来规划路径，泛洪的一个问题是需要防止广播风暴造成大量的流量浪费，主要措施有：

  • 序号控制泛洪（Sequence-number-controlled flooding）：节点会在内部维护一个广播序号表，只有广播分组存在于这些表中，路由才会进行转发，否则会丢弃该分组。

  • 反向路径广播（Reverse Path Broadcasting，RPB）：只接收来自源节点最短单播路径的分组，从其他节点绕路过来的分组都会被丢弃。

  • 生成树广播（Spanning-tree broadcast）：生成树广播会周期性发送数据更新网络的拓扑信息，并且切断冗余路径，在广播时就不会产生冗余环路了。

Dijkstra算法：Dijkstra在数据结构例题中有过介绍，它能够计算带非负权的有向图的两点最短路径，前提是它能知道全局的路由路径信息（对整个路由网络而言），因此路由接到分组，能够进行从本路由到目的路由路径的规划，算法的时间复杂度是，经过小顶堆算法优化可以达到O(nlogn)的时间复杂度。

DV算法：分散信息+Bellman-ford算法

距离向量算法（Distance vector algorithm，DV）是基于分散信息的一种算法，所谓分散信息，是源路由不会向所有路由泛洪信息，而是仅向相邻节点通告信息：我的相邻节点是xx，通过我向xxx节点发送信息的最短路径是xx。当相邻节点的信息变化时，会迭代更新并且向邻居发送DV estimate信息进行通知。

Bellman-ford算法在数据结构与算法二也介绍过，它与Dijstra算法的差别在两个地方，其一，它可以应用于计算带负权最短路径（和路由应用没什么关系）；其二它可以基于局部信息工作，或者说根据跳数工作；对贝尔曼-福特算法，因为给定跳数ttl，到某个点的最短路径是确定的，因此这个可以帮助路由建立局部信息，再去与邻居交流。

DV算法的特点是：“好事传得快、坏事传得慢”，意思是当某条路径cost变小，这个信息会迅速普及到整个网络，而某条路径cost变得很大，需要花比较长的时间去让邻近路由知道；例如A——B——C路径中，假设cost分别为2和1（A的信息是A——B=2，A——C=3），现在B——C路径失效，B要经过跳数限制的信息，才能更新B——C路径失效，而A仍然认为B——C是有效的（B接收了这个错误信息），B会更新B——C路径cost为A——C的cost加上A——B的cost=3+1=4，然后又将这个错误信息传给A，每次传递都导致A——C、B——C的cost增长，这就是“计算到无穷”问题；

也有方法缓解这种现象，也即不要通过同一个接口向邻居学习和通告信息，避免错误信息无限循环，称水平分割（Split Horizon）；或者B——C失效时，B应该及时告知A，称毒性逆转（Poison Reverse）。

由于DV算法的这些特性，DV算法的收敛速度较慢，时间复杂度不确定。

分层次的路由选择协议

庞大的互联网不可能只有一个路由网络，因为更新时间、转发表的存储开销都太大，而且不是所有机构都希望将自己的网络布局暴露在互联网上，因此实际使用的路由网络是一个层次化的网络，整个互联网被划分成许多很小的系统，称自治系统（autonomous system，AS）。

AS内部使用的路由选择协议为内部网关协议（Interiro Gateway Protocol，IGP），其中最常用的是RIP和OSPF协议；AS之间使用的是外部网关协议（External Gateway Protocol，EGP），最常用的是BGP协议。

内部网关RIP协议

RIP(Routing Information Protocol)是基于距离向量算法（DV算法）的路由选择协议：

  • 路由器到直连路由的距离定义为1，到非直连网络的距离就是经过的路由器数量+1；规定最大只能经过15跳，16及以上不可达，只适用于小型互联网；

  • cost只和路由器数目有关，和链路时延、拥塞程度无关，即最短路径是经过路由数最少的路径，而不是时延最低的路径；

  • RIP分组封装在UDP数据报中，再封装成IP数据报进行发送。

  • 周期性（如30s）和相邻路由交换信息，交换的信息是自己的路由表，如下：

目的网络 距离 下一跳路由器
Net1 3 R1
Net2 4 R2
Net3 1 直接交付

每次接收到来自相邻节点的路由表，就将其距离+1，再与自己的路由表比较，如果距离小于就替换下一条路由器为相邻路由器，代表经过相邻路由器的cost更小。

特点：

优点：实现简单、开销较小、好消息传得快

缺点：坏消息传得慢、最大跳数限定在15网络规模有限、网络收敛时间长。

内部网关OSPF协议

OSPF(Open Short Path First,开放最短路径优先)是基于链路状态（LS）算法的协议，为了解决RIP缺点提出，比RIP协议更加复杂：

  • 泛洪（flooding）法，向本AS的所有路由器发送消息，但是不会向刚刚发来信息的路由器发送信息，相邻的路由器接收会继续向其所有相邻路由器发送信息；

  • OSPF分组直接使用IP数据报进行发送；

  • 代价信息可以是时延、带宽、费用等，可自定义；

  • OSPF交换的信息是路由器的所有相邻的路由和代价信息，路由器不会广播自己本地的路由器分组信息，这样开销太大，而是会通过数据库摘要表明哪些信息已写入本地数据库，然后发送请求分组来获得缺失的链路状态信息，最后交换收敛后，所有路由器都知道整个网络的拓扑结构；

  • 周期性（30min）/链路变化时，才会发生信息交换；

可见OSPF是基于全局的拓扑信息的，为了进一步降低开销，OSPF还会将AS划分成若干个区域Area，每个区域内的拓扑结构对区域内路由是透明的，而对其他区域路由器是不透明的。

特点：解决了坏消息传得慢问题，网络变化响应速度很快（100ms），收敛速度较高；

阉割内容

本层暂时没用上的：Ipv6、外部网关协议BGP、IP多播、VPN、NAT网络地址转换、SDN......

传输层

网络层完成了主机的通信，传输层将实现应用进程间的端到端通信。在传输层中，区分不同应用进程的接口是协议端口（protocol port），也即一般简称的端口（port），一些熟知的应用层服务和端口绑定关系如下：

应用程序 端口号
FTP 21
Telnet 23
SMTP 25
DNS 53
HTTP 80
HTTPS 443

还有其他分布在0——1023端口的，一起被称为熟知端口号（well-known port number），很少在用户程序占用这些端口号。

另外两种分类是：

  • 登记端口号（1024——49151）：除了熟知端口号以外的程序使用，使用要在IANA登记，防止重复。（这一段实际上比较常用）

  • 短暂端口号（49152——65535）：客户进程使用的。

复用和分用

指的是传输层的两个重要功能：

  • 复用（multiplexing）：这是发送方的术语，指的是不同应用进程都可以通过同一个运输层发送信息，方法是在不同应用进程的套接字（socket）上加上传输层头部信息。

  • 分用（demultiplexing）：这是接收方的术语，指的是接收方可以将收到的报文首部剥除并且将数据正确交付到目的应用进程。

传输层UDP和TCP协议

传输层基本被这两个协议垄断了，它们是：

  • 用户数据报协议（User Datagram Protocol，UDP）

  • 传输层控制协议（Transmission Control Protocol，TCP）

UDP协议

设计原则是足够简洁，只在IP协议的基础上增加了传输层的基本功能，包括复用、分用、差错检测。

UDP特点

    1. 无连接的。发送和接受数据无需建立逻辑连接。
    1. 尽最大努力交付（不可靠交付）：
    1. 面向报文的：UDP不会拆分、合并应用层的报文，长度过高分片由IP层完成。交付时也是交付完整的报文。
    1. 没有拥塞控制：发送拥塞时UDP发送速率也不会降低，宁愿丢失数据也不肯接受太大的时延要求。（对实时应用如视频会议、IP电话重要）
    1. 支持一对一、一对多、多对一、多对多交互。
    1. 全双工通信。既作为发送方，也可作为接收方。
    1. 首部开销小，仅8个字节。

UDP首部

UDP会为应用层报文加上UDP首部，格式如下：

分为4个字段，每个字段均占2字节：

  • 源端口：方便对方回信，不需要回信填0；

  • 目的端口：终点交付。

  • 长度：UDP首部+应用报文长度；（最小为首部长度8）

  • 检验和：差错检验。

UDP的检验和计算（差错检验）方法： UDP的检验和计算 UDP的差错检验和IP数据报的差错检验一样，采取反码计算的方式（1+0=0；0+0=0；1+1=0但向前进位，最高位进位最低位+1），不同在于三点：

  • IP仅检验IP首部，UDP检验UDP首部+应用报文数据。

  • UDP会使用12字节伪首部，具体构成是4字节的源IP地址+4字节的目的IP地址+1字节全零字段+1字节协议字段（UDP而言是17）+2字节UDP长度（最小8）。伪首部唯一作用是产生检验和和计算检验和，不会封装发送，也不会向上层交付。

  • 当数据部分字节数是奇数时，需要补充1字节全零字段计算。因为UDP要检验数据部分，而IP检验和不用，所有UDP要有填充机制保证16位数据。

UDP检验和具体产生方法：初始时2字节检验和为零，按照数据部分字节奇偶性填充数据，按字（16位）划分首部和数据，进行反码计算和，得出来结果取反码就是检验和。接收方接收正确的情况下，同样的方法计算和，得出来的结果全1（或取反码后全0），则检验成功。

TCP协议

TCP特点

    1. 面向连接的。数据传输需要先建立逻辑连接，数据传输完毕也要释放连接。
    1. 提高可靠交付服务。TCP传输的数据，能做到无差错、不丢失、不重复、按序到达。
    1. 点对点。每一条TCP连接只有两个端点（endpoint）。
    1. 面向字节流的。UDP清楚知道一个报文的边界，但是TCP不清楚报文是什么样子的，发送方TCP可能发出10个数据块，但是接收方TCP可能接收4个数据块就完成交付，交付的服务如图无结构的字节流。
    1. 全双工通信：发送、接收方都使用缓存临时存放数据。

停止等待协议、自动重传请求ARQ协议

在不完全可靠的信道（传输本身可能受干扰、发送速率过快数据被覆盖）实现可靠的传输，停止等待协议是一种基石。

停止等待协议：本质上就是要求，A发送一组报文，B接收后必须发送确认报文，A接收到确认再继续发送。

因此产生第一个要求是：数据必须具有分组编号，才能对某组数据产生确认。

自动重传请求：

出现差错：但A发送的数据有可能丢失，因此产生第二个要求：超时重传机制。A发出数据时，会有一份数据的副本，并且维护一个计数器，计数器超出超时重传时间还没接收确认，A会重新将副本发出。

确认丢失：B的确认同样会出现丢失，导致A重传，发送同一个数据，B此时会丢弃这份数据，但仍然出现发送确认。

确认迟到：B的第一个确认迟到了，A重传，B的新确认来到，A继续发送剩下数据，一段时间后A收到迟到的第一个确认，会直接丢弃。

这是简化版本的停止等待协议，因为每个分组都停下来等待确认，信道利用率极低，为 其中是A向信道发生数据的时间，是数据在信道往返的数据，是B向信道发送确认的时间。

因此TCP通常使用流水线的发送方法，即滑动窗口式的发送，允许一次性发送多个分组，大大提高了信道利用率，这就是连续ARQ协议。

可靠传输实现细节

连续ARQ协议

连续ARQ协议 - 每按序接收到一个确认，发送窗口会前移；

  • 接收方采取累计确认的机制，即同时按序接收多个分组时，只发送对最后一个分组（编号最大）的分组进行确认（接收方应该在最大确认推迟时间（0.5s）内发送一个确认，否则会引起重传），发送方收到这个确认，会前移若干格。发送的确认信息，是期望下一个收到的数据编号，例如发送31，说明开始的0——30都已经被收到。

发送窗口数据被划分称两部分数据：发送窗口内的都是允许发送的，一部分发送了但是没收到确认，另一部分是未发送的（称“可用窗口、有效窗口”）。

发送窗口+窗口外剩下数据 = 发送缓存数据。

接收窗口的数据都是未按序到达的数据（数据编号前存在未到达的编号）。

从接收缓存来看，接收缓存应该分为两部分：分别是按序到达（已发送确认、未被读走）+接收窗口数据。

连续ARQ+累计确认的方式存在一种问题，即GBN（Go-Back N）问题，如果累计确认在最晚时间没有发出或者丢失，那么连续ARQ需要重传N个数据报，因此在通信链路不佳时，连续ARQ会有负面影响。

超时重传时间选择

基于Karn算法的加权RTT算法：需要计算平滑RTT和偏差RTT。

平滑RTT：首先记录一个报文发送+确认返回的时间，这个值也是作为第一次平滑往返时间，然后下次接收到新的RTT，那么第二次的计算为第一次（初始化）

旧的第二次（递推） 其中α = 0.125，这个权值表示新的平滑RTT仍然接近原来的平滑RTT。

偏差RTT： 第一次（初始化）

旧的第二次（递推） 其中β = 0.25。

最后超时重传时间RTO（Retransmission Time-Out）定义为：

如果发生超时重传，RTT起点如何确定呢？如果认为是第一次的RTT，那么新的RTO就会偏大且多次重传越来越大，如果认为是重传的RTT，新的RTO会偏小且多次重传越来越小（毕竟忽略了第一次重传时间），因此最后融合Karn提出和实践效果较好的方法：当发生超时重传时，递推不再使用第二次的RTT，而是将新的重传时间设置为旧重传时间的2倍。

TCP首部结构

TCP首部占据20——60字节（40字节来自可变的选项长度）: TCP首部结构

  • 源端口/目的端口：各占2字节（16位端口号）；

  • 序号：4字节，32位序号（0——），注意：TCP是面向字节流的而不是面向报文，因此TCP会不断从0——分配序号，直到溢出会重新从0开始（模运算）。

  • 确认号：4字节，也即期望下一个数据字节的序号。

  • 数据偏移：4位（半字节），衡量单位是“4字节”，即最大能表示60字节的偏移，偏移指的是TCP数据部分起始离TCP首部起始的距离，因为首部最大为60字节。

  • 保留：6位，保留使用。

  • 6个已定义的标志位（6位）：URG（紧急数据，优先发送）、ACK（标识上述确认号是否有效，TCP连接后应为1）、PUSH（立即交付，不再等待缓存满）、RST（复位，TCP严重差错，需要释放、重新连接）、SYN（同步，建立连接有用，后文）、FIN（终止，释放TCP连接）

  • 窗口值：2字节，声明自己的接收缓存大小，例如字段十进制为1000，代表可再接收1000字节数据。

  • 检验和：2字节，产生方法同UDP，但12字节伪首部的协议字段应从17改为6，UDP首部长度更改为TCP首部长度。

  • 紧急指针：2字节，仅URG=1有效，表明数据起始——紧急数据末尾的大小，紧急数据后才是普通数据。

  • 选项：0——40字节，选项标签，使用了该字段必须填充保证首部长度仍为4字节的整数倍。一些可选标签包括：

    • MSS（Maximum Segment Size，最大报文段长度）：定义了TCP数据部分的最大大小。TCP报文数据过小，至少加上20TCP首部+20IP首部，网络利用率不会高于1/41，TCP报文过大则会在网络层分片，因此MSS应该做到既不过小，也不需要分片，过去为576字节-20IP首部-20TCP首部=536字节，因此TCP整个报文长度应该不高于556字节，也是所有互联网主机应该能接收的，但由于分片策略也受路径影响，已经不太强调MSS了。（注意：为什么是576字节而不是以太网的1500字节，是因为历史上链路层一部分是基于电话网搭建的X.25网络而非以太网，定义的最大MTU为576字节）
    • 时间戳：一种功能是计算RTT；另一种功能是处理报文序号超过32位导致反复绕回的情况，时间戳可加以区分。（2.5吉比特网络14秒就会发生序号绕回）
    • SACK（选择确认）：允许接收方发送确认号之余，还报告那些已接受、但是仍然无序的数据，避免发送方重复发送，报告一个分片数据例如（400序号——1000序号），就需要花费头尾32*2=64位即8字节的序号，SACK最多只能报告4个分片（还需要额外2字节标识SACK和选项长度，报告5字节需要42首部）。

TCP三次握手与四次挥手

TCP三次握手： TCP三次握手 分为三个阶段，假设A是客户端发起请求，B是服务端被动监听：

  1. A发起请求：选择一个起始序号seq = x发送报文，报文的SYN=1，而且TCP规定报文不能携带数据，客户端进入SYN-SENT（同步已发送）状态。

  2. B响应请求：如果同意连接，B选择一个起始序号seq = y发送报文，而且ACK=1，确认号ack=x+1，SYN=1，服务端进入SYN-RCVD（同步收到）状态；

  3. A再次确认：序号起始seq = x+1，发送报文ACK=1，确认号ack=y+1，A进入ESTABLISHED（已建立）状态，B收到报文也会进入ESTABLISHED状态。（该报文也可以携带数据，如果携带数据，下一个数据报文seq = x+2，如果没有携带，这个报文和下一个报文均使用seq = x+1）

注意，前两次的握手报文是固定消耗seq的，第三次ACK报文则视乎它是否携带数据。第二步的握手报文可以拆分（先发ACK+ack确认报文，再发同步报文sSYN=1，seq = y），成为四次握手（效果是等效的）。

  • 为什么要三次握手而不是两次（最后一次握手为什么？

  1. 避免历史的客户端SYN请求：假设客户端的第一次SYN迟到了，一段时间后服务端接收到了这个历史的请求，认为客户端想发起新的连接请求（而实际上客户端可能已经通过新连接完成请求或者放弃了请求），服务端就发送了响应报文，然而客户端现在没有请求因此会丢弃该报文，二次握手服务端却认为连接建立，一直等待数据到来，浪费了服务器的资源。

  2. 较好地同步双方的序列号：在二次握手中服务端基于第一个报文向客户端发送了确认号，三次握手中客户端也能基于服务器的报文向服务端发送确认号，保证了序号的同步性，也能验证双方的发送和接收能力是正常的。

TCP四次挥手： TCP四次挥手 分为四个阶段：假设客户端A发送完数据，数据最后一个序号是seq=A_end，现在想主动释放TCP。B发送的最后一个数据序号是seq=B_end

  1. A发送报文seq = u = A_end+1，FIN=1，客户端A进入FIN-WAIT-1（终止等待1）状态；

  2. B收到并响应报文，seq = v = B_end+1，ACK=1，确认号ack = u+1，B进入CLOSE-WAIT（关闭等待）状态。此时TCP连接属于半关闭（half-close）状态，B逐渐通知高层应用TCP关闭（不应该再期望数据），A不能向B发送数据，B仍能向A发送数据。

  3. A接收响应报文进入FIN-WAIT-2（终止等待2）状态，等待B的连接释放报文。B继续发送剩余数据，最后的序号演变成seq = w-1。B无数据发送，同意终止TCP连接，发送seq=w，FIN=1，ACK=1，重复确认号ack = u+1，B进入LAST-ACK（最后确认）状态，等待A确认。

  4. A发送最后确认，ACK=1，seq = u+1，ack=w+1，A进入TIME-WAIT状态，服务器收到报文关闭服务。此时A需要等待2倍报文最长寿命（Maximum Segment Lifetime，MSL），一般建议是两分钟，即等待4分钟，A才会完全关闭TCP或者重新发起TCP连接。

  • 为什么需要TIME-WAIT？

  1. 保证服务端正常关闭：如果A发送确认就关闭TCP，最后发送的确认如果丢失了就无法重传，导致服务器会反复重传最后确认，无法进入CLOSED状态；

  2. 等待该次TCP连接的网络中所有报文死亡：这样网络上就不会有任何报文出现在下次的TCP连接中。

TCP流量控制（Flow Control）

目的：控制发送方的速率，使得接收方来得及接收。几种特性在前文已经讨论了：

  1. 基于窗口的发送策略：发送报文时在窗口字段声明自己的最大接收空间，要避免一种死锁问题：当0空间报文发出时，对方不再发送数据，非0空间发出了但丢失，对方无法恢复；因此收到0空间报文时应该维护一个定时器，定时发送探测报文段（1字节数据），对方会相应窗口值，如果窗口值非0，死锁打破，如果仍然为0，复位定时器继续轮询。

窗口值为0也能接收的三类数据报：探测报文段、确认报文段、紧急数据报文段。

  1. TCP发送的时机： 几种机制：

  2. 根据MSS（最大报文长度）：达到MSS字节就发送，对TCP而言，MSS=536字节（注意MSS是不包括TCP首部的）。

  3. 根据PUSH字段：PUSH决定什么时候交付发送。

  4. 根据计时器：发送方维护定时器，期限到了（且不超过MSS就发送。

广泛使用的Nagle算法：发送缓存收到应用进程数据，第一个字节数据立刻发送，剩下的字节缓存起来，等待收到第一个字节确认ACK时再发送剩下数据。另一方面，缓存数据到达发送窗口一半、或者MSS时立刻发送。这种方法网络吞吐量大、带宽占用较小。

糊涂窗口综合征（Silly Window Syndrome）

TCP接收缓存已满，应用进程读走1字节，接收发送ACK声明空闲是1，发送方发送一字节又满了，这样的网络效率很低，影响TCP性能。

解决：接收方只有在空间能容纳一个MSS，或者空余空间占接收缓存一半时，才会发送确认报文；发送方不会发送太小的报文段，尽量组成足够大的才会发送。

TCP拥塞控制（Congestion Control）

流量控制针对是点对点的通信而言的，它倾向于描述发送、接收的速率问题，另一个角度来看是发送缓存、接收缓存的问题，因为缓冲区总是有限的，它不能无限制大小、无限制速率读走数据。拥塞控制则倾向于考虑网络的拥塞问题，假设已经实现了一种无限速率、无限大小的接收方，然而只有低速的网络传输或者拥堵的网络，那么整体的通信速率仍然受限于后者。这就是两种控制的区别。

当然就现实而言，二者应该是不可分割的，因为发送、接收的速率本身也会影响整个链路的速率，例如本身链路拥堵的情况下，就不应该维持高速的发送速率，这样等同于“加塞”，只会让拥堵程度严峻。

拥塞控制的目的是：防止数据无节制涌入网络导致吞吐量下降（过载，为0称死锁）。

TCP拥塞控制算法融合了四种，分别是慢开始（slow-start）、拥塞避免（congestion avoidance）、快重传（fast retransmit）、快恢复（fast recovery）。

慢开始与拥塞避免

基于前文描述“加塞”原因，拥塞控制同样需要约束发送窗口，约束方法是通过拥塞窗口cwnd进行判定，慢开始和拥塞避免都是调整cwnd的算法。

慢开始（慢是起始窗口设置小，并不是增长慢）：

初始时设置cwnd为较小值，具体是取决于发送方定义的最大报文段（Sender Maximum Segment Size，SMSS）：(cwnd不超过以下定义) 字节字节字节

每次cwnd字节增加量定义为： 意味着如果每次接收确认的字节N不超过SMSS，那么每次就会增加N字节。

TCP是面向字节流的，但为了描述方便，在拥塞控制中也引用报文段作为cwnd的单位。因此上面的增量就可以表述为，假设起始cwnd=1个报文段，接收到1个报文端确认，那么cwnd=2报文段，那么下次就会发出2个报文段，接收2个报文段确认，cwnd变为4...从这个计量单位而言，慢开始呈指数上升，因此这种算法的增长速度是极快的。

拥塞避免：

为了限制它的增长速度（假如不加以限制，那么多个Sender都会无节制生长，大大增加了网络拥堵出现的频率和概率），引入了另一种拥塞避免算法：增长不再按照接收的确认报文段数确定，而是每经过一个RTT，cwnd增加1个报文段，从报文段计量单位而言，这种算法呈线性上升。

TCP设定了慢开始门限（slow-start thresh，ssthresh），在cwnd<ssthresh时，拥塞窗口增长使用慢开始算法，大于时改成拥塞避免算法，等于时两种均可。

无论哪种算法，都导致cwnd增长，总会导致拥塞的发生的（为了追求高效，拥塞是不可避免的），因此当网络出现超时时（超时重传就认为拥塞，链路传输本身导致丢包概率远小于1%），就应该使cwnd减小,具体是：

  • ssthresh = cwnd/2，然后重置cwnd为1，重新执行慢开始和拥塞避免。
快重传和快恢复

超时导致cwnd从头增长效率是比较低的，因此弥补了快重传和快恢复机制，目的就是减少超时重传的发生，在触发超时重传的时间内接收方就应该报告提前触发重传，这就是快重传。

快重传：

使用快重传技术的接收方不用等待发送数据时才发送ACK确认，而是立刻发送确认，而且短时间内反复发送确认（例如收到序号100，短时间内仍然没有收到101，就需要反复发送ack=100的包），发送方一连收到三个相同确认，就要立刻进行重传。

该技术大概提升20%网络吞吐量。

快恢复：

当发送方发生快重传（一连三个相同ACK并且发起重传）后，就需要使用快恢复调整cwnd，具体是：

  • ssthresh = cwnd/2，再设置cwnd = ssthresh，然后执行拥塞避免算法（cwnd已经达到ssthresh）。

四种算法联合工作示意如下： 四种算法联合

以上拥塞避免采样线性加法增大（add increase，AI），快重传减小是减半，即乘法减小（multiplicative decrease，MD），合称AIMD算法。

最后发送窗口取值就是cwnd和接收窗口的较小值。

TCP应用细节

TCP粘包与拆包问题

TCP粘包拆包问题：TCP粘包与拆包是数据传输过程中，由于某些原因将发送方的小数据包合并成一个大数据包，或者将一个大数据包拆成多个小数据包，导致接受发无法确定数据包边界造成解析错误。

成因包括：
1. 本质原因是TCP面向字节流传输，本身并不关心数据包的边界。

  1. TCP的发送策略，例如Nagle算法、滑动窗口、延迟确认（允许接受方发送自己数据时捎带ACK，发送方在接收ACK前会缓存数据包）发送时，会将多个小数据包一起打包发送。

  2. TCP路径传输时，传输链路会根据TCP数据包长短进行合并或者分片传输，也会带来粘包和拆包问题。

几种解决方法：
1. 约定定长信息：发送和接受方都根据固定的长度进行解析，不足则以0填充；

  1. 特殊字符间隔：约定特殊字符作为分隔符，数据含分隔符则需要转义字符。

  2. 头部信息加入信息长度：发送方计算并填充数据长度，接受方按字段读取。

  3. 应用层协议：HTTP、Ftp等应用层协议都有消息填充规则和解析规则，确保数据解析准确。

TCP最大连接数限制

参数限制主要来自两个方面： 1. socket文件描述符：操作系统会限定文件描述符的数量和打开文件的数量。

  1. 等待队列长度：listen函数、操作系统内核都约定了等待队列的最大长度，超过该长度发起连接请求不会被接纳。

其余：还有其他参数、网络硬件性能、内存等限制TCP最大连接数目。

应用层