Benes switching fabrics with O(N)-complexity internal backpressure

Multistage buffered switching fabrics are the most efficient method for scaling packet switches to very large numbers of ports. The Benes network is the lowest-cost switching fabric known to yield operation free of internal blocking. Backpressure inside a switching fabric can limit the use of expensive off-chip buffer memory to just virtual-output queues (VOQ) in front of the input stage. This paper extends the known backpressure architectures to the Benes network. To achieve this, we had to successfully combine per-flow backpressure, multipath routing (inverse multiplexing), and cell resequencing. We, also, present a flow merging scheme that is needed to bring the cost of backpressure down to O(N) per switching element. We prove freedom from deadlock for a wide class of multipath cell distribution algorithms. Using a cell-time-accurate simulator, we evaluated various cell distribution and resequencing methods, we found that delay under bursty traffic is only 25 to 50 percent higher than ideal output queueing, and we showed that the delay of well-behaved flows remains unaffected by the presence of congested traffic to oversubscribed output ports. Using simplified models of the Benes fabric, we show that cell distribution does not result in throughput limitations, and identify the points of the fabric where contention is resolved.Τα πλέγματα μεταγωγής με πολλαπλά στάδια και εσωτερικούς ενταμιευτές είναι η πιο αποδοτική μέθοδος για την κλιμάκωση των μεταγωγέων πακέτων σε πολύ μέγαλο αριθμό από πόρτες. Το δίκτυο Benes είναι το χαμηλότερου κόστους πλέγμα μεταγωγής που επιτρέπει λειτουργία χωρίς εσωτερική φραγή (internal blocking). Η αναδραστική πίεση (backpressure) εσωτερικά στο πλέγμα μεταγωγής μπορεί να περιορίσει την χρήση ακριβών off-chip ενταμιευτών μνήμης μόνο στις εικονικές ουρές εξόδου (VOQ) μπροστά από το στάδιο εισόδου. Η παρούσα εργασία επεκτείνει τις γνωστές αρχιτεκτονικές backpressure στο δίκτυο Benes. Για να επιτευχθεί αυτό, έπρεπε να συνδυάσουμε επιτυχώς το backpressure ανά-ροή, τη δρομολόγηση μέσω πολλαπλών μονοπατιών (αντίστροφη πολυπλεξία), και την επαναδιάταξη κελιών (cells). Επίσης, παρουσιάζουμε ένα σχήμα συγχώνευσης ροών το οποίο χρειάζεται για τη μείωση του κόστος του backpressure σε O(N) ανά στοιχείο μεταγωγής. Αποδεικνύουμε ανυπαρξία αδιεξόδων για μια μεγάλη κλάσση από αλγορίθμους δρομολόγησης μέσω πολλαπλών μονοπατιών. Με τη χρήση προσομοιώσεων με ακρίβεια cell time, αξιολογήσαμε διάφορες μεθόδους για την κατανομή και επαναδιάταξη των cells, βρήκαμε ότι η καθυστέρηση για εκρηκτική κίνηση είναι μόνο 25 εώς 50 τοις εκατό υψηλότερη από το ιδανικό σύστημα με ουρές στις εξόδους, και δείξαμε ότι η καθυστέρηση των μη-συμφορημένων ροων παραμένει ανεπηρέαστη από την παρουσία συμφορημένης κίνησης προς ορισμένες πόρτες εξόδου. Με τη χρήση απλοποιημένων μοντέλων για το πλέγμα Benes, δείχνουμε ότι η κατανομή των cells δεν δημιουργεί περιορισμούς στην διαπερατότητα, και εντοπίζουμε τα σημεία του πλέγματος όπου επιλύονται οι συγκρούσεις μεταξύ των cells