路由算法#

静态配置路由#

程序员手动配置路由表

软件定义路由#

• openflow协议

动态配置路由#

层次化路由#

概念#

AS（Autonomous System）,网络世界中的自治邦国

IGP（Internal Gateway Protocol）内部网关协议#

• RIP
• OSPF

EGP（External Gateway Protocol）外部网关协议#

• BGP（Border Gateway Protocol）

RIP（Router Information Protocol）#

• UDP端口号520
• 理论基础 ford算法
• 维护的状态 距离向量（节点到其他节点的距离，包括自己节点和邻居节点）
• 距离 到目标网络的跳数，RIP允许一个路径最多包含15个路由器，跳数为16表示不可达，距离向量算法可能出现环路，规定跳数上限避免循环, 直接到达算距离为1

特点#

1. 简单
2. 报文大小与节点数量正相关，不利于大型系统
3. 分布式路由算法：以迭代的、分布式的方式计算最低费用路径
4. 好消息收敛快，坏消息收敛慢

分组类型#

• Request
• Response

OSPF（Open Shortest Path First）#

• 理论基础 dijk
• IP协议号是89
• 大致流程
  • 定期检查邻居状态，更新相邻链路信息
  • 定期把自己的相邻链路信息广播给整个网络的全部节点
  • 当自己收到链路状态报文时，更新自己的全局链路拓扑图，一旦状态发生变化就用dijk算法更新路由表
• 洪泛（广播） 自己相连的链路状态
• 没有定期交换信息的机制与RIP#定时交换信息不一样
• 同#链路状态方法（Link State）
• 代价的定义不是基于跳数
• 对于不同类型的业务可以定义不同的代价，以实现QOS
• 当到目的网络有多条相同代价的路径可以把分组在多条路径间负载均衡
• 支持鉴权，从而只在可信的路由器上交换链路状态信息
• 支持可变长度子网划分和cidr
• 序号机制，序号越大分组传递的状态越新
• 特点
  1. 是全局路由算法，所有路由器拥有完整的网络拓扑信息和链路费用信息
  2. 没有慢收敛问题，对坏消息响应迅速
  3. 存储空间开销 维护全局状态
  4. 拓扑变化都要重新计算最小代价树开销大
  5. 适合大型系统

分组类型#

• Hello 发现邻居与保证可达性
• Database Description 传递链路状态的摘要信息
• Link State Request 请求数据库某些项目的详细信息
• Link State Update 用洪泛法对整个网络同步链路状态
• Link State Acknowledgement 对更新分组的确认

在网络中通常传送的 OSPF 分组大多是问候分组。两个相邻路由器通常每隔 10 秒要交换一次问候分组，以便知道哪些站可达。若有40秒没有收到某个相邻路由器发来的问候分组，则以为该相邻路由器不可达，应立即修改链路状态数据库，并重新计算路由表。 在路由器刚开始工作时，OSPF 让每个路由器使用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。然后，路由器使用链路状态请求分组，向对方请求发送自己所换少的某些链路状态项目的详细信息。经过一系列的这种分组交换，就建立了全网同步的链路数据库。 在网络运行的过程中，只要一个路由器的链路状态发生变化，该路由器就要使用链路状态更新分组，用洪泛法向全网更新链路状态。其他路由器在收到更新分组后要发送确认。 为了确保链路状态数据库与全网的状态保持一致，OSPF 还规定每隔一段时间（如30分钟）要刷新一次数据库中的链路状态。因为一个路由器的链路状态只涉及与相邻路由器的连通状态，与整个网络的规模并无直接关系，所以当互联网规模很大时，OSPF 要比RIP好得多

区域划分#

BGP#

• TCP端口号179
• BGP Speaker
• BGP对等体
  • 对等体（Peer）
  • 若干相关的对等体可以形成对等体组（Peer Group）

过程#

• 与其他AS的邻站BGP发言人交换信息
• 交换的网络可达性的信息，即要到达某个网络所要经过的一系列AS
• 发生变化时更新有变化的部分 实际上，BGP交换的是各个发言人所掌握的路径向量。

特点#

• BGP支持CIDR，因此BGP的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的 各个自治系统序列
• 在BGP刚刚运行时，BGP的邻站是交换整个的BGP路由表。但以后只需要在发生变化时更新有变化的部分。这样 做对节省网络带宽和减少路由器的处理开销都有好处

BGP-4报文类型#

• OPEN（打开）报文
  • 用来与相邻的另一个BGP发言人建立关系，并认证发送方。
• UPDATE（更新）报文
  • 通告新路径或撤销原路径
• KEEPALIVE（保活）报文
  • 在无UPDATE时，周期性证实邻站的连通性
  • 也作为OPEN的确认
• NOTIFICATION（通知）报文
  • 报告先前报文的差错
  • 也被用于关闭连接。
• 对比OSPF

两类会话#

• eBGP 从邻居AS获取子网可达性信息.
• iBGP 向所有AS内部路由器传播子网可达性信息.

路由选择#

• 每条 BGP 路由包含3个组件： NEXT-HOP（是 AS-PATH 起始的路由器接口的 IP 地址）; AS-PATH; 目的前缀。在实践中，一条BGP路由还包括其他属性，眼下我们将暂且忽略它 - 热土豆路由选择（从所有可能的路由中）选择的路由到开始该路由的NEXT-HOP 路由器具有最小开销（链路长度）
• 路由器选择算法