计算机网络——网络层（2）
小程一言
我的计算机网络专栏，是自己在计算机网络学习过程中的学习笔记与心得，在参考相关教材，网络搜素的前提下，结合自己过去一段时间笔记整理，而推出的该专栏，整体架构是根据计算机网络方法而整理的，包括各大高校教学都是以此顺序进行的。
面向群体：在学计网的在校大学生，工作后想要提升的各位伙伴，
专栏链接: link
网络层——控制平面
概述
网络层的控制平面是指网络层中负责控制和管理网络路由的部分。它主要包括路由选择、转发表的更新、路由协议的运行和路由信息的交换等功能。
路由选择
负责根据网络中的拓扑结构和链路状态信息，选择最佳的路由路径来传输数据包。路由选择算法可以根据不同的需求和条件来进行优化，如最短路径、最小成本、最大带宽等。
转发表
网络设备中用于存储路由信息的数据结构，它会根据控制平面的指示不断更新，以确保数据包能够被正确地转发到目的地。
路由协议
网络层中常用的路由协议有RIP、OSPF、BGP等，它们负责在网络中传播路由信息，协调网络设备之间的路由选择和转发行为。
路由信息的交换
在复杂的网络环境中，不同的网络设备之间需要交换路由信息，以便彼此了解整个网络的拓扑结构和路由信息。这些路由信息的交换是由控制平面来管理和协调的。
小结
网络层的控制平面是网络中非常重要的一部分，它负责管理和控制整个网络的路由行为，确保数据包能够快速、可靠地传输到目的地。
路由选择算法
在计算机网络中，路由选择算法是指网络设备在收到数据包后，根据网络拓扑和链路状态信息选择最佳的路由路径进行数据包的转发。
常见的路由选择算法
距离矢量路由算法
距离矢量路由算法（Distance Vector Routing Algorithm）是一种分布式路由选择算法，用于在计算机网络中确定数据包的最佳路径。该算法基于每个节点维护一个距离向量表，其中包含到达其他节点的距离和下一跳信息。节点之间通过交换距离向量表来更新彼此的路由信息。
工作原理
- 初始状态：每个节点维护一个距离向量表，表中包含到达其他节点的距离和下一跳信息。初始时，节点只知道直接相邻节点的距离，而对于其他节点的距离则被设置为无穷大。
- 信息交换：节点周期性地将自己的距离向量表发送给相邻节点，并接收相邻节点发送的距离向量表。
- 更新距离向量表：当节点接收到相邻节点的距离向量表时，它会更新自己的距离向量表，并将更新后的表发送给其他相邻节点。更新的规则通常包括距离的累积和路径的选择。
- 路由选择：节点根据距离向量表中的信息选择到达目的节点的最佳路径。
- 距离向量表的更新：当网络拓扑发生变化时，节点的距禇向量表会相应地更新，以反映新的最佳路径。
优缺点分析
- 优点:简单易实现，适用于小型网络。
- 缺点: 慢收敛、计数到无穷问题和易受路由环路的影响。
链路状态路由算法
链路状态路由算法（Link State Routing Algorithm）是一种常用的路由选择算法，用于在计算机网络中确定数据包的最佳路径。与距离矢量路由算法不同，链路状态路由算法是基于网络中每个节点收集的全局拓扑信息来计算最佳路径。
基本工作原理
-
拓扑信息收集：每个节点定期广播自己的链路状态信息（包括与相邻节点的连接状态、成本等），并接收其他节点发送的链路状态信息。
-
构建网络拓扑图：每个节点根据收集到的链路状态信息构建网络的全局拓扑图，即描述整个网络结构的图，其中节点表示网络中的路由器，边表示节点之间的链路。
-
最短路径计算：使用最短路径算法（如Dijkstra算法）基于全局拓扑图计算出到达其他节点的最短路径，并更新节点的路由表。
-
路由选择：根据更新后的路由表，节点可以选择到达目的节点的最佳路径。
优缺点分析
- 优点：收敛速度快、能够避免计数到无穷问题、对网络拓扑变化的适应性强等。
- 缺点：需要大量的带宽来传输链路状态信息、对网络中的大规模拓扑信息处理较为复杂等。
链路状态路由算法
路状态路由算法（Link State Routing Algorithm）是一种基于全局网络拓扑信息的路由选择算法。它的主要思想是每个路由器都维护一个关于整个网络拓扑的全局视图，然后利用这个全局视图来计算出最佳路径。
工作原理
-
链路状态信息收集：每个路由器节点定期向其相邻的节点发送链路状态数据包，这些数据包包含了与相邻节点连接的链路状态信息，如带宽、延迟、可靠性等。同时，节点也会接收其他节点发送的链路状态信息。
-
构建网络拓扑图：每个节点根据收集到的链路状态信息构建网络的全局拓扑图，这个图描述了整个网络的结构，其中节点表示路由器，边表示节点之间的链路状态信息。
-
最短路径计算：基于全局拓扑图，每个节点使用最短路径算法（通常是Dijkstra算法）来计算到达其他节点的最短路径，并更新节点的路由表。
-
路由选择：根据更新后的路由表，节点可以选择到达目的节点的最佳路径，从而进行数据包的转发。
-
拓扑变化处理：当网络拓扑发生变化时，例如链路状态发生改变或有新的节点加入网络，每个节点都会重新计算最短路径，并更新自己的路由表。
优缺点分析
- 优点：收敛速度快、能够避免计数到无穷问题、对网络拓扑变化的适应性强等。
- 缺点：例如需要大量的带宽来传输链路状态信息、对网络中的大规模拓扑信息处理较为复杂等。
最短路径算法
在路由选择算法中，最短路径算法用于寻找网络中节点之间的最短路径。最常见的最短路径算法包括Dijkstra算法和Bellman-Ford算法。
Dijkstra算法
- Dijkstra算法用于计算从单个源节点到图中所有其他节点的最短路径。
- 算法使用了一种贪婪的策略，从源节点开始，逐步扩展到其他节点，直到找到到达所有节点的最短路径。
- Dijkstra算法维护一个距离数组dist[]，记录从源节点到各个节点的当前最短距离。同时维护一个集合S，表示已经找到最短路径的节点。
- 在每一步中，选择距离集合S最近的节点，并更新与该节点相邻的节点的距离值，直到所有节点都加入集合S。
- Dijkstra算法的时间复杂度为O(V^2)或O(ElogV)，其中V为节点数，E为边数。
Bellman-Ford算法
- Bellman-Ford算法用于计算从单个源节点到图中所有其他节点的最短路径，与Dijkstra算法不同的是，它可以处理存在负权边的图。
- 算法通过不断的松弛操作，更新节点之间的最短路径估计值，直到所有节点的最短路径被找到。
- Bellman-Ford算法的时间复杂度为O(VE)，其中V为节点数，E为边数。
最短路径小结
这些最短路径算法在路由选择中扮演着重要的角色，路由器可以利用这些算法计算出到达目的节点的最佳路径，以便进行数据包的转发。最短路径算法的选择取决于网络的特性，例如是否存在负权边等。
小结
路由选择算法的选择取决于网络的规模、复杂度、性能需求和安全性要求。不同的算法有不同的优缺点，例如距离矢量算法简单易实现但收敛速度慢，链路状态算法收敛速度快但占用资源多等。在实际应用中，需要根据具体的网络环境和需求来选择合适的路由选择算法。