FITNESS BASED ROUTING

• US 20090041033A1
• Filed: 07/15/2008
• Published: 02/12/2009
• Est. Priority Date: 08/06/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Abbott, Michael, Hasha, Richard L., Lovering, Bradford H., Marucheck, Michael J., Feingold, Max Attar
• Granted Patent: US 7,961,711 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• 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, the computer system included as a node in an overlay network, the overlay network also including a plurality of other nodes, a method for maintaining a routing table at the computer system, the method comprising:

an act 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;

an act of accessing a routing table that includes one or more nodes, each node in the routing table being a node that the computer system can send a message to to delivery the message 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;

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 at least in part on the fitness information for the other node;

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

an act of dividing the 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 routing table to a specified range based on the location of the node in the overlay network;

an act of identifying the range that includes the most nodes;

an act of identifying the node within the identified range that is least able to transfer and process messages within the overly 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.

2. The method as recited in claim 1, wherein the act of receiving node information for another node comprises an act of receiving a node 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 accessing a routing table comprises an act out 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 the routing table size of the other node.

5. The method as recited in claim 1, 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 an exponentially smaller or exponentially larger portion of the overlay network depending on the distance of the range from the computer system, ranges closer to the computer being smaller, and range further from the computer system being larger.

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 overly 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 unlock 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, the computer system included as a node in an overlay network, the overlay network also including a plurality of other nodes, a method for maintaining a routing table at the computer system, the method comprising:

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;

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;

for each of the plurality of further nodes;

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

an act of inserting the further node into the computer system'"'"'s routing table;

an act of determining that the number of nodes in the computer system'"'"'s routing table exceeds a specified number;

an act of dividing the 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 routing table to one of the plurality of ranges based on the location of the node in the overlay network;

an act of identifying the range that includes the most nodes; and

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

11. The method as recited in claim 10, wherein the an 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 fitness metric 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 fitness metric 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 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 the most nodes; 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 unlock 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 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 peer-to-peer network overlaid on the Internet.

20. At a computer system, the computer system included as a node in an overlay network having a doubly linked ring topology, the overlay network also including a plurality of other nodes, a method for maintaining a routing table at the computer system, the method comprising:

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 node information indicating routing table size for each further node in the other node'"'"'s routing table;

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 that the computer system can send messages to to delivery the messages 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 a an indication of a corresponding routing table size of the node;

an act of integrating the plurality of further nodes into the computer system'"'"'s routing table;

an act of determining that the number of nodes in the computer system'"'"'s routing table exceeds a specified number;

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

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 until the number of nodes in the computer system'"'"'s routing table no longer exceeds the specified number;

an act of identifying the range that includes the most nodes;

an act of identifying the 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

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.