Patent ID: 7907596
Filing Date: 2011-03-15
Classification: H04L

Abstract:
1. A method of determining a shortest path for routing data packets between a source autonomous system (src) represented by one node in a first graph and a destination autonomous system (dst) represented by another node in a first graph, the first graph representing an autonomous system topology and comprising a plurality of nodes and a plurality of links, each link linking a first and a second node of the plurality of nodes, the nodes representing autonomous systems and the links representing relationship types, the relationship type being one of: a first, a second or a third type, the method comprising the steps of: generating a second graph using the first graph by: (a) mapping each node of the first graph to an uphill node and a downhill node in the second graph, (b) for each link of the first relationship type between a first node and a second node in the first graph, mapping the link to: a directed link from the first uphill node to the second uphill node, a directed link from the second uphill node to the first downhill node, and a directed link from the second downhill node to the first downhill node, (c) for each link of the second relationship type, between a first node and a second node in the first graph, mapping the link to: a directed link from the first uphill node to the second downhill node, and a directed link from the second uphill node to the first downhill node, (d) for each link of the third relationship type, between a first node and a second node in the first graph, mapping the link to: a directed link from the first uphill node to the second uphill node, a directed link from the second uphill node to the first uphill node, a directed link from the first downhill node to the second downhill node, and a directed link from the second downhill node to the first downhill node, wherein the first uphill node and the first downhill node in the second graph represent the first node in the first graph, and the second uphill node and the second downhill node in the second graph represent the second node in the first graph, determining a shortest-path route between the source (src) and the destination autonomous system (dst) in the second graph, using a shortest-path routing algorithm.