MPLS网络中的QoS路由粒度研究

【摘要】(1.Yueyang Vocational Technical College, Yueyang 414000, China;2.Yueyang Civil Affairs Bureau, Yueyang 414000, China) Abstract: The impact of constraint-based routing d...

摘 要:研究了基于约束的路由决策粒度对mpls网络中QoS路由可靠性和阻塞性能的影响。为实现成本效益的可测量性,这里在现有粒度方案的基础上,提出了使用混合粒度方案:每对/流粒度方案和每对/类粒度方案。有每对/流粒度的每对流方案增加了P缓存和O缓存作为路由缓冲,完成了低阻塞率。有每对/类粒度的每对类方案将流汇聚到几条路由路径,从而允许数据包在有限的缓存规模内被标签转发。仿真结果表明,混合粒度方案减少了路由缓存规模,适合于MPLS网络。关键词:MPLS; QoS; 粒度方案; 路由缓存

中图分类号:TN915-34文献标识码:A

文章编号:1004-373X(2010)18-0079-04

Study of QoS Routing Granularity in MPLS Network

PENG Ying1, WEN Ping-geng1, JI Fei2

(1.Yueyang Vocational Technical College, Yueyang 414000, China;2.Yueyang Civil Affairs Bureau, Yueyang 414000, China)

Abstract: The impact of constraint-based routing decision granularity on the scalability and blocking performance of QoS routing in MPLS network is studied. To achieve scalability of cost-effective, this study proposes using hybrid granularity schemes:the per-pair/flow scheme and the per-pair/class scheme. The per-pair flow scheme with per-pair/flow granularity adds a P-cache (per-pair) and an O-cache (per-flow) as the routing cache, and performs low blocking probability. The per-pair class scheme with per-pair/class granularity groups the flows into several routing paths, thus allowing packets to be label-forwarded with a bounded cache size. This scheme reduces the routing cache size and is suitable for MPLS networks.Keywords: MPLS; QoS; granularity scheme; routing cache

0 引 言

随着Internet的快速发展,网络拥塞问题变得越来越严重。网络资源不足或不平均的业务分配都可能引起网络拥塞。目前使用的动态路由协议RIP和OSPF总是选择最短路径来转发数据包,会引起不平均的业务分配。要解决这个问题,就需要QoS路由技术和流量工程(traffic engineering,TE)。

QoS路由是在一定的可用网络资源下求解满足单个流QoS要求(如带宽、时延、时延抖动等)的路由问题。而TE路由具有更加广泛的目标,它不仅要从个体上考虑即满足特定流的QoS要求,还要从全网的角度上考虑即优化网络性能,均衡负载分布,使网络处于良好的运行状态。关于TE路由问题,正引起人们的关注,目前已经提出了一些算法,如最宽最短路径算法(widest shortest path,WSP)[1]、最小干涉路由算法(minimum interference routing algorithm,MIRA)、基于轮廓的路由算法(profile based routing,PBR)等。这些算法都是以均衡负载分布和减小请求阻塞率为目标,在具体选路过程中又转化成不同的限制条件。

MPLS作为一种先进的转发机制为TE的实施提供了便利,很多流量工程都可以由MPLS有效地完成。MPLS将标签交换转发范例与网络层路由结合起来[2],在MPLS网络的入口处赋予数据包一个固定长度的标记,这样做的依据是转发同等类(forwarding equivalence classes,FEC)的概念。在MPLS域内部,使用标记作转发决定,通常不需要求助于原来数据包的信头。在这里,标签可以用来表现不同粒度的路由,范围从每目标网络这样的粗粒度到每单个流这样的细粒度。粗粒度,如每目的地粒度,存储要求低、上层计算要求低,但仅适用于尽力而为的流量。细粒度,如每流粒度,提供了低阻塞率,但需要大量的状态信息和高计算成本[3]。

为了在不影响QoS需求的情况下减少阻塞可能性,提出了混合粒度路由方案。

1 混合粒度方案

(1) 已有的最短路径算法基础

假定用基于链路状态和直接路由的体系结构。链路状态QoS路由协议用洪泛来交换链路状态信息,让所有的路由器能建立相同的链路状态数据库(LSDB)。给定完整的拓扑信息和资源的可用状态,每个有QoS能力的路由器找到代价最小的路径,同时满足流的资源需求。

混合粒度方案以两个基于命令的最短路径计算探索法[4]作为基础。

① 最宽最短路径探索法:QoS对开放式最短路径优先(QOSPF)的扩展使用最宽最短路径(WSP)选择标准来选择最小跳数(最短)路径。如果有几条这样的路径,选择有最大带宽(最宽)的那条。这个算法迭代地识别从它本身s到任何其他节点d的最优(最宽)路径。然后,WSP选择到节点d的所有可能的最短路径中的最宽σ作为有最小跳数的路由路径。

② 约束的最短路径探索法:显示另一种探索法即约束的最短路径(CSP)。使用“有充足带宽的最小延迟”作为选择标准来为流F找到最短路径。

(2) 有每对/流粒度的启发式方案

这里使用的路由在源路由中无环路,信号程序阻止数据包携带复杂的路由信息。在MPLS中,边缘设备根据应用来辨别流,并依据网络规则给数据包分类。用标签集来区分目的地址、服务类、转发路径等。信号阶段,如果有流请求,路径查询可以进行路径计算,也可以从缓存中提取路径。当查询成功,源节点开始一跳一跳地发信号来建立转发状态,目的节点在路径中沿每个链路返回并进行带宽预定。从缓存中提取的路径可能会误导,也就是说,尽管存在有丰富资源的路径,可能沿此路径也找不到足够的资源。这原因在于,同一源-目的地(S-D)对之间的所有流被缓存到同一路径,而这路径只是为第一个流计算的,可能不满足后来流的带宽需求。特别是当路径链路成为瓶颈的时候,阻塞率迅速增加[5]。另一方面,就算这样的误导不发生在每流粒度的路由,由于细粒度的流状态和路由缓存很大也导致可测量性很低。此外,细粒度路径计算量大,在真实网络中很难实现。因此,可执行路径预运算,异步计算到目的地的可行路径[6]。

在这里,将路由缓存在功能上分为三个部分,每对缓存(P缓存),溢出的每流缓存(O缓存),和每目的地缓存(D缓存)。

算法1:每对流粒度路由搜索

Per_Pair_Flow(F, s, d, b, D)

/*这里,流F从s到d,有带宽需求b和延迟需求D,σ为路径*/

{

如果在P缓存中查找失败:

σ寻找最小代价路径(s, d, b, D)

if (找到路径σ)

路径存入P缓存, 标记流F并路由F通过路径σ

else"路径未找到"

如果在P缓存中查找成功:

if(σ的带宽≥ b且σ的延迟≤D)

标记流F并路由F 通过路径 s

else/* 溢出*/

{

σ寻找最小代价路径(s, d, b, D)

if (找到σ)

路径存入O缓存, 标记流F并路由F 通过路径σ

else"路径未找到"

}

}

算法1显示了每对流粒度方案。多约束路径查询在入口LSR执行,为了得到路由信息,查找P缓存。如果查找失败,意味着没有存储相应的路径。这种情况下,每对流粒度调用寻找最小代价路由函数找到一条qos路径σ。该路径被存储在P缓存中,流请求F直接通过σ。但如果找不到路径σ,请求被阻塞[7]。如果在P缓存查找成功,为了确保流的QoS,必须依照最近链路状态做资源可用性检测。检测成功,信号信息F依照P缓存路径发送。如果检测失败,调用函数寻找最小代价路径,在LSDB中的信息和剩余带宽数据库(RBDB)的基础上,寻找路径,找到的路径σ被存储在O缓存中,F的信号通过σ发送。如果找不到路径σ,流被阻塞。

算法1中寻找最小代价路径用WSP或CSP,按需求找到一条QoS路径。其中链路代价函数可以依据网络管理员的需要定义。

(3)有每对/类粒度的启发式方案

在MPLS中,这个方案用路由标记作为标签的┮徊糠帧＊当流请求达到边缘路由器时,它被转发到当前路由状态接近最好的路径,其中,最好路径为代价最小的可行路径。S-D对之间的流被路由到几条不同的路径,在源和边缘路由器上相应地标记。相同路由路径的流可能需要不同的QoS。MPLS域中的核心路由器使用标签来决定数据包被转发到哪一个出口,并决定服务的类。

算法2:每对类粒度路由搜索

Per_Pair_Class(F, s, d, b, D)

/*这里,流F从s到d,有带宽需求b和延迟需求D,∏(s, d)为缓存入口设置的从s到d的路由路径,π为由缓存中提取的路径,σ为由计算得到的可行路径*/

{

初始化 路径代价 ∞

提取路径 π ∈∏(s, d)要求π的代价是最小的且满足约束{π的带宽 ≥ b,π的延迟 ≤D, … }

case(没找到路径 π ):

寻找最小代价路径(s, d, b, D)

if(没找到路径σ)then"路径未找到"

将(插入或替换∏(s, d),

标记流F并路由F通过σ

case(找到路径 π):

if(π的利用率较轻) then

标记流F并路由F 通过π

endif

σ寻找最小代价路径(s, d, b, D)

if(没找到路径σ)then"路径未找到"

if(σ的代价

将σ插入或替换∏(s, d),

标记流F并路由F通过路径s

else /* π 更好*/

标记流F并路由F 通过路径π

endif

}

算法2显示,在流请求F下,每对类粒度算法首先试图从路由缓冲中提取最小代价可行路径π。如果提取失败,则试图计算最小代价可行路径σ。如果找到σ,每对类粒度算法分配一个新的标记给σ, 将新标记插入路由缓存,然后将流请求F标签/路由,直接通过σ。而如果找到π,且路径仅被很少利用,每对类粒度算法标记流F并将它路由到路径π。否则,流被阻塞。如果路径的利用率σ(π)超过了预先制定的界限,每对类粒度算法将F路由到缓存中已有的一个π,或路由F通过一条新计算的路径σ,任何一个都是代价最小。因此,流量流能被聚集到相同的转发类(FEC)并在边缘路由器上相应地标上标签。相同FEC的流可能要求不同的服务类。从而,S-D对之间的流可能被路由到最多m条不同的路径。其中m是路由类的最大值。在每对类粒度算法中,寻找最小代价路径函数用CSP或WSP计算最小代价路径。

2 算法评估

为在不影响每流QoS需求的情况下减少阻塞的可能性,从粒度方面提出了两个路由方案。每对流方案增加了每对缓存(P缓存)和每流溢出缓存(O缓存)作为路由缓存。如果P缓存不能满足带宽需求,则该路径上的流被分别路由,它们的路由决定溢出到O缓存。每对类方案将流聚集到一些转发类。这里包在边缘路由被打上标签,快速转发到核心网。这个方案减少了路由缓存规模,适合于MPLS网络。

通过限制路由标签的数目,路由算法可将每个S-D对之间的流沿有限的路径路由,通过给相同流的数据包打上相同的标签来强制执行。相对于每流粒度,路由器的转发程序仅检查标签路由缓存的规模限制在ИO(n2m)。其中n是网络节点的数目;m为标签数。如果基于约束的路由分布在边缘节点上,每个节点缓存到其他n-1个目的地的m条路径,路由缓存的规模限制减小到O(nm)。

2.1 网络和流量模型

仿真在Waxman模型的基础上,有100节点的随机图1上运行。模型中n个节点在网格上随机分布。在节点对u,γ之间引入边缘,图中节点的平均度在范围[3.5,5]。假定每条链路有155 Mb/s的STM-1或OC-3。

假定有两种类型的QoS流量:GS1平均速度为3 Mb/s,而GS2平均速度为1.5 Mb/s。流的到达在每节点上独立,遵循Poisson模型。流的持续时间服从平均值为μ的指数分布。源路由器的相邻链路的链路状态立即更新,而其他链路周期性地接收链路状态公告(LSA)。

2.2 仿真结果

仿真主要检查在中等流量负载下(如, ρ= 0.7)流的行为,这里大部分阻塞率都不会超过20%。此外,95%的信心间隔在这里报道的所有统计的仿真平均的5%内。

图1 阻塞率随链路状态更新周期变化比较

正如所料,大的更新周期增大了流的阻塞率。然而,当更新周期超过一个临界值时,阻塞并不是越来越高。曲线的上升在流平均持续时间较长的情况下比流平均持续时间较短的情况下要慢。这种现象暗示,为了得到更正确的网络状态和更好的QoS路由性能,更新周期不应超过流的平均持续时间 。

结果还显示,每对粒度路由比其他粒度的阻塞率高。纯每对粒度的网络中,流量往往形成瓶颈,比其他网络更难平衡。相反,在每流粒度和每对流粒度网络中,流量在大型网络里更有机会得到选择路径。直观地看,有最好粒度的每流粒度方案能得到最低的阻塞率。但在实验中,这并不总是正确的。事实上,有CSP的每流粒度方案有最强的路径计算功能;它能在重负载下找到可行路由,只是路径更长。长路径的流比短路径的流利用更多的网络资源。最后,网络资源耗尽;新到来的流只有在其他流结束后才被接纳。这就是每流粒度方案与提出的每对/流粒度和每对/类粒度方案类似或在某些方面更差的原因。

另外,由于有大的更新周期,链路状态信息减小了每流粒度方案的路径计算效果。可能将不可行路径误认为可行(乐观的),或将可行路径误认为不可行(悲观的)。因而,在前一情形下会有更多的信号阻塞,在后者中有更多路由阻塞;两者都是对每流路由的性能的否定。

显然,将CSP和WSP作统计上的比较,在这个实验中WSP比CSP表现更好。WSP用宽度优先搜索找到多个最短路径,选出带宽最宽的一条,达到某种程度上的负载均衡。但另一方面,流量更加集中在CSP计算网络。

2.3 缓存规模

图2显示不管流量负载,每流,每对和每对类方案的缓存几乎保持不变。另一方面,每对/流的缓存随着流量负载的增加而增加。

图2 每流的平均缓存数随负载变化比较

每对的缓存规模被限制为(n-1)2 复杂度O(n2)。其中n为节点数。每对/类缓存被限制为(n-1)2m,复杂度为O(n2m)。其中m为类的数目。

在每流方案中,缓存规模随着流数目的增长而动态增长。每对/流和每对类方案使用混合粒度,这两个都很显著地将缓存规模减小到约10%(轻负载)和20%~40%(重负载),且阻塞率没有增加。

3 结 语

本文研究了在MPLS网络中粒度对基于约束的路由的影响,提出混合粒度方案来完成成本效益可测量性。有每对/流粒度的每对流方案增加了P缓存和O缓存作为路由缓冲,完成了低阻塞率。有每对/类粒度的每对类方案将流汇聚到几条路由路径,从而允许数据包在有限的缓存规模内被标签转发。

仿真结果显示,每对粒度缓存路由阻塞率最高,因为粗粒度限制了网络状态的精确性。每对/流粒度加强了路径选择能力。而每对/类粒度在有限的路由缓存下有小的阻塞率。因此,这种方案适合在MPLS网络中,基于约束的路由。

参考文献

[1]张连俊,李春华.基于MPLS的IP-QoS机制研究[J].计算机工程与设计,2006,27(20):3783-3785.

[2]王必荣,孟昭鹏,范明君,等.MPLS流量工程提升IP网络QoS性能的研究[J].电子与信息学报,2006,42(2):948-953.

[3]王勇智,刘利强.下一代因特网QoS路由机制的研究[J].计算机技术与发展,2006,16(4):105-118.

[4]林娜,宋利雪.一种改进的移动节点快速切换算法研究与仿真[J].小型微型计算机系统,2009,30(11):73-76.

[5]李彬,陈向东.基于MPLS流量工程的重路由算法研究[J].计算机工程与应用,2006,42(31):153-156.

[6]张连俊,王善斌. 基于MPLS的多类路由选择机制研究[J]. 计算机工程与设计,2007,28(17):4143-4144.

[7]LEE Y, SEOL Y F, WANG Z. A constrained multipath traffic engineering scheme for MPLS Networks[C]//ICC′02. New York: IEEE, 2002: 2431 - 2436.

[8]蒋国明,魏仰苏,孟兆航.MPLS的基于最小干涉的负载均衡算法研究[J].计算机工程与设计,2007,28(2):371-372.

[9]KUROSE J F, ROSS K W. Computer networking: a top-down approach featuring the imemet[M].北京:人民邮电出版社,2004.

[10]陈凤,宋玲,马强. 基于MPLS网络的选播QoS路由算法[J].计算机工程,2008,24(2):274-278.