backgroundman
25-02-2010, 02:15
http://www.pctechnology.gr/vbull/vb/attachment.php?attachmentid=26424&stc=1&d=1267052180
Μια επαναστατική ιδέα για τη σχεδίαση των τηλεπικοινωνιακών δικτύων, ονομαζόμενη “κωδικοποίηση δικτύου” (network coding) υπόσχεται, μεταξύ άλλων, να αυξήσει τις ταχύτητες μεταφοράς αρχείων στο internet, να κάνει το video-streaming πιο αξιόπιστο και να βελτιώσει την λήψη στα κινητά τηλέφωνα. Τον τελευταίο χρόνο ερευνητές απο το MIT μοιράστηκαν 2 επαίνους απο την IEEE (Institute of Electrical and Electronics Engineers) για σημαντικές δημοσιεύσεις που έκαναν στο τομέα της κωδικοποίησης δικτύου.
Η πλειοψηφία των τηλεπικοινωνιακών δικτύων σήμερα είναι κατασκευασμένα και δομημένα με βάση τις ίδιες αρχές, όπως αυτές που διέπουν τα δίκτυα διανομής αγαθών (πχ φρούτα). Ένα πακέτο από δεδομένα, το οποίο ταξιδεύει στο Internet, περνά από μια σειρά συσκευών, που ονομάζονται routers, πριν φτάσει στο προορισμό του. Μία τέτοια συσκευή (router) απλά στέλνει το πακέτο στον επόμενο router χωρίς να πειράζει το περιεχόμενο του. Με τη κωδικοποίηση δικτύου μία παρόμοια συσκευή (router) δεν κάνει μόνο παράδοση (στον επόμενο router) των πακέτων που έλαβε, αλλά τα συνδυάζει (combine) με μαθηματικό τρόπο, ώστε να παράξει ένα υβριδικό πακέτο πληροφορίας. Εάν ο συνδυασμός των πακέτων γίνει με έξυπνο τρόπο μπορεί να βελτιώσει την απόδοση ολόκληρου του δικτύου.
Για παράδειγμα αν υποθέσουμε οτι έχουμε 2 υπολογιστές (Α και Β) και ένα router (R) σε ασύρματο δίκτυο και την ίδια χρονική στιγμή ο υπολογιστής Α στέλνει ένα μήνυμα στον υπολογιστή Β και ο Β στέλνει ένα άλλο μήνυμα στον Α. Το μήνυμα από τον υπολογιστή Α θα ταξιδέψει στο router (R) και στη συνέχεια ο router θα το προωθήσει στον υπολογιστή Β. Αντίστοιχα και το μήνυμα που στέλνει ο υπολογιστής Β θα πάει στο router (R) και από εκεί στον υπολογιστή Α. Με αυτή τη διαδικασία έχουμε συνολικά 4 μεταδόσεις πακέτων. Αν αντί να προωθεί ο router ένα ένα τα πακέτα που λαμβάνει, έφτιαχνε ένα πακέτο με το συνδυασμό των πακέτων που έλαβε και το προωθούσε σε όλους τους χρήστες-πελάτες του, τότε θα είχαμε συνολικά 3 μεταδόσεις. Από τη στιγμή που ο υπολογιστής Α έχει αντίγραφο του πακέτου που έστειλε, θα μπορούσε πολύ εύκολα να εξάγει από το νέο πακέτο, που του έστειλε ο router, τη πληροφορία που του έστειλε ο υπολογιστής Β. Το ίδιο θα μπορούσε να γίνει και στον υπολογιστή Β. Έτσι λοιπόν αν οι 2 υπολογιστές και ο router έκαναν λίγο περισσότερη επεξεργασία θα μπορούσαμε να μειώσουμε την κατανάλωση εύρους-ζώνης κατά 25%.
Από την άλλη, στο παραπάνω παράδειγμα υποθέτουμε ότι οι 2 υπολογιστές έχουν τα δεδομένα που χρειάζονται για να μπορέσουν να κάνουν αποκωδικοποίηση της πραγματικής πληροφορίας που τους έχει σταλθεί, από το πακέτο συνδυασμό που τους έστειλε ο router. Στο πραγματικό κόσμο αυτό δεν μπορεί να θεωρηθεί δεδομένο. Επιπλέον τα δεδομένα (πακέτα) ταξιδεύοντας σε ένα δίκτυο συνήθως περνούν από πολλούς routers, αν σε καθένα από αυτούς συνδυάζονται πακέτα συνδυασμοί με άλλα πακέτα συνδυασμούς τότε η διαδικασία της αποκωδικοποίησης γίνεται πολύ πιο περίπλοκη.
Η κωδικοποίηση δικτύου γεννήθηκε το 1999-2000 σε δημοσιεύσεις οι οποίες πρότειναν τον συνδυασμό πακέτων στους routers για βελτίωση της απόδοσης του δικτύου. Αλλά το πώς θα πρέπει να γίνει αυτός ο συνδυασμός (combination) των πακέτων και τι κέρδος έχουμε στην απόδοση του δικτύου ήταν αδιευκρίνιστα.
Το 2003 η Muriel Medard καθώς και καθηγητές και μεταπτυχιακοί φοιτητές από τα πανεπιστήμια του MIT, Illinois και Caltech απέδειξαν και δημοσίευσαν μια διαίσθηση που είχαν, ότι στις περισσότερες περιπτώσεις ο καλύτερος τρόπος για να συνδυάσεις δεδομένα είναι να το κάνεις τυχαία.
Σήμερα οι υπολογιστές και τα κινητά τηλέφωνα στέλνουν μηνύματα ψηφιακά. Κάθε μήνυμα αποτελείται από μια αλληλουχία μηδενικών και άσσων. Κάθε τέτοια αλληλουχία αντιπροσωπεύει έναν αριθμό (στο δυαδικό σύστημα). Με τη κωδικοποίησης δικτύου αν ένας router λάβει π.χ. 3 μηνύματα τότε θα πολλαπλασιάσει το κάθε μήνυμα (αριθμός στο δυαδικό) με έναν τυχαίο αριθμό, θα αθροίσει τα αποτελέσματα και έτσι θα προκύψει το νέο υβριδικό μήνυμα. Ο router θα στείλει το υβριδικό μήνυμα στον επόμενο router του δικτύου μαζί με πληροφορίες σχετικές με τους 3 τυχαίους αριθμούς που επέλεξε ώστε να παραχθεί το υβριδικό μήνυμα.
Η κωδικοποίηση με τυχαίους αριθμούς (Random Coding) ενισχύει περισσότερο την απόδοση δικτύων τα οποία έχουν διασυνδέσεις με χαμηλή απόδοση (spotty connections) αλλά υπάρχουν πολλές πιθανές διαδρομές ανάμεσα στον αποστολέα και τον παραλήπτη. Για παράδειγμα, ας υποθέσουμε ότι βρισκόμαστε σε μία πυκνοκατοικημένη περιοχή με καλή κάλυψη κινητής τηλεφωνίας (αρκετές κεραίες). Βρίσκεσαι στο πεδίο εκπομπής αρκετών κεραιών αλλά το κτίριο στο οποίο βρίσκεσαι δημιουργεί παρεμβολές στη μετάδοση. Το κινητό σου τηλέφωνο στέλνει πολλά πακέτα δεδομένων αλλά κανένας πύργος (cell tower) δε μπορεί να τα λάβει όλα. Εάν κάθε πύργος κινητής τηλεφωνίας δημιουργεί υβριδικά πακέτα, από τα πακέτα δεδομένων που δέχεται, και τα εκπέμπει τότε όσο το κινητό σου μπορεί να λαμβάνει υβριδικά πακέτα από διαφορετικούς πύργους, μπορεί να ανακατασκευάσει το αρχικό πακέτο που του έχει σταλεί.
Οι ερευνητές από το MIT, Univ. of Illinois και CalTech απέδειξαν μαθηματικά ότι εάν το ίδιο γκρουπ από μηνύματα (υβριδικά) εκπέμπονται σε διαφορετικούς δέκτες τότε η κωδικοποίηση με τυχαίους αριθμούς είναι η πιο αποδοτική τεχνική, όσον αφορά την εκμετάλλευση του εύρους ζώνης του δικτύου.
Το 2006 η Dina Katabi μαζί με την Medard και άλλους ερευνητές από το ΜΙΤ και το Cambridge University γενίκευσαν την ιδέα του 2003 για δίκτυα όπου υπάρχουν πολλαπλοί πομποί και δέκτες. Οι ερευνητές γέμισαν 2 ορόφους του MIT από ασύρματους routers που ήταν προγραμματισμένοι να εκτελούν την κωδικοποίηση δικτύου και χρησιμοποίησαν διάφορες ασύρματες συσκευές για να ανταλλάξουν πειραματικά δεδομένα μέσω του συγκεκριμένου δικτύου. Όπως όλα τα δεδομένα που στέλνονται/λαμβάνονται σε σύγχρονα δίκτυα, έτσι και τα πειραματικά δεδομένα των ερευνητών ήταν «κομμένα» σε μικρά πακέτα πληροφορίας. Επιπλέον, όπως ακριβώς στα περισσότερα ασύρματα δίκτυα, οι ηλεκτρομαγνητικές παρεμβολές, τα φυσικά εμπόδια και η μεταβολή της απόστασης των ασύρματων συσκευών έχουν σαν αποτέλεσμα κανένας router να μη μπορεί να λάβει όλα τα πακέτα που έστειλαν οι ασύρματες συσκευές.
Στο δίκτυο του ΜΙΤ οι routers έχουν τη δυνατότητα να «πουν» στους γειτονικούς τους routers ποιο από τα πακέτα έχουν λάβει. Ένας router θα χρησιμοποιήσει τη συγκεκριμένη πληροφορία όταν ετοιμάζεται να στείλει τα υβριδικά πακέτα στους γείτονές του. Ας υποθέσουμε ότι ένας router έχει 4 πακέτα στην μνήμη του (A, B, Γ και Δ). Γνωρίζει ότι ένας από τους γείτονές του έχει επίσης τα πακέτα Α και Γ, ένας άλλος γείτονας έχει τα πακέτα Α, Γ και Δ και ένας τρίτος γείτονας έχει τα πακέτα Γ και Δ. Έτσι δημιουργεί ένα υβριδικό πακέτο συνδυάζοντας τα πακέτα Α, Γ και Δ. Ο πρώτος γείτονας χρησιμοποιεί το συγκεκριμένο υβριδικό πακέτο για να μπορέσει να ανακτήσει το πακέτο Δ, ο δεύτερος γείτονας χρησιμοποιεί το υβριδικό πακέτο για να ανακτήσει το πακέτο Γ και ο τρίτος γείτονας το χρησιμοποιεί για να ανακτήσει το πακέτο Α. Από τη στιγμή που το υβριδικό πακέτο έχει μέγεθος όσο και το μέγεθος των πακέτων που συνδυάζονται, αυτό έχει σαν αποτέλεσμα ένα υβριδικό πακέτο να περιέχει τριπλάσια πληροφορία από τα πακέτα που μεταδίδονται σε ένα συνηθισμένο ασύρματο δίκτυο.
Στα πειράματα, η κωδικοποίηση δικτύου μπορεί να αυξήσει σημαντικά την ποσότητα πληροφορίας που διακινείται στο δίκτυο χωρίς να απαιτεί περισσότερο εύρος ζώνης. Αν και η αύξηση αυτή εξαρτάται από τον αριθμό των ασύρματων συσκευών στο δίκτυο και από το πόσες συσκευές εκπέμπουν σε πόσες άλλες, σε γενικές γραμμές η κωδικοποίηση δικτύου μπορεί να τριπλασιάσει τη ποσότητα της πληροφορίας που διακινείται στο δίκτυο.
O Chris Ramming, ο οποίος σαν επικεφαλής προγραμμάτων στην Αμερικανική Υπηρεσία Εξελιγμένων Ερευνών Άμυνας (DARPA), χρηματοδότησε αρκετά προγράμματα έρευνας για τη κωδικοποίηση δικτύου, είπε ότι οι δύο δημοσιεύσεις (2003, 2006) που βραβεύτηκαν από την ΙΕΕΕ είναι και οι δύο πολύ σημαντικές για διαφορετικούς λόγους η καθεμία. Σύμφωνα με τον Ramming, ο οποίος τώρα είναι διευθυντής στο Corporate External Research Office της Intel, η δεύτερη δημοσίευση (2006) ήταν ένα πρακτικό αποτέλεσμα το οποίο απέδειξε ότι σε ένα πραγματικό ασύρματο δίκτυο σε κτίριο του ΜΙΤ χρησιμοποιώντας τη κωδικοποίηση δικτύου μπορούμε να δούμε σημαντικές βελτιώσεις.
Η Katabi, μετά τη συγκεκριμένη δημοσίευση (2006), βρήκε μία τεχνική ώστε να βελτιώσει περεταίρω την απόδοση των δικτύων εξερευνώντας τα φυσικά χαρακτηριστικά των πραγματικών ασύρματων καναλιών. Στο δίκτυο που αναπτύχθηκε στο ΜΙΤ, για τη δημοσίευση του 2006, οι ασύρματοι routers λάμβαναν ηλεκτρομαγνητικά σήματα. Αλλά τα σήματα που εκπέμπονται από διαφορετικούς πομπούς (ασύρματες συσκευές) τείνουν να συγχωνεύονται σε φυσικό επίπεδο. Αυτό το φαινόμενο γενικά αποτελεί πρόβλημα για τις ασύρματες τηλεπικοινωνίες καθώς τα σήματα θα πρέπει να διαχωριστούν προτού αρχίσει η «εξαγωγή» των δεδομένα από αυτά. Η Katabi δημιούργησε άλλο ένα πειραματικό ασύρματο δίκτυο στο οποίο οι routers δεν διαχώριζαν τα σήματα παρά τα ενίσχυαν και τα προωθούσαν. Έτσι λοιπόν διαπιστώθηκε ότι οι τεχνικές κωδικοποίησης δικτύου, που επηρεάζουν την ψηφιακή πληροφορία σε επίπεδο bit, μπορούν να επεκταθούν στην ανακατασκευή των πρωταρχικών σημάτων χωρίς τη πραγματοποίηση ενδιάμεσων διαχωρισμών.
Η Medard ασχολήθηκε και αυτή με τη πρακτική εφαρμογή της κωδικοποίησης δικτύου σε υψηλότερα επίπεδα του δικτύου. Το internet είναι σχεδιασμένο έτσι ώστε ένας υπολογιστής ή ένα τηλέφωνο (IP) όταν δέχεται πληροφορία κατά γενικό κανόνα επιβεβαιώνει ότι έκανε σωστή λήψη του συγκεκριμένου πακέτου πληροφορίας (TCP/IP πρωτόκολλο). Αν η λήψη του πακέτου δε γίνει τότε δε θα υπάρχει επιβεβαίωση από το δέκτη και ο πομπός είναι σε θέση να καταλάβει εάν χρειάζεται να γίνει επανεκπομπή του χαμένου πακέτου πληροφορίας. Στη περίπτωση όμως της κωδικοποίησης δικτύου πολλά πακέτα συνδυάζονται και φτάνουν στο δέκτη. Ποιο από τα πακέτα θα πρέπει να επιβεβαιώσει ο δέκτης ότι έλαβε χωρίς πρόβλημα; Η Medard και οι συνεργάτες της βρήκαν ένα πρακτικό τρόπο για να απαντηθεί το συγκεκριμένο ερώτημα, ένα σύστημα στο οποίο κάθε υβριδικό πακέτο μπορεί να αναγνωρίσει τα πακέτα τα οποία έχουν συνδυαστεί για να προκύψει. Ο δέκτης, στη συγκεκριμένη περίπτωση, ενημερώνει το πομπό για τα πακέτα που συνδυάστηκαν για να προκύψει το υβριδικό πακέτο που παρέλαβε.
Η Medard και οι συνεργάτες της ασχολήθηκαν και με εφαρμογές της κωδικοποίησης δικτύου για εφαρμογές video-streaming, στις οποίες μπορούν να χρησιμοποιηθούν διαφορετικές μέθοδοι συνδυασμών δεδομένων για διαφορετικές αναλύσεις για τις διάφορες συσκευές δέκτες. Επιπλέον προσπαθούν να εφαρμόσουν τις τεχνικές της κωδικοποίησης δικτύου σε πολλαπλά δίκτυα ταυτόχρονα. Για παράδειγμα αν ένα κινητό τηλέφωνο μπορεί να συνδεθεί και σε WiFi δίκτυα, τότε για λήψη μεγάλων αρχείων θα μπορούσαν να χρησιμοποιηθούν και τα 2 δίκτυα (3G και WiFi) παράλληλα για ταχύτερη λήψη. Από την άλλη μεριά το δίκτυο 3G είναι πολύ πιο ακριβό στη χρήση από ένα τοπικό WiFi δίκτυο και έτσι θα ήθελες να μειώσεις στο ελάχιστο τα δεδομένα που μεταφέρονται από το συγκεκριμένο δίκτυο. Η κωδικοποίηση δικτύου θα μπορούσε να βοηθήσει στο συντονισμό των λήψεων από τα 2 δίκτυα με σκοπό να μεγιστοποιήσει την απόδοση, ελαχιστοποιώντας το κόστος.
Αν και η κωδικοποίηση δικτύου είναι στα πρώτα της βήματα έχει κεντρίσει το ενδιαφέρον μεγάλων εταιριών. Η εταιρία BAE (εργολάβος για το υπουργείο άμυνας των ΗΠΑ) έχει κατασκευάσει τον εξοπλισμό για τα προγράμματα του DARPA, που χρηματοδοτούσε ο Ramming. H Microsoft χρησιμοποιεί τη κωδικοποίηση δικτύου σε ένα πρόγραμμα διαμοιρασμού αρχείων (file-sharing), το οποίο ονομάζεται Avalanche. Η Medard συνεργάζεται με τη γαλλική France Telecom και με τη κινεζική εταιρία τηλεπικοινωνιών Huawei σε εφαρμογές της κωδικοποίησης δικτύου. Η Cisco και η Samsung έχουν εκδηλώσει ενδιαφέρον για την κωδικοποίηση δικτύου.
Μετάφραση από :
1. Network-Coding Part1 (http://web.mit.edu/newsoffice/2010/network-coding-part1.html)
2. Network-coding part2 (http://web.mit.edu/newsoffice/2010/network-coding-part2.html)
Άλλες Πηγές :
1. NetworkCoding (Wikipedia) (http://en.wikipedia.org/wiki/Network_coding)
2. Microsoft Avalanche (http://research.microsoft.com/en-us/projects/avalanche/default.aspx)
3. NetworkCoding WebPage (http://www.ifp.uiuc.edu/%7Ekoetter/NWC/index.html)
Μια επαναστατική ιδέα για τη σχεδίαση των τηλεπικοινωνιακών δικτύων, ονομαζόμενη “κωδικοποίηση δικτύου” (network coding) υπόσχεται, μεταξύ άλλων, να αυξήσει τις ταχύτητες μεταφοράς αρχείων στο internet, να κάνει το video-streaming πιο αξιόπιστο και να βελτιώσει την λήψη στα κινητά τηλέφωνα. Τον τελευταίο χρόνο ερευνητές απο το MIT μοιράστηκαν 2 επαίνους απο την IEEE (Institute of Electrical and Electronics Engineers) για σημαντικές δημοσιεύσεις που έκαναν στο τομέα της κωδικοποίησης δικτύου.
Η πλειοψηφία των τηλεπικοινωνιακών δικτύων σήμερα είναι κατασκευασμένα και δομημένα με βάση τις ίδιες αρχές, όπως αυτές που διέπουν τα δίκτυα διανομής αγαθών (πχ φρούτα). Ένα πακέτο από δεδομένα, το οποίο ταξιδεύει στο Internet, περνά από μια σειρά συσκευών, που ονομάζονται routers, πριν φτάσει στο προορισμό του. Μία τέτοια συσκευή (router) απλά στέλνει το πακέτο στον επόμενο router χωρίς να πειράζει το περιεχόμενο του. Με τη κωδικοποίηση δικτύου μία παρόμοια συσκευή (router) δεν κάνει μόνο παράδοση (στον επόμενο router) των πακέτων που έλαβε, αλλά τα συνδυάζει (combine) με μαθηματικό τρόπο, ώστε να παράξει ένα υβριδικό πακέτο πληροφορίας. Εάν ο συνδυασμός των πακέτων γίνει με έξυπνο τρόπο μπορεί να βελτιώσει την απόδοση ολόκληρου του δικτύου.
Για παράδειγμα αν υποθέσουμε οτι έχουμε 2 υπολογιστές (Α και Β) και ένα router (R) σε ασύρματο δίκτυο και την ίδια χρονική στιγμή ο υπολογιστής Α στέλνει ένα μήνυμα στον υπολογιστή Β και ο Β στέλνει ένα άλλο μήνυμα στον Α. Το μήνυμα από τον υπολογιστή Α θα ταξιδέψει στο router (R) και στη συνέχεια ο router θα το προωθήσει στον υπολογιστή Β. Αντίστοιχα και το μήνυμα που στέλνει ο υπολογιστής Β θα πάει στο router (R) και από εκεί στον υπολογιστή Α. Με αυτή τη διαδικασία έχουμε συνολικά 4 μεταδόσεις πακέτων. Αν αντί να προωθεί ο router ένα ένα τα πακέτα που λαμβάνει, έφτιαχνε ένα πακέτο με το συνδυασμό των πακέτων που έλαβε και το προωθούσε σε όλους τους χρήστες-πελάτες του, τότε θα είχαμε συνολικά 3 μεταδόσεις. Από τη στιγμή που ο υπολογιστής Α έχει αντίγραφο του πακέτου που έστειλε, θα μπορούσε πολύ εύκολα να εξάγει από το νέο πακέτο, που του έστειλε ο router, τη πληροφορία που του έστειλε ο υπολογιστής Β. Το ίδιο θα μπορούσε να γίνει και στον υπολογιστή Β. Έτσι λοιπόν αν οι 2 υπολογιστές και ο router έκαναν λίγο περισσότερη επεξεργασία θα μπορούσαμε να μειώσουμε την κατανάλωση εύρους-ζώνης κατά 25%.
Από την άλλη, στο παραπάνω παράδειγμα υποθέτουμε ότι οι 2 υπολογιστές έχουν τα δεδομένα που χρειάζονται για να μπορέσουν να κάνουν αποκωδικοποίηση της πραγματικής πληροφορίας που τους έχει σταλθεί, από το πακέτο συνδυασμό που τους έστειλε ο router. Στο πραγματικό κόσμο αυτό δεν μπορεί να θεωρηθεί δεδομένο. Επιπλέον τα δεδομένα (πακέτα) ταξιδεύοντας σε ένα δίκτυο συνήθως περνούν από πολλούς routers, αν σε καθένα από αυτούς συνδυάζονται πακέτα συνδυασμοί με άλλα πακέτα συνδυασμούς τότε η διαδικασία της αποκωδικοποίησης γίνεται πολύ πιο περίπλοκη.
Η κωδικοποίηση δικτύου γεννήθηκε το 1999-2000 σε δημοσιεύσεις οι οποίες πρότειναν τον συνδυασμό πακέτων στους routers για βελτίωση της απόδοσης του δικτύου. Αλλά το πώς θα πρέπει να γίνει αυτός ο συνδυασμός (combination) των πακέτων και τι κέρδος έχουμε στην απόδοση του δικτύου ήταν αδιευκρίνιστα.
Το 2003 η Muriel Medard καθώς και καθηγητές και μεταπτυχιακοί φοιτητές από τα πανεπιστήμια του MIT, Illinois και Caltech απέδειξαν και δημοσίευσαν μια διαίσθηση που είχαν, ότι στις περισσότερες περιπτώσεις ο καλύτερος τρόπος για να συνδυάσεις δεδομένα είναι να το κάνεις τυχαία.
Σήμερα οι υπολογιστές και τα κινητά τηλέφωνα στέλνουν μηνύματα ψηφιακά. Κάθε μήνυμα αποτελείται από μια αλληλουχία μηδενικών και άσσων. Κάθε τέτοια αλληλουχία αντιπροσωπεύει έναν αριθμό (στο δυαδικό σύστημα). Με τη κωδικοποίησης δικτύου αν ένας router λάβει π.χ. 3 μηνύματα τότε θα πολλαπλασιάσει το κάθε μήνυμα (αριθμός στο δυαδικό) με έναν τυχαίο αριθμό, θα αθροίσει τα αποτελέσματα και έτσι θα προκύψει το νέο υβριδικό μήνυμα. Ο router θα στείλει το υβριδικό μήνυμα στον επόμενο router του δικτύου μαζί με πληροφορίες σχετικές με τους 3 τυχαίους αριθμούς που επέλεξε ώστε να παραχθεί το υβριδικό μήνυμα.
Η κωδικοποίηση με τυχαίους αριθμούς (Random Coding) ενισχύει περισσότερο την απόδοση δικτύων τα οποία έχουν διασυνδέσεις με χαμηλή απόδοση (spotty connections) αλλά υπάρχουν πολλές πιθανές διαδρομές ανάμεσα στον αποστολέα και τον παραλήπτη. Για παράδειγμα, ας υποθέσουμε ότι βρισκόμαστε σε μία πυκνοκατοικημένη περιοχή με καλή κάλυψη κινητής τηλεφωνίας (αρκετές κεραίες). Βρίσκεσαι στο πεδίο εκπομπής αρκετών κεραιών αλλά το κτίριο στο οποίο βρίσκεσαι δημιουργεί παρεμβολές στη μετάδοση. Το κινητό σου τηλέφωνο στέλνει πολλά πακέτα δεδομένων αλλά κανένας πύργος (cell tower) δε μπορεί να τα λάβει όλα. Εάν κάθε πύργος κινητής τηλεφωνίας δημιουργεί υβριδικά πακέτα, από τα πακέτα δεδομένων που δέχεται, και τα εκπέμπει τότε όσο το κινητό σου μπορεί να λαμβάνει υβριδικά πακέτα από διαφορετικούς πύργους, μπορεί να ανακατασκευάσει το αρχικό πακέτο που του έχει σταλεί.
Οι ερευνητές από το MIT, Univ. of Illinois και CalTech απέδειξαν μαθηματικά ότι εάν το ίδιο γκρουπ από μηνύματα (υβριδικά) εκπέμπονται σε διαφορετικούς δέκτες τότε η κωδικοποίηση με τυχαίους αριθμούς είναι η πιο αποδοτική τεχνική, όσον αφορά την εκμετάλλευση του εύρους ζώνης του δικτύου.
Το 2006 η Dina Katabi μαζί με την Medard και άλλους ερευνητές από το ΜΙΤ και το Cambridge University γενίκευσαν την ιδέα του 2003 για δίκτυα όπου υπάρχουν πολλαπλοί πομποί και δέκτες. Οι ερευνητές γέμισαν 2 ορόφους του MIT από ασύρματους routers που ήταν προγραμματισμένοι να εκτελούν την κωδικοποίηση δικτύου και χρησιμοποίησαν διάφορες ασύρματες συσκευές για να ανταλλάξουν πειραματικά δεδομένα μέσω του συγκεκριμένου δικτύου. Όπως όλα τα δεδομένα που στέλνονται/λαμβάνονται σε σύγχρονα δίκτυα, έτσι και τα πειραματικά δεδομένα των ερευνητών ήταν «κομμένα» σε μικρά πακέτα πληροφορίας. Επιπλέον, όπως ακριβώς στα περισσότερα ασύρματα δίκτυα, οι ηλεκτρομαγνητικές παρεμβολές, τα φυσικά εμπόδια και η μεταβολή της απόστασης των ασύρματων συσκευών έχουν σαν αποτέλεσμα κανένας router να μη μπορεί να λάβει όλα τα πακέτα που έστειλαν οι ασύρματες συσκευές.
Στο δίκτυο του ΜΙΤ οι routers έχουν τη δυνατότητα να «πουν» στους γειτονικούς τους routers ποιο από τα πακέτα έχουν λάβει. Ένας router θα χρησιμοποιήσει τη συγκεκριμένη πληροφορία όταν ετοιμάζεται να στείλει τα υβριδικά πακέτα στους γείτονές του. Ας υποθέσουμε ότι ένας router έχει 4 πακέτα στην μνήμη του (A, B, Γ και Δ). Γνωρίζει ότι ένας από τους γείτονές του έχει επίσης τα πακέτα Α και Γ, ένας άλλος γείτονας έχει τα πακέτα Α, Γ και Δ και ένας τρίτος γείτονας έχει τα πακέτα Γ και Δ. Έτσι δημιουργεί ένα υβριδικό πακέτο συνδυάζοντας τα πακέτα Α, Γ και Δ. Ο πρώτος γείτονας χρησιμοποιεί το συγκεκριμένο υβριδικό πακέτο για να μπορέσει να ανακτήσει το πακέτο Δ, ο δεύτερος γείτονας χρησιμοποιεί το υβριδικό πακέτο για να ανακτήσει το πακέτο Γ και ο τρίτος γείτονας το χρησιμοποιεί για να ανακτήσει το πακέτο Α. Από τη στιγμή που το υβριδικό πακέτο έχει μέγεθος όσο και το μέγεθος των πακέτων που συνδυάζονται, αυτό έχει σαν αποτέλεσμα ένα υβριδικό πακέτο να περιέχει τριπλάσια πληροφορία από τα πακέτα που μεταδίδονται σε ένα συνηθισμένο ασύρματο δίκτυο.
Στα πειράματα, η κωδικοποίηση δικτύου μπορεί να αυξήσει σημαντικά την ποσότητα πληροφορίας που διακινείται στο δίκτυο χωρίς να απαιτεί περισσότερο εύρος ζώνης. Αν και η αύξηση αυτή εξαρτάται από τον αριθμό των ασύρματων συσκευών στο δίκτυο και από το πόσες συσκευές εκπέμπουν σε πόσες άλλες, σε γενικές γραμμές η κωδικοποίηση δικτύου μπορεί να τριπλασιάσει τη ποσότητα της πληροφορίας που διακινείται στο δίκτυο.
O Chris Ramming, ο οποίος σαν επικεφαλής προγραμμάτων στην Αμερικανική Υπηρεσία Εξελιγμένων Ερευνών Άμυνας (DARPA), χρηματοδότησε αρκετά προγράμματα έρευνας για τη κωδικοποίηση δικτύου, είπε ότι οι δύο δημοσιεύσεις (2003, 2006) που βραβεύτηκαν από την ΙΕΕΕ είναι και οι δύο πολύ σημαντικές για διαφορετικούς λόγους η καθεμία. Σύμφωνα με τον Ramming, ο οποίος τώρα είναι διευθυντής στο Corporate External Research Office της Intel, η δεύτερη δημοσίευση (2006) ήταν ένα πρακτικό αποτέλεσμα το οποίο απέδειξε ότι σε ένα πραγματικό ασύρματο δίκτυο σε κτίριο του ΜΙΤ χρησιμοποιώντας τη κωδικοποίηση δικτύου μπορούμε να δούμε σημαντικές βελτιώσεις.
Η Katabi, μετά τη συγκεκριμένη δημοσίευση (2006), βρήκε μία τεχνική ώστε να βελτιώσει περεταίρω την απόδοση των δικτύων εξερευνώντας τα φυσικά χαρακτηριστικά των πραγματικών ασύρματων καναλιών. Στο δίκτυο που αναπτύχθηκε στο ΜΙΤ, για τη δημοσίευση του 2006, οι ασύρματοι routers λάμβαναν ηλεκτρομαγνητικά σήματα. Αλλά τα σήματα που εκπέμπονται από διαφορετικούς πομπούς (ασύρματες συσκευές) τείνουν να συγχωνεύονται σε φυσικό επίπεδο. Αυτό το φαινόμενο γενικά αποτελεί πρόβλημα για τις ασύρματες τηλεπικοινωνίες καθώς τα σήματα θα πρέπει να διαχωριστούν προτού αρχίσει η «εξαγωγή» των δεδομένα από αυτά. Η Katabi δημιούργησε άλλο ένα πειραματικό ασύρματο δίκτυο στο οποίο οι routers δεν διαχώριζαν τα σήματα παρά τα ενίσχυαν και τα προωθούσαν. Έτσι λοιπόν διαπιστώθηκε ότι οι τεχνικές κωδικοποίησης δικτύου, που επηρεάζουν την ψηφιακή πληροφορία σε επίπεδο bit, μπορούν να επεκταθούν στην ανακατασκευή των πρωταρχικών σημάτων χωρίς τη πραγματοποίηση ενδιάμεσων διαχωρισμών.
Η Medard ασχολήθηκε και αυτή με τη πρακτική εφαρμογή της κωδικοποίησης δικτύου σε υψηλότερα επίπεδα του δικτύου. Το internet είναι σχεδιασμένο έτσι ώστε ένας υπολογιστής ή ένα τηλέφωνο (IP) όταν δέχεται πληροφορία κατά γενικό κανόνα επιβεβαιώνει ότι έκανε σωστή λήψη του συγκεκριμένου πακέτου πληροφορίας (TCP/IP πρωτόκολλο). Αν η λήψη του πακέτου δε γίνει τότε δε θα υπάρχει επιβεβαίωση από το δέκτη και ο πομπός είναι σε θέση να καταλάβει εάν χρειάζεται να γίνει επανεκπομπή του χαμένου πακέτου πληροφορίας. Στη περίπτωση όμως της κωδικοποίησης δικτύου πολλά πακέτα συνδυάζονται και φτάνουν στο δέκτη. Ποιο από τα πακέτα θα πρέπει να επιβεβαιώσει ο δέκτης ότι έλαβε χωρίς πρόβλημα; Η Medard και οι συνεργάτες της βρήκαν ένα πρακτικό τρόπο για να απαντηθεί το συγκεκριμένο ερώτημα, ένα σύστημα στο οποίο κάθε υβριδικό πακέτο μπορεί να αναγνωρίσει τα πακέτα τα οποία έχουν συνδυαστεί για να προκύψει. Ο δέκτης, στη συγκεκριμένη περίπτωση, ενημερώνει το πομπό για τα πακέτα που συνδυάστηκαν για να προκύψει το υβριδικό πακέτο που παρέλαβε.
Η Medard και οι συνεργάτες της ασχολήθηκαν και με εφαρμογές της κωδικοποίησης δικτύου για εφαρμογές video-streaming, στις οποίες μπορούν να χρησιμοποιηθούν διαφορετικές μέθοδοι συνδυασμών δεδομένων για διαφορετικές αναλύσεις για τις διάφορες συσκευές δέκτες. Επιπλέον προσπαθούν να εφαρμόσουν τις τεχνικές της κωδικοποίησης δικτύου σε πολλαπλά δίκτυα ταυτόχρονα. Για παράδειγμα αν ένα κινητό τηλέφωνο μπορεί να συνδεθεί και σε WiFi δίκτυα, τότε για λήψη μεγάλων αρχείων θα μπορούσαν να χρησιμοποιηθούν και τα 2 δίκτυα (3G και WiFi) παράλληλα για ταχύτερη λήψη. Από την άλλη μεριά το δίκτυο 3G είναι πολύ πιο ακριβό στη χρήση από ένα τοπικό WiFi δίκτυο και έτσι θα ήθελες να μειώσεις στο ελάχιστο τα δεδομένα που μεταφέρονται από το συγκεκριμένο δίκτυο. Η κωδικοποίηση δικτύου θα μπορούσε να βοηθήσει στο συντονισμό των λήψεων από τα 2 δίκτυα με σκοπό να μεγιστοποιήσει την απόδοση, ελαχιστοποιώντας το κόστος.
Αν και η κωδικοποίηση δικτύου είναι στα πρώτα της βήματα έχει κεντρίσει το ενδιαφέρον μεγάλων εταιριών. Η εταιρία BAE (εργολάβος για το υπουργείο άμυνας των ΗΠΑ) έχει κατασκευάσει τον εξοπλισμό για τα προγράμματα του DARPA, που χρηματοδοτούσε ο Ramming. H Microsoft χρησιμοποιεί τη κωδικοποίηση δικτύου σε ένα πρόγραμμα διαμοιρασμού αρχείων (file-sharing), το οποίο ονομάζεται Avalanche. Η Medard συνεργάζεται με τη γαλλική France Telecom και με τη κινεζική εταιρία τηλεπικοινωνιών Huawei σε εφαρμογές της κωδικοποίησης δικτύου. Η Cisco και η Samsung έχουν εκδηλώσει ενδιαφέρον για την κωδικοποίηση δικτύου.
Μετάφραση από :
1. Network-Coding Part1 (http://web.mit.edu/newsoffice/2010/network-coding-part1.html)
2. Network-coding part2 (http://web.mit.edu/newsoffice/2010/network-coding-part2.html)
Άλλες Πηγές :
1. NetworkCoding (Wikipedia) (http://en.wikipedia.org/wiki/Network_coding)
2. Microsoft Avalanche (http://research.microsoft.com/en-us/projects/avalanche/default.aspx)
3. NetworkCoding WebPage (http://www.ifp.uiuc.edu/%7Ekoetter/NWC/index.html)