Back to results
US 7,889,680 B2Granted
Merging anonymous routers in end-to-end network topology inference
AssigneeThe Hong Kong University of Science and Technology
InventorsShueng-Han Gary Chan, Xing Jin
Life of this patent
Estimating the term…
Abstract
Algorithms are described that facilitate the inference of a network topology by estimating router co-ordinates and merging anonymous routers. The algorithms have practical applications in the inference of a network topology as part of the provision of a network service that is based on the underlying topology and where knowledge of the actual topology allows improved performance.
Claims19
A method, comprising:
- estimating, by an apparatus, coordinates of a plurality of anonymous routers of a network in a multi-dimensional space, the network having a number of hosts and routers, known or anonymous, using path information collected between the hosts, wherein respective ones of the plurality of anonymous routers have at least internet protocol (IP) address unknown to the apparatus;
- inferring, by the apparatus, a topology of the network, using at least the estimated coordinates of the plurality of anonymous routers;
- and
- simplifying the topology of the network, by the apparatus, by merging selected ones of the anonymous routers with other anonymous routers or known routers into one or more groups, treating each of the groups as one router, anonymous or known, wherein said selected ones of the anonymous routers are based on distances between the anonymous routers, between the anonymous routers and the known routers, or between the anonymous routers and the hosts.
1 more element
A method of inferring a topology of a network, comprising:
- estimating, by an apparatus, coordinates of a plurality of anonymous routers of the network in a multi-dimensional space, the network having a number of hosts and routers, known or anonymous, using path information collected between the hosts, wherein respective ones of the plurality of anonymous routers have internet protocol (IP) addresses unknown to the apparatus;
- inferring, by the apparatus, the topology of the network, using at least the estimated coordinates of the plurality of anonymous routers;
- and
- simplifying the topology of the network, by the apparatus, by merging a pair of anonymous routers of the plurality of anonymous routers of the network that shares at least one known router or host as a neighbor, and by treating the pair of anonymous routers as one anonymous router.
1 more element
A method of providing an application layer service, comprising:
- estimating, by an apparatus, coordinates of a plurality of anonymous routers of the network in a multi-dimensional space, the network having a number of hosts and routers, known or anonymous, using path information collected between the hosts, wherein respective ones of the plurality of anonymous routers have internet protocol (IP) addresses unknown to the apparatus;
- inferring, by the apparatus, the topology of the network, using at least the estimated coordinates of the plurality of anonymous routers;
- and
- providing the application layer service on a network, by the apparatus, using a topology wherein a pair of anonymous routers of the plurality of anonymous routers of the network that shares at least one known router or host as a neighbor is merged and considered as one anonymous router.
1 more element
An apparatus, comprising:
- logic configured to cause the apparatus, in response to operation of the logic by the apparatus, to perform operations including:
- estimating coordinates of a plurality of anonymous routers of a network in a multi-dimensional space, the network having a number of hosts and routers, known or anonymous, using path information collected between the hosts, wherein respective ones of the plurality of anonymous routers have internet protocol (IP) addresses unknown to the apparatus;
- inferring, a topology of the network, using at least the estimated coordinates of the plurality of anonymous routers;
- and
- simplifying the topology of the network by merging selected ones of the anonymous routers with other anonymous routers or known routers into one or more groups, treating each of the groups as one router, anonymous or known, wherein said selected ones of the anonymous routers are based on distances between the anonymous routers, between the anonymous routers and known routers, or between the apparent anonymous routers and the hosts.
2 more elements
Dependencies are inferred from the claim text.