基于多約束條件的業(yè)務(wù)規(guī)劃方法

霍永華,曹　毅， 汲錫林

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.裝備發(fā)展部駐石家莊地區(qū)軍事代表室，河北 石家莊050081；3.中國電子設(shè)備系統(tǒng)工程公司研究所，北京 100141)

0　引言

在融合和開放[1-2]的網(wǎng)絡(luò)環(huán)境下，業(yè)務(wù)管理[3-4]需要配合業(yè)務(wù)的快速提供保證業(yè)務(wù)安全、可控及可靠的運行，保障各種業(yè)務(wù)的服務(wù)質(zhì)量，增強網(wǎng)絡(luò)對新業(yè)務(wù)的適應(yīng)能力以滿足各種業(yè)務(wù)用戶的需求。業(yè)務(wù)規(guī)劃是業(yè)務(wù)管理的前提和基礎(chǔ)。業(yè)務(wù)規(guī)劃是將具有多種約束條件的通信保障需求細化為對網(wǎng)絡(luò)資源的需求，從而在應(yīng)用和網(wǎng)絡(luò)能力之間建立一種最佳映射關(guān)系，以便最大化利用網(wǎng)絡(luò)，提高網(wǎng)絡(luò)資源利用率。

1　業(yè)務(wù)規(guī)劃

從通信指揮獲取通信保障需求，進行需求分析，從用戶重要性、任務(wù)重要性和所需資源進行分析，然后進行業(yè)務(wù)預(yù)測[5-6]，基于拓撲驅(qū)動和路由驅(qū)動[7-8]進行網(wǎng)絡(luò)資源遍歷和獲取，自此基礎(chǔ)上完成業(yè)務(wù)建模，進行需求和資源之間的映射，實現(xiàn)按需資源調(diào)配。從業(yè)務(wù)規(guī)劃過程來看，業(yè)務(wù)規(guī)劃是一個跨層[9-10]的從需求到資源的映射過程，從應(yīng)用層到業(yè)務(wù)層到網(wǎng)絡(luò)層。在應(yīng)用層獲取規(guī)劃需求，在業(yè)務(wù)層根據(jù)規(guī)劃的業(yè)務(wù)類型進行時延、抖動和丟包率等QOS參數(shù)分解和映射，最后在網(wǎng)絡(luò)層建立鏈路進行最終的流量分配和調(diào)控，從而完成從應(yīng)用需求到最終鏈路資源按需調(diào)配的業(yè)務(wù)規(guī)劃。

1.1　多約束條件規(guī)劃

業(yè)務(wù)規(guī)劃首先獲取粗粒度的通信保障需求，然后進行需求分析，獲取網(wǎng)絡(luò)資源，進行應(yīng)用需求到網(wǎng)絡(luò)資源的最佳擬合和映射，最后生成業(yè)務(wù)規(guī)劃方案。

① 從通信指揮局獲取通信保障需求，即業(yè)務(wù)規(guī)劃需要完成和達到的目標。通信保障需求是粗粒度的需求描述，(3w)如誰who，在什么地方where，使用什么樣的業(yè)務(wù)what，例如首長A和B，在北京和南京之間進行視頻通信。

② 把粗粒度的通信保障需求分解成相對應(yīng)的用戶屬性、任務(wù)屬性、所需業(yè)務(wù)資源和QoS要求等。如用戶身份(0首長、1重要、2一般)，任務(wù)屬性(1生存性、2及時性、3盡力而為型)，所需業(yè)務(wù)資源(業(yè)務(wù)接入位置、源IP、目的IP、帶寬、優(yōu)先級)，QoS要求(0最高、1高、2中、3一般、4低)。在生成QoS優(yōu)先級時需要參照不同類型應(yīng)用業(yè)務(wù)的QoS參數(shù)要求，如對帶寬、時延、時延抖動以及丟包率的要求，表 1和表 2是流媒體類和數(shù)據(jù)類業(yè)務(wù)等應(yīng)用業(yè)務(wù)的基本QoS參數(shù)要求對照表。

表1多媒體類應(yīng)用業(yè)務(wù)的QoS性能目標參數(shù)

類別應(yīng)用業(yè)務(wù)帶寬時延時延抖動數(shù)據(jù)丟失率音頻語音64～320kbps<150ms<20ms<3%視頻交互視頻512k～1M<150ms<30ms<1%視頻流1M～2M<400ms<30ms<1%

表2數(shù)據(jù)類應(yīng)用業(yè)務(wù)的QoS性能目標參數(shù)

應(yīng)用業(yè)務(wù)帶寬時延時延抖動數(shù)據(jù)丟失率加急文電30kbps250ms無要求<0．01%FTP10k～10M400ms無要求<0．01%

③ 獲取網(wǎng)絡(luò)和業(yè)務(wù)資源：通過與資源管理系統(tǒng)交互，獲取網(wǎng)絡(luò)資源，包括服務(wù)器數(shù)量、接入位置、并發(fā)用戶數(shù)、在網(wǎng)業(yè)務(wù)類型、業(yè)務(wù)流量、已用資源、可用資源及TE鏈路等。

④ 業(yè)務(wù)建模：在進行需求分析和獲取網(wǎng)絡(luò)資源的基礎(chǔ)上，進行業(yè)務(wù)建模，即得出用戶身份、任務(wù)屬性、業(yè)務(wù)類型、業(yè)務(wù)屬性、QoS要求和網(wǎng)絡(luò)資源之間的關(guān)系，根據(jù)不同的業(yè)務(wù)類型建立不同的業(yè)務(wù)模型。

⑤ 進行業(yè)務(wù)規(guī)劃：研究業(yè)務(wù)規(guī)劃算法，如啟發(fā)式算法和基于QoS的多約束最優(yōu)算法，基于策略在滿足業(yè)務(wù)的QoS要求進行業(yè)務(wù)接入、服務(wù)器接入規(guī)劃、并發(fā)操作規(guī)劃、基于負載均衡的最優(yōu)路徑規(guī)劃、MPLS TE鏈路規(guī)劃。

⑥ 生成業(yè)務(wù)規(guī)劃方案：在進行業(yè)務(wù)規(guī)劃的基礎(chǔ)上，基于XML生成業(yè)務(wù)規(guī)劃方案。

1.2　業(yè)務(wù)建模

綜合分析業(yè)務(wù)特點，進行業(yè)務(wù)建模是完成按需業(yè)務(wù)規(guī)劃的一個重要環(huán)節(jié)。

一種求解業(yè)務(wù)建模問題的啟發(fā)式算法，首先將待規(guī)劃的多種業(yè)務(wù)按照優(yōu)先級或者重要性排序，然后依次規(guī)劃。規(guī)劃時，根據(jù)獲取的網(wǎng)絡(luò)資源建立一個約束圖[11-12]，然后將不滿足條件的節(jié)點如服務(wù)器、路由器、鏈路刪除，在更新后的拓撲上運行最短路徑算法[13](如Dijkstra算法)確定最優(yōu)規(guī)劃路徑，然后更新網(wǎng)絡(luò)資源，重復(fù)以上過程完成所有業(yè)務(wù)的規(guī)劃。

① 業(yè)務(wù)拓撲抽象：首先將業(yè)務(wù)拓撲表示為有向圖G=(V，E，W)，其中V為具有路由能力的交換節(jié)點的集合，可以是邊路由器或核心路由器，節(jié)點具有節(jié)點延時、節(jié)點丟包率等屬性；E為圖G的邊集，邊表示連接V中2個節(jié)點的鏈路，鏈路具有鏈路延時、鏈路帶寬、隊列長度等屬性；W為每條邊的權(quán)值。在本模型中，只考慮網(wǎng)絡(luò)節(jié)點的丟包率和延時，而忽略鏈路的丟包率和鏈路延時，這與現(xiàn)實情況相符，且算法實現(xiàn)上也是可行的。

進入網(wǎng)絡(luò)的流量需求由進入各網(wǎng)絡(luò)節(jié)點的各類業(yè)務(wù)(彈性業(yè)務(wù)流、VolP、視頻流等)建模，這些類別的業(yè)務(wù)的到達時問間隔、服務(wù)時間和路由策略各不相同。

② 需求描述：每條實時業(yè)務(wù)流i的流量需求由集合fr=(s，t， TSPEC，service)表示。s、t分別表示源、目的節(jié)點，且有s∈V，t∈V； TSPEC也是用3個參數(shù)[14](峰值速率、最小策略數(shù)據(jù)長度和最大策略數(shù)據(jù)長度)來描述流量需求，它和TB都是用來計算該業(yè)務(wù)流所需的帶寬；service用來定義業(yè)務(wù)的類型。不同的業(yè)務(wù)對于帶寬的要求是不同的，因此基于策略設(shè)定，根據(jù)任務(wù)屬性、用戶身份、業(yè)務(wù)類型和所需資源，生成QoS規(guī)劃策略。

2　實例驗證

以實例說明業(yè)務(wù)建模過程。

業(yè)務(wù)規(guī)劃需求描述：某網(wǎng)絡(luò)規(guī)模包括：30條無向鏈路，25個節(jié)點，如圖1所示?，F(xiàn)在有視頻業(yè)務(wù)和多媒體通信業(yè)務(wù)擬在網(wǎng)絡(luò)中運行。

圖1　實例拓撲

① 獲取通信保障需求：首長欲在北京和南京之間進行視頻通話；

② 通信保障需求分解：用戶身份(0首長)，任務(wù)屬性(2及時性)，所需業(yè)務(wù)資源(源IP192.168.10.4、目的IP101.1.5.102、帶寬50 M、優(yōu)先級1)，QoS要求(1高)。

③ 獲取網(wǎng)絡(luò)資源：在25個節(jié)點中，分別設(shè)有4個源、目的節(jié)點集，假定每個節(jié)點集合內(nèi)各個節(jié)點的流量需求都相同。源節(jié)點集用S1、S2、S3、S4；目的節(jié)點集用D1、D2、D3、D4表示。其中Sl=Dl={n10，nll，n12，n13，n14}， S2=D2={n15，n16，n17，n18，n19}，S3=D3={n20，n21，n22，n23，n24}，S4=D4={n9}。這4個節(jié)點集合中任意2個節(jié)點之間均可以相互通信。

④ 進行業(yè)務(wù)建模：依據(jù)源、目的節(jié)點的位置，抽象拓撲如圖1所示，把鏈路分為E1、E2、E3三個部分：E1={ 0-10、0-11、0-12、0-13、0-14、3-15、3-16、3-17、3-18、3-19、6-20、6-21、6-22、6-23、6-24}，其中3-15、3-16、3-17、3-18、3-19的容量為300 Mbps，其余鏈路容量分別為155 Mbps；E2={0-l、1-2、3-4、4-5、6-7、7-8、0-3、0-4、l-4、2-5、3-6、4-6、4-7、5-8}，其中3-4、4-5、2-5、5-8的容量為1.2 Gbps，0-4、4-6的容量為155 Mbps，其余鏈路容量均為622 Mbps；E3={5-9}上的容量為2.5 Gbps。

MSS=50%*40+15%*550+15%*580+
20%*1500≈490 Byte；

單個業(yè)務(wù)流所需的帶寬為：

為計算簡便，假設(shè)當前所有彈性業(yè)務(wù)都服從M/G/1-PS模型，對4個源節(jié)點集的業(yè)務(wù)流量所需的帶寬進行分析計算：

對于源節(jié)點集S1中的節(jié)點n10～n14，假定各節(jié)點中數(shù)據(jù)包到達率均為31 238數(shù)據(jù)包/s，那么根據(jù)鏈路利用率公式求得，鏈路利用率為:

ρ=λe*le/C=31 238*490/155≈79%；

再根據(jù)業(yè)務(wù)流傳輸所需的帶寬為:

bavg=rpeak/(1+E2(K,Kρ)/K(1-ρ))≈26.9 Mbps。

同理，源節(jié)點集合S2中的節(jié)點n15～n19， 假定各節(jié)點中數(shù)據(jù)包到達率均為68 156數(shù)據(jù)包/s，其鏈路利用率為89.06%。需要為S2中各節(jié)點預(yù)留的帶寬為29.59 Mbps。源節(jié)點集S3中的節(jié)點n20～n24，假定各節(jié)點中數(shù)據(jù)包到達率均為33 166數(shù)據(jù)包/s，其鏈路利用率為83．88%。S3中各節(jié)點需要預(yù)留的帶寬為21.52 Mbps。對源節(jié)點集S4中的節(jié)點n9，假定節(jié)點中數(shù)據(jù)包到達率均為591 774數(shù)據(jù)包/s，其鏈路利用率為92.79%。S4中各節(jié)點需要預(yù)留的帶寬為168.125 Mbps。

將源目的節(jié)點分成各4類，分別為(V1，V2，V3，V4)、(V1，V2，V3，V4)。各節(jié)點的業(yè)務(wù)流量預(yù)測分別假定為：V1各節(jié)點的業(yè)務(wù)量為100業(yè)務(wù)流/s，其中20%發(fā)往節(jié)點集V1，25%發(fā)往節(jié)點集V2，15%發(fā)往節(jié)點集V3，40%發(fā)往節(jié)點集V4；V2各節(jié)點的業(yè)務(wù)量為110業(yè)務(wù)流/s，其中18.2%發(fā)往節(jié)點集V1，27.3%發(fā)往節(jié)點集V2，13.6%發(fā)往節(jié)點集V3，40.9%發(fā)往節(jié)點集V4；V3各節(jié)點的業(yè)務(wù)量為80業(yè)務(wù)流/s，其中18.75%發(fā)往節(jié)點集V1，25%發(fā)往節(jié)點集V2，25%發(fā)往節(jié)點集V3，31.25%發(fā)往節(jié)點集V4；V4各節(jié)點的業(yè)務(wù)量為125業(yè)務(wù)流/s，其中32%發(fā)往節(jié)點集V1，40%發(fā)往節(jié)點集V2，28%發(fā)往節(jié)點集V3。假定V1、V2、V3各節(jié)點集中5個節(jié)點的業(yè)務(wù)流均等。

根據(jù)上述流量建模計算的結(jié)果，單個彈性業(yè)務(wù)流所需的帶寬為270 kbps，各源目的節(jié)點對之間總的業(yè)務(wù)流如表3所示。

表3各源目的節(jié)點對應(yīng)業(yè)務(wù)流量表

源目的節(jié)點D1D2D3D4總計/MbpsS126．933．62520．17553．8134．5S226．940．3520．17560．525147．95S320．17526．926．933．625107．6S453．867．2547．0750168．125總Mbps127．775168．125114．325147．95558．175

⑤ 最后生成規(guī)劃方案，S2→D4的鏈路滿足通信保障要求。

3　結(jié)束語

通過研究基于任務(wù)屬性、業(yè)務(wù)屬性和用戶身份的多約束條件下的業(yè)務(wù)規(guī)劃，重點研究如何將通信保障需求細化映射為資源的需求，最終生成業(yè)務(wù)的QoS規(guī)劃策略，之后進行業(yè)務(wù)建模，業(yè)務(wù)建模是進行業(yè)務(wù)規(guī)劃的重要環(huán)節(jié)，業(yè)務(wù)建模是通信保障需求具體轉(zhuǎn)化為資源需求，且在網(wǎng)絡(luò)抽象拓撲之上建立資源映射關(guān)系，最終滿足不同業(yè)務(wù)的QoS要求。后續(xù)還需要進一步研究針對不同業(yè)務(wù)流的規(guī)劃策略，以便細粒度支撐通信保障任務(wù)。

[1]肖增良,樂曉波.基于與或依賴圖的多Agent系統(tǒng)任務(wù)分解算法 [J].計算機工程與設(shè)計，2009，40(2):267-272.

[2]劉曉明,黃傳河.一種基于移動AGENT技術(shù)的網(wǎng)絡(luò)管理[J].計算機應(yīng)用研究.2004.12(1)：65-69.

[3]Lennselius B,Rydstrom L.Software Fault Content and Reliability Estimations for Telecommunications System[J].IEEE Trans.Selected Areas in Communications,1990,8(2)：262-271.

[4]Thomas D,Anthony S.Evaluating the Performance id Software Reliability Models[J].IEEE Trans.Reliability,1992,41(4):12-16.

[5]Zahedi F,Ashrafi N.Software Reliability Allocation Based on Structure Utility,Price and Cost[J].IEEE Trans.Software Eng,1991,17(21):345-356.

[6]Beaumont O， Casanova H，Legrand A．Scheduling Divisible Loads on Star and Tree Networks：Results and Open Problems[J]．IEEE Trans on Parallel and Distributed Systems,2005,l6(3):207-218.

[7]朱淼良,邱瑜.移動代理系統(tǒng)綜述[J].計算機研究與發(fā)展,2010,35(2):201-206.

[8]劉波,羅軍舟.網(wǎng)絡(luò)管理中多agent的半在線調(diào)度算法[J].計算機研究與發(fā)展,2006,40(2):51-54.

[9]王媛媛，譚獻海.移動代理系統(tǒng)-IBM的Aglets[J].微計算機信息,2006,22(3x):275-277.

[10] 金黎黎,孔令富．協(xié)同設(shè)計環(huán)境中任務(wù)分解與調(diào)度的研究[J]．計算機工程與設(shè)計，2009，43(3)：31-35.

[11] Waish T,Paciorek N,Wong D.Security and Reiiabiiity in Concordia[C]∥31st Annual Hawaii International Conference on System Sciences，Kona，Hawaii，1998，32(3)：22-26.

[12] Rahman M R ,Boutaba R.SVNE: Survivable Virtual Network Embedding Algorithms for Network Virtualization[J].IEEE Transactions on Network and Service Management,2011,10(2):105-118.

[13] Guo T,Wang N,Moessner K,et al.Shared Backup Network Provision for Virtual Network Embedding[C]∥in Proc.IEEE International Conference on Communications (ICC),2011: 1-5.

[14] Yu H,Anand V,Qiao C,et al.Cost Efficient Design of Survivable Virtual Infrastructure to Recover from Facility Node Failures[C]∥in Proc.IEEE International Conference on Communications (ICC),2011:1-6.