Method for designating communication paths in a network

• US 20050256879A1
• Filed: 01/26/2005
• Published: 11/17/2005
• Est. Priority Date: 02/28/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Harvey, Nicholas J.A., Lees, William B., Parham, Jeffrey B., Brown, Mark R., Vu, Van H., Vesztergombi, Katalin, Lovasz, Laszlo
• Granted Patent: US 7,499,413 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. One or more computer-readable media containing executable instructions that, when executed, implement the following steps:

creating one or more communication groups from a network having one or more recipient computers and one or more intermediary computers, each communication group including a recipient computer and one or more intermediary computers by grouping each intermediary computer with a recipient computer with which it is optimal for the intermediary computer to communicate;

designating each recipient computer not grouped with an intermediary computer as a communication group;

identifying one or more inter-group communication paths, each inter-group communication path connecting two or more groups;

creating a network representation having a plurality of primary communication paths in which the intermediary computers are replaced with the inter-group communication paths; and

determining optimal communication paths using the network representation.

2. The one or more computer-readable media of claim 1, wherein the grouping each intermediary computer with a recipient computer further comprises grouping a first intermediary computer with at least a second intermediary computer and a recipient computer.

3. The one or more computer-readable media of claim 1, wherein the grouping each intermediary computer with a recipient computer further comprises:

for each intermediary computer, determining which recipient computer of one or more recipient computers has a fastest intra-group communication path to the intermediary computer and grouping the intermediary computer with the recipient computer.

4. The one or more computer-readable media of claim 1, wherein the grouping each intermediary computer with a recipient computer further comprises:

for each intermediary computer, determining which recipient computer of one or more recipient computers has a shortest intra-group path, in terms of physical distance, to the intermediary computer and grouping the intermediary computer with the recipient computer.

5. The one or more computer-readable media of claim 1, wherein the grouping each intermediary computer with a recipient computer further comprises:

for each intermediary computer, determining which recipient computer of one or more recipient computers has a least expensive, in terms of monetary cost, intra-group communication path to the intermediary computer and grouping the intermediary computer with the recipient computer.

6. The one or more computer-readable media of claim 1, wherein the grouping each intermediary computer with a recipient computer further comprises:

for each intermediary computer, determining which recipient computer of one or more recipient computers has an intra-group communication path with the largest bandwidth to the intermediary computer and grouping the intermediary computer with the recipient computer.

7. The one or more computer-readable media of claim 1, wherein some of the recipient computers have read-only copies of data, and each other recipient computer has one or more writeable copies of the data, further comprising ensuring 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 only read-only copies of the data.

8. One or more computer-readable media containing executable instructions that, when executed, implement the following steps:

creating a replication topology for a network having replicating computers and intermediary computers, wherein the replicating computers share a common data store and replicate changes to the data store to other replicating computers, by grouping each intermediary computer with the replicating computer with which it is least expensive to communicate, thereby creating one or more shortest-path trees;

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

creating a replication path cost map having only replicating computers, wherein each of the pairs of replicating computers is represented as communicating by one or more direct links having a cost equal to the determined total cost; and

,

designating the least expensive, non-redundant paths on the cost map as paths over which the replicating computers can transmit replicated changes to one another.

9. The one or more computer-readable media of claim 8, wherein the common data store is a directory service.

10. The one or more computer-readable media of claim 9, wherein the replicating computers share a common partition within the directory service.

11. The one or more computer-readable media of claim 8, wherein the common data store is a file system.

12. The one or more computer-readable media of claim 8, wherein the common data store is an email message store.

13. The one or more computer-readable media of claim 8, wherein the replicated changes are disseminated to all of the replicating computers, and wherein the intermediary computers do not incorporate the changes.

14. The one or more computer-readable media of claim 8, wherein the network includes one or more bridges, the method further comprising repeating the creating a replication topology, determining, creating a replication cost map, and designating steps for each of the one or more bridges.

15. The one or more computer-readable media of claim 8, wherein the network uses one or more schedules, the method further comprising repeating the creating a replication topology, determining, creating a replication cost map, and designating steps for each of the one or more schedules.

16. A method, comprising:

creating one or more groups from a network of nodes and vertices, each group having one or more terminal nodes and zero or more intermediary nodes, each node linked to one or more other nodes by one or more vertices, by grouping each intermediary node with a terminal node such that transmission between the intermediary node and terminal node can be conducted in an optimal manner;

identifying one or more inter-group transmission paths, each inter-group transmission path connecting two or more groups;

creating a network representation having a plurality of transmission paths in which the intermediary nodes are replaced with the inter-group transmission paths; and

determining optimal transmission paths using the network representation.

17. The method of claim 16, wherein the transmission between the intermediary node and terminal node further comprises moving one or more physical objects, and wherein the inter-group transmission paths are paths over which one or more physical objects can be transmitted, and wherein the transmission paths are paths over which one or more physical objects can be transmitted.

18. The method of claim 16, wherein the one or more created groups include a single terminal node.

19. The method of claim 16, wherein the one or more created groups include a single terminal node and one or more intermediary nodes.

20. The method of claim 16, wherein the grouping each intermediary node with a terminal node further comprises grouping a first intermediary node with at least a second intermediary node and a terminal node.