Download the dissertation in PS, PDF (1 page per sheet) or PS, PDF (2 pages per sheet)
All the comments are welcome.
In the recent years, Internet has become the standard network infrastructure to allow a global communication in the world. Now Internet is not only world-wide, but it is also ``content-wide'' since it supports a very large number and variety of communication services.
Born as a research and university network, providing basic services like e-mail and file transfer, Internet has been growing at an exponential rate. Important research and commercial efforts have supported this expansion. Furthermore, a ``new-economy'' has arisen to exploit the possibilities of this new mean of communication, able to reach a lot of people in the world at low costs. Lately, Internet has also changed the communication habits of millions of people, nowadays familiar with sending e-mails and with browsing the World Wide Web (WWW). During the last couple of years, Internet has been proposed also as a feasible alternative to the Public Switching Telephony System (PSTN), through transport services like ``Voice Over IP''.
The American economical crisis during 2001 has shown also the limit of Internet as mean of business. Internet was initially designed as a low cost and global communication mean, but its intrinsic features seem now to limit its scalability in terms of dimension, services and business. For example, Internet is a ``best-effort'' network; this implies that service provides cannot ask users to pay a significant fee, given that the quality of service over time is not guaranteed. On the contrary, advanced communication systems, like video and audio distribution, require a minimum guaranteed level of service quality to be practical. In general, whenever the network can accommodate the communication requirements of ``Quality-of-Service'' (QoS), Internet will improve its business potentials.
Starting from its birth, several technical considerations rose doubts that Internet would have collapsed after few years, due to the very large number of users and the constantly growing traffic. Internet is a packet switched network based on the ``statistical multiplexing'' paradigm, which means that the resources are shared among users and not dedicated. Hence, Internet could collapse if the offered traffic would become greater than the traffic that the available resources are able to serve. Since no ``admission control'' mechanism is adopted to limit user traffic, this risk is real. Several solutions have been envisaged to deal with this foreseen collapse. One solution is a more thoughtful design of the network architecture, maybe exploiting some fair resource sharing and admission control systems. Another solution is the continous increase of communication links and switching systems, to increase the overall bandwidth available in the network.
The main topic of my Ph.D. work has been the design of high performance switching systems, able to accommodate the exponential traffic growth in Internet by guaranteeing high throughput.
Internet is a very large packet switched network, built around a large variety of transmission and switching systems. The information to transfer through the network is aggregated into packets; each packet is individually forwarded and switched towards its destination through the packet switching systems.
The most important switching systems in Internet are the routers. The main tasks of a router are to receive the packets from input ports, to find their local destination port on the basis of the routing table (built by exchanging information related to network topology through routing protocols) and finally to transfer the packets to output ports. These two basic functions, routing and switching, are very difficult to implement when the aggregate bandwidth is very large, since complex algorithms should run in a very short time. Furthermore, routers must deal with different link technologies, must distribute routing tables and can provide packet classification and filtering services. For all these reasons, high performance routers are very complex systems, whose design is more and more pushed to the edge of the latest technology.
Being able to design high performance routers is particularly important, given that today's Internet is composed by a relative small number of very fast backbone networks, which connect a very large number of smaller networks. Backbone links rates are evolving from today's OC-48 (2.5 Gbps) to OC-192 (10 Gbps) and even OC-768 (40 Gbps), with a rate of increase of about 30% per year. This means that, for a minimum size TCP/IP packet of 40 bytes, the number of packets to be processed is evolving from 8 to 32 and even 125 million of packets/s. So the average time spent to elaborate a single packet (doing at least routing and switching) is decreasing from 125 ns to 30 ns and even 8 ns: hence, the switching process at high speed must be implemented in hardware.
This Ph.D. dissertation is on the design of high performance routers with a very large aggregate bandwidth. Different switching architectures can be employed in high performance routers. This studies focuses mainly on one of the most promising switching architecture, with packet buffers at input ports; this architecture will be introduced in Section 2.2.2 and discussed deeply in Chapter 3.
For very fast switching architectures with buffers at input ports, the main performance bottleneck is given by the scheduler module, which selects the packets to transfer through the switching fabric. In this dissertation it will be discussed mainly the problem of designing very efficient scheduling algorithms, which show very good performance and can be implemented in hardware. The scheduler architecture will be discussed only from the algorithmic point of view, independent from any particular electronic technology to implement it.
The main topics and results discussed in this dissertation are the following:
This Ph.D. dissertation is organized into chapters. Chapter 2 discusses the main design issues involved in designing high performance IP routers and motivates the need for high performance switching fabrics. It introduces the main features of different categories of routers and also highlights some of the most significant bottlenecks in their performance. In addition, it provides a taxonomy of the switching fabrics.
Chapter 3 describes deeply the problem of scheduling. It is a sort of preface to all the subsequent chapters, since it describes the methodological approaches (based mainly on the performance analysis through simulations and stochastic modeling) to study the scheduling problem. The final part of that chapter recalls some well-known results of stochastic modeling, essential to understand the theoretical modeling approach used in the other chapters.
Chapters 4, 5 and 6 discuss respectively each of the three main topics of our research work, presented earlier in this section. Each chapter motivates the outlined approach, comparing it with results known in literature. The approach is then described and its performance are discussed first by theoretical models and then with simulation studies.
After the conclusions and the bibliography, an appendix reports some of the proofs which were skipped in the main context of this dissertation for an easier reading.