του Σφήκα Ευστάθιου:

Στην εργασία αυτή υλοποιείται και παρατίθεται μια νέα δομή επεξεργασίας δεδομένων σε ένα δρομολογητή δικτύου. Τα δεδομένα που δέχεται ο δρομολογητής είναι τα πακέτα που κυκλοφορούν στο δίκτυο. Αυτά εμπεριέχουν την πληροφορία της δρομολόγησης τους , δηλαδή την πηγή δημιουργίας τους καθώς και τον προορισμό τους. Ένας δρομολογητής, εκτός από την ουδετεροποίηση (buffering), την οργάνωση (scheduling) και την μεταγωγή (switching) των πακέτων, επεξεργάζεται την πληροφορία αυτή και δρομολογεί τα πακέτα στον κατάλληλο nexthop δρομολογητή. Ένας δρομολογητής περιέχει διάφορα προθέματα διευθύνσεων με τα οποία ‘χαρτογραφεί‘ όλες τις δυνατές διευθύνσεις του Διαδικτύου. Βάσει αυτών των προθεμάτων στέλνουν το εκάστοτε πακέτο στον επόμενο δρομολογητή, ο οποίος ειδικεύεται καλύτερα σε διευθύνσεις ανάλογες με αυτήν του πακέτου, με αποτέλεσμα ύστερα από κάποιες επαναλήψεις της διαδικασίας το πακέτο να φτάνει στον προορισμό του. Ο λόγος που ένας δρομολογητής δεν μπορεί άμεσα να στείλει το εκάστοτε πακέτο στην επιθυμητή διεύθυνση είναι ότι ο αριθμός των διευθύνσεων,τόσο για το πρωτόκολλο ΙΡv4 των 32-bit διευθύνσεων, πόσο μάλλον για το ΙΡv6 των 128-bit, είναι στο σύνολό τους απαγορευτικά μεγάλος για να χωράνε όλες στον πίνακα ενός δρομολογητή (232 και 2128 αντίστοιχα). Aκόμη όμως και αν υπήρχε η δυνατότητα δημιουργίας τέτοιων μεγεθών πινάκων, κανείς δεν εγγυάται την μείωση του χρόνου αναζήτησης. Εκτός των άλλων, για την διευθυνσιοδότηση χρησιμοποιείται το CIDR σχήμα, το οποίο είναι το επικρατέστερο σχήμα, σε σχέση με προηγούμενα, που στηρίζονταν σε τάξεις (class A, B, C). Παρόλο που το CIDR επιτρέπει την μείωση του μεγέθους των πινάκων δρομολόγησης, το πρόβλημα της αναζήτησης τώρα γίνεται πιο περίπλοκο. Με το CIDR, τα προθέματα-προορισμοί στους πίνακες έχουν αυθαίρετα μήκη και δεν αντιστοιχούν σε δικτυακά μέρη εφόσον δημιουργούνται από έναν αυθαίρετο αριθμό συναθροίσεων δικτύων. Έτσι, όταν χρησιμοποιούμε το CIDR, δεν μπορούμε να στηριζόμαστε σε μεθόδους ακριβούς ταιριάσματος με κάποιο πρόθεμα, επειδή το μήκος του προθέματος δεν μπορεί να εξαχθεί μόνο από το κομμάτι της διεύθυνσης. Συνεπώς, η λήψη απόφασης για μια τέτοια κατάσταση δεν περιέχει μόνο σύγκριση των bits ένα-ένα, αλλά και εύρεση του μήκους. Επομένως μιλάμε για αναζήτηση σε δύο διαστάσεις: τιμή και μήκος.

Eπομένως, στόχος μας κατά την δημιουργία ενός αλγορίθμου routing για έναν δρομολογητή, είναι να μπορέσουμε να κάνουμε (κυρίως) ανταγωνιστική αναζήτηση, αφού κάτι τέτοιο ζητείται κατά το μεγαλύτερο βαθμό κατά την δρομολόγηση. Η παρούσα δομή είναι μια υβριδική δομή δεδομένων, η οποία αποτελείται στα πάνω επίπεδα από συμπιεσμένα δυαδικά tries (multibit tries) και στα κάτω επίπεδα από ειδικά διαμορφωμένα για την αναζήτηση διευθύνσεων splaytrees (self adjusting binary trees). Kάτι τέτοιο σαν ιδέα έχει χρησιμοποιηθεί από τους Νarlikar and Zane, οι οποίοι παρουσιάζουν μόνο τα αποτελέσματά τους (κλειστού κώδικα υλοποίηση), και τα οποία δεν έχουν σχέση με την παρούσα υλοποίηση. Ο λόγος που χρησιμοποιήθηκε μια τέοια δομή είναι:

• συνδυάζει δύο ξεχωριστές σε μέθοδο υλοποίησης όσο και σε γενικότερη αξία δομές , δίνοντας μας έτσι την δυνατότητα να παρατηρήσουμε τη δυναμικότητα και την αξία της κάθε μιας.
• Η δομή του compressed trie μας δίνει την δυνατότητα να περιορίσουμε τις προσβάσεις στην μνήμη του συστήματος (π.χ. για ένα 2-level trie θα χρειαζόμασταν 2 memory accesses) . Ετσι μπορούμε να ελέγξουμε καλύτερα την κατανομή μνήμης και τις απαιτήσεις σε αυτήν .
• Τα splaytrees είναι μια δομή η οποία αποδίδει πολύ καλά και κοντά στο βέλτιστο χρόνο , όταν έχει ένα σχετικό μέτριο μέγεθος. Στην υλοποίησή μας (όπως και των Νarlikar-Zane) χρησιμοποιούνται για να ελέγξουν τα τελευταία bit μιας ΙΡ διεύθυνσης (συνήθως τα τελευταία 8) , οπότε η δομή δεν παίρνει μεγάλες τιμές μεγέθους. Αποτέλεσμα αυτού είναι ότι μπορούμε να την θεωρήσουμε βέλτιστη δομή για το κομμάτι του ελέγχου της .
• O δεύτερος και πιο σημαντικός λόγος ύπαρξης των splaytrees έχει άμεση σχέση με την γενικότερη μορφή των πινάκων των IP routers. Στους πίνακες αυτούς (που ένας μέσος αριθμός καταχωρήσεων για ένα backbone router είναι γύρω στις 50000 καταχωρήσεις) παρατηρείται το εξής φαινόμενο: το 99% των καταχωρήσεων έχουν μήκος (length) μικρότερο των 24 bits. Κάτι τέτοιο είναι απόρροια του προηγούμενου αλγορίθμου δρομολόγησης που βασιζόταν στις τάξεις (24 bits προθέματα διευθύνσεων αντιστοιχούν στην class C). Mάλιστα το μεγαλύτερο πλήθος των διευθύνσεων είναι 24 bits, κάτι που δείχνει την συνεχιζόμενη επιρροή του συστήματος αυτού των τάξεων πάνω στο CIDR. Η δημιουργία επομένως ενός ακόμη επιπέδου στα leveled tries θα αύξανε δραματικά τον απαιτούμενο χώρο που απαιτείται για την αποθήκευση των καταχωρήσεων, ενώ ταυτόχρονα αυτές δεν θα υπερέβαιναν όπως έχει ειπωθεί το 1% του συνόλου τους, με αποτέλεσμα σποραδική αποθήκευσή τους. Αντ’αυτού, η χρησιμοποίηση των splaytrees βοηθάει στην επίλυση του εν λόγω προβλήματος , χωρίς να απαιτείται δραματικά περισσότερος χώρος , ενώ ταυτόχρονα τα μικρά ομολογουμένως μεγέθη τους εγγυώνται την βέλτιστη απόκρισή τους .

Τέλος, οι σημαντικότερες υλοποιητικές αποφάσεις που επάρθησαν στην παρούσα ημιδυναμική δομή είναι οι εξής:

• Χρησιμοποίηση σταθερών ανά επίπεδο strides
• Xρησιμοποίηση ενός είτε δύο (2) επιπέδων trie
• Χρησιμοποίηση της μεθόδου της “επέκτασης των προθεμάτων” (prefix expansion – prefix replication) σε όλα τα επίπεδα του trie
• Κάθε κόμβος του trie αποτελείται από 2 bytes (16 bits)
• Επέκταση της SplayTree class με την SplayTrie class
• File Manipulation

Για μεγαλύτερη ανάλυση των αποφάσεων αυτών , αλλά γενικά και όλων των υλοποιητικών αποφάσεων, ανατρέξτε στο κεφάλαιο 6 της διπλωματικής διατριβής. Τελικά, αν και η δομή είναι ανοιχτή ως προς το benchmarking της, έχει παρατηρηθεί ότι απαιτεί μεγαλύτερο χρόνο αρχικοποίησης, αλλά μετά την αρχικοποίησή της οι χρόνοι είναι ιδιαίτερα ανταγωνιστικοί αν όχι καλύτεροι από τους χρόνους που δίνουν άλλες διάσημες δομές, όπως π.χ. τα LC tries.

License

Copyright (c) 2004-2018, Sfecas D. Efstathios [email protected]. All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

• Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
• Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
• Neither the name of the Hybrid Structures for IP Lookup Project nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.