KR0129609B1 - Method for adjusting inter-cell distance of upc - Google Patents

Abstract

A regulating method for the adaptive cell space of the usage parameter control(UPC)/network node parameter control(NPC) where improves the algorithm of RAT(Recent arrival time) and RDT(recent departure time) in order to decrease the delaying and uses the credit in order to prevent the busy line of the network due to the cell transmission delay variation of ATM. In case that the virtual cell arrival time is TAT(i); the recent cell arrival time is ta(i); and the permitted cell delay variation is the gamma, the number of credit is 1+[gamma-{TAT(i)-ta(i)}+ /T.

Description

Adaptive Cell Spacing Adjustment Method of Used Variable Control / Network Variable Control (UPC / NPC)

1 is a block diagram of an ATM subscriber board to which the present invention is applied.

2 is a spacer diagram of a RAT algorithm.

3 is a spacer diagram of an RDT algorithm.

4 is a flowchart illustrating an adaptive cell interval adjustment process of UPC / NPC using credits.

In the present invention, an ATM parameter function is performed in a subscriber board or trunk access board of an asynchronous transfer mode (hereinafter, referred to as ATM). In particular, the present invention relates to a method for adjusting the interval between cells by inputting an output cell of a traffic monitoring function (policer) in a direction in which the cell is inputted to the exchange side.

ATM, which carries information in a cell of fixed length, is a communication method that can efficiently use line capacity by transmitting multiplexed service information having various traffic characteristics by statistical multiplexing. As the ATM communication method is statistically multiplexed, the connection is accepted according to whether the network can satisfactorily provide the transmission quality required by the service of the connection. By monitoring compliance with the traffic and using non-negotiated traffic, such as discarding non-compliant cells, the traffic negotiation violation of one user does not adversely affect other users' transmission quality and network resource management. Prevent. Therefore, the terminal needs to generate a cell by complying with the traffic parameter negotiated with the network, and the traffic generated from the terminal to the network is adjusted to comply with the traffic parameter negotiated by the terminal or NT (Networ Terminal). It is necessary to have a traffic shaping function or the like.

1 is a block diagram of an ATM subscriber board to which the present invention is applied, and a traffic monitoring function block for monitoring whether a user's traffic complies with traffic parameters negotiated between a user and a network by providing a UPC function in a user-network interface (UN). By disposing of a cell for traffic that does not comply with the negotiated traffic parameters, it prevents problems such as transmission quality deterioration on other connections. NPC performs the same function as UPC in a network node. However, in ATM, there is a cell transmission delay, and a cell transmission delay variation occurs because there is no delay. Cell transfer delay variation in ATM is inevitably caused by ATM cell multiplexing. When looking at the hierarchical function of multiplexing, first, the ATM layer in which cells are multiplexed from two or more ATM connections is a major factor. Some cells may be delayed while an overhead or OAM (Operation And Management) cell is inserted. Also, cell delay may be caused by multiplexing at the ATM Adaptation Layer (AAL) layer, similar to cell multiplexing at the ATM layer. Cell Delay Varation) may occur. In addition, the maximum allowable cell delay variation is different between intervals, i.e. between ATM connection endpoints and TBs, between UNI between TBs and networks, and between NNIs in the network. ITU-T Recommendation I.371 In this paper, VSA (Virtual Scheduling Algorithm) and CSLB (Continuos State Leaky Bucket Algorithm) are presented as examples of useful algorithms for monitoring the maximum cell rate of 1 / T of ATM connections considering the cell delay variation. Algorithm to perform in conjunction with is proposed. Since cell delay is allowed and some cell delay is allowed in UPC / NPC, cell clustering exists even after UPC / NPC function processing, which causes congestion at the switch of the network and at the input terminals of UNI and NNI. We need to change the shape of the input traffic so that congestion does not occur in the network.

On the other hand, the traffic shaping involved in the present invention is a function of changing the traffic characteristics of the cell stream on the Virtual Chenel Commection (VCC) or the Virtual Path Cpnnection (VPC) in order to change the traffic characteristics of the cell strip as desired, the cell on the ATM connection The order should be guaranteed, and examples of the technique include a method of reducing the maximum cell rate, a method of limiting the length of clustered cells, a method of reducing CDV by appropriate cell relocation, and a queue service method. As a spacer algorithm that performs traffic shaping, a technique of reducing CDV by relocating a cell using a buffer is introduced, and is operated to be closely associated with UPC / NPC functions. At this time, the UPC / NPC algorithm used is LB (Leaky Bucket) or VSA applied. For the cell relocation method in the spacer, the RAT (Recent Arrival Time) method and the spacer based on the time when the cell is input into the spacer. There is a RDT (Recent Departure Time) method based on the time at which a cell is output.

First, the operation of the existing RAT and RDT algorithm is described as follows.

In order to describe the RAT algorithm, the present invention is divided into a configuration diagram and an operation algorithm for realizing the RAT algorithm.

As shown in FIG. 2, the core of the spacer using the RAT algorithm is divided into VPI / VCI, and the CAT (Connection Attribute Table) storing the RAT and the negotiated peak interval (PI) value T and input cells The common buffer for managing cells until they are stored and outputted from the spacer, and increases by 1 per cell time, and the head for using the scheduler and common buffer (CB) to manage cell movement in the common buffer. It consists of a number of logical elements that manage the pointer (P) of the head and tail.

In the drawing, the common buffer CB is a set of cell memory (CM), and the cell memory is composed of a memory capable of storing one cell (53 bytes) and one pointer P, and the pointer is another cell. This is to construct a linked-list into cell memory by pointing to memory. The common buffer is divided into three logical queues, which are sets of cell memory, which are waiting for the invalid idle cells to be transferred at a specific time calculated by the FQ (Free Queue) and the spacer algorithm. A cell slot queue (CSQ) connected to cells for transmission to an output queue by a scheduler, and an output queue (OQ) connected to cells for receiving cells from the CSQ and outputting one cell at a time per cell time. Therefore, FQ is composed of FQ head, FQ tail and a list of cell memories belonging to FQ, OQ is composed in the same way, and CSQ is CSQ (i) (i = 0,1,2, ..., K) Each CSQ (i) is constructed in the same way as FQ and OQ.

The RAT algorithm first recognizes the connection corresponding to the cell's VPI / VCI at the time of inputting one cell, and reports the negotiated peak interval T of the connection with the time information RAT for the number of CSQs registered in the previous cell in the CAT. Based on TIME, which is the current counter, the current RAT is calculated as follows to determine in which array of the CSQ the current input cell should be put.

RAT (n) = maximum value (TIME, (RAT (n-1) + T) mode K) (Equation 1)

In the above equation, K is the maximum value of the scheduler, which is equal to the number of CSQ arrays, and the scheduler operates as a modular K by increasing the cell time by one. By the above formula

i) In case of [RAT (n-1) + T] mode K TIME, the input cells are arranged in CSQ (RAT (n)) to be output at T greater than the previous RAT.

ii) If it is [RAT (n-1) + T] mode K TIME, it arranges in CSQ of current time pointed by scheduler so that it can be printed as soon as possible.

If there is a cell already registered when registering with the CSQ, it is registered with the tail of the CSQ.

Looking at the spacer operation of the RAT algorithm, the spacer is driven by the three events described below.

First, in the initial state of the spacer, all cell memories of the common buffer are registered in the FQ, and one cell may be input as a spacer. The input cell is input to the cell memory indicated by the FQ head, and the FQ head changes its value to point to the next cell memory indicated by this cell memory, and the pointer of the cell memory in which the cell is being input is initialized to zero. I of CSQ (i) for registering this cell memory to CSQ while the cell is being input is calculated from RAT (n) of equation (1), and then registered to CSQ (i) if the head of CSQ (i) is 0 Define that there is no cell memory specified so that the head and tail of CSQ (i) point to this new cell memorization, and if the head of CSQ (i) is not zero, the pointer of the cell memory pointed to by the tail of CSQ (i) Change the value to point to this new cell memory and make the tail of CSQ (i) point to the new cell memory as well.

Second, when the scheduler operating at the cell clock is started, all cell memories registered in the CSQ (TIME) of the CSQ corresponding to the counter value TIME indicated by the current scheduler are changed to OQ. According to the cell clock, the spacer connects the head of the CSQ (TIME) corresponding to the current counter value TIME to the tail of the OQ. The tail of OQ is changed to the value pointed to by the head of OQ and the tail of the OQ is changed to the pointer pointed at the tail of CSQ (TIME). If the head of the OQ is 0, the head of the OQ changes its value to the head of the CSQ (TIME) and the tail of the OQ changes to the tail of the CSQ (TIME). The head of the CSQ (TIME) in which the cell memory registration change is completed is set to zero. If the head of the CSQ (TIME) is 0, there is no cell memory registered in the CSQ (TIME). In this case, the cell memory registration change does not occur.

Third, the cell is output from the OQ. If the head of the OQ is not 0 by the output cell request signal operating as a cell clock, the contents of the cell memory indicated by the head of the OQ are outputted, and the head of the FQ is connected to connect the cell memory indicated by the head of the OQ to the tail of the FQ. If 0, the head and tail of the FQ point to this cell memory. If not 0, the tail and pointer of the cell memory pointed to by the tail of the FQ point this cell memory. If this cell memory is the last cell of the OQ, 0 is written to the head of the OQ.

3 is a spacer diagram of the RDT algorithm, which is similar to the spacer of the RAT algorithm, and each VPI / VCI is determined based on the time output from the OQ of the spacer. The input cells of cannot be connected to the CSQ until the previous cell of each connection is output from the OQ. Therefore, in the RDT algorithm, it is necessary to temporarily store a cell. For this purpose, it has a TQ (Tempory Queue) in addition to the CSQ and OQ in the common buffer. TQ is configured in the same arrangement as CSQ and is a bundle of TQ (i) (i = 1, 2, ..., N), where N is the maximum number of VPI / VCI connections. In addition, the CAT should have information about whether the cells involved in each connection are in CSQ and OQ.

The RDT algorithm recognizes the connection i corresponding to the cell's VPI / VCI at one cell input, and if the previous cell of the connection is registered in the CSQ or OQ, the input cell connects to the tail of TQ (i), and the CSQ or If there is no cell registered in the OQ, CAT sees the negotiated pig section T of the connection with the time information RDT outputted from the OQ, and the current input cell is based on the scheduler's current counter TIME. To determine if it should be included in

j = RDT (n)

= Maximum (TIME, (RDT (n-1) + T) mode K) (Equation 2)

Here, K is the maximum value of the scheduler and is equal to the number of CSQ arrays. The scheduler increases by 1 for each cell time and operates as a modular K. According to the above equation, the input cell is registered in CSQ (j). Like the RAT algorithm, when there is a cell already registered when registering to CSQ, it is registered to the tail of CSQ. When one cell is output from the OQ, the CAT improves the RDT to the current RDT at the connection k representing the VPI / VCI of the output cell, and then checks whether another input cell is registered in the TQ (k). If a cell is registered, the cell in the head of TQ (k) is connected to the tail of CSQ (j) as follows.

j = RDT (n-1) + T (Equation 3)

However, the RAT and RDT algorithms attempt to guarantee the inter-cell spacing of the output cells uniformly over the peak interval, and include a lot of delay in the spacer, and the delay is the maximum value of the CDV generated at the front end. This delay causes a direct disadvantage of deterioration of transmission quality in the terminal transmitting data through the ATM network.

Accordingly, the present invention provides a method for adaptive cell spacing of UPC / NPC using credits to prevent congestion in the network due to cell transmission delay variation in ATM by improving the RAT and RDT algorithms. The purpose is to provide.

In order to achieve the above object, the present invention uses a CAT (Connection Attribute Table) for storing a peak section, a recent arrival time or a latest departure time for each virtual connection classified as VPI / VCI, and a cell memory including a pointer and cell data. A cell buffer provided as an empty queue (FQ), a cell slot queue (CSQ), an output queue (OQ), or a temporary queue (TQ), which is a set of linked list nodes in units of memory, An empty queue, a cell slot queue, an output queue or a pointer to a temporary queue for managing cell memory registered in the cell buffer, and a scheduler for countering the cell clock and moving the cell memory registered in the cell slot queue to the output queue. In the cell interval adjustment method, the result of determining the usage variable control / network variable control (UPC / NPC) in conjunction with the usage variable control / network variable control (UPC / NPC) that monitors whether the user's traffic complies with the negotiated traffic parameters How to adjust cell spacing For use, the theoretical cell arrival time is TAT (i); The actual cell arrival time is Ta (i); If the allowed cell delay is τ,

If the credit is large, the small inter-cell spacing of the output cell is also allowed, and the smaller the credit, the inter-cell spacing of the output cell is guaranteed to be close to the maximum interval.

Hereinafter, the present invention will be described in detail with reference to FIG. 3.

In order to examine the spacer algorithm of the present invention using credits, first, a Virtual Scheduling Algorithm (VSA) is described. VSA is the algorithm presented in ITU-T Recommendation I.371 as a reference model for measuring the performance of other UPC / NPC algorithms.

If the negotiated maximum cell rate is 1 / T and the cell interval at this time is T and the allowed CDV is assigned to, when one cell is input, it is checked whether the cell complies with the traffic parameters by the following equation.

ta TAT -τ (Equation 4)

If the above equation is not satisfied, the compliance cell is determined, and the TAT used to determine the next cell to be input is improved by the following equation.

TAT = maximum value (ta, TAT) + T (Equation 5)

In this case, the conventional RAT and RDT algorithms determine the position of the queue into which the current input cell is inserted based on the arrival time or departure time of the previous cell. It was for. As a result, when a cell having a large delay is input, the burst traffic is widened at regular intervals after the cell, and thus burst traffic is accumulated and outputted with delay. Therefore, in order to reduce delay, the cell spacing adjustment result of one burst period should not affect the cell spacing adjustment of the next burst period.

In the present invention, when the cell following the non-burst interval is adjusted, the cell is adjusted in a smaller interval than the PI (Peak Interval) as a method of compensating the influence of the preceding non-burst interval on the assumption that the cells of the current interval will burst. Considered how. In addition, in order to perform the spacer function, a VPI / VCI and a PI, etc. to be remembered in order to perform a traffic monitoring function (hereinafter referred to as a policy) are required. The logic for reading a PI from the VPI / VCI is also the same. Therefore, it is advantageous because the same memory contents and logic, etc. can be saved by integrating the polyser and the spacer, and in the case where the spacer is actually implemented, it is generally configured in such a manner. For example, there is an example of implementing a spacer function by adding some logic and memory to the logic and memory for implementing the policy function.

In the present invention, the result of the VSA, the algorithm of the polyser, is used to adjust the cell spacing of the spacer, and the number of credits is defined as follows.

From here

TAT (i0): theoretical cell arrival time

ta (i): actual cell arrival time

τ: allowed CDV (Equation 6)

(x) +: greater than 0

0≤ (TAT (i)-ta (i)) + ≤τ

Looking at the properties of Equation 6 in relation to the VSA of the polycer,

(1) The first cell input from the VSA is always determined as a compliance cell, and ta (i) TAT (i) is the same condition as the first cell. In Equation 6, the CD has the maximum value for the first cell and ta (i) TAT (i).

(2) Non-compliance cell determination may occur when a burst cell is input, and a cell whose TAT (i) -ta (i) = τ is determined as a compliant cell by the policer, but TAT (i) -ta (i The cell to be determined is a noncompliant cell. In the above equation, it corresponds to the case of CD = 1 and CD1, respectively.

(3) When a burst cell is input, TAT (i) -ta (i) increases by T in VSA, and CD decreases by 1 in Equation 6. If the output cell of the polymerizer is used as the input of the spacer, the minimum value of CD is CDmin and the maximum value is CDmax.

The method of applying the credit to the cell spacing adjustment is a method of correcting the cell spacing by the PI value as the value is closer to CDmin when the credit is close to CDmax. Define the relationship from CDmax, CDmin and CD as follows:

Using this relationship, one can think of a linear adjustment method such as the following equation (8), a nonlinear adjustment method, and the like.

To actually use this, a specific threshold value is defined and used in several steps as shown in Equation (9).

in

In order to implement a cell spacing control method using credits, the cell order must be guaranteed. When the cell spacing adjustment method of the present invention is applied to the RAT, the connection negotiated with the RAT (n-1) representing the time when the previous cell is inserted into the CSQ in the connection corresponding to the VPI / VCI of the cell when one cell is input. Based on PI (Peak Interval), the i of CSQ (i) to register an input cell is calculated according to the current Counter value of the Scheduler. That is, it decides which array of CSQ to put the current input cell, and the following (Equation 10)

Is the same as the RAT algorithm except that Peak Interval T is changed to Adaptive Cell Interval B. In the same way, it is applied to the RDT algorithm to calculate the number of arrays of the current input cell into the CSQ.

In the cell spacing method of the present invention, when A = 0 is fixed irrespective of CD, B = T becomes the original RAT and RDT algorithms.

FIG. 4 is a flowchart illustrating an adaptive cell spacing adjustment process of UPC / NPC using credits. When one cell is input, parameters necessary for a policy and a spacer are obtained from a memory (10). As a previous step to calculate parameter A of If A'0 is YES, it is determined that the input cell has not complied with the traffic parameters and tagged or discarded by the function of the policy. (40), if NO, the spacer algorithms 31 to 34 of the present invention are performed. Performing a spacer algorithm takes A ' By calculating (31), we get the same result as (Equation 7), and look up the table with A to access the value previously saved from (Equation 8) as (Equation 9). By calculating B 'by the method (32) and multiplying by PI to calculate B (33), we get the same result as (Equation 9). The cell spacing adjustment is adaptively performed in the RAT algorithm 34 applying the obtained parameter B to (Equation 10) or the RDT algorithm 34 applying (Equation 11).

According to the present invention as described above, the same memory content and logic can be saved by implementing the spacer in conjunction with the spacer so that the result of the polymer can be used to adjust the cell spacing of the spacer.

Claims (2)

Linked list is linked by unit of CAT (Connection Attribute Table) which stores peak period, last arrival time or latest departure time for each virtual connection classified by VPI / VCI, and cell memory composed of pointer and cell data. List manages cell buffers, which are provided as empty queues (FQ), cell slot queues (CSQ), output queues (OQ), or temporary queues (TQ), and cell memories registered in the cell buffer. A cell spacing adjusting method comprising: a pointer for a blank queue, a cell slot queue, an output queue, or a temporary queue, and a scheduler for counting a cell clock and moving a cell memory registered in the cell slot queue to an output queue, Using the result of the use variable control / network variable control (UPC / NPC) decision in the cell interval adjustment method in conjunction with the use variable control / network variable control (UPC / NPC) that monitors whether the user's traffic complies with the negotiated traffic parameters. for, Theoretical cell arrival time is TAT (i); The actual cell arrival time is Ta (i); If the allowed cell delay is τ, If the credit is large, the small cell-to-cell spacing of the output cell is allowed, and the smaller the credit, the more the cell-to-cell spacing of the output cell to be close to the maximum interval is used variable control / network variable control (UPC / NPC) Adaptive Cell Spacing. The method of claim 1, wherein the cell spacing adjustment Retrieving (10) the parameters required for the polymer and spacer from the memory when one cell is input; Calculate A '(20), if A'0 is YES, determine that the input cell has not complied with the traffic parameters (30); Calculating (31); Finding B 'with A using a table search method; Calculating B by multiplying B 'by a peak interval PI; Applying B to i = RAT (n) = max TIME, (RAT (n-1) + B) mod CSQmax or i = RDT (n) -max TIME, (RDT (n-1) + B) mod CSQmax Adaptive cell interval adjustment method of use variable control / network variable control (UPC / NPC), characterized in that it comprises a step.