最大流算法在小型园区网络中的应用

李江龙 马诗贵

（遵义医科大学计算机网络管理中心 贵州省遵义市 563000）

1 引言

近年来，各大高校的信息化建设突飞猛进，主干设备早已是万兆互连，所以对于高校出口带宽问题，已不用再考虑设备和线路的承载能力，更值得关注的是用户的最终需求，但是在欠发达地区，高校信息化建设水平落后[2]，尤其是中小学的信息化规划与建设，远远跟不上主流地区信息化发展的速度，所以对相关最大流优化算法的应用是不可或缺的，再者对于复杂的大规模网络，提高各类资源的利用率更是显得尤为重要。若是能将最大流算法应用于相关场景，再精准施策，相信这类问题将会得到很大的改善，所以研究最大流问题具有重要的现实意义。

2 基本概念

2.1 （容量）网络[3]

在有向连通图D=(V,E)中，记（容量）网络为G=(V,E,c)，需满足：

（1）在D 中存在特定的两个顶点，分别为源点与汇点；对于D 中的中间节点必须是同时具有入弧和出弧的节点。

2.2 流量、容量和可行流[3]

流量是指链路上正在流过的数据量，通常用f(u,v)来表示，u,v是两个顶点的编号，流量可以是管道中的水量，也可以是道路中的车流量等；容量是指链路的最大承载量，通常用c(u,v)来表示；可行流是指满足条件的流量。

2.3 最大流[3]

同一时间在网络内能够承载的最大流量称为最大流。

2.4 增广路径[3]

增广路径是指连通源点和汇点的一条路径，这条路径上的所有正向边都满足反向边满足这样的路径叫做增广路径。

2.5 邻接矩阵[4]

邻接矩阵（Adjacency Matrix）是表示图的顶点之间相邻关系的矩阵，其实就是一个二维数组。

3 算法简介与应用

本文主要将最大流算法应用到园区网络的管理中，可通过算法计算出园区网络主干设备可承载的出口带宽上限，这个上限对于网络管理员和单位具有非常重要的价值，可以避免不必要的资金浪费。选用的最大流算法为关键顶点可行分量算法（KPFC）。

3.1 算法步骤

图1：园区网络主干部分拓扑图

图2：园区网络主干部分有向图

（1）在网络图中找出并记录关键顶点，去除关键顶点，构建可行分量。

（2）利用DFS 算法在可行分量中寻找增广路径直到可行分量不再连通。

（3）判断是否存在被去除的关键顶点，若存在，加入关键顶点，构建新的可行分量；返回步骤2，若不存在，则算法结束。

3.2 算法应用场景

我单位园区网络采用标准的三层架构[5]，接入层提供10M/100M 自适应多接口，汇聚层具备高速二层转发能力，同时提供三层路由功能与核心层对接，核心层提供高性能的包转发能力，各个层次之间均以千兆光纤互连，采用双核心，双链路保障网络的稳定性，出口租用运营商两条带宽为500Mbps 专线。

图3：可行分量1

图4：可行分量2

本文针对的是园区网络主干部分的承载能力，所以可将网络的主干部分单独分离出来进行讨论，接入层拥有足够数量的接入交换机，我们可以视为从接入层到汇聚层拥有足够大的链路带宽。图1为我单位园区网络的主干部分拓扑图。

我单位园区网主干拥有2 台核心交换机和5 台汇聚交换机，两者之间是千兆互连，每台汇聚都接入足够数量的接入交换机，汇聚层与接入层之间也是千兆互连，所以从接入层到汇聚层，我们视为拥有足够大的带宽，即拥有足够大的链路容量。

3.3 算法的实际应用

首先将拓扑图转化为有向网络图，对于园区网来讲，通常需要的是大量的入方向流量[6]，所以我们在图的转化时，需要着重考虑流量从ISP 到园区内部的流动方向，转化后的网络图如图2所示。

用各个顶点代替相应设备，其中流量是从源点1 流向汇点9，如图2所示，顶点2 和顶点3 分别与顶点4、5、6、7、8 都有连接，设容量单位为100Mbps，则弧24、25、26、27、28、34、35、36、37、38 的容量均为10，顶点4、5、6、7、8 到汇点9 的链路容量视为足够大，设为X，现在是要求出弧12、13 的容量之和的最大值是多少。我们先将两弧的容量和也视为足够大，设为Y，给X 和Y 附一个值10000，这样是为了求出在当前条件下的可租用带宽的上限，设最大流为SUM，关键顶点数组为kpoint 先利用KPFC算法计算其最大流，具体步骤为：

（1）寻找关键顶点，构建第一个可行分量。

此时找到的关键顶点为2，去除后形成如图3所示的可行分量。

（2）在可行分量中寻找增广路径，可找到的增广路径为：1-3-4-9，1-3-5-9,1-3-6-9，1-3-7-9，1-3-8-9，此时SUM=10+10+10+10+10=50。

（3）加入关键顶点2，构建新的可行分量。

加入关键顶点2 后，形成如图4所示的可行分量。

（4）在可行分量中寻找增广路径，可找到的增广路径为：1-2-4-9，1-2-5-9,1-2-6-9，1-2-7-9，1-2-8-9，此 时SUM=50+50=100。发现图不再连通，并且不存在关键顶点，说明最大流为100，即为10Gbps。

由此推出Y 在满足最大流的条件下的最大值为100，所以可以得出结论只需满足弧12 和弧13 的容量和上限为10Gbps，也就是说，我单位园区网现有的主干能够承受的最大出口带宽为10Gbps，若租用的链路带宽高于这个值，多出的部分便是浪费。

但是园区网络的带宽需求最终是由用户的需求量决定的，在实际应用中，解决了设备性能瓶颈之后，带宽需求与在线用户数量成正比，单位现阶段用户总数约12000 人，高峰期在线人数约为10000 人，利用上网行为管理技术可统计出高峰期时所需的最大下行流量，我单位约为5Gbps 左右，所以对单位现阶段来说，租用运营商带宽应该在5Gbps 到10Gbps 之间，等于5Gbps 时刚好能满足用户需求，等于10Gbps 时达到网络设备的最大承载能力。得到这样的结果之后，再结合单位的能力以及发展规划，能够更精准，更灵活的调整运用相关资金费用。

4 结束语

近年来，各种大型企业的信息化建设突飞猛进，网络主干设备早已是万兆互连，所以对于出口带宽问题，已不用再考虑设备和线路的承载能力，更值得关注的是用户的最终需求，但是在欠发达地区的中小学以及中小企业，信息化建设规格远不及高校及大型企业，所以对最大流算法的应用是不可或缺的，再者对于复杂的大规模网络，对于提高各类资源的利用率更是显得尤为重要。所以研究最大流问题在现实问题中的应用会越来越多，具有重要的现实意义。