ATM Bandwidth Assignment Policy Using an Adaptive Methodology

High-speed asynchronous transfer-mode (ATM) network architecture provides increased flexibility in supporting various services. However, ATM's dynamic nature poses difficult traffic-management problems, such as bandwidth estimation and allocation, when trying to achieve efficient use of network resources. This article proposes an adaptive methodology via auto-regressive moving average (ARMAX) and one-layer neural network (NN)-based adaptive bandwidth estimation and allocation in high-speed asynchronous transfer mode (ATM) networks. The paper gives a mathematical analysis to demonstrate the convergence of the prediction error in bandwidth so that a desired quality of service (QoS) can be guaranteed. The QoS is defined in terms of cell-loss ratio (CLR) and transmission delay. The performance of the proposed scheme is evaluated in the presence of MPEG data. The purpose of such a method is to manage the bandwidth efficiently, in routing and in call-admission procedures.

The basic objective of a bandwidth management and traffic control strategy is to achieve high utilization of network resources while sustaining an acceptable QoS. Most traffic-control functions, such as flow and congestion control, routing and call-admission control schemes, depend on characterizing the effective bandwidth of individual connections and link loads. The network requires information on available bandwidth to decide whether or not to accept a new connection. Routes are typically selected and calls accepted to minimize a certain measure of resources while providing adequate QoS to the carried traffic. This requires an accurate estimate of traffic conditions and the impact of adding a new connection. Subsequently, this information is provided for calculating the amount of bandwidth currently allocated to accommodate existing connections, and by identifying how much additional bandwidth needs to be reserved on links over which a new connection will be routed. In order to obtain an accurate accounting of the bandwidth currently used, you have to determine the current traffic onto these links.

The problem of bandwidth estimation and allocation is covered in a number of very interesting papers. While the methods taken in these papers may differ, they are either restricted to self-similar traffic, to a limited range of connections since they essentially rely on sets of curves, obtained by simulation, which are used as guidelines to determine the equivalent capacity of connections. These result in inaccurate bandwidth estimation and allocation. Our scheme takes advantage of a network model, estimation of traffic using an adaptive methodology, calculation of the bandwidth used and allocation policy, and the available capacity for new connections. The objective of the proposed scheme is to obtain the current bandwidth usage, bandwidth requirement, and allocation policy while meeting the QoS using an adaptive network methodology deploying ARMAX and NN.

This article develops a novel adaptive scheme to estimate the traffic by minimizing the buffer-occupancy estimation error and to estimate the bandwidth required. Closed-loop convergence with network stability is proven using a Lyapunov-based analysis. Using the target QoS, the bandwidth required is calculated independently using the cell-loss ratio (CLR), transfer delay (latency), and buffer occupancy. Using the current traffic, buffered traffic, and target QoS, we calculate and allocate the bandwidth required to meet the QoS. The proposed scheme guarantees the desired QoS even in the presence of bounded network traffic uncertainties. We also show simulation results to justify the theoretical conclusions.

      (1)

where q is a matrix of constant parameters (or coefficients) and f(x(k)) denotes the regression matrix at time k, with e(k) a reconstruction error vector. Define the output of the ARMAX model as:

      (2)

It is important to note that the unknown ARMAX parameters enter in a linear fashion. In addition, the ARMAX approach can accurately model voice sources. Furthermore, this approach can also model bursty MPEG data. For a one-layer NN, the parameters will become weights and the linear-regression function in the ARMAX method will become a nonlinear function. For a one-layer NN, for suitable approximation, we use radial basis functions.

ATM Switch and Network Traffic Model
The most important step in determining bandwidth usage and allocation is to estimate the network traffic the switch accumulates in an intelligent manner using the buffer occupancy. Consider a virtual source/destination pair to be controlled, shown in Figure 1, as:

      (3)

where state is the buffer length (or occupancy) at time k, T the sampling time, and the source rate. The nonlinear function f(.) is the buffer occupancy due to traffic flow, which is considered unknown. Then, f(.) is a function of buffer size and service capacity at a given switch. We assume the unknown disturbance vector acting on the system at time k, , is bounded by a known constant, . The disturbance vector d(k) can be an unexpected traffic burst/load or change in available bandwidth due to the presence of a network fault. The state x(k) is a positive scalar if a single switch/single buffer scenario is considered—it becomes a vector when multiple network switches/multiple buffers are involved. The service capacity at the outgoing transmission link is denoted by S_r in Figure 1. The first step in the proposed approach is to estimate the buffer occupancy using an estimate of the network traffic at the switch.

Figure 1:  Multiple sources and network switch with bandwidth allocation

The objective here is to construct a model to identify the traffic accumulation at the switch

      (4)

where the state of the model, is the buffer occupancy estimate at time k and the nonlinear function is the traffic-flow estimate. Therefore, f(.) is a function of past values of buffer occupancy at a given switch.

Define the performance criterion in terms of buffer-occupancy estimation error as:

      (5)

where the cell losses, for a buffer size of x_d, are given by

      (6)

Equation 6 can be expressed using Equations 4 and 5 as:

      (7)

where e(k+1) and x(k+1) denote the error in buffer-occupancy estimate and the state at time k+1, and the traffic-flow modeling error is given by .

Equation 7 relates the buffer-occupancy estimation error with the traffic flow modeling error.

In high-speed networks, each source should be able to use the available bandwidth up to its Peak Cell Rate (PCR). The goal of an bandwidth estimation and allocation scheme is to fully utilize the network's available bandwidth while maintaining a good QoS, where the QoS parameters are the CLR, transmission delay, and network resource utilization. In this article, the objective of selecting a suitable traffic estimation scheme is to minimize the difference between actual and desired occupancy to be able to guarantee the QoS. Equation 7 calculates the cell losses encountered at the switch due to the traffic-estimation scheme.

Figure 2:  Adaptive bandwidth estimator structure

Estimator Structure
Define the traffic estimate as:

      (8)

where are the current values of the parameters. The next step is to determine the parameter updates to guarantee the performance of the closed-loop buffer occupancy dynamics at the switch. Figure 2 shows the controller structure. Let q be the unknown ideal parameters required for the approximation to hold in Equation 3 and assume they are bounded so that

      (9)

where q_max is the maximum bound on the unknown parameters. The error in the parameters during estimation is given by

      (10)

The past values of buffer occupancy are bounded by known positive values so that and .

Using the ARMAX traffic-rate estimate, the closed-loop buffer occupancy dynamics become

      (11)

where the traffic flow modeling error is defined by

      (12)

Parameter Updates for Guaranteed QoS
We need to demonstrate that:

• The performance criterion in terms of cell losses, c(k), and transmission delay monitored through buffer occupancy estimation error, e(k), is suitably small
• The parameters remain bounded such that the traffic rate, u(k), is bounded and finite.

The following theorem gives discrete-time parameter-tuning algorithms based on the error in buffer occupancy.

Theorem 3.1:

Let the desired buffer length x_d be finite and the network traffic estimation error bound, e_N, and the disturbance bound, d_M, be equal to zero. Let the parameter tuning be provided by delta rule. Then the buffer occupancy estimation error e(k) approaches asymptotically to zero and the parameter estimates are bounded.

Proof:

In the next section, we use the estimated traffic-accumulation to obtain current bandwidth usage and the bandwidth requirement for the next time interval. We need to allocate this calculated bandwidth fairly among sources—this is discussed in the next section.

      (13)

where DBw(k) is the additional bandwidth required to process the new data, T is the sampling interval, and and are the traffic estimates at the times k and k-1 respectively. Equation 13 presents the traffic accumulation at the switch during the time interval T. The bandwidth calculation using the traffic accumulation may not be accurate if the QoS is not taken into consideration. Therefore the following equation relates the additional bandwidth to satisfy the CLR requirement as

      (14)

where TCLR represents the target or desired cell-loss ratio. In order to ensure that sufficient bandwidth is assigned to meet the delay requirement, the equivalent bandwidth required to meet the delay is given by

      (15)

where x(k) is the current buffer occupancy and t is the acceptable transmission-delay specification. Equation 15 shows that you need to assign additional bandwidth to transmit the data queued from the switch buffer to its destination. Typically, the target delay is specified as a percentage of total transfer time.

Using Equations 13 and 14, the additional bandwidth required to satisfy accumulated traffic and CLR constraints is

      (16)

where is the traffic accumulated in the time interval. Finally, the bandwidth to be assigned at the switch for the traffic sources to meet the QoS service (CLR and transfer delay) and traffic accumulation requirements is

      (17)

The bandwidth required for the next sampling (measurement interval) is given by

      (18)

where Bw(k+1), Bw(k) represents the bandwidth at times k+1 and k respectively. Equation 18 dictates the bandwidth to be assigned to the sources sending the multiplexed traffic provided the bandwidth meets the maximum available capacity requirement of the outgoing link. If S_max is the maximum capacity of the outgoing link, then if Bw(k+1) exceeds the S_max, the available bandwidth is set to S_max. Otherwise, the bandwidth the sources require in the next sampling interval is calculated using Equation 18.

If multiple sources are sending traffic, these sources must fairly share the bandwidth at the outgoing link. This is bandwidth assignment or allocation.

Network Model
The buffer length at the switch x_d is selected as 250 and varied. The CLR is defined as the total number of cells discarded at the receiver due to buffer overflows divided by the total number of cells sent onto the network. The target CLR is defined as 10^-15 whereas the transfer delay is defined as 0.1% of the total time to transmit the data if the bandwidth is available at the peak cell rate. This value is given as 167 msec (0.1% of 167) and it is used as the target cell-transfer delay.

Traffic Source Used
The MPEG data set used in the simulations was found at a Bellcore ftp site. This data set comes from the movie "Star Wars." The movie length is approximately two hours and contains a diverse mixture of material ranging from low-complexity scenes to scenes with high action. The data set has 174,138 patterns, each pattern representing the number of bits generated in a frame-time F. In this trace, 24 frames are coded per second, so F is equal to 1/24 second. The peak bit-rate of this trace is 185,267 bits/frame, the mean bit-rate is 15,611 bits/frame and the standard deviation of the bit-rate is about 18,157. We used 4000 frames from this trace to run our simulations. Our scheme estimates the bandwidth required for the source to transmit information without losing cells and causing undue delay.

Simulation Example
In these simulations, the peak bandwidth available at the outgoing transmission link is equal to the PCR of the source. When the assigned bandwidth is equal to the PCR, as shown in Figures 3 and 4, the actual delay is less than the targeted delay, but the actual CLR is close to zero. However, a large amount of bandwidth is wasted, as shown in Figure 3 through the negative prediction error, which implies that the PCR method is over-estimating the bandwidth. On the other hand, both adaptive ARMAX and NN methods more accurately predict the bandwidth required for transmission. This has resulted in a low CLR and delay when the buffer size is less than 250 cells. Given the ARMAX and NN methods, the one-layer NN appears to be more accurate than the adaptive ARMAX. Furthermore, when the buffer size is equal or greater than 250 cells, both the ARMAX and NN methods render zero CLR and low latency, which satisfy the target QoS. Table 1 summarizes the results when the buffer size is 250 cells for the MPEG data. As expected, the proposed scheme was able to estimate and assign the bandwidth according to the requirements for bursty MPEG data.

Figure 3:  Exponentially weighted moving average prediction error

Figure 4:  Cell-loss ratio and latency for different methods