Method for designating communication paths in a network

• US 20020120770A1
• Filed: 02/28/2001
• Published: 08/29/2002
• Est. Priority Date: 02/28/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Parham, Jeffrey B., Lees, William B., Brown, Mark R., Vu, Van H., Vesztergombi, Katalin, Lovasz, Laszlo, Harvey, Nicholas J.A.
• Granted Patent: US 6,879,564 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

A method for designating communication paths in a computer network is provided, in which communication paths are designated for the transmission of data throughout a network. The network may have both recipient computers, which are the intended recipients of the data, and intermediary computers, which are not the intended recipients, but merely relay the data. Each intermediary computer is grouped with the “closest” recipient computer (i.e. the recipient computer with whom it is “least expensive” to communicate). Communication paths between the resulting groups are then identified. A representation of the network is then created. The representation replaces the intermediary computers with the inter-group communication paths, so that the inter-group communication paths appear to pass directly through the locations occupied by the intermediary computers. The created representation is then further processed so that the “least expensive” communication paths may be designated.

Claims

1. A method for designating communication paths for transmitting data in a computer network, the computer network having a plurality of computers that are the intended recipients of the data and one or more computers that are intermediaries with respect to the data, the method comprising:

for each intermediary computer, determining which recipient computer of the plurality of recipient computers to which it is most optimal for the intermediary computer to communicate and grouping the intermediary computer with the determined recipient computer, thereby creating a plurality of groups;

identifying one or more inter-group communication paths through the network that connect two or more groups of the plurality of groups;

creating a representation of the network having a plurality of communication paths, in which the intermediary computers are replaced with the inter-group communication paths, such that the inter-group communication paths pass directly through the locations occupied by the intermediary computers; and

,

designating the most optimal communication paths on the created network representation as being the paths over which the data is to be transmitted.

2. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 1.

3. The method of claim 1, wherein the transmitted data is a message that being disseminated to all of the computers that are intended recipients, wherein the intermediary computers do not process or read the message, but only relay it to other computers, and wherein the intended recipient computers do read and process the message.

4. The method of claim 1, wherein the determining step further comprises:

for each intermediary computer, determining which recipient computer of the plurality of recipient computers has the fastest communication path to the intermediary computer and grouping the intermediary computer with that recipient computer.

5. The method of claim 1, wherein the determining step further comprises:

for each intermediary computer, determining which recipient computer of the plurality of recipient computers has the shortest path, in terms of physical distance, to the intermediary computer and grouping the intermediary computer with that recipient computer.

6. The method of claim 1, wherein the determining step further comprises:

for each intermediary computer, determining which recipient computer of the plurality of recipient computers has the least expensive, in terms of monetary cost, communication path to the intermediary computer and grouping the intermediary computer with that recipient computer.

7. The method of claim 1, wherein each of the plurality of created groups includes a single recipient computer.

8. The method of claim 1, wherein each of the plurality of created groups includes a single recipient computer and one or more intermediary computers.

9. The method of claim 1, wherein some of the recipient computers have read-only copies of the data, and the rest of the recipient computers have writeable copies of the data, the method further comprising insuring that those computers having writeable copies of the data have one or more designated communication paths to other computers having writeable copies of the data that do not pass through computers having read-only copies of the data.

10. In a computer network having a plurality of recipient computers, one or more intermediary computers, and a plurality of communication links over which the computers of the network communicate, each link having an associated cost, a method for designating which of the communication links are to be used to transmit data, wherein each recipient computer is an intended recipient of the data and each intermediary computer is an intermediary with respect to the transmitted data, the method comprising:

representing the network as a forest, wherein the forest comprises a plurality of trees, each tree having a recipient computer as its root, wherein each intermediary computer is designated as a branch of a tree so as to minimize the cost of the communication links between the intermediary computer and the root of the tree;

identifying communication links between the trees of the forest;

for each pair of trees for which links have been identified, representing the recipient computers that are the roots of the trees as being directly linked without any intermediary computers, thereby creating a communication topology map for the network;

generating a minimum-cost spanning tree from the created communication topology map, wherein the minimum-cost spanning tree comprises the cheapest non-redundant links for the recipient computers in the network to use for communication; and

,

designating the links of the minimum-cost spanning tree as the links over which the computers are to transmit data.

11. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 10.

12. The method of claim 10, wherein the cost associated with each link is based on the speed of the link.

13. The method of claim 10, wherein the cost associated with each link is based on the monetary cost of the link.

14. The method of claim 10, wherein the forest is implemented as a Dijkstra shortest-path forest.

15. The method of claim 10, wherein the spanning tree is implemented as a Krukal'"'"'s spanning tree.

16. The method of claim 10, wherein the forest is implemented as a Dijkstra shortest-path forest, and wherein the spanning tree is implemented as a Krukal'"'"'s spanning tree.

17. The method of claim 10, wherein the trees of the forest do not intersect.

18. The method of claim 10, wherein the communication topology map is created by adding the cost of the links between a pair of trees with the cost of the links of the branches of the pair of trees to arrive at a total cost and creating a representation of a link directly between the roots of the pair of trees that has an associated cost equal to the total cost, so that there is no longer a need to represent the intermediary computers of each tree.

20. A computer-readable medium having stored thereon computer executable instructions for performing the method of claim 19.

21. The method of claim 19, wherein the common database is a directory service, and the replicating servers share a common partition within the directory service.

22. The method of claim 19, wherein the replicated changes are disseminated to all of the replicating computers, and wherein the intermediary computers do not replicate the changes.

23. The method of claim 19, wherein the determining step further comprises:

determining which paths enable replicated changes to be transmitted at the highest speed.

24. The method of claim 19, wherein the determining step further comprises:

determining which paths enable replicated changes to be transmitted at the lowest monetary cost.

25. The method of claim 19, wherein the network includes one or more bridges, the method further comprising repeating the grouping, determining, creating and designating steps for each of the one or more bridges.

26. The method of claim 19, wherein the network uses one or more schedules, the method further comprising repeating the grouping, determining, creating and designating steps for each of the one or more schedules.

27. The method of claim 19, wherein the network includes one or more transports, the method further comprising repeating the grouping, determining, creating and designating steps for each of the one or more transports.

19. A method for creating a replication topology for a network having replicating servers and intermediary servers, wherein the replicating servers share a common database and replicate changes to database to one another, the method comprising:

grouping each intermediary server with the replicating server with which it is least expensive to communicate, thereby creating a shortest-path tree;

determining the total cost of sending replicated changes between pairs of the replicating servers via their respective shortest-path trees;

creating a replication path cost map having only replicating servers, wherein each of the pairs of replicating servers is represented as being able to communicate by a direct link having a cost equal to the determined total cost; and

,

designating the least expensive, non-redundant paths on the cost map as the paths over which the replicating servers are to send replicated changes to one another.