复习¶

物理层¶

网络层级结构¶

网络由多个层级组成: 从上到下依次是application, transport, network, link, physical. application的协议有http, smtp, ftp; transport的协议有tcp, udp; network的协议有ip; link的协议有ethernet, wifi; physical层则涉及具体的硬件传输介质. ISO/OSI定义模型比上面的这个多两层, 额外包括presentation和session. presentation负责数据的interpretation和encryption, session负责对话控制, 检查点等. 实际上, 在互联网上, 如果需要这两层的功能, 是需要由application层来实现的, 例如HTTPS.

每个层都有自己封装的数据, application层的数据叫做message, transport层的数据叫做segment, network层的数据叫做datagram, link层的数据叫frame, physical层传输的是bits.

网络边缘, 物理媒介和网络核心¶

网络边缘是用户直接接触和使用网络的地方, 包括主机. 物理媒介是连接边缘设备和互联网核心的桥梁, 包括各种有线和无线的通信链路. 网络核心由大量相互连接的路由器组成, 负责在网络中转发数据包.

我们可以通过以下几种常见的方式接入网络: 住宅接入网, 机构接入网, 移动接入网. 其中最关键的指标就是带宽或者data rate, 单位是bit per second. 它就是我们常说的网速. 假设主机以一定的速率R(transmission rate)发送数据, 每个包的长度为L bits, 那么一个数据包的传输时间为L/R.

网络核心有两种工作方式: 一种是分组交换(packet switching), 另一种是电路交换(circuit switching). 分组交换是将数据分成一个个小包进行传输, 每个包独立选择路径, 适合突发性的数据传输; 电路交换是为通信双方建立一条专用的通信线路, 适合持续性的数据传输. 分组交换的核心是存储转发, 即一个路由器必须完整地接收到整个数据报并将其存储在内存中后, 才能开始将其转发到下一个链路, 它不能像水流一样边接受边转发, 例如, 对于一个经过一个路由器的路径(两段链路), 总延迟约等于2 * L/R(忽略其他延迟, 如路由器接受). 这是因为第一段L/R时间将数据包从源发到路由器, 路由器存储后, 再用第二个L/R时间将它转发出去. 例子: 一个7.5Mbits的包, 在1.5Mbps的链路上, 传输一跳就需要 7.5 / 1.5 = 5秒. 这种分组交换带来两个主要问题, 一个是排队延迟, 一个是数据包丢失, 这是因为, 两条高速率链路汇入一条低速率链路, 导致数据包到达地速度远远快于离开的速度, 导致他们需要在路由器的内存中排队等待发送, 如果数据包持续高速到达, 缓冲区会被填满, 新到达的数据包没有地方放, 只能丢弃. 分组交换的两个关键功能: 路由和转发. 路由是一个全局性的过程, 负责确定数据报从源到目标的整体最佳路径, 它通过运行路由算法来创建和维护一张网络地图; 转发是一个在单个路由器上发生的本地行为, 当一个数据报到达路由器的时候, 会查看头部信息, 然后根据这个信息查询本地转发表, 决定该数据包从哪个端口转发出去. 电路交换的核心是先预留再通信, 再真正的通信开始之前, 必须再源和目的地之间建立一条专用的路径, 这条路径上的所有资源都会分配给这次通信, 并且保留到通信结束.

网络延迟¶

网络延迟主要由四部分组成: 处理延迟, 排队延迟, 传输延迟和传播延迟. 分别是nodal processing delay,k queueing delay, transmition delay, propagation delay. 处理延迟是路由器收到数据报之后, 对其进行思考和处理所花费的时间, 检查数据包的头部是否有错误; 排队延迟是数据包在路由器的输出端口排队等待所花费的时间, 取决于当前网络的拥塞程度; 传输延迟是将数据包从路由器的内存中发送到输出链路所需的时间, 计算公式为L/R, L是数据包的长度(单位: bits), R是链路的传输速率(单位: bits per second); 传播延迟是数据包在链路上传播所需的时间, 计算公式为d/s, d是链路的长度(单位: meters), s是信号在链路中的传播速度(通常接近光速, 大约为2 x 10^8 meters per second). 排队延迟可以用流量强度来描述. 计算方式为La/R, 当流量强度接近0的时候, 意味着网络非常空闲, 排队延迟接近0; 当流量强度接近1的时候, 意味着网络非常拥塞, 排队延迟趋向于无穷大.

traceroute是一个非常好用的命令行程序, 可以显示从你的电脑到一个目标服务器所经过的路由路径, 并测量每一跳的延迟. 它巧妙地向目标地址发送一系列地ICMP回显请求报文, 并通过设置不同的TTL值来控制报文在网络中的生存时间. 每当一个路由器收到一个TTL值为1的报文时, 它会丢弃该报文并发送一个ICMP超时消息回源地址. 通过记录每一跳的响应时间, traceroute可以绘制出从源到目的地的路径图.

链路层¶

数据链路层的主要作用是负责将数据包(frame)从一个网络节点传输到下一个相邻节点的过程. 它只关系一跳之内的数据传输. 它提供的主要服务有: 将来自上层的datagram打包为帧, 并添加头部和尾部信息; 在堕胎设备共享同一个链路的时候, 控制谁可以何时发送数据, 避免冲突; 使用MAC地址来识别链路上的源设备和目标设备. 能够监测出数据在传输过程中是否因为干扰而出错, 如果监测到错误, 接收方可能会要求重发或者直接丢弃这个错误的帧. 更进一步, 接收方不仅能够发现错误, 还能直接修正一些比特位的错误, 无需重传.

链路层的功能实现放在网卡中, 网卡是一块插在电脑主板上的硬件, 负责数据链路层和物理层两层的功能. 网卡之间的通信: 发送端从上层接受一个数据报, 将其封装为一个帧, 添加用于错误监测的比特位如CRC(通常添加在尾部), 控制流信息等, 通过物理层发送出去; 接收端接收到一个帧, 检查帧中是否有错误, 如果没有错误, 就从帧中提取出数据报, 将数据报传递给上层.

奇偶校验🌟¶

分为两种, 一种是单比特奇偶校验, 1的总数永远是偶数(如果1的个数是奇数, 那么校验比特就是1; 如果是偶数, 那么校验比特就是0). 另一种是二维就校验, 将数据按行和列排列, 每行和每列都添加一个校验比特, 使得每行和每列中1的个数都是偶数(就是每一行和每一列都有一个单比特奇偶校验).

CRC🌟¶

进制转换¶

十进制转二进制: 举个例子, 将13转为二进制:

1. 13 ÷ 2 = 6 ... 余 1
2. 6 ÷ 2 = 3 ... 余 0
3. 3 ÷ 2 = 1 ... 余 1
4. 1 ÷ 2 = 0 ... 余 1

从下往上读取余数, 得到 1101. 所以, (13)₁₀ = (1101)₂.

十进制转十六进制数: 也是类似的, 将283转为十六进制:

1. 283 ÷ 16 = 17 ... 余 11 (即 B)
2. 17 ÷ 16 = 1 ... 余 1
3. 1 ÷ 16 = 0 ... 余 1

从下往上读取余数, 得到 11B. 所以, (283)₁₀ = (11B)₁₆. 注意, A对应的是10, B对应的是11, 以此类推, 一直到F对应的是15.

CRC算法步骤¶

要了解CRC, 我们就先要了解模2运算. 其规则而是所有的运算都没有进位或者借位. 加法和减法都是完全相同的操作, 等同于XOR, 什么是异或, 就是相同是0, 不同是1. 例如11+11=00, 10+11=01, 01+11=10, 00+11=11, 1+1=0, 1+0=1, 0+0=0. 11*100=11*2^2=1100(相当于左移两位), 11*11=11*10+11*1=110+11=101. 除法里面的减法也是模2减法, 也就是XOR操作.

CRC的操作: 假设数据是D, 我们选取一个Generator G, 它的长度为r+1位, 我们将D左移r位, 得到D*2^r, 然后除以G, 得到余数R, 长度为r, 将这个余数R拼接到D的后面, 形成最终发送的数据T = D*2^r + R. 接收方收到T后, 用G去除T, 如果余数是0, 那么说明数据没有错误; 如果余数不是0, 那么说明数据有错误. 可以使用下面这张图表示:

多路访问协议¶

多台设备共享同一条通信线路, 我们如何避免他们打架呢? 我们可以用Multiptle Access Protocol来协调通信. 现实世界中的MAP可以分为三种: 1. 信道划分, 将信道预先切为固定的小份, 每个设备分到一个专用, 可以按照时间也可以按照频率(FDMA, TDMA). 2. 随机接入: 不预先划分资源, 谁想发就发, 如果发生冲突, 就各自后退一步, 随机等一小段时间后重试; 3. 轮流协议: 设备们排队轮流使用信道, 通过传递一个叫做令牌的信物, 只有拿到令牌的设备才能发送数据.

这里, 我们主要想要了解的是随机接入.

随机接入¶

随机接入协议又分为: ALOHA(最简单的随机接入协议, 设备一有数据就发送), Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA.

Slotted ALOHA🌟¶

当一个节点有数据要发送的时候, 它会等到下一个时间槽的开始, 然后将整个数据帧发送出去, 如果没有冲突, 那么传输成功. 如果发生冲突, 传输失败必须重传这个帧. 发生冲突后, 节点不会立即在下一个时间槽重传, 相反, 对于后续的每一个时间槽, 节点都会以一个预设的概率p来决定是否重传, 这个带有随机性的重传过程会一直持续下去, 直到该数据帧成功发送为止.

那么如何计算成功传输的效率呢? 效率 = 成功传输的时隙 / 全部时隙. 假设有N个节点, 每个节点在一个时隙内发送数据的概率是p. 那么, 在某一个时间槽内, 尝试发送数据的节点的数量X符合二项分布B(N, p). 那么, 效率就是X=1的概率. 例如, 有20个terminal, 每个terminal传送一个包的概率是0.04, 那么效率就是20*0.04*(1-0.04)^19=0.37.

如何计算每个节点平均需要等多久才能发送呢? 每个节点在某个时间槽成功发送的概率是p*(1-p)^(N-1). 那么, 平均需要等1/(p*(1-p)^(N-1))个时间槽才能成功发送一个包. 例如, 还是上面的例子, 那么平均需要等1/(0.04*(1-0.04)^19)=54.35个时间槽才能成功发送一个包.

CSMA🌟¶

CSMA和ALOHA一样, 也是属于一种随机接入协议. 它的核心思想是, 在发送数据之前, 首先监听信道是否空闲, 如果信道是忙的, 那么等待一段时间后再监听; 如果信道是空闲的, 那么立即发送数据.

它有三种分类: 1. 1-persistent CSMA: 一旦发现信道空闲, 就立即发送数据, 若多个设备同时等着, 一旦信道空闲就会一起发送, 容易冲突; 2. non-persistent CSMA: 发现信道忙就等待一段随机时间后再监听, 冲突概率低, 但信道利用率也低; 3. p-persistent CSMA: 主要用于时隙系统, 发现信道空闲后, 以概率p发送数据, 以概率1-p等待下一个时隙.

CSMA/CD🌟¶

因为传播延迟, CSMA仍然可能会发生碰撞, 想象A和B在会议室的两端, A先开始说话了, 但是声音传到B那里需要一点时间, 就在这个短暂的延迟里面, B以为没人说话, 所以他也开始说了. 结果, 这两个人的声音就在半路撞到了一起.

CSMA/CD是一种更加高级的机制, 不仅在发言之前要听, 而且在自己说话的过程中, 还要竖起耳朵听有没有人和自己同时说. 他能够快速监测到碰撞, 一旦监测到碰撞, 立刻中止传输, 从而减少信道时间的浪费. 有线网络可以做到同时发送和接受信号, 通过比较自己发出去的信号和线缆上实际听到的信号是否一致, 就能判断是否发生碰撞, 如果不一致, 说明有别人在发, 就发生了碰撞. 无线网络不能使用CSMA/CD, 因为无线节点在发送信号的时候, 自身的发送功率会非常厉害, 会完全盖过从远处传来的微弱信号. 因此, 他就无法监测碰撞.

流程:

1. 帧的生成: NIC从网络层收到数据报, 并把它封装成链路层的数据帧
2. 帧听信道并决定是否发送: NIC先帧听信道是否空闲, 如果信道空闲, 就立即开始发送帧, 如果信道忙碌, 就等到信道空闲再发送, 这里使用的是1-persistent策略
3. 传输结果: 如果在整个传输过程中, NIC没有检测到其他节点的传输, 那么这帧就发送成功, NIC的工作完成.
4. 冲突检测和jam信号: 如果NIC在传输过程中检测到别的节点也在传输, 则发生冲突, NIC立即中止发送, 并向信道发送一个jam signal, 大约48bit, 确保所有节点都能感知到冲突, 避免有的节点还以为信道空闲
5. 二进制指数退避: 冲突发生后, NIC不会立刻重发, 而是等待一段随机时间再尝试, 防止再次冲突. 第m次冲突后, NIC会从{0, 1, 2, ..., 2^m-1}中随机选择一个数k, 然后等待k*512bit times后再进行重试, 随着冲突次数m的增加, 等待范围会指数级变大, 给网络流出更多的时间环节拥塞

效率公式🌟:

效率 = 1 / (1 + 5 * t_prop / t_trans)

代表意义: t_prop是传播延迟时间, t_trans是传输时间. 值代表了网络中用于有效数据传输的带宽比例.

举个例子:

有 N 台计算机连接到一个长度为2公里的共享介质(一根电缆)上. 该共享介质的最大信道速率为 10 Mbps. 每台计算机每秒产生10个数据帧, 每个帧的大小为1000字节. 信号在介质中的传播速度是 2 x 10⁸ 米/秒. 问题是: 如果该网络使用 CSMA-CD 协议, 它最多能支持多少个节点(计算机)?

首先计算t_prop = 距离 / 传播速度 = (2 × 1000) / (2 × 10⁸) = 10/1000000 秒 = 10 微秒. 然后计算t_trans = 帧大小 / 信道速率 = (1000 × 8) / (10 × 10⁶) = 8000 / 10,000,000 秒 = 0.8 毫秒 = 800 微秒. 注意, Mbps = 10^6 bps. 然后, 根据我们的公式计算CSMA/CD的效率: 效率 = 1 / (1 + 5 * t_prop / t_trans) = 1 / (1 + 5 * 10 / 800) = 1 / (1 + 0.0625) = 1 / 1.0625 ≈ 0.9412. 这意味着, 由于存在延迟传播, 网络的最大容量(10 Mbps)中的大约94%能被真正用来传递有效数据. 由于每一台计算机每秒产生10个数据帧, 每个帧的大小为1000字节, 因此每台计算机每秒需要的带宽为: 10 帧/秒 * 1000 字节/帧 * 8 位/字节 = 80,000 位/秒. 因此, 网络中最多能支持的计算机数量为: 最大有效带宽 / 每台计算机所需带宽 = (10,000,000 位/秒 * 0.9412) / 80,000 位/秒 ≈ 117.65. 因为计算机数量必须是整数, 所以网络最多能支持117台计算机.

以太网¶

拓扑结构¶

• 总线型拓扑: 所有的节点都连接到一根同轴电缆上, 共享整个信道, 所有的节点都在同一个碰撞域里, 任何两台机器同时发送数据会导致碰撞, 影响整个网络的性能.
• 星型拓扑: 所有节点都连接到一个中心交换机上, 交换机是智能设备, 它会为他通信双方建立一个临时的专用通道, 数据只会被转发到目标端口, 而不是广播到所有的端口. 因此, 节点之间通常不会发生碰撞, 大大提高了网络效率.

MAC地址¶

IPv4地址32位, 属于网络层地址; MAC地址, 也叫做局域网地址, 48位, 属于数据链路层地址, 作用是在一个局域网的内部, 将数据帧从一个物理上连接的网卡送到另一个物理上连接的网卡. 这个地址在网卡出厂被烧录在ROM, 是全球统一的.

MAC地址的分配和管理由IEEE统一负责, MAC地址有两种类型, Universally Administered Address (UAA)和Locally Administered Address (LAA). 第一个地址是最常见的一种, 由设备制造商生产的时候唯一地分配, 并烧录到设备中. 本地管理地址是由网络管理员手动指定地, 它的作用是覆盖设备中原来烧录好的那个全局地址. MAC地址是可以携带的, IP地址是不可以携带的.

MAC地址有三种类型: 一个是单播, 一对一通信, 目标地址是网络上某个特定网卡的MAC地址; 另一个是广播, 是一对所有通信, 目标地址是一个特殊的地址: FF-FF-FF-FF-FF-FF, 代表网络上的所有节点; 还有一种是组播, 一对多通信, 目标地址是一个特定的组播地址, 代表一组节点.

Hub是一个用来连接多台计算机的中心设备, 它是一个非常简单的中继器, 当一个信号从Hub的某个端口进来的时候, Hub会把这个信号不加分辨地方大, 然后复制并广播到所有其他端口. 由于这种广播的属性, 所有连接到Hub的设备相当于共享一根总线, 处于同一个冲突域, 任何两台设备同时发送数据都会导致冲突, 影响整个网络环境.

交换机是一种更加智能的设备, 交换机会学习并记录每个端口后面连接的是哪个MAC地址, 当一个数据帧进来的时候, 交换机会检查它的目标MAC地址, 然后只将该帧转发到对应的目标端口, 而不是广播到所有的端口. 交换机具有并行传输能力, 每个主机都会通过一根独立的网线直连到交换机, 交换机内部有缓存帧, 每个连接到交换机的链路都是一个独立的冲突域. 交换机可以同时处理多对主机之间的通信, 没有干扰. 每个交换机内部都有一个交换表, 表的内容是(主机的MAC地址, 接口号, 时间戳), 比如A'的MAC地址->接口4, 这样当A要发送给A'的时候, 交换机直接查表, 从接口4转发就行. 表项是通过自学习的, 当主机发送一个帧的时候, 交换机会看它的源MAC地址, 然后在交换表记下"源MAC->来的端口号", 这样交换机就学会了这个主机在哪个接口. 如果交换机不知道目标MAC在哪个端口, 它会Flood(泛洪), 把帧广播到所有的端口(除了源端口), 等目标主机回应的时候, 交换机就学会了它的位置.

网络层¶

网络层方负责将传输层传下来的segments封装为datagram. 它存在于每一个主机和路由器中. 路由器会检查通过它的每一个IP数据报的头部字段, 决定如何转发. 网络层的两个关键的功能就是转发和路由, 转发是一个局部的操作, 决定将数据包从路由器的输入端口转到合适的输出端口; 路由是一个全局的过程, 决定数据包从源到目的地的所有经过的路径. 路由算法负责计算通过网络的端到端路径, 它决定了数据包应该怎么走. 路由算法计算出的结果被用来填写本地转发表路. 由算法决定表的内容, 转发表决定数据包的实际去向.

IP地址¶

IP地址是一个32位的标识符用于标识主机或路由器的接口他使用点分十进制表示. 接口是主机与物理电路之间的连接点. 路由器通常有多个接口, 每个接口都有一个IP地址. 主机通常只有一个接口, 有一个IP地址. IP地址是关联在接口上的, 而不是关联在整个设备上的. 交换机和集线器通常是没有IP地址的, 他们对网络层是透明的.

早期的IP地址分配策略. 根据网络规模的大小加IP地址分为不同的类别. 分类的依据是地址开头的几位比特. 主要有a类地址, B类地址C类地址D类地址, 4种. 到了1990年代这种分类编制暴露出严重的缺陷导致了互联网危机, 这是因为互联网发展得太快这种地址分类结构不够用了, 为了解决上述的危机工程界提出了短期和长期的解决方案, 短期的解决方案旨在延长IPV4的寿命, 使用CIDR这种子网掩码的形式灵活的划分网络的大小按需分配减少浪费, 或者是使用Nat网络地址转换技术允许企业内部使用私有地址对外只使用一个或少量公网IP. 长期解决方案彻底解决地址不够用的问题, 使用IPV6引入全新的协议地址长度从32位扩展到128位提供了几乎无限的地址空间.

转发表🌟¶

如果路由器的转发表里为每一个目的ip地址都存一行记录, 那么这个表会有四十亿行这样的记录, 这样的表太大了, 查表速度慢, 路由器跑不动. 解决方案是使用地址范围, 而不是记录单个IP, 而是记录一种连续的IP地址, 只要目的地址落在这个范围内, 就使用这一行记录. 这被称为路由聚合. 转发表在匹配的时候采用的规则是"最长前缀匹配原则", 即当一个目的地址于转发表中的多个表项匹配的时候, 路由器会选择掩码最长的那个表项作为转发的一句.

网络层的核心组件包括: IP协议, 负责寻址和数据报格式; 路由协议, 如RIP, OSPF, BGP, 他们负责路径选择, 在后台运行, 计算最佳路径, 并将结果写入转发表; ICMP协议, 负责错误报告和信令. IP数据报地址, 这个不太用知道, 只要知道IP首部占用 20Bytes 就行了.

IP数据报的分片: 不同链路的MTU(maximum transmission unit, 最大传输单元)不一样, 如果一个IP数据报比链路MTU要大, 就必须拆分为多个小片段, 否则无法通过. 分片过程: 在中间的路由器进行, 输入是一个大的数据报, 输出是多个小数据报(每个都带有独立的IP首部), IP首部里面有标识符(identifier), 片偏移(fragment offset), 标志位(MF)用来标记这些小片段属于同一个原始数据报. 重组过程: 重组只会发生在最终目的主机, 中间的路由器不会拼回原始数据报, 目的主机收到所有片段之后, 按照offset排序, 利用identifier判断它们属于同一份数据报, 最终还原出原始数据报. 举个例子, 一个4000字节的数据报, 经过一个MTU为1500字节的链路的时候, 会被拆为3个段, 第一个段包含20Bytes的IP首部和1480Bytes的数据, 第二个段包含20Bytes的IP首部和1480Bytes的数据, 第三个段包含20Bytes的IP首部和1020Bytes的数据. 其中, 第一个段的offset是0, MF=1; 第二个段的offset是1480/8=185, MF=1; 第三个段的offset是2960/8=370, MF=0(最后一个片段).

CIDR🌟¶

注意, 这张图里面有6个子网.

200.23.16.0/23表示的是其子网掩码为255.255.254.0. 前23位网络号, 对应的二进制位是1, 后9位主机号, 对应的二进制位是0. 包含的IP地址范围是: 从200.23.16.0到200.23.17.255, 这是因为200.23.16.0的二进制表示为11001000 00010111 00010000 00000000, 将后9位全部置为1, 得到的最大地址是11001000 00010111 00010001 11111111, 即200.23.17.255.

路由聚合¶

互联网上的路由器如果不做优化, 路由表就会大到无法处理, 为了缩小路由表, 我们需要使用层级化的结构, 例如, 去往 200.23.16.0/23 的数据包 -> 走接口 1. 去往 200.23.18.0/23 的数据包 -> 还是走接口 1. 为了省事, 直接存一条: 去往 200.23.16.0/20 -> 走接口 1.

路由聚合遵循最长前缀匹配, 例如像下面的这种情况, 200.23/18.0/23走的是下面的接口2:

DHCP¶

我们可以通过两种方式获取IP地址, 一种是hard coded, 另一种是DHCP. 它允许主机在加入网络的时候, 自动从服务器中获取IP地址, 而不需要管理员手动去每一台电脑上配置. 它分为4个核心步骤, discover, offer, request, ack.

1. DHCP Discover: 主机发送一个广播消息, 寻找DHCP服务器. 这个消息包含主机的MAC地址, 以便服务器识别.
2. DHCP Offer: DHCP服务器收到Discover消息后, 会为主机分配一个可用的IP地址, 并发送一个Offer消息给主机. 这个消息包含分配的IP地址, 子网掩码, 默认网关等信息.
3. DHCP Request: 主机收到Offer消息后, 会选择其中一个Offer, 并发送一个Request消息给服务器, 表示接受这个IP地址. 其他DHCP服务器收到这个Request消息后, 会将之前为该主机保留的IP地址释放回地址池.
4. DHCP ACK: DHCP服务器收到Request消息后, 会发送一个ACK消息给主机, 确认IP地址的分配. 主机收到ACK消息后, 就可以使用这个IP地址进行通信了.

DHCP中包含网关, DNS服务器, 子网掩码等信息. DHCP是一个应用层的协议, 它运行在UDP之上, 使用67端口和68端口. DHCP Discover和Request消息是广播的, 因为此时主机还没有IP地址; DHCP Offer和ACK消息是单播的, 因为服务器已经知道主机的MAC地址, 可以直接发送给它.

NAT🌟¶

NAT的好处:

• 只需要从ISP那里申请一个地址, 就可以供家里无数台设备使用, 极大缓解了IPv4地址枯竭的问题.
• 可以随意改变局域网内设备的IP, 不需要通知外界
• 如果你换了宽带运营商, 你的公共IP地址会变, 但是你家里的打印机, 电脑的私有IP不需要改变
• 安全性: 互联的黑客只能看到路由器的公共IP, 但是无法直接看到内网的IP

具体是实现细节:

1. 发出请求: 主机10.0.0.1端口3345想要访问外部的Web路由器, 它发送数据包给路由器
2. NAT router拦截这个数据包, 生成一个新的端口号5001, 它将源 IP 改为公共 IP 138.76.29.7, 源端口改为 5001. 它在 NAT 转换表 中写下一行记录: 138.76.29.7:5001 ↔ 10.0.0.1:3345. 现在, 数据包发往互联网.
3. Web 服务器回复数据. 它只知道发给 138.76.29.7:5001.
4. 路由器收到回复. 它查看端口号 5001. 它查表发现: 哦, 5001 对应的是内部的 10.0.0.1:3345. 它将目的地址改回 10.0.0.1:3345, 并转发给主机.

一些争议:

1. 越权处理: 路由器本该只处理第 3 层(网络层 IP), 但 NAT 强行修改了第 4 层(传输层 端口号)的信息.
2. 破坏了"端到端"原则: 互联网的设计初衷是两台主机直接对话, 中间设备不应篡改数据. NAT 打破了这一点.
3. 妨碍 P2P 应用: 如果你在 NAT 后面, 外面的电脑无法主动连接你(因为你没有公网 IP). 这让 P2P 下载(如 BitTorrent)或 VoIP 通话的设计变得复杂(需要穿透技术).
4. 只是权宜之计: 批评者认为, 地址短缺的根本解决之道应该是 IPv6, 而不是用 NAT 这种"创可贴"来修补 IPv4.

NAT穿透:

1. 第一种方案是静态配置, 通常被称为端口转发, 网络管理员可以手动配置路由器, 让外部的端口和内部的端口之间有一个固定的映射关系
2. 第二种方案是中继: 内网的 NAT 客户端主动连接一个公网上的中继服务器 (Relay Server). 外部客户端也连接这个中继服务器. 中继服务器在两者之间搭桥, 转发所有数据包.

IPv6¶

IPv4 只有 32 位地址空间(约 40 亿个), 已经快被分完了. IPv6 使用 128 位地址空间, 提供了几乎无限的 IP 地址. IPv6 的头部格式被简化了, 使得路由器处理数据包的速度更快. 头部设计更好地支持实时应用(如语音, 视频), 确保重要数据优先传输. 头部固定为 40 字节. 这让硬件处理变得非常简单高效(不用像 IPv4 那样去计算头部到底有多长). 路由器不再负责把大包切成小包. 如果包太大, 路由器直接丢弃并通知发送者. 这大大减轻了路由器的负担.

由 8 组 数字组成, 每组 16 位 (4个十六进制数字). 组与组之间用冒号 (:) 分隔. 每组开头的 0 可以不写. 例如 0db8 变成 db8. 如果有一连串的 0 组, 可以用双冒号 :: 代替. :: 在一个地址中只能使用一次(否则无法还原中间到底有多少个 0)

IPv4过度到IPv6: 互联网太大了, 我们不可能命令全世界所有人在同一天(Flag Day)把所有的路由器都升级成 IPv6. 因此, 在这个漫长的过渡期(可能持续几十年), IPv4 和 IPv6 必须共存. 并非所有路由器都能同时升级. 网络中会出现"混搭"的情况: 有的路由器只懂 IPv4, 有的懂 IPv6. 挑战: 两个 IPv6 的孤岛(现代网络)如何穿过一片 IPv4 的海洋(旧网络)进行通信? 将整个 IPv6 数据报(包括头部和数据)当作载荷 (Payload), 塞进一个 IPv4 数据报的数据部分.

路由算法🌟¶

我们将\(C_{ij}\)定义为\(i\)和\(j\)之间的成本, 如果\(i\)和\(j\)不相连的话, 成本是\(\infty\).

路由算法分为两种: link state algorithm, 每个路由器都有一份完成额topology, 每个路由器都可以独立的运行最短路径算法, 如Dijkstra, 如OSPF. distance vector algorithm, 每个路由器只知道直接连接的邻居和到邻居的链路代价, 路由器之间交换信息, 逐渐计算出到所有目的地的最短路径, 如RIP.

Link State算法¶

这种算法会干两件事情, 第一件事情是每个节点都会得到一张完整的网络拓扑图; 第二件事情是每个节点都会使用Dijkstra算法计算出从自己到所有其他节点的最短路径.

第一件事情: 每个节点会周期性地向网络中的所有节点发送Link State Advertisement(LSA), 里面包含它的邻居列表和到每个邻居的链路代价. 每个节点收到LSA后, 会更新自己的拓扑数据库, 并将这个LSA转发给其他节点(除了发送者). 这样, 所有节点最终都会得到一张完整的网络拓扑图. 这个叫做flooding(泛洪).

第二件事情: 每个节点使用Dijkstra算法计算出从自己到所有其他节点的最短路径. 见PPT16-26🌟🌟. 核心思想就是找到离当前的tree的只差一条的节点中离origin最近的节点, 加入tree.

对链路故障的反应: 当网络中的一条链路断开的时候, 路由器会立即将该链路的距离设置为无穷大, 并向全网广播一个更新信息, 所有路由器收到这个消息之后, 会立即更新自己的链路数据库, 并重新计算最短路径, 这个恢复过程非常迅速. 为了防止过时的更新信息造成的干扰, 每个更新包都会加上一个时间戳序号, 路由器只处理比自己记录更新的信息.

在一个有 n 个节点的网络中, 其基础实现的复杂度是 O(n²), 因为每次迭代都需要检查所有节点.

Distance Vector算法¶

这个算法的精髓就是要列出\(n\)的距离等式. 例如: 对于下图这样的网络, 我们有:

• \(D_1 = \min\{3+D_2, 2+D_3, 5+D_4\}\)
• \(D_2 = \min\{3+D_1, 1+D_4, 4+D_5\}\)
• \(D_3 = \min\{2+D_1, 2+D_4, 1\}\)
• \(D_4 = \min\{5+D_1, 1+D_2, 2+D_3, 3+D_5\}\)
• \(D_5 = \min\{4+D_2, 3+D_4, 2\}\)

列出上面的这些等式之后, 我们就可以开始算法, 这是一个消息传播的过程. 详情见36-40. 我们的目标就是要一直迭代, 直到上面等式中的所有部分都被解出.

对链路故障的反应: 链路故障后, 收到影响的节点会排除那条链路(也就是从Bellman-Ford等式中去掉那条链路对应的项), 然后重新计算距离. 这样可能导致一个问题, 叫做counting to infinity problem, 例如下图:

可以通过毒性反转来解决这个问题, 也就是节点B告诉节点A: "去往节点Z的最佳路径是经过我. "节点A收到后, 更新了自己的路由表. 当节点A向邻居B广播路由表时, 它会特意包含一条去往Z的路由, 但成本(metric)设置为无穷大(例如, 在RIP协议中是16). 这样, B收到信息后就会明确知道: "绝对不能通过A去往Z. "

分层路由¶

之前的路由算法假设网络是扁平的, 但是在现实中, 这是不可行的, 因为互联网有6亿个地址, 路由表无法存储所有地址, 路由表本身信息交换就会占满所有的带宽, 互联网是网络的网络, 每网络的管理员都希望控制自己的网络. 解决方案就是分层路由, 将网络划分为不同的层次, 如自治系统(AS)内部路由和AS间路由, 这样可以减小路由表大小, 允许各组织独立管理, 提高路由的效率.

分层路由的原理: 将路由表聚合为自治系统(AS)区域, 同一AS内的路由器运行相同的协议, 不同AS可以使用不同的内部路由协议. 位于AS边缘的特殊路由器, 连接到AS的路由器. 我们之前已经介绍过了AS内部路由(intra-AS)协议OSPF和RIP.

Intra-AS路由协议¶

之前我们已经介绍过Intra-AS用的两种算法. RIP用的是Distance Vector算法, OSPF用的是Link State算法. 这里我们再补充一些细节.

• RIP: RIP是一种intra-AS协议, 用于在单个自治系统内交换路由信息, 它基于Distance Vector算法. 使用跳数作为路径成本, 即经过路由器的数量, 每条链路的成本为1, 最大跳数为15, 16表示不可达. 路由器大约每30秒就向自己的邻居广播自己的路由表信息. 路由器收到邻居的路由信息后, 会更新自己的路由表, 为每个目的地选择跳数最少的路径. 如果一个路由器在180秒内没有收到某个邻居的消息, 它会认为这个邻居或者那条链路失效. 为了防止路由环路问题, RIP使用了毒性反转技术, 即当一条路径失效的时候, 路由器会向邻居广播该路径的跳数为16, 以快速阻止其他路由器使用这条无效路径. RIP是一个在应用层实现的协议, 通常由一个名为route-d的后台守护进程管理, 它使用UDP来传输路由更新数据包.
• OSPF: OSPF是一种intra-AS协议, 它是一个公开的协议, OSPF基于Link State算法. 每个路由器都会向网络中的其他所有路由器泛洪自己的链路状态信息, 因此, 每个路由器都能建立一个完整的网络拓扑图. 基于这个完整的网络拓扑图, 每个路由器使用Dijkstra算法独立计算出到所有目的地的最短路径. OSPF报文直接封装在IP数据包中, 不使用TCP或者UDP. OSPF具有以下的特性: 安全性 (Security): 所有 OSPF 消息都经过认证, 可以防止恶意攻击. 负载均衡 (Multiple Paths): 允许使用多条成本相同的路径进行负载均衡, 而 RIP 只能使用一条. 服务类型 (Type of Service, ToS): 可以为同一条链路针对不同的服务类型设置不同的成本. 例如, 为实时性要求高的流量设置一个成本, 为尽力而为的流量设置另一个成本. 组播支持 (Multicast Support): 集成了对单播和组播的支持 (MOSPF). 分层路由 (Hierarchical Routing): 在大型网络中, OSPF 可以划分为多个区域 (Area), 实现分层路由, 提高了可扩展性和效率.

Inter-AS路由协议🌟¶

BGP是互联网中用于在不同的大型网络之间交换路由信息的协议, 它被称为将互联网粘合在一起的胶水. 互联网由无数个独立的自治系统组成, 在AS内部, 路由协议通常只关心效率, 但是在AS之间, 路由决策更加负责, 需要考虑policy, 例如商业合同, 成本或者安全规定.

eBGP和iBGP¶

BGP如何工作呢? BGP路由器之间会建立连接, 交换路由信息, 一个AS会向另一个AS通告它能到达的网络地址, 并承诺可以将数据包转发到这些地址, eBGP用于在不同的AS之间交换路由信息, iBGP用于将从外部学到的路由信息, 在同一个AS内部同步给所有路由器. 比如说, 在下面的这个拓扑图中:

AS3会将左侧的这个"other networks"的可达性信息(前缀)通过eBGP从3a传递给1c. 1c会用iBGP将这个信息传递给AS1内的其他路由器, 1b会用eBGP将这个信息传递给AS2的2a. 2a会用iBGP将这个信息传递给AS2内的其他路由器...

路由通告¶

一个BGP路由通告(advertisement)的核心内容包含三个部分: 前缀 (Prefix), AS路径 (AS-PATH) 和 下一跳 (NEXT-HOP). 前缀是目标网络的地址范围(例如网络C); AS路径是一个AS编号列表, 它记录了该通告从源头传播过来所经过的路径, 从而指明了数据包要想到达目标所需经过的AS序列; 下一跳则是将数据包发往AS路径中第一个AS的入口路由器的IP地址. 因此, 如果一条通告包含前缀C, AS路径 [AS1, AS3] 和下一跳地址 1b, 它的完整含义是: "要想到达网络C, 你需要沿着先经过AS1再到AS3的路径走, 而你当前的第一步就是把数据包发给路由器1b. "

策略¶

• 服务商
  • 向客户: 宣布它知道的所有路由
  • 向服务商: 宣布它自己的客户路由
• 客户
  • 向服务商: 只宣布自己的路由

BGP路由选择策略¶

大致由4种方法:

• 本地优先级: 首先选择本地优先级(Local Preference)最高的路径, 这是一个人为设置的值, 用于指示首选路径.
• AS路径长度: 如果本地优先级相同, 选择AS路径(AS-PATH)最短的路径, 这样可以减少经过的自治系统数量.
• 下一跳的开销: 如果AS路径长度也相同, 选择到下一跳(NEXT-HOP)开销最低的路径, 这通常基于内部路由协议计算出的成本. 这个就是热土豆路由.
• 其他标准: 如果以上标准都相同, 则可以使用其他标准,

转发表的设置¶

一个路由条目是如何最终进入到路由器的转发表种的, 这是由两个因素决定的, 一个是inter-AS路由的结果, 另一个是intra-AS路由的结果.

1. 首先, 路由器得知远方的存在. 路由器必须知道这个目标网络的存在. 对于不在自己AS内部的网络, 这个信息是通过BGP学到的. AS1中的路由器1c会从它的邻居AS(如AS3)那里收到一个BGP消息. 这个消息就像一张明信片, 包含了到达某个目标网络的完整信息:

   • 目标网络的前缀 (Prefix), 例如 138.16.64/22.
   • AS路径 (AS-PATH), 这条消息经过的AS列表, 例如 [AS3, AS131]. 这告诉1c数据包需要经过的AS路径.
   • 下一跳 (NEXT-HOP): 路径上下一个AS的入口路由器的IP地址, 例如 201.44.13.125(也就是AS3中路由器3a的地址).

   此时, 1c可能从不同的邻居(比如从AS2也)收到关于同一个目标138.16.64/22的路由信息. 这就引出了下一步: 选择最佳路径.

2. 路由器决定最佳路径和出口: 如果1c收到了多条去往同一个前缀的BGP路由, 它必须根据一套严格的规则选出唯一一条最佳路由. 这个选择过程我们假设它通过热土豆选择的. 我们选择下一跳为201.44.13.125. 现在1c面临一个新问题: 我知道了下一个目标是IP地址201.44.13.125, 但在我的AS1内部, 我该从哪个物理接口把数据包发出去才能到达它呢? 这时, OSPF(或其他内部网关协议)就派上用场了. 1c会在AS1的内部网络中, 使用OSPF计算到达201.44.13.125这个IP地址的最短内部路径. OSPF会告诉1c: "要想到达那个地址, 你应该从你的3号接口发出去, 下一站是路由器1d. "

3. 将最终结果填入转发表: 从BGP得知: 目标是 138.16.64/22. 从OSPF得知: 要去这个目标, 需要从本地的 3号接口 发出. 路由器会将这个最终的, 简化的指令填入它最高速的本地转发表(Local Forwarding Table)中:

ARP¶

在网络通信中, 我们通常只知道对方的IP地址(逻辑地址, 像收件人姓名和城市). 但数据在局域网(如以太网)中实际传输时, 需要知道对方网卡的MAC地址(物理地址, 像具体的门牌号)才能将数据帧准确送达.

1. 在同一子网: 假设主机A想给同一网络下的主机B发送数据. A首先会查看自己的ARP缓存表(ARP cache), 看里面有没有记录B的IP地址与MAC地址的对应关系. ARP缓存表像一个临时通讯录, 有时效性(TTL, 通常20分钟), 过期会删除. 如果缓存里没有, A就会向局域网内的所有设备发送一个广播(Broadcast)性质的ARP请求. 这个请求包的目标MAC地址是特殊的 FF:FF:FF:FF:FF:FF, 表示"局域网里的每个人都听一下". 请求的内容是: "谁的IP地址是 137.196.7.23(B的IP)? 请告诉 137.196.7.78(A的IP). "局域网内所有其他设备(除了B)收到请求后, 发现要找的IP不是自己的, 就直接丢弃不管. 主机B收到请求, 发现找的就是自己! 于是它会准备一个ARP响应. 这个响应是单播(Unicast)的, 直接发回给A(因为请求包里有A的IP和MAC地址). 响应内容是: "我是 137.196.7.23, 我的MAC地址是 71-65-F7-2B-08-53. "A收到B的响应后, 就把这个IP-MAC对应关系存入自己的ARP缓存表, 然后就可以愉快地向B的MAC地址发送数据了.
2. 在不同子网: 假设主机A (111.111.111.111) 要给另一个网络的主机B (222.222.222.222) 发数据. A通过IP地址和子网掩码计算, 发现B和自己不在同一个网络. 因此, A确定, 这包数据必须先发给默认网关R(IP地址为 111.111.111.220). 此时, A需要知道的不是B的MAC地址, 而是默认网关R的MAC地址. A会发送一个ARP广播请求, 内容是: "谁的IP地址是 111.111.111.220(网关的IP)? "网关R收到请求后, 会单播回复自己的MAC地址给A. A现在可以发送数据了. 它会创建一个数据帧(Frame), 其中: 目标IP地址: 仍然是最终目的地 B的IP地址 (222.222.222.222). 目标MAC地址: 是下一跳 网关R的MAC地址. 网关R收到这个数据帧后, 会拆开查看目标IP, 然后根据自己的路由表, 决定下一步该把数据包发给谁, 并重复类似的过程, 直到数据包最终到达B所在的局域网.

数据平面和控制平面¶

• 数据平面 (Data Plane): 负责转发. 当一个数据包到达路由器时, 数据平面根据包头中的目标地址查找转发表, 决定将该数据包从哪个端口发出去. 这是一个本地, 快速的硬件操作.
• 控制平面 (Control Plane): 负责路由. 它决定数据包从源到目标的整体路径, 并生成供数据平面使用的转发表. 这是一个更宏观, 更复杂的网络逻辑.

两种实现方式:

• 传统网络 (Traditional): 分布式控制平面: 每个路由器都有自己独立的"大脑"(控制平面). 路由器之间通过路由协议(如 OSPF, BGP)互相交换信息, 然后各自独立计算出路由路径和转发表.
• 软件定义网络 (SDN): 将所有"大脑"集中到一个远程的控制器 (Remote Controller)上. 这个控制器拥有整个网络的全局视野, 负责计算所有路径, 然后将具体的转发指令下发给各个路由器. 路由器本身不再进行复杂的计算, 只保留一个简单的控制代理(CA)来接收指令并执行转发, 从而实现了控制与转发的分离.

为什么会出现SDN这个东西呢?

这是因为在传统网络是分布式的, 每台路由器都是一个独立的个体, 这意味着, 一个设备里面既包含了负责转发数据的硬件, 又包含了负责计算路径的软件(OSPF, BGP等), 这些逻辑功能分散在各个独立的, 封闭的设备中, 配置和管理非常困难, 难以同一. 于是, 2005年左右, 学术界和工业界就开始重新思考, 能够将网络的大脑从硬件设备中抽离出来, 进行集中化管理.

SDN¶

每个网络设备内部都有一张流表 (Flow Table). 当一个数据包到达时, 设备会用包头信息(如IP地址, MAC地址, 端口号)去匹配流表中的规则. 一旦匹配成功, 就执行规则对应的动作 (Action). 这张表是由远程的中央控制器计算好, 然后分发给每个设备的.

OpenFlow 是一种标准协议, 它定义了流表规则的格式, 以及控制器如何与网络设备进行通信. 一个 OpenFlow 规则主要包含三个部分: 匹配字段 (Pattern / Rule), 动作 (Actions), 计数器 (Counters).

一个拥有全局视野的 SDN 控制器可以看到所有链路的实时负载和容量. 它可以智能地做出决策, 比如将一部分流量引导至成本稍高的上方路径, 另一部分走下方路径, 从而实现负载均衡, 最大化网络资源的利用率.

1. 数据平面 (Data Plane) - 相当于"硬件". 网络的"四肢和肌肉", 是执行者. 各种 SDN 交换机, 路由器. 只负责根据流表 (Flow Table) 高效地转发数据包. 它们是"傻瓜式"的, 本身没有智能, 只听从指令.
2. 控制平面 (Control Plane) - 相当于"操作系统". 网络的"大脑", 是管理者和决策者. 对下管理硬件: 通过南向接口 (Southbound API), 如 OpenFlow, 向数据平面的交换机下发流表指令, 告诉它们该如何转发. 对上提供服务: 通过北向接口 (Northbound API), 为上层的应用软件提供一个统一的, 可编程的接口.
3. 应用平面 (Application Plane) - 相当于"应用软件". 网络的"灵魂", 是智能和逻辑的体现. 各种网络应用, 如路由算法, 防火墙策略, 负载均衡逻辑等. 实现具体的网络功能. 它们不直接和硬件打交道, 而是通过调用控制器的北向接口来表达自己的"意图", 由控制器去完成具体的网络配置.

Open-Flow¶

OpenFlow 是一个标准化的通信协议, 用于 SDN 控制器和交换机之间的交互. 使用可靠的 TCP 连接来交换消息. 消息分为两大类: 控制器 -> 交换机: 控制器下发指令. 交换机 -> 控制器: 交换机上报事件和信息.

1. 控制器发给交换机的消息: 这些是"命令"类型的消息, 告诉交换机该做什么. 关键消息包括:

   • modify-state (修改状态): 这是最核心的指令. 控制器用它来添加, 删除, 修改交换机流表中的规则. 这正是 SDN "编程"网络的具体实现方式.
   • packet-out (数据包发出): 控制器可以直接命令交换机从某个指定端口发出一个特定的数据包. 这对于控制器主动探测网络或处理 ARP 请求等场景很有用.
   • features / configure: 用于初始设置, 控制器查询交换机的能力(如端口数量)和进行配置.

2. 交换机发给控制器的消息 (Switch-to-Controller). 这些是"事件上报"类型的消息, 告诉控制器网络中发生了什么. 关键消息包括:

   • packet-in (数据包上报): 这是触发控制器决策的关键事件. 当交换机收到一个数据包, 但在其流表中找不到任何匹配的规则时, 它不知道该如何处理. 于是, 它会把这个"未知"数据包(或其头部)封装在 packet-in 消息中发给控制器, 请求指示.
   • port status (端口状态): 当交换机的某个端口发生变化时(例如网线断开或恢复), 交换机会立即通过此消息通知控制器. 这对于控制器实时感知网络拓扑变化至关重要.
   • flow-removed (流表项移除): 当一条流表规则因为超时等原因被移除时, 通知控制器.

重要提示: 网络管理员通常不直接操作这些底层的 OpenFlow 消息, 而是通过控制器上更高级的应用(如路由应用)来间接管理网络.

链路断开之后会发生什么:

1. 故障发生: 交换机 s1 和 s2 之间的物理链路断开. s1 检测到端口状态变化.
2. 事件上报: s1 立刻向控制器发送一个 port status 消息, 报告该端口已失效.
3. 大脑更新信息: 控制器收到消息, 立即更新其内部维护的全局网络拓扑图, 标记 s1-s2 链路为不可用.
4. 重新计算路径: 控制器上运行的路由应用(例如使用 Dijkstra 算法)被触发. 它基于更新后的网络拓扑图, 重新计算出不经过故障链路的最佳路径.
5. 下发新指令: 控制器将新的路由路径转换成具体的流表规则, 并通过 modify-state 消息下发给路径上的所有相关交换机(s1, s3, s4 等), 更新它们的流表.
6. 网络恢复: 数据流开始按照新的路径转发, 网络在无人干预的情况下自动绕过了故障点.

传输层¶

网络层提供的是主机到主机的通信, 传输层在网络层之上, 提供进程到进程的通信, 并可以增强服务, 例如通过TCP提供可靠性.

一个核心的问题是如何区分不同的进程. 一台主机上可能同时运行着多个需要联网的应用程序(比如浏览器, 微信, 游戏). 当一个数据包从网络层到达这台主机时, 传输层如何知道该把它交给哪个应用程序呢? 答案是通过多路复用和多路分解.

• 多路复用: 想象公寓里的不同住户(进程 P1, P2)都把自己的信件(数据)投递到一个公共的邮箱里, 准备让邮递员(网络层)取走. 传输层从多个不同的套接字 (Sockets) 收集数据, 为每一份数据添加一个头部信息(Header), 这个头部里包含了源端口号和目标端口号. 这个"端口号"就像是信封上写的"房间号", 能唯一标识一个应用程序.
• 多路分解: 公寓的管理员(传输层)收到邮递员送来的一堆信件. 他会查看每封信上的"房间号"(目标端口号), 然后把信准确地投递到对应住户的信箱里(正确的套接字). 传输层接收到数据段后, 会检查其头部的目标端口号, 并根据这个号码, 将数据段递交给与之绑定的正确套接字, 最终送达应用程序(进程 P4).

网络根据协议不同, 主要有两种分用方式: 无连接分用 (Connectionless Demultiplexing) 和 面向连接分用 (Connection-oriented Demultiplexing). 无连接分用只通过目的端口号来确定将数据交给哪个套接字, 只要发往同一个目的端口的数据包, 无论它们来自哪个源IP或源端口, 都会被送到同一个套接字. 面向连接分用则更严格, 它使用四元组 (源IP, 源端口, 目的IP, 目的端口) 来唯一标识一个连接. 这样, 即使多个连接使用相同的目的端口号, 只要它们的源IP或源端口不同, 传输层也能正确区分并将数据送达对应的套接字.

UDP¶

UDP是一个无修饰的协议, 它提供尽力而为的服务. 这意味着数据包可能会丢失, 可能会乱序喂给上层的application. 在发送数据之前, 发送方和接收方之间不需要建立连接, 每个UDP数据段都是独立处理的, 彼此之间没有关联. 主要用于流媒体应用和DNS. UDP的头部非常简单, 只有源端口号, 目的端口号, 长度和校验和.

UDP的校验方式:

• 在发送端, 将 UDP 数据段(包括头部和数据)的内容看作是一系列16位的整数. 将所有这些16位整数相加. 这个加法是反码加法, 意思是如果最高位相加产生了进位, 这个进位需要被加到结果的最低位上(称为回卷 wraparound, 如幻灯片48的例子所示). 将最终的和按位取反(0变1, 1变0), 得到的结果就是校验和. 将这个校验和值放入 UDP 头部的 checksum 字段.
• 在接收端, 将收到的整个数据段(包括 checksum 字段)的所有16位整数用同样的方式(反码加法)相加. 如果结果是全 1 (1111 1111 1111 1111), 说明未检测到错误. 如果结果不是全 1, 说明数据在传输中发生了错误, 接收方通常会直接丢弃这个数据包.

可靠性传输¶

从application layer来看, 我们希望有一个完全可靠的信道, 数据能准确无误的从发送方传到接收方. 实际上, 底层信道是不可靠的, 数据包可能丢失, 损坏或者无序. 为了实现可靠传输, 我们需要设计一个可靠数据传输协议(rdt). 这个协议为上层应用提供了简单的接口: 发送方: 应用调用 rdt_send() 来发送数据. 接收方: 协议通过 deliver_data() 将数据交给应用. 协议在底层和不可靠信道之间交互: 发送方: 调用 udt_send() (unreliable data transfer) 将数据包发往信道. 接收方: 通过 rdt_rcv() 从信道接收数据包.

rdt1.0¶

这是一个假设模型, 前提是底层信道完全可靠, 不会发生比特错误或丢包. 发送方: 从上层接收数据, 打包后直接发送. 接收方: 从底层接收数据包, 解包后直接交给上层. 这只是一个理论起点, 现实网络并非如此.

RDT2.0: 解决比特错误¶

新问题: 数据包在传输过程中可能会损坏 (比特翻转). 解决方案: 引入了三个关键机制:

1. 错误检测 (Error Detection): 使用校验和 (checksum). 发送方计算数据校验和并放入包中; 接收方收到后重新计算并比对, 以此判断数据是否损坏.
2. 接收方反馈 (Feedback): 接收方需要明确告知发送方接收情况.
   • ACK (确认): 表示数据包完好收到.
   • NAK (否认): 表示数据包已损坏.
3. 重传 (Retransmission): 发送方如果收到 NAK, 就会重新发送上一个数据包.

RDT2.1¶

仅靠ACK/NAK无法处理信息本身也损坏的情况, 必须引入序列号来解决由此产生的重复包的问题. 无错误情况: 发送方发包 -> 接收方收到完好包, 回复 ACK -> 发送方收到 ACK, 准备发下一个包. 一切顺利. 数据包错误情况: 发送方发包 -> 接收方收到损坏包, 回复 NAK -> 发送方收到 NAK, 重传同一个包. 这个机制是有效的.

新问题: 如果 ACK 或 NAK 反馈信息本身在传输过程中损坏了, 怎么办? 发送方的困境: 当发送方收到一个无法识别的, 损坏的反馈时, 它完全不知道接收方那边发生了什么. 它无法判断是原始数据包坏了 (应该重传), 还是原始数据包好的, 但返回的 ACK 坏了 (不该重传). 唯一的选择: 为了保证可靠性, 发送方只能选择重传. 导致新问题: 如果原始数据包其实已经被接收方成功接收了 (只是ACK坏了), 那么这次重传就会造成重复数据包 (Duplicate Packet). 如果接收方无法识别这是个重复包, 将其再次交给应用层, 就会导致数据错误.

rdt2.1的核心是引入一个序列号, 为每个数据包添加序列号, 如简单的在0和1之间交替. 发送方: 发送带序列号的包 (例如 pkt0), 然后等待对 pkt0 的 ACK. 如果收到损坏的 ACK/NAK, 就重传 pkt0. 只有在明确收到对 pkt0 的 ACK 后, 才会开始发送 pkt1. 接收方: 接收方会记录它当前期望收到的序列号. 如果收到的包序列号是期望的 (比如期望0, 收到0), 就接收数据, 回复对应序列号的 ACK, 然后开始期望下一个序列号 (期望1). 如果收到的包序列号是过时的 (比如期望1, 却收到了0), 这说明这是一个重复包. 接收方会丢弃这个包的数据 (不上传给应用层), 但仍然会回复一个对应旧序列号的 ACK (ACK0), 以确保发送方能继续前进.

RDT2.2¶

这是一个rdt2.1的变种, 完全移除了NAK消息. 它通过发送对上一个接受包的冗余ACK, 来间接实现NAK消息.

接收方只发送 ACK. 这个 ACK 必须明确包含它所确认的数据包的序列号 (例如 ACK0 或 ACK1). 当接收方收到一个损坏或失序的数据包时, 它不会沉默, 也不会发 NAK, 而是会重新发送一次对上一个正确接收包的 ACK. 发送方根据收到的 ACK 序列号来判断. 如果收到期望的 ACK (例如, 发了包 0, 收到 ACK0), 则说明发送成功, 继续发送下一个包. 如果收到意外的 ACK (例如, 发了包 0, 却收到了 ACK1), 这就等同于收到了 NAK. 发送方明白当前包出错了, 于是重传当前包.

RDT3.0¶

在 rdt2.2 的基础上, 解决了最后一个关键问题: 数据包或确认包在信道中丢失. 引入一个超时重传 (timeout) 机制. 如果发送方在等待一段时间后仍未收到确认, 就假定数据包丢失并进行重传.

底层信道不仅会损坏数据 (bit errors), 还会丢失整个数据包 (packet loss). 这包括数据包和 ACK 包. 现有机制的不足: rdt2.2 的序列号和 ACK 机制可以处理损坏和重复问题, 但如果一个包或它的 ACK 彻底丢失了, 发送方会陷入无限等待, 因为它永远也等不到期望的 ACK.

解决方案是: 发送方在发送数据包后, 启动一个倒计时器 (countdown timer). 如果在计时器超时前, 收到了正确的 ACK, 就万事大吉, 取消计时器即可. 如果计时器超时 (timeout), 发送方就认为包丢失了, 并重新发送该数据包, 然后重启计时器. 超时重传可能会导致重复数据包 (例如, 只是 ACK 延迟了, 并非丢失). 但幸运的是, rdt2.x 版本引入的序列号 (sequence number) 机制已经完美地解决了这个问题, 接收方可以轻易识别并丢弃重复包.

高效传输¶

尽管RDT3.0在逻辑上是正确的, 但是在长距离, 高带宽的线路中, 它的性能非常糟糕. 例如, 假设一个网络的带宽是1 Gbps = 10^9 bits/sec, 单向传播的延迟是15ms, 数据包大小为8000bits, 即1KB, 将数据包推送到链路上需要的时间为8000/10^9=8μs=0.008ms. 传播延迟远大于传输延迟, 这意味着发送方在发送完一个包后, 需要等待很长时间才能收到ACK(30ms), 这段时间链路基本处于闲置状态, 带宽利用率非常低. 利用率 = 0.008ms / 30ms = 0.00027 = 0.027%. 这意味着发送方只有0.03%的时间在发送数据, 其余99.97%的时间都在等待ACK. 所以我们不能直接使用RDT3.0, 必须引入流水线机制. 如下图所示:

为了解决RDT3.0的效率问题, 我们引入流水线技术. 核心概念是发送方不再是一个接一个地停-等, 而是允许发送多个在途且尚未被确认地数据包. 流水线的改进带来两个问题:

1. 序列号范围必须增加: 因为我们需要确认多个数据包, 所以我们再使用之前那种0和1之间交替的序列.
2. 缓存: 发送方需要缓存已经发送但是没有确认的包, 接收方可能需要缓存乱序到达的包

解决上述问题, 有两种方式:

1. GBN
2. Selective Repeat

GBN¶

Selective Repeat¶

TCP🌟¶

TCP的主要特征:

• 点对点: 一个发送方, 一个接收方
• 可靠, 有序的字节流: 应用层只要把数据扔进TCP, TCP保证数据不丢, 不乱, 不出错.
• 流水线: TCP发送的窗口是动态变化的, 基于拥塞控制和流量控制机制调整窗口大小.
• 全双工: 数据可以同时在两个方向传输.
• MSS: 最大报文段长度, 通常是1460字节 (以太网MTU 1500 - IP头20 - TCP头20).
• 面向连接: 通过三次握手建立连接, 四次挥手断开连接.
• 流量控制: 使用滑动窗口机制, 避免发送方过快发送数据淹没接收方缓冲区.

序列号和ACK机制¶

TCP使用序列号 (Sequence Number) 和确认号 (Acknowledgment Number) 来实现可靠传输. 每个字节的数据都有一个唯一的序列号. 发送方在发送数据时, 会为每个数据段分配一个起始序列号. 接收方在收到数据后, 会发送一个确认号, 表示它期望下一个接收的字节的序列号.

🌟重传时间¶

TCP必须设置一个超时计时器来决定什么时候重传, 但是这个时间比较难确定. 核心问题是因为RTT是波动的, 超时太短会导致不必要的重传, 超时太长会导致丢包后反应太慢, 用户体验差. 解决方案是: 测量从发出报文到收到确认的时间, 作为SampleRTT, 如果发生了重传, 就不要把时间算进去, 单词测量不稳定, TCP会计算一个加权平均的EstimatedRTT: EstimatedRTT = (1 - α) * EstimatedRTT + α * SampleRTT. 有了平均值还不够, 还得考虑安全边际, 这是因为如果网络波动幅度非常大, 安全边际就要留大一点, 我们会计算一个波动幅度(DevRTT): DevRTT = (1 - β) * DevRTT + β * |SampleRTT - EstimatedRTT|. 最后, 我们就可以计算出最终的超时重传时间: TimeoutInterval = EstimatedRTT + 4 * DevRTT. 这里α通常取0.125, β取0.25.

可靠性¶

这里, TCP总结了GBN, RDT3.0的特性, 衍生出了自己的可靠性传输机制. 它采用的是流水线, 累积确认, 单一重传计时器的结构. 触发重传的条件有两种: 一种是超时; 另一种是重复ACK(快速重传). 但是它和GBN的一个最大的不同就是: TCP允许接收方缓存乱序到达的包, 这样就不会因为一个包丢失而需要发送方重传后续所有包. 举个例子: 包1 丢了, 但是 包2, 3, 4, 5 都成功到达了接收方.

• 如果是GBN: 接收方收到 包2,3,4,5, 因为没有收到 包1, 它会把 2,3,4,5 全部扔掉(因为它是死板的按序接收), 并不断重复发送 ACK 1. 发送方超时后, 必须重传 1, 2, 3, 4, 5(全部重来). 浪费带宽.
• 如果是TCP: 接收方收到 包2,3,4,5, 它会把它们缓存起来, 并重复发送 ACK 1(告诉发送方我还在等1). 发送方超时后, 只重传 包1. 接收方收到重传的 包1 后, 发现 2,3,4,5 已经在缓存里了, 于是直接发送 ACK 6. 节省带宽.

重传的情况(3种):

快速重传¶

超时等待往往很长. 若仅靠超时重传 会延迟恢复. 通过重复ACK检测丢包. 管道化发送使接收方在缺失某段时会对后续乱序段反复回ACK同一序号. 发送方收到3个重复ACK时 认为最小未确认段很可能丢失 不等超时 立即重传该段. 右图示例. 丢失Seq=100的段 后续段到达触发多次ACK=100. 当出现3个重复ACK时发送方立刻重传Seq=100.

连接管理¶

TCP连接的建立会经理三次握手的过程.

关闭会经历四次挥手的过程.

流量控制¶

注意, 流量控制和拥塞控制是不一样的,

流量控制是通过接收方根据自己的情况在报文中设置一个窗口大小rwnd来实现的. 发送方在发送数据时, 必须确保未被确认的数据量不超过rwnd. 这样可以防止发送方发送过快, 导致接收方缓冲区溢出.

拥塞控制🌟¶

太多的发送方, 发了太多的数据, 且速度太快, 导致网络处理不过来. 这个和流量控制不同, 流量控制是为了照顾发送方, 而拥塞控制是为了保护网络. 面对拥塞, 网络设计者有两种流派, 一种是端到端拥塞控制, 特点是, 没有来自网络的显示反馈, 路由器不会告诉你我堵了, 发送方自己去猜, 如果你发现丢包了, 或者延迟变大了, 就推断可能有拥塞, 然后自己减速. 传统的TCP/IP协议主要采用这种方式, 因为这样路由器就可以很简单; 另一种是网络辅助拥塞控制, 路由器会主动告诉你拥塞情况, 路由器可能在包里面标记一个bit, 或者直接发消息告诉发送方, 请以X mbps的速度发送.

拥塞窗口(cwnd)定义了发送方在收到 ACK 之前, 最多能往网络里发多少数据(即"在途数据 / in-flight data"). 公式为LastByteSent−LastByteAcked≤cwnd, 也就是说, 发送方发送的数据量不能超过拥塞窗口的大小. 发送最大速率为: = cwnd / RTT.

TCP的控制算法如下图:

TCP丢包有两种情况, 反应的激烈程度不同:

• 情况A: 发出去很久都没回音, 连重复的 ACK 都没有, 说明网络可能断了或者极度拥堵. 直接把 cwnd 重置为 1 MSS. 一切从头开始(重新进入慢启动).
• 情况B: 收到3个重复的 ACK, 说明网络只是有点拥堵, 但是还能收到数据.
  • TCP Tahoe (老版本): 不管三七二十一, 处理方式和超时一样: cwnd 归 1, 重新慢启动. (激进的清零).
  • TCP Reno (改进版): 认为网络只是轻微拥塞, 于是把 cwnd 减半 (乘以0.5), 然后进入拥塞避免阶段 (线性增长). 这种方式更温和一些, 避免了频繁的清零.

最终, 我们TCP的窗口大小是: min(cwnd, rwnd).

应用层¶

应用层架构¶

在设计一个网络应用时, 主要有两种结构模式:

1. 客户-服务器模式 (Client-server).
   • 服务器
     • Always-on: 必须一直开机, 等待别人来连接.
     • 固定 IP: 地址不能变, 否则别人找不到.
     • 数据中心: 为了扩展能力(服务更多人), 通常由大型数据中心集群组成.
   • 客户端
     • 主动发起: 与服务器通信.
     • 间歇性连接: 可以随时关机, 断网.
     • 动态 IP: 每次上网 IP 可能都不一样.
     • 互不通信: 客户机之间不直接说话(比如你看网页时, 你的浏览器不会去连隔壁老王的浏览器, 都是连服务器).
2. 对等模式 (Peer-to-peer, P2P)
   • 没有(或很少依赖)总是被连接的服务器: 大家地位平等.
   • 端系统直接通信: 任意两个对等方(Peers)可以直接传数据.
   • 间歇性连接: 你的电脑一会开一会关, IP 也是变的, 这导致管理非常复杂.

进程间通信¶

进程是在主机上运行的程序, 同一主机内, 进程间通过操作系统定义的进程间通信机制进行, 不同主机间, 进程通过交换报文进行通信. 进程间通过套接字发送和接受报文, 它类似于进程通向外部世界的门. 仅靠IP地址无法唯一标识一个主机上的特定进程, 因为一个主机上可以同时运行多个网络进程. 解决方案是使用一个包含IP地址和端口号的组合来作为进程的唯一标识符. 例如, HTTP服务使用的是80端口, 邮件服务使用的是25端口. 应用层协议定义了网络通信的规则, 包括报文类型, 如请求, 相应; 报文语法, 报文语义, 如404, 通信规则, 如进程何时以及如何发送和响应报文. 这些协议可以分为开放协议和专有协议. 不同的应用对底层传输服务有不同的需求, 例如数据完整性方面, 文件传输等应用要求100%可靠的文件传输, 而音频等应用可以忍受部分数据丢失....

HTTP🌟¶

一个网页由一个基础的 HTML 文件和该文件引用的多个对象(如 JPEG 图片, Java applet, 音频文件等)组成. 每个对象都有一个唯一的地址, 称为 URL (Uniform Resource Locator). URL 通常由主机名 (host name) 和路径名 (path name) 组成.

HTTP (Hypertext Transfer Protocol) 是 Web 的应用层协议. 它采用客户端/服务器 (client/server) 模型: 客户端 (Client): 通常是浏览器, 负责发起请求, 接收并展示 Web 对象. 服务器 (Server): 如 Apache Web Server, 负责存储 Web 对象, 并在收到请求时发送相应的响应. HTTP 使用 TCP 作为其底层的传输协议, 以确保数据可靠传输. HTTP 是一个无状态协议. 服务器不会保存任何关于过去客户端请求的信息. 每个请求都被独立处理. 与之相对, 需要维护"状态"的协议会更复杂, 因为需要处理历史记录和数据同步问题.

持久连接和非持久连接¶

HTTP 使用的 TCP 连接可以分为两类:

• 非持久连接 (Non-persistent HTTP): 每个 TCP 连接最多只传输一个对象. 传输完成后, 连接立即关闭. 下载包含多个对象的网页需要建立多次 TCP 连接, 效率较低.
• 持久连接 (Persistent HTTP): 单个 TCP 连接可以用来传输多个对象. 客户端和服务器之间可以复用同一个连接来交换多个请求和响应, 显著提高了效率.

非持久连接:

核心思想: 每个 TCP 连接只传输一个 Web 对象(如一个 HTML 文件或一张图片).

1. 步骤 1a/1b: 客户端发起 TCP 连接请求(SYN), 服务器接受(SYN+ACK). 此过程耗时 1个 RTT.
2. 步骤 2-3: 客户端发送 HTTP 请求报文, 服务器返回包含 home.index 的响应报文. 此过程耗时 1个 RTT (请求发出到收到响应的开始).
3. 步骤 4: 服务器关闭 TCP 连接.
4. 步骤 5: 客户端收到 HTML 文件, 解析后发现其中还引用了 10 张图片.
5. 对于每一张图片, 客户端都必须重复上述步骤 1-4, 即为每一张图片都建立一个新的, 独立的 TCP 连接.

获取单个对象的时间 = 2RTT + 文件传输时间.

持久连接:

单个 TCP 连接可以用来传输多个 Web 对象.

1. 步骤 1a/1b: 客户端发起 TCP 连接请求, 服务器接受. 此过程耗时 1个 RTT.
2. 步骤 2-3: 客户端通过已建立的连接发送对 home.index 的 HTTP 请求, 服务器返回该文件. 关键区别: 服务器在发送完响应后, 不关闭 TCP 连接 (TCP is still on).
3. 步骤 5: 客户端收到 HTML 文件, 解析后发现需要 10 张图片.
4. 后续操作: 客户端会重用这个已经打开的 TCP 连接, 依次发送对这 10 张图片的 HTTP 请求. 服务器也通过这个连接将图片一一发回.

只需要 1 个 RTT 来建立连接, 后续获取每个对象只需 1 个 RTT (请求发出到收到响应的开始).

请求和相应报文¶

HTTP 报文分为请求报文 (Request Message) 和响应报文 (Response Message). 请求报文由请求行 (Request Line), 多个请求头部字段 (Header Fields) 和可选的请求体 (Body) 组成. 响应报文由状态行 (Status Line), 多个响应头部字段 (Header Fields) 和可选的响应体 (Body) 组成. 报文头部字段携带了很多元数据, 如内容类型, 内容长度, 缓存控制等信息.

常见的响应状态码:

Cookies¶

1. 服务器创建状态: 当用户首次访问时, 服务器(如 Amazon)创建一个唯一的 ID(例如 1678), 并在后端的数据库中记录条目.
2. 设置 Cookie: 服务器在 HTTP 响应中通过 Set-Cookie 首部将这个 ID 发送给客户端.
3. 客户端存储: 浏览器将这个 ID 保存在本地的 Cookie 文件中.
4. 后续请求: 当用户再次访问该网站时, 浏览器会自动在 HTTP 请求的 Cookie 首部中带上这个 ID.
5. 服务器识别: 服务器读取请求中的 ID, 查询数据库, 从而识别出是哪个用户, 并可以执行与该用户相关的特定操作(如显示购物车内容).

Web缓存¶

Web 缓存(通常是代理服务器)的目标是: 在不访问源服务器的情况下满足客户端的 HTTP 请求, 以加快响应速度并减轻源服务器的负载.

工作机制:

1. 客户端将所有 HTTP 请求发送给代理服务器(缓存).
2. 如果缓存中有请求的对象(缓存命中 cache hit), 则直接将对象返回给客户端.
3. 如果缓存中没有该对象(缓存未命中 cache miss), 代理服务器会扮演客户端的角色, 向原始服务器发起请求.
4. 原始服务器响应代理服务器后, 代理服务器会将对象存储起来以备后用, 并将其转发给最初的客户端.

条件化GET¶

条件 GET 的目标是: 如果客户端(或代理缓存)中已经有了最新的版本, 就不要重复发送整个对象. 这样做可以: 消除不必要的文件传输延迟. 降低网络链路的带宽占用.

DNS¶

DNS 是一个分布式, 分层的数据库系统, 同时也是一个应用层协议. 它的核心功能是将人类易于记忆的域名(如 www.google.com)解析为机器可以识别的 IP 地址(如 142.251.42.228), 反之亦然. 你可以把它想象成互联网的"电话簿".

DNS不使用集中的服务器是为了避免以下问题:

• 单点故障: 如果唯一的中央服务器宕机, 整个互联网的域名解析服务就会瘫痪.
• 访问延迟: 全球用户访问一个中心点, 距离远的用户延迟会很高.
• 可扩展性差: 单一服务器难以处理全球海量的查询请求.

除了最核心的主机名到IP的转换之外, DNS还提供:

• 主机别名 (Host Aliasing): 允许一个主机拥有多个域名.
• 邮件服务器别名 (Mail Server Aliasing): 为域名指定邮件服务器.
• 负载均衡 (Load Distribution): 将一个域名解析到多个不同的 IP 地址, 从而将访问流量分散到多个服务器上, 提高网站的可用性.

层级结构¶

• 本地DNS服务器: 这是上网接触的第一台DNS服务器, 它会缓存最近查询过的域名-IP映射记录, 以加快后续查询速度. 如果缓存中没有记录, 它会代替你的电脑, 向互联网的其他DNS服务器发起查询.
• 根DNS服务器: 根DNS服务器位于层级结构的顶端, 全球一共有13个逻辑根服务器(实际有数百台物理服务器). 它们知道所有顶级域 (TLD, 如 .com, .org, .net) 的位置.
• 顶级域DNS服务器 (TLD DNS Servers): 这些服务器负责管理特定顶级域下的所有二级域名. 例如, .com 顶级域的 TLD 服务器知道所有以 .com 结尾的域名的权威DNS服务器的位置.
• 权威DNS服务器 (Authoritative DNS Servers): 这些服务器存储了特定域名的最终IP地址映射记录. 当查询到达权威DNS服务器时, 它会返回该域名对应的IP地址.

查询方式🌟¶

DNS的查询方式可以分为迭代和递归.

iterated query:

recursive query:

缓存¶

为了提高效率, 任何 DNS 服务器在获得一次查询结果后, 都会将其缓存起来.

• 目的: 下次再有相同的请求时, 可以直接从缓存中返回结果, 无需再走一遍完整的查询流程, 从而大大加快速度并减少网络流量.
• TTL (Time To Live, 生存时间): 缓存的记录不会永久保存. 每条记录都有一个 TTL 值, 它决定了这条记录可以在缓存中存放多久. 时间一到, 记录就会被丢弃.
• 缺点: 缓存可能导致数据过期 (out-of-date). 如果一个网站更换了 IP 地址, 但全球各地的 DNS 服务器缓存尚未过期, 那么在 TTL 失效前, 用户仍会被导向旧的 IP 地址.

DNS记录¶

DNS 的核心是其数据库, 数据库中存储的就是各种资源记录 (Resource Records, RR). 每条记录都包含四个主要部分: (名称, 值, 类型, TTL).

常见的记录类型 (Type) 包括:

• A 记录 (Type=A): 最常见的记录, 用于将一个主机名 (name) 映射到一个 IPv4 地址 (value). gaia.cs.umass.edu -> 128.119.245.12
• NS 记录 (Type=NS): 指定某个域 (name) 的权威名称服务器 (value) 是谁. 这是实现 DNS 分层查询的关键. umass.edu -> dns.umass.edu
• CNAME 记录 (Type=CNAME): 将一个别名 (name) 映射到一个规范名(真正的名字)(value). www.ibm.com -> servereast.backup2.ibm.com
• MX 记录 (Type=MX): 邮件交换记录, 指定一个域 (name) 的邮件服务器 (value) 是谁. 这决定了发送到 @example.com 的邮件应该被投递到哪台服务器. example.com -> mail.example.com

P2P和CS¶

我们来比较一下两种文件分发类型: CS和P2P的效率, 核心问题是, 将一个大小为F的文件分发给N个用户需要多长的时间:

• CS: 服务器必须为N个客户端分别上传一次文件, 总上传量为N*F, 所需的时间为NF/R, R是服务器的上传速率. 整个分发过程必须等到下载速度最慢的客户端完成下载, 所需时间为F/min{d1, d2, ..., dN}, di是第i个客户端的下载速率. 因此, CS的总分发时间为: Dcs = max{NF/R, F/min{d1, d2, ..., dN}}.
• P2P: 在这种模式下, 下载了文件的客户端也会帮助上传, 成为新的分发节点. 瓶颈在于服务器的初始上传, 服务器至少需要上传一个完整的文件副本, 分发过程才可以开始, 时间为F/R. 和CS一样, 耗时也受限于最慢的客户端, 所需时间为F/min{d1, d2, ..., dN}. 整个系统需要上传NF的总数据量, 而系统的总上传能力是R+u1+u2+...+uN, ui是第i个客户端的上传速率. 因此, P2P的总分发时间为: Dp2p = max{F/R, F/min{d1, d2, ..., dN}, NF/(R + u1 + u2 + ... + uN)}.

Bittorrent是一个高效的P2P文件分发应用. 他能快速的将文件分发给大量用户. 整个文件预先分为许多小的数据块 .torrent文件是一个小的元数据文件, 记录了文件的哈希值, 大小以及 Tracker 服务器的地址等信息. Tracker是一个协调服务器. 它不存储文件本身, 只负责跟踪当前哪些用户 (Peers) 正在下载或分享该文件, 并帮助他们互相发现对方. Torrent (群): 指正在交换同一个文件所有数据块的所有用户的集合.

1. 加入: 用户 (例如 Alice) 打开 .torrent 文件, 她的客户端会联系 Tracker 服务器.
2. 发现 Peer: Tracker 返回一个当前在此 "Torrent (群)" 中的其他用户 (Peers) 的列表.
3. 交换数据块: Alice 开始与其他 Peers 建立连接, 互相交换各自拥有的文件数据块 (Chunks). 她在下载的同时, 也会将自己已有的数据块上传给别人.

激励机制:

这是 BitTorrent 的核心与精髓, 旨在鼓励分享, 防止"搭便车"行为.

• 优先上传: 你的客户端会优先将数据块上传给那些 给你提供最快下载速度 的少数几个 Peers. 你给别人传得快, 别人也给你传得快.
• 定期"乐观地非阻塞" (Optimistic Unchoke): 为了发现潜在的更优连接伙伴, 并让新加入的 Peer 也能获得初始数据块, 客户端会每隔一段时间 (例如30秒) 随机选择一个之前被"阻塞"(不给其上传)的 Peer, 并开始向其上传数据. 如果这个新的 Peer 反过来也提供了很高的上传速度, 他就有可能成为你的"优先上传"伙伴.

网络安全¶

为了方便概念理解, 使用以下虚拟角色: Alice和Bob, 是两个希望进行安全通信的合法用户. Trudy是一个试图破坏他们通信的中间人. 这个中间人可能会eavesdrop(窃听), impresonation(冒充), hijacking, DoS等.

Alice想要发送的原始消息, 记为m, Alice使用一个加密算法和一个加密密钥将明文转为密文, 公式为KA(m). 密文在不安全的信道传输, 可能会被Trudy截获, BoB收到密文后, 使用一个解密算法和一个解密密钥将密文还原为原始明文, 公式为m = KB(KA(m)).

破解方案¶

入侵者Trudy有以下几种常见地攻击方法:

• 唯密文攻击 (Ciphertext-only attack): Trudy 只拥有截获的密文. 她可以:
  • 暴力破解: 尝试所有可能的密钥.
  • 统计分析: 分析密文中字母或符号的频率, 推断其规律 (例如, 在简单替换密码中, 出现最多的密文字母很可能对应明文的'e').
• 已知明文攻击 (Known-plaintext attack): Trudy 拥有一些明文及其对应的密文样本. 这能帮助她更快地推断出密钥或加密规则.
• 选择明文攻击 (Chosen-plaintext attack): Trudy 可以自己选择一些明文, 并获得其加密后的密文. 这是最强大的攻击方式, 因为她可以构造特殊的明文来最高效地破解密码.

对称加密¶

对称密钥加密是一种特殊的加密模型, 其中加密密钥和解密密钥是完全相同的. Alice和Bob必须使用同一个密钥K, 核心问题是, Alice和Bob在开始通信之前, 安全地商定出一个共享密钥K.

在现代对称密钥标准出现之前, 使用的大多数是简单的替换或者多字母替换. 后来, DES出现了, 他使用56位对称密钥, 由于其56位过短你, 在今天的计算下, 已经被证明不安全, 攻击者可以在一天之内暴力破解, 为了加强安全性, 曾使用3次DES操作来加密数据, 被称为3DES, 但是效率较低. AES是取代DES的现代标准, 数据块可以有128, 192或者256位, 安全性较高, 他在设计上旨在抗衡所有的已知攻击, 其更长额密钥使得暴力破解在计算机上变得不可行.

非对称加密🌟¶

公钥加密采用的是一种完全不同的模式. 核心思想是使用一对密钥, 而不是单个密钥. 公钥可以被公开分发, 任何人都可以获取, 它用于加密信息. 私钥必须严格保密, 只有密钥的持有者才拥有, 他用于解密信息. 它完美解决了对称密钥过程中的密钥交换的难题, 发送方和接收方无需事先见面或者通过安全渠道协商一个共享密钥. Alice只需要获取BoB的公钥就可以加密信息发送给他, 只有拥有自己私钥的Bob才能解密.

RSA¶

RSA是第一个满足上述要求的算法, 它的安全性建立在大数质因数分解的困难行之上. RSA的核心是模运算, x mod n指的是x除以n后的余数.

1. 选择两个巨大的素数: p和q
2. 计算n = p * q, z = (p-1) * (q-1)
3. 选择两个整数:
   • e: 使得e和z互质, 且e<z
   • d: 使得(e*d) mod z = 1

产生密钥:

• 公钥: (n, e)
• 私钥: (n, d)

加密解密过程:

• 加密: 发送方想加密一条小于n的数字信息m, c = m^e mod n, c就是加密后的密文
• 解密: 接收方想解密c, m = c^d mod n, m就是解密后的明文

魔法在于(m^e mod n)^d mod n = m, 这在数学上可以证明. 并且, 先用公钥加密后用私钥解密和先用私钥加密再用公钥解密的结果是完全相同的. 这催生出了数字签名, 当一个人用它的私钥对信息进行加密的时候, 任何人都可以用它的公钥来解密, 这就证明信息确实是由私钥的持有者发出的.

RSA的安全性基于一个数学难题, 假设攻击者知道了公钥(n, e), 它是否能够推导出(n, d)呢, (e*d) mod z = 1, 意味着它需要知道z, z = (p-1)(q-1), n = pq, 而要想从一个非常大的数分解出两个质因数在现有的计算能力下是不可行的.

虽然RSA非常安全的解决了密钥交换的问题, 但是它有一个实际的缺点呢, 就是计算速度慢, RSA比AES慢很多, 因此, 在实际应用中(HTTPS), 采用混合加密的策略, 使用RSA交换对称密钥, 然后使用对称密钥加密数据传输.

认证协议¶

• ap1.0: Alice发送了一条消息说, 我是alice, 毫无安全性, Trudy可以简单的重放(replay)或者冒充(impersonation)实现攻击
• ap2.0: alice在消息中加入了它的ip地址, Trudy可以伪造源ip地址, 叫做ip spoofing.
• ap3.0: alice发送ip地址, 以及明文密码. Trudy直接窃听到了alice的密码
• ap3.1: 为了防止密码被窃听, Alice 这次发送她加密后的密码.这是一个进步, 因为 Trudy 无法再直接获取密码了. 但是, 重放攻击依然有效. Trudy 不需要知道加密内容是什么, 她只需要完整地记录下这个加密后的数据包, 并在稍后原封不动地发送给 Bob. Bob 收到后会成功解密并验证通过, 依然无法分辨这是不是一次旧的, 被重放的请求.
• ap4.0: 前几个协议的核心弱点在于它们都是静态的, 容易被记录和重放. 为了解决这个问题, 必须引入动态的, 一次性的元素.Nonce: 一个只使用一次的随机数 (Number used once). 它的作用是确保每次认证请求都是全新的, 独一无二的. Alice 向 Bob 表明身份 ("我是 Alice"). Bob 生成一个随机的 Nonce R 并发送给 Alice (这是"质询"). Alice 必须使用共享密钥加密 R 并将其发送回 Bob (这是"响应"). Bob 收到响应后, 用共享密钥解密. 如果解密结果与他之前发送的 R 相匹配, 则认证成功.
• ap5.0: 协议 4.0 很安全, 但它依赖于一个预先共享的密钥. 如果没有共享密钥, 我们可以用公钥加密来达到同样的目的. Alice 向 Bob 表明身份. Bob 发送一个随机 Nonce R 给 Alice. Alice 用她自己的私钥加密 R, 并将结果 KA-(R) 发送给 Bob. (这个操作本质上就是一次数字签名). Bob 使用他预先知道的 Alice 的公钥来解密收到的信息 KA+(KA-(R)). 如果解密结果等于 R, 则认证成功. 因为只有持有 Alice 私钥的人才能正确地"签名" R, 所以 Bob 可以确认对方就是 Alice. 这个过程同样证明了 Alice 的身份和"在线状态", 并且无需任何预共享的秘密.

中间人攻击¶

1. Trudy 欺骗 Bob:

   • 当 Bob 想要与 Alice 通信并发起认证时, 他会向"Alice" (实际上是 Trudy) 请求其公钥.
   • 这是最关键的一步: Trudy 不会发送 Alice 的公钥 KA+, 而是发送她自己的公钥 KT+.
   • Bob 收到 KT+ 后, 错误地认为这就是 Alice 的公钥, 并用它来加密之后要发送给 Alice 的所有信息.

2. Trudy 欺骗 Alice:

   • 同时, Trudy 与 Alice 建立连接, 伪装成 Bob. 在这个过程中, Trudy 会获取到 Alice 真实, 合法的公钥 KA+.

3. 消息中继与窃听:

   • 现在, Bob 想发送一条秘密消息 m 给 Alice.
   • Bob 使用他以为属于 Alice 的公钥 (实际上是 Trudy 的公钥) 加密消息, 得到 KT+(m), 并发送出去.
   • Trudy 截获该消息. 因为这是用她自己的公钥加密的, 所以她可以用自己的私钥 KT- 轻松解密, 从而窃取到消息 m 的内容.
   • 为了不被发现, Trudy 会用她之前获取到的 Alice 的真实公钥 KA+ 重新加密消息 m, 得到 KA+(m), 然后再发给 Alice.
   • Alice 收到 KA+(m) 后, 用自己的私钥 KA- 成功解密, 得到 m

可怕之处:

• 极难被察觉: 从 Alice 和 Bob 的角度来看, 整个通信过程是完全正常的. 他们发送的消息最终都能够被对方正确接收和解密. 他们甚至可以在事后讨论通信内容, 也发现不了任何问题, 因为内容是对的. 他们完全不知道有第三方正在窃听甚至篡改他们之间的每一条信息.
• 暴露了根本问题: 这个攻击揭示了 ap5.0 协议的根本缺陷——它无法验证公钥的真实性. Bob 没有办法确认他收到的公钥 KT+ 是否真的属于 Alice.

这个漏洞引出了公钥基础设施 (PKI) 中的一个核心概念: 我们需要一个可信的第三方, 即证书颁发机构 (Certificate Authority, CA), 来签发数字证书 (Digital Certificates), 以此来证明某个公钥确实属于某个特定的实体.

数字签名¶

Bob 想发送一份已签名的消息 m. 他使用自己的私钥对消息 m 进行加密, 生成签名 KB-(m). 然后将原始消息 m 和签名 KB-(m) 一起发送. Alice 收到后, 使用 Bob 的公钥解密签名 KB-(m). 如果解密结果与原始消息 m 完全一致, 则验证通过. 这证明了消息确实是 Bob 签的, 且内容未被篡改.

直接对一个大文件 (如一个软件安装包) 进行公钥加密来签名, 速度非常慢. 因此, 实际操作中我们并不直接签文件本身, 而是签它的"指纹". 它能将任何长度的输入数据 (大文件 m) 转换成一个固定长度的, 短小的字符串, 这个字符串就是消息摘要或哈希值 H(m). 这个过程就像为文件生成一个独一无二的"数字指纹".

优化后的签名流程:

1. 签名: Bob 先用哈希函数计算出大文件 m 的摘要 H(m), 然后只用自己的私钥对这个短小的摘要进行签名, 即 KB-(H(m)).
2. 验证: Alice 收到文件 m和签名后, 她自己也用同一个哈希函数计算 m 的摘要, 得到 H(m). 同时用 Bob 的公钥解开签名, 得到另一个 H(m). 如果两个摘要完全一致, 验证通过.

什么是好的哈希函数:

1. 单向性 (One-way): 从消息 m 计算出哈希值 H(m) 很容易, 但从哈希值 H(m) 反推出原始消息 m 在计算上是不可行的.
2. 抗碰撞性 (Collision Resistance): 找到两个不同的消息 m1 和 m2, 使它们拥有相同的哈希值 (H(m1) = H(m2)) 在计算上是不可行的.

两个曾广泛使用的算法:

MD5: 生成 128 位的哈希值. SHA-1: 生成 160 位的哈希值.

尽管这些算法在历史上很重要, 但 MD5 和 SHA-1 目前都被认为是不安全的, 因为它们的抗碰撞性已被攻破. 在现代应用中, 应当使用更安全的替代算法, 如 SHA-256 或 SHA-3 系列.

CA¶

为了解决公钥的信任问题, 我们引入了一个所有人都信任的, 权威的第三方——证书颁发机构 (CA).CA 的作用: 它的唯一工作就是将一个公钥与一个实体 (如个人, 公司, 网站) 的身份进行绑定. 它就像网络世界的"身份认证中心"或"公证处".

证书签发流程:

1. Bob 带着能证明自己身份的材料和他的公钥 KB+ 去找 CA.
2. CA 在验证了 Bob 的真实身份后, 会创建一个数字证书.
3. 这个证书包含了 Bob 的身份信息和他的公钥 KB+.
4. 最关键的一步: CA 会用自己的私钥 KCA- 对这个证书进行数字签名. 这相当于 CA 以自己的信誉为 Bob 的公钥作了担保: "我, CA, 保证这个公钥确实是 Bob 的".

证书验证流程:

1. 当 Alice 想获取 Bob 的公钥时, 她会得到 Bob 的数字证书.
2. Alice 的电脑或浏览器通常预装了各大权威 CA 的公钥. 她使用 CA 的公钥 KCA+ 来验证证书上的签名.
3. 如果验证通过, 她就可以安全地从证书中提取出 Bob 的公钥 KB+, 并确信这个公钥确实属于 Bob.

安全电子邮件¶

1. 保密性

   这个过程采用的是我们之前讨论过的混合加密 (Hybrid Encryption) 方案, 以兼顾安全性和效率.

   • Alice 的操作 (发送方):

     1. 生成会话密钥: 创建一个临时的, 一次性的对称密钥 Ks.
     2. 加密邮件内容: 使用这个快速的对称密钥 Ks 加密邮件正文 m, 得到密文 Ks(m).
     3. 加密会话密钥: 使用 Bob 的公钥 KB+ 对会话密钥 Ks 进行加密, 得到 KB+(Ks).
     4. 发送: 将邮件密文 Ks(m) 和加密后的会话密钥 KB+(Ks) 一起发送给 Bob.

   • Bob 的操作 (接收方):

     1. 解密会话密钥: 使用自己的私钥 KB- 解密 KB+(Ks), 从而安全地获取到会话密钥 Ks.
     2. 解密邮件内容: 使用刚刚得到的会话密钥 Ks 解密邮件密文 Ks(m), 恢复出原始邮件 m.

2. 完整性

   目标: Alice 希望 Bob 能确认这封邮件确实是她发的, 并且内容没有被篡改. 这个过程使用的是数字签名 (Digital Signature).

   • Alice 的操作:

     1. 计算哈希: 对邮件正文 m 进行哈希运算, 得到一个摘要 H(m).
     2. 签名: 用她自己的私钥 KA- 对这个摘要进行加密(签名), 生成数字签名 KA-(H(m)).
     3. 发送: 将原始邮件 m (明文) 和数字签名一起发送给 Bob.

   • Bob 的操作:

     1. 验证签名: 收到后, Bob 用 Alice 的公钥 KA+ 解密数字签名, 得到 H(m).
     2. 自己计算哈希: Bob 也对收到的邮件正文 m 进行哈希运算, 得到另一个 H(m).
     3. 比较: 如果两个摘要完全一致, 则证明邮件确实是 Alice 发的, 且内容完好无损.

   注意: 这个过程只保证了认证和完整性, 邮件本身是明文传输的, 任何人都可以看到内容.

3. 保密性 + 完整性

   目标: Alice 发送的邮件, 既要保密, 又要能证明是她发的, 还要保证内容没被改过.

   这个过程就是将前面两个步骤完美地结合在一起.

   • Alice 的操作 (发送方):

     1. 签名: 首先, 按照目标二的方式, 对邮件 m 进行哈希并用自己的私钥 KA- 签名, 得到数字签名.
     2. 加密 (带签名): 接着, 将原始邮件 m 和她的数字签名打包在一起, 然后用一个新生成的对称会话密钥 Ks 对这个整体进行加密.
     3. 加密会话密钥: 最后, 用 Bob 的公钥 KB+ 加密这个会话密钥 Ks.
     4. 发送: 将最终的密文和加密后的会话密钥一起发送.

   • Bob 的操作 (接收方):

     1. 获取会话密钥: 用自己的私钥 KB- 解密, 得到会话密钥 Ks.
     2. 解密整体内容: 用 Ks 解密收到的邮件主体, 得到原始邮件 m 和 Alice 的数字签名.
     3. 验证签名: 最后, 按照目标二的方式, 用 Alice 的公钥 KA+ 验证签名是否有效.

   总结: 这个完整的流程一共用到了三把密钥:

   • Bob 的公钥 KB+: 用于加密会话密钥, 保证只有 Bob 能看.
   • Alice 的私钥 KA-: 用于签名, 证明是 Alice 发的.
   • 临时的对称密钥 Ks: 用于高效地加密邮件主体, 保证通信的保密性.

SSL¶

位置: SSL (Secure Sockets Layer) 是一个位于应用程序层(如HTTP, FTP)和传输层(TCP)之间的安全层. 你可以把它想象成在你的应用程序和互联网数据传输管道之间加了一个"安全保险箱".

作用: 它为上层应用提供了一个标准的编程接口(API). 这意味着程序员无需自己从头开始设计复杂的加密协议, 可以直接调用现成的C或Java等语言的SSL库, 就能让他们的应用程序实现加密通信, 大大简化了安全应用的开发.

需要满足的核心要求:

• 交换证书 (Certificate Exchange): 通信的双方需要一种方式来验证对方的身份. 这通过在协议的初始阶段(称为"握手"阶段)交换数字证书来实现.
• 建立共享密钥 (Set of Secret Keys): 为了加密后续的通信数据, 双方需要协商出一套只有他们自己知道的密钥. 这些密钥在整个连接期间有效.
• 传输通用数据 (Byte Streams & Interactive Data): 协议必须足够通用, 能够加密和传输任何类型的应用数据, 无论是文件下载还是实时交互数据.

流程:

1. 握手 (Handshake): 这是最关键的第一步. 通信双方(Alice和Bob)会互相交换证书, 并使用非对称加密(公钥/私钥)来验证对方身份, 并安全地协商出一个共享的初始秘密, 即"主密钥 (Master Secret)".
2. 密钥派生 (Key Derivation): 直接使用主密钥来加密所有数据是不安全的. 因此, 协议会使用一个"密钥派生函数 (KDF)", 将主密钥作为"种子", 生成一系列不同的会话密钥, 用于后续的数据加密和完整性校验.
3. 数据传输 (Data Transfer): 使用派生出来的会话密钥, 将应用程序数据分割成记录(records), 然后对每条记录进行加密和添加完整性校验后, 再发送出去.
4. 连接关闭 (Connection Closure): 使用特殊的安全消息来正式关闭连接, 以防止数据被意外截断.

如何在握手阶段共享主密钥(MS, Master Secret):

1. 客户端(Alice)向服务器(Bob)发起连接请求, 并发送自己的证书. 这个证书里包含了Alice的公钥.
2. 服务器(Bob)收到后, 自己生成一个随机的秘密数值, 这就是"主密钥"(MS).
3. 为了把这个MS安全地传回给Alice, Bob使用从Alice证书里获得的公钥对MS进行加密, 得到"加密后的主密钥"(EMS).
4. Bob将EMS发送给Alice.
5. 由于只有Alice拥有与公钥配对的私钥, 所以只有她能解密EMS, 从而获得MS. 至此, Alice和Bob就拥有了一个只有他们双方知道的共享秘密(主密钥), 而任何在网络上窃听的人都无法知道它是什么.

VPN¶

VPN利用公共互联网来传输机构间的内部流量, 并在数据进入公共网络前对其进行加密, 从而创建出一个既经济又安全的网络. IPsec是实现VPN的关键技术.

IPsec¶

IPsec是一种在网络层为IP通信提供安全服务的协议, 他可以在两个网络实体之间提供机密性, 并对所有的上层协议, TCP, ICMP等数据加密.

IPsec的两种工作模式:

• 传输模式: 端到端(主机到主机)的通信模式. 只加密和/或认证IP数据包的载荷(payload), IP头部保持不变. 主要用于保护上层协议的数据.
• 隧道模式: 将整个原始IP包(包括头部和载荷)进行加密和/或认证, 并将其封装在一个新的IP包中. 常用于网关之间(路由器到路由器)或主机到网关, 以保护整个内部网络流量. VPN通常使用此模式.

IPsec的两种核心协议:

• AH, Authentication Header, 提供源身份验证和数据完整性, 不提供机密性(即不加密数据).
• ESP: 提供源身份验证, 数据完整性和机密性. 由于功能更全面, ESP比AH应用得更为广泛.

总结¶

🌟 = remember.

奇偶检验¶

首先是单比特及奇偶校验, 1的个数永远是偶数, 即如果1的个数是奇数, 那么会校验比特就是1, 如果是偶数, 那么校验比特就是0. 还有一种是二维奇偶校验, 就是将数据按照行和列各做一次单比特奇偶校验. 使得每一行和列中的1的个数都是偶数.

CRC¶

十进制转二进制: 比如将13转为二进制, 是一个从上到下进行整除取余的过程. 然后将余数从下到上写出. 十进制转十六进制, 也是类似的, 除以16, A对应的是10, B对应的是11.

要了解CRC, 我们先要了解模2运算. 不同是1, 相同是0. 如11+00=11, 加法, 减法都是一样的. 例如11-01=10. 对于乘法, 是11*11=11*10+11*1=110(左移两位)+11=101. 对于除法来说, 里面的减法也是模二运算.

🌟CRC的操作: 假设数据是D, 选取一个G, 长度为r+1位, 我们将D左移r位, 得到D*2^R, 然后除以G, 将得到的余数R(长度为r)拼接到D的后面, 形成发送的数据T. 接收方收到T之后, 用G除以T, 如果余数是0, 说明数据没有错误; 如果不是0, 说明有错误. 其实去记那张图就好了.

多路访问协议¶

🌟随机接入协议分为ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA. Slotted ALHOA: 当一个数据想要发出的时候, 会等到下一个时间槽的开始, 将整个数据帧传输出去; 如果没有冲突, 则传输成功; 如果产生冲突, 必须要重传这个帧, 但是他不会立即在下一个帧进行重传, 而是以概率p决定是否重传. 直到该帧成功传输. 效率 = 成功传输的时隙 / 全部时隙. 假设有N个节点, 每个节点在一个时间槽内发送数据的概率是p, 那么, 在一个时间槽内, 尝试发送数据的节点符合二项分布, 那么效率就是这个时间槽内只有1个节点发送的概率.