基于主动网络的多约束路由探测算法 multi-constrained active routing algorithm based on probing.pdfVIP

第 11 卷 第 1 期 电路与系统学报 Vol.11 No.1 2006 年 2 月 JOURNAL OF CIRCUITS AND SYSTEMS February 2006 文章编号 1007-0249 (2006) 01-0006-06 基于主动网络的多约束路由探测算法* 中国科学技术大学 电子工程与信息科学系 安徽 合肥 230027 摘要 本文提出了一种基于主动网络的多约束路由探测算法 MAR Multi-constrained Active Routing 与传统路 由算法相比 MAR 不仅能灵活地提供多种约束条件的服务质量保证 而且充分发挥了主动网络的可编程和自定制能 力 允许用户根据业务要求和网络状况自定制约束条件和相关参数 通过仿真 MAR 算法在各种网络条件下的性能表 明 MAR 算法能够提高多约束条件寻路的成功率 关键词 主动网络 QoS 路由 探测算法 中图分类号 TP393 文献标识码 A 1 引言 目前 Internet 上广泛使用的域内路由协议是 RIP Routing Information Protocol 和 OSPF Open Shortest Path First 这两种协议的本质都是采用最短路径算法 具有公平性 fairness 的特点 即在 寻路时不区分用户业务的种类 将网络资源公平地提供给各类业务 这种将网络中所有分组都按一种 机制进行路由的方式 使分组的丢失率 可用带宽 延迟 抖动等服务质量 Quality of Service QoS 参数无法得到保证 而这些参数对于分布式多媒体应用业务却是至关重要的 服务质量路由 QoS Routing QoSR 的目标就是要在源节点和目的节点之间找到一条满足多 QoS 约束条件的传输路径 在多约束条件下求解可行路径属于 NP 完全 NP-complete 问题 不能在多项 式时间内精确求解 因此研究人员设计出多种启发式算法和近似算法 例如 Wang 和 Crowcroft 使用 Dijkstra 最短路径算法实现了带宽延迟受限的源路由求解[1] Shin 和 Chou 设计了延迟受限的分布式路 由算法[2] Yuan 和 Liu 设计了粒度受限的启发式路由算法[3]等等 纵观这些算法 还存在以下三方面 的问题 1 计算复杂度高 在目前的实 际网络中无法实现 2 算法性能低 当找不到满足条件的可 行路径时 不具有路由协商机制 3 可扩展性差 大部分算法都只是针对 QoSR 问题中某些特殊情况 难于在不改变原型设计的基础上 增加新 的约束条件 主动网络是一种新型 的网络体系结构[4] 它 的提出是为 了解决现有共享 网络结构 中新协议和新业 务引入困难的问题 避免对标准化 的依赖 主动网络的基本设计思想是通过对用户开放 网络资源 使 具有可编程能力的用户能够对网络中的主动节点进行编程 以达到利用网络中的物理资源构建并管理 新业务的目的 可以说 主动网络是下一代 网络体系结构 的理想方案 主动功能实现原理[5]如下 在 主动节点上运行节点操作系统 Node Operating System 和执行环境 Execution Environments 节点 操作系统负责分配和调度节点资源 包括