流量分配算法剖析.ppt

网络流量分配算法 ——基于时延和跳数 摘要 提出了一种资源占用最小的并行标签交换路径( LSPs) 流量分配算法。该算法根据LSP( label switch paths)的跳数和时延来进行自适应流量分配，避免了传统基于最短路径路由流量分配算法引起的网络拥塞。仿真表明，该算法经过约15 次迭代就可以收敛到预定的阈值，实现多协议交换网络资源的优化利用。 　　根据Internet 工程任务组( IETF, internet engineering task force) 的定义， Internet 流量工程是指能够处理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 ≤Ck，Ck 为链路k 的容量，并且有Σk λk=λ 考察代价函数可以发现，其最重要的2 个参数是带宽和跳数。时延、丢包率与带宽成反比， 而费用一般与带宽成正比. 跳数则反映资源占用的概况， 同样的数据流穿过的跳数越多其资源消耗得越大，因此，可以利用这2 个参数作为分配流量的基准。 然而在实际的网络中， 一条LSP 的剩余带宽是很难测量的， 相对而言，时延却较易测量。对于一条LSP k ，令其平均分组时延为Tk，跳数为Nk. 定义Xk= Tk×Nk 作为分配流量的基准，则代价函数可以表示为 F= Σk Xk = Σ Nk Tk(λk) λk (2) 其中，约束条件为λ= Σkλk ，并且λk≤Ck 。所以分配流量的目标是使F最小。而方程(2) 有解的充分条件是函数F为凹函数，这时存在一组值(λ*1 , λ*2 , λ*3 ,?, λ*k , ?, λ*n ) ，使得F最小。因为对于任何一条显示LSP k 来说其一旦建立，则该LSP上的跳数就是固定的。同时根据F最小原则来分配流量，意味着对于2 条LSP 来说, 如果其平均时延相等，跳数少的LSP 将被优先分配流量，这样就达到资源占用最少的目的。 对于参数为λk 的Tk(λk ) 函数来说, Tk(λk) 是单调增的。显然，随着流量的增加时延肯定会增大。根据最优化理论，在约束条件下，式( 2) 如 果存在一组向量[λ*1 , λ*2 , ?, λ*k , ?, λ*n ] 使得F有最小值,则 由于Tk (λk ) 是单调增的，所以对于式( 2)的最小值所对应的λ*k 可以按下面计算： (3) 求得λ*k = αkλ，Σkαk= 1。根据αk就可以进行流量分配。实际网络中， 由于Tk (λk ) 不可能有精确的表达式，因此也就不可能计算出准确的αk ， 所以基于上述推导结果进行准确的流量分配是很困难的。 虽然Tk(λk) 没有精确的表达式，但从统计的观点来看，如果其统计平均时延能够估算的话，也可以进行统计优化的流量分配。在广域网中，流量的变化并不如想象中的剧烈，至少在5min内感觉不到明显的变化。所以可以对每条LSP 进行时延测量，因为5 min 的时间远远大于时延测量的间隔时间。因此一条LSP 可以看作一个M/ M/ 1 服务模型。其平均时延T =1/(μi- αλ)，据此可以估算出LSPi 的平均剩余处理能力μi。根据上述分析在一个时延测量时间段内可以认为μi为常量。根据估算的μi 值就可以进行基于平均统计资源占用最小的流量分配计算。本文正是基于统计