基于最短路徑樹覆蓋的AS拓撲監測點部署方法
2010-12-31 00:00:00孫力偉彭偉劉宇靖呂保平
計算機應用研究 2010年9期
摘要：面向互聯網AS級拓撲監測應用，提出了一種基于最短路徑樹SPT覆蓋的算法，用于選擇部署最少的監測點，發現盡量完整的AS拓撲。該算法求出所有頂點的最短路徑樹，按照啟發式策略選擇最小的頂點集合，使集合中節點的最短路徑樹可以覆蓋全圖的邊。采用CAIDA AS-links的數據對算法進行驗證，SPT算法選擇了750個左右的監測點，即可發現互聯網中16500多個AS之間(約30000條左右)的鏈路。與隨機選擇節點進行覆蓋的方法相比，該方法選擇的監測點數目減少了近37.5％。
關鍵詞：AS拓撲；監測點；最短路徑樹
中圖分類號：TP309 文獻標志碼：A 文章編號：1001－3695(2010)09－3473－03
