锐客网

  1. 首页 > it技术 > >

拥塞控制与多径路由

【拥塞控制与多径路由】?When you read a paper,you understand it from the perspective of reader,but when you write a review,you understand from the perspective of author and explain the key points to other readers.
?[1]我上学期就看过，但是今天再看的时候，没有一点印象。做笔记很重要，可以留下一些思考的印迹。
?网络可以建模为一个闭环反馈系统，可以通过控制理论分析其系统的稳定性。
?Kelly在1998年发表的论文[2],引入了经济学中的utility function，可以说开启了网络拥塞控制的理论分析时代。其主要理论基本就是两个公式，可以参考我之前写的博文[3]。Low又在里面深耕了几年，算是对于网络中的拥塞算法与主动队列管理的实例分析。[2]的引用量就达到了可怖的5500多次了。[2]可以算的是“网络拥塞控制的数学原理”。确实有这样一本书《the mathematics of internet congestion control》，讲的就是Kelly的两个式子。现在入门，大概也能弄些残羹冷炙。
?[1]讲明的是在路由器节点上搞多径，怎么控制数据流的分割比例。但是基于时延的代价函数，导致路由器队列时延的震荡。
?i,j表示相邻的路由器节点， i→ji → j 为一条链路。
?在源节点，发送速率：
xks(k)=xk(1)(1) x s ( k ) k = x k
?节点j(路由器)的inflow rate:
xkj=∑i:(i,j)∈Lyki,j(2)(2) x j k = ∑ i : ( i , j ) ∈ L y i , j k .
?The outflow balance of node i is:
xki=∑j:(i,j)∈Lyki,j(3)(3) x i k = ∑ j : ( i , j ) ∈ L y i , j k .
?第一个问题，utility function maximization,max∑kUk(xk)m a x ∑ k U k ( x k ) ，约束为 yl≤cly l ≤ c l .
?第二个问题，最大化：
S:=∑kUk(xk)?∑l?l(yl)(5)(5) S := ∑ k U k ( x k ) ? ∑ l ? l ( y l ) .
?作者称S是经济学中的aggregate function。
?把一条数据流看为一个商品，用k表示。 αdi,jα i , j d 为目的为d，在链路(i,j)的数据流分割比例。
yki,j=αd(k)i,jxki(6)(6) y i , j k = α i , j d ( k ) x i k
定义i到d的代价：
qdd=0,qdi=∑j:(i,j)∈Lαdi,j[pi,j+qdj](8)(8) q d d = 0 , q i d = ∑ j : ( i , j ) ∈ L α i , j d [ p i , j + q j d ]
?其中 αdi,jα i , j d ，节点i经由j最终发送至目的节点d的数据流的分割比例。 qdiq i d 为i到d的代价，可以理解为时延。
? qkq k 为数据流 xkx k 经历过所有链路的加权平均代价。 plp l 为数据流在子路径上的代价。
xkqk=∑l∈Lyklpl(9)(9) x k q k = ∑ l ∈ L y l k p l
?对(9)求导，并认为子链路上的代价在小尺度时间不变，但是路径分割比例随时间变化：
x˙kqk+xkq˙k=∑l∈Ly˙klpl(10)(10) x ˙ k q k + x k q ˙ k = ∑ l ∈ L y ˙ l k p l
x˙kqk=∑l∈Ly˙klpl?∑(i,j)∈Lxkiα˙d(k)i,j[pi,j+qdj](11)(11) x ˙ k q k = ∑ l ∈ L y ˙ l k p l ? ∑ ( i , j ) ∈ L x i k α ˙ i , j d ( k ) [ p i , j + q j d ]
?另：
αdi,j≥0,∑j:(i,j)∈Lαdi,j=1(13)(13) α i , j d ≥ 0 , ∑ j : ( i , j ) ∈ L α i , j d = 1
?对于导数 α˙diα ˙ i d ,加以以下约束：
1)
∑j:(i,j)∈Lα˙di,j[pi,j+qdj]≤0(14)(14) ∑ j : ( i , j ) ∈ L α ˙ i , j d [ p i , j + q j d ] ≤ 0
?(3)式的约束，表示的就是对于代价小的路径，要增加相应路径上的 αα 的值，对于路径代价大的路径，要减少相应路径上的 αα 的值。假设节点i相连的节点只有j1,j2。 πdi,j=pi,j+qdjπ i , j d = p i , j + q j d ，假设 πdi,j1<πdi,j2π i , j 1 d < π i , j 2 d 。有 α˙(πdi,j1+πdi,j2)=πdi,j1(α1+Δα)+πdi,j2(α2?Δα)?πdi,j1?α1?πdi,j2?α2Δt<0α ˙ ( π i , j 1 d + π i , j 2 d ) = π i , j 1 d ( α 1 + Δ α ) + π i , j 2 d ( α 2 ? Δ α ) ? π i , j 1 d ? α 1 ? π i , j 2 d ? α 2 Δ t < 0 。
2)根据式(2)可得：
∑j:(i,j)∈Lα˙di,j=0(15)(15) ∑ j : ( i , j ) ∈ L α ˙ i , j d = 0
3)当一条 α˙di=0α ˙ i d = 0 ，说明通过数据流分割，各条路径代价达到均衡点，或者这条路径代价过大，没有被分配负载。
qdi=pi,j+qdj or αdi,j=0 and qdi ?可以找到满足上述约束1-3的 α˙α ˙ 值。其中一个为：
α˙di,j=βi(πdiˉˉˉˉˉ?πdi,j)α ˙ i , j d = β i ( π i d ˉ ? π i , j d ) ,增加代价小于代价平均值的链路上的数据分割比例，而减少剩下路径的分割比例。当然，增加数据流的发送，也会增加相应链路上的代价，最终达到equilibrium point。这种思想在wVegas也有体现，参看[4].
?这种在路由器节点上基于时延的路由，有严重的缺陷，同tcp协议数据包的有序性相违背。
[1]A unified approach to congestion control and node-based multipath routing(2009-ton)
[2]Rate control for communication networks: shadow prices, proportional fairness and stability
[3]Multipath TCP与网络效率最大化
[4]tcp拥塞控制vegas的数学分析

    推荐阅读


    上一篇：AbstractMap作为Map接口的骨干实现是一种怎样的存在（）

    下一篇：工具和库的使用--pomelo-sync