WASHINGTON UNIVERSITYSEVER INSTITUTE OF TECHNOLOGYPERFORMANCE EVALUATION OF ASYNCHRONOUSTRANSFER MODE SWITCHING SYSTEMSbyEINIR VALDIMARSSONPrepared under the direction of Professor Jonathan S. TurnerA thesis presented to the Sever Institute ofWashington University in partial fulfillmentof the requirements for the degree ofDOCTOR OF SCIENCEDecember, 1994Saint Louis, MissouriWASHINGTON UNIVERSITYSEVER INSTITUTE OF TECHNOLOGYABSTRACTPERFORMANCE EVALUATION OF ASYNCHRONOUSTRANSFER MODE SWITCHING SYSTEMSby EINIR VALDIMARSSONADVISOR: Professor Jonathan S. TurnerDecember, 1994Saint Louis, Missouri The design of switching systems is an important and active research area because it is essen-tial to the success of broadband communication systems. The work presented in this thesis pro-vides models that evaluate the performance of high speed Asynchronous Transfer Mode switchingsystems. These models help to evaluate the design trade-offs in switching systems needed to sup-port current and future communication needs.The work has two parts. The first part provides new analytical models for buffered switchingnetworks. Specifically, models for copy networks with various buffer schemes and a model forshared buffer Benes network with non-uniform traffic are presented. Our results show that themodels are accurate for single stage networks, and close approximations for multistage networks. The second part of the work focuses on the development and use of simulation models ofswitching systems. Such simulation models are necessary, due to the limitations of analytical mod-els, and can provide valuable information on many complex switching systems. To make evalua-tion and design of such systems easier and to gain a better understanding we have designed andimplemented an efficient tool for evaluating switching systems. The tool is general enough toallow performance evaluation of a variety of different switching architectures. The novel aspectsof the tool include easy network construction and interaction, and visualization and animation ofnetwork state and statistics.We have used the models provided by the simulation tool to compare various switching sys-tems in terms of cell loss probability, cell delay, and complexity required to obtain certain perfor-mance requirements. Finally, we have used the tool to examine the transient behavior of sharedbuffer Benes systems and we have obtained new insights about the congestion conditions in thenetwork.copyright byEinir Valdimarsson1994iiiTABLE OF CONTENTSPageLIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiLIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiCHAPTER1 INTRODUCTION 1Motivation and Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 BROADBAND ATM SWITCHING 5Asynchronous Transfer Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Switching Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Switching Network Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Performance Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Switching Network Architectures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Single stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Unbuffered networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Buffered networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26Multicast Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 QUEUEING ANALYSIS OF BUFFERED COPY NETWORKS 34Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Model Assumptions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36ivModel of Copy Switch Elements. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Output Buffer Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Shared Virtual Output Buffer Model . . . . . . . . . . . . . . . . . . . . . . . . . 42Shared Buffer Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …