一體化承載網絡的互斥問題研究

摘 要:一體化承載網是一種全新的網絡體系架構，其以網絡承載服務為核心，結合可重構路由平臺技術，根據用戶的業務需求，在現有的物理網絡上構建邏輯承載網。但構建邏輯網時，會產生分布式公用資源訪問的互斥問題。針對一體化承載網絡的體系結構，設計了一種基于令牌的互斥算法。該算法借鑒解決旅行商問題的算法思想，構造一個邏輯環，使得令牌遍歷所有節點的代價最小，并提出了一種新的基于請求的令牌傳遞策略，能有效降低系統中的通信量。最后對算法進行了模擬仿真。

關鍵詞:一體化承載網;互斥;最優邏輯環;令牌

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1148-03

doi:10.3969/j.issn.1001-3695.2010.03.095

Research of mutual exclusion problem of universal carrying network

ZHANG Wei1，WU Chun-ming1，JIANG Ming2，ZHANG Dong1(1.College of Computer Science， Zhejiang University， Hangzhou 310027， China;2.College of Computer Science， Hangzhou Dianzi University，Hangzhou 310018， China)

Abstract:UCN is a new network architecture.Logical carrying network is the core of UCN design.According to users’ requirements，it constructed logical carrying network on physical network structure combined with the reconfigurable routing platform technology. When constructing logical carrying network， it would produce mutual exclusion problem of distributed public resources accessing. In view of the architecture of UCN， this paper designed a mutual exclusion algorithm based on token. The algorithm constructed an optimal logic ring borrowing idea from travelling salesman problem.It also introduced a new token-asking method which could effectively reduce system traffic.Finally， it gave simulation results of the algorithm.

Key words:universal carrying network(UCN); mutual exclusion; optimal logic ring; token

近年來，網絡技術取得了飛速發展，服務能力比以前有了很大提高。現有網絡采用面向業務支撐的體系架構，用戶業務和網絡提供的服務是緊耦合關系。當用戶出現了新的業務需求，或者對原有業務的需求提高時，就需要對網絡進行改造，而這種改造通常都是從增加鏈路帶寬、提高節點處理速度、增加協議的復雜度等方面展開，難以滿足特性差異日益擴大的用戶業務承載需求。一體化承載網是一種面向服務提供的新型網絡技術體系，它根據網絡服務提供能力和用戶的業務需求、業務特性，在現有物理網絡的基礎上，為用戶構建專用的邏輯承載網。這種定制網絡的服務提供方式能夠更好地滿足用戶多樣化的業務需求，是將來網絡技術發展的一大趨勢[1]。

構建邏輯網的關鍵是對鏈路帶寬、節點端口等公共資源進行分配。由于有多個節點具有構建邏輯網的權利，因此對這些公共資源進行訪問會產生互斥的問題。這個問題究其本質是分布式系統內的互斥問題[2]。

國內外針對分布式系統的互斥問題展開了技術探索，提出了很多算法。這些算法大致可以歸為以下兩類:基于許可的算法和基于令牌的算法。基于許可的算法在主機訪問臨界資源以前，向系統內其他節點發出請求，在得到所有節點的許可后才能訪問臨界資源，典型例子有Lamport算法[3]、Maekawa算法[4]等;基于令牌的算法，系統維護一個令牌，令牌表示一個控制點，只有得到令牌的主機才有資格訪問臨界資源。文獻[5，6]詳細介紹了該類算法。

1 一體化承載網的體系結構

為了簡化整個網絡的管理和邏輯網的構建，一體化承載網采用了分層的體系結構。整個體系結構分為路由節點、域(domain)和區(region)三層，如圖1所示。

所有的路由節點組成物理承載網，局部的多個路由節點組成一個域，多個域組成一個區，全網由多個區組成。柔性網絡配置代理(flexible network configure broker，FNCB)負責域內的邏輯網構建，根服務器(root server)負責區內跨多個域的邏輯網絡的構建，跨多個區的邏輯網則由根服務器協調完成[7]。

在構建域內和區內的邏輯網時，FNCB和root server分別充當配置服務器的角色，由它們統一進行資源的分配和邏輯網的構建，因此不會產生互斥問題。在構建跨區的邏輯網時，是由多個root server協調完成。連接各個root server之間的鏈路是全網的公共資源，不屬于任何root server，是一種臨界資源，所以要設計一種分布式的互斥算法，解決跨區邏輯網構建時訪問公共資源產生的互斥問題。

2 系統模型

2.1 網絡模型

一體化承載網的拓撲結構可以用連通圖G(V，E)表示。其中:V為所有處理節點的集合;E為所有鏈路的集合。網絡具有以下特點:

a)整個網絡的拓撲結構以矩陣的形式保存在每個根服務器中。當有新的節點加入或者退出網絡時，必須通知根服務器更新拓撲信息。

b)所有的根服務器都分配一個惟一的ID號。

2.2 計算模型

算法定義了以下兩種消息:請求消息和令牌消息。

請求消息的結構如下:

Request{

RootServerID;//發送請求的根服務器ID

RequestTime;//發送請求的時間

Resend;//1表示是重發包，0表示不是

};

令牌消息的結構如下:

Token{

ReqList_Token;//請求令牌的節點列表

};

令牌和節點各維護一個請求消息隊列。令牌的隊列為ReqList_Token，節點的隊列為ReqList_Node。請求消息隊列按照請求消息的優先級大小進行排序。優先級的計算規則如下:如果RequestTimei Pri(Reqj);如果RequestTimei=RequestTimej，RootServerIDi Pri(Reqj)。

3 一體化承載網的分布式互斥算法

一般來說，基于令牌的算法需要交換的平均消息數少于基于許可的算法。雖然有些基于許可的算法，如Maekawa算法，能夠將消息復雜度降到O(n)，但是這些算法計算量大，容易出現死鎖。而且，基于令牌的算法有實現簡單，所需消息類型少等優點，因此，采用基于令牌的算法解決一體化承載網的互斥問題。算法的具體實現分為兩個步驟:邏輯環的構造和令牌的傳遞。

3.1 構造邏輯環

系統初始化時，指派一個根服務器節點，根據網絡的拓撲信息G(V，E)構造一個邏輯環，該邏輯環要包括所有根服務器節點。而且，為了優化網絡的性能，提高令牌運行的效率，要使得令牌遍歷邏輯環所經過的節點數目最少。該問題類似于旅行商問題[8](traveling salesman problem)，但是旅行商問題中，需要訪問所有的節點，在一體化承載網的應用背景下，遍歷所有的根服務器節點即可。

該問題的數學模型如下:

對于一體化承載網G(V，E)中的所有根服務器節點集合V′，得到一個訪問序列T=(t1，t2，…，tn)，其中ti∈V′(i=1，2，…，n)，且tn+1=t1，使得minT∈Ω ni=1dti，ti+1。其中:Ω為訪問全部根服務器節點回路的所有組合。

在經典的旅行商問題的解法中，要求圖中所有節點只被訪問一次。但是在現實的網絡拓撲結構中，如果允許重復走，有可能存在更短的回路，而且在有些情況下，如具有星型拓撲的網絡，某些節點必須被訪問多次才能遍歷所有的節點。

基于以上考慮，本文對G(V，E)進行改造。構造一個新圖G′(V′，E′)，其中V′為G中所有根服務器節點。圖G′中，所有的節點兩兩相連，邊E′ij表示在原圖G中連接根服務器Ni和Nj的最短路徑。E′ij不僅存儲邊經過節點的跳數，而且還存儲它對應于原圖G中的路徑。顯然，G′是一個完全圖，且只包含根服務器節點。對該圖運用經典的解決旅行商問題的算法，可以得到一個遍歷所有根服務器節點且代價最小的訪問序列T，這個序列就是本文算法所要構造的邏輯環。邏輯環建立好以后，由構建邏輯環的節點將邏輯環廣播至其他根服務器節點。

3.2 令牌的傳遞

令牌的運動采用基于請求(token-asking)的策略，而不是無限期地在邏輯環內循環。請求消息以鏈表的形式保存在令牌或節點中。算法的具體實現步驟如下所示:

a)根服務器節點Ni接收到構建邏輯網的指令后，產生一個請求消息Reqi，并將節點ID和RequestTime寫入到消息中，然后按照邏輯環的順序將Reqi發送到下一節點。

b)節點Nj收到了Reqi以后，采取以下動作:

(a)如果Nj此時不擁有令牌，且Nj沒有發送請求消息，那么直接將Reqi發送到下一節點;

(b)如果Nj此時不擁有令牌，但是Nj也發送了請求，則按照優先級的順序將Reqi插入到Nj維護的請求隊列ReqList_Nodej中，阻塞此請求，不再進行傳遞。

(c)如果Nj此刻擁有令牌，且Nj此刻沒有構建邏輯網，那么直接發送令牌到節點Ni;

(d)如果Nj擁有令牌，但是Nj此刻正在構建邏輯網，那么就將請求消息按照優先級的順序加入到令牌維護的請求隊列ReqList_Token中。當Nj構建好邏輯網后，從令牌的請求隊列中找到優先級最高的請求，然后將令牌發送到產生該請求的節點。

c)節點Ni收到令牌后，將自己的請求列表ReqList_Nodei合并到ReqList_Token中，并從合并后的列表中刪除自己的請求項。合并以后，被Ni阻塞的所有請求消息被放入ReqList_Token中，然后清空節點維護的請求隊列ReqList_Nodei。接下來Ni開始構建邏輯網，構建好以后將令牌消息發送到ReqList_Token中優先級最高的節點。

4)如果Ni在一段時間內收不到令牌，則有可能是發送的請求消息丟失了，那么重新發送一個請求消息，將Resend置為1，其他內容和上一條請求消息保持一致。持有令牌的節點Nj在收到該消息后，檢查令牌請求隊列中是否有Ni的請求消息，如果有，則丟棄重發的請求;沒有，則將Ni的請求加入到隊列中。

4 算法的模擬仿真與分析

為了檢驗算法的正確性和效率，本文對算法進行了模擬仿真。利用3.1節所描述的方法對圖2所示的網絡構造邏輯環。

圖中共有36個節點，圓圈表示路由器，被虛線框包圍的路由器構成了區，虛線框外的黑色節點表示管轄該區的根服務器。最后得到的邏輯環的拓撲結構如圖3所示。

本文按照圖3所示的邏輯環的拓撲結構布置了局域網，作為實驗網絡。網內設置了30個節點，其中10個被指定為根服務器，其他節點為路由節點。將用本文所述算法實現的程序放到根服務器上，某個根服務器上的文本文件Text.txt作為根服務器訪問的臨界資源。所有根服務器均以時間上服從均勻分布的方式發出臨界資源訪問請求，訪問臨界資源的時間統一設置為30 ms，發送請求消息的間隔分別設置為10 ms、20 ms、50 ms、100 ms、200 ms、500 ms和1 000 ms。最后分別對平均消息數、平均響應時間和響應時間的標準差這三個參數進行分析。

4.1 平均消息數

平均消息數是指平均每個節點訪問臨界資源的過程中產生的消息數。圖4為仿真實驗所得到的關于平均消息數的圖。

如圖4所示，發送的消息數隨著請求間隔的增大而增大。請求間隔小，則表示單位時間內發送的請求數目多，那么請求消息在節點被阻塞的幾率就會增大，因此消息數目較少。當請求間隔很大時，請求消息基本不會被節點阻塞，而是直接發送到令牌持有者，因此消息數目多。

4.2 平均響應時間

平均響應時間是指從發送請求消息到接收令牌平均需要經過的時間。圖5為仿真實驗得到的關于平均響應時間的圖。

平均響應時間為在請求隊列中的等待時間與令牌消息在鏈路上的傳輸時間的總和。一般構建邏輯網的時間遠大于令牌傳輸時間，因此平均響應時間主要取決于在請求隊列的等待時間。從圖中可以看出，單位時間內發送的請求消息越多，令牌的響應時間越長。

4.3 響應時間的標準差

響應時間的標準差可以用來衡量令牌響應時間的波動性。圖6為響應時間標準差的仿真結果。

從圖6中可以看出，請求間隔越大，響應時間的標準差就越小。這是因為請求間隔越短，請求消息就會越多，那么請求消息隊列就會越長。這就導致了有些請求可能等待較長時間，有些能馬上得到響應。當請求間隔增大到一定限度時，請求消息隊列只有很少的請求，那么令牌的響應時間約等于消息傳遞的時間，因此響應時間基本相等。

5 結束語

本文針對一體化承載網在構建邏輯網時的互斥問題，結合一體化承載網體系結構的特點，提出了一種基于令牌的分布式互斥算法。算法借鑒了解決旅行商問題的思想，構造了一個最優的邏輯環，使得令牌傳遞一周的時間最小;并且提出了一種新的令牌傳遞策略，該策略能夠有效地降低系統的通信量，尤其是在請求負荷較高的情況下。本文對所提出的互斥算法進行了模擬仿真實驗，實驗結果表明，該算法能很好地解決一體化承載網中的互斥問題。

參考文獻:

[1]

王浩學，汪斌強，于婧，等.一體化承載網絡體系架構研究[J].計算機學報，2009，32(3):371-376.

[2]張棟，吳春明，姜明.分布式系統中資源分配的一致性算法綜述[J].信息工程大學學報，2009，10(1):37-40.

[3]LAMPORT L.Time，clocks， and the ordering of events in a distributed system[J].Communications of the ACM，1978，21(7):558-565.

[4]MAEKAWA M.A sqrt(n) algorithm for mutual exclusion in decentralized systems[J].ACM Trans on Computer Systems，1985，3(2):145-159.

[5]李云鶴.一種基于令牌的新的互斥算法分析與設計[J].計算機科學，2008，35(4):119-121.

[6]RAZZAQUE M A，HONG C S.Multi-token distributed mutual exclusion algorithm[C]//Proc of the 22nd International Conference on Advanced Information Networking and Applications.Washington DC:IEEE Computer Society，2008:963-970.

[7]吳春明，張棟，姜明.面向服務提供的一體化承載網體系結構的探討[J].信息工程大學學報，2009，10(1):23-27.

[8]李敏，吳浪，張開碧.求解旅行商問題的幾種算法的比較研究[J].重慶郵電大學學報:自然科學版，2008，20(5):624-630.