Accurate estimation of end-to-end delivery delay in space internets: protocol design and implementation

Abstract

In this thesis, we study the issue of estimating end-to-end delivery delays for data transmissions in space internets. We provide solutions that deal with the challenging nature of space communications and improve the delay estimation for different network conditions. To achieve that, we leverage Delay/Disruption Tolerant Networking (DTN), an architecture that has recently emerged to interconnect space assets into the Interplanetary Internet (IPN). By exploiting the basic principles of the DTN architecture and studying the challenged space network conditions, we model the different components of the end-to-end latency, and advance the awareness of the network as well as its inherent ability to accurately predict them. In particular, we deal not only with the deterministic components of total latency (e.g., signal propagation delay for a given pair of space assets, transmission delays through links with given data rates, waiting times for scheduled communication establishment, etc.), but also with the probabilistic parameters that pertain to the data transmissions (e.g., queueing delays induced by cross-traffic data backlog, retransmission delays due to lost or corrupted data, etc.). We then exploit the improved latency prediction functions in real-time network operations: we enhance network routing ability to capture the end-to-end path that data items will follow from source to destination, and, by developing algorithms and protocols that improve routing capability in estimating delivery times at destination, we boost overall routing efficiency. Furthermore, we leverage the achieved accuracy in computing round-trip times and the corresponding maximum limits, for computing dynamic retransmission timeout intervals for end-to-end transport protocols.Initially, we study in an analytical way the plausible delivery times of a data unit at destination. We design a technique that leverages management statistics to construct time series on the error rates, and uses a forecasting procedure to predict future error rates. Based on the extracted forecasts and the protocol retransmission procedures, we provide analytical methods to obtain the retransmission probabilities and corresponding delays, accordingly. We also exploit information on the network connectivity, as well as links’ and data units’ parameters, to extract, for a given data unit, a probabilistic delivery latency profile, which comprises a list of possible arrival times at destination along with the corresponding probabilities. We implement the Bundle Delivery Time Estimation (BDTE) tool that realizes the proposed analytical methods, and incorporate it into ION implementation. Validation experiments show that it can efficiently provide delivery latency profiles, in an accurate way, and thus constitutes a useful tool for administrative purposes.We then focus on the queueing component of the total delivery delay, and introduce two different approaches to estimate it. In the first approach, we encode the queueing delay component and incorporate it as a distinct element of the network connectivity plan, which we name Earliest Transmission Opportunity (ETO). In order to exploit the obtained information, we propose an enhancement to the Contact Graph Routing (CGR) algorithm, namely CGR-ETO, to incorporate backlog information into routing decisions. We pair the introduced algorithm with an update protocol, namely Contact Plan Update Protocol (CPUP), which implements the dissemination of contact plan changes. This way, information on increased queue backlogs is disseminated through the network with CPUP messages, and, hence, network nodes’ inherent capability to calculate the corresponding delays for data transmissions is enhanced. In the second approach, we propose a proactive framework for estimating queueing delays through network statistics procedures and time series forecasting. We propose that network nodes extract queueing rate measurements in regular time intervals, and disseminate them to other network nodes using the CPUP dissemination mechanism. The obtained measurements are then stored in the contact plan, composing different time series between each pair of network nodes. The available time series information are then used to forecast future queueing rates, and the predictions are combined with the contact plan schedules to estimate the queueing delay for the data units to be transmitted. This way, the proposed estimation of the overall, end-to-end delivery delay incorporates the obtained forecasts of future queueing delays, and therefore can more accurately match the actual delays experienced in a congested network. Evaluation shows that both approaches can efficiently estimate the queueing delays and, hence, can provide more accurate predictions of total end-to-end delays. Furthermore, we observe, through both simulation and emulation studies, that the proposed CGR-ETO routing algorithm, based in its improved delay estimations, can improve routing decisions, and provide basic functionality of load balancing, as well as a way of proactively controlling the congestion that is observed with the capacity exhaustion of transmission windows.In the last part of this thesis, we exploit the introduced analytical methods and algorithms to improve the transport layer’s capability of estimating RTTs, and to enhance the efficiency of the end-to-end retransmission mechanism. To this end, we develop a novel, dynamic end-to-end retransmission framework that takes into account cross-layer information to estimate the major latency components, and combines them to calculate efficient retransmission timeout intervals using the maximum -within some boundaries- expected end-to-end delay, based on the worst-case network conditions that may be experienced on the routing paths. We develop the introduced framework as extension of Delay-Tolerant Payload Conditioning (DTPC) transport protocol, and incorporate it into ION DTN implementation. Emulation studies show that the advanced, more accurate RTT estimator provides faster retransmission of lost data, and significant reduction in the overall data transmission time, while keeping at the same time the overhead (due to duplicate transmissions) minimum. Finally, by achieving faster retransmission of lost data, the dynamic framework provides great reduction of the storage occupancy and utilization, primarily at destination node, when the in-order delivery feature of DTPC protocol is applied.

Στην παρούσα διδακτορική διατριβή μελετάμε το πρόβλημα της ακριβούς εκτίμησης του χρόνου μετάδοσης των δεδομένων από-άκρο-σε-άκρο, σε διαστημικά διαδίκτυα. Παρέχουμε λύσεις που αντιμετωπίζουν τις απαιτητικές συνθήκες των επικοινωνιών σε διαστημικά περιβάλλοντα και βελτιώνουν την εκτίμηση της καθυστέρησης μεταφοράς των δεδομένων σε διαφορετικές δικτυακές συνθήκες. Για να επιτύχουμε τους στόχους μας χρησιμοποιούμε τα Δίκτυα Ανεκτικά στην Καθυστέρηση και στις Διακοπές Επικοινωνίας (Delay/Disruption Tolerant Networking – DTN), μία δικτυακή αρχιτεκτονική που προτάθηκε πρόσφατα για να διασυνδέσει τις επικοινωνίες μεταξύ των διαφορετικών διαστημικών αποστολών και υπηρεσιών σε ένα Διαπλανητικό Διαδίκτυο. Εκμεταλλευόμενοι τις βασικές αρχές της αρχιτεκτονικής DTN και μελετώντας τις διαφορετικές δικτυακές συνθήκες, μοντελοποιούμε τα επιμέρους συστατικά της καθυστέρησης από-άκρο-σε-άκρο και βελτιώνουμε την εγγενή ικανότητα του δικτύου να τα προβλέπει με ακρίβεια.Αρχικά μελετάμε με αναλυτικό τρόπο την καθυστέρηση παράδοσης ενός πακέτου δεδομένων και σχεδιάζουμε την αντίστοιχη διαχειριστική εφαρμογή, με όνομα Bundle Delivery Time Estimation (BDTE). Η εφαρμογή αυτή εκμεταλλεύεται στατιστικές πληροφορίες που βρίσκονται σε μία διαχειριστική βάση δεδομένων καθώς και το πλάνο συνδεσιμότητας του δικτύου, για να προβλέψει τους μελλοντικούς ρυθμούς σφαλμάτων που υπάρχουν σε κάθε κανάλι σύνδεσης του δικτύου, και να υπολογίσει με ακρίβεια τις διαφορετικές καθυστερήσεις που μπορεί να συναντήσει το πακέτο στη διαδρομή που θα ακολουθήσει μέχρι την παράδοση στον προορισμό του. Οι διαφορετικές αυτές καθυστερήσεις περιέχουν ντετερμινιστικά συστατικά (καθυστερήσεις διάδοσης, καθυστερήσεις μετάδοσης, χρόνοι αναμονής για επαναφορά επικοινωνίας) καθώς και στοχαστικά συστατικά (καθυστερήσεις επαναναμετάδοσης χαμένων πακέτων), ενώ δε λαμβάνονται υπόψη οι καθυστερήσεις ουράς με την υπόθεση ότι το πακέτο είναι υψηλής προτεραιότητας. Το τελικό αποτέλεσμα της εφαρμογής είναι μία σειρά από διαφορετικούς πιθανούς χρόνους άφιξης του πακέτου στον προορισμό, καθώς και οι αντίστοιχες πιθανότητες για κάθε χρόνο.Στη συνέχεια επικεντρωνόμαστε στην εκτίμηση της καθυστέρησης ουράς που παρατηρείται κατά τη μετάδοση των δεδομένων σε διαστημικά διαδίκτυα. Για τη λύση του προβλήματος αυτού παρουσιάζουμε δύο διαφορετικές προσεγγίσεις. Στην πρώτη προσέγγιση ενσωματώνουμε πληροφορίες σχετικές με την καθυστέρηση ουράς στο πλάνο συνδεσιμότητας, με την παράμετρο Earliest Transmission Opportunity (ETO), η οποία χρησιμοποιείται από τον εξελιγμένο αλγόριθμο δρομολόγησης CGR-ETO, επιτυγχάνοντας τη βελτίωση της εκτίμησης του συνολικού χρόνου άφιξης των δεδομένων και επομένως την βελτιστοποίηση της δρομολόγησης. Η λειτουργία αυτή συμπληρώνεται από το πρωτόκολλο Contact Plan Update Protocol (CPUP), το οποίο σχεδιάστηκε για να διαχέει στο δίκτυο πληροφορίες για μεταβολές σε καθυστερήσεις ουράς. Στη δεύτερη προσέγγιση χρησιμοποιούμε στατιστικά δεδομένα του δικτύου για ρυθμούς μετάδοσης δεδομένων, καθώς και το πλάνο συνδεσιμότητας, για να προβλέψουμε με τη χρήση χρονοσειρών μελλοντικούς ρυθμούς άφιξης και προώθησης δεδομένων και επομένως καθυστερήσεις ουράς που θα εμφανιστούν σε μελλοντικές χρονικές στιγμές. Οι δύο αυτές τεχνικές προσεγγίζουν ικανοποιητικά την καθυστέρηση ουράς και συνεπώς επιτυγχάνουν σημαντικές βελτιώσεις στην ακρίβεια της εκτίμησης της συνολικής καθυστέρησης μετάδοσης. Στο τελευταίο μέρος της διατριβής προσαρμόζουμε την ανάλυση και τους αλγορίθμους που παρουσιάζονται προηγουμένως, στον υπολογισμό του χρόνου μετ’επιστροφής (round-trip time – RTT) για το επίπεδο μεταφοράς που εφαρμόζεται πάνω από την αρχιτεκτονική DTN και συγκεκριμένα για το πρωτόκολλο μεταφοράς DTPC. Σχεδιάζουμε ένα νέο, δυναμικό πλαίσιο επαναμεταδόσεων από-άκρο-σε-άκρο, το οποίο υπολογίζει τη μέγιστη (εντός ενός διαστήματος εμπιστοσύνης) τιμή του χρόνου μετ’ επιστροφής, για μια ομάδα πακέτων, και ορίζει αντίστοιχα το χρονισμό επαναμετάδοσης για αυτά τα πακέτα. Με αυτό τον τρόπο, επιτυγχάνουμε γρηγορότερες επαναμεταδόσεις των χαμένων πακέτων, μείωση στον συνολικό χρόνο μεταφοράς ενός συνόλου δεδομένων, και καλύτερη διαχείριση αποθηκευτικού χώρου από το πρωτόκολλο μεταφοράς, όταν αυτό παραδίδει τα δεδομένα στην εφαρμογή σε σειρά.Για την αποτίμηση των πρωτοκόλλων και μεθόδων που αναπτύχθηκαν σε αυτή τη διατριβή πραγματοποιήθηκαν μελέτες προσομοίωσης και εξομοίωσης σε εξειδικευμένα περιβάλλοντα. Συγκεκριμένα υλοποιήσαμε τον προσομοιωτή διαδικτύων SpaceDTNSim, που στοχεύει στις προσομοιώσεις δικτύων με προγραμματισμένη και διακοπτόμενη συνδεσιμότητα και υλοποιεί τον πυρήνα λειτουργικότητας της αρχιτεκτονικής DTN. Επιπλέον, πραγματοποιήσαμε δικτυακές εξομοιώσεις στο περιβάλλον του Spice Testbed, που χρηματοδοτήθηκε από την Ευρωπαϊκή Υπηρεσία Διαστήματος (ESA) και την Ευρωπαϊκή Επιτροπή (EC FP7) για να αποτελέσει ένα πρότυπο κέντρο εξομοίωσης διαστημικών διαδικτύων με ρεαλιστικές συνθήκες.