网络层的路由算法概述

概念

什么是转发？

分组到达, 取出目标地址,查看转发表, 将分组转发出去 一个节点的局部操作

什么是转发表？

转发表的每一行必须包含从要到达的目的网络，到输出端口和某些MAC地址信息（如下一跳以太网地址）的映射。

什么是路由？

根据分组中包含的信息（目标地址）找到转发路径，是建立路由表的过程，要使用路由算法 

• 数据报的路由 每一个到达的分组  
• 虚电路的路由 建立虚电路时 会话路由：会话期间，一直保持

什么是路由表？

网络号到 下一跳 (IP addresses)

不同于数据链路层

• 转发表的格式不同
• 转发表的更新方法不同

回忆一下数据链路层是啥样子的呢？

• 转发表

• 目标的物理地址和转发的端口号

• 表的更新

• 手工配置
• 反向学习 

@H_696_96@

@H_302_6@mAC

@H_696_96@

Port#

@H_696_96@  @H_696_96@  @H_696_96@  @H_696_96@  @H_696_96@  @H_696_96@ 

而网络层是这样的：

• 转发表

• 目标网络到下一跳地址(or 接口)

• 表的更新

• 直接连接
• 手工配置 (static routE)

• 通过路由协议（dynamically route）

NetNum	NextHop/Interface#

 

目标

Correctness(正确性) Simplicity (简单性) Robustness (健壮性) Stability (稳定性) Fairness (公平性) Optimality (最优性) 

分类

• 静态路由算法 根据网络初始状态进行路由选择 不能适应网络拓扑的变化

• 手工配置转发表 

• 动态路由算法

• 根据网络当前信息量和拓扑结构进行路由选择

• 周期更新
• 对链路通信代价变化及时响应

• 需要路由协议 交换信息  

优化原则

优化原理 ：如果路由器 J 在从路由器 I 到 K 的最佳路径上 则从 J to K 的最佳路也在同一路上 

从所有源到给定目标的最佳路由的集合称为汇集树 (sink treE)

路由算法的目标就是 discover the sink tree for all router