Η οπτική μεταγωγή καταιγισμών (Optical Burst Switching) είναι ένα ελπιδοφόρο παράδειγμα μεταγωγής για την επόμενη γενεά του Διαδικτύου. Ένα βασικό πρόβλημα στα δίκτυα OBS είναι η δρομολόγηση και ο χρονοπρογραμματισμός των καταιγισμών στους συνδέσμους του δικτύου, ώστε να μειωθεί η απώλεια και η καθυστέρηση τους. Εδώ παρουσιάζουμε έναν βασισμένο στην πηγή αλγόριθμο δρομολόγησης και χρονοπρογραμματισμού πολλαπλών κριτηρίων για την επιλογή μονοπατιών (διαδρομών) που ακολουθούνται από τους καταιγισμούς. Ο αλγόριθμος επιπλέον υπολογίζει και το χρόνο στον οποίο πρέπει να αρχίσει η μετάδοση των καταιγισμών ώστε να φθάσουν στον προορισμό με την ελάχιστη καθυστέρηση. Τα διαγράμματα χρησιμοποίησης (utilization profiles) των συνδέσμων του δικτύου, η καθυστέρηση διάδοσης των συνδέσμων και οι παράμετροι των καταιγισμών (μέγεθος, offset time κ.α.) διαμορφώνουν τα δεδομένα εισόδου του αλγορίθμου. Το προτεινόμενο σχήμα εκμεταλλεύεται τα κενά (void filling) που προκύπτουν από τη χρήση του bandwidth σε κάθε σύνδεσμο ώστε να βρεθεί η καλύτερη διαθέσιμη διαδρομή. Όταν δεν υπάρχει καμία κατάλληλη διαδρομή τη χρονική στιγμή που ζητείται από τον καταιγισμό, ο αλγόριθμος καθορίζει επίσης το χρονικό διάστημα (Time Offset) που πρέπει να καθυστερήσουμε τον καταιγισμό στην πηγή έως ότου γίνει διαθέσιμη η καλύτερη δυνατή διαδρομή. / Optical burst switching (OBS) is considered a promising switching paradigm for the next generation Internet. A key problem in OBS networks is the routing and scheduling of the bursts on the network links, so as to reduce burst loss and delay. In this paper we present a source-based multicost routing and scheduling algorithm to select the paths to be followed by the bursts and the times when the bursts should start transmission from their source so as to arrive at their destination with minimum delay. The utilization profiles of the network links, the link propagation delays, and the parameters of the bursts that have to be scheduled form the inputs to the algorithm. The proposed scheme exploits gaps in capacity utilization so as to find the best available path. When there is no suitable path at the time it is requested, the algorithm also determines the amount of time the burst must be delayed at the source for the best path to become available.

Στην παρούσα εργασία εξετάζουμε το πρόβλημα της δρομολόγησης σε δίκτυα ad-hoc, όπου οι κόμβοι είναι ακίνητοι και έχουν πεπερασμένα αλλά επαναφορτιζόμενα ενεργειακά αποθέματα. Αρχικά μελετάμε σε θεωρητική βάση τους ενεργειακούς και χωρητικούς περιορισμούς. Ενεργειακοί είναι οι περιορισμοί που οφείλονται στην μικρή ενεργειακή αυτοτέλεια των κόμβων, ενώ οι χωρητικοί περιορισμοί οφείλονται στην περιορισμένη χωρητικότητα του ασύρματου μέσου και στην παρεμβολή. Συγκεκριμένα εξετάζουμε πώς ορισμένα δικτυακά χαρακτηριστικά επηρεάζουν την απόδοση του δικτύου. Τέτοια δικτυακά χαρακτηριστικά είναι η πυκνότητα των κόμβων του δικτύου, η φυσική απόσταση τους, η ακτίνα μετάδοσης τους κ.α. Εξετάζουμε διαφόρων ειδών δίκτυα και σε γενικές γραμμές αποδεικνύουμε ότι η ενέργεια είναι ο κρίσιμος πόρος σε δίκτυα τα οποία είναι αραιά ή οι κόμβοι τους έχουν μικρό ρυθμό επαναφόρτισης της ενέργειας ή μεγάλη ακτίνα μετάδοσης. Στην αντίθετη περίπτωση η απόδοση των δικτύων περιορίζεται από την χωρητικότητα και την παρεμβολή. Επιπλέον προτείνουμε και υλοποιούμε έναν ενεργειακά-αποδοτικό αλγόριθμο δρομολόγησης με πολλαπλά κόστη, όπου ένα διάνυσμα από παραμέτρους, εν’αντιθέσει με μία μόνο παράμετρο, ανατίθεται σε κάθε σύνδεσμο του δικτύου. Σε κάθε ανακαλυπτόμενη διαδρομή ανατίθεται ομοίως ένα διάνυσμα παραμέτρων, που προκύπτει από τα αντίστοιχα διανύσματα των συνδέσμων της διαδρομής. Οι παράμετροι που χρησιμοποιούμε είναι ο αριθμός των συνδέσμων της διαδρομής, η υπολειπόμενη ενέργεια και η ισχύς μετάδοσης. Ο αλγόριθμος αυτός συγκρίνεται με τον αλγόριθμο ελάχιστου-μήκους διαδρομής, για την επίλυση του προβλήματος του άπειρου χρονικού ορίζοντα. Στο πρόβλημα του άπειρου χρονικά ορίζοντα, ενέργεια και νέα πακέτα δεδομένων δημιουργούνται συνεχώς σε κάθε κόμβο του δικτύου. Στα πειράματα που εκτελέσαμε μας ενδιαφέρει να υπολογίσουμε την μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax στους κόμβους, η οποία επιτρέπει στο δίκτυο μας να παραμένει ευσταθές. Ένα δίκτυο χαρακτηρίζεται ευσταθές όταν η εισερχόμενη κίνηση εξυπηρετείται από το δίκτυο με μικρή μέση καθυστέρηση παράδοσης αλλά και μεγάλο ποσοστό επιτυχούς παράδοσης των πακέτων δεδομένων στους προορισμούς τους. Όταν μία από αυτές τις συνθήκες δεν ισχύει τότε θεωρούμε ότι το δίκτυο είναι ασταθές και δεν μας ενδιαφέρει περαιτέρω η μελέτη του. Ουσιαστικά η μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax είναι η μέγιστη απόδοση του δικτύου μας. Η μέση καθυστέρηση παράδοσης των πακέτων δεδομένων ορίζεται ως ο μέσος χρόνος μεταξύ της δημιουργίας ενός πακέτου στον κόμβο-πηγή και της λήψης του πακέτου στον κόμβο-προορισμού. Το ποσοστό της επιτυχούς παράδοσης των πακέτων δεδομένων ορίζεται σαν τον λόγο του αριθμού των πακέτων που παρελήφθησαν επιτυχώς από τους κόμβους-προορισμού προς τον αριθμό των πακέτων που δημιουργήθηκαν στους κόμβους-πηγής. Κατά την διάρκεια των πειραμάτων μας δοκιμάζουμε διάφορες πιθανότητες δημιουργίας πακέτων δεδομένων p και διάφορους ρυθμούς επαναφόρτισης των κόμβων X. Από τα αποτελέσματα των πειραμάτων μας παρατηρούμε ότι ο ενεργειακά-αποδοτικός αλγόριθμος δρομολόγησης με πολλαπλά κόστη υπερτερεί του αλγορίθμου ελάχιστου-μήκους διαδρομής, πετυχαίνοντας όταν το δίκτυο είναι ενεργειακά περιορισμένο, μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax σχεδόν διπλάσια από αυτή που πετυχαίνει ο ελάχιστου-μήκους διαδρομής αλγόριθμος. Ακόμα παρατηρούμε ότι η μέση καθυστέρηση καθώς και το ποσοστό επιτυχούς παράδοσης των πακέτων δεδομένων παρουσιάζουν καλύτερα αποτελέσματα με την χρήση του ενεργειακά-αποδοτικού αλγορίθμου. Επιπλέον παρατηρούμε ότι η μέση καθυστέρηση αυξάνει πολύ απότομα σε σχέση με την πιθανότητα δημιουργίας πακέτων δεδομένων p, όταν το δίκτυο γίνεται ασταθές λόγο των ενεργειακών περιορισμών. Αντίθετα η αύξηση αυτή είναι πολύ πιο ομαλή, όταν το δίκτυο γίνεται ασταθές λόγο των χωρητικών περιορισμών. / In our thesis we examine the problem of routing in ad-hoc networks, where the nodes are stationary and have limited but rechargeable energy reserves. Initially we study theoretically, the energy and the capacity constraints. The energy constraints are the result of the limited energy reserves of the nodes, while the capacity constraints are the result of the limited capacity and of the interference in the wireless medium. In our theoretically study we examine how the various network characteristics, influence the network performance. Such network characteristics are the nodes density, their distance, the transmission radius etc. We examine various network topologies and in every case we prove that energy is a vital resource in networks which are sparsely or where the nodes have small recharge rate or big transmission radius. In every other case the performance of a network is constrained by the capacity and the interference. Furthermore we propose and implement an energy-aware multicost routing algorithm, where a vector of parameters, instead of just one parameter, is assigned to each link of the network. In the same way in every discovered path, a vector of parameters is assigned. This vector is calculated using the vectors of the links from which the path consists of. The parameters used are the hops number, the residual energy and the transmission power. The proposed algorithm is compared with the minimum-hop algorithm, under the infinite time horizon problem. In this problem energy and data packets are constantly created in every node of the network. In our experiments we are interested in finding the maximum packet generation probability pmax in the nodes, under which the network remains stable. A network is characterized as stable when the incoming traffic is served by the network with small average delivery delay and big successful delivery ratio, of the packets in their destinations. When one of these conditions doesn’t hold, then we assume that the network is unstable and we do not study it anymore. The maximum packet generation probability pmax is in fact the maximum throughput of the network. The average delivery delay is defined as the average time between the creation of a data packet in the source-node and the reception of the packet in the destination-node. The successful delivery ratio is defined as the ratio of the number of packets successfully received by their destinations by the number of packets created in the source-nodes. During our experiments we tried various packet generation probabilities p and recharge rates at the nodes X. From the results of ours experiments we observe that the energy-aware multicost routing algorithm outperforms the minimum-hop algorithm. Specifically when the network is energy constrained, the maximum packet generation probability pmax is almost double as the one achieved by the minimum-hop algorithm. Furthermore the average delivery delay and the successful delivery ratio present better results using the energy-aware algorithm. Also we generally observe that the average delivery delay increases suddenly as the packet generation probability p increases, when the network becomes unstable because of the energy constraints. On the other hand the increase in the average delivery delay is much more normal, when the network becomes unstable because of the capacity constraints.

Το πρόβλημα εύρεσης συντομότερης διαδρομής είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην δρομολόγηση σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει ταυτόχρονα η ελαχιστοποίηση του χρόνου και του κόστους σε χρήματα. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές οι περιπτώσεις η ``καλύτερη\\\\ / The shortest path problem is perhaps the most fundamental single objective optimization problem in networks. In many applications however we are interested in more than two objectives. For example, when routing in a network with tolls, we are interested in minimizing both the time and the cost. Similar examples can be also found in communication networks where the criteria under investigation are the delay, the fault probability, the number of hops and other. In such cases the \\\\