AsiaIPEX is a one-stop-shop for players in the IP industry, facilitating IP trade and connection to the IP world. Whether you are a patent owner interested in selling your IP, or a manufacturer looking to buy technologies to upgrade your operation, you will find the portal a useful resource.

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

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
Sub Category
Application Date
5 Sep 2007
Application No.
US 11/850151
Patent Information
US 7889680
ID No.
Hong Kong

For more information, please click Here
Mobile Device