孫士國

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

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

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

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

1 問題構建

1.1 λ網(wǎng)絡建模

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

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

1.2 速率分配問題

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

速率分配算法應當充分利用每個源端和目的端的容量，同時保持可行.可行就是要求每個源端和目的端的會話總速率不超過其容量，而且每個會話速率不超過其期望速率.因此，對于每個節(jié)點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(·)為更新函數(shù).函數(shù)f(·)可能依賴于會話期望速率、每個源端和目的端的狀態(tài)等.對于一個運行良好的網(wǎng)絡來說，速率分配算法也應當是穩(wěn)定且收斂的.

2 分布式速率分配算法

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

(5)

(6)

(7)

2.2 源端和目的端算法

如果當前會話速率小于目標速率，就調(diào)節(jié)其接近目標速率xf，表達式為

(8)

式中：α為步長調(diào)節(jié)因子，0<α<1；xf為目標速率，其表達式為

(9)

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

(10)

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

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

x(t+1)=x*

(11)

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

x(t)=x*

(12)

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

(13)

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

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

(14)

可見，在平衡狀態(tài)下，D=0.

3.1 一個目的節(jié)點和多個源節(jié)點

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

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

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

圖2 5個會話速率變化軌跡Fig.2 Rate change trajectories for five sessions 表1 5個會話的平衡速率和目的節(jié)點速率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目的節(jié)點1.001.01.001.01.01

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

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

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

3.2 多個目的節(jié)點和多個源節(jié)點

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

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

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

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

4 結 論

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