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
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. xe2x80x9cA NOTE ON TWO PROBLEMS IN CONNEXION WITH GRAPHSxe2x80x9d, 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 userxe2x80x94i.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.
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.