Call setup control apparatus in ATM switch

[0002] The present invention relates to a call setup control apparatus equipped in an ATM (Asynchronous Transfer Mode) switch capable of providing a plurality of services with different QoS (Quality of Service) requirements.

[0003] In ATM networks, priority control and CAC (Call Admission Control) are indispensable traffic management methods to guarantee QOS requirements for different types of traffic, such as voice, video and data. In addition, recent various demands for communication make difficult to previously calculate required bandwidths in the networks which will satisfy the QoS requirements by estimating cell traffic characteristics of the ATM connections of each type in each priority class.

[0004] In order to flexibly respond to the various demands for communication and to effectively utilize network resource, it is necessary to correctly grasp the amount of current resource depending upon connection state for calls and to evaluate whether a fresh call is acceptable or not. However, according to the conventional priority control method, influences of higher priority calls over QoS requirements of lower priority calls are not sufficiently considered for providing a plurality of services with the different QOS requirements. Thus, it is impossible to precisely estimate current bandwidth and required bandwidth for accepting a fresh call.

[0005] It is therefore an object of the present invention to provide a call setup control apparatus equipped in an ATM switch, whereby the amount of bandwidth occupied by a plurality of calls with different QoS requirements can be correctly grasped and whether a fresh call is acceptable or not can be suitably evaluated.

[0006] The present invention concerns a call setup control apparatus, equipped in an ATM switch with a plurality of buffers for respective priority classes of calls, for providing priority control of calls of a plurality of types with different quality of service requirements. Particularly, according to the present invention, the apparatus has a first calculation unit for calculating an objective value of cell loss ratio P_B(u) of a buffer B_uin priority class u which is equal to or lower than a priority class k (u=k to K), based upon parameters of an average cell rate R(k,j), an objective value of cell loss ratio Q(k,j), and the number of calls N(k,j) for calls of each type j (j=1 to J_k) in each class k (=1 to K), with considering a cell rate of calls in priority class which is higher than the class k (class 1 to k−1), when a fresh call is arrived, a unit for obtaining a bandwidth α(k,u,j) required for calls of type j in class k in the buffer B_uto make a cell loss ratio in the buffer B_uto be equal to or less than the objective value P_B(u), a second calculation unit for calculating a required bandwidth C(u) for the buffer B_u, based upon the obtained bandwidth α(k,u,j), and a unit for judging whether the fresh call is acceptable or not by comparing the calculated bandwidth C(u) with a link capacity C_p.

[0007] It is preferred that the first calculation unit includes a third calculation unit for calculating a summation S(k) of the average cell rates R(k,j) of all types 1 to J_k(j=1 to J_k) class k (k=1 to K), based upon the parameters of the average cell rates R(k,j) and the number of calls N(k,j), and a determination unit for determining an objective value of cell loss ratio P_Q(k) for calls in the class k to one with the minimum value among the objective value of cell loss ratio Q(k,j) of the type j in the class k, and wherein the objective value of cell loss ratio P_B(u) of class k buffer is calculated in accordance with the summation S(k) of the average cell rates and the objective value of cell loss ratio P_Q(k) for calls in the class k.

[0008] The summation S(k) of the average cell rates may be calculated from $\begin{array}{cc}S\left(k\right)=\sum _{j=1}^{J_k}N\left(k,j\right)R\left(k,j\right).& \text{Equation (2)}\end{array}$

[0009] The objective value of cell loss ratio P_Q(k) for calls in the class k may be calculated from $\begin{array}{cc}{P}_Q\left(k\right)=\underset{j}{\min }\left\{Q\left(k,j\right)\right\}.& \text{Equation (1)}\end{array}$

[0010] The objective value of cell loss ratio P_B(u) may be calculated from $\begin{array}{cc}{P}_B\left(u\right)=\frac{S\left(u\right)}{\sum _{i=1}^{u}S\left(i\right)}{P}_Q\left(u\right)\left[u=k,\dots ,K\right].& \text{Equation (3)}\end{array}$

[0011] The required bandwidth C(u) for the buffer B_umay be calculated from $\begin{array}{cc}C\left(u\right)=\sum _{i=1}^u\sum _{j=1}^{J_i}N\left(i,j\right)\alpha \left(i,u,j\right).& \text{Equation (4)}\end{array}$

[0012] It is also preferred that the apparatus further has control parameter tables for storing the average cell rate R(k,j), the objective value of cell loss ratio Q(k,j), and the number of calls N(k,j) for calls of each type j in each class k, the objective value of cell loss ratio P_Q(k) for calls in the class k, the summation S(k) of the average cell rates R(k,j) in all classes, the objective value of cell loss ratio P_B(u) of the buffer B_u, the bandwidth α(k,u,j) required for calls of type j in class k in the buffer B_u, and the required bandwidth C(u) for the buffer B_u.

[0013] The call setup control apparatus of the present invention calculates a required bandwidth for satisfying QoS requirements with respect to calls under priority control by using an effective bandwidth method described in for example F. P. Kelly, “Effective bandwidth at multi-class queues”, Queuing Syst. 9, pp.5-15, 1991 so as to enable an optimum call acceptance check for an arbitrary combination of priority of calls, call type and the number of calls in progress.

[0014] Further objects and advantages of the present invention will be apparent from the following description of the preferred embodiments of the invention as illustrated in the accompanying drawings.

[0015] FIG. 1 illustrates a model of a buffer configuration in an ATM switch according to the present invention;

[0016] FIG. 2 illustrates behavior of a processor with priority control in the buffer configuration shown in FIG. 1;

[0017] FIG. 3 illustrates the number of cells in a buffer B₂with a priority class 2 in the buffer configuration shown in FIG. 1;

[0018] FIG. 4 illustrates a model for probability density function of the number of cells in the buffer B₂in the buffer configuration shown in FIG. 1;

[0019] FIG. 5 illustrates a model for probability density function of the number of cells in a buffer B_Kwith a priority class k in the buffer configuration shown in FIG. 1;

[0020] FIG. 6 illustrates a model for the estimation of required bandwidth;

[0021] FIG. 7 shows a block diagram schematically illustrating a preferred embodiment according to the present invention;

[0022] FIG. 8, constituted by combining FIGS. 8A and 8B, illustrates functions of a call admission control unit and control parameter tables in the embodiment shown in FIG. 7;

[0023] FIG. 9, constituted by combining FIGS. 9A and 9B, shows a flow chart for checking whether a fresh call is acceptable or not at each time of call arrival;

[0024] FIG. 10 shows a flow chart for previously calculating the number of acceptable calls at designing;

[0025] FIG. 11 illustrates call admission control of a fresh call with class 3 in a model with class 1 to 5 buffers; and

[0026] FIG. 12 shows a graph illustrating required bandwidth with varying the capacity of class 2 buffer B₂.

[0027] Before describing the preferred embodiments of the present invention, basic concept of the invention will be explained with reference to FIGS. 1 to 6.

[0028] First, it is described with respect to a priority control queue model. FIG. 1 illustrates a model of a buffer (queue) configuration of an ATM switch with priority control. In the figure, C_pdenotes a bandwidth (capacity) of an output link connected with a processor and thus is equal to the service rate of the processor, B₁-B_Kdenote buffers with the respective cell loss priority classes, and S₁-S_Kdenote calls with the respective cell loss priority classes. In this example, the number of the buffers which share the processor is K. In other words, the ATM switch accommodates K different kinds of connection groups with corresponding K cell loss priority classes. A connection group with cell loss class k (k=1,2, . . . , K) is called class k connection according to the QoS requirement in term of cell loss ratio. The smaller the class number implies the higher the priority. Thus, the class 1 connection has the highest priority to be served by the processor, whereas the class K connection has the lowest priority in the connection groups. The service discipline of the processor is first-in-first-out with non-preemptive priority control, and thus the high priority buffer is served whenever it is non-empty. A cell stored in class k buffer B_kwill be served only when there is no cell in the buffers B₁to B_k−1of class 1,2, . . . , k−1. If there is no cell in all the buffers, the processor sends an invalid cell to the link.

[0029] FIG. 2 illustrates behavior of the processor for an example of two-priority case. It is assumed that a cell comes into the high priority class (class 1) buffer B₁while the low priority class (class 2) buffer B₂is not empty. According to the priority control discipline, the processor begins to serve the high priority buffer B₁and cells in the low priority buffer B₂stay in their buffer B₂until the high priority buffer B₁is served and becomes empty. From the view point of the number of cells stored in the low priority buffer B₂, a cell arrival to the high priority buffer B₁is equivalent to a situation that the low priority buffer B₂is served by the processor while a cell comes into the low priority buffer B₂as shown in FIG. 3. Therefore, in order to estimate the distribution of the number of cells in the low priority buffer B₂, the prioritized parallel queue model shown in FIG. 2 can be transformed into the non-prioritized tandem queue model shown in FIG. 4. This transformation of queuing models can be recursively applied from the top priority buffer B₁to a class k buffer B_kand it results in the tandem queuing model shown in FIG. 5. It should be noted that each buffer is a push-out buffer such that overflowed cells in class k buffer B_kare cells which come from class k sources.

[0030] Next, calculation of bandwidth required for accommodating each ATM connection is described. The required service rate C_kof class k buffer B_kis defined as the service rate to make cell loss ratio in the buffer B_kbe less than or equal to an objective value of cell loss ratio P_B(k) in the buffer B_k. A major problem in estimation of C_kis how to handle the traffic characteristics of the output stream from the buffer B_k−1. For precise analysis of this traffic, a sophisticated method will be needed to take account traffic inference in upstream buffers in tandem. However, the present invention adopts a single queue model shown in FIG. 6, obtained by simplifying the tandem queue model shown in FIG. 5, in which calls of type j in class k are directly applied to the buffer B_k, in other words the output stream of the buffer B_k−1is approximated to be aggregated streams of class 1 to k−1 calls. This model has a great advantage of simplicity in the calculation of required bandwidth because it can directly use the effective bandwidth method.

[0031] It should be noted that the present invention adopts the above-mentioned concept to the call setup control apparatus equipped in the ATM switch for providing a plurality of services with different QoS requirements.

[0032] FIG. 7 schematically illustrates a preferred embodiment of the ATM switch according to the present invention.

[0033] In the figure, reference numerals 10 and 14 denote port interfaces, 11 denotes a cell switch, 12 denotes buffers for respective priorities, 13 denotes a cell multiplexer with priority control, and 15 denotes a connection control apparatus. The connection control apparatus 15 has a connection control unit 16, a routing control unit 17 for executing typical traffic control, i.e. priority control and route control of calls, control parameter tables 18, and a call admission control unit 19 for evaluating whether a fresh call is admitted or not by using the control parameter tables 18.

[0034] FIG. 8 illustrates functions of the call admission control unit 19 in the left side and the control parameter tables 18 in the right side.

[0035] A traffic contract parameter table stores information of service in each class k (k=1 to k) and call type j (j=1 to j_k), average cell rate R(k,j) of each type j in each class k, and the objective value of cell loss ratio Q(k,j) of each type j in each class k as shown in following Tables 1 to 3, respectively.

[0036] A table for the number of calls stores the number of calls N(k,j) of each type j in each class k as shown in Table 4.

[0037] A buffer capacity table stores capacity or size B(k) of the buffer B_kas shown in table 5.

[0038] A buffer cell loss ratio (design value) table stores the design value of cell loss ratio P_Q(k) with respect to calls using the buffer B_Kas shown in table 6. This P_Q(k) is expressed by the following equation (1). $\begin{array}{cc}{P}_Q\left(k\right)=\underset{j}{\min }\left\{Q\left(k,j\right)\right\}& \text{Equation (1)}\end{array}$

[0039] A summed average cell rate table stores the summation of the average value of cell rate S(k) in class k as shown in Table 7. This S(k) is expressed by the following equation (1). $\begin{array}{cc}S\left(k\right)=\sum _{j=1}^{J_k}N\left(k,j\right)R\left(k,j\right)& \text{Equation (2)}\end{array}$

[0040] A buffer cell loss ratio (objective value) table stores the objective value of cell loss ratio P_B(k) with respect to calls using the buffer B_kas shown in Table 8. This P_B(k) is expressed by the following equation (3). $\begin{array}{cc}{P}_B\left(u\right)=\frac{S\left(u\right)}{\sum _{i=1}^{u}S\left(i\right)}{P}_Q\left(u\right)\left[u=k,\dots ,K\right]& \text{Equation (3)}\end{array}$

[0041] A call-required bandwidth table stores the bandwidth α(k,u,j) required for call of type j in class k in buffer B_uas shown in Table 9.

[0042] A buffer-required bandwidth table stores the bandwidth C(u) totally required by the buffer B_uas shown in table 10. This C(u) is expressed by the following equation (4). $\begin{array}{cc}C\left(u\right)=\sum _{i=1}^u\sum _{j=1}^{J_i}N\left(i,j\right)\alpha \left(i,u,j\right)& \text{Equation (4)}\end{array}$

[0043] The call admission control unit 19 has a class and type determination function for determining priority class k and type j of call, a traffic contract parameter management function for registering and managing traffic contract parameters R(k,j) and Q(k,j) which share calls of class k and type j, and P_Q(k), a summed average cell rate calculation function for calculating the summation of the average cell rate S(k), a buffer cell loss ratio calculation function for calculating the objective value of the buffer cell loss ratio P_B(k), a required bandwidth evaluation function for obtaining the call-required bandwidth α(k,u,j), a required bandwidth calculation function for calculating the buffer-required bandwidth C(u), a bandwidth assignment function for assigning the bandwidth for the call, and a message transmission function for notifying whether a call is acceptable or not to another switch.

[0044] There are two call admission control schemes. One is that the maximum number of calls is not predetermined. In this scheme, the required service rate of each buffer is calculated at each time of a fresh call arrival to check whether the fresh call is acceptable or not. The other one is that the maximum number of calls is preliminarily designed. In the latter scheme, call admission control is done in such a way that a fresh call is accepted if the number of calls in progress is less than or equal to the designed maximum number otherwise the fresh call is rejected.

[0045] FIG. 9 shows a flow chart of the call admission control, in accordance with the former scheme, to check whether a fresh call is acceptable or not at each time of call arrival.

[0046] When a fresh call is arrived, priority class k (k=1 to K) and call type j (j=1 to J_K) of the call is first determined by using the class and type determination function. Thus, the average cell rate R(k,j), the objective value of cell loss ratio Q(k,j) and the number of calls N(k,j) which are traffic contract parameters and share calls of type j in class k, and the design value of cell loss ratio P_Q(k) which will be calculated from the equation (1) are determined.

[0047] Then, a summation of average cell rate S(k) of calls in the class k buffer B_kis calculated by the average cell rate calculation function. This S(k) is calculated from the equation (2) by using as parameters R(k,j) in the traffic contract parameter table and N(k,j) stored in the call number table. The calculated S(k) is stored in the average cell rate table.

[0048] Then, the looped steps with respect to calls of classes u (=k to K) are executed to check whether the calls are acceptable or not.

[0049] In the looped steps, first, the objective values of cell loss ratio P_B(u) with respect to all the buffer B_kto B_K(u=k to K) are calculated by the buffer cell loss ratio calculation function. These P_B(u) values are calculated from the equation (3) by using as parameters S(u) stored in the summed average cell rate table and P_Q(u) stored in the buffer cell loss ratio (design value) table. The calculated P_B(u) is stored in the buffer cell loss ratio (objective value) table.

[0050] Then, the call-required bandwidth α(k,u,j) is evaluated by the required bandwidth evaluation function. At this step, obtained Is the call-required bandwidth α(k,u,j), where k=1 to K, u=k to K, J=1 to J_k, required for calls with class k and call type j in each class u (u=k to K) buffer B_uin order that the cell loss ratio in the class u (u=k to K) buffer B_uis equal to or less than the objective value P_B(u). The obtained call-required bandwidth α(k,u,j) is stored in the call-required bandwidth table.

[0051] Then, the bandwidth C(u) totally required by the buffer B_uis calculated by the required bandwidth calculation function. This C(u) is calculated from the equation (4) by using as parameters N(k,j) stored in the call number table and α(k,u,j) stored in the call-required bandwidth table. The calculated C(u) is stored in the buffer-required bandwidth table.

[0052] At the final step in the loop, it is judged whether the link capacity C_pis less than the required bandwidth or the required service rate C(u) in this buffer B_uor not. If C_p<C(u), the fresh call is rejected and a fresh call rejection message is transmitted to another switch by the message transmission function. If C_pis equal to or more than C(u), u is incremented by one and then the above-mentioned looped steps are repeated for next class.

[0053] If the link capacity C_pis equal to or more than all of the calculated required service rates C(u) of the buffers k to K, the fresh call is accepted and the looped steps are completed. In this case, bandwidth is assigned by the bandwidth assignment function and a fresh call acceptance message is transmitted to another switch by the message transmission function.

[0054] FIG. 10 shows a flow chart for previously calculating the number of acceptable calls at designing, used in the call admission control in accordance with the latter scheme. In this scheme as aforementioned, the call admission control is done in such a way that a fresh call is accepted if the number of calls in progress is less than or equal to the designed maximum number otherwise the fresh call is rejected.

[0055] At designing, the maximum number of acceptable calls for each call type N_max(k,J), where J=1 to J_k, is preliminarily assumed. The assumed maximum number for each call type N_max(k,j) is stored as the number of calls N(k,j).

[0056] Then, the looped steps with respect to calls of classes 1 to K are executed to determine the maximum number of acceptable calls for each class. First, whether N(k,j) is acceptable number in this class k or not is executed. If the number of calls N(k,j) is not acceptable in this class k, N(k,j) is reduced by one and the judgment is executed again. If the number of calls N(k,j) is acceptable in this class k, N(k,j) is determined as the maximum number N_max(k,j) in this class k and the judgment in next class is executed. Thus, when the looped steps are completed, the maximum numbers of acceptable calls for all classes N_max(k,j), where k=1 to K, are determined.

[0057] FIG. 11 illustrates call admission control of a fresh call with class 3 in a model with class 1 to 5 buffers. Hereinafter, numerical example of the call admission control in the model shown in this FIG. 11 will be described with reference to FIG. 9 and Tables 1 to 10.

[0058] First, class k and call type j of a fresh call is determined. If this fresh call is a high rate Internet call corresponding to NV2 in Table 1, class k=3 and call type J=2 are determined. Thus, R(3,2)=400 [cells/sec] is determined from Table 2, Q(3,2)=2.00E−05 is determined from Table 3, N(3,2)=26 is determined from Table 4, and B(3)=150 [cells] is determined from Table 5. As expressed in equation (1), P_Q(3) is equal to Q(3,J) of type j in class 3 with the minimum value (Table 3). Therefore, P_Q(3) is determined to P_Q(3)=1.00E-05 as shown in Table 6.

[0059] Then, the average cell rate S(3) in class 3 is calculated from the equation (2) as follows;

[0060] The calculated value is stored in the average cell rate table of Table 7.

[0061] Then, the looped steps with respect to calls with classes equal to or lower than class 3, i.e. u=3,4,5, are executed to check whether the calls are acceptable into the bandwidth or not.

[0062] In the looped steps, first, P_B(3) is calculated from the equation (3) as follows;

[0063] The calculated value is stored in the buffer cell loss ratio (objective value) table of Table 8.

[0064] Then, the call-required bandwidth α(k,u,j) where k=1 to 5, u=3 to 5 and j=1 to J₅obtained by using P_B(3). In FIG. 11, boldface symbols indicate updated bandwidths α(k,u,j). The obtained call-required bandwidths α(k,u,j) are stored in the call-required bandwidth table of Table 9.

[0065] Then, the bandwidth C(3) totally required by the buffer B₃is calculated from the equation (4) by using as parameters stored in the call number table and the call-required bandwidth table. The calculated C(3) is stored In the buffer-required bandwidth table of Table 10.

[0066] At the final step in the loop, whether the link capacity C_pis less than the required bandwidth C(3)=43010 in this buffer B₃or not. If C_p<C(3), the fresh call is rejected and the fresh call rejection message is transmitted to finish the call admission control. If C_pis equal to or more than C(3), the above-mentioned looped steps are repeated for next lower class. In FIG. 11, boldface parameters indicate parameters updated in the looped steps.

[0067] FIG. 12 shows a graph illustrating required bandwidth with varying the size of class 2 buffer B₂. In the figure, a solid line represents the required link capacity C_pand a dashed line shows the total required bandwidth of all connections V₁+V₂, where $V_k=\sum _{j=1}^{J_k}N\left(k,j\right)\alpha \left(k,k,j\right)$

[0068] that corresponds to the total required bandwidth of class k calls in class k buffer. With reference to FIG. 12, an example for calculating the required bandwidth in case that calls in two priority classes are arrived at the ATM switch in class k=2 will be described.

[0069] It is assumed that cell arrivals of each connection are Poissonean with respective arrival rates, that summation of the average cell rates in class 1 and class 2 are S(1)=4000 [cells/sec] and S(2)=1000 [cells/sec], and that the objective values of cell loss ratio are Q(1)=Q(2)=10⁻⁵. The size of the class 1 buffer B₁is assumed as B(1)=20 [cells]. The VP bandwidth for each class V_kand the required link capacity C_pwhen the size of the class 2 buffer B₂is varied as B(2)=10 to 100 are obtained. It will be noted from FIG. 12 that the required link capacity C_pis decreased when the objective value of cell loss ratio in the buffer B₂or the size of the buffer B₂increased. Also, the required link capacity C_pbecomes smaller than the total required cell rate of connections V₁+V₂when the size of the buffer B₂is larger than 30 cells. This is because the required bandwidth for class 1 calls in the buffer B₂denoted by α(1,2,1) is smaller than that in the buffer B₁denoted by a(1,1,1) when the buffer capacity B(2) becomes larger than 30 cells.

[0070] Thus, according to the present invention, influences of higher priority calls over QoS requirements of lower priority calls are sufficiently considered for providing a plurality of services with the different QOS requirements. As a result, it is possible to precisely estimate bandwidth in progress and required bandwidth due to acceptance of a fresh call.

[0071] Many widely different embodiments of the present invention may be constructed without departing from the spirit and scope of the present invention. It should be understood that the present invention is not limited to the specific embodiments described in the specification, except as defined in the appended claims.