E-Locus - Institutional Repository of the University of Crete - Δίκαιος χρονοπρογραμματισμός μεγίστου-σταθμισμένου-ελαχίστου, για ένα με ουρές αποθήκευσης στις εισόδους και μικρούς εσωτερικούς ενταμιευτές

Home Δίκαιος χρονοπρογραμματισμός μεγίστου-σταθμισμένου-ελαχίστου, για ένα με ουρές αποθήκευσης στις εισόδους και μικρούς εσωτερικούς ενταμιευτές

Results - Details

[Add to Basket]

Identifier

uch.csd.msc//2002chrysos

Title

Δίκαιος χρονοπρογραμματισμός μεγίστου-σταθμισμένου-ελαχίστου, για ένα με ουρές αποθήκευσης στις εισόδους και μικρούς εσωτερικούς ενταμιευτές

Alternative Title

Weighted Max-Min Fair Scheduling, for a Crossbar, with Small Internal Memory

Author

Χρυσός, Νικόλαος Ιωάννη

Thesis advisor

Κατεβαίνης, Μανόλης

Abstract

Switches play a pivotal role in the design of high performance networks; thus, they have to be efficient and inexpensive. Input buffered switches require the memories to run at just twice the line rate, thus demonstrating very good scalability. However, they also need a centralized scheduler that configures their crossbar so that, at any given time, non-conflicting packets are forwarded; the complexity of this scheduler increases considerably with switch size. Moreover, it is doubtful whether such an architecture can provide sophisticated QoS guarantees without sacrificing switching capacity. By contrast, the scheduling task is dramatically simplified if small buffers are included at each crosspoint of the crossbar. In this thesis we analyze such a buffered crossbar architecture which allows distributed scheduling: distinct servers at each input and output collectively but still independently schedule the set of flows through the interconnect. The input and output servers implement Weighted Round Robin (WFQ-like) scheduling and are loosely coordinated through backpressure signals from the crosspoint buffers. We study how close this system approximates the ideal weighted max-min fair allocation. We provide extensive simulations and preliminary analytical hints indicating that our scheme converges to such a fairness objective. In addition, we study convergence time and we quantify the unfairness during the convergence process. We also study saturation throughput under various assumptions on the form of traffic. Although even a buffer space of one cell suffices for the scheduling operation, a buffer size of 4 to 5 cells per crosspoint yields excellent performance, at least for switches up to 32x32.

Language

Greek

Issue date

2002-07-01

Collection

School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses

Type of Work--Post-graduate theses

Views

436

Digital Documents
	Download document View document Views : 8