趙海軍,李 敏,李明東,岳 淼

(1.西華師范大學(xué)計算機(jī)學(xué)院,四川南充637009;2.成都供電公司信息通信分公司,成都610000)

基于多變量判決函數(shù)的最優(yōu)路由策略

趙海軍1,李 敏2,李明東1,岳 淼1

(1.西華師范大學(xué)計算機(jī)學(xué)院,四川南充637009;2.成都供電公司信息通信分公司,成都610000)

針對分布式并行處理系統(tǒng)中路由算法數(shù)據(jù)包的路由選擇問題,提出一種改進(jìn)的最優(yōu)化路由策略。從輸入數(shù)據(jù)包得到數(shù)據(jù)包前后到達(dá)時間分布Pt(x)和包大小分布Pp(x),采用權(quán)值函數(shù)通過對平均前后到達(dá)時間、平均包大小和向量的不斷學(xué)習(xí)獲得所有包的最小化平均延遲。仿真結(jié)果表明,該策略不僅在處理器數(shù)量發(fā)生變化,而且在包前后到達(dá)時間分布和包大小分布改變的情況下,都能獲得所有包的最小平均延遲。

分布式并行處理系統(tǒng);多變量;路由策略;平均延遲;最小化;流量強(qiáng)度

1 概述

近年來,隨著計算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展,并行處理技術(shù)已成為研究熱點(diǎn)。主要體現(xiàn)在以下5個方面:(1)對稱多處理技術(shù)。這種系統(tǒng)在結(jié)構(gòu)上一般是用總線將多個處理機(jī)連接而成。系統(tǒng)中的硬件和軟件都是對稱的。硬件上每個CP的能力完全相等,它們共享主存。軟件上共享一份操作系統(tǒng)代碼。(2)大規(guī)模并行處理技術(shù)。目前松耦合分布式存儲的MIMD型MPP系統(tǒng)是其主流技術(shù),關(guān)鍵技術(shù)包括節(jié)點(diǎn)結(jié)構(gòu)、高速互聯(lián)網(wǎng)絡(luò)和并行程序開發(fā)環(huán)境等。(3)工作站群機(jī)技術(shù)。是將一組工作站、服務(wù)器、小型機(jī)甚至巨型機(jī)或MPP系統(tǒng)用互聯(lián)網(wǎng)連在一起,構(gòu)成并行處理系統(tǒng)。(4)并行程序開發(fā)環(huán)境技術(shù)。它不僅要解決并行軟件的編程問題,還應(yīng)解決并行軟件的可移植性問題。(5)并行數(shù)據(jù)庫技術(shù)。即提高計算機(jī)在數(shù)據(jù)管理和查詢方面的能力。包括對數(shù)據(jù)庫的分區(qū)管理和并行查詢。多線程技術(shù)和虛擬服務(wù)器技術(shù)是目前并行數(shù)據(jù)庫實(shí)現(xiàn)中采用的重要技術(shù)［1］。

分布式并行處理系統(tǒng)是一種結(jié)構(gòu)復(fù)雜的計算機(jī)處理系統(tǒng),其基本特征是系統(tǒng)中有多個處理器(或稱為服務(wù)器)。在設(shè)計分布式并行處理系統(tǒng)時,要考慮多方面。其中主機(jī)間的最佳資源配置和最小通信延遲都是典型的和通常要考慮的方面,而這方面又著重體現(xiàn)在數(shù)據(jù)包的路由選擇算法。

針對當(dāng)前各種服務(wù)網(wǎng)絡(luò)結(jié)構(gòu)存在的問題,文

獻(xiàn)［1］針對計算機(jī)負(fù)荷并行處理的高效穩(wěn)定和最優(yōu)化問題,提出了選擇各節(jié)點(diǎn)狀態(tài)和啟動策略,以使通信開銷最小和負(fù)荷均衡的智能化任務(wù)分配算法。文獻(xiàn)［2］采用一種服務(wù)網(wǎng)絡(luò)架構(gòu),并提出使用向量長度的方法衡量不同服務(wù)路徑的優(yōu)劣從而得到非線性的合計函數(shù)F;文獻(xiàn)［3］從體系結(jié)構(gòu)上提出了動態(tài)重構(gòu)容錯算法,算法通過動態(tài)重構(gòu)數(shù)據(jù)分布和操作解決了系統(tǒng)節(jié)點(diǎn)和網(wǎng)絡(luò)故障,且使正在執(zhí)行的任務(wù)不被中斷,使系統(tǒng)可用性和效率得到大幅度提高。

本文主要研究并行傳輸處理器系統(tǒng)中數(shù)據(jù)包的路由選擇問題。該問題把到達(dá)包分配給幾個并行傳輸處理器中的一個,以使所有到達(dá)包的平均延遲最小化。對于重尾分布,文獻(xiàn)［4-6］提出了一種啟發(fā)式的基于包大小的路由算法;另一種常見的路由算法即JSD(Join Shortest Delay),但該算法被認(rèn)為是個單一的最佳算法,因為它僅使每個到達(dá)包的延遲最小。而單一基于包大小的固定隊列FQS(Fix Queue based on Size)算法是一種不公平算法;文獻(xiàn)［7］提出了貪婪吞吐量(Greedy Throughput,GT)算法,這種算法雖然可以提高部分并行處理器的效率,但會造成整個并行處理系統(tǒng)的延遲增加;文獻(xiàn)［8］提出了等負(fù)荷大小間隔任務(wù)分配(Size Interval Task Assignment with Equal load,SITA-E)算法,這種算法與文獻(xiàn)［7］的結(jié)果剛好相反。因此,尋找一個利用每個到達(dá)包大小、并使所有到達(dá)包延遲最小的全局最優(yōu)化算法仍是一個難題［9-14］。對此,本文提出路由判決的路由算法,以使所有到達(dá)包的平均延遲最小,提高分布式并行傳輸處理器的效率。

2 模擬最佳路由算法

把上述問題的數(shù)學(xué)模型表示為下列組合最佳問題P1:

其中,N,p,DN和un分別表示到達(dá)包的數(shù)量、并行處理器的數(shù)量、所有到達(dá)包的平均延遲和分配給第n個到達(dá)包的處理器。于是,求解問題P1的數(shù)值解就是確定最佳路由。

本文確定最佳路由的主要思想為:隨著輸入流量強(qiáng)度的增加,就把數(shù)據(jù)包分別分配給不同的處理器,然后設(shè)計出一個算法(本文稱為模擬最佳路由(Mimic Optimal Routing,MOR))來使所有到達(dá)包的平均延遲最小。

本文提出的MOR采用1個權(quán)值函數(shù)和3個參數(shù),即平均前后到達(dá)時間(1/λ),平均包大小(1/μ)和向量α=(α1,α2,…,αp-1);目標(biāo)就是通過從輸入流量獲得1/λ,1/μ和α的不斷學(xué)習(xí)來提高M(jìn)OR的適應(yīng)性,并得到滿足以下2個條件的權(quán)值函數(shù):

(1)MOR可工作于任意數(shù)量的同類型并行處理器;

(2)盡管前后到達(dá)時間分布Pt(x)和包大小分布Pp(x)未知且可能隨時間變化,但分別包含Pt(x)和Pp(x)的分布集St和Sp預(yù)先給定并可用于路由判決。

3 并行處理器模型

本文考慮的并行處理器模型M如圖1所示,由系統(tǒng)S和輸入流量T構(gòu)成。在系統(tǒng)S中,有p個傳輸處理器且每個處理器k有自己的無限長隊列k。每個到達(dá)包按照某種路由算法瞬間加入p個隊列中的一個(忽略選擇處理器的時間),每個到達(dá)包的傳輸按先到先服務(wù)。

圖1 并行處理器模型M(S,T)

為了得到到達(dá)包的平均延遲表達(dá)式,令Ck為處理器k的傳輸速率,xn和tn分別為系統(tǒng)S中第n個到達(dá)包的大小和到達(dá)時間。服務(wù)器k在時刻t的騰空時間(Wk(t))等于在時刻t通過處理器k傳輸?shù)陌氖Ｓ鄠鬏敃r間與在時刻t隊列k中所有包等待傳輸?shù)目偟臅r間之和。因此,如果第n個到達(dá)包被分配給處理器un,則對所有k∈Sp={1,2,…,p},有:

如果un=k,則,否則。文中的t-(t+)表示正好在t之前(之后)的時刻。因此,在時間間隔［tN0+1,tN+N0］內(nèi)到達(dá)的N個包的平均延遲為:

輸入流量T可以用集合{tn}和{xn}來表示,它們的值按照某個概率分布來確定。設(shè)前后到達(dá)時間tn+1-tn和包大小xn的概率分別為Pt(x)和Pp(x)。在本文中,對Pt(x)和Pp(x)采用下列3個分布:

Pe(x;m),Pu(x;m)和Pt(x;m),Pe(x;m)是均值為m的指數(shù)分布,Pu(x;m)是區(qū)間(0,2m)上的均勻分布;Pt(x;m)是模式為m,左端點(diǎn)為0,右端點(diǎn)為2m的三角分布。另一方面,系統(tǒng)S可表示為C={C1,C2,…,Cp}。設(shè)所有處理器是同類的(C1=C2=…=Cp),因此,對所有k∈Sp,Ck=C/p,C(C=∑pk=1Ck)為總的傳輸速率。所以系統(tǒng)S可以由p和C來決定。

4 MOR算法

4.1 MOR的解析表達(dá)式

假設(shè)MOR把第n個到達(dá)包分配給處理器,則如果Mn,k=mini∈SpMn,i時,。其中:

其中,Mn,k可視為分配第n個到達(dá)包給服務(wù)器k的耗時。因此,MOR就是選擇一個處理器以使耗時最小。式(3)中的wn為權(quán)值函數(shù),與流量強(qiáng)度In有關(guān)。In定義為In=λn/Cμn,1/λn和1/μn分別為在時刻測得的輸入流量T的平均前后到達(dá)時間和平均包大小;式(3)中的φn用來調(diào)整和的比例,φn的表達(dá)式為:

當(dāng)最佳權(quán)值wn用一個最優(yōu)算法求解時,φn有助于快速收斂到最優(yōu)的解。

設(shè)系統(tǒng)S的結(jié)構(gòu)為C,狀態(tài)為W=(W1,W2,…,Wp),到達(dá)包大小xn對路由判決來說都是已知的。如果wn,α=(α1,α2,…,αp-1),1/λn和1/μn給定,則由式(3)～式(5),就可以得到判決函數(shù)如下:

由于1/λn和1/μn可以通過測量時刻的輸入流量T來獲得,因此下面主要討論如何決定這4個參數(shù)中的另外2個參數(shù)α和wn的值。

4.2 α的確定

α的計算基于假設(shè):如果所有前后到達(dá)時間{tn+1–tn}接近于0,則MOR就收斂?；谶@個假設(shè),α就是最優(yōu)化問題P2的解:

其中,JN是在下列2個條件下得到的前N個到達(dá)包的期望平均延遲。(1)所有N個包的大小是獨(dú)立、均勻分布的連續(xù)隨機(jī)變量,而且它們的概率分布為Pp(x);(2)t1=t2=…=tN。同時路由判決{un}按順序u1,u2,…,un進(jìn)行。因而JN可表示為:

這里α0=0,αp=∞,且:

由于所有處理器同類(C1=C2=…=Cp),式(8)右邊第一項是一個常量。因此,問題P2的解又等價于問題P3的解:

假設(shè)dPp(x)/dx≠0,如果x∈［xmin,xmax］。這里xmin和xmax分別為Pp(x)中的最小和最大包大小。對k=1,2,…,p–1,α使得F(α)為局部極小值(也就是(F(α)/(αk=0)的條件就可以表示為:

為了實(shí)時計算α值,用(x+s)代替式(11)中的被積函數(shù)(x+αk),對k=1,2,…,p-1有:

其中,1/μ是Pp(x)的平均值(也就是平均包大小)。如果s＞0且式(10)成立,則式(12)有唯一解。這里p(x)=dPp(x)/dx。因此,G(αk)=0有唯一解。用牛頓法可一一得到α1,α2,…,αp-1,使α的計算量大大減少。

由于s替換αk,它必須接近αk,又由于α1,α2,…,αp-1分布在Pp(x)的均值1/μ周圍,因此1/μ是一個很好的替換。當(dāng)時,令為式(12)的解,且令,就可得到α(1),α(2),…,初始值為α(1)=(1/μ,…,1/μ)。

4.3 權(quán)值函數(shù)的確定

假設(shè)以下3個條件用于權(quán)值函數(shù)的計算:

(1)Pt(x),Pp(x)∈Sd(={Pe(x;1),Pu(x;1),Pt(x;1)});

(2)對每對Pt(x)和Pp(x)來說,輸入流量T({tn}和{xn})是唯一的;

(3)N=4(105且N0=N/10。

從條件(1)和條件(2)可知,當(dāng)改變1/λ,1/μ和C其中之一時,流量強(qiáng)度I(=λ/μC)都要變化(這里1/λ和1/μ分別為Pt(x)和Pp(x)的均值),

所以僅考慮1/λ=1/μ=1的情形,這時強(qiáng)度可簡單地表示為I=1/C;條件(3)包含在狀態(tài)W變成幾乎穩(wěn)態(tài)后,N0(=N/10)大到足以用來計算平均延遲,即使N進(jìn)一步增大,計算結(jié)果也沒有明顯變化。

令DN(N0,{un};Pt(x),Pp(x))表示當(dāng)輸入流量T由Pt(x)和Pp(x)產(chǎn)生時由式(2)給出的平均延遲DN。首先來看最佳權(quán)值函數(shù),因為當(dāng)Pt(x)和Pp(x)已知時,要使用這個權(quán)值函數(shù)。對Pt(x)和Pp(x)來說,最佳權(quán)值w?(Pt(x),Pp(x))(簡記為w?)的定義必須是w?∈Sw(={0,Δw,2Δw,…,1}),且對所有w∈Sw滿足:

這里MOR按式(7)給出且α(3)必須在計算w?之前計算。因為對所有w∈Sw,必須得到DN。對強(qiáng)度I(=1/C)來說,計算DN的次數(shù)就是集合Sw(|Sw|=1/Δw+1)中的元素的數(shù)量。最佳權(quán)值函數(shù)w?(I;Pt(x),Pp(x))(簡記為w?(I))的定義對所有I∈SI(={ΔI,2ΔI,…,4})成立。

5 MOR算法的性能仿真

5.1 仿真環(huán)境及模型

為了對算法的性能進(jìn)行測試,本文在Linux環(huán)境中,采用Opnet Modeler 10.0A網(wǎng)絡(luò)仿真平臺,并結(jié)合C++編程語言來對算法進(jìn)行仿真。

用Opnet Modeler的Rapid Configuration方式建立仿真網(wǎng)絡(luò)拓?fù)?。其中源?jié)點(diǎn)采用Possion PMF函數(shù)得到按泊松分布產(chǎn)生的DP數(shù)據(jù)包輸入流量,數(shù)據(jù)包長度服從64 Byte～3 036 Byte的均勻分布,保護(hù)帶時間為5 μs,最大負(fù)載為100 000 bit/s;工作站節(jié)點(diǎn)(服務(wù)器)數(shù)量分別設(shè)置為3和10,工作站節(jié)點(diǎn)模型均相同,到達(dá)每個工作站節(jié)點(diǎn)的DP數(shù)據(jù)包采用Exponential PDF函數(shù)得到前后到達(dá)時間分布Pt(x)和包大小分布Pp(x)的指數(shù)分布業(yè)務(wù)流和采用niform PDF函數(shù)得到前后到達(dá)時間分布Pt(x)和包大小分布Pp(x)的均勻分布業(yè)務(wù)流,且按先進(jìn)先出(FIFO)的方式存于工作站節(jié)點(diǎn)處理器的模塊存儲器中,仿真時間設(shè)置為60 s。由于是基于包的仿真機(jī)制,因此采用背景業(yè)務(wù)能加速仿真運(yùn)行速度。

5.2 仿真結(jié)果及分析

對本文提出的MOR算法和現(xiàn)有主要路由算法的性能進(jìn)行仿真比較,性能指標(biāo)為數(shù)據(jù)包的平均延遲。用于比較的現(xiàn)有主要路由算法包括等負(fù)荷大小間隔任務(wù)分配(Size Interval Task Assignment With Equal Load,SITA-E)算法、最短期望延遲(Shortest Expected Delay,SED)算法(等價于JSD)、貪婪吞吐量(GT)算法。分別對服務(wù)器數(shù)量為3和10,Pt(x),Pp(x)為指數(shù)和均勻分布的仿真結(jié)果如圖2所示。

圖2 MOR算法與現(xiàn)有路由算法的性能比較

從圖2可見,MOR是最優(yōu)的,JSD是次優(yōu)的。MOR的平均包延遲在Pt(x)=Pp(x)=Pe(x;1)且p=3、Pt(x)=Pp(x)=Pe(x;1),p=10和Pt(x)=Pp(x)=Pu(x;1)且p=3,Pt(x)=Pp(x)=Pu(x;1)且p=10的情況下比SITA-E和GT的平均包延遲都要小得多,且隨著流量強(qiáng)度的增加,平均包延遲減

少得更多,這對負(fù)荷流量日益加大的并行處理系統(tǒng)來說無疑節(jié)約了傳輸時間而相應(yīng)地提高了處理速度;從圖2還可看到,在重負(fù)荷條件下,所有算法的性能都將隨p的減小而提高,這除了與算法本身因素有關(guān)外,還與處理器速度和通信鏈路的帶寬等因素有關(guān),后者不屬于本文研究的內(nèi)容。

6 結(jié)束語

本文提出一種模擬最佳路由(MOR)算法,該算可工作于任意數(shù)量的同類服務(wù)器。在目前應(yīng)用的大多數(shù)互聯(lián)網(wǎng)中,如文件傳輸和基于IP的語音在一個會話內(nèi)的所有IP包(除最后傳輸?shù)陌?大小相同。因此,考慮在一個會話內(nèi)的IP包大小是不變的。當(dāng)流量很大且發(fā)生突變時,可以把MOR擴(kuò)展成自適應(yīng)MOR。自適應(yīng)MOR從輸入流量中獲得統(tǒng)計值,并能在前后到達(dá)時間或包大小分布變化后作出響應(yīng),下一步將對以下3個方面加以研究:(1)α的近似值的計算;(2)權(quán)值函數(shù)的動態(tài)選擇,它基于近似包大小的分布;(3)包大小分布的有效近似值,如包大小區(qū)間［0,L］的動態(tài)選擇。

［1]崔夢天,趙海軍,李明東,等.基于智能化分配算法的計算機(jī)負(fù)荷并行處理技術(shù)［J］.系統(tǒng)工程與電子技術(shù), 2005,30(11):2270-2273.

［2]吳華鑫.分布式服務(wù)網(wǎng)絡(luò)中保證QoS的服務(wù)路由算法研究［D］.合肥:中國科學(xué)技術(shù)大學(xué),2009.

［3]左朝樹,劉心松,邱元杰,等.分布式并行服務(wù)器的動態(tài)重構(gòu)容錯算法［J］.系統(tǒng)工程與電子技術(shù),2005, 27(5):900-913.

［4]Pavone M,Frazzoli E,Bullo F.A Daptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment［J］.IEEE Transactions on Automatic Control,2011,56(6):1259-1274.

［5]Mohammad S B.The Effect of Heavy-tailed Distribution onthePerformanceofNon-contiguousAllocation Strategies in 2D Mesh Connected Multi-computers［C］// Proceedings of IEEE International Symposium on Parallel& Distributed Processing.Washington D.C.,USA:IEEE Press,2009:1-8.

［6]Oida K,Shinjo K.Characteristics of Deterministic Optimal Routing for a Simple Traffic Control Problem［C］// Proceedings of IEEE IPCCC’99.Washington D.C.,USA: IEEE Press,1999:386-392.

［7]Shenker S,WeinribA.TheOptimalControlof Heterogeneous Queueing Systems:A Paradigm for Load-SharingandRouting［J］.IEEETransactionson Computers,1989,38(12):1724-1735.

［8]Crovella M E.PerformanceEvaluationwithHeavy Tailed Distributions［C］//Proceedingsofthe7th JSSPP’01.Cambridge,USA:［s.n.］,2221:1-10.

［9]Oida K,ShinjoK.CharacteristicsofDeterministic OptimalRoutingforTwoHeterogeneousParallel Servers［J］.InternationalJournalofFoundationsof Computer Science,2001,12(6):775-790.

［10]Shenker S,WeinribA.TheOptimalControlof Heterogeneous Queueing Systems:A Paradigm for Loadsharing andRouting［J］.IEEETransactionson Computers,1989,38(12):1724-1735.

［11]Matteo S,Ilaria V.Branch and Price for the Vehicle Routing Problem with Discrete Split Deliveries and Time Windows［J］.EuropeanJournalofOperational Research,2011,213(3):470-477.

［12]Christophe D,PhilippeL,CarolineP.Efficient Frameworks for Greedy Split and New Depth First Search Split Procedures for Routing Problems［J］.Computers&OperationsResearch,2011,38(4): 723-739.

［13]Nguyen N C,Thanh V D.Optimal Routing Algorithms for Hyper-de Bruijn Networks［C］//Proceedings of ATC’10.Washington D.C.,USA:IEEE Press,2010: 297-300.

［14]Banawan S A,Zahorjan J.Load Sharing in Heterogeneous Queueing Systems［C］//Proceedings of IEEE INFOCOM’89.Washington D.C.,USA:IEEE Press, 1989:731-739.

編輯 索書志

Optimal Routing Policy Based on Multivariable Decision Function

ZHAO Haijun1,LI Min2,LI Mingdong1,YUE Miao1

(1.School of Computer,China-West Normal University,Nanchong 637009,China;

2.Information Communications Branch,Chengdu Power Supply Company,Chengdu 610000,China)

Aiming at the disadvantage of existing routing algorithm in distributed parallel processing system,a novel and effective routing policy is proposed.The concrete implement is to obtain the packet fore-and-aft arriving time distributionPt(x)and the packet size distributionPp(x)from input packets,and a weight function is introduced to achieve the minimal average delay of all packets by learning continuously average fore-and-aft arriving time,average packet size and vector.Simulation result shows that the minimal average delay of all packets can be obtained not only in the condition of the varied number of processors,but also in the condition of the changed packet fore-and-aft arriving time and the packet size distribution.

distributed parallel processing system;multivariable;routing policy;average delay;minimum;flow intensity

趙海軍,李 敏,李明東,等.基于多變量判決函數(shù)的最優(yōu)化路由策略［J］.計算機(jī)工程,2015,41(3):92-96.

英文引用格式:Zhao Haijun,Li Min,Li Mingdong,et al.Optimal Routing Policy Based on Multivariable Decision Function［J］.Computer Engineering,2015,41(3):92-96.

1000-3428(2015)03-0092-05

:A

:TN915.6

10.3969/j.issn.1000-3428.2015.03.017

四川省教育廳自然科學(xué)基金資助項目(10ZC012);西華師范大學(xué)基本科研業(yè)務(wù)費(fèi)專項基金資助項目(14C002)。

趙海軍(1966-),男,教授,主研方向:無線通信,網(wǎng)絡(luò)數(shù)據(jù)通信;李 敏,工程師、碩士;李明東,教授;岳 淼,講師、碩士。

2014-03-13

:2014-05-21E-mail:zhaohai_jun@163.com