Cooperation and fair resource allocation in communication networks

Abstract

Last few years have witnessed a dramatic growth of communication networks, with peer-to-peer (p2p) overlay communities becoming a new network paradigm for diverse applications and services. Peers can simultaneously act as clients and servers taking part in a collaborative work process. However, although cooperation is of utmost importance to p2p systems, peers seem to be naturally incited only to consume but not contribute to a community. This phenomenon is known as “free riding” and leads to the degradation of the system performance. In this thesis we propose distributed reputation based resource allocation and server selection policies to motivate cooperation among users of p2p networks and provide fairness by guarantying that more contributive peer can receive a better QoS from their community. We use a common system design that can be applied to both single service (e.g., file sharing systems) and multiple services’ systems (e.g., p2p grids). Proposed framework consists of an autonomous reputation scheme, reputation-based resource allocation and server selection policies which are robust under the presence of misbehavior, strategic peers, greedy peers and newcomers. We quantify a peer’s capability in providing a good quality service by a novel reputation metric and an update mechanism is proposed to dynamically track the contribution level of the peer as the system evolves. Our reputation-based allocation policies determine the quality of service given to all competing for resources peers at a given time according to their reputations, demands, and profiles. On the other hand, our reputation-based server selection policy is used to choose suitable providers of the requested service and avoid misbehaving (non contributive) ones. Our simulations in various different setups of peers with different resource capabilities, consumption and service evaluation profiles present how proposed policies outperform previous work both for single and multiple services systems and lead to the dynamic formation of coalitions (cooperation) between peers who mutually benefit by their transactions. We further study systems of peers who use their capacity-limited access links both for their upstream and downstream connections (single capacity limited-link systems). Such peers have to share their available resources between their own and other peers’ needs. In the selfish approach, each peer would like to exploit the full capacity of his access link only for his downloads. However, if all peers acted selfishly, the system would collapse. In order to motivate peers to cooperate under such systems, we combine our distributed reputation-based system with a novel capacity adaptation algorithm. In this way, each peer has to trade off the capacity he will dedicate for uploading in order to increase his reputation and therefore his revenue and the capacity he will dedicate for his downloads. All peers act rationally, trying to maximize their utility. Our proposed policies lead rational peers to cooperation while promoting fairness, as peers receive resources in proportion to their contributions. Our policies outperform existing work in this area in which the slowest link becomes the bottleneck of a heterogeneous system of different link capacity peers. In the contrary, no such bottleneck appears when our policies are used, improving the performance of the system. Moreover, we apply our reputation-based framework in a BitTorrent-like file sharing system and we highlight the performance gains both for ADSL-type and single capacity-limited link systems. Finally, we study a wireless internet sharing community and we propose easily applicable distributed reputation-based policies to motivate users to share their Internet connection in a p2p fashion. The goal is the provision of free and good quality Internet access anytime and anywhere inside the community. We study general systems of users with different contribution and consumption profiles and show that when our reputation-based allocation scheme is applied, mobile users enjoy a QoS Internet connection from their community in proportion to their cooperation level; the more greedy for community resources users are, the more contributive they should be to satisfy their needs. Our allocation scheme is further implemented in 802.11 APs and clients with no modifications at existing standards at the MAC or network layers and experimental results present that the throughputs of the community members are in proportion to their reputations for any channel conditions, type of traffic sent or received, and number of competing clients.

Η αποτελεσματικότητα υπαρχόντων δικτύων ομότιμων κόμβων (p2p) βασίζεται στην συνεργασία μεταξύ χρηστών και στην συνεισφορά των διαθέσιμων πόρων τους. Είναι ωστόσο γνωστό κοινωνιολογικό φαινόμενο ότι οι χρήστες είναι διστακτικοί στο να συνεργάζονται, και μόνο ένα μικρό ποσοστό αυτών είναι διατεθειμένοι να μοιραστούν τους πόρους τους με άλλους χρήστες. Το φαινόμενο αυτό οδηγεί στην υποβάθμιση του συστήματος καθώς οι λίγοι χρήστες που είναι διατεθειμένοι να προσφέρουν στο σύστημα μπορεί να μην ικανοί να το κάνουν όταν η ζήτηση γίνει μεγάλη. Η εν λόγω διδακτορική διατριβή επικεντρώνεται σε κατανεμημένες τεχνικές διαμοιρασμού πόρων στα εν λόγω δίκτυα, κατά τέτοιο τρόπο ώστε να διασφαλίζει την συνεργασία των χρηστών και να εγγυάται τον δίκαιο διαμοιρασμό των πόρων, έτσι ώστε οι πιο συνεργάσιμοι χρήστες να απολαμβάνουν καλύτερη ποιότητα υπηρεσιών μέσα στο δίκτυο. Οι ίδιες τεχνικές αποσκοπούν στο να περιθωριοποιούν χρήστες που κάνουν εγωιστική χρήση των πόρων του δικτύου, χωρίς να προσφέρουν οι ίδιοι τίποτα. Η μεθοδολογία που ακολουθείται στη συγκεκριμένη διατριβή χρησιμοποιεί μία μετρική που καλείται φήμη (reputation) και αντανακλά τα επίπεδα συνεργασιμότητας των χρηστών, έτσι ώστε οι συνεργάσιμοι χρήστες να αυξάνουν την φήμη τους, και ανάλογα με αυτήν την φήμη που καθίσταται γνωστή στο δίκτυο, να μπορούν να αντλήσουν τους ανάλογους πόρους από αυτό. Στην συγκεκριμένη μεθοδολογία χρησιμοποιήθηκε μια νεοεισαχθείσα ποσοτική μετρική για το reputation ενός χρήστη που καθορίζεται από τον βαθμό ικανοποίησης που παρείχε ο συγκεκριμένος χρήστης στους υπόλοιπους του δικτύου σε ποιότητα εξυπηρέτησης. Η μετρική αυτή αλλάξει δυναμικά, ανάλογα με την συμπεριφορά και τις απαιτήσεις των χρηστών. Σε συνδυασμό με το προτεινόμενο σύστημα φήμης, προτείναμε μεθοδολογίες διανομής των πόρων των χρηστών στους ενδιαφερόμενους με βάση την φήμη τους (Reputation-based Resource Allocation Policies), έτσι ώστε το ποσοστό καν διαθέσιμων πόρων που θα δίνεται σε κάθε ενδιαφερόμενο χρήστη σε μια δεδομένη στιγμή να είναι συνάρτηση της φήμης του, των αναγκών του σε πόρους (που τις εκφράζει σε κάθε αίτηση του) και του καταναλωτικού του προφίλ (ρυθμό με τον οποίο γεννάει αιτήσεις). Οι προτεινόμενοι αλγόριθμοι λειτουργούν έτσι ώστε όσο περισσότερο απαιτητικοί είναι οι χρήστες στο δίκτυο, είτε διότι γεννάνε πολλές αιτήσεις, είτε διότι ζητάνε πολλούς πόρους ανά αίτηση, τόσο πιο υψηλά επίπεδα φήμης θα πρέπει να έχουν προκειμένου να ικανοποιήσουν τις υψηλές απαιτήσεις τους. Οι αλγόριθμοι αυτοί, συνδυασμένοι και με έναν προτεινόμενο μηχανισμό επιλογής εξυπηρετητή (server selection policy) για μια δεδομένη αίτηση, οδηγούνε στην δίκαιη αντιμετώπιση των χρηστών ανάλογα με τα επίπεδα προσφοράς τους στο δίκτυο και στην αύξηση του κέρδους τους από τις συνδιαλλαγές τους. Αρχικά, σχεδιάσαμε τους παραπάνω μηχανισμούς για δίκτυα χρηστών όπου διαμοιράζεται ένας πόρος, όπως εύρος ζώνης για μεταφορά αρχείων. Χρησιμοποιήθηκαν οι προτεινόμενοι μηχανισμοί για την διαχείριση του διαθέσιμου εύρους ζώνης για την μεταφορά αρχείων από τον έναν χρήστη στον άλλο και οι μηχανισμοί επιλογής εξυπηρετητή με βάση την φήμη του. Οι μηχανισμοί εξετάστηκαν συγκριτικά και με άλλους μηχανισμούς διαχείρισης πόρων και παρουσιάστηκαν τα πλεονεκτήματα τους. Στην συνέχεια οι παραπάνω μηχανισμοί επεκτάθηκαν για δίκτυα χρηστών, όπου διαμοιράζονται παραπάνω από έναν πόροι (p2p grids), στοχεύοντας στην διαχείριση διαφορετικών πόρων μέσα στο ίδιο δίκτυο και στην ενίσχυση συνεργασίας. Το πλαίσιο το οποίο διαμορφώθηκε για αυτό το σκοπό λαμβάνει υπόψη του τις διαφορετικές δυνατότητες, ανάγκες και εκτιμήσεις των χρηστών για κάθε πόρο. Οι προσομοιώσεις μας δείξανε ότι το σύστημα αποτρέπει τις συνδιαλλαγές με μη συνεργάσιμους (selfish) χρήστες και οδηγεί στην δημιουργία κατάλληλων συνασπισμών μεταξύ χρηστών, προκειμένου να αυξήσουν το κέρδος τους από τις συνδιαλλαγές τους. Η αποτελεσματικότητα των προτεινόμενων μηχανισμών παρουσιάζεται και συγκριτικά με άλλες πολιτικές. Στην συνέχεια, εξετάστηκαν ρ2ρ συστήματα όπου οι χρήστες χρησιμοποιούν την περιορισμένη σε εύρος ζώνης χωρητικότητα του καναλιού τους και για να ανεβάζουν (upload) σε άλλους και για να κατεβάζουν (download) από άλλους δεδομένα, παράλληλα. Τέτοιου είδους συστήματα, στα οποία αναφερόμαστε ως single capacity-limited link systems, αφορούν τεχνολογίες πρόσβασης στο κανάλι τύπου WiFi, WiMAX, Ethernet LANs κ.α. Εάν οι χρήστες φέρονται εγωιστικά, κάθε ένας από αυτούς θα χρησιμοποιεί την συνολική χωρητικότητα του μόνο για να κατεβάζει δεδομένα, οδηγώντας το σύστημα στην κατάρρευση. Προκειμένου να οδηγήσουμε το σύστημα των χρηστών σε συνεργασία ενσωματώσαμε στις προαναφερθείσες τεχνικές μας έναν δυναμικό αλγόριθμο διαμοιρασμού της χωρητικότητας των χρηστών μεταξύ καναλιού ανόδου (uplink) και καναλιού καθόδου (downlink) ανάλογα με την ποιότητα των υπηρεσιών που λαμβάνουν. Οι προσομοιώσεις μας έδειξαν ότι σε ομογενή συστήματα χρηστών που έχουν την ίδια χωρητικότητα, το σύστημα οδηγείται σε ένα σημείο ισορροπίας όπου οι χρήστες κρατάνε την μισή χωρητικότητα για τον εαυτό τους και αποδίδουν την υπόλοιπη για τις ανάγκες των άλλων χρηστών, ενώ σε ετερογενή συστήματα οι χρήστες μπορούν να αντλήσουν πόρους ανάλογα με τις συνεισφορές τους στο δίκτυο. Παράλληλα, ο προτεινόμενος αλγόριθμος χρησιμοποιήθηκε στο δημοφιλές πρωτόκολλο BitTorrent για να διευρύνει την αποτελεσματική του εφαρμογή σε τέτοιου είδους συστήματα. Η προτεινόμενη μεθοδολογία τόσο για single capacity-limited link systems, όσο και για τα ADSL-τύπου συστήματα που μελετήσαμε αρχικά, εξετάστηκε και στο πρωτόκολλο BitTorrent, όπου έγιναν συγκρίσεις με τον δικό του μηχανισμό κινήτρων, τον οποίο η εκτεταμένη βιβλιογραφική έρευνα ανέδειξε ανεπαρκή. Οι προσομοιώσεις έδειξαν ότι οι προτεινόμενοι μηχανισμοί μπορούν να βελτιώσουν την συμπεριφορά του συστήματος, να άρουν τα φαινόμενα αδικίας που έχουν παρατηρηθεί στο BitTorrent, και να προσφέρουν κίνητρα σε χρήστες που ήδη έχουν κατεβάσει ένα αρχείο (seeds) να παραμείνουν στο σύστημα κα να συνεχίσουν να προσφέρουν τις υπηρεσίες τους. Το τελευταίο λείπει από το πρωτόκολλο και κρίνεται κρίσιμο για την αποτελεσματικότητα του, εφόσον έρευνες έχουν δείξει ότι η απόδοση των χρηστών κρίνεται από πόσους seeds υπάρχουν μέσα σε αυτό. Το τελευταίο κομμάτι της διατριβής αφορά την απόδοση κινήτρων στους χρήστες μιας κοινότητας διαμοιρασμού ασύρματης διαδικτυακής πρόσβασης. Ένας τέτοιος χρήστης θα απέφευγε να μοιράσει την σύνδεση του στο διαδίκτυο, καθότι θα μείωνε την δική του ποιότητα εξυπηρέτησης και επομένως χρειάζεται τα κατάλληλα κίνητρα για να συνεργαστεί. Τέτοιες εφαρμογές διαμοιρασμού της διαδικτυακής σύνδεσης αρχίζουν να γίνονται πολύ δημοφιλείς και να χρησιμοποιούνται από εταιρείες ευρυζωνικής παροχής διαδικτύου, όπως το FON. Η εν λόγω διατριβή χρησιμοποιεί κατανεμημένες τεχνικές ώστε να μην χρειάζεται κεντρικός έλεγχος, αφήνοντας στους χρήστες τον έλεγχο της διαχείρισης της σύνδεση τους, και εγγυάται την συνεργασία ανάμεσα τους, παρέχοντας καλύτερη ποιότητα εξυπηρέτησης στους πιο συνεργάσιμους χρήστες. Η αποτελεσματικότητα των τεχνικών αυτών εξετάστηκε από προσομοιώσεις τέτοιων κοινοτήτων και μοντέλων συμπεριφοράς χρηστών σε παρόμοιες κοινότητες. Παράλληλα, υλοποιήσαμε τον μηχανισμό ανάθεσης πόρων σε σημεία πρόσβασης (ΑΡ) και σταθμούς (clients) τεχνολογίας 802.11, χωρίς να επιφέρουμε αλλαγές στα υπάρχοντα πρότυπα του επιπέδου δικτύου (Network layer) και πρόσβασης στο μέσο (MAC layer) και πειραματιστήκαμε στο πειραματικό δίκτυο του Πανεπιστημίου Θεσσαλίας όπως και σε επιμέρους ORBIT κόμβους. Αυτό που παρατηρήσαμε είναι ότι χρησιμοποιώντας τον προτεινόμενο μηχανισμό μπορούμε να επιτύχουμε λόγο ποιότητας εξυπηρέτησης (throughput) για τους χρήστες ανάλογο με τον λόγο των reputations τους, για οποιεσδήποτε συνθήκες καναλιού, είδους αποσταλείσας ή ληφθείσας κύησης και αριθμό χρηστών.