Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-03-29
2004-07-13
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S400000
Reexamination Certificate
active
06762997
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of network communications. More specifically the invention relates to a methodology for determining transmission paths in a multi-path network
BACKGROUND OF THE INVENTION
In the operation of networked systems the expeditious routing of signals or data packets through the network is of significant importance. Typically, the shortest paths between a source and destination node are chosen as best candidates for data transmission. The shortest paths are generally considered the most expeditious and economical paths. Numerous methods and algorithms exist in the prior art to determine those network data links that comprise the shortest path between a source node and a destination node. The method of Dijkstra is the best known of these methods of determining shortest path. See, DIJKSTRA, E. W. “A NOTE ON TWO PROBLEMS IN CONNEXION WITH GRAPHS”, NUMBERISCHE MATHEMATIC 1, pp. 269-271 (1959). The method according to Dijkstra determines the shortest path from a source node to a destination node by blindly accumulating network link distances, or lengths, for each path between the source node and the destination node.
Dijkstra and other prior art methodologies determine a shortest path solely on length and these :routing determinations are referred to as unconstrained paths since system parameters that may affect data transmission throughput or delay are not considered. However, when other system parameters that influence data transmission are considered, the shortest path may be neither the most efficient path nor the most expeditious path to send data between a source node and destination node. For example, data paths using older transmission media may be less efficient than a longer data path using newer transmission media. The shorter data path may introduce significant time delays in the data transmission that adversely affect the timely reception of the data. The delay may be introduced, for example, because of buffering time at intermediate nodes, traffic density or data link bandwidth limitations. A longer path with a larger bandwidth may thus be a more efficient path for data transmission, as less delay may be introduced in the transmission.
Time delay in data transmission is extremely important for data transmission in a TCP/IP environment, such as the Internet. In this case, data transmissions occur in data packets that are distributed over a plurality of data paths. These data packets are known to arrive at different times because of different accumulated delays among the transmission paths. For the transmission of textual and static graphical data the different arrival times of such data is usually manifested as a slight delay in displaying the full image and/or text block, and generally constitute only an inconvenience to the user—i.e., there is no ultimate degradation in the received image or text due to such path delays. However, in the field of multi-media, such as video-conferencing or real-time imaging, where audio and visual data are transmitted simultaneously, the arrival of the audio significantly before or after the corresponding visual image destroys the synchronization between the visual image and corresponding audio. Accordingly, for an acceptable quality-of-service (QoS) in multi-media transmission the reception of audio and the associated visual data must occur within a known period. Thus, in transmission of multi-media data, the total delay along paths selected for data transmission must introduce substantially the same amount of delay to achieve an acceptable quality of service.
SUMMARY OF THE INVENTION
The present invention sets forth a methodology that determines data transmission paths between a source node and a destination node to satisfy system constraints imposed on data transmission in the selection of one or more transmission paths. In addition to a system constraint of path length or distance, system parameters, such as link delay and node delay, introduce constraints within the network that affect the selection of the data paths and the QoS of the network. The present invention determines the shortest delay routes or paths between a source and a destination using both distance and other selected system parameters that impose constraints upon the data transmission.
In accordance with the invention, candidate data paths that satisfy known system constraints are determined based on distance and other system parameters. The candidate path characteristics are developed with regard to the imposed constraints using a look-ahead feature that determines the path parameters of a candidate path by projecting the system parameters ahead to the destination node. The projected parameters are used to determine which paths potentially satisfy the imposed constraints. The candidate paths are then iteratively extended node by node through connecting nodes until a transmission path is determined that satisfies the imposed system constraints.
As illustrated in
FIG. 2
, processing blocks
230
-
310
define a loop in which a candidate path list is ordered on path-specific values of a system parameter. A second loop extends each candidate path by one hop. In this loop, defined by blocks
330
-
370
, each extended candidate path is tested to determine if it satisfies the imposed system constraint when the extended candidate path is projected to the destination node. If the extended candidate path satisfies the imposed system constraint, the extended path is placed among the candidate paths on the candidate list.
In one embodiment of the invention, candidate paths are removed from further consideration when the look-ahead feature indicates the projected path parameters of a candidate path exceed the imposed constraints. In this embodiment of the invention only paths that are potentially viable constrained shortest paths are subject to further evaluation.
REFERENCES:
patent: 5521910 (1996-05-01), Matthews
patent: 5596719 (1997-01-01), Ramakrishnan et al.
patent: 5600638 (1997-02-01), Bertin et al.
patent: 5649108 (1997-07-01), Spiegel et al.
patent: 6108702 (2000-08-01), Wood
patent: 6363319 (2002-03-01), Hsu
patent: 6377551 (2002-04-01), Luo et al.
The Network Working Group Request for Comments (RFC) 1058 document Routing Information Protocol, Jun. 1988.*
“A Note on Two Problems in Connexion with Graphs” by E.W. Dijkstra; Numberische Mathematic 1, pp. 269-271 (1959).
“The Traveling-Salesman Problem and Minimum Spanning Trees” by Michael Held and Richard M. Karp; Operations, Research 18, pp. 1139-1162 (1970).
“Network Flows—Theory, Algorithms, and Applications” by Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin; Addison-Wesldy Publishing Company, MA; 1998.
Liu Gang
Ramakrishnan Kajamalai G.
Kizou Hassan
Lucent Technologies - Inc.
Swickhamer Christopher M
LandOfFree
Method for finding shortest network routing paths subject to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for finding shortest network routing paths subject to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for finding shortest network routing paths subject to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207213