Fitness based routing

• US 7,961,711 B2
• Filed: 07/15/2008
• Issued: 06/14/2011
• Est. Priority Date: 08/06/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Abbott, Michael, Lovering, Bradford H., Marucheck, Michael J., Feingold, Max Attar, Hasha, Richard L.
• Primary Examiner(s): Ryman; Danniel J
• Assistant Examiner(s): FIALKOWSKI, MICHAEL R
• Application Number:
  US12/173,195
• Publication Number:
  US 20090041033A1
• Time in Patent Office: 1,064 Days
• Field of Search: None
• US Class Current: 370/351
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

The present invention extends to methods, systems, and computer program products for fitness based routing. Embodiments of the invention significantly improve the likelihood that routing nodes contained in routing table have adequate (or even relatively increased) ability to transfer and process messages in an overlay network. Thus, when the node is to make a routing decision for a message, the node has some assurances that any selected routing node is adequate (or is at least the best currently available). Further, a sending node can take preference to routing nodes with higher fitness values when sending a message. Preference to higher fitness metric values further insures that messages are adequately transferred and processed. Accordingly, embodiments of the invention can be used to route messages in a manner that optimizes bandwidth and provides efficient routing capability.

Claims

1. At a computer system which represents a node in an overlay network, the overlay network also including a plurality of other computer systems representing other nodes, a method for maintaining a routing tables at each of the computer systems of the nodes of the overlay network so that routing information from one node to another can be more efficiently determined using the routing tables, the method comprising:

at the computing system of one or more nodes of the overlay network, performing the following;

at a first node of the overlay network, performing an act of receiving node information for another node that exists at a specified location within the overlay network, the node information including fitness information for the other node;

at the first node of the overlay network, performing an act of accessing a routing table that includes one or more nodes, each node in the routing table being a node to which the computer system of the first node can send a message that is then forwarded by that node for delivery to a destination node within the overlay network, each node in the routing table having a fitness metric value representing an ability of the node to transfer and process messages within the overlay network;

at the first node, performing an act of calculating a fitness metric value for the other node, the fitness metric value representing the other node'"'"'s ability to transfer and process messages within the overlay network, the fitness metric value based on one or more characteristics used to determine the fitness information for the other node;

an act of inserting the other node into the routing table of the first node;

an act of dividing the first node'"'"'s routing table into a plurality of ranges, each range corresponding to a portion of the overlay network;

an act of assigning each node in the first node'"'"'s routing table to a specified range based on the location of each of the assigned nodes in the overlay network; and

an act of maintaining the size of the first node'"'"'s routing table so that the routing table does not exceed a specified size when adding other nodes to it, by performing the following;

an act of identifying in the first node'"'"'s routing table a range that is as large or larger than any other range in the routing table in terms of the number of nodes included in the identified range;

an act of identifying a node within the identified range that has the lowest fitness value and as such is least able to transfer and process messages within the overlay network based on fitness metric values of the nodes in the identified range; and

an act of removing the identified node from the routing table of the first node.

2. The method as recited in claim 1, wherein the act of receiving node information for another node comprises an act of receiving a routing table size for the other node along with one or more other characteristics of the other node.

3. The method as recited in claim 1, wherein the act of accessing a routing table comprises an act of accessing a routing table containing nodes that can be used to route a message in a ring topology.

4. The method as recited in claim 1, wherein the act of calculating a fitness metric value for the other node comprises an act of calculating a fitness metric value based on routing table size of the other node.

5. The method as recited in claim 1, wherein each node in the overlay network is assigned a unique identifier, and wherein the act of dividing the routing table into a plurality of ranges comprises an act of dividing the routing table in ranges, each range corresponding to a smaller or larger portion of the overlay network depending on the distance of the range from the computer system, wherein ranges that encompass nodes with unique identifiers that are closer to the node'"'"'s identifier encompass fewer nodes than ranges that encompass nodes with unique identifiers that are closer to the node'"'"'s identifier.

6. The method as recited in claim 1, wherein an act of identifying the node within the identified range that is least able to transfer and process messages within the overlay network comprises an act of identifying the node with the smallest routing table.

7. The method as recited in claim 1, wherein the act of removing the identified node from the routing table comprises an act of removing the node having the smallest routing table from the computer system'"'"'s routing table.

8. The method as recited in claim 1, further comprising:

an act of locking the routing table prior to accessing the routing table; and

an act of unlocking the routing table subsequent to removing the identified node.

9. The method as recited in claim 1, further comprising:

an act of selecting a routing node from the routing table subsequent to removing the identified node; and

an act of sending a message to the selected routing node.

10. At a computer system which represents a node in an overlay network, the overlay network also including a plurality of other computer systems representing other nodes, a method for maintaining routing tables at each of the computer systems of the nodes of the overlay network so that routing information from one node to another can be more efficiently determined using the routing tables, the method comprising:

at the computing system of one or more nodes of the overlay network, performing the following;

at a first node of the overlay network, performing an act of receiving a message from another node in the overlay network, the message including node information for a plurality of further nodes in the overlay network, the node information including fitness information for each of the plurality of further nodes;

at the first node of the overlay network, performing an act of accessing the computer system'"'"'s routing table, the computer system'"'"'s routing table including a plurality of nodes that the computer system can communicate with to route messages to destination nodes within the overlay network, each of the plurality of nodes in the computer system'"'"'s routing table having a fitness metric value representing an ability to transfer and process messages within the overlay network;

at the first node, for each of the plurality of further nodes;

using a fitness calculation module to perform an act of calculating a fitness metric value for the further node, the fitness metric value representing the further node'"'"'s ability to transfer and process messages within the overlay network, the fitness metric value based at least in part on the fitness information for the further node; and

using a routing table manager to perform an act of inserting the further node into the computer system'"'"'s routing table;

at the first node, performing an act of determining in accordance with a routing policy that the number of nodes in the computer system'"'"'s routing table exceeds a specified number;

an act of dividing the first node'"'"'s routing table into a plurality of ranges, each range corresponding to a portion of the overlay network;

an act of assigning each node in the first node'"'"'s routing table to one of the plurality of ranges based on the location of the node in the overlay network;

an act of reducing the size of the first node'"'"'s routing table to the specified number of nodes in accordance with the routing policy, by performing the following;

an act of identifying in the first node'"'"'s routing table a range that is as large or larger than any other range in the routing table in terms of the number of nodes included in the identified range; and

an act of removing the node that has the lowest fitness value and as such is least fit to transfer and process messages, among the nodes in the identified range, from the first node'"'"'s routing table.

11. The method as recited in claim 10, wherein the act of receiving a message from another node in the overlay network comprises an act of receiving a message that includes routing table size for each of the plurality of further nodes along with one or more other characteristics for each of the plurality of further nodes.

12. The method as recited in claim 10, wherein the act of calculating a fitness metric value for the further node comprises an act of calculating a fitness metric value based on routing table size of the further node.

13. The method as recited in claim 10, wherein the act of calculating a fitness metric value for the further node comprises an act of calculating a fitness metric value based solely on routing table size of the further node.

14. The method as recited in claim 10, wherein the act of determining that the number of nodes in the computer system'"'"'s routing table exceeds a specified number comprises an act of referring to a routing table policy.

15. The method as recited in claim 10, further comprising subsequent to removing the node that is least fit to transfer and process messages from among the nodes in the identified range:

repeating the following acts until the number of nodes in the computer system'"'"'s routing table no longer exceeds the specified number;

an act of identifying a next range that includes more nodes, or at least as many nodes, as any other range in the routing table; and

an act of removing the node that is least fit to transfer and process messages, among the nodes in the next identified range, from the routing table, based on fitness metric values.

16. The method as recited in claim 10, further comprising:

an act of locking the routing table prior to accessing the routing table; and

an act of unlocking the routing table subsequent to removing the identified node.

17. The method as recited in claim 10, further comprising:

an act of selecting a routing node from the routing table subsequent to removing the identified node; and

an act of sending a message to the selected routing node.

18. The method as recited in claim 10, wherein the overlay network is a ring topology.

19. The method as recited in claim 10, wherein the overlay network is a peer-to-peer network overlaid on the Internet.

20. At a computer system which represents a node in an overlay network having a doubly linked ring topology, the overlay network also including a plurality of other computer systems representing other nodes, a method for maintaining routing tables at each of the computer systems of the nodes of the overlay network so that routing information from one node to another can be more efficiently determined using the routing tables, the method comprising:

at the computing system of one or more nodes of the overlay network, performing the following;

at a first node of the overlay network, performing an act of receiving a message from another node in the doubly linked ring topology, the message including node information for a plurality of further nodes in the other node'"'"'s routing table, the received node information indicating routing table size for each further node in the other node'"'"'s routing table;

at the first node, performing an act of locking the computer system'"'"'s routing table to prevent any routing determinations subsequent to receiving the message, each node in the computer system'"'"'s routing table being a node to which the computer system of the first node can send messages that are then forwarded by that node for delivery to a destination node within the doubly linked ring topology, each of the plurality of nodes in the computer system'"'"'s routing table stored along with an indication of a corresponding routing table size of the node;

at the first node, performing an act of integrating the plurality of further nodes into the computer system'"'"'s routing table;

at the first node, performing an act of determining that the number of nodes in the computer system'"'"'s routing table exceeds a specified number based on a routing table policy;

at the first node, performing an act of dividing the routing table into a plurality of ranges, each range corresponding to a portion of the doubly linked ring topology;

at the first node, performing an act of assigning each node in the routing table to one of the plurality of ranges based on the location of the node in the doubly linked ring topology;

repeating the following acts at the first node until the number of nodes in the computer system'"'"'s routing table no longer exceeds the specified number;

an act of identifying in the first node'"'"'s routing table a range that is as large or larger than any other range in the routing table in terms of the number of nodes included in the identified range;

an act of identifying a node within the identified range that has the smallest indicated routing table size; and

an act of removing the identified node from the computer system'"'"'s routing table; and

at the first node, performing an act of unlocking the computer system'"'"'s routing table so that the computer system'"'"'s routing table can again be used in routing determinations subsequent to the number of nodes in the computer system'"'"'s routing table no longer exceeding the specified number.

21. At a computer system which represents a node in an overlay network, the overlay network also including a plurality of other computer systems representing other nodes, a computer program product comprised of computer-readable physical storage media, which, when implemented on a computer system of one of the nodes performs a method for maintaining routing tables at each of the computer systems of the nodes of the overlay network so that routing information from one node to another can be more efficiently determined using the routing tables, the method comprising:

at the computing system of one or more nodes of the overlay network, performing the following;

at a first node of the overlay network, performing an act of receiving node information for another node that exists at a specified location within the overlay network, the node information including fitness information for the other node;

at the first node of the overlay network, performing an act of accessing a routing table that includes one or more nodes, each node in the routing table being a node to which the computer system of the first node can send a message that is then forwarded by that node for delivery to a destination node within the overlay network, each node in the routing table having a fitness metric value representing an ability of the node to transfer and process messages within the overlay network;

at the first node, performing an act of calculating a fitness metric value for the other node, the fitness metric value representing the other node'"'"'s ability to transfer and process messages within the overlay network, the fitness metric value based on one or more characteristics used to determine the fitness information for the other node;

an act of inserting the other node into the routing table of the first node;

an act of dividing the first node'"'"'s routing table into a plurality of ranges, each range corresponding to a portion of the overlay network;

an act of assigning each node in the first node'"'"'s routing table to a specified range based on the location of the each of the assigned nodes in the overlay network; and

an act of maintaining the size of the first node'"'"'s routing table so that the routing table does not exceed a specified size when adding other nodes to it, by performing the following;

an act of identifying in the first node'"'"'s routing table a range that is as large or larger than any other range in the routing table in terms of the number of nodes included in the identified range;

an act of identifying a node within the identified range that has the lowest fitness value and as such is least able to transfer and process messages within the overlay network based on fitness metric values of the nodes in the identified range; and

an act of removing the identified node from the routing table of the first node.

22. At a computer system which represents a node in an overlay network, the overlay network also including a plurality of other computer systems representing other nodes, a computer program product comprised of computer-readable physical storage media, which, when implemented on a computer system of one of the nodes performs a method for maintaining routing tables at each of the computer systems of the nodes of the overlay network so that routing information from one node to another can be more efficiently determined using the routing tables, the method comprising:

at the computing system of one or more nodes of the overlay network, performing the following;

at a first node of the overlay network, performing an act of receiving a message from another node in the overlay network, the message including node information for a plurality of further nodes in the overlay network, the node information including fitness information for each of the plurality of further nodes;

at the first node of the overlay network, performing an act of accessing the computer system'"'"'s routing table, the computer system'"'"'s routing table including a plurality of nodes that the computer system can communicate with to route messages to destination nodes within the overlay network, each of the plurality of nodes in the computer system'"'"'s routing table having a fitness metric value representing an ability to transfer and process messages within the overlay network;

at the first node, for each of the plurality of further nodes;

using a fitness calculation module to perform an act of calculating a fitness metric value for the further node, the fitness metric value representing the further node'"'"'s ability to transfer and process messages within the overlay network, the fitness metric value based at least in part on the fitness information for the further node; and

using a routing table manager to perform an act of inserting the further node into the computer system'"'"'s routing table;

at the first node, performing an act of determining in accordance with a routing policy that the number of nodes in the computer system'"'"'s routing table exceeds a specified number;

an act of dividing the first node'"'"'s routing table into a plurality of ranges, each range corresponding to a portion of the overlay network;

an act of assigning each node in the first node'"'"'s routing table to one of the plurality of ranges based on the location of the node in the overlay network;

an act of reducing the size of the first node'"'"'s routing table to the specified number of nodes in accordance with the routing policy, by performing the following;

an act of identifying in the first node'"'"'s routing table a range that is as large or larger than any other range in the routing table in terms of the number of nodes included in the identified range; and

an act of removing the node that has the lowest fitness value and as such is least fit to transfer and process messages, among the nodes in the identified range, from the first node'"'"'s routing table.

23. At a computer system which represents a node in an overlay network having a doubly linked ring topology, the overlay network also including a plurality of other computer systems representing other nodes, a computer program product comprised of computer-readable physical storage media, which, when implemented on a computer system of one of the nodes performs a method for maintaining routing tables at each of the computer systems of the nodes of the overlay network so that routing information from one node to another can be more efficiently determined using the routing tables, the method comprising:

at the computing system of one or more nodes of the overlay network, performing the following;

at a first node of the overlay network, performing an act of receiving a message from another node in the doubly linked ring topology, the message including node information for a plurality of further nodes in the other node'"'"'s routing table, the received node information indicating routing table size for each further node in the other node'"'"'s routing table;

at the first node, performing an act of locking the computer system'"'"'s routing table to prevent any routing determinations subsequent to receiving the message, each node in the computer system'"'"'s routing table being a node to which the computer system of the first node can send messages that are then forwarded by that node for delivery to a destination node within the doubly linked ring topology, each of the plurality of nodes in the computer system'"'"'s routing table stored along with an indication of a corresponding routing table size of the node;

at the first node, performing an act of integrating the plurality of further nodes into the computer system'"'"'s routing table;

at the first node, performing an act of determining that the number of nodes in the computer system'"'"'s routing table exceeds a specified number based on a routing table policy;

at the first node, performing an act of dividing the routing table into a plurality of ranges, each range corresponding to a portion of the doubly linked ring topology;

at the first node, performing an act of assigning each node in the routing table to one of the plurality of ranges based on the location of the node in the doubly linked ring topology;

repeating the following acts at the first node until the number of nodes in the computer system'"'"'s routing table no longer exceeds the specified number;

an act of identifying in the first node'"'"'s routing table a range that is as large or larger than any other range in the routing table in terms of the number of nodes included in the identified range;

an act of identifying a node within the identified range that has the smallest indicated routing table size; and

an act of removing the identified node from the computer system'"'"'s routing table; and

at the first node, performing an act of unlocking the computer system'"'"'s routing table so that the computer system'"'"'s routing table can again be used in routing determinations subsequent to the number of nodes in the computer system'"'"'s routing table no longer exceeding the specified number.