Αλγόριθμοι χρονοδρομολόγησης για δρομολογητές υψηλών επιδόσεων

Abstract

This dissertation deals with the design of scheduling algorithms for high-speed switches. The analysis focuses on the Input-Queue Cell-Switch architecture, which is the most promising in terms of scalability for speed and number of router ports. After describing the main problems in the design of such devices and the critical role that the scheduling algorithm plays, it is proven that the scheduling problem is a problem of ?nding a matching in a bipartite graph. Also, the main tools of the analysis, simulations and stochastic modelling, are presented. So far, the algorithms in the area were either simple in their implementation, but with poor results, or too complex with better performance. The dissertation presents a series of new algorithms based on the study scheme that, while being less complex, they maintain very high performance levels. The main ideas used were the observation of previous matchings, randomization, observation of arrivals and parallel processing. In today's Internet, data comes in the form of variable sized packets, while the switch would have better performance if ?xed sized cells were to be used. The dissertation proposes the use of scheduling algorithms for cell- switches, with some modi?cations, in packet-switches. It is proven that these algorithms, although they are designed for cell-switches, operate without problems as far as throughput and delay are concerned in a packet-switching environment.