基于多約束條件的業務規劃方法

霍永華,曹　毅， 汲錫林

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

0　引言

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

1　業務規劃

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

1.1　多約束條件規劃

業務規劃首先獲取粗粒度的通信保障需求，然后進行需求分析，獲取網絡資源，進行應用需求到網絡資源的最佳擬合和映射，最后生成業務規劃方案。

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

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

表1多媒體類應用業務的QoS性能目標參數

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

表2數據類應用業務的QoS性能目標參數

應用業務帶寬時延時延抖動數據丟失率加急文電30kbps250ms無要求<0．01%FTP10k～10M400ms無要求<0．01%

③ 獲取網絡和業務資源：通過與資源管理系統交互，獲取網絡資源，包括服務器數量、接入位置、并發用戶數、在網業務類型、業務流量、已用資源、可用資源及TE鏈路等。

④ 業務建模：在進行需求分析和獲取網絡資源的基礎上，進行業務建模，即得出用戶身份、任務屬性、業務類型、業務屬性、QoS要求和網絡資源之間的關系，根據不同的業務類型建立不同的業務模型。

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

⑥ 生成業務規劃方案：在進行業務規劃的基礎上，基于XML生成業務規劃方案。

1.2　業務建模

綜合分析業務特點，進行業務建模是完成按需業務規劃的一個重要環節。

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

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

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

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

2　實例驗證

以實例說明業務建模過程。

業務規劃需求描述：某網絡規模包括：30條無向鏈路，25個節點，如圖1所示。現在有視頻業務和多媒體通信業務擬在網絡中運行。

圖1　實例拓撲

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

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

③ 獲取網絡資源：在25個節點中，分別設有4個源、目的節點集，假定每個節點集合內各個節點的流量需求都相同。源節點集用S1、S2、S3、S4；目的節點集用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個節點集合中任意2個節點之間均可以相互通信。

④ 進行業務建模：依據源、目的節點的位置，抽象拓撲如圖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；

單個業務流所需的帶寬為：

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

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

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

再根據業務流傳輸所需的帶寬為:

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

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

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

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

表3各源目的節點對應業務流量表

源目的節點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

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

3　結束語

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

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

[2]劉曉明,黃傳河.一種基于移動AGENT技術的網絡管理[J].計算機應用研究.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]朱淼良,邱瑜.移動代理系統綜述[J].計算機研究與發展,2010,35(2):201-206.

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

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

[10] 金黎黎,孔令富．協同設計環境中任務分解與調度的研究[J]．計算機工程與設計，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.