Exploit link-state routing to improve TCP in mobile ad hoc networks

Abstract

The present thesis exploits the link-state routing paradigm to improve the end-to-end throughput of mobile ad hoc networks by providing an enhanced network layer to TCP. Apart from the use of proactive, i.e., link-state, routing, the main purpose of the thesis is to leave TCP intact. Neither its core functionality nor its end-to-end semantics subject to changes. TCP is considered to operate in impromptu, self-organised and self-congured networks, in the absence of any pre-existing infrastructure. The protocol stack considered incorporates TCP operating over potentially mobile nodes, with a network layer managed by OLSR and with an IEEE 802.11 MAC layer. The study begins with an evaluation of the TCP's behaviour in static and mobile ad hoc networks. To achieve a long-term performance evaluation, a scalable optimised simulation model for TCP is introduced, which allows to reach long simulation times. The model allows to obtain stable results for the network's throughput, and to study the behaviour and the interactions of the involved protocols.Following the results of the performance study, the mechanisms of proactive routing are exploited to propose an enhanced and more efficient network layer for TCP. The approach is twofold. First, we investigate how TCP can be improved in the presence of QoS link-state routing. Second, the link-state protocol is used to generate appropriate feedback and convey it to TCP, which in turn adapts its retransmission timer and its congestion window limit accordingly. The solutions proposed by this thesis are as follows. TCP is first evaluated over a delay-based routing scheme with a path locking optimisation. Such an approach provides low delay paths to the TCP connections, avoiding at the same time the route oscillations. Furthermore, the routing protocol makes estimations about the network delays, both locally between neighbours, as well as end-to-end. It conveys the delay information to TCP, which adapts its retransmission timer. Finally, a delay-based expression for the bandwidth-delay product is introduced to set the congestion window limit of TCP dynamically. Traditionally, the latter has a fixed value. The main consideration of the present work is to maintain the fundamental TCP's operation and algorithms. Apart from preserving the TCP's semantics, wealso aim at keeping the design of any proposed mechanism simple and realistic, so that the solutions are scalable.

Στην παρούσα εργασία αξιοποιούμε τη δυναμική δρομολόγηση για τη βελτίωση του πρωτοκόλλου μεταφοράς δεδομένων (TCP) πάνω από ασύρματα δίκτυα αυθαίρετης δομής πολλαπλών βημάτων, τεχνολογίας ΙΕΕΕ 802.11. Εκτός από τη χρήση δυναμικής δρομολόγησης, για την οποία επιλέγεται το πρωτόκολλο βελτιστοποιημένης δρομολόγησης κατάστασης ζεύξεων (OLSR) κύριος στόχος της εργασίας είναι το πρωτόκολλο μεταφοράς να μείνει αμετάβλητο. Ούτε οι κεντρικές του δομές και λειτουργίες, αλλά ούτε και η από άκρο-σε-άκρο συμπεριφορά του υπόκεινται σε αλλαγές. Αφετηρία της εργασίας είναι η αξιολόγηση του TCP πάνω από στατικά και κινητά δίκτυα. Προς την κατεύθυνση αυτή, είναι επιθυμητό τα όποια αποτελέσματα να είναι ευσταθή. Διερευνούμε την ευστάθεια των αποτελεσμάτων με προσομοιώσεις σε μακρό χρόνο. Καθώς τα υπάρχοντα μοντέλα δεν επιτρέπουν μεγάλους χρόνους προσομοίωσης σε ρεαλιστικό πραγματικό χρόνο, αναπτύσσουμε ένα νέο, βελτιστοποιημένο μοντέλο, που επιτρέπει να φτάσουμε σε διάρκεια προσομοίωσης ημέρες ή εβδομάδες, σε πραγματικό χρόνο της τάξης μερικών ωρών. Κύριο χαρακτηριστικό του μοντέλου είναι η αναπαράσταση του δικτύου με μια πολλαπλή ουρά, κάθε στοιχείο της οποίας αντιπροσωπεύει έναν ασύρματο σταθμό. Συνεπώς, η ανταλλαγή πακέτων στο δίκτυο είναι ουσιαστικά μια ακολουθία από ενταμιεύσεις και εκταμιεύσεις πακέτων στις αντίστοιχες ουρές. Το μοντέλο αυτό πετυχαίνει δραματική μείωση των συμβάντων (events) της προσομοίωσης, και μειώνει το χρόνο εκτέλεσης. Μελετώντας σενάρια ασύρματων δικτύων, διαπιστώνουμε ότι χρειάζονται αρκετές ώρες προσομοίωσης ενός συστήματος, ώστε τα αποτελέσματα να είναι ευσταθή. Στα υπάρχοντα μοντέλα ευσταθείς εκτιμήσεις επιτυγχάνονται με την επανάληψη του πειράματος με διαφορετικούς σπόρους και υπολογίζοντας το μέσο όρο στις τιμές των αποτελεσμάτων. Αντ’ αυτού, προτείνουμε την εκτέλεση ενός και μόνο πειράματος, έως ότου τα αποτελέσματα σταθεροποιηθούν. Μερική διερεύνηση του χρόνου που απαιτείται για την ευστάθεια των αποτελεσμάτων παρουσιάζει η παρούσα εργασία. Εκτενής διερεύνηση και πιστοποίηση του μοντέλου δεν είναι στα πλαίσια αυτής. Το μοντέλο χρησιμοποιείται ως εργαλείο για τη βελτίωση του TCP με χρήση δυναμικής δρομολόγησης, ως ακολούθως. Αρχικά, το TCP μελετάται πάνω από δρομολόγηση βάσει της μετρικής της από άκρο-σε-άκρο καθυστέρησης του δικτύου, αντί του αριθμού βημάτων. Η δρομολόγηση βάσει παραμέτρων ποιότητας υπηρεσίας (QoS) είναι πολύ δημοφιλής σε εφαρμογές πραγματικού χρόνου, που συνήθως δεν υποστηρίζονται από το TCP, αλλά το τελευταίο είναι ένα πρωτόκολλο ευαίσθητο στην καθυστέρηση. Η παραπάνω τεχνική δρομολόγησης βελτιώνει τον χρόνο μετ’ επιστροφής των πακέτων, αλλά εισάγει ταλαντώσεις στο μονοπάτι που επιλέγεται γι’ αυτά. Στην περίπτωση του TCP, οι ταλαντώσεις προκαλούν την παράδοση πακέτων εκτός σειράς στον TCP παραλήπτη, γεγονός επιβλαβές για τη λειτουργία και απόδοση του πρωτοκόλλου. Για την εξάλειψη του φαινομένου των ταλαντώσεων εισάγουμε μια βελτιστοποίηση στον αλγόριθμο δρομολόγησης, σύμφωνα με την οποία η δρομολόγηση γίνεται ανά ροή και όχι ανά κόμβο προορισμού. Το μονοπάτι για κάθε ροή “κλειδώνει” και δε μεταβάλλεται, με την προϋπόθεση ότι υπάρχει συνδεσιμότητα. Η τεχνική αυτή βελτιώνει αισθητά τη διαπερατότητα του δικτύου, χωρίς να θέτει ιδιαίτερο ζήτημα στην κλιμάκωση κατά την εφαρμογή της. Κατόπιν, αξιοποιούμε το πρωτόκολλο δυναμικής δρομολόγησης για να παράγουμε πληροφορία καθυστέρησης του δικτύου, την οποία χρησιμοποιούμε για τη βελτίωση του TCP με δύο τρόπους. Πρώτον, για να θέσουμε το μηχανισμό χρονοκαθυστέρησης επαναμετάδοσης του TCP με τρόπο πιο ακριβή από τον υπάρχων, και δεύτερον για να υπολογίσουμε δυναμικά την ανώτατη τιμή του παραθύρου συμφόρησης. Κλασσικά, το τελευταίο παίρνει ένα ανώτατο επιτρεπόμενο όριο με στατικό τρόπο. Η πληροφορία για την καθυστέρηση του δικτύου παράγεται με τη βοήθεια του μηχανισμού ανταλλαγής πακέτων ελέγχου, τα οποία τα -κατά βάση κατανεμημένα- πρωτόκολλα δυναμικής δρομολόγησης ανταλλάσσουν περιοδικά. Στον υπολογισμό λαμβάνουμε υπόψη και τα χαρακτηριστικά του πρωτοκόλλου επιπέδου πρόσβασης (MAC 802.11). Σε όλες τις περιπτώσεις, οι προτεινόμενοι μηχανισμοί αξιολογούνται μέσω προσομοιώσεων χρησιμοποιώντας το μοντέλο που αναπτύχθηκε στην αρχή της εργασίας. Τα αποτελέσματα είναι ενθαρρυντικά και, ειδικά στην περίπτωση του περιορισμού της μέγιστης τιμής του παραθύρου, αιτιολογούν την υλοποίηση του μηχανισμού σε πραγματικά συστήματα.