最大流算法在小型園區網絡中的應用

李江龍 馬詩貴

（遵義醫科大學計算機網絡管理中心 貴州省遵義市 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 結束語

近年來，各種大型企業的信息化建設突飛猛進，網絡主干設備早已是萬兆互連，所以對于出口帶寬問題，已不用再考慮設備和線路的承載能力，更值得關注的是用戶的最終需求，但是在欠發達地區的中小學以及中小企業，信息化建設規格遠不及高校及大型企業，所以對最大流算法的應用是不可或缺的，再者對于復雜的大規模網絡，對于提高各類資源的利用率更是顯得尤為重要。所以研究最大流問題在現實問題中的應用會越來越多，具有重要的現實意義。