A GUARANTEED-NO-CELLS-DROPPED BUFFER MANAGEMENT SCHEME WITH SELECTIVEBLOCKING FOR CELL-SWITCHING NETWORKS

Fundamentally, the inclusion of bursty traffic, the desire to achieve a cost-effective network design, i.e. to obtain maximum throughput in a given network while minimizing cell loss, and the limitation of maxi mum buffer size, derived from basic digital design principles, lends s ignificant importance to the issue of buffer management in cell switch ing networks including ATM networks. The buffer management literature is rich and includes reports on improved network performance through p riority schemes, fixed thresholds, admission control, buffer partition ing, fuzzy thresholds, fuzzy rule-based congestion and admission contr ol, fuzzy policing mechanisms, and a shared memory buffer for all outp ut ports of a switch subject to a delayed pushout scheme. While highly effective, these techniques suffer from two key weaknesses. First, th ey are susceptible to cell loss owing to buffer overflow. Second, the performance reported for all of these schemes have been obtained for a single switch and, consequently, the results are not necessarily appl icable to a realistic cell-switching network consisting of multiple sw itches. This paper presents a novel scheme-guaranteed-no-cells-dropped (GNCD), that eliminates cell loss owing to buffer overflow. In this a pproach, the switching node first records the current buffer occupancy and then determines the absolute number of empty slots. It then admit s from the input cell-burst from other switches an exact number of cel ls equal to the number of empty slots. The remainder of the cells are blocked at the sending switch. The computation involved in the decisio n to admit or refuse entry into the buffer is simple and fast-a key ad vantage for high-speed networks. Further, buffer overflow is eliminate d implying no cell loss-a key potential advantage for specific traffic classes in ATM. Although the fuzzy thresholding-based buffer manageme nt scheme holds a significant potential, according to the literature, to effectively reduce cell loss owing to buffer overflow, GNCD achieve s in eliminating cell loss owing to buffer overflow completely. Althou gh the fate of a large fraction of the blocked cells, caused by excess traffic, is similar to that in the fuzzy scheme, it is logical to ass ume that the prevention of cell loss owing to buffer overflow manifest s through increased blocking. GNCD includes an effort to reroute the c ells, constituting the increased blocking, to their eventual destinati ons. Clearly, these rerouted cells may incur delays and cause other ce lls in the network to suffer additional delays. Thus, the absolute cur rent buffer occupancy and the size of the incoming cell-burst constitu te the basis for admitting or blocking cells into the buffer. The GNCD scheme is modeled for both: (1) a single, stand-alone switch to facil itate a meaningful comparison with other competing approaches in the l iterature; and (2) a 50-switch, representative cell-switching network to study its performance under realistic conditions. Both models are s imulated, the first on a uniprocessor computer and the second on a tes tbed consisting of a network of 25 + Pentium workstations under linux, configured as a loosely coupled parallel processor. For the simulatio n of model i, a representative traffic stimulus, characterized by a tw o-state, 'on-off Markov chain model and exponentially distributed depa rtures, is utilized. A comparative analysis of the results reveal that the GNCD scheme yields a slightly higher throughput than the fuzzy sc heme while ensuring zero cell loss owing to buffer overflow, over a ra nge of values of input cell arrival rates. Performance results also in dicate that, contrary to the general expectation that large buffers wi ll enhance throughput and mitigate congestion, the throughput and bloc king behavior of the GNCD scheme are unaffected by increasing the buff er capacity beyond a 'critical buffer size'. For the simulation of mod el 2, the input traffic distribution consists of a total of 1.0-1.5 mi llion cells that are asserted into the network for each experiment, wi th the video traffic synthesized from an actual movie in MPEG-1, the a udio traffic obtained using an ON/OFF model utilizing parameters extra cted from an actual voice segment, while the generator for the data tr affic utilizes a Markov chain model, subject to traffic shaping. The r esults corroborate those in model 1 in that, even for a large-scale re presentative cell-switching network, the throughput is higher and bloc king is lower under GNCD than for the fuzzy thresholding approach, ove r a range of input traffic distributions corresponding to throughputs of 73-91%, although the difference in the throughputs and blocking are negligibly small for both low and high values of input cell arrival r ates. At either extremes of the input cell arrival rate values, the be haviors of both GNCD and fuzzy thresholding are similar. However, whil e the cell loss owing to buffer overflow is nil, the average delay inc urred by the cells in the network are higher for GNCD than the fuzzy a pproach, for the same range of input traffic distributions, by a facto r ranging from 1.43 for relatively light input traffic density to 1.92 for moderate input traffic to 0.93 for heavy traffic. This paper note s that GNCD incurs less blocking than the fuzzy scheme and that the fu zzy scheme incurs cell loss through buffer overflow, and argues conser vatively that the cells lost through buffer overflow in the fuzzy sche me manifest through increased blocking at the sending switches and tha t effort must be expended to reroute them to their respective destinat ions. Under these circumstances, the average delay incurred by the cel ls in the network is higher for GNCD than the fuzzy scheme by a factor ranging from 2.5 for relatively light input traffic density to 5.72 f or moderate input traffic to 1.6 for heavy traffic. (C) 1998 Elsevier Science B.V.