Method for designating communication paths in a network
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
27 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
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.
-
Specification