From: George Stamoulis <gstamoul@csi.forth.gr>
To: hy534-list@csd.uch.gr
Subject: Seira Thewtirikwn Askisewn
Date: Thu, 9 Apr 1998 08:48:47 +0300 (EET DST)


Τμήμα Επιστήμης Υπολογιστών 
ΗΥ534 : Αρχιτεκτονική Μεταγωγής Πακέτων 
9 Απριλίου 1998
Μ.Κατεβαίνης/Δ.Σερπάνος/Γ.Δ.Σταμούλης 

Σειρά Ασκήσεων στα Δίκτυα Non-blocking

Ημερομηνία Παράδοσης: 28 Απριλίου 1998


1)    Η άσκηση αυτή αναφέρεται στο δίκτυo Banyan με  περιττό πλήθος 
      Μ επιπέδων. Οπως απεδείχθη κατά την σχετική διάλεξη 
      υπάρχει μία μετάθεση κατά την δρομολόγηση της οποίας, κάποιοι 
      από τους σύνδεσμους του μεσαίου 
      επιπέδου (M-1)/2 πρέπει να δρομολογήσουν sqrt(N/2) (ρίζα Ν/2)
      πακέτα. Να αποδείξετε ότι αυτή η συμφόρηση είναι η 
      *χειρότερη* δυνατή. Μπορείτε να υποδείξετε κάποια άλλη 
      μετάθεση που να έχει την ίδια συμφόρηση σε ορισμένους συνδέσμους ? 

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

3)    Να δρομολογήσετε *non-blocking* την εξής μετάθεση στο δίκτυο Benes
      8 κόμβων: 
       0 --> 3 
       1 --> 6 
       2 --> 5
       3 --> 0
       4 --> 2
       5 --> 7
       6 --> 4
       7 --> 1
      Κατόπιν, να εξετάσετε πώς πρέπει να γίνει η δρομολόγηση 
      αν οι κόμβοι εισόδου 0 και 3 ενάλλαξουν αμοιβαία προορισμούς.