介绍路由算法等。

路由算法

转发表确定路由器如何转发分组，路由算法确定去往目的地的最佳路径。（最短路径问题）

分类：

  • 静态路由：手工配置，路由更新慢，优先级高（反映人的具体需求）
  • 动态路由：路由更新快，一般定期更新，及时响应链路费用或者网络拓扑变化
  • 全局信息：每个路由器掌握完整网络拓扑和费用信息，如链路状态（LS）路由算法
  • 分散信息：路由器只掌握物理相连的邻居以及链路费用，通过邻居路由器之间的信息交换和迭代，如距离向量（DV）路由算法

链路状态路由算法

Dijkstra算法

所有结点掌握网络完整拓扑信息和链路费用，通过链路状态广播

距离向量路由算法

Bellman-Ford方程（动态规划）

层次路由

聚合路由器为一个区域：自治系统（AS），同一AS内的路由器运行相同的路由协议，不同自治系统可以选择不同的路由协议

网关路由器（gateway router）：位于AS边缘，与其他AS的网关路由器交换AS的信息

转发表由AS内部的路由协议和AS之间的路由协议共同确定

热土豆路由：将分组发送给最近的网关路由器

Internet路由

Internet采用层次路由

AS内部路由协议称为IGP（内部网关协议，interior gateway protocol），如RIP（路由信息协议，Routing Information Protocol）、OSPF（开放最短路径优先，Open Shortest Path First）、IGRP（内部网关路由协议，Interior Gateway Routing Protocol，思科私有协议）

RIP协议

距离向量路由算法

  • 距离度量：跳步数，每条链路一个跳步，最大有效路由为15
  • 每隔30秒，邻居之间交换一次DV，称为通告
  • 每次通告最多25个目的子网（IP地址形式）

OSPF协议

开放：公众可用

采用链路状态路由算法