20220119-路由算法
路由算法
路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。路由器使用路由算法来找到到达目的地的最佳路由。
1. 传统路由算法
分类：①总体式路由算法；②分散式路由算法；
总体式（对应LS算法，链路状态）：每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。
链路状态算法【短路径优先算法】：把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述自己连接状态的部分；
适合情况：网络规模较大时，链路状态路由选择更可取些。另外，链路状态协议能够为安全起见把机密信息隔离在特殊区域，或避开网上正在进行计算机辅助计算、多媒体通讯等拥挤区域。并且路由选择信息表在必要时进行交换而不是规律性地交换，这样可以减少网络上的信息流量。链路状态路由选择比距离向量路由选择需要更强的处理能力，它可以对路由选择过程提供更多的控制和对变化相应更快。路由选择可以基于避开拥塞区、线路的速度、线路的费用或各种优先级别。Dijkstra算法用于计算路由，根据如下：
- 分组到达目的站经过的路由器数量（路由中继Hop），并且hop跳数越少越好；
- 局域网间传输线路的速度。有些路由使用低速异步链接，而另一些路由使用高速数字链路。
- 信息拥塞将造成延迟。如果一台工作站传送一个大文件，路由器可以通过不同的路径发送分组以避免交通阻塞。
分散式（对应DV算法，距离向量）：每个路由器只有与它直接相连的路由器的信息，没有网络中的每个路由器的信息。
距离向量算法【Bellman-Ford算法】：网络中每个路由器发送路由表的全部或部分，但只发给其邻居。距离向量路由选择协议的分组传送路由是根据到接收站的跳数或费用决定的，这些信息由各相邻的路由器提供。技术上通常都遵循Bellman-Ford算法。（一个路由器有几个端口，每个端口都有指定的价值，这些价值是由网络管理员设定的。用使用一条路线实际费用的多少，作为一种衡量手段表明一条路线比另一条好或坏。）通用距离向量路由选择协议由：RIP和IGRP。
不适合情况：不适合于有几百个路由器的大型网络或经常要更新的网络。在大型网络中，表的更新过程可能过长，以至于最远的路由器的选择表不大可能与其他表同步更新。它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近节点信息的改变实时更新的。
链接状态算法到处发送较少的更新信息，距离向量算法只向相邻路由器发送较多的更新信息。
收敛：在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。
核心：路由选择算法。设计路由算法时需要考虑的技术要素有：
- 选择最短路由还是最佳路由；
- 通信子网是采用虚电路操作方式还是采用数据报的操作方式；
- 采用分布式路由算法还是采用集中式路由算法；
- 考虑关于网络拓扑、流量和延迟等网络信息的来源；
- 确定采用静态路由还是动态路由；
各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链路状态与距离向量；
- 静态路由选择：路由器可以依赖人工编程把选择的路径输进设备。
- 动态路由选择：依靠路由器收集网络信息和建立自己的路由表。路由器相互交换路由表，并且归并这些路由信息建立更新的路由表。从其他路由器上获得的信息，提供到网络上目的站点的路由终极数或与路径相关的费用。同时每个路由选择设备上的路由表，应该包含大体上一致的路由选择信息。
metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度；
路由选择协议：当两台非直接连接的计算机需要经过几个网络通信时，通常就需要路由器，路由器提供一种方法来开辟通过一个网状联结的路径。路由选择协议的任务是：为路由器提供他们建立通过网状网络最佳路径所需要的相互共享的路由信息。当一个计算机发送一个分组时，在网络上网络协议栈的每一层都附加一些信息给它。在接收方的对等层协议可以读出这些信息。这些信息类似于通信会话的某些部分。网络层的协议附加路由选择信息，这可能是通过一个网络的完整路径或是一些指示分组应该采用哪条路径的优先值、发送方添加的网络层信息只能由路由器或接收方的网络层协议读取。中继器和桥接器不能识别网络层信息，只能传送和转发分组。
路由选择算法：一个路由器设备可能有两个或多个可以发送数据分组的端口。它必须有一张转发表为每一个端口标明一个特定地址。早期路由器不和其他路由器交换网络上有关路由器的信息，因此一个路由器通常沿着每条路径发送数据分组，分组充满网络，并且发送的一些分组在网络上无休止地循环。
路由的费用：通常是根据传输介质确定的。最便宜的路径可能不是最快的，但是对某些类型的传输却更为可取。最常用的链路状态路由选择协议是优先开放最短路径（OSPF），它和OSI的中间系统到中间系统是类似的。OSPF路由选择表仅当在需要时更新，而不是定时更换。这有效地较少了通信流量和节省了网络带宽。通过网络的路径由上述标准选定。一个网络管理员可以根据信息传送的类型编制通过网络的路径。例如，当路线有较高数据传输率时，即使通过网络的那条路径有较多的HOP数也是可取的；此外对于不重要的信息将安排在低速低值的线路上传送。
自治环境：一个区域是一些使用相同路由选择协议的主机和路由器的集合，它们使用相同的路由选择协议和由单一机构管理。
内部/域内协议
外部/域间协议
2. 卫星网络路由
早期：快照技术，基于虚拟拓扑的集中式路由机制；
改进算法：
由于卫星网络内部的星间相对位置通常相对固定，一部分工作提出基于虚拟节点的分布式路由机制。基于已知的星间相对位置的信息，根据星上存储的预先计算生成的映射表选择转发接口，或者邻居之间交换位置信息和移动方向信息，比较邻居距目的地址绝对距离得到下一条路由。
- 优点：避免了基于虚拟拓扑的集中式路由机制存在的路由表存储开销巨大的问题；
- 弊端：由于卫星高速运动，卫星与用户之间切换频繁，获取落地卫星标识会产生大量的位置更新开销。此外由于卫星位置具有时变性，部分解决方案需要邻居间定期交换状态信息。随着卫星星座规模的增大，邻居间消息交换愈发频繁，导致卫星网络中带宽资源浪费严重。
现有地面基于IP的分布式路由协议迁移应用能充分发挥地面互联网的优势，但是现有的分布式IP路由协议主要是针对地面互联网设计，其拓扑基本稳定，这导致协议对一体化网络链路连接关系高动态变化场景应对不足，路由频繁更新使协议可用性受到极大影响。相应的改进算法，尝试利用卫星周期运行规律，引入预测信息，优化一体化网络路由机制设计，如OSPF+、BGP+等。
- 缺点：规模增大使得需要预测的指标增多，对卫星存储能力和计算能力提出了更高的要求，频繁的消息交换也给卫星能耗带来更大挑战。
基于位置的天地一体化网络路由寻址机制：创新之处在于以下方面：
- 不需要通过获取邻居信息计算下一跳，仅 需要从IP地址中获取目的地址的位置信息来计算方位，由选择算法计算得到的卫星自身最优的接口直接进行数据分组转发。同时算法结合传统路由表查找机制的优势，提出星上临时路由表的概念，将分布式计算结果存储到路由表中，当卫星与目的地址相对位置发生改变时，更新临时路由表。临时路由表使LA-ISTN对于连续数据传输支持度更高。
路由机制：
LA-ISTN：
- 算法1：首先查找临时路由表，若查找成功，将数据分组从路由表中记录的接口转发给目的用户；否则选择对应最小接接口方向角的转发接口，将数据分组从该接口转发给下一条邻居卫星节点。
- 由于单颗卫星的计算能力不足，卫星接口方向角的获得和计算开销对此类卫星网络压力大，因此引申出算法2；
- 算法2：利用星间邻居相对位置来选择转发接口——目的地址与卫星的相对方位根据目的IP地址中记录的位置信息计算得到。它将复杂的接口选择问题转化为选择轨内星间链路或轨间星间链路转发的问题。考虑不同维度轨间星间链路的长度有区别，在选择最优转发接口时：
- 若目的地址相对当前卫星处于较高纬度，优先轨内转发；
- 若目的地址相对当前卫星处于较低纬度，优先轨间转发；
临时路由表：星上存储临时接入当前卫星的终端路由信息和LA-ISTN生成的路由表项。当卫星与目的地址的相对位置发生改变时，清除当前路由表项信息，以保证临时路由表中记录始终是有效的。
机理分析：
- 最后一跳寻址可达性分析：分布式位置路由算法存在不可达问题在于路由的最后一条。卫星覆盖区域重叠导致用户节点位于当前卫星覆盖范围内但并未接入当前卫星的情况发生。在LA-ISTN中，寻址机制将继续选取靠近目的位置的接口方向进行转发。
- 轨间链路断开及拼缝位置寻址可达性分析
- 开销分析
- 性能分析
《Loop-Free Hybrid Single-Path/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks》
想法：
- 选择方向角最小的那个，但是不知道原因orz
- compass routing, 选择与当前节点的夹角和当前节点和目的节点夹角最小的节点；
- MFR (most forward within radius)
- distance, progress, and direction-based approaches
- 蚁群算法：分布计算、信息正反馈、启发式搜索特征，本质是进化算法中的一种启发式全局优化算法。和传统的路由算法相较，该算法在网络路由中具有信息分布式性、动态性、随机性和异步性等特点，而这些特点正好能满足网络路由的需要。