This paper presents an in-depth survey on network bandwidth allocation policies and discuss design methodologies of distributed rate calculation algorithms in packet-switched networks. In particular, we discuss two rate allocation policies: the generalized max-min and the generic weight- proportional max-min policies, both of which generalize the classical max-min rate allocation policy. For the design of distributed algorithms to achieve these two rate allocation policies, we focus on rate-based distributed flow control where special control packets are employed to achieve the information exchange between a source and the network. We categorize two broad classes of distributed rate calculation algorithms in the literature using live algorithms as illustrations. We compare the design tradeoffs between these two classes of algorithms in terms of performance objectives and implementation complexities and discuss important extensions within each class of algorithms.

In many ATM switches, only a limited number of delay priority queues are available at each link. In order to support all five service categories defined in ATM Forum, the UBR and ABR service classes may have to be assigned to the same priority queue. In this paper we address the problem of controlling the resource sharing between UBR and ABR when both share the same FIFO queue in an ATM switch. We achieve the desired bandwidth sharing between these two classes by controlling the amount of buffer each class can occupy. In particular, we use the EDP threshold to control UBR by dropping UBR cells when this threshold is exceeded. We show that the control algorithm proposed in this paper achieves a tight control of the resource allocation between UBR and ABR.

In this paper, we introduce a novel explicit rate algorithm to support available bit rate service in asynchronous transfer mode networks. Our algorithm is based on observing the maximum bandwidth usage of different connections and incorporating both rate and queue length information to achieve a stable operation. Zero steady state queue length is achieved. We separate congestion control and fairness issues in our design and estimate the number of locally bottlenecked active connections. This number is used to normalize control and to redistribute spare bandwidth during transient and does not affect the steady state fair rate used by each connections. As such, our algorithm is relatively insensitive to the accuracy of this number. The issue of supporting both UBR and ABR is addressed. The performance of our algorithm is evaluated through simulations.

This tutorial paper surveys the important issues in stability and sensitivity analysis of ABR flow control of ATM networks. THe stability and sensitivity issues are formulated in a systematic framework. Four main cause of instability in ABR flow control are identified: unstable control laws, temporal variations of available bandwidth with delayed feedback control, misbehaving components, and interactions between higher layer protocols and ABR flow control. Popular rate-based ABR flow control protocols are evaluated. Stability and sensitivity is shown to be the fundamental issues when the network has dynamically-varying bandwidth. Simulation result confirming the theoretical studies are provided. Open research problems are discussed.

In this paper, we demonstrate the existence of fair end-to- end window-based congestion control protocols for packet- switched networks with FCFS routers. Our definition of fairness generalizes proportional fairness and includes arbitrarily close approximations of max-min fairness. The protocols use only information that is available to end hosts and are designed to converge reasonably fast. Our study is based on a multiclass fluid model of the network. The convergence of the protocols is proved using a Lyapunov function. The technical challenge is in the construction of the protocols.

We propose and analyze a traffic model of a cellular radio communication network with an arbitrary cell connection and arbitrary probabilistic movement of mobiles between the cells. Our analytic model consists of birth-and-death processes for individual cells connected by the numerical adjustment of hand-off rates. This approximation is validated by simulation. We evaluate the probabilities of the immediate loss, the completion, and the forced termination during hand-off for an arbitrary call in the network. Our numerical examples reveal the cases in which the increase in the generation rate of new calls results in the loss probability without affecting much the probability of forced termination in a limited service area.

Multimedia wireless networks are being considered as a natural evolution of the present radio networks. In most of the case, these networks will be connected to an ATM high sped backbone network, and the evaluation of the network performance under users mobility activity demands for new analyses. In this environment, it is particularly important to know the number of handoffs or handovers during a call to make an appropriate dimensioning of virtual circuits for a wireless cell. In this paper we study the handover distributions and their statistical moments for a variety of cell residence times and call holding times distributions. The pmf of the number of handoffs is then used to evaluate the probability of a call completion as a function of the call forced terminated probability due to unavailability of channels in the handoff event.

In recent years many research efforts have focussed on resource reservation and call admission for the case when hard guarantees are required, and on the development of algorithms that take time-invariant descriptions of continuous media (CM) flows with stringent delay requirements. In this paper we take a different approach and address the problem of call admission by developing an algorithm that uses more general descriptions of stored CM flows which are not necessarily time-invariant. We present an algorithm for producing a parsimonious flow description which improves the network resource utilization as much as 200-250 percent over the best possible utilization that can be achieved using any time-invariant workload function. We also present the admissibility conditions for flows with more general descriptions that need not be time-invariant, where packets are scheduled according to the earliest- deadline-first scheduling policy. This generalizes an earlier result. Furthermore, we present an algorithm for testing for admissibility of a new flow whose computational complexity is linear in the number of flows, i.e., the same as the case when time-invariant descriptions are used.

We propose a video adaptation scheme for video transmission over available bit rate channels. We assume that the ABR channel supports a modified version of the explicit rate feedback control scheme, with which video sources can specify their bandwidth needs by placing a demand value in the resource management cells. Bandwidth is distributed among video connections in proportion to their demands. We investigate issues such as 'How should we adapt the video output rate to the allocated bandwidth.' 'How frequently should we change the demand.' and 'How should we adapt the video output rate to the allocated bandwidth.' Based on our investigation, we propose that the bandwidth demand specification should include both the intrinsic bandwidth requirement of a video source and the current smoothing buffer level. We show that by defining the demand this way, we can limit the worst-case buffering delay at the source. We also show that with an encoder-rate controller, the impact of buffer overflow on the video quality can be reduced by discarding bits from video frames evenly.

The main problem complicating multicast video transport is variation in network bandwidth constraints. This paper presents a novel credit-based multicast flow control approach, which allows for potentially full utilization of all branches in a multicast tree at the expense of low priority packets losses. It uses hop-by-hop flow control as well as explicit rate congestion feedback from the destinations. The responsiveness, bandwidth utilization, video quality and fairness of the mechanism are evaluated through simulations. Results suggest that the proposed mechanism is capable of providing a high quality video service in the presence of varying bandwidth constraints.

In this paper, we discuss issues of rate controlling many- to-many multicast connections. In particular, we present an end to end rate control algorithm for multicast ABR service in ATM networks. The algorithm is the extension of the SP- MRCA point-to-multicast congestion control algorithm proposed. The goal is to control the various multicast members input rates in order to achieve high bandwidth utilization without overflowing any queue along a multicast tree. We show that a multipoint-to-multipoint multicast connection can be viewed as a superposition of one-to-many multicast connections, and compute the multicast input rate for each multicast member separately. The algorithm proposed, called SP-MMRCA, inherits many of the properties of the point-to-multipoint SP-MRCA.

In multipoint-to-point connections, the traffic at the root is the combination of all traffic originating at the leaves. A crucial concern in the case of multiple senders is how to define fairness within a multicast group, and among groups and point-to-point connections. Fairness definition can be complicated since the multipoint connection can have the same identifier on each link, and senders might not be distinguishable in this case. Many rate allocation algorithms implicitly assume that there is only one sender in each VC, which does not hold for multipoint-to-point cases. We give various possibilities for defining fairness for multipoint connections, and show the tradeoffs involved. In addition, we show that ATM bandwidth allocation algorithms need to be adapted to give fair allocations for multipoint-to-point connections.

Multipoint communication has been an increasingly focused topic in computer communication networks, including both the Internet and the ATM networks. We have previously presented, analyzed, and evaluated new point-tomultipoint ABR flow control algorithms. In this paper, we focus on multipoint-to-point flow control. As the major objective of ABR service is to provide minimum-loss, fair service to data traffic, an effective merge-point scheme for multipoint-to-point flow control should guarantee some suitable fairness. In this paper, we first examine the "essential fairness" concept proposed by Wang and Schwartz for point-to-multipoint flow control in the Internet. We extend and enhance the concept to the multipoint-to-point ABR flow control. A general algorithm guaranteeing essential fairness is presented, with a detailed implementation on top of the ERICA unicast algorithm proposed by Jam, et. al. The general algorithm may be used for a wide range of fairness specifications to accommodate various bandwidth requirement from unicast or multicast sources of different application streams. Three major variations of the general algorithm are presented. These three schemes are simulated and evaluated, and compared with an existing scheme proposed by Ren, Siu, and Suzuki. Simulation results show that the proposed merge-point algorithm achieves, within short transient time, max-mm fairness based on different weights given to individual sources or sessions, or according to various specifications of fairness. The fairness concept and the general algorithm presented here may be readily applied to other high-speed networks such as the Next Generation Internet and Wireless ATM, and to different multicast settings such as point-to-multipoint and multipoint-to-multipoint.

Keywords: ATM network, ABR traffic, flow control, multicast

Multipoint communications has been an increasingly focused topic in computer communication networks, including both the Internet and the ATM networks. We have previously presented, analyzed, and evaluated new point-to-multipoint ABR flow control algorithms. In this paper, we focus on multipoint- to-point flow control. As the major objective of ABR service is to provide minimum-loss, fair service to data traffic, an effective merge-point scheme for multipoint-to-point flow control should guarantee fairness. In this paper, we first examine the 'essential fairness' concept proposed by Wang and Schwartz for point-to-multipoint flow control in the Internet. We extend and enhance the concept to the multipoint-to-point ABR flow control. A general algorithm guaranteeing essential fairness is presented, with a detailed implementation on top of the ERICA unicast algorithm proposed by Jain, et. al. The general algorithm may be used for a wide range of fairness specifications to accommodate various bandwidth requirement from unicast or multicast sources of different application streams. Three major variations of the general algorithm are presented. These three schemes are simulated and evaluated, and compared with an existing scheme proposed by Ren, Siu, and Suzuki. Simulation results show that the proposed merge- point algorithm achieves, within short transient time, max- min fairness based on different weights given to individual sources or sessions, or according to various specifications of fairness. The fairness concept and the general algorithm presented here may be readily applied to other high-speed networks such as the Next Generation Internet and Wireless ATM, and to different multicast settings such as point-to- multipoint and multipoint-to-multipoint.

We study the delay in asymmetric cyclic polling systems with general mixtures of gated and exhaustive service, with generally distributed service times and switch-over times, in heavy traffic. We obtain closed-form expressions for all moments of the delay incurred at each of the queues. The expressions are strikingly simple and can even be expressed as finite products of known factors. The results provide new insights into the heavy-traffic behavior of polling systems.

In this paper we present a performance evaluation of windowing mechanisms in WWW applications. Previously, such mechanisms have been studied by means of measurements only, however, given suitable tool support, we show that such evaluations can also be performed conveniently using infinite-state stochastic Petri nets. We briefly present this class of stochastic Petri nets as well as the approach for solving the underlying infinite-state Markov chain using matrix-geometric methods. We then present a model of the TCP slow-start congestion avoidance mechanisms, subject to a typical WWW workload. The model is parameterized using measurement data for a national connection and an overseas connection. Our study shows how the maximum congestion window size, the connection release timeout and the packet loss probability influence the expected number of buffered segments at the server, the connection setup rate and the connection time. Furthermore, the crucial effect of correctly modeling the bursty nature of the system workload is illustrated by investigating several arrival models.

Scalable web servers can be built using a Network of Workstations (NOW) where server capability can be added by adding new workstations as the workload increases. The task of load balancing Hyper Text Transfer Protocol traffic to scalable web servers is the topic of this paper. We present a classification framework for scalable web servers, and present simulations of a clustered web server. The cluster communication is modeled using a detailed, verified model of TCP/IP processing over Asynchronous Transfer Mode. The simulator is a trace driven discrete even simulator, and the traces are obtained from the proxy server of a large Internet Service Provider in Norway. Various load balancing schemes are simulated for Robin load balancing policy implemented in a modified router gives better average response time and better load balancing than the Rotating Nameserver method used in current scalable web servers.

The recent deployment of broadband networks that accommodate applications with diverse quality of service requirements presents new challenges to the pricing services. Pricing can and should be used to influence customers to chose services that fit their application needs, maximizing the statistical multiplexing capability of the network. This paper presents a framework for studying the issues involved in pricing for multiple-service networks. Our results illustrate how we can affect customers' choices by charging according to the amount of resources that are allocated to a connection.

The available bit service (ABR) is a promising 'best effort' service designed to achieve in ATM networks high efficiency and low cell loss. Since the ATM forum approved a first standard, intensive research has been done about ABR. The aim of this paper is to analyze the main research topics involved in ABR, namely: the evaluation of traffic and congestion control schemes, conformance definition and policing and charging.

Rate allocation using the Max-Min fairness criterion may highly discriminate against multicast and long unicast sessions and may lead to sever network underutilization. In this paper, we present a solution for rate allocation that is based on competitive pricing. The resultant allocation increases fairness towards multicast sessions and improves network utilization considerably. The solution requires no re-routing of sessions. The economy on which we base our solution is simple enough, enabling its implementation for practical use. We present a distributed asynchronous protocol suitable for the ATM ABR service, which achieves the economy's allocation efficiently and with short convergence time.

We consider a dynamically reconfigurable network environment where dynamically changing traffic is offered. Rearrangement and adjustment of network capacity can be performed to maintain Quality of Service requirements for different traffic classes in the dynamic traffic environment. In this work, we specifically consider the case of a single, dynamic traffic class scenario in a loss mode environment. We have developed a numerical, analytical tool which models the dynamically changing network traffic environment using a time-varying, fluid-flow, differential equation that can be used to study the impact of an adaptive capacity adjustment control scheme. In particular, we show that a purely blocking-based capacity adjustment control scheme can be very sensitive to capacity changes, and can lead to network instability.

This paper studies the ordering properties of quality of serve (QoS) measures and their rendered values in multi- class QoS provision system when generalized processor sharing (GPS)-based packet scheduling is employed at routers. GPS has been proposed as a building block for providing multiple service classes with differentiated services to applications with diverse QoS requirements. Previous works have concentrated on finding algorithms and implementations that faithfully approximate the fairness properties of GPS with some work done on deriving performance bounds when leaky-bucket traffic shaping is applied at traffic sources.

Non-renewal processes are relevant in queueing analysis to include various types of traffic arising in integrated services communication networks. We consider a workload based approach to the single server queue in discrete time domain with semi-Markov arrivals (SMP/G/1). Starting from a subdivision of the busy periods, we generalize a computationally attractive algorithm for the discrete time GI/G/1 queue. The stationary distributions of the waiting and idle time as well as the moments of the busy period are computed. Performance results are given for deterministic servers with autoregressive input and the output process of a server is modeled by adapting a SMP of small size.

A novel model for simulating aggregate network traffic is proposed. Our model, besides reflecting self-similarity and long-range dependence, it is able to capture the appropriate level of burstiness of different types of traffic by selecting the proper parameters. Different types of self- similar traffic traces are analyzed by estimating their self-similarity coefficient H, as well as the parameters of their marginal distributions. When comparing the real traces with our artificial traces, the agreement, which was evaluated both qualitatively and quantitatively, is better than the achieved with previously proposed models. By analyzing different types of traffic traces, the model is shown to be flexible enough to be applied to simulate a variety of communications scenarios. A queue with our proposed traffic as input is analyzed. A proof of convergence of aggregate traffic to alpha-stable processes is also included, as well as the conditions under which the Gaussian assumption is appropriate.

Measurements of file sizes transported on the WWW have led some researchers to propose describing them by probability distributions with infinite variance. The M/G/1 queue often arises as a performance model for components of the WWW, and the service times correspond to file sizes; the infinite variance of the file sizes becomes the variance of the service times. In this paper the effects of very large service-time variance on some performance measures for the M/G/1 queue are explored via numerical examples and analytic arguments.

In telecommunication networks, the correlated nature of teletraffic patterns can have significant impact on queuing measures such as queue length, blocking and delay. There is, however, not yet a good general analytical description which can easily incorporate the correlation effect of the traffic, while at the same time maintaining the ease of modeling. The authors have shown elsewhere, that the covariance structures of the generalized Interrupted Poisson Process (GIPP) and the generalized Interrupted Bernoulli Process (GIBP) have an invariance property which makes them reasonably general, yet algebraically manageable, models for representing correlated network traffic. The GIPP and GIBP have a surprisingly rich sets of parameters, yet these invariance properties enable us to easily incorporate the covariance function as well as the interarrival time distribution into the model to better matchobservations. In this paper, we show an application of GIPP and GIBP for matching an analytical model to observed or experimental data.

This paper proposes and investigates a protocol or real-time multicast applications called MSR. Two essential features in MSR are its traffic shaping and scalable retransmission schemes. To minimize packet loss and delay in the network, MSR spaces out the transmission of bursty data at the source. Reliability is further enhanced with a scheme in which the receivers make use of NAC messages to request for retransmission of packets from the sender. To avoid the well-known NACK is issued among a group of receivers. Unlike previous multicast protocols which attempt to achieve 100 percent reliability by requiring a correct copy of a packet to reach all receivers before the retransmission process stops, a key feature in our scheme is that the level of reliability can be scaled in accordance with the maximum tolerable end-to-end delay, defined as the difference between the instant at which the real-time data must be presented to the user and the instant at which it is created at the sender. MSR attempts to make optimal use of measured parameters such as delay, round-trip delay, loss rate, etc. to scale the retransmission process and provide single NACK mechanism. We adopt the framework of the standard RTP and RTCP for the implementation of MSR. This paper present a proof to show that the time-out mechanism in MSR, which is required to effect retransmission request, would work even if the clocks of the sender and receivers are not synchronized, a situation not uncommon in the Internet. Many multimedia streaming protocols currently used on the Web either uses a 100 percent reliable protocol like TCP or unreliable protocol like UDP. The former sacrifices the 'real-timeness' and the latter sacrifices the quality of the presentation. Our rough performance analysis indicates that there is perhaps a better intermediate solution using a scalable protocol like MSR.

A cooperative reliable multicast protocol (CRMP) has been developed to improve real-time data transmission on the Internet Multicast Backbone by adding a retransmit server and some repair servers to the multicast session in order to recover lost packets. This paper describes a design and implementation of CRMP with local recovery (L-CRMP), an extension to the original CRMP. In L-CRMP each repair server can work as a local server that retransmits packets to other repair servers that do not receive them from the source. Our goal in L-CRMP is to reduce the network overhead caused by retransmission packets while keeping the effective loss rate at the receivers approximately the same.

Many multicast ATM switch architectures have been proposed which differ greatly in the method in which replication of cells is handled. Depending on the switch architecture, the processing overhead incurred due to the cell copy function may be non-negligible. We develop a queuing model for a multicast switching node which accounts for this overhead. In the model, the source sends some number of duplicate cells, each of which is replicated at the switch to yield the total number of required copies. We use constrained optimization to determine the optimal amount of source duplication which minimizes the mean response time of the system. It is found that higher resource duplication is favored when the copy function overhead is comparable to the service time of a single cell. The model is then enhanced to account for errors and retransmission for reliable multicast.

Performance studies of ATM switches typically consider the binomial distribution to model the traffic behavior at the input of the switch. For instance, the basic knockout principle for the packet loss performance measure, has been solved by considering the binomial assumption in most of the cases. In this paper, we have found that the binomial distribution remains essentially valid for modeling MPEG video traces at the input of the switch, however, in video- on-demand applications with multicasting, the binomial assumption is no longer valid. In this case we have found that the beta-binomial model for the knockout switch gives a better cell loss performance prediction.

In this paper, we study the multicast routing problem in broadband networks. The multicast routing problem, also known as the Steiner tree problem, has been well studied in the literature. However, less attention has been made for the definition of link costs and evaluating the performance of multicast routing algorithm from the network revenue point of view. Therefore, in this paper, we examined three approaches for defining link costs, namely, the Markov Decision Process-based (MDP), the Competitive On-Line (COL) routing-based and the linear-based approaches. Two heuristic multicast algorithms, TMR and MSPF. were developed for investigating the performance of these approaches. We proposed a new performance metric, referred to as the fractional reward loss, to evaluate the multicast routing algorithm. Performance of the multicast algorithms under different link cost functions was evaluated via simulations on a 20-node random graph. Our simulation results indicated that the way of defining link costs affects the performance of the multicast routing algorithms significantly and the best performance is yielded when using the MDP-based link costs.

Study of long-range dependence (LRD) properties in real traffic has received an increasing attention in traffic analysis. A wavelet-based tool for the analysis of LRD is presented in this paper together with a semi-parametric estimator of the Hurst parameter. The estimator has been proved to be unbiased under very general conditions and efficient under Gaussian assumptions. Analysis of the Bellcore Ethernet traces as well as some VBR video traces using the wavelet-based estimator is reported.

This paper presents a low-cost hardware and software system that can be used to monitor ATM cell flows, and to make absolute measurements of ATM cell arrival times. The system uses a purpose-built ATM cell capture board in a standard LINUX PC, with a GPS time receiver to provide an accurate time reference. The systems can be used locally, or can be operated remotely, sending its results back to a central point over a network connection. As well as cell arrival times, the system computes a 32-bit signature for each cell payload. This enables the recognition of cells in different parts of the network, the measurement of cell transit time, and the detection of cell loss. Results are presented of measurements made on local and wide area ATM networks, and on the intercontinental Internet.

The GFR service category has been proposed for data services in ATM networks. Since users are ultimately interested in data service that provide high efficiency and low latency, it is important to study the latency performance for data traffic of the GFR service category in an ATM network. Today much of the data traffic utilizes the TCP/IP protocol suite and in this paper we study through simulation the latency of TCP applications running over a wide-area ATM network utilizing the GFR service category using a realistic TCP traffic model. From this study, we find that during congestion periods the reserved bandwidth in GFR can improve the latency performance for TCP applications. However, due to TCP 'Slow Start' data segment generation dynamics, we show that a large proportion of TCP segments are discarded under network congestion even when the reserved bandwidth is equal to the average generated rate of user data. Therefore, a user experiences worse than expected latency performance when the network is congested. In this study we also examine the effects of segment size on the latency performance of TCP applications using the GFR service category.

Asynchronous transfer-mode (ATM) is the technology chosen for implementing the broadband integrated services digital network. The performance of internet protocols over ATM is an extremely important research area. As web traffic forms a major portion of the Internet traffic, we model WWW servers and clients running over an ATM network using the available bit rate (ABR) service. The WWW servers are modeled using a variant of the SPECweb96 benchmark, while the WWW clients are based on a model proposed. The traffic generated is typically bursty, having active and idle transmission periods. A timeout occurs after a certain idle interval. During idle periods, the underlying TCP congestion windows remain large until the timer expires. This raises the possibility of large queues at the switches, if the source rates ar not controlled by ABR. We study this problem and show that ABR scales well to a large number of bursty TCP sources in the system.

ABT is promising for effectively transferring a highly bursty data traffic in ATM networks. Most of past studies focused on the data transfer capability of ABT within the ATM layer. In actual, however, we need to consider the upper layer transport protocol since the transport layer protocol also supports a network congestion control mechanism. One such example is TCP, which is now widely used in the Internet. In this paper, we evaluate the performance of TCP over ABT protocols. Simulation results show that the retransmission mechanism of ABT can effectively overlay the TCP congestion control mechanism so that TCP operates in a stable fashion and works well only as an error recovery mechanism.

ATM is a connection oriented network while IP is based on a connectionless protocol. Connecting the two networks requires protocol conversion. When IP packets arrive at the interconnection between the two networks, signalling is used to open a switched virtual circuit on the ATM side. In this paper, we look at the management of the ATM connection with a view to reducing the cost of the connection. We develop and compare the cost functions of three connections management policies: the delayed vacation policy, the control operating policy and the permanent virtual circuit. Furthermore, we have developed the conditions under which the control operating policy (COP) will be more cost effective than the other two policies. We conclude that there always exists some condition under which the COP will be better than the other two policies.

Cell Loss Ratio estimation is a crucial technology in call admission control and traffic engineering in ATM networks. Cell arrival process and analytical approach had been investigated in recent years. However, an effective and practicable CLR estimator is still a challenge. Based on the analysis of cell loss problem, an improved simple traffic model and a new algorithm are presented in this paper, to estimate CLR of ATM network multiplexed with heterogenous traffic classes services rapidly. Traffic model is constructed with standard parameters, so it is easy to use in practical situations. The new algorithm runs quickly enough to respond the call real-time. Simulation results show that accuracy, complexity and robustness of algorithm are ideal to be utilized in real network.

We present a queuing model for an ATM multiplexer with unequal input/output link capacities in this paper. This model can be used to analyze the buffer behaviors of an ATM multiplexer which multiplexes low speed input links into a high speed output link. For this queuing mode, we assume that the input and output slot times are not equal, this is quite different from most analysis of discrete-time queues for ATM multiplexer/switch. In the queuing analysis, we adopt a correlated arrival process represented by the Discrete-time Batch Markovian Arrival Process. The analysis is based upon M/G/1 type queue technique which enables easy numerical computation. Queue length distributions observed at different epochs and queue length distribution seen by an arbitrary arrival cell when it enters the buffer are given.

In this paper, we purpose a novel approach to analyze exact cell loss probability of Shared Buffer ATM switch. In a N X N ATM switch whose input ports and output ports share one buffer, the number of arriving cells from input ports at one time slot is less than or equal to N. If these cells were destined to n output ports, no cells will be destined to the remaining N-n output ports. In the extremism, all arriving cells were destined to one output port, no cell will be destined to the other N-1 output ports. So, the arriving cells at each time slot from the input ports are destined to the output ports correlatively, but not independently. For this reason, the analyzing result on the assumption that all output cell queues are independent one another is larger than actual result. We complete our analysis by three steps. First, considering the case that there are cells arriving from input ports but not cells remove from output ports, we can get one-step state transition probability matrix P_a; Second, considering the case that there are cells removing from output ports but not cells arrive from input ports, we can get one-step state transition probability matrix Ps; Third, considering arrival process and service process are independent, the accurate one-step state transition probability matrix P of cell's number in the buffer is derived, and then cell queue length steady probability distribution can be found. We can compute the accurate buffer capacity below certain cell loss probability. Computer simulation proves that the approach is efficient and exact.