Media.Player

Merging Anonymous Routers in End-to-End Network Topology Inference端對端網絡拓撲結構測量中匿名路由器的合並

Summary

Previous merging algorithms have un-practically high computational complexity and hence cannot be applied to medium or large size networks.

This invention presents two fast algorithms to merge anonymous routers. The first one uses Isomap to embed routers into a high-dimensional space based on their network distances. It then merges anonymous routers according to their coordinates. The second approach trades off some accuracy for lower complexity, which merges anonymous routers based on their neighbors. Extensive simulations on Internet-like and real Internet topologies have been conducted. The results show that this merging algorithms can efficiently reduce router inflation with low error. Among them, the delay-based Isomap merging algorithm obtains the most similar topology to the actual one and the neighbor matching algorithm achieves the lowest computational and storage complexities.

Technology Benefits

1. Fast inference algorithms with low computational and storage complexities
2. Inferring a topology with low distortion

Technology Application

- For use in topology inference by researcher, Internet service provider and network deployer / maintainer:
(a) A peer-to-peer streaming system can integrate the topology information to provide efficient data delivery to users.
(b) Other applications include peer-to-peer file sharing, overlay network routing and application-layer multicast.

Supplementary Information

Patent Number: US7889680B2
Application Number: US2007850151A
Inventor: Chan, Shueng-Han Gary | Jin, Xing
Priority Date: 5 Sep 2006
Priority Number: US7889680B2
Application Date: 5 Sep 2007
Publication Date: 15 Feb 2011
IPC Current: G08C001500
US Class: 370255
Assignee Applicant: The Hong Kong University of Science & Technology
Title: Merging anonymous routers in end-to-end network topology inference
Usefulness: Merging anonymous routers in end-to-end network topology inference
Summary: Method for inferring an end-to-end network topology from a traceroute result to provide an application layer service e.g. application-layer multicast (ALM) service, peer-to-peer service and overlay path routing service, on an underlying network.
Novelty: End-to-end network topology inferring method for e.g. overlay path routing service, involves collecting and analyzing round-trip delays, estimating anonymous router co-ordinates, and merging anonymous routers

Industry

ICT/Telecom

Sub Category

Telecommunication

Application Date

5 Sep 2007

Application No.

US 11/850151

Patent Information

US 7889680

ID No.

TTC.PA.317S

Country/Region

Hong Kong