Quality of service based path selection for connection-oriented networks
OwnerDeepak Kataria, Dimitris Logothetis +2inventors
InventorsDeepak Kataria, Dimitris Logothetis, Santhanam Srinivasan, Malathi Veeraraghavan
Life of this patent
Estimating the term…
Abstract
Arrangements and methods for improving the probability of finding a connection path that meets user specified delay requirements. The improvements offer packet switches enhanced path selection that will improve the resource utilization of networks, both flat networks and hierarchical networks incorporating such switches. The latter type of networks run the path selection algorithm in the PNNI v1.0 standard where the packet switches are asynchronous transfer mode switches. Two modes of enhanced delay-based path selection are based on two different accumulation methods, namely an additive method and an asymptotic method.
Claims21
A method for use in a communication network including a plurality of network terminal nodes and a plurality of packet switches, comprising the steps of:
- determining topology of the network, link weights, and delay-related parameters;
- and
- providing from a first one of said plurality of network terminal nodes to a second one of said plurality of network terminal nodes at least one delay-based shortest transmission path via at least one of said plurality of packet witches, including the step of selecting said path on the basis of a particular delay-related parameter, and including precomputing a multiplicity of sets of shortest paths, wherein the step of providing at least one delay-based transmission path includes the step of employing a restricted shortest path algorithm, further including the step of precomputing possible delay-based transmission paths in advance of cell call set up request.
A method for use in a communication network including a plurality of network terminal nodes and a plurality of packet switches, comprising the steps of:
- determining topology of the network, link weights, and delay-related parameters;
- and
- providing from a first one of said plurality of network terminal nodes to a second one of said plurality of network terminal nodes at least one delay-based shortest transmission path via at least one of said plurality of packet switches, including the step of selecting said path on the basis of a particular delay-related parameter, and including precomputing a multiplicity of sets of shortest paths,
- wherein the step of providing at least one delay-based transmission path includes the step of employing a restricted shortest path algorithm,
- wherein the step of employing restricted shortest path algorithm comprises employing an asymptotic-type restricted shortest path algorithm,
- wherein the step of employing an asymptotic-type restricted shortest path algorithm comprises the steps of:
- defining lij and tij to be the AW and CDV of the link that connects nodes i and j, respectively, letting L be an upper bound on the end-to-end delay of any path in the network, letting gi(l), μi(l), σi2(l) and di(l) be the CDV, the cumulative mean of the delay, the cumulative variance of the delay and the discrepancy of the delay of a shortest path from node 1 to node i with AW at most 1;
- i nitializing g i ( l ) = 0 l = 0 , ⋯ , L ;
- i nitializing g j ( 0 ) = ∞ j = 2 , ⋯ , N ;
- i nitializing μ i ( l ) = μ j ( l ) = σ i 2 ( l ) = d j ( l ) = 0 , 1 = 0 , ⋯ , L , j = 2 , ⋯ , N , l = 1 , ⋯ , L ,
- where
- gk{circle around (X)}tkjμk(l−lkj)+μkj+[{square root over (σk2)}(l−lkj)+σkj2]×t(α)+max{dk(l−lkj),dkj(α)};
- and is defined as:
- checking whether the at least one delay-based transmission path exists with delay not greater than gi(l).
A method for use in a communication network including a plurality of network terminal nodes and a plurality of packet switches, comprising the steps of:
- determining topology of the network, link weights, and delay-related parameters;
- and
- providing from a first one of said plurality of network terminal nodes to a second one of said plurality of network terminal nodes at least one delay-based shortest transmission path via at least one of said plurality of packet switches, including the step of selecting said path on the basis of a particular delay-related parameter, and including precomputing a multiplicity of sets of shortest paths, wherein the step of providing at least one delay-based transmission path includes the step of employing a restricted shortest path algorithm,
- wherein the providing step, in response to a call setup request, computes on-the-fly a suitable delay-based transmission path.
A method for use in a communication network including a plurality of network terminal nodes and a plurality of packet switches, comprising the steps of:
- determining topology of the network, link weights, and delay-related parameters;
- and
- providing from a first one of said plurality of network terminal nodes to a second one of said plurality of network terminal nodes at least one delay-based shortest transmission path via at least one of said plurality of packet switches, including the step of selecting said path on the basis of a particular delay-related parameter, and including precomputing a multiplicity of sets of shortest paths, wherein the step of providing at least one delay-based transmission path includes the step of employing a restricted shortest path algorithm,
- wherein the providing step, in response to a call setup request, computes on-the-fly a suitable delay-based transmission path, and
- wherein the step of employing an asymptotic-type restricted shortest path algorithm comprises the steps of:
- defining lij and tij to be the AW and CDV of the link that connects nodes i and j, respectively;
- letting L be an upper bound on the end-to-end delay of any path in the network;
- letting gi(l), μi(l), σi2(l) and di(l) be the CDV, the cumulative mean of the delay, the cumulative variance of the delay and the discrepancy of the delay of a shortest path from node 1 to node i with AW at most 1;
- i nitializing g i ( l ) = 0 l = 0 , ⋯ , L ;
- i nitializing g i ( 0 ) = ∞ j = 2 , ⋯ , N ;
- i nitializing μ i ( l ) = μ j ( l ) = σ i 2 ( l ) = d j ( l ) = 0 , 1 = 0 , ⋯ , L , j = 2 , ⋯ , N , l = 1 , ⋯ , L ,
- where
- gk⊕tkjμk(l−lkj)+μkj+[{square root over (σk2)}(l−lkj)+σkj2]×t(α)+max{dk(1−lkj),dkj(α)};
- and is defined as:
- checking whether the at least one delay-based transmission path exists with delay not greater than gi(l).
Dependencies are inferred from the claim text.