基于QoS的分布式路由算法的研究

　第 14 卷 第 3 期 　2006 年 6 月 安徽建筑工业学院学报 (自然科学版 ) Journal of Anhui Institute of Architecture & Indust ry Vol. 14 No . 3 　 J un. 2006 　 　　 收稿日期 :2006203223 基金资助 :安徽省教育厅自然科学基金资助课题 (2004kj096) 。 作者简介 :沈庆伟 (1967 - ) ,女 ,副教授 ,硕士 ,主要研究方向为计算机网络技术。 基于 Qo S 的分布式路由算法的研究 沈庆伟 (安徽建筑工业学院计算机与信息工程系 合肥　230022) 摘　要 :随着网络应用的不断增长 ,现有的路由算法难以满足用户的多 QoS 要求。本文在分析了经典路由算 法的基础上 ,介绍了一种通用的分布式 QoS 路由算法并详细阐述了几种具有不同 QoS 度量的具体的分布式 路由算法的实现。 关键词 :路由算法 ;分布式路由算法 ;QoS 中图分类号 : TN913. 2 　　　文献标识码 :A 　　　文章编号 :100624540 (2006) 032062205 Research on distributed routing algorithm based on QoS SH EN Qing2wei (Depart ment of Computer and Information Engineering , Anhui Institute of Architecture & Indust ry , Hefei 230022 , China) Abstract :Along wit h t he develop ment of network , existing routing algorit hm can’t satisfy wit h t he multi2QoS demand. Based on analyzing t he classic dist ributed routing algorit hm , this paper int roduces a general dist ributed QoS routing algorit hm and describes the realization of a few concrete algorit hms on species QoS met rics. Key words :routing algorit hm ; dist ributed routing algorit hm ; QoS 　　计算机网络飞速发展 ,网络上信息类型和信 息流量呈几何级数增长 ,特别是各种多媒体应用 程序的使用 ,使得传统的 Internet“尽力而为” (Best Effort ) 服务机制难以满足网络用户的需 求。随着宽带网络的出现和分布式多媒体应用对 端到端服务质量保证要求的增加 ,对网络服务质 量 (QoS)路由的研究逐步发展起来。 路由包括两个基本功能 :一是搜集网络的状 态信息并不断更新 ;二是根据所搜集的信息计算 可行路径。QoS 是网络在传输数据流时要求满 足的一系列服务请求 ,具体可量化为带宽、时延、 时延抖动等 ,它用来刻画服务提供者与用户间用 数量或质量来定义的性能约定。QoS 路由不同 于传统 IP 网络仅仅提供尽力而为的路由 ,它是面 向连接、有资源预留功能 ,并且提供有质量保证的 服务。因此 ,有必要对现有的路由算法进行改进 , 提出新的路由算法。 分布式路由算法的基本思想是各个节点独立 的计算最短路径 ,每个节点并不需要详细的网络 拓扑信息 ,只需要知道到达某一节点的路径长度 (时延 ,跳数等) 。其优点是能够适应网络拓扑变 化和网络业务流量变化 ,时间复杂度底。本文介 绍的 QoS 路由算法是分布式的基于本地拓扑和 状态信息的无路由环路通用路由算法 ,它可以用 于开发各种具体的满足某些特定约束条件的路由 算法。通过设定具体的转发条件和用于计算探测 等待时间的具体公式 ,新算法可以方便的由通用 算法得到。 1 　基本路由算法 传统的数据网中 ,构造路由表可以使用集中 式的算法 (如 Dijkst ra 算法) 或者分布式算法 (如 距离矢量算法和链路状态算法) 。 1. 1 　最短路径路由算法 有两种算法可以求出加权图中的最短路径 , 一种是 Dijkst ra 法 ,另一个是 Ford 和 Fulkerson 算法。 Dijkst ra 算法可以求出从一点到其他点的最 短路径 ,它需要有整个网络的拓扑知识 ,就是网络 中全部节点的互相连接情况以及每条链路的费用 (权重) 。因此在集中式路由选择中使用较多。 Ford 和 Fulkerson 算法求得的结果是某节点距 离源节点的最短距离以及沿最短路径通向的下一 个节点。此算法多用于分布式路由选择。 1. 2 　距离矢量路由算法 在距离矢量路由算法中 ,每个路由器维持有 一张子网中每一个以其他路由器为索引的路由选 择表 ,表中的每一个项目都对应于子网中的每个 路由器。此表项包括两个部分 ,即希望使用的到 达目的地的输出线路和估计到达目的地所需时间 或距离。距离度量标准可为跳数、时延、路径排队 长度或者类似的值。如果度量标准为跳数 ,则其 距离为一跳 ;如果度量标准是队列长度 ,则路由器 会简单地检查每个队列 ;如果度量标准为时延 ,则 路由器可直接发送一个特别“响应”分组来测出时 延 ,接收者只对它加上时间标记后就尽快返回。 1. 3 　链路状态路由算法 每条链路具有 - 套有关 QoS 度量准则的被 测量状态。链路状态是一个包含剩余带宽、时延 和代价的三元组。节点也有状态信息 ,节点的状 态信息可以单独地测量出来 ,或者合并到相邻链 路的状态中。链路状态路由算法的工作流程 : (1) 每个路由器发现它的邻居节点 ,并知道 其网络地址 ; (2) 测量到各邻居节点的延迟或者开销 ; (3) 组装一个分组以告之路由器刚知道的所 有信息 ; (4) 将该分组发送给所有其他路由器 ; (5) 计算到每个其他路由器的最短路径。 现在各种各样的链路状态路由选择算法得到 了广泛的应用 ,例如在 Internet 上在越来越多地 使用开放最短路径优先 (OSPF) 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 就是使用链 路状态算法的一个例子。 2 　服务质量路由 (QoSR)基本问题 2. 1 　服务质量路由 (QoSR) 服务质量路由 (QoS Routing) 是一种基于数 据流 QoS 请求和网络可用资源进行路由的机制。 或者说 ,QoSR 是一种动态路由协议 ,并且在其路 径选择标准里可能包含可用带宽、链路和端到端 路径利用率、资源消费代价、延迟、跳数以及抖动 等。为了提供 QoS 保证 ,数据传输前通常需要沿 着计算好的路径 ,从源到目的地传播一个消息 ,用 来通知路径上的所有节点为这个 QoS 业务保留 相应的资源 (如带宽、缓存等) ,而后续的数据传输 则沿着这条已经预留了资源的路径。因此 ,QoSR 具有面向连接的特性。QoS 路由选择必须满足 QoS 的多个约束条件 ,而且必须尽量有效地使用 网络资源并使网络资源利用率最大。 一个运行效果良好的 QoS 路由算法 ,除了考 虑路由的优化 ,还要如整个网络的性能、路由表信 息过时的可能性、链路参数的频繁变化以及信道 建立期间的资源预留等其他问题。QoS 路由算 法必须具有以下特征[ 1 ] : (1) 算法必须在不牺牲任何呼叫所需条件的 前提下 ,使整个网络性能最大化 ; (2) 算法在实现路出策略时必须 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 成能够 保证资源顶留 ; (3) 算法必须在几乎不具备全局状态信息的 情况下能够正常运行 ; (4) 算法必须适应链路状态 (如链路时延和 可获得带宽)的变化 ; (5) 算法必须能够优化 QoS 路由所需的多 个约束条件。 2. 2 　服务质量 (Qo S)度量 目前 QoS 路由算法涉及的度量参数包括 :带 宽、时延、代价、时延抖动、丢失率和跳数。根据对 整个路径 QoS 特性影响的不同 ,这些度量参数可 以分为加性度量参数、乘性度量参数和凹性度量 参数。设网络可用图 G(V , E) 表示 ,其中 V 表示 网络中的节点集合 ,即路由器 ; E 表示网络中各路 由器间链路的集合 ,w (e) 表示附加在链路 e ∈E 36　第 3 期 　　　　　　　　　沈庆伟 :基于 QoS 的分布式路由算法的研究 上的度量值 ,w (p)表示路径 p 的度量值。各种度 量参数特性定义如下[2 ] : 如果 w ( p) = ∑e∈p w ( e) ,即路径的 QoS 特 性为该路径上每条链路的相应 QoS 特性之和 ,则 称度量为可加的 ,典型的加性度量参数有时延、抖 动、跳数、代价等 ; 如果 w ( p) = ∏e∈p w ( e) ,即路径的 Qo S 特性 为该路径上每条链路的相应 QoS 特性之积 ,则称 度量为可乘的 ,典型的乘性度量参数有报文丢失 率等 ; 如果 w ( p) = min{ w ( e) e∈p } ,即路径的 QoS 特性为该路径上每条链路的相应 QoS 特性的极 小值 ,则称度量为凹性的 ,典型的凹性度量参数有 带宽等。 3 　分布式路由算法及分析 3. 1 　网络模型 网络 G(V , E) 中每个节点都有一个路由表 , 该路由表基于网络拓扑进行构造。考虑到网络拓 扑的变化没有带宽、时延等网络参数的变化频繁 , 假设路由表由距离矢量或链路状态算法维护。也 就是说 ,QoS 路由和非 QoS 路由可以使用相同的 路由表和其他状态信息。端到端 Qo S 配置机制 描述如下 :当节点 s 想发送具有特定 QoS 要求的 数据到节点 t 时 ,它发出 QoS 连接请求 ,系统首 先确定一条可以满足 QoS 要求的从 s 到 t 的路 径 ,然后沿该路径实施接纳控制并预留资源来建 立连接 ,前者被称为 QoS 路由 ,后者为资源预留。 当连接建立后 ,s 将沿着预约的路径向 t 发送数据 从而保证 QoS。 网络中连接请求可以表示为一个四元组 : R = (id ,s ,d ,QoS) 。其中 id 为连接请求标识码 ,s 和 d 分别表示连接的源节点和目的节点 ,QoS 为 服务质量请求 ,可以由一组关系式 U n i = 1 { m i oM i }来 表示 ( m i 为衡量度量 , o是关系运算符 , M i 是一个 常数) 。QoS 路由的目的就是找到一跳路径 P 满 足 : Π i ∈[1 ⋯n] , m i ( p) R M i , R 可能是 < 、> 、= 、 ≤、≥等 ,如果 QoS 包含至少两个加法度量 ,则该 路由的求解是 N P 完全问题[3 ] 。 3. 2 　通用分布式路由算法 ( GDRA) [ 4 ] GDRA 算法包括三个阶段 :探测阶段、确认 阶段和出错处理阶段 ,具体描述如下 :探测阶段是 整个算法的核心 ,它负责寻找 QoS 路由 ;后两个 阶段用于资源预留 ,三个阶段分别使用 probe、 ack 和 failure 消息。探测阶段基于可选择的洪泛 探测方法 ,当一个连接请求 (id ,s ,t ,QoS) 到达时 , 探测分组在 s 到 t 的路径上进行可选择的洪泛广 播 ,只有当路经上的节点和链路满足规定的 Qo S 要求时探测分组才继续广播。当 t 收到探测分组 后 ,探测阶段结束 ,探测分组所经过的路径即为试 探路径。在确认阶段 ,确认消息由 t 向 s 沿着试 探路径反向发送到 s ,并且沿着该路径预留资源。 当 s 接收到 ack ,连接即成功建立。但是 ,由于节 点和链路资源的动态变化 ,探测路径的某一节点 可能在收到 ack 时已经没有足够的资源用于预 留 ,此时将调用出错处理阶段。出错处理阶段中 , 无法满足资源预留的节点将发送一个 failure 消 息沿试探路径返回到节点 t ,并释放已经预留的 资源。探测阶段结束调用确认阶段 ,直到 s 接收 到 ack 分组或中间节点由于缺少资源而调用差错 处理阶段或者发生超时。 GDRA 算法以一个消息的往返时间来建立 一个连接 ,假定在正常情况下 ,一个消息在一段链 路上花费的时间 (包括缓存和处理时间)为一个单 位时间 ,那么算法的时间复杂性为 O (2L) ,L 为试 探路径的长度。在从源到目的的所有路径中 ,算 法最多在每个链路发送一个探测分组 ,发送的探 测分组的总数受限于网络中的链路总数 e。在试 探路径上的每个链路最多会有一个 ack 和 failure 消息 ,这些控制消息的总数受限于 2L ,于是一个 连接请求的消息复杂性是 O (e + 2L ) 。如果需要 实现某种具体要求的 DRA 算法 ,只需向满足某 种 QoS 特性的路径发送探测分组 ,从而大大减少 了控制消息的数量。 3. 3 　带宽、时延、代价受限的分布路由算法 如果要寻找满足凹性参数要求的试探路径 , GDRA 算法中的转发条件是 : ( i , j , QoS { mc οMc }) :mc (i ,j) R Mc , R 可能是 < 、> 、= 、≤、≥ 等。若一带宽作为约束条件 ,令 bw (i ,j) 为链路 (i ,j)的可用带宽 ,B 为连接的带宽要求 ,于是转发 条件变为 : (i ,j ,QoS{bwοB}) : bw (i ,j) ≥B。这 就是带宽受限的分布式路由算法。 以加性参数作为约束条件。令 ma 为加性参 46 安徽建筑工业学院学报 (自然科学版) 　　　　　　　　　　第 14 卷 数 , p 为探测分组 , P 为 p 目前所经过的试探路 径 ,定义 ma (p) = ma ( P) 。扩展探测分组的数据 结构 ,增加一个字段用于纪录 m (p ) ,初始化时 , ma (p) = 0。当 P 经过一条新的链路 (i ,j) 后 , ma (p) = ma (p) + m (i ,j) 。与 ma 对应的 GDRA 中 的转发条件变为 : (i ,j ,QoS{ ma o Ma ) : ma ( P) + ma (i ,j) R Ma ( Ma 为一常数) 。路径的端到端时 延是所有节点的节点时延与所经链路的链路时延 的总和。前者包括协议处理时延和排队时延 ,后 者指链路传播时延。时延参数可以定义为 : delay (i ,j) = node delay (i ,j) + link delay (i ,j) ,而 p 所 经过的路径 P 的时延 delay ( P) 为各个节点间的 时延之和 ,D 为必须满足的时延约束。于是时延 受限的 DRA 的转发条件为 : (i ,j ,QoS{delayοD}) :delay (i ,j) + delay ( P) < D 这是时延受限的分布式路由算法。在这个算 法中 ,必须选择适当的探测等待时间Δt ,一般令 Δt = f (delay (i ,j) ) , f 是单调非减函数。 把时延 ( delay) 参数换成另一加性参数代价 (cost) ,情况也是一样的。代价参数定义为 :cost (i ,j) = node co st (i ,j) + link cost (i ,j) ,而 p 所经 过的路径 P 的 cost ( P) 为各个节点间的代价之 和 ,C 为必须满足的代价约束。转发条件为 : (i ,j , QoS{costοD}) :cost (i ,j) + cost ( P) < C ,Δt = f (cost (i ,j) ) 。这是代价受限的分布式路由算法。 3. 4 　多度量受限的分布路由算法 这里举两个例子 ,一个以带宽和时延作为约 束 ,一个以时延和代价作为约束。 将带宽和时延作为约束 ,这两个度量分别为 凹性和加性参数 ,那么转发条件为 : (i ,j ,QoS{ bwοB ,delay O D}) :bw (i ,j) ≥ B ∧delay (i ,j) + delay ( P) < D , Δt = node cost (i ,j) 将时延和代价作为约束 ,由于两个度量都是 加性参数 ,要求找到同时满足时延的代价要求的 路径是一个 N P ( Complete Problem) 完全问题。 这是一种可行的启发式算法 ,其转发条件为 : (i ,j ,QoS{delay O D ,costοC }) : delay (i ,j) + delay ( P) < D ∧cost (i ,j) + cost ( P) < C 这里Δt 的选择很巧妙 ,通常为 :Δt = max (α ×delay ( i , j) +β×cost ( i , j) - link delay ( i , j) ,0) 当时延约束难满足 ,而代价约束易满足时 ,可 令α= 1 ,β= 0 ,此时就变成时延约束的情况 ;当代 价约束难满足 ,而时延约束易满足 ,可令α= 0 ,β = D/ C,β不设为 1 是为了平衡两个度量对Δt 的 影响 ;当两个约束地满足难度相当时 ,可令α= 1 , β= D/ C ;当无法确定满足两个约束的难易程度 时 ,为了提高路由查找的概率 ,允许同时运行多个 具有不同Δt 的分布式路由算法。 3. 5 　迭代分布式路由算法 ( IDRA) 前面分析的通用分布式路由算法 ,通过试探 分组之间的竞争来找到一条试探路径 ,最先到达 的试探分组将首先确定该路径 ,当存在多条满足 QoS 要求的路径时 ,通常优先选择最短路径。为 此提出一种迭代 DRA 算法 ,下面以带宽为例说 明该算法的实现方法。 设 age (p ) 为探测分组经过的跳数 ,最初令 age (p) = 0 ,每经过一条链路转发 , age (p ) 加 1。 于是迭代 DRA (bw)的转发条件为 : (i ,j ,QoS{bw οB}) : bw (i ,j) ≥B ∧age (p ) + dj , t + 1 ≤L 。其 中 , d 是 j 到目的节点 t 的距离 , L 是一个不小于 ds , t 的常数 , ds , t 为源到目的节点的最短距离。 当 L = ds ,t时 ,算法将沿着最短的路径转发探测分 组 ,此时 DRA 称为满足 L = ds ,t 的 DRA ( bw) 。 迭代 DRA 算法可以表示为 : DRA ( bw) iterative on{L = ds ,t ,L = ds ,t + 1 , ⋯,L = + ∞} ,即它反复 执行具有不同约束条件的 DRA ( bw) ,直到建立 一个连接。为了减少开销 ,一种简单的方法只定 义两个 L 值 ,即 L = ds ,t 和 L = + ∞第一次迭代 时 ,探测分组只沿着最短路径发送开销较小 ,如果 此次查找成功 ,将找到一条最短路径 ,并取消下一 次迭代 ,否则在所有可能的路径上进行搜索。与 非迭代 DRA 算法相比 ,在网络轻载的情况下 ,迭 代 DRA 一般工作得更好 ,即使在网络负载较重 时 ,其开销也小于非迭代算法开销的两倍。 4 　结束语 Qo S 路由算法是随着计算机网络和应用的 发展而产生的一个新兴研究领域。当前的许多 QoS 路由算法要求节点维护全局的网络状态 ,开 销过大 ,可扩展型不好 ,通用的分布式路由算法可 以作为设计具体的满足特定指标的 QoS 路由算 法的基础。该算法基于分布式计算并且只需利用 (下转第 94 页) 56　第 3 期 　　　　　　　　　沈庆伟 :基于 QoS 的分布式路由算法的研究 ⋯, S 个方程的两端 ,然后相加 ,同样根据引理 1 , 引理 2 可得 D X 1 = b′1 B11 + b′2 B21 + ⋯+ b′sB s1 = C1 由于 D ≠0 , 故 X1 = C1D 。同理可得 X2 = C2 D , ⋯, X s = Cs D ,这就是说 ,当 X1 , X2 , ⋯X n 为 (3) 的任何 一解时 ,这个解必为 (4) 的解 ,即解是唯一的。 当 k = 1 时 ,方程组 (3) 就是方程组 (1) ,而这 时的定理就变成通常的克莱姆法则了。 推论 ,方阵 A = a11 a12 ⋯ a1 n a21 a22 ⋯ a2 n ⋯ ⋯ ⋯ ⋯ an1 an2 ⋯ ann 是满秩的充要条件为 A 的 k 阶子式阵是满秩的 证明 :由线性方程组的理论知 ,方程组 (1) 或 (3) 有唯一解的充要条件是 ,它们的系数方阵是满 秩的 ,再由定理便可得推论的结论。 参考文献 1 　同济大学应用数学系. 线性代数 (第 3 版) [ M ] . 北京 : 高教出版社 ,2004 : 28 30. 2 　北京大学数学力学系几何与代数教研室小组编. 高等 代数[ M ] . 北京 :人民教育出版社 ,1978 : 89 91. 3 　周伯薰. 高等代数 [ M ] . 北京 :人民教育出版社 ,1966 : 32 36. (上接第 65 页) 本地最新的拓扑和状态信息 ,没有路由环路 ,并且 可以减少控制消息的开销 ,同时实现比较简单。 该算法具有很大的灵活性 ,可以用于多种约束条 件的组合。此外 ,迭代 DRA 算法在网络轻载时 可以进一步减少控制消息开销。但是 ,QoS 路由 算法是一个比较复杂的问题 ,本文介绍的多维 DRA 算法也只是一种启发式算法 ,为了使其实用 化 ,需要进一步在各种网络环境下进行试验来验 证该算法的有效性 ,同时需要研究多播环境下的 相应算法。 参考文献 1 　林 　闯. 计算机网络的服务质量 (QoS) [ M ]. 北京 :清 华大学出版社 ,2004 :192 - 193. 2 　徐 　恪. 高等计算机网络[ M ] . 北京 :机械工业出版社 , 2003 :192 - 193. 3 　Z wang ,J Crowcroft . QoS routing for supporting re2 source reservation [J ] . Journal of Select areas in com2 munication ,1996. 4 　Ghosh , D. ; Sarangan. Quality2of2service routing in IP networks [ J ] . Multimedia , IEEE Transactions on , 2001 ,3 (2) :200 - 208. 49 安徽建筑工业学院学报 (自然科学版) 　　　　　　　　　　第 14 卷