Σχεδιασμός p2p πρωτοκόλλου (network coding Πρακτικά Θέματα)

[balios]

Καλησπέρα,θα ήθελα να ρωτήσω αν κάποιος έχει ασχοληθεί με το παραπάνω θέμα

και κυριώς με την υλοποίηση κωδικοποίησης πακέτων για αποστολή μέσα απο

δίκτυο.

[gon1332]

Δεν έχω ασχοληθεί με το συγκεκριμένο θέμα, αλλά όταν ρωτάς για την κωδικοποίηση των πακέτων εννοείς σε επίπεδο socket;

[defacer]

p2p πρωτοκόλλου που να κάνει τι πράγμα;

 

Αν ασχοληθείς με την υλοποίηση τέτοιου πρωτοκόλλου, έχεις διαβάσει πρώτα την υπάρχουσα βιβλιογραφία πάνω σε DHTs (Chord, Kademlia κλπ)?

 

Όταν λες "κωδικοποίηση πακέτων" τι ακριβώς εννοείς;

[balios]

p2p πρωτοκόλλου που να κάνει τι πράγμα;

 

Αν ασχοληθείς με την υλοποίηση τέτοιου πρωτοκόλλου, έχεις διαβάσει πρώτα την υπάρχουσα βιβλιογραφία πάνω σε DHTs (Chord, Kademlia κλπ)?

 

Όταν λες "κωδικοποίηση πακέτων" τι ακριβώς εννοείς;

 

Κωδικοποιήση πακέτων (χοντρικά) έχει να κάνει με μία τεχνική κατα την οποία κάποιος κόμβος αντί να προωθεί τα πακέτα που λαμβάνει στους υπόλοιπους κόμβους του δικτύου είτε με unicast είτε με broadcast μεταδόσεις δημιουργεί και στέλνει πακέτα τα οποία αποτελούν τυχαίους γραμμικούς συνδυασμούς πακέτων που έχει λάβει κάποια συγκεκριμένη χρονική στιγμή.

Οι τελικοι κόμβοι λαμβάνουν πακέτα τα οποία είναι κωδικοποιημένα και προκειμένου να έχουν τα πακέτα στην αρχικη τους μορφή τα αποκωδικοποιούν λύνοντας ενα σύστημα γραμμικών εξισώσεων.Η ιδέα αυτή έχει υλοποιηθεί στη δημιουργία του πρωτοκόλλου Avalanche(http://en.wikipedia.org/wiki/Avalanche_(P2P))

To κέρδος απο την κωδικοποιήση συνηθως έχει να κάνει με αποδοτικοτερη χρηση του Bandwidth,πιθανη εξοικονόμηση ενέργειας,διορθωση σφαλματων που συμβαίνουν κατα τη μετάδοση.

Ωστόσο προυποθέτει ότι οι κόμβοι έχουν ικανη επεξεργαστική ισχύη για τη διαδικασία της κωδικοποίησης αποκωδικοποιησης.

Αυτο που θέλω δεν ειναι να υλοποιήσω ενα τέτοιο πρωτόκολλο για επικοινωνία με sockets etc αλλα πιο πολύ η προσομοίωση της λειτουργίας αυτής σε κάποιο custom simulator που θέλω να υλοποιήσω.

[defacer]

Άρα τι περιμένεις από αυτό το thread? Να βρεις κάποιον στο forum που έχει ασχοληθεί συγκεκριμένα με υλοποίηση Avalanche?

[ChRis6]

Στην αρχή νόμιζα οτι εννούσες την κωδικοποίηση των πακετων στο φυσικό επίπεδο,δηλαδή πως βάζουμε τα bits σε συμβολα για την περίπτωση των p2p πρωτοκολλων,αλλά λες δεν θες αυτό.Κρίμα ! Φαίνεται να έχει ενδιαφέρον

Εφόσον θες να κάνεις προσομοίωση(π.χ με NS-3),πρέπει να έχεις έτοιμο και υλοποιημένο το πρωτόκολλο.Άρα πρέπει έιτε να το βρεις,είτε να το γράψεις μόνος σου...

edit:Συγγνωμη δεν κατάλαβα.Τον simulator θες να φτιάξεις ;

[balios]

Στην αρχή νόμιζα οτι εννούσες την κωδικοποίηση των πακετων στο φυσικό επίπεδο,δηλαδή πως βάζουμε τα bits σε συμβολα για την περίπτωση των p2p πρωτοκολλων,αλλά λες δεν θες αυτό.Κρίμα ! Φαίνεται να έχει ενδιαφέρον

 

Εφόσον θες να κάνεις προσομοίωση(π.χ με NS-3),πρέπει να έχεις έτοιμο και υλοποιημένο το πρωτόκολλο.Άρα πρέπει έιτε να το βρεις,είτε να το γράψεις μόνος σου...

 

edit:Συγγνωμη δεν κατάλαβα.Τον simulator θες να φτιάξεις ;

 

Δεν έχω σκοπό να χρησιμοποιήσω τον ns σαν simulator.Για το προβλημά μου εχω ήδη ξεκινήσει να υλοποιώ τον δικό μου simulator.Οσον αφορά την κωδικοποίηση των πακέτων αυτο που με ενδιαφέρει είναι αν ο γραμμικός συνδυασμός των πακέτων θα πρέπει να γίνει μόνο οσον αφορά τα δεδομένα που περιέχονται στο Payload του πακέτου ή και σε άλλα τμήματα του πακέτου???

Πχ. έχω θεωρήσει ότι 1symbol = 1 byte( 8 bits). Οι πράξεις (προσθεση και πολλαπλασιασμος) που χρειάζονται ώστε να προκύψει κάποιος γραμμικός συνδυασμός ειναι κλειστές πράξεις ορισμένες στο πεδίο Galois GF(2^8).

Στη δομη που έχω ορίσει σαν πακέτο (μια class packet) εκτός απο διάφορες άλλες μεταβλητές έχω ορίσει κάποια μεταβλητή int id που είναι το id του πακέτου που προκύπτει κατα το σπάσιμο του αρχείου σε πακέτα(πακετοποίηση).

Υπάρχει και κάποιος πίνακας payload (με μέγεθος = MTUsize(maximum transmission unit))μέλος και αυτος της κλασης που περιέχει τα δεδομένα που μεταφέρει το πακέτο που αποτελούν κομμάτι απο τα Bytes πληροφορίας του αρχικού αρχείου.

Δημιουργώντας ενα coded packet στο simulator στην ουσία δημιουργω ένα νέο Instance της κλασης packet. το οποίο 

θα έχει ένα καινούριο ID και στο payload θα περιέχονται bytes Που έχουν προκύψει απο τον τυχαίο γραμμικό συνδυασμό των αντίστοιχων Bytes των Payloads των πακέτων που συμμετέχουν στη δημιουργία του νέου κωδικοποιημένου πακέτου.

Ωστόσο με αυτό τον τρόπο χάνεται η πληροφορία σχετικά με το id του πακέτου που προκύπτει απο την πακετοποίηση.

Θα πρέπει και για το id του πακέτου να κάνω το ίδιο (δηλαδή να προκύψει και αύτο μέσα απο τον τυχαίο γραμμικό συνδυασμό?)

Γενικά ποια πεδία του πακέτου θα πρέπει να συνδυαστουν γραμμικά σε επίπεδο byte.

Ελπίζω να μπόρεσες να καταλάβεις την απορία μου.

[ChRis6]

Δεν έχω σκοπό να χρησιμοποιήσω τον ns σαν simulator.Για το προβλημά μου εχω ήδη ξεκινήσει να υλοποιώ τον δικό μου simulator.Οσον αφορά την κωδικοποίηση των πακέτων αυτο που με ενδιαφέρει είναι αν ο γραμμικός συνδυασμός των πακέτων θα πρέπει να γίνει μόνο οσον αφορά τα δεδομένα που περιέχονται στο Payload του πακέτου ή και σε άλλα τμήματα του πακέτου???

Αυτό πιστευω μπορεις να το απαντήσεις και μόνος σου.Αν πειραξεις τα headers των MAC και IP layers με το γραμμικό συνδυασμό,ποιο θα είναι τότε  το αποτέλεσμα ;

 

Εφόσον με το γραμμικό συνδυασμό παράγονται καινούρια και διαφορετικά πακέτα,δεν πρέπει να τα ξεχωρίζεις αυτά μεταξύ τους ; Πώς αλλιως θα κάνεις decode ;

 

Υλοποίησε πρώτα τη λειτουργικότητα που θες για απλά πακέτα που χωράνε σε ένα MTU(π.χ 1500bytes για ethernet ) και συνεχίζεις με το fragmentation ενός μεγαλύτερου αρχείου( video λογικά αφου θες throughput)

[defacer]

Αν κατάλαβα καλά (chris σχετικό με την απάντησή σου) ως "payload" το παλικάρι αναφέρεται στα "πραγματικά δεδομένα" που θέλει να μεταφέρει, βγάζοντας απέξω το overhead του δικού του πρωτοκόλλου -- το overhead του TCP νομίζω πως είναι δεδομένο πως δεν αποτελεί μέρος του payload.

 

@balios, πρώτα απ' όλα θα σου πώ δύο πράγματα:

1. Γιατί δε διαβάζεις παλικάρι μου τα papers του avalanche να σου λυθούν οι απορίες; Μένω με την εντύπωση ότι εδώ ένας τύπος που δεν έχει διαβάσει τη σχετική βιβλιογραφία ζητάει εξηγήσεις από άλλους τύπους που επίσης δεν την έχουν διαβάσει. Αυτό σου ακούγεται αποτελεσματικό;
2. Όσα γράφω παρακάτω τα κατεβάζω από το κεφάλι μου αυτή τη στιγμή και άρα μπορεί να είναι τελείως άκυρα.

 

Λοιπόν... από την περιγραφή του τι γίνεται εδώ εγώ καταλαβαίνω πως το κάθε piece που στέλνεις είναι γραμμικός συνδυασμός Ν τμημάτων (ίσων σε μέγεθος με το piece) των πραγματικών δεδομένων σου, στον οποίο κάθε ένα τμήμα Τ_ν συμμετέχει με κάποιο συντελεστή Α_ν. Ο παραλήπτης λαμβάνοντας αρκετά από αυτά τα pieces μπορεί να λύσει τα γραμμικά συστήματα και έτσι να ανακτήσει μέρος ή και το σύνολο των τμημάτων που συμμετείχαν στα pieces που έχουν παραληφθεί.

 

Προφανώς για να γίνει αυτό θα πρέπει ο παραλήπτης να γνωρίζει για κάθε piece που λαμβάνει α) πόσα και ποιά τμήματα περιλαμβάνονται στη δημιουργία του piece και β) ποιοί οι σταθεροί συντελεστές που χρησιμοποιήθηκαν για να τα μαγειρέψουν. Αυτές λοιπόν οι πληροφορίες θα πρέπει να είναι μέρος του piece -- δεν ξέρω αν θες να το πεις payload, αλλά πρέπει να είναι εκεί.

 

Αυτό λοιπόν που εσύ λες "id του πακέτου που προκύπτει από το σπάσιμο του αρχείου" είναι το (α) που λέω παραπάνω. Τώρα, ο αριθμός των διαφορετικών pieces που μπορούν να δημιουργηθούν είναι οι διατάξεις των Χ πακέτων που λες ανά Ν, επί τον αριθμό των συνδυασμών του αριθμού των στοιχείων που περιέχονται στο σύνολο των γραμμικών συντελεστών που χρησιμοποιείς πάλι ανά Ν. Είναι φανερό πως ανάλογα τα νούμερα για τα οποία συζητάμε αυτός ο αριθμός παίζει να είναι πολύ μεγάλος.

 

Εκτός λοιπόν από τα πρακτικά προβλήματα που μπορεί να έχεις για να στείλεις "id ενός piece", δεν καταλαβαίνω και ποιός ο λόγος να το κάνεις αυτό in the first place. Από τη στιγμή που το piece περιλαμβάνει τις πληροφορίες που λέω παραπάνω θα πρέπει να είσαι καλυμμένος.

[balios]

Αν κατάλαβα καλά (chris σχετικό με την απάντησή σου) ως "payload" το παλικάρι αναφέρεται στα "πραγματικά δεδομένα" που θέλει να μεταφέρει, βγάζοντας απέξω το overhead του δικού του πρωτοκόλλου -- το overhead του TCP νομίζω πως είναι δεδομένο πως δεν αποτελεί μέρος του payload.

 

@balios, πρώτα απ' όλα θα σου πώ δύο πράγματα:

1. Γιατί δε διαβάζεις παλικάρι μου τα papers του avalanche να σου λυθούν οι απορίες; Μένω με την εντύπωση ότι εδώ ένας τύπος που δεν έχει διαβάσει τη σχετική βιβλιογραφία ζητάει εξηγήσεις από άλλους τύπους που επίσης δεν την έχουν διαβάσει. Αυτό σου ακούγεται αποτελεσματικό;

Προφανώς και δεν απαιτώ απο κάποιον να μου διαβάσει το paper και να το εξηγησει ,εχω διαβασει διάφορα Papers στα οποία περιγράφεται

η τεχνική του network coding αλλά δεν αναφέρονται σε λεπτομέρειες,(οπως πχ το ποια πεδία του πακετου συμμετέχουν στις πραξεις κτλ)

Προφανώς ζητάω την γνώμη που απο κάποιον που πιθανόν έχει τύχει να ασχοληθεί με κάποια παρόποιου τύπου υλοποίηση και οι πληροφορίες

που θέλω είναι καπως abstract καθως η υλοποιηση η δικια μου περίεχει λεπτομέρειες διαφορετικές απο την υλοποιηση που μπορει να κάνει καποιος άλλος.

1. Οσα γράφω παρακάτω τα κατεβάζω από το κεφάλι μου αυτή τη στιγμή και άρα μπορεί να είναι τελείως άκυρα.

 

Λοιπόν... από την περιγραφή του τι γίνεται εδώ εγώ καταλαβαίνω πως το κάθε piece που στέλνεις είναι γραμμικός συνδυασμός Ν τμημάτων (ίσων σε μέγεθος με το piece) των πραγματικών δεδομένων σου, στον οποίο κάθε ένα τμήμα Τ_ν συμμετέχει με κάποιο συντελεστή Α_ν. Ο παραλήπτης λαμβάνοντας αρκετά από αυτά τα pieces μπορεί να λύσει τα γραμμικά συστήματα και έτσι να ανακτήσει μέρος ή και το σύνολο των τμημάτων που συμμετείχαν στα pieces που έχουν παραληφθεί.

 

Προφανώς για να γίνει αυτό θα πρέπει ο παραλήπτης να γνωρίζει για κάθε piece που λαμβάνει α) πόσα και ποιά τμήματα περιλαμβάνονται στη δημιουργία του piece και β) ποιοί οι σταθεροί συντελεστές που χρησιμοποιήθηκαν για να τα μαγειρέψουν. Αυτές λοιπόν οι πληροφορίες θα πρέπει να είναι μέρος του piece -- δεν ξέρω αν θες να το πεις payload, αλλά πρέπει να είναι εκεί.

Πολυ σωστα!

 

Αυτό λοιπόν που εσύ λες "id του πακέτου που προκύπτει από το σπάσιμο του αρχείου" είναι το (α) που λέω παραπάνω. Τώρα, ο αριθμός των διαφορετικών pieces που μπορούν να δημιουργηθούν είναι οι διατάξεις των Χ πακέτων που λες ανά Ν, επί τον αριθμό των συνδυασμών του αριθμού των στοιχείων που περιέχονται στο σύνολο των γραμμικών συντελεστών που χρησιμοποιείς πάλι ανά Ν. Είναι φανερό πως ανάλογα τα νούμερα για τα οποία συζητάμε αυτός ο αριθμός παίζει να είναι πολύ μεγάλος.

 

Εκτός λοιπόν από τα πρακτικά προβλήματα που μπορεί να έχεις για να στείλεις "id ενός piece", δεν καταλαβαίνω και ποιός ο λόγος να το κάνεις αυτό in the first place. Από τη στιγμή που το piece περιλαμβάνει τις πληροφορίες που λέω παραπάνω θα πρέπει να είσαι καλυμμένος.

 

Τhanks anyway!

Αυτό πιστευω μπορεις να το απαντήσεις και μόνος σου.Αν πειραξεις τα headers των MAC και IP layers με το γραμμικό συνδυασμό,ποιο θα είναι τότε  το αποτέλεσμα ;

 

Σωστά κάποια πεδία δεν έχουν νόημα να πειραχτούν

 

Εφόσον με το γραμμικό συνδυασμό παράγονται καινούρια και διαφορετικά πακέτα,δεν πρέπει να τα ξεχωρίζεις αυτά μεταξύ τους ; Πώς αλλιως θα κάνεις decode ;

 

Τα κωδικοποιημένα απο τα native πακέτα σαφώς και τα διαχωρίζω.

Το προβλημα μου ειναι οταν κάποιος κόμβος θεωρητικά καταφέρει να αποκωδικοποιήσει κάποια απο τα κωδικοποιημένα πακέτα και λάβει

την αρχική πληροφορία ,θα πρέπει να βάλει τα bytes Πληροφορίας σε μια σειρά προκειμένου να συνθεσει σωστά το αρχικό αρχείο.

κάτι το οποίο σημαίνει ότι θα πρέπει αυτη η πληροφορία (πχ sequenceID να διατηρείται να υπάρχει στον τελικό κόμβο)

Υλοποίησε πρώτα τη λειτουργικότητα που θες για απλά πακέτα που χωράνε σε ένα MTU(π.χ 1500bytes για ethernet ) και συνεχίζεις με το fragmentation ενός μεγαλύτερου αρχείου( video λογικά αφου θες throughput)

[ChRis6]

Εφοσον κανεις το decode,μετα  φτάνεις στο κλασσικό προβλημα : Πώς μαζευεις τα fragments για να φτιαξεις το αρχικο αρχείο.

Αν εισαι πανω απο το TCP,δεν εχεις προβλημα αφου το specification του TCP εγγυαται σειρα παράδοσης FIFO.Άρα ο παραλήπτης βλέπει τα πακέτα με τη σειρά που τα στέλνει ο αποστολέας.

Αν πάλι είσαι πάνω από κάποιο transport layer πρωτόκολλο που δεν εγγυαται FIFO,όπως πχ UDP,τότε πρέπει να κάνεις αυτό προτείνεις.Δίνεις σε κάθε πακέτο έχει ένα σειριακό αριθμό και φτιάχνεις τα αρχικά δεδομένα από τα πακέτα που φτάνουν.Αν κάποιο πακέτο δεν είναι το επόμενο στη σειρά,το βάζεις σε ένα buffer και περιμένεις να φτάσει το σωστό( κάτι τέτοιο κάνει και το TCP ).

Εγώ στη θέση σου θα έκανα το τελευταίο ακόμα και αν ήμουν πάνω απο TCP.Οτιδήποτε μπορεί να πάει στραβά κατά τη μετάδοση...Ιδιαίτερα αν στέλνεις δεδομένα με wifi (802.11/CSMA).Στο LTE ίσως να είναι καλύτερα τα πράγματα