Method for designating communication paths in a network

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.

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.