一种基于路径权值的流量映射方法

焦利彬 赵波

摘要：针对流量映射问题，在已有业务流量采集和业务流量预测的基础上，基于网络拓扑和剩余带宽计算最优路径集合，为不同类型的业务流搜索计算出最优路径，同时计算路径的负载确定路径权值，直到为所有类型的业务都找到满足QoS需求的可行的路径。流量映射根据计算出的可行路径，基于业务类型为不同的链路分配相应的带宽，实现按需流量映射。

关键词：流量采集；流量映射；最优路径；路径权值；业务流量

中图分类号：TP393文献标志码：A文章编号：1008-1739（2020）01-56-4

0引言

随着网络规模的日益扩大和应用需求的海量增长，网络所承载的业务流量越来越大。为了满足不同应用的QoS要求，通过采用过载或轻载流量方法予以保证，例如采用MPLS RSVP TE[1-2]技术，为特殊业务预留单独的、有带宽保证的LSP，此种流量映射方法虽然部分解决了不同业务的QoS要求，但是却造成了在资源短缺情形下的流量资源的极大浪费，因此做到按需流量映射和最大化利用带宽资源是非常必须的。

1流量映射

1.1业务流量采集

要进行准确的流量分配和流量映射，首先要监测和分析在网运行的流量。流量采集是流量监测和分析的前提和基础。流量采集来源不同，主要有以下4种：①基于SNMP协议针对路由器或交换机的端口进行流量采集；②基于流量监测工具进行的端到端IP流量测量；③针对特殊用户或特殊服务的流量监测；④用户业务服务质量监测评估等。

根据实际使用需求，结合网络流量采集的特点和处理方式，流量采集分为部分流量采集和完全流量采集、主动采集和被动采集、集中式采集和分布式采集、硬件采集和软件采集以及在线采集和离线采集等。

基于SNMP协议采集主要针对MIBⅡ中的iftable表中定义的变量参数，包括：①接口速率（ifSpeed）；②接口当前状态（ifOperStatus）；③接口接收的总字节数（ifInOctets）；④接口发送的总字节数（ifOutOctets）；⑤接口丢弃的输入包数（ifInDiscards）；⑥接口丢弃的输出包数（ifOutDiscards）。

由于基于NetFlow V9采集的流量信息巨大，因此采用基于HDOOP的大数据处理平台，将流量测试Spirent Testcenter仪表嵌入网络中，使用仪表按照设定周期发送UDP测试包进行流量测试。仪表定期从源主机向目的主机发送测试包，在目的主机上安装UDP ECHO软件，将Spirent Testcenter发送的UDP测试包返回至源主机的Spirent Testcenter仪表，进而完成流量测试。

1.2业务流量预测

获得总业务量以及流量流向的分布就可以计算出各个区域之间的流量矩阵，从而进行业务流量预测，为流量映射提供依据。

流量矩阵是一个逻辑上全连接的流量矩阵，实际的物理网络一般不是一个全网状的网络结构。这就存在一个逻辑上的流量矩阵向物理网络的映射过程。对于比较简单的网络拓扑结构（如星型结构），可以通过手工计算方式，实现映射过程；对于比较复杂的网络拓扑结构（如网状和不完全网状）则需要借助相应的流量仿真软件，并对路由协议进行配置后进行流量映射。

1.3流量映射最佳路径

流量映射根据流量预测估算出的带宽，为不同类型的业务流计算出最优路径，以及这些最优路径的负载，直到为所有类型的业务都找到满足QoS需求的可行路径。链路容量分配根据计算出的链路负载和业务类型为不同鏈路分配相应的带宽，得出一个或多个最优的网络拓扑。

流量映射[5]就是将业务流量映射到网络拓扑中，具体操作是依据业务的流量需求选择合适的路径，使得网络中的所有业务的总时延最小。流量映射的结果即网络的负载分配，依据此网络负载分配和费用函数，可以进一步对网络进行规划。

对于路径选择问题，使用OSPF路由最优化方法。首先将各链路的延迟增量设置为该链路的权值。所谓延迟增量，就是指各条链路的实际吞吐量与该链路容量的比值。对于每条链路来说，权值越小，被路由的概率就越大。所有链路的权值设定后，再采用Dijkstra最短路径[6-7]算法计算路由。

实时业务的流量映射采用的也是最短路径算法。算法不仅考虑了实时业务流量的带宽需求，还考虑了在计算最短路径的过程中链路的剩余容量[8-9]和已选路径的跳数。

实时业务的流量映射过程中，网络为单个实时业务流指定一条最佳路径，并预留相应的带宽。每指定一条路径并预留带宽后，都需要重新计算网络中各节点及链路的剩余容量，从最优路径集合中去掉已被分配的路径，再继续为下一条业务流选择最短路径，此过程一直循环进行，直到为每一条实时业务流都分配一条最短路径为止。

实时业务的流量映射结果就是为每条实时业务流搜索一条最佳路径，在路径的搜索[10]中，不同的搜索顺序会导致最后的最短路径集不同。为了保证路径集中每条路径的可用带宽尽可能大，以便能够接收大带宽网络请求，减小请求被拒数目，采取以下策略进行路径搜索：

2实例验证

业务流量映射需求描述，某网络规模包括30条无向链路和25个节点，如图1所示。现在需要为视频业务和多媒体通信业务进行流量映射。

（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个节点之间均可以相互通信。

（2）流量采集预测

利用Wincap抓包工具，基于网络拓扑结构进行流量采集预测，实时业务各源目的节点对之间的流量预测为：

Vl={v10，v11，v12，v13，v14}各节点实时业务流条数到达速率为72业务流/s。其中语音业务到达速率为60业务流/s，发往D1，D2，D3，D4各节点的比例分别为33.3%，28.3%，13.3%，25%；交互式媒体类业务到达速率为8业务流/s，发往D1，D2，D3，D4各节点的比例分别为37.5%，25%，12.5%，25%；流式媒体业务到达速率为4业务流/s，发往D1，D2，D3，D4各节点的比例分别为25%，25%，25%，25%。

V2={v15，v16，v17，v18，v19}各节点实时业务流条数到达速率为9l业务流/s。其中语音业务到达速率为70业务流/s，发往D1，D2，D3，D4各节点的比例分别为21.4%，35.7%，14.3%，28.6%；交互式媒体类业务到达速率为14业务流/s，发往D1，D2，D3，D4各节点的比例分别为21.4%，35.7%，14.3%，28.6%；流式媒体业务到达速率为7业务流/s，发往D1，D2，D3，D4各节点的比例分别为14.3%，57.1%，14.3%，14.3%。

V3={v20，v2l，v22，v23，v24}各节点实时业务流条数到达速率为65业务流/s。其中语音业务到达速率为55业务流/s，发往D1，D2，D3，D4各节点的比例分别为14.5%，27.3%，36.4%，21.8%；交互式媒体类业务到达速率为6业务流/s，发往D1，D2，D3，D4各节点的比例分别为16.7%，33.3%，33.3%，16.7%；流式媒体业务到达速率为4业务流/s，发往D1，D2，D3，D4各节点的比例分别为25%，25%，25%，25%。

V4={v9}，节点实时业务流条数到达速率为320业务流/s。其中语言业务到达速率为260业务流/s，发往D1，D2，D3各节点的比例分别为28.8%，48.1%，23.1%，21.8%；交互式媒体类业务到达速率为35业务流/s，发往D1，D2，D3各节点的比例分别为28.6%，57.1%，14.3%；流式媒体业务到达速率为25业务流/s，发往D1，D2，D3各节点的比例分别为20%，60%，20%。

（3）业务流量计算

根据流量建模计算的结果，单个实时业务流所需的带宽分别为：语音类业务流162 kBps、交互式媒体业务流2.43 Mbps和流式视频类业务5.31 Mbps，各源目的节点对之间的总业务流量如表1所示。

（4）经过弹性业务的映射后，各链路剩余的容量表如表2所示。

（5）经过流量映射，各条最短路径及其对应的权值如表3所示。

3结束语

随着网络规模的日益扩大和应用需求的海量增长，网络负荷越来越大，网络性能越来越差，而一些冗余链路却无法利用，浪费了有限的带宽资源，因此研究流量映射，寻找最优路径集合，实现按需流量调控，尽量做到最大化利用带宽资源，避免冗余链路的出现。

参考文献

[1]肖增良，乐晓波，周辉.基于与或依赖图的多Agent系统任务分解算法[J].计算机工程与设计，2009，30（2）：426-428.

[2]刘晓明，黄传河，江贝.一种基于移动Agent技术的网络管理模型[J].计算机应用研究，2000（12）：52-53.

[3] LENNSELIUS B，RYDSTROM L.Software Fault Content and Reliability Estimations for Telecommunications System[J]. IEEE Trans.on Selected Areas in Communications，1990，8（2）： 262-271.

[4] DOWNST，SCOTT A. EvaluatingthePerformanceofSoftware Reliability Models[J].IEEE Trans.on Reliability，1992，41（4）： 533-538.

[5] ZAHEDI F，ASHRAFI N.Software Reliability Allocation Based on Structure Utility，Price and Cost[J].IEEE Trans.on 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].计算机研究与发展， 2001（1）：16-25.

[8]刘波，李伟，罗军舟，等.网络管理中多Agent的半在线调度算法[J].计算机研究与发展，2006（4）：571-578.

[9]王媛媛，谭献海.移动代理系统———IBM的Aglets[J].微计算机信息，2006（9）：275-277.

[10]金黎黎，孔令富.协同设计环境中任务分解与调度的研究[J].计算机工程与设计，2009，30（22）：5291-5293.