Flexible Scheduling Discipline for Fixed-Size-Packet Switched Networks
Tamás Marosits, Sándor Molnár · 2007
How to provide Quality of Service is one of the main question in the recent and future internet. The wide variety of services demand granularity while the huge amount of traffic require robustness and simplicity in traffic control (e.g., call acceptance, routing, scheduling). In our previous work ([1]) the Advanced Round Robin (ARR) scheduling algorithm for fix packet length packet switching networks was introduced. As its name suggests ARR is a round robin-type scheduling method in which every connection has its own buffer and there is a known time limit between the service opportunities of these buffers. The main difference is that queues in ARR may be served more than once in a cycle and the access periods of a flow are uniformly distributed during the service cycle. Considering the architecture of ARR scheduler we can easily formulate worst case delay and the maximum difference between successive packet departures of the flows. Moreover, if we know the arrival process of the connections even average delay and average difference between successive packet departures can be given. The above mentioned results are based on the consideration, that we already have an optimal organized service cycle in which the service opportunities of a connection are uniformly distributed in the service cycle. Obviously, this can not be made for every possible combination of traffic parameters and service requirements if we want to have a work conserving scheduler. However, we can build suboptimal service cycles and can examine the difference between the optimal and the suboptimal solutions. In this paper we present some further important features of ARR. These features make it possible to locate ARR in the broad list of known schedulers. As several well known scheduling algorithms do belong to the class of Latency Rate servers (described in [3]) also does ARR which will be shown in this paper. According to the characterization of LR servers new bounds can be given for the ARR, however these bounds might be looser then those which were evaluated based on the architecture of ARR. The ARR can be also characterized as a Guaranteed Rate server and we calculate the error term to this characterization. We show that ARR is in the class of Latency Rate servers, therefore all results of LR-servers can be applied for ARR. We also show the connection between ARR and Generalized Processor Sharing (GPS) discipline. Presenting the relationship between ARR and GPS we will be able to take full advantages of results achieved in connection of GPS: for example new worst case guarantees can be formulated for single node case and a multi-node ARR-scenario can be easily analyzed taking into account the results can be found in the literature (e.g., [4], [2], [5]). Moreover, we also present the fairness-index of ARR which is one of the most important feature of schedulers. Calculating the fairness of ARR it become comparable to the known schedulers and the applicability of the method will be obvious. These results can provide a good guideline framework for designers to apply ARR and calculate its parameters and performance.