网络层路由选择算法是要在源主机和目的主机之间找到一条最佳路径，以便使报文能够在互联网中从源主机传到所要通信的目的主机。
路由选择算法分类
- 理想的路由选择算法：
- 算法必须是正确的
- 算法在计算上要简单
- 算法应能适应通信量和网络拓扑的变化，即具有自适应性
- 算法应具有稳定性。在网络通信量和网络拓扑相对稳定的情况下，路由算法计算得出的路由也应该稳定，而不应使获得的路由不停地变化
- 算法应是公平的，即对所有用户都是平等的
- 算法应是最佳的
- 路由算法分类，按照算法能否根据网络的通信量或者拓扑自适应地调整来划分，可将路由选择算法分为两大类，即非自适应路由选择算法与自适应路由选择算法：
- 非自适应路由选择算法又称为静态路由，按照某种固定的规则来进行路由选择
- 自适应路由选择协议又称为动态路由协议，它根据网络拓扑结构以及通信量的变化改变路由，目前常用的自适应的分布式路由算法有距离向量算法和链路状态算法
- 距离向量算法又称为Ford-Fulkerson、Bellman-Ford或Bellman算法。这种算法的思想比较简单，每台路由器会周期性地与相邻路由器交换路由表中的信息。实现简单，但是不能适应大的网络环境。
- 链路状态算法又称为最短路径优先（Shortest Path First，SPF）算法。按照SPF的要求，路由器中路由表依赖于一张能表示整个网络拓扑结构的无向图G（V，E）。在无向图G中，结点V表示路由器，边E表示连接路由器的链路。在信息一致的情况下，所有路由器的链路状态图都应该是相同的。
- Dijkstra算法是典型的最短路径算法，用于计算一个结点到其他所有结点的最短路径。主要特点是以起始点为中心向外层扩展，直至扩展至终点为止。该算法能得出最短路径的最优解，但其效率较低。
- 路由协议
- 现在互联网的网络规模已经很大，无论单独使用哪种路由协议都不能完成全网的路由选择，所以通过引入自治系统（Autonomous System，AS）的概念将其划分为了很多个区域。
- 互联网中常见的路由选择协议按照工作范围的不同可以分为内部网关协议（IGP）与外部网关协议（EGP）
- 内部网关协议(Interior Gateway Protocol，IGP)即在一个自治系统内部使用的路由选择协议，如RIP和OSPF。
- 外部网关协议（External Gateway Protocol，EGP）中，若源主机和目的主机处在不同的自治系统中（这两个自治系统可能使用不同的内部网关协议），当数据报文传到一个自治系统边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议（EGP）。目前使用最多的外部网关协议是BGP的版本4（BGP-4）。
- 比较大的自治系统还可以将网络再次划分为多个小的自治系统。
路由信息协议
- 路由信息协议（Routing Information Protocol，RIP）是最著名、历史最悠久的动态路由协议，是第一个出现的内部网关协议（IGP），即在自治系统内实现路由选择功能
- RIP采用的是距离向量路由算法，同时为了能够较好地适应快速的网络拓扑变化，RIP规定了一些与其他路由协议相同的稳定特性：路由表更新定时器、路由超时定时器和路由表清空定时器
- 特点：仅和相邻路由器交换路由信息、交换的信息是当前本路由器所知道的全部路由信息，即自己的路由表、按固定的时间间隔交换路由信息
- RIP的两个版本：RIP-1是有类别路由协议，它只支持以广播方式发布协议报文；RIP-2是一种无类别路由协议
- RIP的工作原理：RIP作为一个系统常驻进程存在于路由器中，负责从网络系统的其他路由器接收路由信息，从而对本地网络层路由表做动态的维护；同时负责向相邻路由器广播本路由器的路由信息，通知相邻路由器做出相应的修改；RIP处于UDP的上层，RIP所接收的路由信息都封装在UDP的数据报文中。
- RIP优点：实现简单，开销较小；缺点：汇聚缓慢、路由表更新数据占用宝贵的网络带宽、缺乏动态负载均衡技术。因此，较小的网络中适合使用RIP，较大网络应该使用OSPF。
开放最短路径优先协议
- 开放最短路径优先（Open Shortest Path First，OSPF）协议是由IETF开发的基于链路状态（L-S）算法的自治系统内部路由协议
- 最短路径优先算法是OSPF路由协议的基础，每个路由器根据一个统一的链路状态数据库计算到达某个目的网络的最优路径。在OSPF协议中不使用UDP，而是直接用IP数据报文传送，可见OSPF的位置在网络层。OSPF构成的数据报文很短，这样就可以减少路由信息的通信量。而数据报文很短的另一个好处是不必考虑分片，在分片报文之中只要丢失一个，就无法组装成原来的数据报文，而整个数据报文就必须重传。
- 在OSPF协议中使用以下5种分组完成路由信息的更新：
- 问候（Hello）分组，用来发现和维持邻站的可达性。--路由器启动时
- 数据报描述（Data Description）分组，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息。--路由器启动一条新的通信链路时
- 链路状态请求（Link State Request）分组，请求对方发送某些链路状态项目的详细信息。--向其他路由器要求链路状态信息
- 链路状态更新（Link State Update）分组，用洪泛方法更新全网链路状态，这是协议的核心部分。--路由器在链路状态发生变化时
- 链路状态确认（Link State Acknowledgment）分组，对链路更新分组进行确认。
- RIP与OSPF协议进行一个简单的对比：
- 在RIP中，用于表示距离目的网络远近的唯一参数为跳数；对于OSPF路由协议，路由表中表示到达目的网络远近的参数不受物理跳数的限制，与网络中链路的带宽等相关
- RIP收敛较慢；OSPF路由协议即使是在大型网络中也能较快地实现收敛
- 在RIP中，网络是一个平面的概念，并无区域及边界等定义；OSPF路由协议，配合无类型域间路由CIDR，将一个自治系统划分为多个区域，更好管理网络
- OSPF路由协议支持路由验证，提高网络的安全性；OSPF路由协议对负载分担的支持性能较好，支持多条开销（cost)相同的链路上的负载分担。
边界网关协议
- 边界网关协议（BGP），BGP是不同自治系统的路由器之间交换路由信息的协议
- 自治系统间为什么不使用RIP、OSPF，而要使用BGP
- 互联网的规模太大，使用RIP，则互联网中众多路由器之间需要频繁地交换路由信息，将导致网络带宽被大量占用，RIP路由表收敛速度缓慢也将导致路由表不能及时反映当前的网络状况，当然也不能对收到的IP数据报文进行有效路由；使用链路状态协议，则每一个路由器必须维持一个很大的链路状态数据库，对于这样大的主干网用Dijkstra算法计算最短路径时花费的时间也太长；比较合理的做法是在自治系统之间交换“可达性”信息（即“可达”或“不可达”）
- 自治系统之间的路由选择必须考虑有关策略：政策、经济、安全
- 基于上述情况，边界网关协议（BGP）只能是力求寻找一条能够到达目的网络且比较好的路由，只要不兜圈子就可以，而并非要寻找一条最佳路由。BGP采用了路径向量路由选择协议，它与距离向量协议和链路状态协议都有很大的区别。
- BGP-4的4种报文：
- OPEN（打开）报文，用来与相邻的另一个BGP发言人建立关系，初始化通信。
- UPDATE（更新）报文，用来通告某一路由信息，以及列出要撤销的多条路由。
- KEEPALIVE（保活）报文，用来周期性地证实邻站的可达性。
- NOTIFICATION（通知）报文，用来发送检测到的差错。