计算机网络的核心功能
核心功能
- 互联：将不同类型的网络连接在一起，使得他们对传输层呈现统一的特征
- 编址：让主机/路由器的地址在网络中唯一，两个不同的设备永远不能有同样的地址
- 组包：将上层传输下来的数据封装为包，在互联网中由IP协议完成这项工作
- 分段：由于不同的数据链路层协议支持的最大数据长度不同，网络层需要能够将包分为不同长度的段
- 路由：决定将包送到哪一条，由路由器决定
本文的行文脉络也将根据核心功能的顺序展开~
对上层提供的服务
虚电路：面向连接的服务。需要先建立连接，然后选择路由节点。但是需要带一个VCI的标识，以便转发
数据报：面向无连接的服务，需要携带完整IP。
两种服务的对比：
路由
基本概念
1、最优化原则：如果节点J在节点I-K的最短路径上，那么J-K的最短路径也是I-K的最短路径的一部分，即最优路径上任意两点之间的路径也是最优的。
2、汇集树：以目的节点为根，所有源节点到目的节点的最优路径构成的数。(可以理解为是目的节点的路由表的树形表达)
3、泛洪(flooding)：将收到的包，发送给所有邻居。(一般用于路由表还没有完全建好的时候)
静态路由算法
由网络管理员手动设计，十分繁琐
动态路由算法
距离向量路由算法(DVR)
1、基于Bellman-Ford算法发展而成
2、Bellman-Ford算法的基本思想：
基于此，每个节点只需要维护以下数据：
- 从x到其每个直接相连的邻居的直接距离
- 节点x的距离向量(其到剩余所有节点的距离)
- 它收到的每个邻居的距离向量
3、算法运行过程：
1) 节点定期的向每个邻居发送他的距离向量副本
2)
节点每收到一个距离向量副本，就尝试运行Bellman-Ford算法更新自己的距离向量
3) 如果更新成功，立刻向所有邻居发送更新过的距离向量副本
4、问题：需要维护的表过于庞大，收敛速度慢
链路状态路由算法(LSR)
1、基于Dijkstra算法发展而成
2、中心思想是，每个路由节点需要知道其余所有路由节点的拓补信息，然后调用Dijkstra算法。
3、算法运行过程
1) 节点定期测试和它的所有邻居的距离
2) 将测试得到的距离通过泛洪发送给网络中的所有路由节点
3) 通过其余节点的信息，建立整个网络拓补图
4) 算出最短路径
4、问题：每次运行占用的网络资源过大
层次选路
1、其并非一种实际的算法，而是一个思想。即将网络划分区域，避免每次都需要获取整个网络的拓补。我只需要知道这个包需要发送到哪个区域，然后算出到那个区域的最短路径后，区域内再执行路由算法即可。
缺点：并非最优路径
拥塞控制
1、原因：资源不足，处理时间过慢等因素造成包阻塞
2、解决方案主要分为两种，一种是开源，一种是节流。开源类型的解决方案过于简单，不主要论述，主要就是增加网络供给和增加业务量感知路由
下面讨论节流类型的方法
流量限制
1、第一步：通过下面这个公式确定拥塞发生
2、第二步：通知发送方发生拥塞
3、第三步：发送方调整发送速率
对于第二步，通知发送方发生拥塞这一步，有两个方法
ECN显式拥塞通知：在发送过程中，只要有路由器检测到拥塞，就会对packet中特定的控制字段进行修改。然后如果在接收方接收到被修改过的packet控制字段，就会返回一个显式的信号给到发送方。
发送抑制分组通知：路由器向源主机以低速率发送抑制分组，原发生拥塞的包被标记，不会在后续的路由器产生更多的抑制分组。
负载掉落
说白了就是丢掉一些包。当包阻塞的时候，路由器直接就把他们扔了。
所以关键之处在于，该丢掉哪些包？
RED(早期随机检测)：当包的数量堆积超过阈值，那么此时开始随机丢包。
由于数据链路层协议的设计，此时接收方会收到连续的同一帧的ACK，所以隐式地通知了接收方一些包被丢掉了。
QoS参数
和第一章一样，但是这里不再以比特位单位，而是以包为单位
1、可靠性：包丢失率和包错误率
2、时延
3、抖动
4、带宽
综上，不同的服务对QoS有不同的要求，但核心问题在于，怎么改进QoS
流量整形法
现象：主机以不规律的方式发包，容易导致拥塞
漏桶算法
如图所示，Packet原来是以不同的速率发出的，但是在和实际网络拓补的接入点之间，插入了一个缓冲区，它像一个桶一样，接收所有的不规律速率的包，然后以一个标准的速率向外转发包。就像是打点滴的时候那个滴水的东西一样。这样就控制了流量的平滑性
令牌桶算法
令牌桶算法的过程是这样的，每隔一段时间，令牌桶中会以一个确定的速度产生令牌，每个令牌相当于一个“传输许可证”，缓冲区中的包只要有令牌，就可以往外传。如果此时的令牌是有冗余的，那么这个包就会以一个很快的速率往外传，如果没令牌了，立刻就会降速到令牌产生的速度。
以下为一个例子：
下面是考试的重点，要会计算经过令牌桶之后的突发数据的持续时间。公式：
其中，B是令牌桶中令牌的存量(单位为byte)，S是以最大速率运行的时间，R是令牌的产生速率，M是最大的输出速率。这个公式的意思是，令牌桶中存有的令牌数量，加上突发的时间到来的可以产生的令牌总量，要等于以最大输出速率输出的总字节数。
包规划法
来自不同流的包来到同一个路由器，路由器可以以不同的方式对待这些流量来增加QoS
FIFO
最简单的模型，先到的包先出
优先级队列 PQ
在原队列之外，设置一个优先级队列。用一个判断器，判断收到的包是重要的包还是不重要的，然后将包丢入对应的队列中。
系统空闲时，将优先处理高优先级的数据，让他们先发送。
但是这样会对低优先级队列不公平。
公平队列
路由器为每个流分配相应的队列，采用轮询的方式发送包。
但是根据mmr模型，这样会对小包不公平
公平加权队列
每个队列有不同的权值，在公平队列的基础上，对于权值高的队列，每次轮询到它的时候，就处理多次它的包。
下面这张图展示了公平队列模型的表格计算，基本必考。
公式说明：
这个公式的意思是，在上一个包的完成时间和这个包的到达时间中取最大值作为开始传输的时间，然后加上传输的总时间，即得这个Packet的传输完成的时刻。
如果您喜欢我的文章，可以考虑打赏以支持我继续创作.
