System and method for routing messages within a messaging system

• US 20060268722A1
• Filed: 05/27/2005
• Published: 11/30/2006
• Est. Priority Date: 05/27/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tribble, Eric D., Pearson, Malcolm E., Warman, Leon, Achlioptas, Demetrios
• Granted Patent: US 7,693,071 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04L 51/23 Reliability checks, e.g. acknowledgments or fault reporting

Abstract

Systems and methods are described which provide enhanced stability, increased predictability, reduced transmission costs, and which conserve bandwidth in routing messages over computer networks. The systems and methods further include providing improved transmission of messages wherein the messages are transmitted to nodes closest to a target delivery node. If delivery is possible to a target node, the message transmission stops at the point of failure in the network, wherein delivery to the target node is accomplished at a later time or the message is returned to the sender.

Claims

1. A computer-implemented method for transmitting a message over a computer network, said network having a current node, a target node, and one or more intermediate nodes connected to the network between the current node and the target node, the method comprising:

creating a destination alternative table of the intermediate nodes located on the network having transmission costs to the target node that are less than the transmission costs of the current node to the target node, wherein the intermediate nodes are prioritized according to their minimum transmission costs;

attempting transmission of the message to the target node; and

if the transmission of the message to the target node fails, attempting transmission of the message to at least one intermediate node as a function of its priority identified in the destination alternative table.

2. The method of claim 1, wherein

if the attempt to transmit the message to the target node fails, attempting transmission of the message to the intermediate node having the highest priority;

and

if the attempt to transmit the message to the highest priority intermediate node fails, attempting transmission of the message to intermediate nodes of successively decreasing priority.

3. The method of claim 1, wherein the message is transmitted over a computer network from the current node to at least two target nodes, the method further comprising:

creating a minimum spanning tree for the network with the current node as a root;

determining a last node of divergence from the minimum spanning tree of at least two recipients residing on different nodes;

grouping recipients according to a last node of divergence; and

transmitting the message to last node of divergence.

4. The method of claim 3, further comprising,

determining if the last node of divergence can transmit the message to the target node;

and

diverging the message from the current node for transmission to the target node when it is determined that the last node of divergence cannot transmit the message to the target node.

5. The method of claim 1, further comprising tracking the number of transmissions between nodes for the message;

wherein the number of transmissions exceeds a minimum threshold, delaying additional transmissions for a settling period; and

wherein the number of transmissions exceeds a maximum threshold, return message as undeliverable.

6. The method of claim 1, wherein the transmission of the message to the target node fails, further comprising:

determining the available transmission schedules of network nodes; and

attempting transmission of the message to an intermediate node according to its priority identified in the destination alternative table and its availability schedule.

7. The method of claim 1, wherein one or more computer-readable media have computer-executable instructions for performing the computer-executable method of claim 1.

8. A message communication system for transmitting a message having a current server, a target server, and one or more intermediate servers connected to the network between the current server and the target server on a message communication network, comprising:

a destination alternative table of the intermediate servers located on the network having transmission costs to the target server, wherein the intermediate servers are prioritized according to their minimum transmission costs;

the current server being configured to execute computer-executable instructions for;

attempting transmission of a message to the target server; and

if the transmission of the message to the target server fails, attempting transmission of the message to at least one intermediate server as a function of its priority identified in the destination alternative table.

9. The system of claim 8, wherein said current server is further configured to execute computer-executable instructions for:

attempting transmission of the message to the intermediate node having the highest priority if the attempt to transmit the message to the target node fails; and

attempting transmission of the message to intermediate nodes of successively decreasing priority if the attempt to transmit the message to the highest priority intermediate node fails.

10. The system of claim 8, wherein the message is transmitted over a computer network from the current node to at least two target nodes, said current server is further configured to execute computer-executable instructions for:

creating a minimum spanning tree for the network of servers with the current server as a root;

determining a last server of divergence from the minimum spanning tree of at least two recipients residing on different servers;

a

grouping recipients according to a last server of divergence; and

transmitting the message to last node of divergence.

11. The system of claim 10, further comprising,

determining if the last node of divergence can transmit the message to the target node;

and

diverging the message from the current node for transmission to the target node when it is determined that the last node of divergence cannot transmit the message to the target node.

12. The system of claim 8, further comprising tracking the number of transmissions between nodes for the message;

wherein the number of transmissions exceeds a minimum threshold, delaying additional transmissions for a settling period; and

wherein the number of transmissions exceeds a maximum threshold, return message as undeliverable.

13. The system of claim 8, wherein the transmission of the message to the target node fails, further comprising:

determining the available transmission schedules of network nodes; and

attempting transmission of the message to an intermediate node according to its priority identified in the destination alternative table and its availability schedule.

14. One or more computer-readable media having computer-executable instructions for transmitting a message over a computer network, said network having a current node, a target node, and one or more intermediate nodes connected to the network between the current node and the target node, comprising:

instructions for determining the transmission costs from the intermediate nodes to the target node and prioritizing the intermediate nodes according to their associated transmission costs; and

instructions for attempting transmission of the message to the target node and if the transmission of the message to the target node fails, attempting transmission of the message to at least one intermediate node as a function of its priority identified in the destination alternative table.

15. The computer-readable media of claim 14, further comprising:

instructions for attempting transmission of the message to the intermediate node having the highest priority if the attempt to transmit the message to the target node fails; and

instructions for attempting transmission of the message to intermediate nodes of successively decreasing priority if the attempt to transmit the message to the highest priority intermediate node fails.

16. The computer-readable media of claim 14, wherein the message is transmitted over a computer network from the current node to at least two target nodes, the computer-readable media further comprising:

instructions for creating a minimum spanning tree for the network with the current node as a root;

instructions for determining a last node of divergence from the minimum spanning tree of at least two recipients residing on different nodes;

instructions for grouping recipients according to a last node of divergence; and

instructions for attempting transmission of the message to the last node of divergence.

17. The computer-readable media of claim 14, further comprising:

instructions for determining if the last node of divergence can transmit the message to the target node and diverging the message from the current node for transmission to the target node when it is determined that the last node of divergence cannot transmit the message to the target node.

18. The computer-readable media of claim 14, further comprising:

instructions for tracking the number of transmissions between nodes for the message;

instructions for delaying additional transmissions for a settling period wherein the number of transmissions exceeds a minimum threshold; and

instructions for returning the message as undeliverable wherein the number of transmissions exceeds a maximum threshold.

19. The computer-readable media of claim 14, wherein the transmission of the message to the target node fails, further comprising:

instructions for determining the available transmission schedules of network nodes; and

instructions for attempting transmission of the message to an intermediate node according to its priority identified in the destination alternative table and its availability schedule.

20. The computer-readable media of claim 14, further comprising:

instructions for maintaining a cache of all nodes having recently failed connections wherein the cache is utilized to avoid attempting to transmit the message to recently failed nodes.