计算机网络笔记

发表于 更新于 分类于 本文字数： 6.1k 阅读时长 ≈ 6 分钟

前言

计网和软工都放到下学期开学考了，于是笔记也顺理成章的推迟了。

镜子的世界里会有美丽的东西吗？
镜子的世界里会有快乐的事情吗？
镜子世界的我，像我一样摆着一副无聊的表情

我觉得计算机网络是非常迷人的，如果说总线IO代表着一个能独立运行计算机系统的内部通信，那么网络IO解决的是计算机系统之间的通信。为了能构建更庞大的网络，必须摆脱总线IO提供的各种便利。在物理介质上建立可靠可复用的通信，直面高延迟、丢包、重复包等情况。如何解决，怎么解决，为什么这么解决？这些都很有意思。

就算知道方法，也绝对不能去改变过去，绝不能将存在的可能性转变为既定的现实，未来是没有人能预测的，是无法重来的，正因如此人们才能接受各种痛苦，不幸与飞来横祸，迈步前进。——冈部伦太郎《命运石之门》

协议与划分层次

网络协议一般由三种要素组成。

  • 语法（数据与控制信息的结构和格式）
  • 语义（需要发出何种控制信息，完成何种动作和做出如何响应）
  • 同步（事件实现顺序的详细说明）

还记得一门计算机语言需要定义语法、语义以及实现语义的语言虚拟机。网络协议也差不多，不过支持语义的虚拟机变成了同步，因为协议一般并不进行多么复杂的可编程计算。而协议一般都默认有一个输入（上层给协议了什么）和输出（即输出在到什么上）（全双工同理）。所以一个图灵完备的虚拟机就退化为了如何在输入和输出之间进行同步。因此感觉状态机外加一个同步措施就能完整描述网络协议。

实际网络通常使用层次式网络协议结构。

  • 各层之间是独立的
  • 灵活性好
  • 结构上可分隔开
  • 易于实现和维护
  • 能促进标准化工作

各层所要保证的功能主要有以下一些

  1. 流量控制（发送端的发送速率必须让接收端来得及接受，比如波特率的控制）
  2. 差错控制
  3. 分段和重装（长数据包的拆分和重组）
  4. 复用和分用（demux和mux/编码器和译码器）
  5. 连接建立和释放（文件打开和关闭）

  1. 应用层-定义进程间通信和交互的规则，基本单位是报文（message）。
  2. 运输层-提供两台主机中进程间通信的通用数据传输服务。复用，分用在此解决。
  3. 网络层-负责为分组交换网上不同主机提供通讯服务。
  4. 数据链路层-将IP数据报外加控制信息封装成帧。一般初步解决差错控制，流量控制。
  5. 物理层-物理层上传输的单位是比特。某些物理传输媒介（如电磁波）需要进行一定的处理后才能变成比特流这种工作并不在物理层。

可见“进程”这个概念下到运输层，之后就消失了。“主机”这个概念下到网络层，之后就消失了。因此有一个非常有趣的事情，在数据链路层应该说“节点”而不是“主机”。在网络层则不应该提及进程。

而TCP/IP则把数据链路层和物理层合并为一层。整个应用层-传输层-网络层-链路层。

物理层

物理层解决的问题

  1. 物理层要尽可能地屏蔽掉物理设备和传输媒体，通信手段的不同，使数据链路层感觉不到这些差异，只考虑完成本层的协议和服务。（封装）
  2. 给其服务用户（数据链路层）在一条物理的传输媒体上传送和接收比特流（一般为串行按顺序传输的比特流）的能力，为此，物理层应该解决物理连接的建立、维持和释放问题。（维护并提供比特流信道）
  3. 在两个相邻系统之间唯一地标识数据电路（为信道命名）

物理层的定义

物理层的主要任务是确定与传输媒体的接口有关的一些特性

  1. 机械特性 指明接口的物理形状尺寸、引脚数目排列、固定和锁定装置等
  2. 电气特性 指明接口电缆的电压范围
  3. 功能特性 指明某引脚上出现某一电平的电压的意义
  4. 过程特性 指明对于不同功能的各种可能事件的出现顺序（状态机）

物理层下面的传输媒介

导引型传输媒体

指传输信号沿传输媒介传输的，常见的有双绞线、同轴电缆(以太网)，光缆。

非导引型传输媒体

特指传输信号在自由空间中传播的传输媒体，即无线电传输，简称无线传输。

信道复用技术

  • FDMA(Frequency Division Multiple Access)频分复用
  • TDMA(Time Division Multiple Access)时分复用
  • STDM(Statistic TDM)统计时分复用——设置一个集中器(concentrator)，每个用户维护一个buffer，不断循环buffers传输
  • WDM(Wavelength Division Multiplexing)波分复用——光的频分复用（光复用器-分用器）
  • CDM(Code Division Multiplexing)码分复用和CDMA(Code Division Multiple Access)码分多址。(利用异或和反异或组成的线性空间正交的码元和数据（0 1）异或来区分用户)

信道的指标

信号的平均功率(S)(S)

噪声的平均功率(N)(N)

信噪比(dB)=10log⁡10(S/N)(\text{dB}) = 10\log_{10}(S/N)

信道的极限信息传输速率C=Wlog⁡2(1+S/N) (bits/s)C=W\log_2(1+S/N)\space(\text{bits/s})

数据链路层

物理层提供比特流信道，数据链路层根据信道种类的不同有着不同的处理方式

  1. 点对点信道
  2. 广播信道

数据链路层解决的问题

  1. 封装成帧
  2. 透明传输
  3. 差错控制

数据链路层的定义

链路(link) 指的是从一个节点到另一个节点的物理线路且中间没有任何中间节点。

数据链路(link) 指的是使用数据链路层传输时，由不少于一个的链路组成了抽象的数据链路。

封装成帧

帧由三部分组成：帧首部、帧的数据部分和帧尾部。每一种数据链路协议都会规定帧的数据部分的长度上限(最大传输单元MTU(Maximum Transfer Unit))。

当数据由可打印的ASCII字符组成的字符串时，帧定界可以用不可打印ASCII字符——特殊的帧定界符来处理，即首部为SOH StartOfHeader(00000001)，尾部为EOT EndOfTransmission。

透明传输

透明传输即数据段可以为任意字符，让对上层的抽象和下层提供的抽象一致。具体的解决办法是添加一个转义字符ESC Escape(00011011)。即为C语言里的’'，在每个数据段出现的SOH/EOT/ESC前插入ESC。这样接收端只需要看到上一个字节没有ESC的SOH/EOT就能检测帧的开始/结束了。

差错检测

在帧首部或帧尾部插入校验码即可进行差错检测。接收端对帧数据进行同样的校验码计算，如果和传入校验码不一致就丢弃数据并回报上层。

CRC(Cyclic Redundancy Check)检测

TLDR:设输入数据的数字表示为AA，生成多项式的数字表示为PP，校验码R=(A×2⌊log⁡2(P)⌋−1)mod  Pmod  2⌈log⁡2(P)⌉R=(A\times 2^{\lfloor\log_2(P)\rfloor-1})\mod P \mod 2^{\lceil\log_2(P)\rceil}

PPP(Point to Point Protocol)

PPP被设计用来承载各种各样的网络层，由ISP为用户提供多种网络服务。

PPP协议设计目标

PPP协议的设计目标除了解决上述数据链路层的三种问题外，还有以下几点

  1. 简单（互操作性高）
  2. 承载多种网络层协议
  3. 运行于多种链路
  4. 检测链路连接状态
  5. 网络层地址协商
  6. 数据压缩协商

PPP协议由三部分组成，一个网络层数据报封装到串行链路的方法，链路控制协议（Link Control Protocol），网络控制协议NCP(Network Control Protocol)。

一个典型的PPP帧如下所示

1
2
3
       F |A |C |协议种类|信息部分|FCS|F
       7E|FF|03|       |      |   |7E
字节数  1 |1 |1 |2      |<=1500|2  |1

为了实现传输透明，对于异步传输(字符流)信息部分出现0x7E时需要添加额外的字符转义，具体规则如下

  1. 0x7E -> (0x7D,0x5E)
  2. 0x7D -> (0x7D,0x5D)
  3. ASCII控制字符a（x<0x20） -> (0x7D,a^0x20)

简记为

a为0x7E/0x7D/控制字符 -> (0x7D,a^0x20)

因此，接收端只需要检测0x7E即可

对于同步传输(一连串的比特连续发送)，因为0x7E具体体现为01111110，在信息段如遇连续的5个1则马上插入一个0。

以太网

以太网使用差分曼彻斯特编码，通常使用于局域网。传统意义上的局域网构型有星形，环形总线型三种。都为共享信道，需要解决为多用户合理方便的共享信道的问题。有两种大思路

  1. 静态划分
  2. 动态媒体接入，又称多点接入
  • 随机接入(碰撞问题)
  • 受控接入(令牌环局域网等方案)

对于总线型以太网，使用随机接入分类下的CSMA/CD(Carrier Sense Multiple Access with Collision Detection)，载波监听多点接入/碰撞检测算法来解决碰撞问题。

Multiple Access(多点接入)即总线型

Carriar Sense即载波监听，即不断监听当前信道状况，这导致CSMA/CD只能进行半双工通讯。

Collision Detection即碰撞检测，如果某个引脚上的电压超过阀值就认为发生了碰撞，立即停止并等待再发送。

等多久，以太网使用阶段二进制指数避退决定。

令τ\tau为端到端的最大通讯时延。基本退避时间(争用期)为2τ2\tau 。每次等待r=randint(0,2∗∗(min(重传次数,10))−1)r=randint(0,2**(min(重传次数,10))-1)。当超过16次时丢弃并向上报告。

以太网帧格式

1
2
3
                            | MAC帧   
       前同步码 | 帧开始定界符 | 目的地址 | 源地址 | 类型 |  数据  | FCS
字节数  7       |1           |6       |6      |2     |<=1500 |4
以太网特征
  • 可扩展的
  • 灵活的
  • 易于安装的
  • 稳健性好的

网络层

网络层的任务是统一不同的数据链路层，向上提供统一的网络服务。

而使用数据报服务而放弃虚电路则出于计算机能够进行更强大的差错处理，因此网络层不负责差错处理能使网络层设备更简单，更便宜，普及更快。

网络层解决的问题

  1. 地址分配
  2. 路由选择

网络的两个层面

  1. 转发源主机和目的主机之间所传送的数据（数据层面）
  2. 传送路由信息（控制层面）

1的过程可能会经过多个路由器

2的过程会根据路由选择协议所使用的路由算法，不断的交换路由信息分组来在路由器中维护路由表并导出转发分组而用的转发表。

网际协议 IP

IPv4

IPv4总长度<=65535B

IPv4 Packet-en

ICMP

ICMP被封装到IPv4数据内

ARP(Address Resolve Protocol)

IP地址->MAC地址

IPv6

IPv6扩展首部+数据部分不超过66535B

IPv6 Packet Header-en

路由选择协议

年轻人的第一个分布式算法

路由选择协议的核心就是路由算法，最终获得一个尽可能完成路由任务的路由表。一个理想的路由算法应具有如下的一些特点：

  1. 算法必须是正确的和完整的（在某一时刻沿着路由表分组一定能到达目的网络和目的主机）
  2. 算法应该尽量简单（路由器的性能有限，不应该给路由器增加太多的开销）
  3. 算法应能适应通信量和网络拓扑的变化
  4. 算法应具有稳定性（收敛）
  5. 算法应是公平的
  6. 算法应是“最佳”的
RIP(Routing Information Protocol)

RIP的思路是，定期将自己收到的相邻路由路由表信息更新到自己的路由表，如成功修改则向相邻路由发送自己的完整路由表。

  • 优点：好消息传播快
  • 缺点：坏消息传播慢
OSPF(Open Shortest Path First)
BGP(Border Gateway Protocol)

运输层

运输层的目的是实现应用程序级别的端到端通讯

运输层解决的问题

  1. 应用程序级别的复用和分用
  2. 差错检测
  3. 对于某些应用(TCP)，还需要实现可靠通信

对于TCP/UDP，使用端口进行复用和分用。端口号01023为熟知端口号，用于常见的服务器软件。102449151留给没有熟知端口号的应用。49152～65535留给客户端的源端口号。

UDP(User Datagram Protocol)

UDP的特点
  1. 无连接
  2. 尽最大努力交付
  3. 面向报文
  4. 没有拥塞控制
  5. 支持一对一、一对多、多对一、多对多的通信
  6. 首部开销小
UDP的首部格式

UDP的首部格式

UDP的校验为填充0到4的整数倍字节（包括校验码字段），然后计算二进制反码运算，写进校验码字段。

TCP(Transmission Control Protocol)

TCP的特点
  1. 面向连接
  2. 每个TCP通信只能是一对一的
  3. 可靠交付（无差错、不丢失、不重复且按序到达）
  4. 全双工
  5. 面向字节流
TCP发送/接受算法

发送端/接收端维护一个发送/接受窗口，在连接建立时发送端根据接收端窗口大小调整自己的窗口大小。

TCP发送端滑动窗口分类

发送端窗口内容可分为四类

  • 已经发送并得到对端ACK的
  • 已经发送但还未收到对端ACK的
  • 未发送但对端允许发送的
  • 未发送且对端不允许发送。

中间两部分数据称之为发送窗口，发送窗口维护超时重传。

接收端窗口内容可分为三类

  • 已接收
  • 未接收准备接收
  • 未接收并未准备接收

接收端发送ACK仅发送已接受的字节数。

控制滑动窗口的大小即可控制流量控制

TCP的首部格式

TCP的首部格式

超时重传时间的计算

TCP记录每个报文的往返时间RTT，每测量到一次RTT就更新下值

加权平均往返时间 RTTS=(1−α)×(RTTS)+α×(RTT)\text{RTT}_S=(1-\alpha)\times(\text{RTT}_S)+\alpha\times (\text{RTT})，α\alpha一般取1/81/8

偏差加权平均 RTTD=(1−β)×(RTTD)+β×∣RTTS−RTT∣\text{RTT}_D=(1-\beta)\times(\text{RTT}_D)+\beta\times |\text{RTT}_S-\text{RTT}|，β\beta一般取1/41/4

超时重传事件RTO(RetransmissionTime-Out)=RTTS+4×RTTD=\text{RTT}_S+4\times \text{RTT}_D

每重传一次RTO增大两倍

拥塞控制

拥塞信息高速公路堵车的情况下， 网络利用率显著降低

∑对资源的需求>可用资源\sum {对资源的需求} > 可用资源

总体上拥塞控制就是控制窗口大小，因此TCP使用拥塞控制算法调整拥塞窗口，最终窗口大小小于等于拥塞窗口。

拥塞控制算法有三种(下文数字单位均为报文段个数)

  • 慢开始 （初始设1，每收到一个RTT后增加1），最终呈现指数型增长。如果超时ssthresh=cwnd/2,cwnd=1
  • 拥塞避免 当cwnd>ssthresh(可能的=)时使用，按线性规律增长。如果超时ssthresh=cwnd/2,cwnd=1
  • 快重传 发送方收到接收方三次重复ACK后立即重传下一个报文
  • 快恢复 在快重传后cwnd=ssthresh=cwnd/2
TCP状态机

TCP状态机