Routing-based proximity for communication networks

• US 8,179,801 B2
• Filed: 06/09/2009
• Issued: 05/15/2012
• Est. Priority Date: 06/09/2009
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Previdi, Stefano, Medved, Jan, Tian, Jining, Luong, Steven
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Bokhari, Syed M
• Application Number:
  US12/480,941
• Publication Number:
  US 20100309789A1
• Time in Patent Office: 1,071 Days
• Field of Search: 370/254, 370/258, 370/238, 709/201, 709/217, 703/13
• US Class Current: 370/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length

Abstract

A node in an overlay network requests a ranked list of other nodes in multiple areas of the overlay network that can provide a desired piece of content or service to the requesting node. A separate node such as a router generates the ranked list using a routing algorithm, returning the list to the requesting node so that the requesting node may acquire the desired content or service from the nearest node in the overlay network.

Claims

1. A system comprising:

at least one non-transitory computer readable storage medium storing data;

at least one processor configured to perform operations on the stored data;

a service gateway configured to;

receive node identifications of a plurality of nodes from a requesting node, the plurality of nodes being peers to the requesting node in an overlay network using infrastructure of a backbone network, the requesting node residing in a different specified network area than at least some of the plurality of nodes including a second node residing in a second network;

determine a topological distance between the requesting node and each of the plurality of nodes, wherein a shortest path first (SPF) proximity algorithm is used to determine the topological distance between the requesting node and at least one of the plurality of nodes and determining the topological distance between the requesting node and the second node includes using link state information of a second service gateway associated with the second area and received from the second service gateway over a tunnel-based adjacency established between the service gateway and the second service gateway;

generate a list of peers ranking the plurality of nodes, based at least in part on the respective topological distance of each node in the plurality of nodes to the requesting node; and

return the list of peers to the requesting node in response to a proximity request received from the requesting node, the proximity request including the node identifications.

2. The system of claim 1, wherein the service gateway is a first service gateway associated with a first area and determining distance between the requesting node and the second node includes:

establishing the tunnel-based adjacency between the service gateway and the second service gateway associated with the second area, wherein the service gateway and second service gateway are including in a plurality of service gateways each associated with at least one network area in a plurality of network areas;

identifying the second service gateway as a member of the second area; and

receiving link state databases of other service gateways in the plurality of service gateways, including the link state database of the second service gateway, wherein the link state database of each service gateway is flooded to at least some of the service gateways in the plurality of service gateways.

3. The system of claim 1, wherein the proximity request includes a proximity source address corresponding to the requesting node, the service gateway further configured to identify that the proximity source address is in a different area than at least one of the plurality of nodes identified in the received node identifications.

4. The system of claim 1, wherein an Open Shortest Path First (OSPF) routing protocol is employed.

5. The system of claim 4, wherein during the use of the SPF algorithm, multiple topologies from multiple areas are attached to form a single tree.

6. The system of claim 2, further comprising a reflector service gateway associated with the first service gateway, the reflector service gateway storing link state information from other areas in the plurality of areas from the link state databases received by the first service gateway, the reflector service gateway configured to:

receive requests from the first service gateway relating to a proximity determination relating to a particular node, in the plurality of nodes, from a different area; and

return, to the first service gateway, link state information corresponding to the different area in response to the received requests from the first service gateway.

7. The system of claim 1, wherein the service gateway is transparent to the overlay network.

8. The system of claim 7, wherein the service gateway collects link state data in connection with routing protocol operations and receives traffic only if the traffic is destined for the service gateway.

9. An article comprising logic encoded in non-transitory media and operable, when executed by a processor, to perform operations comprising:

receiving from a requesting node in a communication network a proximity request including a list of a plurality of other nodes in a plurality of areas in the network that can provide a desired piece of content to the requesting node, the plurality of the other nodes including a particular node residing in a particular network area different from the area of the requesting node;

determining a topological distance between the requesting node and each of the plurality of other nodes, wherein determining topological distance between the requesting node and the particular node includes using link state information of a service gateway associated with the particular area and received from the service gateway over a tunnel-based adjacency established with the service gateway;

generating a ranked list of the plurality of other nodes ranking the plurality of other nodes, based at least in part on the respective topological distance of each of the plurality of other nodes to the requesting node; and

returning the ranked list to the requesting node in response to the proximity request.

10. The article of claim 9 wherein the operations further comprising:

establishing tunnel-based adjacencies among a plurality of service gateways each associated with at least one network area in the plurality of areas;

identifying each service gateway as a member of the respective area associated with the service gateway;

participating in flooding link state databases among the plurality of service gateways to correlate link state information among at least a portion of the plurality of areas, each service gateway in the plurality of service gateways having a respective link state database; and

storing flooded link state databases of service gateways associated with the portion of the plurality of areas for use in determining topological distance between nodes in different areas.

11. The article of claim 9, wherein topological distance is determined at least in part using a shortest path first (SPF) proximity algorithm.

12. The article of claim 9, wherein each of the requesting node and the plurality of other nodes are peer nodes in a peer-to-peer network.

13. The article of claim 9, wherein each area in the plurality of areas is a defined grouping of contiguous networks and attached nodes.

14. A computer-implemented method comprising:

receiving, using at least one processing device, a proximity request from a requesting node, the proximity request including a list of at least two nodes, identified by the requesting node, at least one particular node of the at least two nodes residing in a particular area different from the requesting node;

determining, using at least one processing device, a topological distance between the requesting node and each of the at least two nodes by executing a shortest path first (SPF) algorithm on each of the at least two nodes relative to the requesting node, wherein determining topological distance between the requesting node and the particular node includes using link state information of a service gateway associated with the particular area and received from the service gateway over a tunnel-based adjacency established with the service gateway;

generating, using at least one processing device, an ordered list of the at least two nodes ranking the at least two nodes, based at least in part on the respective topological distance of each of the at least two nodes to the requesting node; and

returning, using at least one processing device, the ordered list to the requesting node in response to the proximity request.

15. The method of claim 14, further comprising:

identifying that the requesting node is in a first area in a plurality of network areas and that the particular node is in a second area in the plurality of network areas;

retrieving link state data for the second area captured during a flooding of link state databases from a plurality of service gateways including a particular service gateway associated with the second area, the respective link state database of the particular service gateway including link state data for the second area; and

storing databases from each area in the reflector-using the retrieved link state data for the second area to determine the distance between the requesting node and the particular node.

16. The method of claim 14, wherein an Open Shortest Path First (OSPF) routing protocol is employed.

17. The method of claim 16, wherein during use of the SPF algorithm, multiple topologies from multiple areas are attached to form a single tree.

18. The method of claim 14, wherein an Intermediate System to Intermediate System (ISIS) routing protocol is employed.

19. The method of claim 18 further comprising attaching a level 1 database and a level 2 database to form a single tree.

20. The method of claim 14, further comprising:

receiving a second proximity request from a second requesting node on behalf of another node, the second proximity request including a listing of the other node and a plurality of peer nodes to the other node;

determining a topological distance between the other node and each of the plurality of peer nodes by executing a shortest path first (SPF) algorithm on each of the plurality of peer nodes relative to the other node;

generating an ordered list of the plurality of peer nodes ranking the plurality of peer nodes, based at least in part on the respective topological distance of each of the plurality of peer nodes to the other node; and

returning the ordered list to the second requesting node in response to the second proximity request.