计算机网络笔记Ⅰ

概述

网络概述

​ 计算机网络=通信技术+计算机技术

​ 上图为通信系统的模型

​ 计算机网络就是一种特殊的通信网络，信源和信宿是计算机

​ 计算机网络定义：互联的自治的集合

​ 通过交换网络互联主机，交换节点（路由器或者交换机）

​ Internet：ISP网络互联的“网络之网络”。注意主机 = 端系统，通过通信链路连接，实现数据的分组交换。从服务的角度：通信基础设施，API

​ 网络协议，为进行网络中的数据交换而建立的规则，标准或约定。协议规定了格式，意义，顺序，动作。协议三要素：语法，语义，时序。协议举例：TCP，IP，HTTP，Skype，802.11。RFC文档。

​

网络结构

​ 网络结构分为网络边缘，接入网络/物理介质（有线，无线），网络核心

​ 网络边缘。主机，C/S应用模型，P2P应用模型。

​ 接入网络。家庭接入，机构介入，移动接入。带宽，指数据传输速率。独占/共享。DSL（数字用户线路），用分离器分离电话和网络，利用已有的电话线连接中心局的DSLAM，频分多路复用。ADSL，上下行速率不对称的DSL，独占。电缆网络，频分，也叫HFC（混合光纤同轴电缆），非对称，上行2M，下行30M，共享。家庭内用以太网。机构接入网络使用以太网。无线接入网络，通过基站（接入点）。无线局域网（LANs）如Wifi，广域无线接入。

​ 网络核心。关键功能：路由和转发。本地转发表（路由表），由路由算法产生。

​ Internet网络结构。端系统通过接入ISP（即上文接入网络）连接到Internet。接入ISP必须进一步互联。ISP互联方式：对等链路，IXP（本身是高速网络）。

网络核心

​ 数据交换解决主机之间的信息交流。交换设备互联形成交换网络。交换设备可以：动态转接（建立端口连接），动态分配传输资源。数据交换的类型：电路交换，报文交换，分组交换。

​ 电路交换。如电话网络。三个阶段：建立连接，通信，释放连接。独占资源。共享中继线的技术：多路复用技术。多路复用将链路/网络资源划分为资源片，每路独占。多路复用技术包括：频分多路复用（FDM)），时分多路复用（TDM），波分多路复用（WDM），码分多路复用（CDM）。频分多路复用，划分频率，有限电视网络。时分多路复用，TDM帧，每个用户占用时隙周期性出现。波分复用就是光的频分复用。码分多路复用，广泛应用于无线链路共享，每个用户分配一个位移的m bit码片序列，使用相同频率载波，各用户码片序列相互正交。

​ 报文交换。报文：发送信息整体。

​ 分组交换。把报文拆分，加头部信息。报文的拆分与重组，产生额外开销。共享链路，统计多路复用，按需共享链路。报文交换和分组交换均采用存储-转发交换方式。
$$
分组传输延迟（时延）=\frac{L(bits)}{R(bits/sec)}
$$
​ 对比报文交换和分组交换。报文交换时中间路由器需要更大的缓存空间。$M$表示整个文件大小，$L$表示单个分组的大小，$R$链路带宽，$h$跳步数，$n$路由器数（$n=h-1$)。计算分组交换需要的时间$T$。
$$
\begin{align}
T&=\frac{M}{R}+\frac{(h-1)L}{R}\&=\frac{M}{R}+\frac{nL}{R}
\end{align}
$$
​ 注意单位之间的转换，$8B=1Byte$，$100Mbps=100,000,000bps$。现在更广泛使用分组交换。

​ 分组交换和电路交换的比较。分组交换用统计多路复用。分组交换允许更多用户同时使用网络。分组交换不是绝对优于电路交换，分组交换使用于突发数据传输网络，且分组交换可能产生拥塞，需要协议处理可靠数据传输和拥塞控制。

计算机网络性能

​ 速率。速率即数据率，数据传输速率或比特率。单位时间（秒）传输信息（比特）量。最重要的性能指标。单位是bps，比特每秒。注意单位换算
$$
k=10^3\quad M=10^6\quad G=10^9
$$
​ 速率往往是额定速率（标称速率）， 理想（最大）数据传输速率

​ 带宽。原本指的频带宽度，单位是Hz。网络中的“带宽”是数字信道所能传送的”最高数据率“，单位是bps。

​ 延迟（时延）。 发生丢包和时延的原因，路由器的缓存队列。四种分组延迟：$d_{proc}$节点处理延迟，$d_{queue}$排队延迟，$d_{trans}$传输延迟，$d_{prop}$传播延迟（电，光，无线）。其中
$$
d_{trans}=\frac{L}{R}\quad d_{prop}=\frac{d}{s}
$$
​ 因此最终的总延迟是上述所有延迟的和。令$R$是链路带宽，$L$是分组长度，$a$是平均分组到达速率，定义流量强度为
$$
流量强度=\frac{La}{R}
$$
​ 流量强度$\rightarrow0$的时候平均排队延迟很小，流量强度$\rightarrow1$的时候平均排队延迟很大，流量强度$>1$的时候超出了服务能力，平均排队延迟无限大。

​ 时延带宽积。$时延带宽积=传播时延*带宽$，以比特为单位的链路长度。丢包率为丢包数/已发分组总数。吞吐量/率，表示发送端与接收端之间传送数据速率（b/s)，即时吞吐量，平均吞吐量，吞吐量取决于瓶颈链路。

计算机网络体系结构

​ 分层结构。网络体系结构是从功能上描述计算机网络结构，是分层结构，是计算机网络的各层及其协议的集合，是抽象的。下图是分层网络体系结构基本概念。

​ 协议是控制对等实体，协议是水平的，服务是垂直的，下层协议的实现对上层的服务用户是透明的。交换原语（SAP，服务访问点）。

​ OSI参考模型，开放系统互联参考模型，目的是支持异构网络系统的互联互通。OSI有七层。

​ 主机完成七层，路由器完成三层，交换机完成两层。上面四层叫端-端层。应用层，协议数据单元，A-PDU，+AH。表示层，P-PDU，+PH。会话层，S-PDU，+SH。传输层，T-PDU，+TH。网络层，N-PDU，+NH。数据链路层，+DT，+DH（加头加尾）。控制信息主要包括：地址，差错检测编码（不是所有协议），协议控制。

​ 物理层，规范接口特性，比特编码，数据率，比特同步（实际上解决的是时钟同步），传输模式（单工，半双工或叫交替双向，全双工）。数据链路层，构造帧，负责结点-结点数据传输（直接相连结点传输），组帧，物理寻址（在数据链路层），流量控制（避免淹没接收端），差错控制，访问（接入）控制（对共享的链路的控制）。网络层，负责源主机到目的主机数据分组交付，逻辑寻址。（IP地址），路由，分组转发。传输层，段，负责源-目的（端-端）（进程间）完整报文传输。分段与重组，SAP寻址（找到正确的进程，如端口号），连接控制（逻辑连接），流量控制，差错控制（不一定所有协议）。会话层，对话控制，不会分割数据，同步（插入同步控制点）。表示层，处理两个系统交换信息的语法与语义问题，数据表示转化（如字节顺序不同），应用层，加密/解密，压缩/解压缩，支持用户通过用户代理或者网络接口使用网络（服务），典型有FTP（文件传输），SMTP（电子邮件），HTTP（Web）。

​ TCP/IP参考模型

​ 实际上网络接口层没有实际协议。特点：Everything over IP，IP可为各式各样的应用程序提供服务，IP over Everything，IP可应用到各式各样的网络上。实际上更倾向展开网络接口层，因此有五层参考模型，应用层，传输层，网络层，数据链路层，物理层。数据名称。应用层-报文，传输层-段，网络层-数据报，链路层-数据帧。

计算机网络发展历史

​ 第一阶段：分组交换原理的提出与应用$\rightarrow$提出ARPAnet构想$\rightarrow$ARPAnet公开演示，第一个主机协议NCP

​ 第二阶段：ALOHAnet卫星网络$\rightarrow$提出网络互联体系结构（基本原则：极简，资质，尽力服务，无状态路由器，分散控制）$\rightarrow$以太网，私有网络体系结构

​ 第三阶段：部署TCP/IP

​ 第四阶段：因特网协会ISOC成立$\rightarrow$Web应用

​ 第五阶段：快速发展，宽带接入的快速部署，告诉无线接入快速增长，服务提供商创建其自己的专用网络。

网络应用

网络应用（层）内容概述

​ 主要内容：网络应用体系结构，网络应用的服务需求，Internet传输层服务模型，特定网络应用及协议，Socket编程。

网络应用的基本原理

​ 网络应用与单机应用的不同：远程与本地的交互。

​ 网络应用的体系结构。三种体系结构：客户机/服务器结构（C/S结构），点对点结构（P2P），混合结构。C/S结构，有功能角色上的划分，即服务器和客户机。Web就是C/S结构。P2P结构，优点：高度可伸缩，缺点：难于管理。混合结构，如Napster（应用），文件传输使用P2P，文件的搜索使用C/S结构（集中式）。

​ 网络应用进程通信。两个进程之间的通信。同一主机上的进程通过操作系统控制，不同主机上的进程通过消息交换通信。客户机进程是发通信的进程，服务器进程是等待通信请求的进程。注意P2P架构也有这两种区分。通过套接字Socket通信，Socket是对传输层，网络层，数据链路层和物理层的抽象，是网络提供的API，可以选择传输协议，参数设置等。对进程的寻址通过IP地址和端口号，HTTP是80端口，邮件是25端口。IP地址+端口号是进程的唯一标识。网络层应用需要遵循协议，公开的协议由RFC定义，私有协议如多数P2P文件共享应用。应用层协议的内容：消息的类型（请求消息，响应消息），消息的语法/格式，字段的语义，规则。

​ 网络应用需求。要求类型：数据丢失/可靠性，时间/延迟，带宽。下图是传输层提供的服务。

Web应用

​ Web应用概述。构成要素：网页及其互相连接。网页包好多个对象，包括HTML文件，JPEG图片，视频文件，动态脚本，有一个基本HTML文件。Web对象的寻址，通过URL（同一资源定位器）。基本格式为Scheme://host:port/path。Web遵循HTTP协议（超文本传输协议），是C/S结构。典型的Web Server软件是Apache软件，是事实上的标准。HTTP版本有1.0和1.1。使用的传输层协议是TCP，使用80端口。HTTP是无状态协议，即不维护有关客户端过去所发请求的信息。

​ HTTP连接类型。两种连接的类型：非持久性连接，持久性连接。非持久性中每个TCP连接最多允许传输一个对象，使用在HTTP1.0中。持久性允许多个对象，使用在HTTP1.1中。非持久性连接，过程是建立连接-请求资源-关闭连接。RTT（Round Trip Time）从客户端发送一个很小的数据包到服务器并返回所经历的时间。非持久性连接的响应时间$Total=2Rtt+发送时间$。非持久性连接的问题：每个对象需要2个RTT，并且并行请求TCP连接会占用资源。持久性连接，分为无流水的持久性连接（客户端收到前一个响应才发送新的请求）和带有流水机制的持久性连接。

​ HTTP消息格式。HTTP协议有两类消息，请求消息和响应消息。请求消息是ASCII码，人可直接读。请求消息格式：第一行请求行（包含URL），下面是头部行，然后是空行。具体如下。

​ POST方法（method）上传客户端的输入，GET方法也可以上传输入（URL方法）即在URL里面带有传输信息。HTTP1.0有GET，POST，HEAD，HTTP1.1增加了PUT和DELETE，即上传文件和删除文件。

​ HTTP响应消息。第一行是状态行，然后是头部行。头部行中包含两个时间，响应时间和文件上次修改时间。HTTP响应状态代码有200 OK，301 Moved Permanently，400 Bad Request，404 Not Found，505 HTTP Version Not Supported（都在状态行里）。

​ Cookie技术。HTTP协议是无状态，但是很多应用需要服务器掌握客户端的状态。HTTP的响应消息和请求消息可以添加cookie的头部行。每次用户登陆时，服务器可以根据用户的HTTP请求中的头部的cookie在数据库中找到用户的数据，及cookie相当于用户在这个服务器上的唯一标识。第一次登陆的用户，服务器会给用户分配一个cookie。

​ Web缓存/代理服务器技术。功能是能在不访问服务器的前提下满足客户端的HTTP请求。目的是改善性能（缩短客户请求的响应时间，减少流量，大范围实现有效内容分发）。大致意思是客户向代理服务器而不是原始服务器发送请求，如果代理服务器里有请求对象则直接返回，否则向原始服务器发送请求返回给客户端并保存此对象。缓存服务器的问题是保持数据和原始服务器相同，解决办法是条件性GET，即缓存服务器在HTTP请求消息中声明所持有版本的日期，如果缓存的版本是最新的，则响应消息中不包含对象，即发送304 Not Modified（HTTP/1.0），否则发送最新的版本。

Email应用

​ Email应用概述。Email应用由邮件客户端，邮件服务器和SMTP协议构成。邮件客户端主要读写Email消息，与服务器交互，收，发Email消息（如Outlook，Foxmail，Thunderbird，Web客户端）。邮件服务器为用户分配邮箱（储存空间），维护消息队列。SMTP，邮件服务器之间传递消息所使用的协议。SMTP依赖TCP协议，使用端口25，有三个阶段：握手，消息的传输，关闭，采用命令/响应交互模式，即命令（ASCII码）然后响应。具体过程是发送方将邮件发送到自己的邮件服务器，然后发送到接收方的邮件服务器，最后被接收方接收。常用命令：HELO，MAIL FROM，RCPT TO，DATA，QUIT。SMTP协议使用持久性连接，要求消息必须由7位ASCII码构成，SMTP服务器利用回车.回车确定消息的结束。HTTP是拉式的服务，SMTP是推式的服务，都使用命令/响应交互模式，命令和状态代码都是ASCII码。而HTTP每个对象封装在独立的响应消息中，SMTP多个对象在由多个部分构成的消息中发送。

​ Email消息格式。由头部行和消息体组成。头部由To，From和Subject组成，消息体由消息本身（ASCII码构成）。MIME：多媒体邮件扩展，通过在邮件头部增加额外的行以声明MIME的内容类型。注意从服务器获取邮件不是使用SMTP而是使用邮件访问协议（如POP3，IMAP，HTTP）。POP协议有认证过程和事务阶段。认证过程：客户端命令$\rightarrow$服务器认证。事务阶段的命令如，List，Retr，Dele，Quit。POP协议常用模式：下载并删除模式，下载并保持模式（对于服务器而言）。POP3是无状态的。IMAP协议3个优势（消息统一保存，允许文件夹，支持跨会话的用户状态，即IMAP是有状态的）。

DNS应用

​ DNS概述。DNS中文名域名系统，解决Internet上主机/路由器的识别问题。由于IP地址不易于记忆，因此人使用域名，机器使用IP地址。域名解析系统DNS就是将域名翻译成IP地址。DNS是使用多层域名服务器构成的分布式数据库（分布式层次数据库），是互联网的核心服务（位于应用层）。DNS提供的服务：域名翻译成IP地址，主机别名，邮件服务器别名，负载均衡（Web服务器）。下图是DNS分布式层次是数据库的结构。

​ 根域名服务器，当本地域名服务器无法解析域名时，访问根域名服务器。 然后有顶级域名服务器（TLD），权威域名服务器。本地域名服务器。每个ISP有一个本地域名服务器（默认域名解析服务器），当主机进行DNS查询时，查询被发送到本地域名服务器。本地域名服务器作为代理将查询转发给（层级式）域名解析服务器。DNS查询使用的是迭代查询或者递归查询（区别在于是哪台服务器在查询最终解析结果）。

​ DNS记录缓存和更新。域名服务器会缓存得到的IP地址。本地域名服务器一般会缓存顶级域名服务器的映射，因此根域名服务器不经常被访问，并且有更新的机制。

​ DNS记录和消息格式。DNS记录称为资源记录（RR）。下图是RR的格式。

​ Type=A时，表示主机域名和IP地址，Type=NS时，代表域和该域权威域名解析服务器的主机域名。Type=CNAME时是某一真实域名的别名和真实域名，Type=MX时Value和name是相对应的邮件服务器。DNS协议是查询/回复协议。也有消息头部。消息头部包括16位查询编号，flags等

​ 注册域名的步骤：在域名管理机构提供权威域名解析服务器的名字和IP地址，然后域名管理机构想com顶级域名解析服务器中插入两条记录（一条是你的权威域名解析服务器的名字，一条是权威域名解析服务器的IP地址）。

P2P应用

​ 以文件分发为例。C/S架构的文件分发时间为服务器上传N个文件的时间和客户端下载的时间，注意服务器要串行上传N个文件，N是需要此文件的客户端的数量）。下图是C/S架构和P2P架构需要的大致时间。

​ 文件分发使用BitTorrent协议（BT协议）。torrent值交换同一个文件的文件块的节点组。tracker是跟踪参与torrent的节点。文件划分为256KB的chunk。节点会加入torrent，向tracker注册以获得节点清单，下载的同时，节点需要向其他节点上传的chunk。节点可能加入或离开。获取chunk的过程：不同节点持有的文件的不同chunk结合，节点定期查询每个邻居所持有的chunk列表，节点发送获得缺失的chunk的请求（稀缺优先）。发送chunk时是tit-for-tat，Alice会选择正在向她发送chunk且速度最快的四个发送chunk，并且每30s随机选择一个其他节点发送chunk，新节点可能加入top4。

​ P2P应用_索引。P2P系统的索引：信息到节点位置（IP地址+端口号）的映射，如文件传输（电驴）和即时消息（QQ）。索引分为集中式索引，如Napster，节点加入时通知中央服务器报告IP地址和内容，存在单点失效问题，性能瓶颈和版权问题，还有分布式索引（洪泛式查询），是完全分布式架构（如Gnutella），每个节点仅对它共享的文件进行索引。覆盖网络是指TCP连接和节点构成的图。洪泛式查询时，查询消息通过已有的TCP连接发送，节点会转发查询消息，如果查询命中，则利用反向路径发回查询节点，第三种是层次式覆盖网络（Skype），是介于集中式索引和洪泛查询之间的方法，每个节点是超级节点或者被分配一个超级节点，普通节点查询时会在超级节点上找，如果没找到超级节点之间会使用洪泛查询。

Socket编程

​ 可以直接面向网卡编程（数据链路层），基于Packet Driver，NDIS，LibPcap/WinPcap，Libnet，Libnids，Libicmp编程（数据链路和网络层之间），NetBIOS，Socket编程（在传输层和应用层之间），Web/RPC/中间件编程（应用层之上）。

​ 应用编程接口（API）。应用层是应用进程控制，传输层及以下基本都是操作系统控制。典型的应用编程接口：Berkeley UNIX操作系统定义的Socket，微软定义的WINSOCK，AT&T的UNIX V系统的TLI。

​ 套接字最初面向TCP/IP协议栈接口，但是后来发展成可以支持多种协议，现在是事实上的工业标准，提供了应用进程间通信的抽象机制。Socket对外使用IP地址+端口号（端点地址）来标识，对内使用套接字描述符（小整数）。在Windows中每个进程都有一个Socket描述符表，当应用进程创建套接字时，操作系统分配一个数据结构存储该套接字相关信息。套接字地址使用数据结构sockaddr_in。下图是sockaddr_in的成员变量。地址族用于适用于多种不同的协议栈，TCP/IP是AF_INET。

​ 套接字函数。介绍WinSock。Winsock必须先调用WSAStartup，最后调用WSACleanup（因为Windows使用动态链接库Windows Sockets DLL）。

​ 服务器端和客户端的函数调用过程

传输层

传输层服务

​ 需要理解机制：多路复用/分用，可靠数据传输机制，流量控制机制，拥塞控制机制。

​ 传输层协议为运行在不同Host上的进程提供了一种逻辑通信机制（两个进程直接通信），而网络层是主机之间的逻辑通信之间的通信，传输层是进程之间。

​ TCP协议：可靠的，按序的交付服务，有拥塞控制，流量控制，连接建立

​ UDP协议：不可靠的（尽力而为）

​ 两种服务都不提供延迟和带宽的保障。

复用和分用

​ 多路复用/分用。使用多路复用/分用的原因是如果某层的一个协议对应直接上层的多个协议/实体，则需要复用/分用。分用的工作过程就是封装传输层数据段成IP数据包传输给目的主机之后解封装。

​ 无连接的多路分用（面向UDP），由二元组（目的IP地址和端口号）唯一标识socket。主机收到UDP段后，检查段中的端口号并将UDP段导向绑定在该端口号的socket，而不管源主机的端口号或者IP地址。

​ 面向连接的多路分用（面向TCP），由四元组（源IP地址和端口号，目的IP地址和端口号）唯一标识socket。目的主机（服务器主机）区分socket使用四元组中的所有信息。因为TCP连接一定是一对一的，但在一个端口上可以有多个TCP socket。

无连接传输协议——UDP

​ UDP协议基于IP地址，使用多路复用/分用，能够进行简单的错误校验（遵守段-段的原则）。UDP是Best Effort的，UDP是无连接的（不需要握手，每个UDP段和其他UDP段独立）。

​ UDP为什么存在？无需建立连接（减少延迟），UDP实现非常简单，无需维护连接状态，UDP头部开销少（8字节，TCP是20字节），UDP没有拥塞控制，应用可更好地控制发送时间和速率。

​ UDP的用途：流媒体，DNS，SNMP（简单网络管理协议，在IP网络中管理节点，应用层协议）。同时UDP其实是可以实现可靠数据传输。

​ UD使用的报文格式

​ UDP检验和。检验和用于检验UDP段在传输中是否发生错误。每16bit视为一个整数，并把所有整数相加，进位加在和的后面，最后将结果按位取反。接收方也是计算校验和（相同的方法），如果不相等则检测出错误，如果相等也有可能有错误。具体校验和如下图所示

可靠数据传输的基本原理

​ 可靠的定义：不错，不丢，不乱。以后用RDT代表可靠数据传输。下图表示常用的函数（行为）的具体含义。rdt_send()：被上层应用调用，将数据交给rdt以发送给对方。udt_send()：被rdt调用，在不可靠信道上向接收方传输数据。rdt_rev()：当数据包到达接收方信道时被调用。deliver_data()：被rdt调用，向上层应用交付数据。注意到udt_send()和rdt_rcv()都是双向箭头，意味着可靠数据传输不只是单向数据流动而是双向控制消息的流动。FSM，有限状态自动机，用来刻画传输协议。

​ RDT1.0，在可靠信道上的可靠数据传输。假设底层信道完全可靠（不会发生错误，不会丢弃分组），发送方只需要不断接收来自上层的数据（rdt_send）并发送（udt_send）就可以，而接收方接收数据（rdt_rec）后直接交给上层（deliver_data）。

​ RDT2.0，假设信道可能产生错误，但是不会丢失或者乱序。可以利用校验和检测出错误，而纠正错误需要确认机制。ACK表示接收方显式告知发送方分许已正确接收，NAK表示接收方显式告知发送方分组有错误。发送方收到NAK后，重传分组。这种rdt协议称为ARQ协议。

​ RDT2.1，假设ACK/NAK消息发生错误/被破坏。解决办法是重传，并使用序列号来解决重复分组的问题（即不知道ACK的是哪个分组）。FSM需要添加状态。左图为发送方FSM，右图是接收方FSM。注意到发送方如果接收到了NAK就会重传当前的分组而不管NAK的序号，仅到收到了ACK才进入下一个状态，接收方仅当接收到了正确序号分组（并发送ACK）才进入下一个状态，而收到受损的分组会发送NAK，收到错误序号的分组发送ACK。

​ RDT2.2，假设与RDT2.1一致。可以取消NAK。在ACK中加入序列号，ACK的序号意思是最后一个被确认的分组的序号（即用ACK 1代替NAK 0，用ACK 0代替NAK 1）。

​ RDT3.0，假设信道即可能发生错误，也可能丢失分组。解决办法是设置定时器，发送方等待合理的时间之后若没有收到ACK则重传。下图为发送方的FSM。发送方仅当收到正确ACK时进入下一步状态，仅到定时器超时才重传当前分组。

​ RDT2.0采用了校验和+ACK+重传，RDT2.1和RDT2.2采用了校验和+ACK+重传+序列号，RDT3.0采用了校验和+ACK+重传+序列号+定时器。

​ RDT3.0的性能不够，下图显示链路带宽有1Gbps，但是由于等待ACK，导致实际带宽为33KB/sec。

滑动窗口协议

​ 流水线机制与滑动窗口协议。流水线与停等协议不一样在于停等协议每次等待收到ACK再发下一个分组，而流水线不等待直接发送。流水线机制需要更大的序列号范围，发送方和接收方需要更大的存储空间以缓存分组。

​ 滑动窗口协议（Sliding-window protocol）。随着协议的运行，窗口在序列号空间内向前滑动。具体的滑动窗口协议有GBN，SR。

​ GBN（Go Back to N）协议，分组头部包含k-bit序列号，窗口尺寸为N，即最多允许N个分组未确认。GBN采用累计确认机制，即收到ACK n的时候n之前的分组都被确认接收。需要为未收到确认的分组设置计时器，如果发生Timeout，重传所有未收到ACK的分组。注意发送方发生了传输请求，Timeout，收到了完整的分组，收到了受损的分组时的动作。接收方没有缓存，只维护期望收到的分组的序列号。下面左图是发送方，右图是接收方。

​ SR（Selective Repeat）协议。与GBN不同，SR协议有多个计时器，接收方设置了缓存，对每个分组单独进行确认，发送方只重传那些没收到ACK的分组（每个分组的定时器超时了就重传），SR在发送方也有一个大小为N的窗口。在SR协议中，发送方与接收方的窗口的base不是同步的。

​ 具体的SR协议的发送方和接收方的动作如下所示。注意接收方如果接收到了[rcvbase-N,rcvbase-1]时的行为。SR协议可能会面对的问题是，接收方有可能不能区分收到的分组是序列号中前一轮的分组还是新一轮的分组，因此序列号空间大小$2^k$与窗口尺寸$N_s$和$N_r$需要满足$N_s+N_r\leq2^k$。

面向连接传输协议——TCP

​ TCP的特点：点对点（一个发送方对应一个接收方），可靠的，按序的字节流，有流水线机制，发送方和接收方都有缓存，是全双工的，是面向连接的（连接状态只在连接的两端中维护，在沿途节点中并不维护状态，TCP的连接包括，两台主机上的缓存，连接状态变量，socket等），有流量控制机制和拥塞控制机制。

​ TCP的端结构如下图所示。注意TCP的sequence number是TCP段中第一个字节的编号，建立TCP连接时，双方随机选择序列号。Receive Window表示接收窗口的大小，用来流量控制。ACK表示希望收到的下一个字节的序列号，同时TCP采用累计确认机制，即该序列号之前的所有字节均已被正确收到。TCP规范中没有规定接收方如何处理乱序到达的段，由TCP的实现者做出决策。

​ TCP的可靠数据传输。TCP可靠数据传输的概述：流水线机制，累计确认，单一的重传计时器。触发重传的事件有超时和收到重复ACK。

​ TCP的定时器的超时时间的设置，与RTT有关，但RTT不是常量。定时器时间过短会有不必要的重传，过长会对段丢失反应慢。对RTT的估计要测量RTT，测量多个RTT求平均值来形成RTT的估计值$EstimatedRTT$，其中$\alpha$的典型值是0.125，下面公式也称为指数加权移动平均
$$
EstimatedRTT=(1-\alpha)EstimatedRTT+\alphaSampleRTT
$$
​ 定时器超时时间设置为$EstimatedRTT$加上一个安全边界$DevRTT$（反应了网络的稳定状况），$DevRTT$的计算公式也是指数加权移动平均，$\beta$的典型值为0.25，最后的定时器超时时间设置为$TimeoutInterval$。
$$
DevRTT=(1-\beta)DevRTT+\beta|SampleRTT-EstimatedRTT|\
TimeoutInterval=EstimatedRTT+4*DevRTT
$$
​ TCP的发送方事件。接收到上层数据之后创建段，开启计时器，设置超时时间。如果超时了重传引起超时的一个段并重启定时器。如果收到了ACK，如果收到ACK则更新base并重启定时器（收到重复ACK将在下面描述）。接收方如果接收了期望序列号，则延迟ACK（先不发ACK，等待下一个段，最多500ms，如果这时接收到了另一个按序段则发送ACK），如果收到了比期望序列号大的段则立即发送相同ACK（如果此时有填补的分组到达则更新并发送）。TCP的快速重传机制，因为TCP如果发生了超时则超时时间间隔会被重新设置为原来的两倍导致其很大，可以通过重复ACK检测分组丢失，如果发送方收到对同一数据3个ACK则执行快速重传。

​ TCP的流量控制。接收方会为TCP连接分配buffer用来接收收到的数据，并处理buffer里面的数据。流量控制就是让发送方不会传输太多，太快以至于淹没接收方（buffer溢出），本质上是一种速度匹配的机制。假定TCP接收方会丢弃乱序段，接收方通过在段的头部字段将RcvWindow（接收方可用缓存空间）告诉发送方来让发送方限制已发送的但是还未收到ACK的数据不超过RcvWindow尺寸。

​ TCP连接管理。TCP发送方和接收方在传输之前要建立连接。客户端和服务器端通过三次握手来建立连接。第一步，客户端选择初始序列号（随机等）发送TCP SYN段给服务器，第二步服务器端答复SYN ACK报文段，并选择初始序列号并向系统申请资源，第三步，客户端答复ACK报文段（不是SYN），为了向服务器确认收到了SYN ACK。

​ TCP连接的关闭。第一步客户端向服务器发送FIN控制段，第二步服务器端收到FIN后回复ACK，关闭连接并发送FIN，第三步客户端收到FIN回复ACK（会等待，为了确保服务器端关闭，如果收到FIN会重新发送ACK），第四步服务器端收到ACK会真正关闭连接。

拥塞控制原理

​ 拥塞的非正式定义：太多发送主机发送了太多数据或者发送速度太快，以至于网络无法处理。表现为：分组丢失（路由器缓存溢出），分组延迟过大（排队延迟）。注意区分拥塞控制（路由器排队）和流量控制（接收方处理速度）。注意区分不同场景下拥塞的成因和代价。场景1展示的代价：延迟过大，吞吐率限制，场景2展示的代价：由于重传导致了网络资源的浪费，吞吐率进一步降低，场景3展示的代价：当分组被drop掉时，任何用于该分组的“上游”传输能力全都被浪费掉。下图展现的是场景3中结果。

​ 拥塞控制为什么要在传输层（待解答）。拥塞控制的方法分为：1.端到端的拥塞控制，网络层不需要显式地提供支持，端系统通过观察loss，delay等网络行为判断是否发生拥塞，TCP采取这种方法，2.网络辅助的拥塞控制，利用路由器向发送方显式地反馈网络拥塞信息（简单的拥塞指示），ATM网络采用。ATM ABR拥塞控制：使用ABR提供的“弹性服务”，发送方发送RM（resource management cells）被交换机设置之后由接收方返回给发送方，交换机设置RM cell位（网络辅助）来控制发送方，NI bit表示rate不许增长，CI bit表示拥塞指示。实际上数据cell（类似TCP数据段）中也有标志位来表示拥塞程度。

TCP拥塞控制

​ 拥塞控制需要发送方控制发送的数据量，定义$CongWin$为最后一个被发送的字节的序列号减去最后一个被ACK的字节的序号的差值，即$LastByteSent-LastByteAcked\leq CongWin$。那发送速度大小约为
$$
rate\approx\frac{CongWin}{RTT}Bytes/sec
$$
​ 所以我们可以通过动态调整$CongWin$来调整发送速率，同时$CongWin$反映所感知的网络拥塞。当发生loss事件时（timeout或3个重复ACK）调整$CongWin$。两种机制：1.加性增，乘性减（AIMD），2.慢启动（SS）。

​ AIMD，原理：逐渐增加发送速率，谨慎探测可用带宽，直到发生loss。每个RTT将$CongWin$增大一个MSS，发生loss后将$CongWin$减半。

​ SS，原理：当连接开始时，$CongWin$被初始化为1个MSS。具体算法如下。注意$CongWin$的数值为MSS的数量。虽然在算法内看上去为线性增长，但由于$CongWin$控制了发送速度，实际上为指数型增长，即每次RTT之后都会将$CongWin$翻倍。

​ Threshold变量，控制指数增长转变为线性增长。下图蓝色的线为TCP早期版本，发生了loss之后会将$CongWin$设置为1，同时要改变Threshold为发生loss事件时$CongWin$的一半。而TCP Series 2 Reno则是真正的AIMD。同时TCP对不同的Loss事件的处理也不一样，如果收到了3个重复ACK，$CongWin$会被切到一半然后线性增长（下图黑线），如果发生Timeout事件会直接将$CongWin$设置为1个MSS（下图蓝线）。原理是Timeout代表更加严重的拥塞，3个ACK表示网络还能传输一些段。更详细的TCP拥塞控制行为见MOOC。

​ 上述过程就是TCP的拥塞控制算法。具体表示如下图。

​ TCP性能分析。TCP吞吐率，给定拥塞窗口大小（即$CongWin$）和RTT，忽略SS，TCP发生超时事前的吞吐率为$W/RTT$，发生超时之后为$W/2RTT$，平均吞吐率为$0.75W/RTT$（粗略估计）。吞吐率与丢包率的关系，10Gbps网络下，$CongWin$从$W/2$增加至$W$时出现一个丢包，那么需要的丢包率为$2*10^{-10}$。TCP的公平性，如果K个TCP Session共享相同的瓶颈带宽R，那么每个Session的平均速率为$R/K$，TCP是具有公平性的（交叉线）。UDP由于没有拥塞控制，因此UDP将比TCP快（UDP破坏了公平性），同时某些应用打开了多个并发连接TCP连接也会破坏公平性。

传输层总结

​ 基本原理：复用/解复用，可靠数据传输，流量控制，拥塞控制。

​ Internet的传输层：UDP，TCP