面向云計算框架的最大流算法實現研究

鄧華富

(四川省 綿陽財經學校，四川 綿陽 621000)

0 引 言

目前，計算機已經成為研究各類問題的有效工具之一.例如，在交通路徑規劃領域，具備最大可增流量的出行路徑是實現交通科學誘導、緩解擁堵的基礎;而在通信等領域，最大可增流路徑是實現有效路由尋址、避免數據擁塞的前提［1－2］.該類問題具有通用的數學模型，即從網絡中搜索任意2 個結點之間的具有最大可增加流量的路徑.圖論中將這樣的問題放在抽象的賦權圖中研究.賦權圖分為有向圖和無向圖，由結點、邊(有向圖中稱弧)和每條邊對應的權值組成.權值一般代表邊上能通過某種物理量的最大值，如運輸費用、尋址代價等等，它與邊的自身性質有關.在此基礎上，可以計算任意2 個結點之間在權值約束下可增加流量最大的路徑，該路徑稱為最大可增路徑.將交通流或通信數據流按照最大可增路分配，能夠平衡網絡負載，減少因某局部區域擁堵而造成的網絡其他資源閑置，進而提高網絡利用率［3］.然而，隨著科學技術的飛速發展，需要考察的路網規模越來越大，單機計算時間也超過了可以接受的限度，這已經影響到多種實際問題的實時計算與決策.而近年興起的云計算思路與模型，為上述問題提供了一個可行的解決方案.基于此，本研究從最大流理論出發，提出了一種面向云計算框架的最大可增路分布式計算方式，并在開源云平臺——Hadoop 上加以實現.

1 最大流理論及可增路計算方法

一般而言，抽象路網由有向圖N(V，L，C)表示.其中，結點集為V，邊集為L，分別代表路口和路段.以c(a)表示a 邊允許通過的最大流量，C 表示所有路段最大流量集合.稱起始結點為源結點，終止結點為匯結點.根據圖論中的最大流理論以及上述定義，問題可歸結為:在網絡的某源—匯結點對間尋求最大可增路.理論上，可增路是指滿足以下條件的路徑P:對任意邊，若是P 的正向邊，則有△f(a)= c(a)－f(a)＞0;若a 是P 的反向邊，則有△f(a)= f(a)＞0.其中，f(a)是路段a 的當前流量值，△f(a)稱為路段a 的可增流.對與某一對源— 匯結點，若存在某條可增路，則可以沿該可增路將網絡總流量增加△f(a).這也是可增路和可增流名稱的來源.進一步，定義△f(P)= mina∈P△f(a)為路徑P 的可增流.在所有可增路中，具有最大可增流的路徑就是需要搜索的最大可增路.圖1 給出了一個簡單的示例.網絡中每條有向邊上括號里面的值表示該邊的最大流量，而括號之前的值代表當前流量(即當前交通流量).圖1(A)中虛線所示路徑即為一條可增路.該路徑上每條邊的可增流△f 均已標明，顯然路徑可增流△f(P)= mina∈P△f(a)= min{6，6，3}=3.圖1(B)中虛線所示路徑為含有反向邊(v2-v3)的可增路，不屬于本研究考慮的范圍，予以排除.

對于理論上的最大流問題，已有一系列經典的

圖1 網絡可增路示意圖

搜索算法可以很好地加以解決，例如Ford-Fulkerson算法［3］.然而，對于僅考察正向邊的情況，需要在原有基礎上稍加改動.其中，S1 為在原網絡基礎上構造的殘差網絡;S2 至S7 為迭代搜索可增路的過程，S3 僅對正向邊做處理，從而保證了可增路中只包含正向邊.S8 的輸出可能有2 種情況:一種是具有最大可增流的路徑，即為最優交通分配路徑;另一種是空集，這意味著當前網絡已經達到最大流狀態，沿任何路徑均不能增加總的網絡流.從交通控制的角度看，這種情況表明當前路網已經達到最大承載能力，無論采用何種控制方式都不能改善交通狀況，只能通過進一步加大基礎設施建設來達到目的.圖2 給出了以圖1 所示網絡作為輸入的計算過程.可以看到，“路徑4”具有最大的可增流，因此算法將輸出路徑4 作為最大可增流路徑.必須指出的是，最優分配路徑并不唯一.當多條可增路均具有最大可增流時，算法將隨機輸出一條作為結果.此時從流量分配的角度看，這些最大可增路是等效的.在實際應用過程中，可以將考察全時段劃分成多個子區間，每個子區間上按照最大可增路的搜索算法搜索最大可增路并進行流量分配，從而達到動態更新的目的.

圖2 示例計算結果

最大可增路的搜索算法的具體步驟如下:

輸入:當前路網N(V，L，C)中各路段的流量值.

輸出:所有源—匯結點對間的最大可增路及其可增流量值.

對任意出行源—匯結點對(Sou，Con)，可按以下步驟搜索:

S0:令PathSet=φ;(PathSet 為可增路集合)

S1:對所有路段a，令，△f(a)=c(a)－f(a)，得到一個新網絡，稱為殘差網絡;

S2:令Stack=Sou，將Sou 標號為“已查點”，其余標號“未查點”;(Stack 用來記錄一條可增路)

S3:對Stack 中的棧頂結點u，若存在鄰結點v滿足:①(u，v)∈L;②vStack;③v 通過u 被檢查;則轉S4，否則，轉S5;

S4:將v 壓棧，轉S6;

S5:將所有通過u 查詢過的結點標號為“未查點”，并將u 出棧，轉S6;

S6:若匯結點Con 位于棧頂，則將Con 標號為“未查點”，將Stack 中的路徑結點復制存儲于Path-Set 中，并將Con 出棧;

S7:若Stack 非空，則轉S2，否則轉S8;

S8:若PathSet=φ，則當前的網絡流已達到最大流，算法停止;否則，按照公式，△f(P)=mina∈P△f(a)，計算PathSet 中所有路徑的可增流，并輸出具有最大可增流的路徑和可增流量值，算法停止.

2 算法在Hadoop上的MapReduce實現

在實際應用中，面對大規模路網搜索過程會非常緩慢，使得分配過程不能在有效時間內完成，計算結果變得毫無意義.因此，必須采取加速手段來提高其實時性.

Hadoop 是一個開源的云計算平臺，由The Apache Software Foundation 公司維護，其實現語言是Java.Hadoop 的核心由分布式文件系統(Hadoop Distribution File System，HDFS)和MapReduce 編程模型構成，是針對分布式計算所設計的一種編程方式［4－6］.在該模型框架下，用戶需要指定以下信息:分布式文件系統作業輸入路徑;分布式文件系統作業輸出路徑;輸入數據格式;輸出數據格式;包含Map 方法的類;包含Reduce 方法的類(可選);Map類、Reduce 類以及其他必需類的Jar 文件路徑.

MapReduce 的作業過程如圖3 所示.輸入數據以鍵值對的形式存在，稱為記錄.Map 操作對每一條記錄生成一條或多條輸出記錄.這些記錄在分割階段按照鍵排序并溢出到硬盤，以此作為Reduce 階段的輸入.在Reduce 階段，具有相同鍵值的記錄被打包作為一個Reduce 的輸入，從而進行Reduce 操作.顯然，采用Hadoop 進行計算時，最主要的問題是如何設計Map 和Reduce 函數.

圖3 MapReduce 過程

在圖4 所示的實驗路網，共14 個路口，38 條路段.抽象路網中每條邊上的值仍然代表某一檢測時間段內的交通流量值以及路段最大流量值.

圖4 實驗路網示意圖

圖5 是其第一輪MapReduce 過程示意圖.左側的Map 階段，以所有邊的信息作為輸入.其中鍵值對的鍵部分預設為默認，而值部分由邊的起點終點和流量組成.Map 操作將對每一條記錄進行展開，生成2 條記錄.結果記錄中鍵部分即為原輸入邊的起點和終點，而值部分的流量變為可增流量.可以看出，Map 操作實際上是生成了所有單條邊的可增流.在Reduce 階段，所有具有相同鍵的記錄被集中到一起，按照收尾結點相同的組合原則生成長度為2(即包含2 條邊)的可增路.可增路的可增流量為組合的2 條記錄中可增流的較小值.

圖6 所示為其第二輪MapReduce 迭代過程.在本輪操作中，將原始邊的信息和第一輪MapReduce的輸出結果一起作為輸入.同樣地，Map 對于每條輸入記錄，分別以其首尾結點做鍵產生2 條記錄.具有相同鍵的記錄被匯集到一起，根據首尾結點組合成長度為3 或者更長的可增路.可增流仍然采用組合記錄中的最小值.按照上述過程，可以繼續第4 輪、第5 輪迭代.隨著迭代次數的增加，得到的可增路的長度也逐步增加.需要指出的是，在每一輪Reduce中，需要排除結果中的“回路”，如此可以大幅降低計算開銷.當某兩輪的迭代結果完全相同時，計算停止.此時，需要將歷次迭代的輸出結果匯總并排序.MapReduce 提供了二次排序的功能，即利用分割階段具有相同鍵的記錄被匯集到同一個Reduce 中的特點進行排序.在二次排序中，需要對輸入結構做微小修改，即以歷次迭代輸出記錄的鍵和可增流的組合作為新的鍵，稱為“復合鍵”(見圖7)，則Hadoop 分割器會首先按照復合鍵的邊部分排序，將相同起始結點和終止結點的記錄集中為一個組，然后再按照復合鍵的可增流部分從大到小排序.該步操作完成之后，只需要選取每個組的第一條記錄即為對應出行起點和終點之間的最大可增路.

圖5 第一輪MapReduce 過程

圖6 第二輪MapReduce 過程

圖7 二次排序

3 Hadoop 下的計算性能分析

為考察上述模型在Hadoop 平臺上的計算性能，本研究進行了一系列計算實驗.其中，Hadoop 平臺包含10 個計算結點，每個結點硬件配置均為Intel Core2 Quad 8400 CPU(主頻2.66 GHz)，4 GB Memory.實驗網絡仍然采用圖4 所示的路網.實驗共進行了10 輪迭代以及1 輪二次排序.

表1 給出了計算中單個任務的耗時情況.可以看出，Map 操作的時長基本穩定在6 s 左右，這是因為Map 函數并不需要對輸入做復雜操作，而只需要按照首尾結點產生2 條幾乎完全一樣的記錄作為Reduce 的輸入.

隨著迭代次數的增加，可增路的長度也逐漸增加，體現為Reduce 的耗時越來越長.顯然，這是由于生成可增路的主要操作都在Reduce 函數中進行，如組合路徑、檢查并排除回路等復雜步驟.在最后兩輪迭代中，Reduce 耗時有所下降，其原因是大部分可增路已經生成，計算量有所減少.另外，二次排序由于只涉及到分割操作，而對Map 和Reduce 函數無復雜計算要求，故耗時較短.

表1 MapReduce 單個任務耗時統計

表2 MapReduce 任務分配統計

表2 給出了每一輪迭代中，計算任務分配到10個結點的情況.表2 中數據為Map/Reduce 階段的任務個數.可以看出，除首輪迭代外，Map 函數的任務一般有15 個，而Reduce 任務一共有14 個.從數據上看，計算任務分布較均衡，這表明Hadoop 的運行狀況較理想.

4 結 論

本研究從最大流理論出發，回顧了最大可增路的搜索算法.同時，針對大規模網絡計算緩慢的情況，為提高計算速度，本研究給出了在開源云計算平臺——Hadoop 上的MapReduce 實現方式.基于簡單路網的計算實驗表明，本研究算法的分布式實現方式能夠在較短時間內得到最大可增路，可為實時快速決策奠定基礎.

［1］Van Aerde M，Yagar S.Dynamic integrated freeway/traffic signal networks:a routing based modeling approach［J］.Transp Res Part A:General，1988，22(6):445－453.

［2］Jayakrishnan R，Chen A，Tsai W K.Freeway and arterial traffic flow simulation analytically embedded in dynamic assignment［J］.Transp Res Rec，1999，1678(1):242－250.

［3］Ford L R，Fulkerson D R.Maximal flow through a network［J］.Can J Math，1956，8(3):399－404.

［4］White Tom.Hadoop:The definitive guide［M］.Sebastopol，CA，USA:O＇Reilly Media，Inc.，2009.

［5］Venner J.Pro hadoop:Build scalable，distributed applications in the cloud［M］.New York:Apress，2009.

［6］Dean J，Ghemawat S.MapReduce:simplified data processing on large clusters［J］.Comm ACM，2004，51(1):107－113.