Cell loss rate sensitive routing and call admission control method

• US 5,850,385 A
• Filed: 01/11/1995
• Issued: 12/15/1998
• Est. Priority Date: 09/24/1991
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Esaki, Hiroshi
• Primary Examiner(s): TON, DANG T
• Application Number:
  US08/371,514
• Time in Patent Office: 1,434 Days
• Field of Search: 370/16, 370/17, 370/94.1, 370/60, 370/94.3, 370/85.1, 370/85.6, 370/84, 370/216, 370/218, 370/227, 370/228, 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/237, 370/252, 370/395, 370/389, 370/401, 370/408, 370/351, 370/358, 370/356, 370/468, 371/11.1, 340/827, 340/825.5, 340/825.51, 340/825.52, 340/825.01, 340/825.02, 379/113, 379/221, 395/181
• US Class Current: 370/395.21
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A cell loss rate routing and a call admission control method and evaluation of ATM traffic. The two main communication qualities for connection oriented calls in an ATM network are the cell loss rate and the link delay. The purpose of routing control in an ATM network is to achieve high network throughput while guaranteeing both of these qualities. When high speed bursty calls are multiplexed in ATM fashion, the cell loss rate is more sensitive to offered load than the queuing delay. Usually, the cell loss rate grows large at lower offered load, even though the queuing delay is small. Moreover, the cell loss rate is determined not only by the offered load but also by other parameters, such as the burstiness and the percentage of high speed calls. Therefore, both the call admission control and the routing control methods in an ATM network are cell loss rate sensitive.

Claims

1. A method for routing offered traffic through an Asynchronous Transfer Mode (ATM) network comprising nodes wherein each node is adapted to communicate with each of the other nodes, said method comprising the step of generating sets of routes between source and destination node pairs wherein each route comprises at least one link interconnecting specific nodes, wherein each node comprises a multiplexer connecting each link incoming into a node to a multiplexed line which forms a link to another node, said method further comprising the steps of:

controlling the selection of traffic routes between said source and destination node pairs from the corresponding sets of routes by evaluating each of the routes in the corresponding sets of routes using a routing protocol in which cell loss rates of the sets of routes are used as matrix elements of a routing matrix in a routing protocol calculation;

dividing calls into priority calls and non-priority calls according to a preset criteria; and

performing a priority control to favor said priority calls over said non-priority calls such that priority calls are transferred before said non-priority calls,

wherein evaluating said cell loss rate comprises the steps of;

(a) determining a probability distribution function (G) for priority calls (p) and for non-priority (np) calls from ##EQU17## where .left brkt-bot. .right brkt-bot. is defined as an integer which is a smallest integer closest to the number within .left brkt-bot. .right brkt-bot. and is greater than the number within .left brkt-bot. .right brkt-bot. if the number within .left brkt-bot. .right brkt-bot. is not an integer, or, if the number within .left brkt-bot. .right brkt-bot. is an integer, then .left brkt-bot. .right brkt-bot. is defined as the number within .left brkt-bot. .right brkt-bot.,

M_T1 is the maximum number of cells that can be transferred to a multiplexed line during the time T₁,

T₁ is the inverse of the peak bit rate for the call whose peak bit rate is the maximum value among the non-priority calls,

V is the bit rate of the multiplexed line,

N_j is the number of calls of type j,

n_j is the number of activated calls of type j,

Vpj is the peak bit rate of the activated call j,

V_aj is the average bit rate of the activated call j,

P(k) is a probability density function for a packet arriving in a number k and where the peak bit rate for the calls is smaller than a predetermined value driven from a system parameter such as a speed of the multiplexed line,

Q_k is a probability density function for a packet arriving in the number of k from a certain type of call, and where the peak rate for the calls is greater than a predetermined value driven from the system parameter,

L is an integer equal to the number of types of calls that are multiplexed, and

where F(n) is evaluated when a new call is established through the recursive equation, ##EQU18## (b) evaluating the cell loss rate for priority calls from ##EQU19## and for non-priority calls from ##EQU20##

2. In an ATM network wherein calls comprising a plurality of cells are transferred along said network which includes a plurality of nodes interconnected by communication links, each node adapted to communicate with a plurality of other nodes, each node including a multiplexer for coupling incoming links to an outgoing multiplexed line, a method of call admission comprising the steps of:

1) dividing calls into priority calls and non-priority calls according to a preset criteria;

2) performing a call admission analysis to determine whether to accept or reject a call set-up request by evaluating a cell loss rate along candidate routes between a source and destination node so as to favor said priority calls over said non-priority calls such that priority calls are transferred before said non-priority calls;

3) said step of evaluating a cell loss rate for each candidate route comprises the steps of;

(a) determining a probability distribution function (G) for priority calls (p) and for non-priority (np) calls from ##EQU21## where .left brkt-bot. .right brkt-bot. is defined as an integer which is a smallest integer closest to the number within .left brkt-bot. .right brkt-bot. and is greater than the number within .left brkt-bot. .right brkt-bot. if the number within .left brkt-bot. .right brkt-bot. is not an integer, or, if the number within .left brkt-bot. .right brkt-bot. is an integer, then .left brkt-bot. .right brkt-bot. is defined as the number within .left brkt-bot. .right brkt-bot.,

M_T1 is the maximum number of cells that can be transferred to a multiplexed line during the time T₁,

T₁ is the inverse of the peak bit rate for the call whose peak bit rate is the maximum value among the non-priority calls,

V is the bit rate of the multiplexed line,

N_j is the number of calls of type j,

n_j is the number of activated calls of type j,

Vpj is the peak bit rate of the activated call j,

V_aj is the average bit rate of the activated call j,

P(k) is a probability density function for a packet arriving in a number k and where the peak bit rate for the calls is smaller than a predetermined value driven from a system parameter such as a speed of the multiplexed line,

Q_k is a probability density function for a packet arriving in the number of k from a certain type of call, and where the peak rate for the calls is greater than a predetermined value driven from the system parameter,

L is an integer equal to the number of types of calls that are multiplexed, and

where F(n) is evaluated when a new call is established through the recursive equation, ##EQU22## (b) evaluating the cell loss rate for priority calls from ##EQU23## and for non-priority calls from ##EQU24##

3. A method for routing offered traffic through a multi-stage switching Asynchronous Transfer Mode (ATM) network comprising input and output ports and a plurality of at least three switching stages interconnecting the input and output ports, the method including the steps of:

1) generating a set of candidate switching routes between a given input and output port pair;

2) selecting a traffic route between the given input and output port pair from the set of candidate routes by using a routing protocol in which cell loss rates for each candidate switching route are used as matrix elements of a routing matrix in a routing protocol calculation; and

3) routing the offered traffic through said multi-stage switching unit along the selected switching route,

wherein the step of evaluating the cell loss rate includes the steps of;

(a) determining a probability distribution function (G) for priority calls (p) and for non-priority (np) calls from ##EQU25## where .left brkt-bot. .right brkt-bot. is defined as an integer which is a smallest integer closest to the number within .left brkt-bot. .right brkt-bot. and is greater than the number within .left brkt-bot. .right brkt-bot. if the number within .left brkt-bot. .right brkt-bot. is not an integer, or, if the number within .left brkt-bot. .right brkt-bot. is an integer, then .left brkt-bot. .right brkt-bot. is defined as the number within .left brkt-bot. .right brkt-bot.,

M_T1 is the maximum number of cells that can be transferred to a multiplexed line during the time T₁,

T₁ is the inverse of the peak bit rate for the call whose peak bit rate is the maximum value among the non-priority calls,

V is the bit rate of the multiplexed line,

N_j is the number of calls of type j,

n_j is the number of activated calls of type j,

Vpj is the peak bit rate of the activated call j,

V_aj is the average bit rate of the activated call j,

P(k) is a probability density function for a packet arriving in a number k and where the peak bit rate for the calls is smaller than a predetermined value driven from a system parameter such as a speed of the multiplexed line,

Q_k is a probability density function for a packet arriving in the number of k from a certain type of call, and where the peak rate for the calls is greater than a predetermined value driven from the system parameter,

L is an integer equal to the number of types of calls that are multiplexed, and

where F(n) is evaluated when a new call is established through the recursive equation, ##EQU26## (b) evaluating the cell loss rate for priority calls from ##EQU27## and for non-priority calls from ##EQU28##

4. A method for routing offered traffic through an Asynchronous Transfer Mode (ATM) network comprising nodes wherein each node is adapted to communicate with each of the other nodes and comprises a multiplexer connecting each link incoming into a node to a multiplexed line which forms a link to another node, the method comprising the steps of:

generating sets of routes between source and destination node pairs wherein each route comprises at least one link interconnecting specific nodes;

controlling the selection of traffic routes between said source and destination node pairs from the corresponding sets of routes by evaluating the routes with respect to cell loss rates of the sets;

dividing calls into priority calls and non-priority calls according to a preset criteria; and

performing a priority control to favor the priority calls over the non-priority calls such that the priority calls are transferred before the non-priority calls;

wherein the cell loss rates are obtained by;

(a) determining a probability distribution function indicating a probability for a given number of cells to be transferred from multiplexed calls during a prescribed time, for each class of the priority calls and the non-priority calls; and

(b) calculating the cell loss rate for each class of the priority calls and the non-priority calls from the probability distribution function for each class of the priority calls and the non-priority calls, and

wherein the step (a) determines the probability distribution functions by;

(a1) dividing calls into high speed calls and low speed calls according to peak bit rates of calls;

(a2) calculating a first probability for a given number of cells to be transferred from high speed calls during a prescribed time, and a second probability for a given number of cells to be transferred from low speed calls during a prescribed time, for each class of the priority calls and the non-priority calls; and

(a3) calculating a convolution of the first probability and the second probability for each class of the priority calls and the non-priority calls to obtain the probability distribution function for each class of the priority calls and the non-priority calls.

5. A method for routing offered traffic through a multi-stage switching Asynchronous Transfer Mode (ATM) network comprising input and output ports and a plurality of at least three switching stages interconnecting the input and output ports, the method comprising the steps of:

generating a set of candidate switching routes between a given input and output port pair;

evaluating the selection of the traffic route between the given input and output port pair from the set of candidate routes in response to cell loss rates for each candidate route;

routing offered traffic through said multi-stage switching unit along the selected candidate route;

dividing calls into priority calls and non-priority calls according to a preset criteria; and

performing a priority control to favor the priority calls over the non-priority calls such that the priority calls are transferred before the non-priority calls;

wherein the cell loss rates are obtained by;

(a) determining a probability distribution function indicating a probability for a given number of cells to be transferred from multiplexed calls during a prescribed time, for each class of the priority calls and the non-priority calls; and

(b) calculating the cell loss rate for each class of the priority calls and the non-priority calls from the probability distribution function for each class of the priority calls and the non-priority calls, and

wherein the step (a) determines the probability distribution functions by;

(a1) dividing calls into high speed calls and low speed calls according to peak bit rates of calls;

(a2) calculating a first probability for a given number of cells to be transferred from high speed calls during a prescribed time, and a second probability for a given number of cells to be transferred from low speed calls during a prescribed time, for each class of the priority calls and the non-priority calls; and

(a3) calculating a convolution of the first probability and the second probability for each class of the priority calls and the non-priority calls to obtain the probability distribution function for each class of the priority calls and the non-priority calls.

6. A method of call admission control in an Asynchronous Transfer Mode (ATM) network wherein calls comprising a plurality of cells are transferred along the network which includes a plurality of nodes interconnected by communication links, wherein each node is adapted to communicate with a plurality of other nodes and including a multiplexer for coupling incoming links to an outgoing multiplexed line, the method comprising the steps of:

dividing calls into priority calls and non-priority calls according to a preset criteria; and

performing a call admission control to determine whether to accept or reject a call set-up request by evaluating cell loss rates along candidate routes between source and destination nodes so as to favor the priority calls over the non-priority calls such that the priority calls are transferred before the non-priority calls;

wherein the cell loss rates are obtained by;

(a) determining a probability distribution function indicating a probability for a given number of cells to be transferred from multiplexed calls during a prescribed time, for each class of the priority calls and the non-priority calls; and

(b) calculating the cell loss rate for each class of the priority calls and the non-priority calls from the probability distribution function for each class of the priority calls and the non-priority calls, and

wherein the step (a) determines the probability distribution functions by;

(a1) dividing calls into high speed calls and low speed calls according to peak bit rates of calls;

(a2) calculating a first probability for a given number of cells to be transferred from high speed calls during a prescribed time, and a second probability for a given number of cells to be transferred from low speed calls during a prescribed time, for each class of the priority calls and the non-priority calls; and

(a3) calculating a convolution of the first probability and the second probability for each class of the priority calls and the non-priority calls to obtain the probability distribution function for each class of the priority calls and the non-priority calls.