Quality of service based path selection for connection-oriented networks

A communication system, comprising:

• a network having a topology including a plurality of communication links and a plurality of packet switches;
• data processing apparatus for accessing stored values of the topology of the network and delay-related and length-related parameters for sets of links between switches including the plurality of packet switches;
• and
• apparatus for providing a delay-based shortest-path connection between two or more users, including means for testing various ones of the sets of links for the connection, said testing means including a central processing unit adapted to include routines to provide to a user a connection to one or more destinations satisfying a quality of service QoS that the user has specified, wherein the user has specified a delay threshold T of a particular delay-related parameter and has also specified a delay threshold tolerance within which the delay threshold T is to be met.

A communication system, comprising:

• a network having a topology including a plurality of communication links and a plurality of packet switches;
• means for accessing stored values of the topology of the network and delay-related and length-related parameters for sets of links between switches including the plurality of packet switches;
• and
• means for providing a delay-based shortest-path connection from a user to one or more destinations, the user having specified both a delay threshold T and a delay tolerance ε, including means for testing various ones of the sets of links for the connection, said testing means including a central processing unit adapted to include routines including a dynamic programming routine for finding said connection and an iterative routine for scaling the delay threshold T and the delay measures on links, starting with a small initial value of scaling factor τ and increasing the scaling factor at each iteration, computing the shortest path length using the dynamic programming algorithm, accumulating the scaled length delays in that shortest path, until the dynamic programming algorithm finds a path that satisfies the user-specified delay threshold T within the user-specified delay tolerance ε or, when no further increase of τ is available, finds that no path exists that satisfies the delay threshold T within the delay tolerance ε.

A communication system, comprising:

• a network having a topology including a plurality of communication links and a plurality of packet switches;
• means for accessing stored values of the topology of the network and delay-related and length-related parameters for sets of links between switches including the plurality of packet switches;
• and
• means for providing a delay-based shortest-path connection from a user to one or more destinations via at least one of the plurality of packet switches, including means for testing various ones of the sets of links for the connection, said testing means including a central processing unit adapted to include routines to scale the delay threshold T to a value τ, appropriately chosen to ensure delays for a maximum number of links in a shortest-path connection will accumulate to less than the user-specified delay threshold within the user-specified tolerance, correspondingly scaling a delay parameter on each link, and then truncating all the scaled values to integers, computing the shortest length path by using a dynamic programming algorithm;
• and accumulating the scaled link delays for a connection using the just-computed shortest path.