量子波动速读《计算机网络:自顶向下方法》

1,854 阅读13分钟

本文为《计算机网络:自顶向下方法》的阅读笔记,一些过于简单和偏门的知识点会被忽略,例如经常接触的应用层知识就不需要赘述了。

运输层

无连接运输:UDP

UDP仅仅在IP协议的基础上实现了多路复用(端口)和校验,不保证交付以及按序交付,虽然简陋但是有以下优点:

  • 关于何时、发送什么数据的应用层控制更为精细;
  • 无需连接建立;
  • 无连接状态;
  • 分组首部开销小。

首部只有四个字段:源端口、目标端口、长度和校验和。发送方的UDP对报文段中的所有16比特字的和进行反码运算,求和时遇到的任何溢出都被回卷。在接收方,全的16比特字(包括检验和)加在一起,如果该分组中没有引入差错,则显然在接收方处该和将是1111111111111111

可靠数据传输原理

如何在不可靠的信道上实现可靠的传输,我们可以根据信道的特性从简到繁一步步得到可靠的传输协议。

经完全可靠信道的可靠数据传输

在可靠信道只需要简单地发送接收就行。

  • 发送端

  • 发送端

经具有比特差错信道的可靠数据传输

这种情况需要自动重传请求协议来处理,需要三种机制处理比特差错:

  1. 差错检测,需要一种机制以使接收方检测到何时出现了比特差错;
  2. 接收方反馈:接收方回答的“肯定确认”(ACK)和“否定确认”(NAK);
  3. 重传:接收方收到有差错的分组时,发送方将重传该分组文。

一种直观的方案是发送收到ACK后发送下个分组,收到NAK后重新发送,然后确认分组本身也会损坏。当发送方收到损坏的确认分组时,需重传当前数据分组即可。 然而,这种方法在发送方到接收方的信道中引人了冗余分组,这就需要发送方对其数据分组编号来确认收到的分组是否为重传数据。另外,如果不发送 NAK, 而是对上次正确接收的分组发送一个ACK,发送方就知道接收方没有正确接收到跟在被确认两次的分组后面的分组。

  • 发送方

  • 接收方

经具有比特差错的丢包信道的可靠数据传输

对于丢包信道,一方面需要重传丢失数据,另外需要一个倒计数定时器来实现超时重传,发送方需要做到:

  1. 每次发送一个分组时,便启动一个定时器。
  2. 响应定时器中断。
  3. 终止定时器。
  • 发送方

流水线可靠数据传输协议

停等协议的信道利用率低,更好的方法是使用流水线,一次发送和确认多个分组,协议需要做出以下扩展:

  • 必须增加序号范围;
  • 协议的发送方和接收方两端也许必须缓存多个分组;
  • 解决流水线的差错恢复有两种基本方法是:回退N步选择重传
回退N步

回退N步也成为滑动窗口协议,要求流水线中未确认的分组数不能超过窗口大小N,协议的发送方看到的分组流水线如下:

  • 基序号(base)为最早的未确认分组的序号;
  • 下一个序号(nextseqnum)为最小的未使用序号;

发送方必须响应三种类型的事件:

  • 上层的调用:当上层调用 rdt_send()时,发送方首先检查发送窗口是否已满。如果窗口未满,则产生一个分组并将其发送,并相应地更新变量。如果窗口已满,发送方告知上层该窗口已满;
  • 收到一个ACK:对序号为n的分组的确认采取累积确认的方式,表明接收方已正确接收到序号为几的以前且包括在内的所有分组。
  • 超时事件:如果出现超时,发送方重传所有已发送但还未被确认过的分组。

因此完整的协议如下:

  • 发送方

  • 接收方

选择重传

回退N步会传递已经收到的分组,造成了性资源的浪费,而选择重传只需要重传丢失或者损坏的分组即可。发送方和接收方看到的流水线如下:

发送方的事件与动作如下:

  1. 从上层收到数据。和回退N步相同;
  2. 超时。现在每个分组必须拥有其自己的逻辑定时器,因为超时发生后只能发送一个分组;
  3. 收到ACK。如果收到ACK,倘若该分组序号在窟口内,则发送方将那个被确认的分组标记为已接收。如果该分组的序号等于send_base,则窗口基序号向前移动到具有最小序号的未确认分组处。如果窗口移动了并且有序号落在窗口内的未发送分组,则发送这些分组。

面向连接的运输:TCP

TCP在不可靠的IP协议之上实现了一个端到端的可靠数据传输通道(可靠、有序)。TCP协议是一道字节流流水线,每次从缓冲区取出最大报文段长度组成分组。TCP报文段首部如下

  • 32比特的序号字段和32比特的确认号字段
  • 16比特的接收窗口字段,该字段用于指示接收方愿意接受的字节数;
  • 首部长度字段,该字段指示了以32比特的字为单位TCP首部长度;
  • 可选与变长的选项字段
  • 6比特的标志字段,ACK比特用于指示确认字段中的值是有效的,RST、SYN和FIN比特用于连接建立和拆除。

TCP的序号是建立在传送的字节流之上,因此一个报文段的序号 是该报文段首字节的字节流编号,主机填充进报文段的确认号是主机期望从主机 收到的下一字节的序号,TCP使用了累计确认

TCP发送方的整体运行逻辑如下

NextSeqNum=InitialSeqNumber
SendBase=InitialSeqNumber

loop (forever) {
    switch(event) {
        event: data received from application above
            create TCP segment with sequence number NextSeqNum
            if (timer currently not running)
                start timer
            pass segment to IP
            NextSeqNum=NextSeqNum+length(data)
            break;
        event: timer timeout
            retransmit not-yet-acknowledged segment with
            smallest sequence number
                start timer
            break;
        event: ACK received, with ACK field value of y
            if (y > SendBase) {
                SendBase=y
                if (there are currently any not-yet-acknowledged segments)
                    start timer
            }
            break;
    }
} /* end of loop forever */

TCP涉及到以下技术点:

  • 往返时间的估计与超时:需要统计出RTT平均值(EstimatedRTT)和方差(DevRTI),从而可以计算出超时时间:Timeoutlnterval = EstimatedRTT + 4 · DevRTT
  • 可靠数据传输
    • 超时间隔加倍:每次TCP重传时都会将下一次的超时间隔设为先前值的两倍。
    • 快速重传:一且收到3个冗余ACK,TCP就执行快速重传
    • 流量控制:TCP通过让发送方维护一个称为接收窗口,接收窗口告知发送方接收方还有多少可用的缓存空间。

TCP的连接通过三次握手建立

  1. 客户端发送SYN报文,并告知随机选择的初始序号(client_isn);
  2. 服务端回复SYNACK报文,告知随机选择的初始序号(server_isn),以及确认收到client_isn;
  3. 客户端回复送ACK报文,确认收到server_isn。

TCP关闭需要四次握手,一方发送FIN,另外一方回复ACK。

TCP拥塞控制

拥塞会带来诸多问题:

  • 当分组的到达速率接近链路容量时,分组经历巨大的排队时延。
  • 发送方必须执行重传以补偿因为缓存溢出而丢弃(丢失)的分组。
  • 发送方在遇到大时延时所进行的不必要重传会引起路由器利用其链路带宽来转发不必要的分组副本。
  • 当一个分组沿一条路径被丢弃时,每个上游路由器用于转发该分组到丢弃该分组而使用的传榆容量最终被浪费掉了。

TCP使用拥塞窗口cwnd对发送流量的速率进行了限制,TCP定义“丢包事件”为:要么出现超时,要么收到来自接收方的个冗余ACK。拥塞窗口的调整机制如下:

网络层

因特网的网路协议提供的是尽力而为服务,尽力而为服务看起来是根本无服务的一种委婉说法。

路由器工作原理

  • 输入端口:功能包括执行将一条输入的物理链路与路由器相连接的物理层功能、执行需要与位于人链路远端的数据链路层交互的数据链路层功能,以及通过查询转发表决定路由器的输出端口(最长前缀匹配);
  • 交换结构:交换结构将路巾器的输入端口与输出端口相连接,有经内存交换、经总线交换和经互联网络交换三种形式;
  • 输出端口:输出端口存储从交换结构接收的分组,并通过执行必要的链路层和物理层功能在输入链路上传输这些分组;
  • 路由选择处理器:路由选择处理器执行路由选择协议,维护路由选择表以及连接的链路状态信息,并为路由器计算转发表。

当输出端口等待分组超过一次发送能力时就需要排队,当无内存可用于存储到达的分组时将会出现丢包。在输出端口上的一个分组调度程序须在这些排队的分组中选出一个来发送,如先来先服务调度、加权公平排队等。如果没有足够的内存来缓存一个人分组,那么必须选择丢弃的分组,策略有弃尾主动队列管理(例如随机早期检测)等。

网际协议:因特网中的转发和编址

IPv4数据报首部定义如下

关键字段如下:

  • 版本:IPv4还是IPv6;
  • 首部长度
  • 服务类型
  • 数据报长度
  • 标识、标志、片偏移:与1P分片有关;
  • 寿命:每当数据报由一台路由器处理时,该字段的值减一。TTL字段减为0,则该数据报必须丢弃;
  • 协议:数据部分应交给哪个特定的运输层协议;
  • 首部检验和:在每台路由器上必须重新计算检验和并再次存放到原处,因为TTL字段以及可能的选项字段会改变;
  • 源和目的IP地址
  • 选项
  • 数据

当分组大小超过链路的最大传送单元,发送方需要将分组分片,分片后的分组使用标识标志片偏移字段,由最终的接收端完成组装。一个典型的分片如下

字节 ID 偏移 标志
第1片 1480 777 0 1
第2片 1480 777 185 1
第3片 1020 777 370 0

IP地址可以人为分配,或者通过DHCP动态分配,DHCP的工作流程如下:

  • DHCP服务器发现:新加入的主机广播一个DHCP发现报文
  • DHCP服务器提供:广播一个DHCP提供报文向客户作出响应;
  • DHCP请求:并向选中的服务器提供用一个DHCP请求报文
  • DHCP ACK:服务器用DHCP ACK报文证实所要求的参数。

路由选择算法

路由选择问题可归结为最短路径问题,算法按照是全局式的还是分散式可以分为全局式路由选择算法(链路状态算法)和分散式路由选择算法(距离向量算法),按照静态的还是动态分为静态路由选择算法动态路由选择算法,按照负载敏感的还是负载迟钝可以分为负载敏感算法负载迟钝算法

  • 链路状态算法:让每个结点向网络中所有其他结点广播链路状态分组,然后使用最短路径算法求出路径;
  • 距离向量算法:从相邻路由获取路由信息,然后使用Bellman-Ford公式更新路由表d_x(y) = \min_v|c(x,v) + d_v(y)|,然而距离向量算法存在无穷计数问题,需要毒性逆转技术解决。

两者的区别如下

链路状态算法 距离向量算法
报文复杂性
收敛速度
健壮性

链路层

链路层协议负责单一链路上的数据传输,可能的服务包括:成帧、链路接入、可靠交付、差错检测和纠正,链路层协议通常由网络适配器实现。

差错检测和纠正技术

  • 奇偶校验:数据加上校验位的1数量为偶数或者奇数,采用二维奇偶校验甚至可以实现纠错。
  • 检验和方法:将数据被作为一个k比特整数的序列处理,将这k比特整数加起来,并且用得到的和作为差错检测比特。
  • 循环冗余检测:对于d位数据,接收方用G(r+l位)去除接收到的d+r比特如果余数为非零,接收方知道出现了差错;否则认为数据正确而被接收。

交换局域网

链路层主要依赖MAC地址进行寻址,将MAC地址和IP地址对应的是ARP协议。每台主机或路由器在其内存中具有一个ARP表,这张表包含IP地址到 MAC地址的映射关系和一个寿命(TTL)值。当主机遇到未知IP地址时,构造并广播一 个ARP分组,与之匹配的主机回复响应ARP分组。

以太网协议的帧格式如下

  • 数据字段:以太网的最大传输单元为1500字节;
  • 目的地址源地址
  • 类型字段:得知将数据段的内容传递给哪个网络层协议;
  • CRC:检测帧中是否引入了差错;
  • 前同步码:该前同步码的前7字节的值都是10101010,最后一个字节是10101011。

链路层交换机维护交换机表完成转发和过滤,假定目的地址为xx 帧从交换机接口x到达:

  • 表中没有对于xx的表项,交换机向接口x无外的所有接口前面的输出缓存转发该帧的副本;
  • 表中有一个表项将xx与接口x联系起来,丢弃该帧即可;
  • 表中有一个表项将xx与接口y!=x联系起来,交换机通过将该帧放到接口y的输出缓存完成转发功能。

交换机表是自学习的:

  1. 交换机表初始为空;
  2. 对于在每个接口接收到的每个入帧,该交换机在其表中存储;
  3. 如果在一段时后,交换机没有接收到以该地址作为源地址的帧,就在表中删除这个地址.

链路层交换机的优点包括:消除碰撞、连接异质的链路和便于管理。链路层交换机相对于路由器的劣势包括:无法处理广播帧的循环、设备数量相关的ARP表,以及无法处理广播风暴。