Στόχος της παρούσας εργασίας, είναι η σχεδίαση και η υλοποίηση ενός προγράμματος, το οποίο θα υπολογίζει την βέλτιστη διαδρομή μεταξύ δύο σημείων στην πόλη της Πάτρας, το οποία συνδέονται με αστική συγκοινωνία. Στα πλαίσια της εργασίας αυτής, συγκεντρώθηκαν τα δεδομένα που αφορούν τις διαδρομές των λεωφορείων, τα δρομολόγια και οι χρόνοι μετάβασης. Στη συνέχεια, τα δεδομένα αυτά κωδικοποιήθηκαν κατάλληλα και δημιουργήθηκε πρόγραμμα το οποίο θα τα χρησιμοποιεί για να υπολογίζει την βέλτιστη δρομολόγηση μεταξύ δύο σημείων που θα επιλέγει ο χρήστης. Το πρόγραμμα παρέχεται και ως ανεξάρτητη εκτελέσιμη εφαρμογή αλλά και ως υπηρεσία web, με δυνατότητα εγκατάστασης στον web server του εργαστηρίου. / The main purpose of this Diploma Thesis is the development of a computer program, that is going to estimate the best route between two city points in the city of Patras. These two places are accessible by Patras public transportation system. For this project, we gathered all the appropriate data that are related with the bus routes, the routes, and the time between subsequent bus stop. Furthermore, these data were encoded in such a way, that they are accessible by our program, which calculates the best route between two points chosen by a user. This program was developed as an independent executable application but also as a web service, with the ability to be uploaded in the laboratory’s web server.

Το πρόβλημα εύρεσης συντομότερων διαδρομών είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε αυτό το πρόβλημα αναζητείται η συντομότερη διαδρομή μεταξύ δύο δεδομένων σημείων ελαχιστοποιώντας ένα κριτήριο κόστους. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην εύρεση διαδρομών σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει εκτός από την διανυμένη απόσταση και η ελαχιστοποίηση του χρόνου και του κόστους. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές τις περιπτώσεις η καλύτερη λύση δεν μπορεί να οριστεί με μονοσήμαντο τρόπο, και συνεπώς καταφεύγουμε σε αντισταθμίσεις μεταξύ των παραγόντων, που είναι γνωστές ως σύνολο λύσεων κατά Pareto. Παρόλο που για το πρόβλημα μονοκριτηριακής εύρεσης συντομότερων διαδρομών υπάρχουν πολλοί αποδοτικοί αλγόριθμοι για την επίλυση του προβλήματος, το αντίστοιχο πολυκριτηριακό πρόβλημα είναι πολύ πιο σύνθετο. Μέχρι τώρα, αυτό το πρόβλημα έχει αποδειχθεί ότι είναι NP-πλήρες. Επιπλέον, έχει αποδειχθεί ότι το πλήθος των λύσεων σε αυτό το πρόβλημα αυξάνεται εκθετικά σε σχέση με το μέγεθος της εισόδου. Υπάρχουν δύο βασικές προσεγγίσεις επίλυσης τέτοιων προβλημάτων, όπου εξετάζονται πολλαπλά κριτήρια. α) Η πρώτη μέθοδος βρίσκει προσεγγιστικές λύσης κατά έναν ορισμένο παράγοντα. Οι προσεγγιστικές μέθοδοι δεν βρίσκουν απαραίτητα ακριβείς λύσεις, αλλά είναι σχετικά γρήγορες και προσφέρουν εγγύηση για το ποσοστό απόκλισης από την βέλτιστη λύση. β) Η δεύτερη μέθοδος χρησιμοποιεί ευρετικές βελτιώσεις για να επιταχύνει τους ήδη υπάρχοντες αλγορίθμους. Τέτοιες τεχνικές βρίσκουν ακριβείς λύσεις, και το ζητούμενο είναι να επιτευχθεί μια πολύ καλή χρονική απόδοση. Στην παρούσα διπλωματική εργασία επικεντρωνόμαστε στην δεύτερη μέθοδο, υποκινούμενοι από την μεγάλη ζήτηση πρακτικών εφαρμογών για εύρεση αποτελεσματικής και ακριβούς λύσης του προβλήματος συντομότερων διαδρομών υπό πολλαπλά κριτήρια. Πιο συγκεκριμένα, στην εργασία αυτή παρουσιάζουμε ένα ενοποιημένο πλαίσιο για την αποδοτική επίλυση αυτών των προβλημάτων. Προτείνουμε νέες μεθόδους ή βελτιώσεις των υπαρχόντων. Υλοποιήσαμε τις μεθόδους που παρουσιάζουμε συνοδεύοντάς τις με μια εκτενή πειραματική μελέτη πάνω σε δίκτυα ευρείας κλίμακας. / We present new implementations of heuristic algorithms for the solution of the multiobjective shortest path problem, using a new graph structure specifically suited for large scale road networks. We enhance the heuristics with further optimizations and experimentally evaluate the performance of our enhanced implementation on real world road networks achieving 10 times better performance with respect to the best previous study.

Στην εργασία αυτή, μελετήθηκε η δομή του σύγχρονου ίντερνετ από την σκοπιά του δικτύου και κατέστη σαφές το πως διασυνδέονται οι πάροχοι υπηρεσιών και οι τερματική χρήστες, πως γίνεται η δρομολόγηση και ποιοί αλγόριθμοι χρησιμοποιούνται για τιν επίτευξη της. / This diploma thesis focus on how modern networks connect together in order to create the internet and which algorithms used for the routing of informations that traverse through them.

Αντικείμενο της παρούσας διπλωματικής εργασίας αποτελεί η μελέτη της τηλεπικοινωνιακής κίνησης σε οπτικά δίκτυα δρομολόγησης μήκους κύματος. Στα πλαίσια της αποτίμησης της απόδοσής τους, υπολογίζεται η πιθανότητα φραγής κλήσης (Call Blocking Probability) για ένα σύνολο δοσμένων διαδρομών. Αφού αρχικά γίνεται αναφορά στην ιστορία και την εξέλιξη της τεχνολογίας των οπτικών ινών και των οπτικών δικτύων, το θέμα της εργασίας επικεντρώνεται στα οπτικά δίκτυα σταθερής δρομολόγησης και σταθερής εναλλακτικής δρομολόγησης. Γίνεται χρήση δύο αναλυτικών μοντέλων υπολογισμού της πιθανότητας απωλειών σε αυτά: το μοντέλο Birman και το μοντέλο Sridharan-Sivarajan, τα οποία υλοποιούνται στη γλώσσα προγραμματισμού C. Τα αποτελέσματα των μεθόδων ανάλυσης για συγκεκριμένα παραδείγματα συγκρίνονται με αυτά της προσομοίωσης, που υλοποιείται με χρήση της γλώσσας προσομοίωσης SIMSCRIPT II.5. Επιπρόσθετα, εξετάζεται η τεχνική της ομοιοκαταχώρησης τηλεπικοινωνιακής κίνησης (Traffic grooming) με προσομοίωση της λειτουργίας οπτικών δικτύων που κάνουν χρήση της τεχνικής αυτής. / The main objective of this diploma thesis is the study of the telecommunication traffic in Wavelength-Routed Optical Networks. In the frames of their performance evaluation, Call Blocking Probabilities for given routes are calculated. Firstly, the history and evolution of optical fibers and optical networks are described. Followingly, the present thesis is focused in Wavelength-Routed Optical Networks for two routing schemes: Fixed Routing and Fixed Alternate Routing. Two analytical models are used for the calculation of blocking probabilities for these optical networks: Birman model and Sridharan-Sivarajan model, which are realized in C programming language. Afterwards, both these analytical techniques and the simulation, which is realised in SIMSCRIPT II.5 simulation language, are applied in particular examples and their equivalent results are compared. In addition, the Traffic-Grooming technique is examined by simulating the operation of optical networks which use this specific technique.

Η παρούσα εργασία αφορά την παρουσίαση μιας νέας ιδέας στην δρομολόγηση των ασυρμάτων ad hoc δικτύων, την δομημένη δρομολόγηση. Η ιδέα αυτή εξελίχθηκε σταδιακά στην διάνοιά μου τον τελευταίο ένα χρόνο, η ιδέα για την δόμηση μιας υπερκείμενης δομής πάνω από ένα ασύρματο ad hoc δίκτυο που θα καθοδηγούσε την αναζήτηση του κόμβου προορισμού. Η έρευνά μου είχε αρχίσει από τα p2p δίκτυα και τις δομές. Κάποια στιγμή συνειδητοποίησα ότι όλα αυτά είχαν άμεση σχέση με τα ad hoc δίκτυα. Όταν τελικά διαπίστωσα την ευρεία υιοθέτηση της πλημμύρας στους αλγορίθμους δρομολόγησης στα ad hoc, ήμουν βέβαιος πως σίγουρα θα μπορούσαμε να κάνουμε κάτι καλύτερο. Να αντικαταστήσουμε την αδόμητη, τυφλή, τεχνική της πλημμύρας με μια δομημένη, κατευθυνόμενη, αναζήτηση που θα ελαχιστοποιούσε την επιβάρυνση στο δίκτυο. Έτσι άρχισε η αναζήτησή μου, που κατέληξε στην ανάπτυξη του πρωτοκόλλου CONOS. Ενός πρωτοκόλλου που φιλοδοξεί να μετατρέψει τα ad hoc δίκτυα από μια εξειδικευμένη τεχνική σε μια καθημερινή πραγματικότητα. Το πρωτόκολλο CONOS περιγράφεται αναλυτικά στο δεύτερο μέρος αυτής της αναφοράς, και όπως φαίνεται από τις μετρήσεις που έχω κάνει, όντως ελαχιστοποιεί την επιβάρυνση στην αναζήτηση του κόμβου προορισμού. Ωστόσο απομένει να γίνει και άλλη έρευνα, το κεφάλαιο 6 συνοψίζει διάφορα ανοιχτά θέματα και προτάσεις για την αντιμετώπισή τους. / -

Στην διπλωματική εργασία παρουσιάζεται μια νέα δομή δεδομένων ειδικά σχεδιασμένη για δίκτυα μεταφορών ευρείας κλίμακας τα οποία αλλάζουν δυναμικά. Η νέα δομή δεδομένων γραφημάτων μας παρέχει ταυτόχρονα τρία μοναδικά χαρακτηρισ τικά: 1. Σύμπτυξη(Compactness): ικανότητα να προσπελάσει αποδοτικά διαδοχικές κορυφές και ακμές, μια απαίτηση όλων των αλγορίθμων γραφημάτων). 2. Ευκινησία (Agility): ικανότητα να αλλάξει και να ρυθμίσει εξαρχής την εσωτερική της διάταξη με σκοπό να βελτιώσει την τοπικότητα των αναφορών των στοιχείων, σύμφωνα με έναν δεδομένο αλγόριθμο. 3. Δυναμικότητα (Dynamicity): ικανότητα να ενθέσει ή να διαγράψει αποδοτικά κορυφές και ακμές. Όλες οι προηγούμενες γνωστές δομές γραφημάτων δεν υποστήριζαν τουλάχιστον ένα από τα προηγούμενα χαρακτηριστικά ή/και δεν μπορούσαν να εφαρμοστούν σε δυναμικά δίκτυα μεταφορών ευρείας κλίμακας. Σε αυτή τη διπλωματική εργασία, παρουσιάζεται η πρακτικότητα της νέας δομής γραφημάτων εκτελώντας μια εκτενή πειραματική μελέτη για δρομολόγηση συντομότερων διαδρομών σε Ευρωπαϊκά οδικά δίκτυα ευρείας κλίμακας με μερικές δεκάδες εκατομμύρια κορυφές και ακμές. Χρησιμοποιώντας κλασικούς αλγόριθμους εύρεσης συντομότερων διαδρομών, επιτυγχάνονται εύκολα χρόνοι ερωτημάτων από μια αρχική κορυφή σε μια τελική κορυφή της τάξης των milliseconds, ενώ η νέα δομή γραφημάτων μας μπορεί να ενημερωθεί σε μόλις μερικά microseconds μετά από μια ένθεση ή διαγραφή μιας κορυφής ή ακμής. / We present a new graph data structure specifically suited for large scale transportation networks in dynamic scenario. Our graph data structure provides tree unique characteristics, namely compactness, agility and dynamicity. All previous data structures were lacking support in at least one of the aforementioned characteristics. We demonstrate the practicality of the new graph data structure by conducting experiments on large scale European road networks, achieving query times of classical routing algorithms in the order of milliseconds and update times in the order of a few microseconds.

Το βασικό χαρακτηριστικό των ασύρματων δικτύων αυθαίρετης τοπολογίας (wireless ad hoc networks) είναι πως δεν απαιτούν την ύπαρξη σταθερής υποδομής (σε αντίθεση π.χ. με τα κυψελωτά δίκτυα). Ένα ιδιαίτερα σημαντικό παράδειγμα τέτοιων δικτύων αποτελούν τα λεγόμενα δίκτυα αισθητήρων (sensor networks), τα οποία μπορούν να χρησιμοποιηθούν σε τομείς όπως η παρακολούθηση και καταγραφή φυσικών φαινομένων, ή η προσωρινή δημιουργία δικτύου επικοινωνίας σε περιοχές που έχουν πληγεί από κάποια καταστροφή, κλπ., και επομένως αποτελούν μια ερευνητική περιοχή μεγάλου ενδιαφέροντος. Στα δίκτυα αυτά, όταν ένας κόμβος πρέπει να στείλει ένα πακέτο σε κόμβο που βρίσκεται εκτός της ακτίνας μετάδοσης του, τότε η μετάδοση γίνεται μέσω κόμβων που βρίσκονται πάνω σε μια διαδρομή μεταξύ αυτών των δύο κόμβων. Επειδή, όμως, οι κόμβοι αυτοί συνήθως έχουν περιορισμένη ενέργεια, ο τρόπος δρομολόγησης είναι καθοριστικός για τη λειτουργία του δικτύου. Τα πρωτόκολλα δρομολόγησης βασίζονται σε διάφορες μεθόδους όπως: κάθε κόμβος να επικοινωνεί μόνο με ορισμένους από τους γείτονες του, ή κάθε κόμβος να επιλέγει κόμβους στους οποίους θα μεταδώσει πακέτα με βάση τη γεωμετρική θέση τους. Μια άλλη μέθοδος δρομολόγησης είναι η κατασκευή ενός εικονικού δικτύου υποδομής, οι κόμβοι του οποίου είναι κόμβοι του ασύρματου δικτύου και οι ακμές του οποίου χρησιμοποιούνται για τη μεταφορά των πακέτων. Η κατασκευή του δικτύου υποδομής πρέπει να πραγματοποιηθεί με κατανεμημένο τρόπο και το μέγεθος και η δομή του πρέπει να είναι τέτοια ώστε η δρομολόγηση να απαιτεί όσο το δυνατόν λιγότερη κατανάλωση ενέργειας από τους κόμβους. Στα πλαίσια της διπλωματικής αυτής εργασίας: 1) Αναπτύχθηκαν δύο νέες μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας μέσω κατασκευής εικονικών δικτύων υποδομής. Οι μέθοδοι αυτοί βασίζονται σε αντίστοιχους αλγόριθμους κατασκευής επικαλυπτόντων υπογραφημάτων και έχουν την ιδιότητα ότι τα εικονικά δίκτυα που παράγονται έχουν σχετικά μικρό αριθμό ακμών, ενώ παράλληλα η απόσταση μεταξύ δύο κόμβων στο εικονικό δίκτυο είναι το πολύ t φορές μεγαλύτερη από την ελάχιστη απόσταση τους στο αρχικό δίκτυο (όπου t είναι παράμετρος που εξαρτάται από τον αλγόριθμο). 2) Υλοποιήθηκαν οι δύο αυτές νέες μέθοδοι δρομολόγησης σε κατάλληλο περιβάλλον εξομοίωσης και έγινε εκτενής πειραματική αξιολόγηση τους. / The characteristic feature of wireless ad hoc networks is that there is no fixed infastructure (in constrast with cellular networks). One considerabe example of such networks is sensor networks, which can be used to monitor a natural phenomenon, or to construct a temporary communication network in areas where a disaster has occurred, etc, therefore wireless ad hoc networks is a research area of great interest. In wireless ad hoc networks when a node needs to send a message to a node which relies outside of its transmission range, then the transmission takes place through the nodes which rely on a path which connects these two nodes. The wireless nodes, however, have limited energy, therefore routing method is crusial for the operation of the network. Routing protocols are based on several methods, such as: each node is allowed to communicate with only a selected subset of its neighbors, or each node chooses to transmits a message to one of its neighbors based on its geometrical position. Another routing method is to construct a virtual backbone network. The virtual network has the same nodes as the ad hoc network, but only its links are used for the routing of messages. The construction of the virtual network must be executed in a distributed way and its size and structure must be suitable to allow the nodes to consume as less energy as possible in order to support the routing protocol. In this work 1) we have developed two new routing methods for wireless ad hoc networks by constructing virtual networks. These two methods are based on corresponding algorithms for maintaining spanners. The virtual networks constructed have relatively small number of links, while having the ability that for every pair of nodes their distance in the virtual network is at most t times their distance in the ad hoc network (parameter t depends on the algorithm). 2) we have implemented these two algorithms in a simulation environment, and we have conducted an extensive study on them.

Είναι γεγονός ότι, τα τελευταία χρόνια, η χρήση των κινητών δικτύων τρίτης γενιάς έχει αρχίσει να επεκτείνεται. Οι υπηρεσίες που απευθύνονται σε ομάδες χρηστών θα αποτελέσουν μία νέα κατηγορία προηγμένων υπηρεσιών προς στους κινητούς χρήστες. Στα συμβατικά ενσύρματα δίκτυα, η χρήση multicast μηχανισμών είναι αυτή που συνήθως ενδείκνυται για αυτή την κατηγορία υπηρεσιών. Ένας multicast μηχανισμός μεταδίδει τα δεδομένα μόνο μία φορά πάνω από κάθε σύνδεσμο που αποτελεί τμήμα των μονοπατιών προς τους προορισμούς. Είναι προφανής η αύξηση της απόδοσης που προσφέρει το multicasting καθώς ελαχιστοποιεί τη χρήση των πόρων του δικτύου. Επομένως, η εφαρμογή του multicasting σε ένα κινητό δίκτυο έχει αρκετά διαφορετικά χαρακτηριστικά σε σχέση με την εφαρμογή του στο Internet. Κατά συνέπεια, δημιουργείται η ανάγκη για νέους μηχανισμούς οι οποίοι θα καλύψουν τις ιδιαιτερότητες των κινητών δικτύων. Στην παρούσα διπλωματική εργασία προτείνεται ένας μηχανισμός που εκτελεί multicast μετάδοση δεδομένων στο σύστημα UMTS. Ο συγκεκριμένος μηχανισμός εκμεταλλεύεται τη δενδρική τοπολογία των κινητών δικτύων και εισάγει τη χρήση των Routing Lists (RLs) στους κόμβους του UMTS. Η χρήση και η ενημέρωση των RLs γίνεται από τον προτεινόμενο μηχανισμό με τρόπο που παρουσιάζεται αναλυτικά. Επίσης, εξετάζονται διεξοδικά τα πιθανά σενάρια τα οποία περιλαμβάνουν όλες τις περιπτώσεις κινητικότητας των χρηστών. Ειδικότερα, εξετάζονται οι διάφοροι τύποι handover καθώς και η διαδικασία SRNS relocation. Τέλος, ο συγκεκριμένος μηχανισμός εξομοιώνεται στον network simulator ns-2. Μέσω της εξομοίωσης διερευνάται η ορθότητα του μηχανισμού καθώς και η αποδοτικότητά του. / It is a matter of fact that the third generation cellular networks are being deployed all over the world. A set of new services which will be provided by these networks, are those who address to user groups. Wireline networks use multicast mechanisms for the provision of similar services. A multicast mechanism transmits the same data once over each link of the path from the source to the destinations. Obviously, multicasting leads to the efficient use of the network resources. Nevertheless, the adoption of this kind of mechanisms by a mobile network is quite complicated and new schemes are required. In this master thesis, I present a mechanism for the multicast transmission of data in UMTS. This mechanism takes advantage of the tree topology of the examined networks and introduces the use of Routing Lists (RLs) in the nodes of UMTS. The use and the update of RLs are performed by the proposed mechanism and each step of these procedures is described in detail. Furthermore, I analyze the handling of special cases such as user mobility scenarios. Especially, the various handover types are examined along with the SRNS relocation procedure. Finally, I implement this approach in the ns-2 simulator. Through this simulation, I investigate the correctness and the efficiency of the proposed mechanism.

Η διπλωματική αυτή σκοπό έχει να μελετήσει στρατηγικές οι οποίες έχουν ως στόχο την αύξηση της αποδοτικότητας με κριτήριο την ενέργεια σε ad hoc δίκτυα. Σε αυτού του είδους τα δίκτυα η ενέργεια είναι κρίσιμος πόρος και η εξοικονόμησή της είναι κρίσιμος παράγοντας. Θα ακολουθήσουμε τον αλγόριθμο δρομολόγησης multi-cost με cost vectors πολλών παραμέτρων. Με βάση αυτά τα cost vectors ένα σύνολο από candidate paths θα υπολογιστούν για κάθε ζευγάρι κόμβων source-destination και μια συνάρτηση βελτιστοποίησης χρησιμοποιείται για να επιλεχθεί το βέλτιστο από αυτά. Οι παράμετροι που μας ενδιαφέρουν είναι ο αριθμός των hops σε ένα μονοπάτι, η υπολειπόμενη ενέργεια και η ισχύς μετάδοσης των κόμβων σε ένα μονοπάτι καθώς και η παρεμβολή που δημιουργείται από την μετάδοση ενός κόμβου. Αυτές οι παράμετροι συνδυάζονται σε ποικίλες συναρτήσεις βελτιστοποίησης οι οποίες αντιστοιχούν σε διαφορετικούς αλγόριθμους δρομολόγησης και οι οποίοι εξετάζονται για την επιλογή του βέλτιστου μονοπατιού. Λαμβάνοντας υπόψη όλες αυτές τις συναρτήσεις εξετάζουμε την συμπεριφορά του δικτύου προσέχοντας την κατανάλωση ενέργειας, το throughput κα. Από τα πειράματα καταλήγουμε στις βέλτιστες από τις συναρτήσεις βελτιστοποίησης. / In this work we study the combination of multi-cost routing and variable transmission power in wireless ad hoc networks. We assume that the nodes have power control capabilities and can adjust their transmission power to their desired level. We propose algorithms for selecting the routes to be followed by the packets and the transmission power to be used by the nodes at each hop in order to reduce interference and energy consumption, and improve network performance. The cost parameters used by the proposed interference/energy-aware routing algorithms are the number of hops of the paths, the interference caused to other nodes, the node residual energies, and the node transmission powers. In the experiments conducted we examine the resulting network performance with respect to energy consumption, packet delay, frequency of collisions, and other parameters of interest. Our results show that the proposed routing algorithms significantly improve network performance and lifetime.

Η οπτική μεταγωγή καταιγισμών (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.