Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1998-08-20
2002-04-23
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
C370S235000, C370S413000
Reexamination Certificate
active
06377544
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to distributed networks, and more particularly to optimizing flow through a local-control network.
BACKGROUND OF THE INVENTION
One of the primary goals of any communications system is to be able to optimize the flow of information through the system. Typically, a communication system may include a network of communication nodes through which data packets are transferred from a source node to a destination node. In order to be able to accomplish the above-stated goal, it is necessary to develop a methodology which determines the optimal routing of information through a network.
In the prior art, those who sought to determine the optimal flow of information through a communication system utilized flow theory directed to determining the maximum flow of any type of commodity through a distributed network. In a typical communication network, commodities are various data types such as text, voice, video graphics, etc., routed from a source node to a sink or destination node. A source node is a point within the distributed network at which some commodity originally exists. A sink node is another point within the network at which the same commodity is desired to be routed to. A distributed network may have many nodes, located within such network and configured such that a commodity must be routed through a number of these nodes in order to travel from the source node to the sink node.
FIG. 1
illustrates a part of a sample network, showing source node
10
, which transfers data
60
to sink node
110
across edge
50
a
. Data divider
30
operates to divide data within the queues of source node
10
, the purpose and method of which will be discussed in detail later. Queues
20
,
20
a
and
120
of source node
10
and sink node
110
, respectively, are memory spaces which store the data prior to transfer from one node to the other.
Each edge
50
has two queues connected to it—one at each end of the edge. Thus, an edge which connects one node and a neighboring node has one queue in the first node and the other queue in the second node.
FIG. 1
shows edge
50
a
with two queues connected to it, namely queue
20
a
and queue
120
. The other edges
50
are shown connected to the other queues
20
in source node
10
. Though not shown, the other end of each of the other edges
50
is connected to a queue of a neighboring node. It should also be noted that in this figure, the source node and the sink node are situated adjacent to each other, such that they are not seperated from each other by several other nodes (as would be the case in the typical network flow problem), and are thus meant only to illustrate some of the features of a typical node within a distributed network.
FIG. 2
, which will be explained more fully later, illustrates a mesh graph, having 14 nodes (of the type of node illustrated in
FIG. 1
) and 3 levels. This graph represents just one way in which a distributed network can be configured, although it is understood that there are countless other possible configurations. In particular, a mesh graph may be representative of an asynchronous transfer mode (hereinafter “ATM”) network, in which commodities such as audio or video data are routed by switches through the ATM network across connections having pre-determined bandwidth. In this figure, the numbered circles are communication nodes, such as those employed in a computer communication network. As shown, the nodes are connected by arrows. The arrows show the manner in which the computer terminals are connected to each other and the directions in which they can transfer data through the network. Thus, for example, if a person using the computer terminal designated as node
14
desires data from a host computer terminal designated as node
1
, the arrows represent the possible paths for the data to be transmitted from node
1
to node
14
. In this example, the data is the commodity sought.
Alternatively, the communications system illustrated in
FIG. 2
could also be representative of a fiber optic telephone network, in which each node is representative of a call switching station and each arrow is representative of a fiber optic cable over which a telephone call or data transmission may be sent. In this manner, a call (the commodity in this example), could be made from a telephone designated by node
1
(the “source” node) to a telephone designated by node
14
(the “sink” node), and that call could be routed through the fiber optic network in any manner shown by the arrows.
FIG. 3
is provided to illustrate a sample of an RMF graph. The sample graph is a 3×3×2 RMF graph, showing another way in which a distributed network can be configured. As in the ATM network, the numbered circles represent nodes and the arrows represent edges over which desired information may be routed. Of course, it is understood that
FIGS. 2 and 3
describe just two of many types and configurations of communications systems which could exist, and that a communication system is just one type of network which routes commodities between routing nodes.
Referring back to the prior art which sought to determine optimal flows through a network, in addition to a source node and a sink node, each commodity also has an associated demand, which is the amount of that commodity that must be transmitted from its source to its sink. When only one type of commodity exists in a distributed network, a problem called the max flow problem exists. The max flow problem is the question of how to maximize a feasible flow, of a single type of commodity, through a network from a source to a sink. A flow is feasible if the transfer rate satisfies the demand for the commodity while remaining within the network's capacity constraints.
The network's capacity constraints are expressed through constraints placed on the edges of the network. An edge, as shown and described previously, is the connection between two neighboring nodes over which an amount of commodity can be transferred. Thus, in the max flow problem, it is desired to find the maximum flow of the single commodity through the network that does not exceed the capacities of the edges. Referring to the examples of communications systems discussed above, the capacity of the edges of a computer or internet system may be the bandwidth or data transfer capabilities of the connections, while the capacity of the edges of the fiber optic system may be the number of optical strands in a fiber optics trunk cable, and total channel bandwidth between two nodes.
The prior art also considered multicommodity flow. Multicommodity flow is an arrangement wherein a network simultaneously transmits multiple types of commodities through a network such that the total amount of flow on each edge is no more than the flow capacity of the edge. Multicommodity flow arises in a wide variety of contexts, such as product distribution, traffic planning and scheduling problems, but particularly in packet-routing and communications systems, such as networks that route data, voice, audio, video graphics, etc.
An additional consideration for those seeking to optimize flow through a communication system is the problem presented by each node's inability to monitor the flow at every other point in the network. Particularly, in packet-routing and communications systems employing a distributed network, it is typically necessary for each node of the network to be locally-controlled. A locally-controlled network is one in which each node communicates only with neighboring nodes and has no global knowledge of the network. Packet-routing and communications systems are typically locally-controlled, since it is impractical for each node of a packet-routing or communications network to have knowledge of the existing flow conditions between every node pair within the network. It is practical, however, for each node of a network to have knowledge of the existing flow conditions between itself and adjacent or neighboring nodes. Thus, local-control algorithms for analyzing multicom
Muthukrishnan Shanmugavelayut
Suel Torsten
Chin Wellington
Lucent Technologies - Inc.
Sofer & Haroun
Tran Maikhanh
LandOfFree
System and method for increasing the speed of distributed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for increasing the speed of distributed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for increasing the speed of distributed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2910981