网络层

网络层的功能

网络层的运行环境是网络中的 ISP 设备，网络层的主要功能是实现主机之间的通信。网络层的主要功能包括：

• 分组转发：网络层的主要功能是将分组源主机经过多个网络和多段链路传输到目的主机。在发送端，网络层将传输层的报文段封装成分组，并在每个分组中添加首部信息。在接收端，网络层将分组中的数据交付给接收方的传输层。
• 路由选择：网络层的另一个重要功能是路由选择。路由选择是指在网络中选择合适的路径，使分组从源主机传输到目的主机。路由选择是网络层的核心功能，它决定了分组的传输路径，直接影响网络的性能和可靠性。

网络层向上层提供了

• 面向连接的虚电路服务
• 无连接的数据报服务

路由算法

路由算法特指管理路由器中的路由表并作出路由决策的算法

面对的是无连接的数据报服务，因为在这样的服务当中，每一个路由器与主机之间的通信都是独立的，没有连接的概念，路由器只会根据邻近的路由器的信息来决定下一跳的路由器进行点对点（PPP）的链路发送。

而整体的发送方向由网络层算法决定，而不是链路层的协议。

因此，确定路由表的算法是网络层的核心算法。

静态路由算法

静态路由算法是指路由表是由网络管理员手动配置的，不会根据网络的拓扑结构和流量情况进行调整。

但是当网络的拓扑结构发生变化时，网络的流量情况发生变化甚至数据不断发送导致网络中每一条链路状况发生改变时，静态路由算法就会出现问题。

泛洪算法

泛洪算法是一种简单的路由算法，它的基本思想是：当一个路由器收到一个分组时，它将这个分组发送到所有的邻居路由器，除了发送方之外。

而每一个路由器都会将这个分组发送到所有的邻居路由器，直到这个分组到达目的主机。

但是泛洪算法会导致分组在网络中不断传播，直到网络中的所有路由器都收到这个分组，这样会导致网络中的分组数量呈指数级增长，最终导致网络拥塞。

同时，泛洪算法也会导致分组在网络中不断循环，导致多次接收，因此需要记录已经接收过的分组，避免重复接收。

但是也有一些优点

• 确保数据包能被送达目的地
• 非常健壮，就算出现故障，只要能到达目的地，就能找到路径

动态路由算法

动态路由算法是指路由表是由路由器之间自动交换信息而得到的，根据网络的拓扑结构和流量情况进行调整。

但是算法的复杂度较高，需要大量的计算和存储资源，而且需要大量的带宽来传递路由信息。

链路状态路由算法和距离向量路由算法是两种常见的动态路由算法。分别使用 Dijkstra 算法和 Bellman-Ford 算法。

距离向量路由算法

主要思想是分布式 Bellman-Ford 算法，每个节点维护一个距离向量，周期性地向邻居节点发送距离向量，根据邻居节点的距离向量更新自己的距离向量。（想知道详细思想请看 Bellman-ford 算法）

import copy
n, m, k = map(int, input().split())
edge = []
for i in range(m):
    edge.append([int(x) for x in input().split(" ")])

dist = [float('inf')] * 555
dist[1] = 0

for i in range(k):
    # 拷贝dist 防止串联
    backup = copy.deepcopy(dist)
    for j in range(len(edge)):
        a,b,w = edge[j]
        if dist[b] > backup[a] + w:
            dist[b] = backup[a] + w

if dist[n] == float('inf'):
    print("impossible")
else:
    print(dist[n])

整个网络最佳路径的寻找过程叫做收敛

其实本身 bellman-ford 算法没有问题，但是在网络中，如果突然有一个路由器宕机（距离变为\(+\infin\)），那么整个网络的路由表的估计最优距离到达不了断开的稳定状态

就是对于每一个路由器，都是一个计算单源最短路径的过程

链路状态路由算法

使用了分布式的 Dijkstra 算法，每个节点维护一个链路状态数据库

• 使用泛洪算法向所有路由器发送信息
• 发送与本路由器相邻的所有路由器的链路状态信息（包括路由器编号、链路的距离度量）
• 只有当链路状态发生变化时，才会发送链路状态信息

拥塞控制

拥塞控制通常出现在传输层、网络层中

从吞吐量的角度来看，输入的带宽大于输出的带宽，就会出现拥塞，这是理想的情况，但是实际上由于重传，小于带宽大小也会出现拥塞