Valley-free shortest path method

Details Valley-free shortest path method Valley-free shortest path method

2011-03-15

2011-03-15

Levitan, Dmitry H (Department: 2461)

Multiplex communications

Pathfinding or routing

Reexamination Certificate

active

07907596

ABSTRACT:
A method of calculating a valley-free shortest path between two autonomous systems having a first graph representing an autonomous system topology and comprising a plurality of nodes and a plurality of links interconnecting the nodes, each link linking a first and a second node of the plurality of nodes. The method comprises generating a second graph using the first graph by: Mapping the nodes of the first graph into the second graph, by representing each node of the first graph by a respective uphill node and a downhill node; mapping each link of the first, second and third relationship type with a plurality of directed links between the uphill and downhill nodes according to the type of relationship. The method further comprises calculating the shortest-path route between two autonomous systems on the second graph, using the shortest-path routing algorithm.

REFERENCES:
patent: 6981055 (2005-12-01), Ahuja et al.
patent: 2008/0218519 (2008-09-01), Coury et al.
Gao, “On Inferring Autonomous System Relationships in the Internet”, IEEE/ACM Transactions on Networking, Dec. 2001.
Subramanian, et al, “Characterizing the Internet Hierarchy from Multiple Vantage Points”, Proc. IEEE INFOCOM, Jun. 2002.
Dimitropoulos, et al, “AS Relationships: Inference and Validation”, ACM SIGCOMM Computer Communication Review, Jan. 2007.
Dimitropoulos, et al, “Inferring AS relationships: Dead end or lively beginning?”, Proceedings of 4th Workshop on Efficient and Experimental Algorithms (WEA '05), May 2005.
Mao, et al, “On AS-level path inference”, ACM SIGMETRICS, Jun. 2005.
Gao, et al, “The Extend of AS Path Inflation by Routing Policies”, IEEE Global Internet Symposium, Nov. 2002.
Dimitropoulos, et al, “Revisiting Internet AS-level Topology Discovery”, Proceedings of Passive and Active Measurements, Mar. 2005.

Affiliated with

Also associated with

Rating

Valley-free shortest path method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Valley-free shortest path method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Valley-free shortest path method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2740113