Traffic flow assignment for multi - homed wireless hosts system architecture and algorithms

Abstract

Multi-homing support in multi-radio terminals provides improved user experience through increased bandwidth capacity availability and reliability of wireless access. Furthermore, optimized assignment of application traffic flows to available interfaces and radio access bearer services contributes to economic and power consumption efficiency. The thesis studies the traffic flow assignment problem (TFAP) in a mobile node, multi-homed through a set of different technology radio interfaces. It introduces an analytical formulation for the problem and proves its hardness through reduction from the Multiple Knapsack Problem with Assignment Restrictions. Problem solutions are approximated with a heuristic algorithm that is based on local search and is characterized by efficient execution time. The quality of approximation is rather satisfactory and is evaluated through comparison of heuristic and exact solutions for a large set of randomly generated problem instances. An evaluation of the approach through simulation also supports these findings and provides an estimation of the associated mobility management overhead. The employment of advanced network selection (or handover decision) or TFAP algorithms cannot be based solely on end-host infrastructure. The decision mechanisms require locally available information and location-based network information that is not practical to be retrieved by the mobile terminal through active scanning. Moreover, reliable and in-time information on resource availability of available access networks may not be provided by a single network operator, e.g., the home operator, as it has no incentives to provide it and let its customers utilize third-party services. The thesis proposes a system architecture for supporting the execution of handover decisions or TFAP algorithms. The architecture spans multiple administrative domains and is based on software agents. The agents represent the users, the network operators, a Multi-Access Provider and the regulatory authority. Handover or traffic flow assignment decisions are delegated to agents that are user representatives and execute in the network for saving the terminal's limited power and computational resources. Decision making is initiated by user agents that execute either in the terminal or the network, depending on the source of handover triggering events. Performance evaluation of the architecture has been performed through simulation with focus on the impact on handover latency.

Η διατριβή στοχεύει στη βελτιστοποίηση της συνδεσιμότητας ενός κινητού τερματικού σε ένα ετερογενές περιβάλλον ασύρματης δικτυακής πρόσβασης. Συγκεκριμένα, γίνεται μελέτη του προβλήματος της κατανομής των ροών κίνησης ενός ασύρματου σταθμού που διαθέτει δυνατότητα ταυτόχρονης χρήσης πολλαπλών δικτυακών διεπαφών (multi-homed). Επιπλέον, γίνεται προδιαγραφή της αρχιτεκτονικής και μελέτη της επίδοσης ενός συστήματος για την υποστήριξη της εκτέλεσης αλγορίθμων κατανομής ροών κίνησης ή συναφών μηχανισμών απόφασης. Το πρόβλημα της κατανομής ροών κίνησης (traffic flow assignment problem-TFAP) αποτελεί προσαρμογή για multi-homed σταθμούς του προβλήματος επιλογής δικτύου πρόσβασης. Στα πλαίσια της διατριβής γίνεται αναλυτική διατύπωση του TFAP προβλήματος και μελέτη της πολυπλοκότητάς του. Καθώς το TFAP αποδεικνύεται ότι είναι NP-Hard, γίνεται προδιαγραφή ενός ευρετικού αλγορίθμου βασισμένου σε τοπική αναζήτηση για την προσεγγιστική επίλυσή του. Ο ευρετικός αλγόριθμος επιτυγχάνει ικανοποιητική ακρίβεια η οποία αξιολογείται μέσω της σύγκρισης των προσεγγιστικών λύσεων με τις ακριβείς λύσεις για ένα μεγάλο αριθμό τυχαία παραγομένων προβλημάτων. Η αξιολόγηση της προσέγγισης πραγματοποιείται επίσης και μέσω προσομοίωσης όπου γίνεται μελέτη του κόστους διαχείρισης κινητικότητας που υπεισέρχεται η συνεχής βελτιστοποίηση της κατανομής των ροών κίνησης ενός σταθμού. Η εκτέλεση αλγορίθμων επιλογής δικτύου ή κατανομής ροών κίνησης απαιτεί την μεταφορά στα σημεία απόφασης πληροφορίας η οποία είναι κατανεμημένη μεταξύ των ασύρματων σταθμών και των δικτύων πρόσβασης. Η έγκαιρη μεταφορά της στα σημεία απόφασης καθώς και η ολοκλήρωση ομοειδών δεδομένων από διαφορετικές πηγές αποτελούν προϋποθέσεις για την αξιόπιστη εκτέλεση των αλγορίθμων. Η συλλογή της παραπάνω πληροφορίας αυτόνομα από κάθε τερματικό είναι χρονοβόρα, ενώ η συγκέντρωση και παροχή της αποκλειστικά από τον οικείο πάροχο κάθε χρήστη θέτει ζητήματα αξιοπιστίας. Η διατριβή προτείνει την αρχιτεκτονική ενός συστήματος για την υποστήριξη της εκτέλεσης αλγορίθμων κατανομής ροών κίνησης ή επιλογής δικτύου πρόσβασης το οποίο λαμβάνει υπόψη τα παραπάνω ζητήματα. Το σύστημα είναι κατανεμημένο σε πολλαπλές διαχειριστικές περιοχές και είναι βασισμένο σε πράκτορες λογισμικού οι οποίοι εκπροσωπούν τους χρήστες, τους παρόχους και τη ρυθμιστική αρχή. Η διατριβή προδιαγράφει τις βασικές λειτουργίες του συστήματος και την ενσωμάτωσή του στη δικτυακή υποδομή ενός ετερογενούς ασύρματου δικτύου. Επιπλέον, παρέχει μελέτη θεμάτων που σχετίζονται με την επίδοσή του μέσω της υλοποίησης ενός συστήματος προσομοίωσης.