兩個庫所不變量表明，代理端、管理端，各自對應的所有庫所的token數等於常數1即各S不變量中的庫所對應的執行機構，在任何時候，隻有其中之一動作，信息在處理前，不會被再次傳送，從而保證了協議的可靠性。不依賴於初始標識，這代表代理端和管理端在協議運行過程中的庫所總量沒有發生變化，體現了協議的守恒性。
4.3分析結論
由以上分析可以得出結論，協議是無死鎖的、安全的、守恒的，最終能實現在建立聯係的基礎上進行PDU操作，或向上層用戶發出指示無法建立聯係。
5.結束語
本文介紹了MNMP，該協議的執行是未來衛星網網絡管理的基礎。我們給出了該協議的Petri網形式描述，並利用可達樹和不變量分析技術驗證了該協議的正確性。下一步的工作是利用Petri對該協議的性能進行分析。
LEObrMEO衛星網絡中一種抗毀路由算法
李冬妮、馮金、王光興
（東北大學網絡與通信中心）
摘要：本文提出了一種基於ATM技術的抗毀路由算法。該算法通過VPC將衛星網虛擬成一個全連接網絡，將衛星網絡劃分為若幹個可動態重組的簇，簇首維護本簇實時拓撲信息。星際鏈路出現故障時，簇首將盡量在本簇內重建VPC，如果無法重建則在更大的已知拓撲範圍內重建VPC。在Iridium係統模型上對該算法的信令開銷、有效性進行的仿真結果顯示，抗毀路由算法可以繞開故障的星際鏈路，提高係統抗毀性，尋路開銷較之OSPF算法大大減小，適合應用於LEObrMEO衛星網絡。
關鍵詞：ATMLEObrMEO；衛星網絡；星際鏈路；抗毀性路由；
1.引言
在LEObrMEO（低br中地球軌道）衛星通信係統中，要提高遠距離傳輸速度和可靠性，使用星際鏈路（ISL）是十分必要的，由此也帶來了一個關鍵性問題——路由算法設計。如果采用有線網絡中廣泛使用的最短路徑算法是不合適的，國內外學者基於星際鏈路的LEObrMEO路由算法做了很多研究。本文提出了一種應用於LEObrMEO衛星網絡的抗毀路由算法。該算法解決的問題定義為：在一個采用ATM技術的LEObrMEO衛星網絡中，衛星到衛星的端對端路由問題。
2.抗毀路由算法
抗毀路由算法可分為三個過程：路由的離線初始化、動態成簇和擴散式抗毀尋路。
2.1路由的離線初始化
由於衛星運行的規律性和可預知性，可以在離線的狀態下采用VPC（虛通路連接）將基於ATM技術的衛星LEObrMEO網絡虛擬成一個全連接的網絡。其基本思想是：根據衛星運行的規律將衛星運行的周期分為若幹個離散的時間片，並認為在一個時間片內衛星網的拓撲是不變化的。在這個不變的拓撲中，為每一顆衛星離線計算到其他所有衛星的路由。
2.2動態成簇
動態成簇算法包括“簇的離線初始化”和“簇的動態重組”。本文以Iridium（銥星）係統為例說明這兩個過程。
（1）簇的離線初始化。
簇的離線初始化利用衛星運動的規律，采用離線路由算法的思想遵循以下幾個原則來設計衛星網的初始成簇方案：
①同簇內衛星間應有較多的冗餘鏈路；
②同簇內的衛星數量應該適中；
③簇首盡量選在簇中心位置；
④簇應該與盡量多的其他簇相鄰。
根據上述思想，本文在離線狀態下，將Iridium係統的星座分為6個簇。
（2）簇的動態重組。
為了盡量減少係統開銷，隻有在以下兩種情況下才啟動簇的重組過程：
①衛星檢測不到簇首時。
導致簇首不可達的原因可能有兩種情況：簇首失效和ISL故障導致簇分裂。
除簇首以外所有節點都始終維護一個“簇首存在定時器”（CET）。一旦該定時器超時，就觸發“簇首不可達”事件，衛星馬上檢查自身ISL連接情況：如無原始簇ISL，則該衛星自成一簇，並設自己為簇首；如還可以與同原始簇的其他衛星連通，則與原始簇可連通衛星組成一個新簇，並選舉簇首。
②兩重組簇首可通過原始簇ISL互通時。
重組簇之間的ISL修複時，應該重新合並為原始簇，並依據簇首優先級重新選舉簇首。
2.3擴散式抗毀尋路
衛星網絡中可能出現不可預知的ISL斷鏈，導致VPC中斷。檢測到ISL故障的衛星分析故障ISL上的VPC結構表，並把“VPC重建請求”發送給本簇的簇首。簇首收到“VPC重建請求”後將完成VPC的重建過程。
（1）VPC的簇內重建。
簇首收到“VPC重建請求”後對要求重建的VPC逐條進行處理。簇首衛星根據VPCi的PList和NList,在簇內為VPCi重新選擇路由，並且發送“路由配置報文”,要求相關簇內衛星重新配置路由表，實現VPC的重建。
3.算法的性能分析
本文在Iridium係統拓撲結構上運行OSPF（開放最短路徑優先）和抗毀路由兩種算法，采用NS2仿真軟件對其信令開銷、有效性進行了分析比較。
3.1信令開銷
當網絡無故障時，抗毀路由算法僅要求簇成員節點將自己的鏈路狀態信息發送給本地的簇首，而非OSPF那樣進行全網的廣播，因此信令開銷遠小於OSPF算法。
出現故障時，為了對節點的路由表進行動態的調整從而繞開故障鏈路，抗毀路由要求節點增加發送的信令包數目。
3.2算法的有效性
此處所說的算法的有效性，是指算法對網絡資源利用的效率。在仿真中我們選擇一定時間內網絡中所有節點成功轉發網絡層協議數據單元（N-PDU）的數量作為其度量標準（稱之為平均網絡吞吐量），將抗毀算法與OSPF進行了比較。
可以看出，當網絡負載較輕時平均網絡吞吐量基本是隨網絡負載的加重線性增加的，而隨著網絡負載進一步加重平均網絡吞吐量也逐漸飽和。網絡無故障時，抗毀路由與OSPF的曲線完全重合；當網絡中ISL故障（隨機選定兩條故障）時，隨著網絡負載加重抗毀路由更快的飽和，其效率不如OSPF算法。抗毀路由與OSPF的平均網絡吞吐量比較這主要是因為ISL故障時，抗毀路由無法完成對路徑的全局優化，但在網絡負載較輕的時候，其效率與OSPF相差不多。