Approximation algorithms for packet routing in networks with reconfiguration cost

The problem tackled throughout this thesis is referred to and encountered in various forms in international bibliography and has many applications as far as Optical Networks, TDMA (Time Division Multiple Access) and parallel message or data transmission are concerned. For the purposes of this manuscript the graph theoretic model of the problem is used. Researchers are referring to the problem at hand as PREEMPTIVE BIPARTITE SCHEDULING (PBS). In its various forms it has been studied extensively by many researchers and scholars. It is described as follows:Given a set of transmission stations (a set of vertices V, |V|=n), a set of receivers U (a set of vertices U, |U|=m) and a set of messages to be transmitted from V to U (a set of edges E), we are required to produce an efficient schedule such that the total time duration from beginning of the first transmission to the conclusion of the last will be minimized. Each of the messages to be transmitted has some specific duration (edges weight: w). To achieve our goal we are allowed to interrupt (preempt) message packages. Unfortunately, preemption comes with a cost (delay=d) in order to reconfigure the system and/or prepare for the next transmission. Each time we decide to preempt, a reconfiguration delay add to the total transmission time. Therefor in order to produce an optimal schedule one has to take into account two different parameters simultaneously.Previous research resulted mainly in designing 2-approximation algorithms (100% deviation from the cost of the optimal solution).Briefly, the contributions of this thesis to tackling PBS are the following:1.Polynomial time algorithms to provide an optimal solution in the following cases:-In the case of unvarying graphs -In case we wish to minimize the number of preemptions-In case we need to minimize only the transmission time (d=0).To design the two later we prove that any PBS input might be transformed to an Open Shop input and vice versa.2.The best so far polynomial time approximation algorithm with guaranteed approximation ratio less than two. In fact, we designed a family of algorithms which we named A-PBS(a). Among those algorithms A-PBS(d+1) (a=d+1) stands out, as it produces the lowest approximation ratio. Proof of the algorithm’s approximation ratio as well as tightness were done using derivative methods to identify a minimum value. The approximation ratio of A-PBS(d+1) is 2-1/(d+1), resulting in down to just 50% deviation from eth optimal in the case of d=1. The same algorithm for d=0 will yield an optimal schedule for PBS.3.Fast heuristic algorithms to mitigate disadvantages and make improvements on preexisting research.4.Design not only of the fastest but also the best in terms of deviation from the cost of the optimal solution algorithm. Efficiency of this algorithm has been tested through experiments against the most efficient algorithms proposed for PBS by other researchers in the past.5.A combination of all previous results and methodologies to produce a final hybrid algorithm, the efficiency of which we tested not only for the usual uniform distribution data but also in cases the data may follow a normal or an exponential distribution.All of the above were studied in terms of computational complexity as well and were tested through experiments to verify how well they perform in practice.Το πρόβλημα που μελετάται στην παρούσα εργασία αναφέρεται σε διάφορες μορφές στη βιβλιογραφία και έχει εφαρμογές τόσο στα οπτικά δίκτυα και συστήματα TDMA (Time Division Multiple Access), όσο και στην παράλληλη μετάδοση μηνυμάτων αλλά και σε ποικίλα άλλα δίκτυα επικοινωνίας. Για το σκοπό της έρευνάς μας υιοθετήσαμε τον ορισμό που αφορά γράφους και με τον ορισμό αυτό το πρόβλημα αναφέρεται στη βιβλιογραφία ως PREEMPTIVE BIPARTITE SCHEDULING (PBS). Στις διάφορες μορφές του έχει μελετηθεί κατά καιρούς από πολλούς ερευνητές και έχει αποδειχθεί ότι ανήκει στην κατηγορία των NP-Hard προβλημάτων ακόμα και για πολύ απλές μορφές δεδομένων εισόδου. Ένας τρόπος να περιγραφεί το πρόβλημα είναι ο ακόλουθος:Δεδομένου ενός συνόλου σταθμών εκπομπής μηνυμάτων (ένα σύνολο κόμβων V με n στοιχεία), ενός συνόλου δεκτών (ένα σύνολο κόμβων U με m στοιχεία) και ενός συνόλου μηνυμάτων που πρέπει να μεταδοθούν από το U στο V (το σύνολο ακμών Ε), καθένα από τα οποία έχει μία συγκεκριμένη διάρκεια (ακμές με βάρη), ζητείται αποδοτικό χρονοπρόγραμμα ώστε η συνολική διάρκεια από τη στιγμή εκκίνησης της πρώτης εκπομπής μέχρι την ολοκλήρωση της τελευταίας να είναι η ελάχιστη δυνατή. Κατά την επίλυση του προβλήματος έχουμε τη δυνατότητα να διακόπτουμε εκπομπές και να συνεχίζουμε τη μετάδοσή τους σε κάποια άλλη χρονική στιγμή, όμως ο χρόνος που θα χρειαστεί σε μία τέτοια περίπτωση το σύστημα για να επανέλθει σε κατάσταση κατάλληλη για την αναμετάδοση νέων δεδομένων δεν είναι μηδενικός και έτσι κάθε φορά που πρέπει ή που εμείς αποφασίζουμε να διακόψουμε μία εκπομπή, επιβαρύνεται ο συνολικός χρόνος μετάδοσης. Έτσι για την εύρεση βέλτιστου χρονοπρογράμματος απαιτείται να λάβει κανείς υπόψη του δύο παραμέτρους: τον συνολικό χρόνο εκπομπών και τον αριθμό των διακοπών.Προηγούμενη έρευνα είχε ως αποτέλεσμα το σχεδιασμό αλγορίθμων για την εύρεση λύσης η οποία να μην είναι χειρότερη από το διπλάσιο της βέλτιστης (ή σφάλμα 100%). Συνοπτικά οι κύριες συνεισφορές της διατριβής είναι: 1. Αλγόριθμοι πολυωνυμικού χρόνου που υπολογίζουν βέλτιστη λύση στις εξής περιπτώσεις: - Επιλύουν το πρόβλημα παράγοντας βέλτιστο χρονοπρόγραμμα στην περίπτωση που τα δεδομένα είναι ειδικής μορφής (μονότονοι γράφοι), - Εξασφαλίζουν το ελάχιστο πλήθος διακοπών και υπό την προϋπόθεση αυτή προσεγγίζεται ένα κάτω φράγμα για τον χρόνο εκπομπής , και τέλος- Ελαχιστοποιούν τον χρόνο εκπομπής και υπό την προϋπόθεση αυτή ελαχιστοποιούν τον αριθμό διακοπών. Για τον σχεδιασμό των 2 τελευταίων αποδείχθηκε ότι κάθε στιγμιότυπο του PBS μπορεί να μετασχηματιστεί σε στιγμιότυπο open shop και αντίστροφα.2. Ο καλύτερος μέχρι στιγμής πολυωνυμικός αλγόριθμος με πηλίκο προσέγγισης γνήσια μικρότερο του 2 για όλες τις τιμές των παραμέτρων εισόδου. Στην πραγματικότητα πρόκειται για μια οικογένεια αλγορίθμων που ονομάστηκε A-PBS(a). Μεταξύ των αλγορίθμων αυτών ξεχωρίζει ο A-PBS(d+1). Για τιμή την εύρεση της ιδανικής τιμής της παραμέτρου a=d+1 εισαγάγαμε πρωτοποριακή μέθοδο απόδειξης για τα δεδομένα της Θεωρητικής Πληροφορικής μέσω παραγώγων. Με τη μέθοδο αυτή αποδείχθηκε τόσο η τιμή του πηλίκου προσέγγισης όσο και η ανελαστικότητα (tightness) του A-PBS(d+1).Το πηλίκο προσέγγισης που αποδείχθηκε για τον A-PBS(d+1) είναι 2-1/(d+1) και επομένως, ανάλογα με τα δεδομένα μπορεί να έχει εγγυημένη απόδοση με μόλις 50% απόκλιση από τη βέλτιστη λύση για d=1. Έτσι επιτυγχάνεται βελτίωση έως και 50% σε σχέση με τον καλύτερο από προγενέστερους αλγορίθμους που επιχειρούν να λύσουν το πρόβλημα. Για d=0 ο ίδιος αλγόριθμος υπολογίζει βέλτιστη λύση τόσο του προβλήματος PBS όσο και του προβλήματος Preemptive Open Shop σε χρόνο πολυωνυμικό.3. Γρήγοροι ευριστικοί αλγόριθμοι που αντιμετωπίζουν τα μειονεκτήματα και βελτιώνουν τους καλύτερους αλγορίθμους που προτάθηκαν από άλλους ερευνητές στο παρελθόν. 4. Σχεδιασμός του καλύτερου μέχρι στιγμής αλγορίθμου όχι μόνο ως προς την ταχύτητα αλλά ταυτόχρονα και ως προς την προσέγγιση της βέλτιστης λύσης του οποίου η αποδοτικότητα αποδείχθηκε μέσω πειραμάτων σε σύγκριση με τους καλύτερους αλγορίθμους που έχουν προταθεί από άλλους ερευνητές.5. Συνδυασμός αποτελεσμάτων και σύνθεση μεθοδολογιών όλων των προηγούμενων αλγορίθμων σε έναν νέο (υβριδικό), τελικό αλγόριθμο που σε πειράματα με διάφορα δεδομένα εισόδου αποδίδει λύση με ελάχιστη απόκλιση από τη βέλτιστη. Οι επιδόσεις του αλγορίθμου αυτού έχουν επιβεβαιωθεί και σε περιπτώσεις που τα δεδομένα εισόδου ακολουθούν όχι μόνο τη συνήθη ομοιόμορφη κατανομή αλλά και άλλες κατανομές που συναντώνται συχνά σε δεδομένα εισόδου όπως κανονική και εκθετική.Για όλα τα ανωτέρω έγινε μελέτη πολυπλοκότητας καθώς και υλοποίηση με κώδικα για την επιβεβαίωση της αποδοτικότητας που προέκυψε από τη θεωρητική τους μελέτη