Χρονοδρομολόγηση εργασιών σε κατανεμημένα συστήματα - εκτίμηση της απόδοσης

Abstract

In the field of modern distributed systems, where a lot of applications run at the same time, the accurate resource management technique that ensures end to end Quality of Service (QoS) is perhaps one of the most important issues for the end user. New applications are continuously being born, particularly applied for pervasive environments that enable high rates connectivity between mobile devices and at the same time claiming end to end reliability and integrity. Moreover, the software that is intended for pervasive services in ubiquitous computing environment requires a new design form of distributed network-centric applications. Taking all these issues into account the creation of efficient strategies becomes imperative need for the localised monitoring of mobile users characteristics. These characteristics are in terms of energy conservation and energy consumption of nodes, synchronization, scheduling and co-scheduling of all internal communicational processes. Such problems can be faced using significances that imitate behaviours of biological entities, or mimic the characteristics and behaviours of these entities. These entities co-operate to iteratively construct potential observation schedules. By combining cognitive science and anticipatory systems of biological intelligence via artificial biological entities and behaviours, these techniques can be applied to distributed systems offering significant throughput optimization. In this research, several case studies have been used to experimentally assess the performance of the proposed approaches in terms of quality solutions and computational effort. A variety of disciplines have recently advocated the use of self-adaptive and auto-configuration methods, including biodynamics, cybernetics and computer modelling. Of these methods, one which exhibits numerous powerful features that are desirable in communication systems is adaptive swarm based intelligence. Swarm-based self-configuration does not require the need of external help, supervision or control. An approach is modeled and presented called bandwidth clustering scheme suited for network resource allocation problem. Bandwidth clustering is used in a swarm-based active network environment where active packets continuously communicate with active nodes by using the Split Agent Routing Technique (SART). This mechanism enables the adaptation of the system to new conditions (bandwidth reservation/capacity allocation), as well as the passing of additional information to neighbouring nodes for which the information is held in transmitted packets. The performance, reliability and adaptivity degree of the proposed scheme is thoroughly examined through simulation, for different traffic measures, as well as the corresponding QoS offered (in terms of the end-to-end delay, available bandwidth and probability of packet loss). An approach for the stabilisation of reliability in mobile environment is also presented, in terms of communication maintenance and efficient utilization of battery power. Unlike wired networks in mobile networks, mobility induces frequent route changes. Energy conservation is an important issue that has to be taken into account for mobile devices. Traffic plays a major role for energy consumption because of its unpredictable incoming flow nature. This part of work proposes an adaptive traffic-based control method for energy conservation, which bounds an asynchronous operation where each node evaluates dissimilar sleep­wake schedules/states based on each node’s incoming sleep-history traffic. Simulation study is carried out for throughput, traffic characterization against performance and energy conservation evaluation of the proposed model taking into account a number of metrics and estimation of the effects of incrementing the sleep time duration to conserve energy. The proposed method could be applied to infrastructureless networks with any underlying routing protocol to provide independency, portability, as well as “fair” collaboration among energy conservation mechanism and routing protocol. Due to the spread of different file sharing platforms, peer-to-peer applications have become highly popular in today's pervasive environments. These applications could host multimedia on-demand applications in a fully distributed dynamically changing topology environment. In such a multiclient environment, the asymmetry in communication causes a degradation of reliability. A novel mimicking approach is proposed based on the advantages of epidemic selective resource placement through mobile Infostations. Epidemic placement policy combines the strengths of both proactive multicast group establishment and hybrid Infostation concept. With epidemic selective placement we face the flooding problem locally (in geographic region/landscape) and enable end to end reliability by forwarding requested packets to epidemically ‘selected’ mobile users in the network on a recursive basis. The sharing policy is based on a mathematical model of Markov chain rules. Markov chain model was chosen to evaluate extra storage requirements, for modelling of infectious diseases to determine the file sharing termination criteria. The selection of users is performed based on their remaining capacity, weakness of their signal and other mobility limitation characteristics. Experimental examination through simulation is performed for the response and reliability offered by epidemic placement policy which reveals the robustness and reliability in file sharing among mobile peers.

Στα σύγχρονα κατανεμημένα συστήματα, όπου πολλές εφαρμογές τρέχουν παράλληλα, η διαχείριση των πόρων (resource) που διασφαλίζει την από άκρο-σε-άκρο (end-to-end) ποιότητα υπηρεσίας (QoS-Quality of Service) είναι ίσως από τα σημαντικότερα ζητήματα για τον τελικό χρήστη. Νέες εφαρμογές γεννιούνται ολοένα και περισσότερο σε διεισδυτικά περιβάλλοντα (pervasive environments) που απαιτούν τον συνδυασμό ολοκληρωμένων υπηρεσιών σε μια συσκευή, και υποστηρίζουν ένα τεράστιο πληθυσμό χρηστών. Επιπλέον, το λογισμικό που προορίζεται για κινητές υπηρεσίες σε κινητές συσκευές, δηλαδή ο κώδικας ή τα δεδομένα που διακινούνται μεταξύ δικτυακών τοποθεσιών, προβάλλεται σαν μια νέα μορφή δημιουργίας κατανεμημένων δίκτυο-κεντρικών εφαρμογών. Με βάση τα ζητήματα αυτά, γίνεται επιτακτική ανάγκη η δημιουργία αποδοτικών στρατηγικών για τον εντοπισμό χαρακτηριστικών κινούμενων χρηστών, σε επίπεδο εναπομένουσας ενέργειας των κόμβων, συγχρονισμού και χρονοδρομολόγησης όπως και αναγνώρισης της τρέχουσας θέσης τους. Είναι πλέον παραδεκτό, ότι τέτοια προβλήματα μπορούν να αντιμετωπιστούν χρησιμοποιώντας έννοιες που μιμούνται συμπεριφορές οντοτήτων, ή χρησιμοποιούν χαρακτηριστικά των συμπεριφορών των οντοτήτων αυτών όπως και των βιολογικών τους συμπεριφορών και εκκρίσεων. Αυτές οι τεχνικές μπορούν να προσφέρουν βελτιστοποίηση στις παραμέτρους και στις συμπεριφορές των πολύπλοκων προβλημάτων κατανεμημένων συστημάτων. Ο συνδυασμός του τομέα της υπολογιστικής βιολογικής νοημοσύνης μέσω τεχνητών βιολογικών οντοτήτων και του τομέα των κατανεμημένων συστημάτων επικοινωνιών έχει πολλά να προσφέρει στην τεχνολογία των δικτυακών μοντέλων σε επίπεδο ταχύτητας και απόδοσης. Η παρούσα διδακτορική διατριβή παρουσιάζει την μοντελοποίηση και την εφαρμογή των θεωρητικών προσεγγίσεων για θέματα βελτιστοποίησης της ταχύτητας μετάδοσης της πληροφορίας, αλλά και της μελέτης και εκτίμησης της ρυθμαπόδοσης σε σύγχρονα κατανεμημένα συστήματα. Εξετάζει την προσαρμοστική συμπεριφορά πρακτόρων και την συνεισφορά τους στην βελτιστοποίηση της ρυθμαπόδοσης σε δίκτυα συγκεκριμένης τοπολογίας για μια ορισμένη κυκλοφορία δεδομένων. Οι αλγόριθμοι χρονοδρομολόγησης είναι υπεύθυνοι να δρομολογούν τα πακέτα πληροφοριών σε μια συγκεκριμένη χρονοθυρίδα (time slot). Ο τρόπος προώθησης του κάθε πακέτου και η χρονική καθυστέρηση αυτού, έχει άμεσο αντίκτυπο στις παραμέτρους που κρίνουν ένα δίκτυο αν είναι αποδοτικό και αν παρέχει QoS στον τελικό χρήστη. Σε ιδανικές περιπτώσεις το δίκτυο θα πρέπει να επιλέγει τις διαδρομές έτσι ώστε να ελαχιστοποιείται ο χρόνος που καταναλώνουν τα πακέτα πληροφορίας στο δίκτυο. Σε αυτή την διατριβή προτείνεται και παρουσιάζεται η έννοια της SART τεχνικής δρομολόγησης (Split Agent-based Routing Technique- μέθοδος Διαμοιραζόμενων Πρακτόρων Προσαρμογής) που αποτελεί μια παραλλαγή της swarm based routing δρομολόγησης. Τα ευαίσθητα στην καθυστέρηση πακέτα παίρνουν προτεραιότητα από τις κινητές λογισμικές μονάδες πρακτόρων, και επηρεάζουν τους πίνακες δρομολόγησης ενημερώνοντάς τους για τις προτεραιότητες αυτές. Επίσης χρησιμοποιείται η έννοια της ενθυλάκωσης των πρακτόρων στα πακέτα πληροφορίας (τ.β.ο-Π). Στο προτεινόμενο σχήμα δεν χρησιμοποιούνται εξειδικευμένα πακέτα ελέγχου όπως σε άλλα σχήματα δρομολόγησης δεδομένου ότι οι κινητές λογισμικές μονάδες πρακτόρων εκτελούν τον έλεγχο. Η τεχνική δρομολόγησης SART προσφέρει έναν αποκεντρωμένο έλεγχο για χρονοδρομολόγηση πληροφορίας στο δίκτυο και έναν αποδοτικό τρόπο για να αυξηθεί ο γενικός έλεγχος των πακέτων, προσφέροντας αύξηση στη ρυθμαπόδοση του συστήματός μας, αλλά και δίκαιη κατανομή των διαθέσιμων πόρων.