基于多约束条件的业务规划方法

霍永华,曹　毅， 汲锡林

(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.