维普资讯 http://www.cqvip.com 第４７卷第３期 Ｖｏ１．４７ Ｎｏ．３ ２００７年６月 Ｊｕｎ．２０ｏ７ 文章编号：１００１—８９３Ｘ（２００７）０３—０１７４—０４ ＭＰＬＳ流量工程中的约束路由技术 李兴和，杰 （中国电子科技集团公司第５４研究所所，石家庄０５００８１） 摘要：传统的ＩＰ路由协议采用最短路径算法（ＳＰＦ），极易造成网络的拥塞。流量工程是目前网络 中实现负载均衡和提高网络性能的一个重要技术。文中简要介绍了ＭＰＬＳ流量工程，重点分析了 也一ＭＰＬＳ流量工程中所使用的路由协议——约束路由，给出了约束的计算方法以及路由度量选择的准 町 则。 讥 关键词：ＭＰＬＳ；流量工程；ＱｏＳ路由；约束路由 中图分类号：ＴＮ９１５．０１ 文献标识码：Ａ 技 咖 Ｃｏｎｓｔｒａｉｎｅｄ Ｒｏｕｔｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ ｉｎ ＭＰＬＳ Ｔｒａｆｉｆｃ Ｅｎｇｉｎｅｅｒｉｎｇ ．ｎ ｕ Ｘ ｇ—ｈｅ。ＺＨＡＮＧ Ｌｉｎ－ｆｉｅ （Ｔｈｅ ５４ｔｈ Ｉｎｓｔｉｔｕｔｅ ｏｆ ＣＥＴＣ，Ｓｈｉｊｉａｚｈｕａｎｇ ０５００８ １，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｕｓｅ ｏｆ Ｓｈｏ￣ｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ（ＳＰＦ）ａｌｇｏｒｉｔｈｍ ｉｎ ｔｒａｄｉｔｉｏｎａｌ ＩＰ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｃａｎ ｃａｕｓｅ ｎｅｔ— ｗｏｒｋ ｃｏｎｇｅｓｔｉｏｎ．Ａｔ ｐｒｅｓｅｎｔ，ｔｒａｆｉｆｃ ｅｎｇｉｎｅｅｒｉｎｇ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｔｅｃｈｎｏｌｏｇｙ ｔｏ ａｃｈｉｅｖｅ ｎｅｔｗｏｒｋ ｌｏａｄ ｂａｌａｎｃｅ ａｎｄ ｅｎｈａｎｃｅ ｎｅｔｗｏｒｋ ｐｅｒｆｏｒｍａｎｃｅ．Ｔｈｅ ＭＰＬＳ ｔｒａｆｉｆｃ ｅｎｇｉｎｅｅｒｉｎｇ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａｎｄ ｔｈｅ ｒｏｕ— ｔｉｎｇ ｐｒｏｔｏｃｏｌ ｕｓｅｄ ｉｎ ＭＰＬＳ ｔｒａｆｆｉｃ ｅｎｇｉｎｅｅｒｉｎｇ——ｃｏｎｓｔｒａｉｎｅｄ ｒｏｕｔｉｎｇ ｉｓ ｄｅｓｃｒｉｂｅｄ．Ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ａｌｇｏ— ｒｉｔｈｍ ｏｆ ｃｏｎｓｔｒａｉｎｅｄ ｒｏｕｔｉｎｇ ａｎｄ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ｃｈｏｏｓｉｎｇ ｒｏｕｔｉｎｇ ｍｅｔｒｉｃｓ ａｒｅ ｇｉｖｅｎ． Ｋｅｙ ｗｏｒｄｓ：ＭＰＬＳ；ｔｒａｆｆｉｃ ｅｎｇｉｎｅｅｒｉｎｇ；ＱｏＳ ｒｏｕｔｉｎｇ；ｃｏｎｓｔｒａｉｎｅｄ ｒｏｕｔｉｎｇ １ 引 言 ２ ＭＰＬＳ流量工程 随着Ｉｎｔｅｍｅｔ的网络规模和用户数量的迅猛发 流量工程是一种可用来控制网络资源、提高网 展，Ｉｎｔｅｍｅｔ业务种类与日俱增。多媒体业务和实时 络性能的网络资源技术。它是一种既能够将业 业务的出现带动了网络朝着宽带的方向发展，同时 务流映射到实际的物理通路上，同时又可以自动优 要求网络能够提供足够的服务质量（ＱｏＳ）保证。在 化网络资源以满足特定应用的ＱｏＳ要求。对于流 传统的ＩＰ网络中，所有的业务流都是基于内部网关 量工程来说，ＭＰＬＳ是当前最好的解决方案。 协议（ＩＧＰ）选出的路由进行逐跳转发的，这些协议 ＭＰＬＳ是当前被普遍看好的高速骨干网络技 以到达目的地址的最短路径为准则对业务流进行选 术。作为ＭＰＬＳ的一种重要应用，ＭＰＬＳ流量工程的 路。这种选路机制不具备全网资源的调节能力，极 目的就是要最大效率地利用网络资源，在提高业务 易造成网络资源使用的不平衡，出现网络拥塞现象， 性能的同时，提高网络运行效率，使网络运行更加可 导致网络性能的下降，网络的ＱｏＳ无法保证。为 靠。流量工程的性能目标主要体现在两个方面：业 此，流量工程（Ｔｒｆａｉｆｃ Ｅｎｇｉｎｅｅｒｉｎｇ）技术应运而生。 务方面和资源方面。业务方面主要指的是：减少分 收稿日期：２００６—０８—１２；修回日期：２００６—１２—２２ ・１７４・ 维普资讯 http://www.cqvip.com 第４７卷第３期 ２００７年６月 组丢失率、降低延时、提高网络吞吐量、保障ＱｏＳ。 Ｖｏ１．４７ Ｎｏ．３ Ｊｕｎ．２００７ ＱｏＳ要求都必须被映射成为一个路径的具体的约束 资源方面主要指的是资源使用优化的问题。约束路 由对ＭＰＬＳ流量工程的支持体现在为ＭＰＬＳ流量工 程提供流量管理所需的显式路由。所谓显式路由， 就是指在标记交换路径建立过程中，明确指定所经 过的部分或全部节点，如果只指定了部分节点，称为 疏松的显式路由（Ｉ．￣Ｋ）ｓｅ Ｅｘｐｌｉｃｉｔ Ｒｏｕｔｉｎｇ）；如果指定 了全部节点，则称为严格的显式路由（Ｓｔｒｉｃｔ Ｅｘｐｌｉｃｉｔ 条件，这些约束条件用度量来表示，因此，度量从某 种程度而言决定了一个网络可以提供的ＱｏＳ保证 的类型； （３）度量之间应该是正交的，以便度量之间没 有冗余的信息。冗余的信息会引起度量之间相互依 赖，这样很难对每个度量地做出计算。 路由度量实际上是与链路相联系的一种权值， Ｒｏｕｔｉｎｇ）ｏ ∞ ３基于约束的路由选择技术 国一基于约束的路由由ＱｏＳ路由发展而来， 但并不 等同于ＱｏＳ路由，它包括一系列的路由算法，讥 这些 算法的计算是基于一系列的约束和性能要求的。这 些约束可以是由管理策略发起的，技 也可以是由ＱｏＳ 要求发起的。由管理策略发起的约束称为策略约束 咖 ∞ （ｐｏｌｉｃ．ｙ兰 ｃｏｎｓｔｒａｉｎｔｓ），与其相关的路由称为策略路由 （ｐｏｌｉｃｙ ｒｏｕｔｉｎｇ）；由ＱｏＳ要求发起的约束，如带宽、 延迟、丢包率等，称为ＱｏＳ约束（ＱｏＳ ｃｏｎｓｔｒａｉｎｔｓ），与 其相关的路由选择称为ＱｏＳ路由（ＱｏＳ ｍｕｔｉｎｇ），它 们之间的关系如图１所示。 图１约束路由包含的内容 基于约束的路由选择由两方面组成：一是为数 据包选路时依据那些度量参数作为寻路标准，称为 度量参数选择问题；二是在参数标准确定后，如何找 到满足业务需求约束的路径，并保证数据经由选定 路径传输到目的节点，称为约束路由的计算问题。 ３．１路由度量的选择 路由度量不仅和路由计算的复杂度有关，而且 与路由所能支持的ＱｏＳ要求的范围有关。选择路 由度量应考虑以下几点： （１）不论选择什么样的度量，必须有一个高效 的算法来计算路径，以便于路由协议能适用于大型 的网路。路径计算算法的复杂度应该与现有的路由 算法的复杂度相当； （２）度量必须能反映网路的基本特征，度量所 包含的信息应支持基本的ＱｏＳ要求。注意到任何 它既可以作为路径选择的约束条件，也可以作为衡 量路径优劣的一种重要判据。路由度量根据其特性 大致分为３类。 设ｄ（ ，－『）是链路（ｉ， ）的度量，则对于任意的路 径Ｐ＝｛ｉ，＿『，ｋ，…，ｚ，ｍ｝，有： （１）当路径Ｐ的度量满足：ｄ（ｐ）＝ｍｉｎ｛ｄ（ ，－『）， ｄ（ｊ，ｋ），…，ｄ（ｚ，ｍ）｝时，称度量ｄ为凹性度量。路 径的可用带宽或者可预留带宽都是典型的凹性度 量； （２）当路径Ｐ的度量满足：ｄ（Ｐ）＝ｄ（ｉ，．『） ＋ａ（ｊ，ｋ）＋…＋ｄ（Ｚ，ｍ）时，称度量ｄ为加法度量。 节点数、时延、时延抖动等都是属于加法度量； （３）当路径Ｐ的度量满足：ｄ（Ｐ）＝ｄ（ｉ， ） ×ｄ（ｊ，居）×…×ｄ（ｚ，ｍ）时，称度量ｄ为乘法度量。 链路的可靠性，丢包率都属于乘法度量。对乘法度 量进行适当的转换，如对数转换，可将乘法度量转换 成加法度量。 ３．１．１混合单度量 只有一个度量的路径计算算法（比如跳数或延 迟）已经广为人知，而且已经广泛地应用于现在的网 络中。由于单度量没有包含足够的信息来指示路径 是否能满足ＱｏＳ要求，所以单个度量不能很好地支持 ＱｏＳ。一个可能的方法就是定义一个函数，再由多个 参量来得出一个度量。这个方法就是把各种各样的 信息融合成一个度量，以此度量作为路由选择的基 础。如，一个混合的度量 可能是由带宽Ｂ、延迟Ｄ Ｄ／一、 和丢包率￡通过公式 ｐ） 得到。在这 种合成方法中ｆ（ｐ）越大，认为所选的路径越优。 ３．１．２多度量 多度量（如延迟、带宽和丢包率）可以准确地模 拟一个网络的特点。在基于约束的路由算法中，希 望对支持的每一个参数都要求加以考虑，找到同时 满足所有度量约束的路径。考虑时延、时延抖动、带 宽、丢包率和开销，其中任何两个作为度量是一个完 ．１７５・ 维普资讯 http://www.cqvip.com 第４７卷第３期 ２００７年６月 国讥技 Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏ１．４７ Ｎｏ．３ Ｊｕｎ．２００７ 全问题－４ Ｊ。一个可行的方法是将带宽与剩余４个中 的任何一个进行结合。虽然延迟、延迟抖动、丢包率 和开销都是非常重要的参数，但是对于大多数应用 来说，带宽和时延比其它几个参数要相对重要一些。 在同构网络中，链路的传输时延可以用跳数来代替。 由于存在ＮＰ完全问题，因此多度量选择的一个 主要问题是如何在基本满足ＱｏＳ要求的前提下简化 问题，降低算法设计的复杂度，保证算法的可实现性。 目前降低算法复杂度的方法主要有以下几种： １）ｗｉｄｅｓｔ—ｓｈｏｒｔｅｓｔ路径：选择一条时延最小的 路径，并且如果有多条这样的路径时，选择其中可用 带宽最大的那一条路经； ２）ｓｈｏｒｔｅｓｔ—ｗｉｄｅｓｔ路径：选择一条可用带宽最 选择的路由上传送一个控制包，通知路由上的每个 节点，说明其前继者和后继者为谁。每个节点的信 息由链路信息分发协议完成。 源路由中，源端可以选择路由算法计算路 由，不需要有多个节点协同进行路由选择，可以避免 分布式路由中的死锁和环路等现象。在基于源的发 送策略中，更容易设计出可实现的低复杂度寻路算 法。源路由主要的问题是寻路开销大、状态信息准 确性不高和网络扩展受限。这几个问题都与节点需 要保留全网状态信息有关。 ３．２．２分布式路由 路由选择的计算是分布计算完成的，其路径上 的各个节点通过交互控制信息，并结合各个节点所 存储的状态信息来完成路由选择的计算。大多数分 布式路由算法需要用距离一向量协议或链路状态协 议来保持其全局信息，在每个节点上此信息是以距 离向量的形式保存。根据距离向量，路由以逐跳的 方式完成。 分布式路由存在２个主要问题。一个是环路问 大的路径，并且如果有多条这样的路径时，选择其中 时延最小的那一条路径； ３）ｓｈｏｒｔｅｓｔ—ｄｉｓｔａｎｃｅ路径：一个跳的路径的距 离定义为 ｄｉｓｔ（ｐ）＝∑（１／Ｓ ） ｉ：１ 其中．ｓ 表示链路 的带宽。此准则是一个折衷的方 法，即当网络负载较重时它倾向于最短路径，而负载 较轻时它倾向于最宽路径。 ３．２约束路由的计算 题。网络中各个节点保留的其它节点状态信息不一 致或者节点路由信息不准确，都可能引起环路。虽 然，环路可以在数据包第二次到达同一节点时被检 测到，但是环路的存在会引起非网络拥塞造成的业 务延迟。另外，业务在相同链路上的重复发送也会 根据网络状态信息的保存方式和路由搜寻方式的 不同，路由策略可以分为２种：源路由和分布式路由。 ３．２．１源路由 加重网络负荷，降低网络效率。另一个是多个路由 节点的有效协同问题。如果路由节点间不能很好地 协同，对整个网络的性能、路由协议的动态特性及路 每个节点保存全局的网络状态信息，包括网络 的拓扑信息和每条链路的状态信息。根据此全局信 息，源节点在本地计算出一条合适的路由，然后在所 由结构的扩展性都会有负面影响。 源路由和分布式路由的比较如表１所示。 表１ 源路由和分布式路由的比较 寻路开销 更新信令开销 开销量 大 节点保存的状态信息 状态信息不准确可能引起的问题 源 计算路径开销 路 由 链路信令开销 预约延迟开销 大 较小 大 保存网络中所有节点参 ①选路失败，重新寻路，开销增加； 数特性（如：带宽大小链 ②所选路径不是最优路径； 路延时） ③网络扩展性降低。 分 更新信令开销 较小 布 计算路径开销 式 较小 大 较小 保存网络中所有节点或 ①节点间寻路协同性降低； 路 信令探测开销 由 预约延迟开销 下一跳节点参数特性 ②引起环路。 ・１７６・ 维普资讯 http://www.cqvip.com 第４７卷第３期 ２００７年６月 国讥技 Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏ１．４７ Ｎｏ．３ Ｊｕｎ．２ｏｏ７ ４约束路由设计的难点 约束路由的主要目标是为接人的业务选择满足 其服务质量要求的传输路径，同时保证网络资源的 ５ 结束语 本文主要介绍了流量工程中的约束路由的选择 以及路径的优化。约束路由由ＱｏＳ路由发展而来， 有效利用。约束路由在进行路由选择时，除了考虑 在计算路由的过程中不仅考虑到ＱｏＳ要求，而且要 多度量的约束外，还要考虑网络的拓扑和链路状态 考虑一系列的策略性的要求。约束路由主要包括２ 的变化。所以，约束路由在设计时会面临以下几个 个部分：度量的选择和路径的计算。约束路由的使 难点。 （１）ＮＰ一完全（Ｎｏｎ Ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ Ｃｏｍｐｌｅｔｅ， 用可以大大减少流量工程过程中所需的人工配置和 手工干预。鉴于约束路由在实现流量工程中的重要 ＮＰ—Ｃｏｍｐｌｅｔｅ）问题 作用，对约束路由及相应规范的研究将是未来网络 所谓ＮＰ—Ｃｏｍｐｌｅｔｅ问题，是指同时对２个或者 研究的热点之一，但是由于约束路由本身的复杂性， 以上相互的参数提出要求时，解决这个问题的 还有大量具体的工作需要研究。 多项式时间算法可能并不存在，一般用近似算法来 求解。实时应用往往会对延迟、抖动、带宽、丢失率 参考文献： Ｚｈｅｎｇ Ｗａｎｇ，Ｊｏｎ Ｃｒｏｗｃｒｏｆｔ．Ｑｕａｌｉｔｙ一０ｆ—Ｓｅｒｖｉｃｅ Ｒｏｕ－ 和业务代价等多个参数同时提出性能要求。这些参 ［１］数相互时，选择满足多个参数约束的路由就成 为ＮＰ—Ｃｏｍｐｌｅｔｅ问题。ＮＰ—Ｃｏｍｐｌｅｔｅ问题直接关 系到路由算法的可实现性。 ｔｉｎｇ ｆｏｒ Ｓｕｐｐｏｒｔｉｎｇ Ｍｕｌｔｉｍｅｄｉａ Ｓｐｐｌｉｃａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｊｏｕｒ－ ｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，１９９６，１４（７）： １２２８—１２３４． （２）网络状态信息扩散量大 约束路由中，为了获得满足一定约束条件的路 由，网络必须实时地更新网络的当前状态，所以，约 束路由会产生较大的自身开销。 （３）信息不准确 ［２］ Ｚｈｅｎｇ Ｗａｎｇ，Ｊｏｎ Ｃｒｏｗｃｒｏｆｔ．Ｂａｎｄｗｉｄｔｈ—Ｄｅｌａｙ Ｂａｓｅｄ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍｓ［ｃ］／／ＩＥＥＥ ＧｌｏｂａｌＣｏｍ ９５．Ｓｉｎｇａ－ ｐｏｒｅ：ＩＥＥＥ，１９９５． ［３］Ｘｉｐｅｎｇ Ｘｉａｏ，Ｌｉｏｎｅｌ Ｍ Ｎｉ．Ｉｎｔｅｍｅｔ ＱｏＳ：Ａ Ｂｉｇ Ｐｉｃｔｕｒｅ ［Ｊ］．ＩＥＥＥ Ｎｅｔｗｏｒｋ，１９９９． ［４］Ｘｉｐｅｎｇ Ｘｉａｏ，ＡＪａｎ Ｈａｎｎａｎ，Ｂｒｏｏｋ Ｂａｉｌｅｙ．Ｔｒａｆｆｉｃ Ｅｎｇｉ－ ｎｅｅｒｉｎｇ ｗｉｔｈ ＭＰＬＳ ｉｎ ｔｈｅ Ｉｎｔｅｒｎｅｔ［Ｊ］．ＩＥＥＥ Ｎｅｔｗｏｒｋ， ２０００． 传输负荷的抖动、新连接的加入或取消等都可 能导致网络状态变化，这些变化因素直接影响全网 状态信息的准确性。不准确的路由信息可能会使路 作者简介：李兴和（１９６７一），男，高级工程师，研究方向：通信装备 由选择失败，重新进行路由计算和发送预约信令，从 与系统，（电子信箱）ｌｉｘｉｎｇｈｅ＠ｔｏｍ．ｅｏｍ。 而增大网络开销和业务延迟。分布式路由中，不准 确的路由信息还可能导致环路。 ・１７７・
