基于隨機Ｐｅｔｒｉ網的ＳＬＰ平臺可信研究

摘 要：在介紹當前主要可信研究方法的基礎上，以SLP為分析對象，重點討論了如何利用隨機Petri網進行服務發現平臺可信研究的建模和分析，并以實例分析為基礎介紹了服務發現平臺主要可信指標的分析步驟和計算方法。最后總結基于隨機Petri的可信服務發現平臺研究面臨的主要問題以及可能的發展方向，并對下一步的工作內容進行了展望。

關鍵詞：隨機Petri網；服務定位協議；全互連服務定位協議；可信計算

中圖分類號：TP31文獻標志碼：A

文章編號：1001-3695(2009)06-2023-04

doi:10.3969/j.issn.1001-3695.2009.06.007

Research of trust SLP based on stochastic Petri net

LEI Wan-bao，ZHU Yi-an

(School of Computer， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:Based on SLP platform， this paper presented how to use SPN to analysis the trust of SDP， and constructed the SPN model of SDP and the analysis scheme of main benchmarks.In the end，summarized the key problem and possible orientation of this area.

Key words:stochastic Petri net（SPN）;service location protocol;mSLP;trust computing

隨著異構資源的極大豐富以及異構性網絡的不斷普及和發展，傳統意義上以IP地址或主機名為主要手段的訪問方式已逐漸不能滿足人們對資源訪問可用性、可靠性以及安全性等可信指標的要求。特別是隨著移動設備的普及和4G網絡的出現，如何在復雜的網絡環境下提高資源訪問透明性；如何應對在通信網絡固有脆弱性、非可視服務本身安全性以及其他非安全性因素條件下，保障服務發現平臺的可用性和可靠性；如何應對因環境變化而采取的自適應可靠性和安全性措施以提高系統的可用性等都成為服務發現平臺（SDP）研究面臨的主要問題。在這種情況下，以追求系統綜合可信服務性能的系統可信性研究逐漸走進人們的視野，即傳統意義上以追求系統高效性為主要目標的研究理念逐漸被現代以構建高可信的系統所替代，可信性必須成為可以衡量和驗證的性能^[1]。

1 研究背景和主要研究方法

系統可信性是指系統提供綜合可信服務性能的能力，其表征的是多個系統可信指標的加權值。根據系統提供服務內容、服務對象以及服務場景等的不同，各SDP平臺關心的可信指標內容以及指標權重值也不盡相同，如可信網絡主要偏重可生存性、可控性和安全性等^[2]，數字系統的可信性主要包括硬件可靠性、軟件可測性、可維護性、可用性以及安全性等^[3]，而SDP卻更多地關心系統的可用性、可靠性、實時性以及安全性等。值得注意的是，雖然可信系統的研究工作是當前工業界和學術界的研究熱點，但是從研究歷程上講，它還比較年輕，尤其是對服務發現平臺可信性研究。另外，以往對系統可信性的研究工作存在明顯的不平衡性和片面性，如UPnP平臺對安全性的研究一直是盲點，而網絡的可控性研究更是可信網絡研究的軟肋。

根據采用的數學模型不同，可信系統的分析方法主要包括數學分析、實驗模擬、排隊理論和隨機Petri網(SPN)等^[4]。

數學方法具體包括解析/代數方法和數值分析方法兩種。其中，解析/代數方法是通過構造系統性能參數之間的函數關系，進而根據函數關系式的解析可解或代數可解來確定系統性能評價標準；數值分析方法以馬爾可夫過程為基礎，通過構造變遷速率或變遷概率矩陣來分析系統的可信性^[4]。

實驗模擬是以模擬程序對目標系統的模擬實驗為基礎，通過對模擬結果的分析來實現對系統的可信分析。其不足之處在于，準確構造模擬程序通常比較復雜，特別是對大型復雜系統和系統內部復雜單元關系的構造等^[4]。

排隊理論通過以建立單元服務對象到來和服務時間的統計研究為基礎，得到相應可信指標的統計規律，進而實現對系統可信性的分析。作為一種較為古老而成熟的可信分析方法，它得到廣泛的認可和應用，但其缺點主要表現在：對分析系統的尺寸比較敏感，且對并行系統的資源共享模型和非乘積解問題的描述能力明顯表現不足^[4]。

SPN以研究模型系統的組織結構和動態行為為目標，著眼于系統中可能發生的各種狀態變化以及變化之間的關系^[5]。近幾年來，其憑借對系統并發性、異步性和不確定性具有很強的動態分析能力，同時具有建模源語少、符合直觀的圖形表示等優點；同時，它既能描述系統狀態，又能表現系統行為，且全局的狀態和行為不是最基本的概念，而是由局部的狀態和行為組合得到的，特別適合于對系統建模和進行系統可信分析^[5]?；谏鲜龇治霾⒔Y合SDP平臺可信研究的主要對象，本文將選用SPN作為SDP可信分析的主要工具，著力于研究UA請求工作模型、DA域更新和修復模型、DA域同步模型以及關鍵可信指標的分析方法。

2 服務發現平臺的可信模型

2.1 模型概述

當前，根據應用背景的不同，人們提出了很多SDP平臺，但都定位基本一致的目標，即為用戶提供對異構資源的透明服務訪問方式，典型的平臺包括UPnP^[6]、Jini^[7]、SLP^[5]以及Allia^[8]等。在這里，本文將選擇SLP作為分析對象，主要原因在于其提供了可選擇的DA目錄工作模式，即可以很好地擬合分布式和集中式兩種SDP平臺因工作模式不同而造成的差異；另外，其延伸版本mSLP采用域內DA全互連結構以提高系統修復能力和工作效率的方法在很大程度上影響著未來SDP的發展方向。

以SLP為基礎架構的SDP平臺主要包括原始SLP、mSLP以及其他SLP平臺變種，它們都以IETF提出的SLP框架為基礎，并結合各自應用背景，分別從不同的角度為人們提供了服務發現和訪問機制。具體模型如圖1~4所示。

1)SLP^[5] 它是由IETF發起且旨在為應用程序提供靈活和可擴展的架構，以實現對網絡服務的發現、訪問以及配置的服務發現平臺^[5]。其可以根據工作場景中是否存在有效DA節點來自動地調整自身的工作模式(目錄式和分布式模式)，以有效地適應網絡拓撲變化。

2）mSLP^[9] 為了解決SLP的帶寬浪費和域內DA注冊服務不一致性問題，以提高系統可信度，mSLP引入了域內DA Mesh互連的體系結構。當某個域內存在多個DA時，mSLP通過持續TCP鏈路將所有DA進行全互連以同步所有DA間的服務注冊信息；在DA廣播階段，除向其域內的所有UA和SA進行廣播外，還向該DA工作域中的其他DA進行廣播以同步服務信息；當某個DA首次進入網絡或重新啟動時，它將直接向其域內的其他DA發送服務注冊信息請求（如果其域內的其他DA都失效時，則采用SLP處理機制）；當SA發送服務注冊請求時，僅需向域中的任一個DA發送服務注冊即可，而剩余工作由DA互連結構來完成。

3)其他變種 為了擴展SLP的應用范圍，人們還提出了能夠有效適應Ad hoc網絡環境需要的SLP-based；為了更好地提供系統對域失效的魯棒性，基于小世界理論的模型亦被引入DA的互連結構中。

從本質上講，SLP-based的基本工作模型繼承了SLP；而基于小世界理論的SLP繼承了mSLP的工作模型。因此，下面將以SLP和mSLP兩種SDP平臺為分析對象，構造出基于SPN的可信模型。

2.2 UA請求工作模型

UA請求工作模型主要描述從UA發送服務查詢請求到SLP平臺返回查詢結果這段過程中系統各模型的工作情況。由于SLP及其變種的區別主要集中在DA收集信息方式上，如SLP主要通過向所在域內所有SA發送廣播消息來實現對DA信息域的更新和修復，各DA之間相互獨立且沒有同步機制；而mSLP更多地將目光投向其域內的其他DA，通過持續的TCP連接來實現對自身信息域的更新和修復。對于用戶請求而言，在正常工作環境下，UA請求工作模型是基本相同的。具體如圖5所示。

圖5中展示了在UA啟動查詢請求后，SLP首先進行DA域查詢請求。當UA所在域內存在有效的DA節點且包括其所查詢的服務信息時，SLP將隨機選擇一個DA作為響應對象，將相應的查詢結果返回給UA并結束查詢；否則，UA將啟動SA廣播查詢請求。與DA查詢類似，若某SA中存在UA所查詢的服務信息，則返回相應的服務信息，并在完成所有SA節點查詢后結束查詢；否則查詢失敗。值得注意的是，UA向DA發送查詢請求是以單播（unicast）形式給出的，而向SA發送查詢請求多以多播(multicast)或廣播(broadcast)形式給出，故在DA有效的情況下，SLP和mSLP均可以有效地節約查詢帶寬，從而提高用戶查詢效率。另外，該模型中還適用于DA無效情況下的分析處理，即DA節點返回查詢結果為空時啟動SA查詢請求。從系統結構上看，DA查詢與SA查詢請求兩者之間關系是有序的儲備系統。將該模型映射到具體服務發現平臺中，即可得到相應的系統可信性的SPN模型。在這種情況下，通過結合實際工作環境中測量的DA和SA查詢平均響應時間和SPN同構的馬爾可夫過程，就可以實現對系統可信性的分析。

2.3 DA域更新和修復模型

DA域更新和修復方式是SLP與mSLP之間的主要區別。該模型主要描述系統中DA發生更新和失效情況下平臺內部進行更新和修復的情況。具體如圖6和7所示。圖6中，當SLP中DA發生失效時，其立即啟動修復請求。由于系統中存在多個SA節點，DA節點將以多播或廣播形式向其域內其他節點發送服務注冊請求。值得注意的是，各SA節點的響應時間變遷（time transition）所對應的實施速率可以通過實際SA節點工作的性能測量得到，故具有實際意義。另外，所有SA節點響應DA服務注冊請求是相互獨立的且并非所有SA都存在所請求查詢的服務信息，故從上述模型可以很直觀地給出一個定性的可用性分析結果，即SLP在DA域更新和修復過程中存在帶寬浪費以及由于獨立性而導致的DA節點所包含服務信息不一致問題。圖7與6最大的區別在于，在向所有SA發送服務注冊查詢之前，DA會向其周圍其他DA節點發送服務注冊請求，僅需要有一個節點響應即可完成整個服務注冊查詢請求，且該動作是以單播形式給出的。從上述兩個模型可以很直觀地得出兩者之間性能的定性關系，同時結合實際系統的響應時間參數可以給出相應的定量分析結果。具體的求解過程可參考文獻［10］。

2.4 DA域同步模型

SLP中所有DA之間是相互獨立的，故DA域同步模型主要針對mSLP而言。在mSLP中，所有DA都要周期性地向其域內其他節點發送同步信息請求以同步各自所擁有的SA注冊信息，且所有同步操作都是以兩兩相互作用為基礎進行的。具體如圖7所示。

對于參與同步的兩個DA而言，首先篩選出兩者所擁有SA注冊信息的并集；在確定所有DA信息都被檢索到后進行重新注冊前的同步；最后再將所有SA信息重新注冊到兩個參與同步的DA域中。msLP的SPN工作模型如圖8所示。

3 可信指標分析實例

下面將介紹如何利用上述SLP可信模型進行可信指標分析。通常利用SPN進行性能分析需要借助于與SPN同構的MC協助，即通過構造出與SPN同構的MC后，利用馬爾可夫過程求解方法進行系統可信分析。為了便于討論，本文以圖7為例，對相應的工作場景作如下假設并進行討論：場景中DA1節點所包含的注冊服務信息集為D1，DA2節點所包含的注冊

其他參數可根據其描述內容進行求解。具體求解過程可參考文獻[10]。

4 結束語

現有SDP研究工作在系統可信性研究方面的不足必將成為困擾SDP平臺走向廣泛應用的主要障礙。SPN在對系統各個狀態間的邏輯關系和動態變化過程所表現出的描述能力^[10]為本文進行可信研究提出了良好的基礎。在介紹了系統可信性研究的主要研究方法的基礎上，本文重點討論了如何利用SPN對SLP和mSLP平臺的UA請求工作模型、DA域更新和修復模型以及DA域同步模型進行建模和分析；并以同步模型為例，詳細描述了具體模型的可信指標求解步驟和方法。從現有的分析內容來看，本文所構建的可信模型基本覆蓋了SLP工作的整個過程，能夠滿足SLP和mSLP可信性的定性和定量分析的需要。由于各SDP的基本目標是一致的，本文所提出的可信平臺分析方法可做拋磚引玉之意，其他SDP可信模型均可以本文所提出的模型為基礎，展開對更具體、更細致模型的分析和研究，這也是下一步研究工作的重點。值得注意的是，現有的研究方法主要針對獨立SDP平臺而言，而對集成式SDP和元SDP容易引發狀態空間爆炸以及維數災難問題，這也是當前研究的難點和下一步工作的內容。

參考文獻：

［1］PATTERSON D.Recovery oriented computing[M].[S.l.]:Princeton University， University of Illinois，University of Michigan，2002.

[2]林闖，彭雪海.可信網絡研究[J].計算機學報，2005，28(5):751-758.

[3]徐拾義.可信計算系統設計和分析[M].北京：清華大學出版社，2006.

[4]林闖，李雅娟，王忠民.性能評價形式化方法的現狀和發展[J]. 電子學報，2002，30(12A):1917-1922.

[5]PERKINS G C，VEIZADES J，DAY M. RFC 2608，Service location protocol，version 2[S].1999.

[6]Universal plug and play specification， v1.0[EB/OL].http://www.upnp.org.

[7]ARNOLD K，SCHEIFLER R W，WALDO J，et al.The Jini specification[S]. 1999.

[8]RATSIMOR O，CHAKARBORTY D，JOSHI A.Allia:alliance-based service discovery for Ad hoc environments[C]//Proc of the 2nd International Conference on Mobile Commerce.[S.l.]:ACM Press，2002.

[9]ZHAO Wei-bin，SCHULZRINNE H，GUTTMANZ E.mSLP-mesh-enhanced service location protocolTechnical Report CUCS-013-00[R].New York:Columbia University，2000.

[10]林闖，汪洋，李泉林.網絡安全的隨機模型方法與評價技術[J].計算機學報，2005，28（12）：1943-1956.

[11]LAPRIE J C.Dependability:basic concepts and terminology[M].Vienna:Springer-Verlag，1990.

[12]MITCHELL C，STAVRODOU V.Mathematics of dependable systems[M].Oxford:Clarendon Press，1995.

[13]XU Shi-yi.On dependability of computing systems[J].Journal of Computer Science and Technology，1999，14(2):116-128.

[14]PENZ S.SLP-based service management for dynamic Ad hoc networks[C]//Proc ofthe 3rd International Workshop on Middleware for Pervasive and Ad hoc Computing.New York:ACM Press，2005:1-8.

[15]CHUANG L.Performance evaluation for computer network and computer architecture[M].2001.