System and method for routing messages within a messaging system

• US 7,693,071 B2
• Filed: 05/27/2005
• Issued: 04/06/2010
• Est. Priority Date: 05/27/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Achlioptas, Demetrios, Tribble, Eric D., Pearson, Malcolm E., Warman, Leon
• Primary Examiner(s): Ferris; Derrick W
• Assistant Examiner(s): GHOWRWAL, OMAR J
• Application Number:
  US11/139,704
• Publication Number:
  US 20060268722A1
• Time in Patent Office: 1,775 Days
• Field of Search: 370/238
• 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;

determining an available transmission schedule of the target node and the one or more intermediate nodes, wherein the available transmission schedule comprises an operating schedule indicating the times of day that the target node and each intermediate node in the created destination alternative table are available to accept transmissions from other network nodes;

attempting transmission of the message to the target node as a function of the available transmission schedule of the target node;

if the transmission of the message to the target node fails, attempting transmission of the message to at least one intermediate node having the highest priority as identified in the created destination alternative table, where the at least one intermediate node is available to accept transmissions at the time of attempting transmission of the message according to the determined available transmission schedule of the target node and the one or more intermediate nodes; and

if the transmission of the message to the highest priority intermediate node fails, attempting transmission of the message to additional intermediate nodes of successively decreasing priority as identified in the created destination alternative table, said additional intermediate nodes being nodes which are available to accept transmissions at the time of attempting transmission of the message according to the determined available transmission schedule of the target node and the one or more intermediate nodes;

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 the last node of divergence.

2. The method of claim 1, 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.

3. The method of claim 1, further comprising tracking the number of times the message has been transmitted between nodes;

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

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

4. 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.

11. The method of claim 1 further comprising:

attempting transmission of the message to the target node when the transmission schedule of the target node indicates that the target node is available.

5. A message communication system for transmitting a message, the message communication system having a current server, a target server, and one or more intermediate servers connected to a 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 that are less than the transmission costs of the current server to the target server, wherein the intermediate servers are prioritized according to their minimum transmission costs;

the current server configured to execute computer-executable instructions stored on a computer-readable storage media for;

determining an available transmission schedule of the target server and the one or more intermediate servers, wherein the available transmission schedule comprises an operating schedule indicating the times of day that the target server and each intermediate server in the destination alternative table accept transmissions from other network servers;

attempting transmission of a message to the target server as a function of the available transmission schedule of the target server;

if the transmission of the message to the target server fails, attempting transmission of the message to at least one intermediate server having the highest priority as identified in the destination alternative table, where the at least one intermediate server is available to accept transmissions at the time of attempting transmission of the message according to the determined available transmission schedule of the target server and the one or more intermediate servers;

if the attempt to transmit the message to the highest priority intermediate server fails, attempting transmission of the message to additional intermediate servers of successively decreasing priority as identified in the destination alternative table, said additional intermediate servers being nodes which are available to accept transmissions at the time of attempting transmission of the message according to the determined available transmission schedule of the target server and the one or more intermediate servers; and

tracking the number of transmissions between servers 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, returning the message as undeliverable.

6. The system of claim 5, wherein the message is transmitted over a computer network from the current server to at least two target servers, 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 the last server of divergence.

7. The system of claim 6, further comprising,

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

and

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

12. The system of claim 5 wherein the current server being configured to further execute computer-executable instructions being stored on a computer-readable storage media for:

attempting transmission of the message to the target server when the transmission schedule of the target server indicates that the target server is available.

8. One or more computer-readable storage 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 creating a destination alternative table of the intermediate nodes on the network and determining the transmission costs from the intermediate nodes to the target node that are less than the transmission costs of the current node to the target node, and prioritizing the intermediate nodes according to their associated minimum transmission costs;

instructions for maintaining a cache of intermediate nodes having failed connections occurring within a predetermined time period, wherein intermediate nodes are removed from the cache after the expiration of the predetermined time period;

instructions for determining an available transmission schedules of the target node and the one or more intermediate nodes, wherein the available transmission schedule comprises an operating schedule indicating the times of day that the target node and each intermediate in the node accepts transmissions;

instructions for attempting transmission of the message to the target node as a function of the cache of failed nodes and the available transmission schedule of the target node, wherein the available transmission schedule comprises an operating schedule indicating the times of day that the target node and each intermediate node in the created destination alternative table are available to accept transmissions from other network nodes, and if the transmission of the message to the target node fails, attempting transmission of the message to at least one additional intermediate node as a function of its priority as identified in the created destination alternative table, the cache of failed nodes, and the available transmission schedule of the at least one additional intermediate node, wherein the at least one additional intermediate node is available to accept transmissions at the time of attempting transmission of the message according to the determined available transmission schedule of the target node and the one or more intermediate nodes, and wherein the message is not transmitted to an intermediate node included in the cache of failed nodes;

instructions for attempting transmission of the message to the intermediate node having the highest priority as identified in the created destination alternative table if the attempt to transmit the message to the target node fails; and

instructions for attempting transmission of the message to additional intermediate nodes of successively decreasing priority as identified in the created destination alternative table if the attempt to transmit the message to the highest priority intermediate node fails;

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 transmitting the message to the last node of divergence.

9. The computer-readable storage media of claim 8, further comprising:

instructions for determining if a 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.

10. The computer-readable storage media of claim 8, 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.

13. The computer-readable storage media of claim 8, further comprising:

instructions for attempting transmission of the message to the target node when the transmission schedule of the target node indicates that the target node is available.