Design and implementation of algorithms exploiting properties of the delay-disruption tolerant networks

Abstract

In the present work towards a PhD degree we study Delay-Disruption Tolerant Networking (DTN) applications and algorithms, addressing problems mainly related to traditional wired and wired-cum-wireless infrastructure networks. The DTN computer networking architecture was designed to cope with long propagation delays and lack of continuous end-to-end connectivity, as well as to provide the necessary framework for interconnecting heterogeneous computer networks. Despite its original conception as a space-communications architecture, DTN has been proposed for applications in various settings, including wired or wired-cum-wireless networks on the edges of the well-connected Internet. In this context, we extend DTN and apply the resulting architecture on a number of distinct use-cases, while investing significant effort in developing detailed simulation tools necessary for evaluating application feasibility and performance. The proposed solutions share the characteristic of deploying DTN as an overlay over traditional IP networks, engaging well-known protocols such as the Internet transport protocols TCP and UDP and, in certain cases, the de facto standard for wireless LANs 802.11.In a typical deployment, DTN can be setup as an overlay on top of existing networks (i.e. IP networks) and provide delay-disruption tolerant services among different segments of the underlying network. Resilience to long delays and connectivity interruptions is ensured by permanently storing protocol state and in-flight protocol data, enabling seamless operation across machine restarts. Responsibility for reliably delivering data is passed between nodes on the path towards their destination through the custody mechanism, a coarse-grained retransmission capability provided by DTN. Through the described core mechanisms, DTN relaxes the restrictions imposed by traditional networking protocols, offering multiple potential contributions in a variety of circumstances, far beyond the space networking environment it was originally designed for.By breaking the synchronous, source-to-destination connectivity constraint, DTN may provide asynchronous services utilizing any of a wide range of data transportation methods. A prominent such example of asynchronous service is the use of DTN to limit the digital divide between developed and developing areas by bringing Internet connectivity to regions lacking the required infrastructure. The DakNet network provides a solution to this problem by physically transferring data using vehicles equipped with Wi-Fi devices and permanent storage. Vehicles visit disconnected areas, collect data, such as applications referred to certain governmental agencies, and travel back to locations with Internet connectivity in order to unload the collected data. In a similar scenario, temporary connectivity may be provided via satellite links, only for certain pre-determined intervals. Significant attention from the research community has also been drawn by DTN applications related to vehicular communications and pocket-switched networks, which target at providing Internet connectivity to commuters and mobile users without the need for cellular data connections. DTN has also been proposed as a means to offer Less-than-Best-Effort (LBE), free Internet services for all users, through the sharing of the broadband connection using resource pooling techniques.In a spirit similar to the applications described in the previous paragraph, we exploit the inherent capabilities of DTN to create networking overlays and to provide non-volatile data storage, and make use of the custody mechanism to propose solutions to certain networking problems relevant in today’s research literature. The first DTN application in our work targets at improving energy efficiency of mobile devices in an infrastructure wired-cum-wireless Internet setting with a last-hop 802.11 connection. The inherent store-and-forward functionality of DTN is utilized in order to buffer incoming data at the Base Station (BS) and allow the Mobile Receiver (MR) to conserve energy by switching its Wireless Network Interface Card (WNIC) to sleep mode, exploiting possible excess capacity of the wireless vs. the broadband link.In the second application, DTN is utilized for disseminating space-data in a decentralized manner to end-users connected to the Internet. Satellites transmit data through a broadcasting mechanism of varying reliability, according to the mission requirements. On the ground, space-data is disseminated over a DTN overlay, following a peer-to-peer multicast approach. Speedy delivery is achieved due to both the creation of shortest routes to the interested recipients as well as due to offloading the network from duplicate data transmission.The third application involves a game-theoretic, storage-based routing approach in an opportunistic DTN setting where persistent storage for accepting custody of relay bundles is scarce. The aim of the routing algorithm is to achieve efficient and fair resource allocation, in a distributed setting, without the need for a central authority.The simulation tools necessary to support development of the above-mentioned solutions have been implemented in great detail in the ns-2 network simulation environment. The simulation model implements functionality across the entire protocol stack, namely at the physical, link, MAC and transport layers. The developed simulation framework has also been employed in order to support peripheral experiments such as cryptographic operations in DTN.

Στην παρούσα διδακτορική διατριβή μελετούμε εφαρμογές και αλγορίθμους σε Δίκτυα Ανεκτικά στις Καθυστερήσεις και τις Διακοπές (Delay-Disruption Tolerant Networking – DTN), εστιάζοντας, κατά κύριο λόγο, σε παραδοσιακά δίκτυα υποδομής που συνδυάζουν ενσύρματες και ασύρματες συνδέσεις. Η αρχιτεκτονική DTN σχεδιάστηκε με γνώμονα τη λειτουργία υπό συνθήκες μεγάλων καθυστερήσεων διάδοσης και έλλειψης συνεχούς συνδεσιμότητας από άκρο σε άκρο, καθώς και με σκοπό να παράσχει ένα ολοκληρωμένο πλαίσιο διασύνδεσης ετερογενών δικτύων υπολογιστών. Παρά το ότι ο αρχικός στόχος των εμπνευστών της αρχιτεκτονικής DTN ήταν η παροχή μίας ενοποιημένης πλατφόρμας για διαστημικές επικοινωνίες, η αρχιτεκτονική αυτή έχει προταθεί προς χρήση σε πλήθος εφαρμογών που περιλαμβάνουν επίγεια δίκτυα σταθερής υποδομής.Σε αυτά τα πλαίσια, επεκτείνουμε το DTN και αξιοποιούμε την προκύπτουσα αρχιτεκτονική για την επίλυση μίας σειράς προβλημάτων, ενώ επενδύουμε σημαντική προσπάθεια στην ανάπτυξη λεπτομερών εργαλείων προσομοίωσης, απαραίτητων για την αξιολόγιση των προτεινόμενων εφαρμογών. Οι προτεινόμενες λύσεις έχουν ως κοινό χαρακτηριστικό την ανάπτυξη του DTN ως υπερκείμενου στρώματος (overlay layer) σε παραδοσιακά IP δίκτυα και τη χρήση ευρέως διαδεδομένων πρωτοκόλλων όπως τα πρωτόλλα μεταφοράς του Internet TCP/UDP και το πρότυπο ασύρματης δικτύωσης 802.11. Έτσι, εκμεταλλευόμαστε τις εγγενείς δυνατότητες του DTN για δημιουργία υπερκείμενων δικτύων και για παροχή μόνιμης αποθήκευσης δεδομένων εντός του δικτύου, αξιοποιώντας ταυτόχρονα το μηχανισμό μεταβίβασης επιμέλειας (custody transfer), και προτείνουμε λύσεις σε δικτυακά προβλήματα της τρέχουσας ερευνητικής βιβλιογραφίας.Η πρώτη εφαρμογή της αρχιτεκτονικής DTN, στα πλαίσια της παρούσας διατριβής, στοχεύει στην βελτίωση της ενεργειακής απόδοσης φορητών, δικτυακών συσκευών, σε μία τυπική τοπολογία Διαδικτύου όπου το τελευταίο σκέλος της σύνδεσης είναι μία ασύρματη σύνδεση 802.11. Η εγγενής λειτουργικότητα για αποθήκευση-και-προώθηση (store-and-forward) του DTN χρησιμοποιείται με στόχο την κατακράτηση εισερχομένων δεδομένων στο Σταθμό Βάσης (Base Station), δίνοντας τη δυνατότητα στο φορητό δέκτη να θέσει την κάρτα ασύρματης δικτύωσης σε κατάσταση αναμονής (sleep). Με τον τρόπο αυτό εκμεταλλευόμαστε την ύπαρξη ενδεχόμενης επιπλέον χωρητικότητας της ασύρματης σύνδεσης, σε σχέση με την ενσύρματη σύνδεση ευρείας ζώνης που παρέχει τη σύνδεση με το Διαδίκτυο, εξοικονομώντας ενέργεια στο φορητό δέκτη.Στη δεύτερη περίπτωση, το DTN χρησιμοποιείται για την αποκεντρωμένη διάδοση διαστημικών δεδομένων στους τελικούς χρήστες μέσω του Διαδικτύου. Δορυφόροι σε χαμηλή τροχιά γύρω από τη Γη (Low Earth Orbit – LEO) συλλέγουν επιστημονικά δεδομένα και τα μεταδίδουν στους τελικούς χρήστες που είναι συνδεδεμένοι στο Διαδίκτυο, μέσω ενός μηχανισμού εκπομπής προσαρμοζόμενου στις ανάγκες της εκάστοτε διαστημικής αποστολής. Όταν τα δεδομένα βρεθούν στο έδαφος, διαδίδονται με τη βοήθεια ενός υπερκείμενου στρώματος DTN, ακολουθώντας την μέθοδο διομότιμης πολυεκπομπής (peer-to-peer multicasting). Ταχεία παράδοση των δεδομένων επιτυγχάνεται χάριν τόσο στη δημιουργία σύντομων διαδρομών προς τους ενδιαφερόμενους αποδέκτες, όσο στην αποσυμφόρηση του δικτύου λόγω της αποφυγής πολλαπλών περιττών μεταδόσεων.Η τρίτη εφαρμογή περιλαμβάνει μία προκαταρκτική έρευνα στο χώρο της δρομολόγησης με περιορισμούς αποθηκευτικού χώρου σε καιροσκοπικά (opportunistic) DTN δίκτυα. Ο στόχος του αλγορίθμου δρομολόγησης είναι να πετύχει αποδοτική και, ταυτόχρονα, δίκαιη κατανομή δικτυακών πόρων, σε ένα κατανεμημένο περιβάλλον, χωρίς την ύπαρξη μιας κεντρικής αρχής. Οι μηχανισμοί που χρησιμοποιούνται από τον αλγόριθμο δρομολόγησης είναι εμπνευσμένοι από τη Θεωρία Παιγνίων, ενώ η ίδια η δρομολόγηση αντιμετωπίζεται ως παίγνιο κατά το οποίο οι δικτυακοί κόμβοι προσπαθούν να μεγιστοποιήσουν την παράδοση των τοπικά παραχθέντων δεδομένων.Τα εργαλεία προσομοίωσης που απαιτούνται για την ανάπτυξη των λύσεων που αναφέρθηκαν στις προηγούμενες παραγράφους υλοποιήθηκαν με λεπτομέρεια στο περιβάλλον δικτυακής προσομοίωσης ns-2. Καθώς ο ns-2 δεν παρείχε εγγενή υποστήριξη για DTN, δημιουργήσαμε το αντίστοιχο μοντέλο προσομοίωσης από μηδενική βάση. Το μοντέλο αυτό περιλαμβάνει λειτουργικότητα που ετείνεται σε ολόκληρη τη στοίβα πρωτοκόλλων και, πιο συγκεκριμένα, στα επίπεδα φυσικό (physical), σύνδεσης (link), ελέγχου πρόσβασης στο μέσο (MAC) και μεταφοράς (transport). Εκτός από τις ήδη αναφερθείσες εφαρμογές, το πλαίσιο προρσομείωσης που αναπτύχθηκε χρησιμοποιήθηκε για την υποστήριξη περιφερειακών πειραμάτων όπως οι κρυπτογραφικές λειτουργίες σε δίκτυα DTN.