基于多變量判決函數的最優路由策略

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

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

基于多變量判決函數的最優路由策略

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

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

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

分布式并行處理系統;多變量;路由策略;平均延遲;最小化;流量強度

1 概述

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

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

針對當前各種服務網絡結構存在的問題,文

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

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

2 模擬最佳路由算法

把上述問題的數學模型表示為下列組合最佳問題P1:

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

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

本文提出的MOR采用1個權值函數和3個參數,即平均前后到達時間(1/λ),平均包大小(1/μ)和向量α=(α1,α2,…,αp-1);目標就是通過從輸入流量獲得1/λ,1/μ和α的不斷學習來提高MOR的適應性,并得到滿足以下2個條件的權值函數:

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

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

3 并行處理器模型

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

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

為了得到到達包的平均延遲表達式,令Ck為處理器k的傳輸速率,xn和tn分別為系統S中第n個到達包的大小和到達時間。服務器k在時刻t的騰空時間(Wk(t))等于在時刻t通過處理器k傳輸的包的剩余傳輸時間與在時刻t隊列k中所有包等待傳輸的總的時間之和。因此,如果第n個到達包被分配給處理器un,則對所有k∈Sp={1,2,…,p},有:

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

輸入流量T可以用集合{tn}和{xn}來表示,它們的值按照某個概率分布來確定。設前后到達時間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的指數分布,Pu(x;m)是區間(0,2m)上的均勻分布;Pt(x;m)是模式為m,左端點為0,右端點為2m的三角分布。另一方面,系統S可表示為C={C1,C2,…,Cp}。設所有處理器是同類的(C1=C2=…=Cp),因此,對所有k∈Sp,Ck=C/p,C(C=∑pk=1Ck)為總的傳輸速率。所以系統S可以由p和C來決定。

4 MOR算法

4.1 MOR的解析表達式

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

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

當最佳權值wn用一個最優算法求解時,φn有助于快速收斂到最優的解。

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

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

4.2 α的確定

α的計算基于假設:如果所有前后到達時間{tn+1–tn}接近于0,則MOR就收斂。基于這個假設,α就是最優化問題P2的解:

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

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

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

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

為了實時計算α值,用(x+s)代替式(11)中的被積函數(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/μ是一個很好的替換。當時,令為式(12)的解,且令,就可得到α(1),α(2),…,初始值為α(1)=(1/μ,…,1/μ)。

4.3 權值函數的確定

假設以下3個條件用于權值函數的計算:

(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)可知,當改變1/λ,1/μ和C其中之一時,流量強度I(=λ/μC)都要變化(這里1/λ和1/μ分別為Pt(x)和Pp(x)的均值),

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

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

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

5 MOR算法的性能仿真

5.1 仿真環境及模型

為了對算法的性能進行測試,本文在Linux環境中,采用Opnet Modeler 10.0A網絡仿真平臺,并結合C++編程語言來對算法進行仿真。

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

5.2 仿真結果及分析

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

圖2 MOR算法與現有路由算法的性能比較

從圖2可見,MOR是最優的,JSD是次優的。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的平均包延遲都要小得多,且隨著流量強度的增加,平均包延遲減

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

6 結束語

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

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

［2]吳華鑫.分布式服務網絡中保證QoS的服務路由算法研究［D］.合肥:中國科學技術大學,2009.

［3]左朝樹,劉心松,邱元杰,等.分布式并行服務器的動態重構容錯算法［J］.系統工程與電子技術,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

趙海軍,李 敏,李明東,等.基于多變量判決函數的最優化路由策略［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

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

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

2014-03-13

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