流量分配算法.ppt

网络流量分配算法——基于时延和跳数摘要?提出了一种资源占用最小的并行标签交换路径( LSPs) 流量分配算法。该算法根据 LSP( label switch paths) 的跳数和时延来进行自适应流量分配,避免了传统基于最短路径路由流量分配算法引起的网络拥塞。仿真表明,该算法经过约 15 次迭代就可以收敛到预定的阈值,实现多协议交换网络资源的优化利用。? 根据 工程任务组( IETF, engineering task force) 的定义, 流量工程是指能够处理 IP 网络性能评估以及性能优化的一种网络工程。支持显示路由的多协议标签交换( MPLS) 技术的出现及其日益成熟,为流量工程的实现提供了一种基本的机制。? Elwalid 以及 Widjaja 等人首次提出了 MPLS 自适应流量工程( MATE , adaptive traffic engineering ) 的概念,但只是简单地从避免拥塞的角度出发把流量从高拥塞的 LSP 转移到不拥塞的 LSP 上。其仿真也表明在整个网络负荷很小的时候能够正常工作,随着网络负荷的增加,其收敛性会变差。本文把跳数和时延作为评估参数, 提出一种改进的显式并行 LSP 分配流量算法, 并通过仿真验证该算法的有效性以及收敛性。 1 理论分析? MAT E 的目标是使整个网络的性能得到最优化,通过在一对入口标签交换路由器( LSR , label switch router) 和出口 LSR 之间动态配置流量来实现流量的均衡。如图 1 所示,从入口 LSR 进入的流量为 K,由 LSR 将流量分配到各个 LSP 上。图1 MPLS 网络结构图?设分配的代价函数为 F= Σ k? k ( λ k ) (1) 其中, λ k为链路 k 上分配的流量, λ k≤C k,C k为链路 k 的容量, 并且有Σ k λ k=λ考察代价函数可以发现,其最重要的 2 个参数是带宽和跳数。时延、丢包率与带宽成反比, 而费用一般与带宽成正比. 跳数则反映资源占用的概况, 同样的数据流穿过的跳数越多其资源消耗得越大, 因此,可以利用这 2 个参数作为分配流量的基准。?然而在实际的网络中, 一条 LSP 的剩余带宽是很难测量的, 相对而言, 时延却较易测量。对于一条 LSP k ,令其平均分组时延为 T k,跳数为 N k . 定义 X k = T k×N k作为分配流量的基准,则代价函数可以表示为 F= Σ k X k = Σ N k T k(λ k ) λ k (2) ?其中,约束条件为λ= Σ kλ k ,并且λ k≤C k。所以分配流量的目标是使 F最小。而方程(2) 有解的充分条件是函数 F为凹函数,这时存在一组值(λ* 1 , λ* 2 , λ* 3 , ?, λ* k , ?, λ* n ) ,使得 F最小。因为对于任何一条显示 LSP k 来说其一旦建立,则该 LSP 上的跳数就是固定的。同时根据F最小原则来分配流量,意味着对于 2 条 LSP 来说, 如果其平均时延相等,跳数少的 LSP 将被优先分配流量,这样就达到资源占用最少的目的。?对于参数为λ k的T k(λ k ) 函数来说, T k(λ k ) 是单调增的。显然,随着流量的增加时延肯定会增大。根据最优化理论,在约束条件下,式( 2) 如果存在一组向量[λ* 1 , λ* 2 , ?, λ* k , ?, λ* n ] 使得 F有最小值,则由于 T k (λ k ) 是单调增的,所以对于式( 2) 的最小值所对应的λ* k可以按下面计算: (3) 求得λ* k = α kλ,Σ kα k = 1 。根据α k就可以进行流量分配。实际网络中, 由于 T k (λ k ) 不可能有精确的表达式,因此也就不可能计算出准确的α k,所以基于上述推导结果进行准确的流量分配是很困难的。?虽然 T k(λ k ) 没有精确的表达式,但从统计的观点来看,如果其统计平均时延能够估算的话,也可以进行统计优化的流量分配。在广域网中,流量的变化并不如想象中的剧烈,至少在 5min 内感觉不到明显的变化。所以可以对每条 LSP 进行时延测量,因为 5 min 的时间远远大于时延测量的间隔时间。因此一条 LSP 可以看作一个 M/ M/ 1 服务模型。其平均时延 T =1/( μ i - αλ),据此可以估算出 LSP i的平均剩