网络路由选择.pdf.PDF

网络路由选择 ——Dijkstra路由算法 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 1 内容提要 • 网络路由概述 • Dijkstra路由算法 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 2 网络路由概述 • 路由是指路由器从一个接口上收到数据包， 根据数据包的目的地址进行定向并转发到另 一个接口的过程。 • 路由算法初始化并维护包含路径信息的路由 表，路径信息根据使用的路由算法不同而不 同。 • 路由算法根据许多信息来填充路由表。 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 3 网络路由概述 • 路由工作包含两个基本的动作： 1、确定最佳路径：根据目标地址和路由表 内容，进行路径选择。 2、数据交换：根据选择的路径，将接收到 的数据包,转发到另一个接口（输出口） 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 4 网络路由概述 传统的路由选择算法： •根据整个网络拓扑和各链路长度，通过求给定 网络中两个节点之间的最短通路得出所选择的 最佳路由。 •计算简单，相对稳定，但没有考虑带宽等因素。 •适用于小规模的较固定的网络，且将吞吐量和 平均延时作为网络的主要性能指标。 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 5 Dijkstra路由算法 经典的求最短路径路由算法——Dijkstra算法 •条件：已知网络的拓扑和各链路的长度 •通过计算任意两节点间的最小链路长度，求得 从源节点到目的节点间最短通路。 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 6 Dijkstra路由算法 • 基本思想 • 设置顶点集合S并不断地作贪心选择来扩充这个集合。一 个顶点属于集合S当且仅当从源到该顶点的最短路径长度 已知。 • 初始时，S 中仅含有源。设u是G的某一个顶点，把从源到 u且中间只经过S 中顶点的路称为从源到u的特殊路径，并 用数组dist记录当前每个顶点所对应的最短特殊路径长度。 • Dijkstra算法每次从V-S 中取出具有最短特殊路长度的顶点 u，将u添加到S 中，同时对数组dist作必要的修改。一旦S 包含了所有V 中顶点，dist就记录了从源到所有其它顶点之 间的最短路径长度。 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 7 Dijkstra路由算法 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 8 Dijkstra路由算法 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 9 Dijkstra路由算法 • Dijkstra算法可推广： • 若将已知的各链路长度改为链路时延，跳数， 带宽或费用，就相当于求任意两节点之间具 有最小时延，最小跳数，最大带宽或最小费 用的通路。 • 求最小路径的算法应用范围很广。 湖南大学信息科学与工程学院 /coursestatic/course_2799.html 10 Dijkstra路由算法 • 关于最短路径问题, 目前所公认的最