λ網絡中一種分布式速率分配算法*

孫士國

(華北科技學院 基礎部， 河北 三河 065201)

光傳輸的發展極大地推動了可用網絡帶寬的快速增加，如密集波分復用使得每根光纖能攜帶成百上千個λ(即波長).專用光路、高速交換和高速路由能使中心網絡具有足夠的帶寬，這些容量可用來建立高速共享的、基于路由的互聯網和專用的光纖網絡，以及基于新的動態配置技術的動態專用網絡，通常稱這些高速專用網絡為“λ網絡”.在λ網絡中，可以基于需求來構建專用高速光路，以提供充足的、專用的端到端帶寬.

提供端到端高性能通信是有線、無線和衛星網絡研究中的一個長期性的挑戰課題.文獻[1]介紹了超密集波分復用(ultra-dense wavelength division multiplexed passive optical network，UDWDM-PON)的方案、結構、原理、集成設想和升級方式等，UDWDM-PON可以在C波段密集排到1 000個下行波長和1 000個上行波長，支持1 000個用戶，每個用戶獨立使用一對波長，并具有每個用戶接入帶寬10 Gbit/s的潛力；文獻[2]闡述了分層圖模型的概念，提出波長可變光網絡中的動態路由和波長分配算法(routing & wavelength assignment，RWA)，在提高波長資源利用率的同時，降低網絡阻塞率；文獻[3]為了解決時分復用無源光網絡的低帶寬、高延時，以及波分復用無源光網絡的高成本、低利用率的問題，提出一種新型時分波分混合復用無源光網絡系統.利用馬赫曾德爾干涉光開關陣列和高速鈮酸鋰馬赫曾德爾調制器，可靈活、快速地為不同光網絡單元傳遞數據包，減少了光調制器的使用數量，降低了系統成本.

常用的傳輸協議TCP被設計用作共享低帶寬網絡，因此，該協議在高速環境下不能很好地對帶寬和延遲增加作出響應，而且由于采用“和式增加、積式減少”(additive increase and multiplicative decrease，AIMD)控制算法，需要用較長時間來恢復數據包丟失和獲得高的帶寬.已有學者提出多種策略來改進標準的TCP，以實現大延時網絡中快速高效的傳輸.文獻[4]保持了TCP控制策略，但改進了TCP協議棧的實現；文獻[5]采用了并行連接；部分學者提出了一些高性能TCP控制策略來提高TCP在共享和分組交換網絡中的性能(如高速TCP和BIC-TCP[6])；基于時延的(如FAST-TCP[7])和基于速率的(如RBUDP和GTP[8])數據傳輸協議采用TCP來改進其數據包丟失.

1 問題構建

1.1 λ網絡建模

本文令G表示一個λ網絡，具有有限的節點集合V和有效會話集合K；用VS和VR分別表示源節點和目的節點集合；多個會話可以在相同的源節點或目的節點上開始或結束.

考慮一個離散時間模型，把時間分為相等長度的時隙.令每個會話k∈K有一個期望(峰值)速率Mk；令xk(t)為時隙t中會話k的瞬時速率，則x(t)=(x1(t)，x2(t)，…，xK(t))為時隙t中全部有效會話的速率向量；令每個源節點和目的節點v∈V有容量Cv，當v分別屬于VS或VR時，Cv或者是節點v的發送容量，或者是節點v的接收容量；令Kv表示節點v參與的會話集合.在本文模型中，節點v或者是一個源節點，或者是一個目的節點，但不能同時二者都是.因此，G(V，C，K，M)就可以用來描述λ網絡中的速率分配問題.

1.2 速率分配問題

λ網絡中速率分配的關鍵就是如何高效、公平地在有效會話之間的每個源節點和目的節點分配容量.

速率分配算法應當充分利用每個源端和目的端的容量，同時保持可行.可行就是要求每個源端和目的端的會話總速率不超過其容量，而且每個會話速率不超過其期望速率.因此，對于每個節點v∈V，則有

(1)

同時對于每個會話k∈K，則有

xk≤Mk

(2)

即可認為一個速率向量x是可行的.

(?p∈K)yp?xp?(?q∈K)yq?xqxp

(3)

x(t+1)=f(x(t+1))

(4)

式中，f(·)為更新函數.函數f(·)可能依賴于會話期望速率、每個源端和目的端的狀態等.對于一個運行良好的網絡來說，速率分配算法也應當是穩定且收斂的.

2 分布式速率分配算法

2.1 分布式速率分配與自適應

(5)

(6)

(7)

2.2 源端和目的端算法

如果當前會話速率小于目標速率，就調節其接近目標速率xf，表達式為

(8)

式中：α為步長調節因子，0<α<1；xf為目標速率，其表達式為

(9)

xf的每次迭代更新反映了剩余容量的變化.當全部未確定會話的最小會話速率大于目標速率xf時，就把剩余容量平均分配給全部會話，即把目標速率分配給每個會話，表達式為

(10)

通常，總是先使具有更低期望速率的會話的速率最大化.首先考慮具有最小速率的會話，只要速率最小，就讓其速率增加，只有當其被對等節點或期望速率限制，或達到了目標速率時，才停止增加.

源節點算法采用類似于目的節點算法的方式計算源節點的預期速率.在時隙t+1，會話k∈K的實際發送速率是會話k的期望速率、目的節點預期速率和源節點期望速率中的最小值.

x(t+1)=x*

(11)

對于任意初始速率向量x(0)(時刻t=0)，速率向量x在有限步數收斂到最終速率向量x*，即存在時刻t0>0，且對任意時隙t>t0，則有

x(t)=x*

(12)

除初始狀態(t=0)外，在時隙t≥1時，任何節點v∈V上的最大總速率不超過(1+α)Cv，則有

(13)

3 算法性能仿真及結果分析

本文對所提算法的性能在具有不同期望速率、流量模式和動態期望速率變化的網絡拓撲中進行仿真，仿真在NS-2仿真軟件環境中進行.

(14)

可見，在平衡狀態下，D=0.

3.1 一個目的節點和多個源節點

圖1為具有5個源節點和1個目的節點的網絡拓撲結構.每個源節點的會話終止于單一的目的節點.5個會話分配的速率(歸一化值)分別為0.1、0.2、0.3、0.4和0.5，每個源節點和目的節點的容量(歸一化值)為1.分布式算法采用的參數為α=0.1和β=0.1，這時會話的期望速率和接收節點存在瓶頸.

圖1 1個目的節點和5個源節點的拓撲結構Fig.1 Topological structure of one destination node and five source nodes

設在t=0時，全部會話的初始速率為(0，0，0，0，0)，且有不同的期望速率.全部會話和目的節點上的總速率隨時間的變化軌跡如圖2所示.由圖2可知，在20個時隙內，全部會話都收斂到平衡速率；在t=50時，會話1的期望速率從0.1開始增加到1，分布式算法對這種變化迅速做出響應，而且會話速率在短時間內收斂到一個新的平衡速率分配，同時每個會話獲得相同的速率0.2；在t=100、150、200、250時，終止會話5、4、3、2.由仿真結果可知，剩余會話速率能夠快速適應變化，填補空出的容量，并收斂到一個新的平衡速率分配.表1列出了各種時隙內的平衡速率分配.

圖2 5個會話速率變化軌跡Fig.2 Rate change trajectories for five sessions 表1 5個會話的平衡速率和目的節點速率Tab.1 Equilibrium rates of five sessions and rate of destination node

會話0～5051～100101～150151～200201～250251～300會話10.100.20.270.50.81會話20.200.20.200.20.20會話30.230.20.270.300會話40.230.20.27000會話50.230.20000目的節點1.001.01.001.01.01

為了說明分布式算法參數α和β對收斂性的影響，采用圖1的會話拓撲結構.圖3為D隨時間的變化關系曲線.圖3a中，α從0.05變化到0.2，β=0.1固定不變；圖3b中，β從0.05變化到0.2，α=0.1固定不變.

圖3 參數α和β對收斂性的影響Fig.3 Effect of parameters α and β on convergence

由圖3可知，較大的α值可以使算法更快收斂，一個大的α值在某些情況下可以得到更高的過沖；較大的β值也有助于系統快速收斂接近平衡點，但不如α值影響明顯.

3.2 多個目的節點和多個源節點

考慮3個源節點和3個目的節點的網絡拓撲結構.每個源節點和目的節點都參與3個連接會話，如圖4所示.圖4中，各個C值分別為各個節點容量(歸一化值).可以看到，源節點2的容量比其他節點要小，全部會話都有相同的期望速率(歸一化值)1；全部會話開始于t=0，初始速率分別為0.02、0.04、0.06、0.08、0.10、0.12、0.14、0.16、0.18，參數α=0.1，β=0.1.圖5為每個會話和每個源節點上的總速率隨時間的變化關系曲線.

圖4 3個源節點和3個目的節點的拓撲結構Fig.4 Topological structure of three source and three destination nodes

圖5 會話速率和源節點總速率隨時間的變化曲線Fig.5 Change curves between session rates and total rate of source node with time

由圖5可知，每個會話的速率以及每個源節點上的總速率在30～35個時隙內基本能夠收斂到平衡點.

4 結 論

本文針對具有充足帶寬的λ網絡中通信會話的源節點和目的節點容量的高效和公平分配問題進行了研究，構建了一個分布式速率分配和自適應算法，該算法不需要關于應用的任何信息.仿真結果表明，本文提出的分布式速率分配算法是穩定的，而且具有快速收斂的特性.