北京大学计算机网络路由选择及算法

1、 第十讲计算机网络路由选择及算法 路由选择算法Array主要内容路由基本概念静态路由算法距离矢量算法链路状态算法阅读 路由选择概述 路由器的内部结构 路由选择算法 路由算法的分类 非自适应算法 不根据实测或估计的网络的当前通信量和拓扑结构来作路由选择。 自适应算法根据拓扑结构、通信量的变化来改变其路由选择。 9可提高网络性能 有助于拥塞控制路由决策复杂依赖于状态信息 不能太快和太慢路由算法的设计目标对随时出现的局部网络故障和负载变化迅速作出反映,理想情况下不丢失包和中断虚电路。 不管运行多长时间始终稳定; 在路由变化期间包可能循环通过网络,要解决; 路由处理和传输的开销应小于基于某种度量获得的

2、好处。 10正确性(correctness 简单性(simplicity 健壮性稳定性最优性(optimality 公平性(fairness 有效性(efficiency路由技术元素 11 路由性能标准 12 目标端13 节点1到节点6的最短路经是1-3-6,路径长为10;节点1到节点6的最小成本路径是1-4-5-6,路径成本4;14 路由决策时间与地点决策时间内部数据报:为每个包单独作路由决策内部虚电路:当建立虚电路时作路由决策决策地点分布式路由每个节点都负责为到达的包选择一条输出链路集中式路由15 由某些指定节点(如网络控制中心负责决策源路由路由决策由源站点而非网络作出16网络信息源和更新

3、时间 路由信息需求 无信息(扩散法 局部信息其他信息源(邻接节点,全部节点 从不更新信息 固定策略不时更新信息自适应策略静态路由算法最短路径选择测量路径长度的方法 最小跳计数 最短距离 信道带宽 传输延迟 平均通信量 Dijkstra子网图节点代表路由器 弧线代表两个路由器之间的一条链路 初试化测量每一条链路的长度 选择当前工作节点A(, -标值其他节点到源的距离Dijkstra 算法迭代(1/3 选择当前工作节点E(, - 标值其他节点到 选择当前工作节点 B标值其他节点到 源的距离 Dijkstra算法迭代(2/3 (, - 标值其他节点到源的距离 选择当前工作节点 G标值其他节点到源的距

4、离 选择当前工作节点 F( , - Dijkstra算法迭代(3/3选择当前工作节点H 标值其他节点到源的距离选择当前工作节点C 标值其他节点到源的距离 (10, H 从目标节点倒着往前推即可获得从源节点到当前节点的一条最短路径。 (10 , H 扩散法(flooding 扩散法的特性优点尝试所有可能路由至少有一个包通过最小跳路由到达所有与源节点连接的节点都被访问健壮性 建立虚电路广播重要信息 每个节点接收来自与其直接邻接节点的路由信息执行路由计算 将计算结果回传给直接邻接的节点迭代的(iterative计算过程循环进行直到相邻节点没有可交换的路由信息为止异步的(asynchronous 并不

5、要求所有节点相互锁步操作距离矢量算法距离 其中w 为Z 的所有直接邻居(包括X考虑X 经直接邻居Z 到达Y 距离矢量算法距离矩阵 D E ( A ,D = c(E,D +D D ( A , w = 2+3 = 5 距离矢量算法的数据结构主要数据结构每个节点维护的距离表(distance table。一个节点能得到的信息与其直接相连链路的成本Array来自邻接节点的路由信息DV算法用估算延迟作为性能指标基于Bellman-Ford算法 2 for all adjacentnodes v:3 D X(*, v = 4 D X(v, v = c(X, v5 for all destinations,

6、y 表中到邻居的距离设置成链路成本; 把距离表中到非邻居的距离设置成无穷大; 把到所有目的地的距离信息发给每个邻居6 send min w D(y, w to each neighbor/* w over all X's neighbors */78 loop9 wait (until I see a link cost change to neighbor v10 or until I receive update from neighbor v 11 12 if (c(X,v changesby d X到邻居v的距离发生变化d13 /* change cost to all des

7、t's vianeighbor v by d */14 /* note:d could be positiveor negative */15 for all destinations y: D X(y,v = D X(y, v + d16 17 else if (update received fromv wrt destination y35 18 /* shortest path fromv to some y haschanged */19 /* v has sent a new value forits min w D V(y,w */ 20 /* callthis rece

8、ived new value is"newval" */21 for the single destination y:D X(y, v = c(X, v + newval22 23 if we have a new min w D X(y, wfor any destination y24 send new value of min wD X(y,w to all neighbors36 25 26 forever 最左列为x, y, z初始化后的距离表37 X收到来自y, z的更新信息后,重新计算距离表收到Z的消息后 收到y的消息后 X计算出D x(z,y=3需要通知邻

9、居 38 39 链路成本变化对算法的影响 X YXD Z 550 X ZX DY4 6X ZX DY1 6X ZXDY31 假设 x y 链路的成 本由 4 下降为 1 无穷计算问题 假设 x y 链路的成 本由 4 上升为 60 C(X, Ychangedtime t0 t1t2 t3 t4Y的距离表Y 的距离表 X Z X DY 4 X Y X DZ50 5C(X, Ychanged timet0t1t2 t3 t4 50 Z的距离表 X Z X DY 4 -X YX D Z 550 染毒反向法的局限 A 通知C 到D 的距离为;B 通知C 到D 的距离为; 当C-D 链路失效后,C 到D

10、 不可达; A 选择经过B 到D 且距离为3 C C 选择经过A到D且距离为4 B B选择经过C到D且距离为5 A链路状态路由算法(LS LS算法特性每个节点都有网络的完整拓扑;每个节点维护到每个邻居的连通性与链路成本;例如:节点每10秒计算每条出境链路的平均延迟节点向网络中所有其他节点广播自己和邻居的连接信息;每当接收到来自其他节点的信息时用Dijkstra算法重新计算路由表;通常采用延迟作为性能标准;能消除慢速收敛的问题; LS路由算法方法延迟计算方法(在每个节点发出去的包被盖上时间戳,记录其离开时间;收到返回的肯定确认时,计算该包的延迟;收到返回的否定确认时,更新包的离开时间; Dijk

11、stra 算法计算从一个节点(源,假设为A到网络中所有其他节点的最小成本路径。算法迭代进行;经第k次迭代后,就能找到到k个目标节点的最小成本路径。 1 Initialization:2 N = A3 for all nodes v4 if v adjacent to A5 then D(v = c(A,v6 else D(v = 78 Loop :将到A的邻居的距离标记为链路成本;9 find w not in N such that D(w is a minimum10 add w to N选择距离值最小的w,更11 update D(v for all v not in N:新所有w邻居的距离值。 12 D(v = min( D(v, D(w + c(w,v 13 /* new cost to v is either old cost to v or known14 shortest path cost to w plus cost from w to v */15 until all nodes in NLS算法初始化假设C(i,j:从节点i到j的成本D(v:从源节点到目标节点v的当前最小成本48 P(