Routing-based proximity for communication networks to routing-based proximity for overlay networks

• US 8,014,318 B2
• Filed: 02/10/2009
• Issued: 09/06/2011
• Est. Priority Date: 02/10/2009
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Luong, Steven, Tian, Jining, Davie, Bruce, Medved, Jan, Previdi, Stefano
• Primary Examiner(s): SCHEIBEL, ROBERT C
• Application Number:
  US12/368,436
• Publication Number:
  US 20100202448A1
• Time in Patent Office: 938 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04W 4/02 Services making use of location information

Abstract

A node in an overlay network requests a ranked list of other nodes in 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. An apparatus, comprising:

a processor; and

a computer readable storage medium bearing instructions to cause the processor to;

receive node identifications from a requesting node, the node identifications being associated with respective peers to the requesting node in an overlay network using infrastructure of a backbone network;

use a shortest path first (SPF) algorithm to determine a metric associated with at least one peer and the requesting node;

based at least in part on the metric, generate a list of peers ordered by proximity to the requesting node, wherein a TENT list is generated based on advertisements from certain nodes, the TENT list being generated prior to generating the list of peers; and

return the list of peers to the requesting node, wherein a subset of the peers sharing a common prefix with the requesting node is provisioned with a proximity metric of zero, the subset of the peers having a same subnet as the requesting node.

2. The apparatus of claim 1, wherein the apparatus avoids originating a routing update pursuant to its cooperation with the overlay network.

3. The apparatus of claim 2, wherein the apparatus avoids attracting traffic pursuant to its cooperation with the overlay network.

4. The apparatus of claim 1, wherein particular nodes under test are given preference by the requesting node.

5. The apparatus of claim 1, wherein pseudonodes are given higher preference than non-pseudonodes as part of generating the list of peers.

6. A tangible computer readable non-transitory medium bearing instructions executable by a computer processor for:

receiving from a requesting node in a communication network a list of other nodes in the network that can provide a desired piece of content or service to the requesting node;

generating a ranked list of the other nodes ordered by proximity to the requesting node, wherein a TENT list is generated based on advertisements from certain nodes, the TENT list being generated prior to generating the ranked list; and

returning the ranked list to the requesting node, wherein a subset of the nodes sharing a common prefix with the requesting node is provisioned with a proximity metric of zero, the subset of the nodes having a same subnet as the requesting node.

7. The medium of claim 6, wherein the ranked list is generated at least in part using a shortest path first (SPF) routing algorithm.

8. The medium of claim 6, wherein the processor avoids originating a routing update pursuant to its cooperation with the network.

9. The medium of claim 8, wherein the processor avoids originating traffic pursuant to its cooperation with the network.

10. The medium of claim 6, wherein particular nodes under test are given preference by the requesting node.

11. The medium of claim 6, wherein pseudonodes are given higher preference than non-pseudonodes as part of generating the ranked list.

12. A computer-implemented method comprising:

receiving a list of at least two nodes from a requesting node;

executing a shortest path first (SPF) algorithm on each of the at least two nodes relative to the requesting node to generate an ordered list of the at least two nodes, wherein a TENT list is generated based on advertisements from certain nodes, the TENT list being generated prior to generating the ordered list; and

returning the ordered list to the requesting node, wherein the two nodes share a common prefix with the requesting node and are provisioned with a proximity metric of zero, the two nodes having a same subnet as the requesting node.

13. The method of claim 12, wherein the method avoids originating a routing update pursuant to its cooperation with an overlay network associated with the requesting node.

14. The method of claim 13, wherein the method avoids attracting traffic pursuant to its cooperation with the overlay network.

15. The method of claim 12, wherein particular nodes under test are given preference by the requesting node.

16. The method of claim 12, wherein pseudonodes are given higher preference than non-pseudonodes as part of generating the ordered list.

17. The method of claim 12, wherein the SPF algorithm is a reverse-SPF algorithm.