计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2010年
9期
3473-3475
,共3页
孙力伟%彭伟%刘宇靖%吕保平
孫力偉%彭偉%劉宇靖%呂保平
손력위%팽위%류우정%려보평
AS拓扑%监测点%最短路径树
AS拓撲%鑑測點%最短路徑樹
AS탁복%감측점%최단로경수
面向互联网AS级拓扑监测应用,提出了一种基于最短路径树SPT覆盖的算法,用于选择部署最少的监测点,发现尽量完整的AS拓扑.该算法求出所有顶点的最短路径树,按照启发式策略选择最小的顶点集合,使集合中节点的最短路径树可以覆盖全图的边.采用CAIDA AS -links的数据对算法进行验证,SPT算法选择了750个左右的监测点,即可发现互联网中16 500多个AS之间(约30 000条左右)的链路.与随机选择节点进行覆盖的方法相比,该方法选择的监测点数目减少了近37.5%.
麵嚮互聯網AS級拓撲鑑測應用,提齣瞭一種基于最短路徑樹SPT覆蓋的算法,用于選擇部署最少的鑑測點,髮現儘量完整的AS拓撲.該算法求齣所有頂點的最短路徑樹,按照啟髮式策略選擇最小的頂點集閤,使集閤中節點的最短路徑樹可以覆蓋全圖的邊.採用CAIDA AS -links的數據對算法進行驗證,SPT算法選擇瞭750箇左右的鑑測點,即可髮現互聯網中16 500多箇AS之間(約30 000條左右)的鏈路.與隨機選擇節點進行覆蓋的方法相比,該方法選擇的鑑測點數目減少瞭近37.5%.
면향호련망AS급탁복감측응용,제출료일충기우최단로경수SPT복개적산법,용우선택부서최소적감측점,발현진량완정적AS탁복.해산법구출소유정점적최단로경수,안조계발식책략선택최소적정점집합,사집합중절점적최단로경수가이복개전도적변.채용CAIDA AS -links적수거대산법진행험증,SPT산법선택료750개좌우적감측점,즉가발현호련망중16 500다개AS지간(약30 000조좌우)적련로.여수궤선택절점진행복개적방법상비,해방법선택적감측점수목감소료근37.5%.
