CS-534: Packet Switch Architecture
Fall 2001		 Department of Computer Science
© copyright: University of Crete, Greece

Exercise Set 10:
Switching Fabric Topologies

Assigned: 2001-12-07 (week 11) -- Due: 2001-12-14 (week 12)

10.1 Internal Blocking σε Banyans

Η άσκηση αυτή αναφέρεται σε ένα δίκτυο Banyan με Ν εισόδους και περιττό πλήθος Μ επιπέδων. Αποδείξετε ότι υπάρχει μετάθεση, κατά την δρομολόγηση της οποίας, κάποιοι από τους μεταγωγής του μεσαίου επιπέδου πρέπει να δρομολογήσουν sqrt(N/2) cells (τετραγωνική ρίζα του Ν/2 πακέτα). Αποδείξετε ότι αυτή η συμφόρηση είναι η χειρότερη δυνατή και δώσετε τουλάχιστον ένα παράδειγμα μεταθέσεως που την προκαλεί.

10.2 Permutation Routing σε Buffered Banyans

Βασιζόμενοι στην προηγουμένη άσκηση, να αποδείξετε ότι τα πακέτα οποιασδήποτε μεταθέσεως μπορούν να δρομολογηθούν σε χρόνο της τάξεως μεγέθους του sqrt(N) (δηλαδή της τετραγωνικής ρίζας του Ν), εφ όσον το μέγεθος ενταμιευτών στους μεταγωγείς του δικτύου Banyan είναι απεριόριστο. (Θεωρείστε ότι η μετάδοση κάθε πακέτου σε ένα σύνδεσμο διαρκεί μία μονάδα χρόνου). Ποίο είναι το μέγεθος ενταμιευτών που χρησιμοποιείται πραγματικά;

10.3 Rearrangably Non-Blocking Δίκτυο Benes

Να δρομολογήσετε σε ένα δίκτυο Benes 8 εισόδων την παρακάτω μετάθεση: Κατόπιν, να επαληθεύσετε ότι, αν οι είσοδοι 0 και 3 αλλάξουν αμοιβαία προορισμούς, τότε μεταβάλλονται αναγκαία και κάποια από τα άλλα μονοπάτια. Περιγράψετε έναν αλγόριθμο που κατασκευάζει τα μονοπάτια σε ένα δίκτυο Benes για την δρομολόγηση μιας μετάθεσης.

10.4 Δίκτυα Clos

Θεωρούμε ένα δίκτυο Clos (IN,N1,N2,N3,OUT) όπως το ορίσαμε στο μάθημα: Ν1, Ν2, Ν3 είναι ο αριθμός των μεταγωγέων στο 1ο, 2ο, 3ο επίπεδο αντίστοιχα, ΙΝ είναι ο αριθμός των εισόδων για κάθε μεταγωγέα του πρώτου επιπέδου, και OUT είναι ο αριθμός των εξόδων για κάθε μεταγωγέα του τρίτου επιπέδου. Αποδείξετε ότι αυτό το δίκτυο είναι rearangably non-blocking για:
N2 >= max(IN,OUT)
Δώστε έναν αλγόριθμο κατασκευής μονοπατιών για την δρομολόγηση μιας μετάθεσης σε ένα rearrangably nonblocking δίκτυο Clos. Θυμηθείτε τον αλγόριθμο για κατασκευή μονοπατιών στο δίκτυο Benes.

Up to the Home Page of CS-534
 		 © copyright University of Crete, Greece.
Provided by: P. Fragopoulou and G. Stamoulis.
Last updated: 7 Dec. 2001, by M. Katevenis.