QoS-based web service description and discovery

Abstract

The success of the /Web Service/ (WS) paradigm has led to a proliferation of available WSs. As these WSs are advertised in registries, they have to be discovered based on user needs. However, these registries rely on the current WS technology stack that uses /WSDL/ and /UDDI/ for WS description and discovery. Unfortunately, these two languages rely on syntactic descriptions of WS functional and non-functional attributes. This situation creates two problems. Firstly, syntactic discovery efforts return inaccurate results. Secondly, no means are provided in order to select among multiple WSs that perform the same function. The first problem has been solved by combining /Semantic Web/ (SW) and WS technologies. The second problem can be solved by taking into account a big subset of all non-functional properties of WSs, which is called /Quality of Service/ (QoS). QoS is closely related with the performance of a WS so it has a substantial impact on user's expectations from a WS and can be used as a discriminating factor between functionally equivalent WS advertisements. Thus WS descriptions must be enhanced with QoS descriptions. Additionally, WS discovery algorithms should perform QoS-based /filtering/ (matchmaking) and /ranking/ (selection) on WS advertisements in order to produce fewer ranked results. A /QoS offer/ (or /demand/) of a WS is a set of constraints on some QoS attributes. Actually, the current modeling efforts of QoS specifications only differ in the expressiveness of these constraints. However, when it comes to QoS attributes modeling, these efforts fail. The main reason is that they use a poor, syntactic and inextensible QoS attributes model. Based on the above problem, the first part of this thesis is dedicated to conducting a research on all QoS-based WS description efforts in order to unveil those features that are necessary for a QoS description model of WSs. The result is a set of requirements for a rich, semantic and extensible QoS-based WS description model. Based on these requirements, an ontology language called /OWL-Q/ has been carefully created by extending OWL-S. One disadvantage of using ontologies is the creation of different descriptions of the same concept. Concerning the QoS domain, this can be true for QoS metrics. We argue that the state-of-the-art ontology alignment algorithms cannot be used in this case because of the use of mathematics for deriving complex QoS metrics from simpler ones. For this reason, we have devised a twofold solution to this problem: a) a semantic QoS metric matching algorithm and b) based on this algorithm, an alignment algorithm for aligning OWL-Q descriptions of WS providers and requesters. There are two main approaches for QoS-based WS matchmaking: ontology-based and /Constraint Programming/ (CP)-based but both of them present some major drawbacks. In this thesis, we argue that the CP-based approach is better but has to be enhanced in many ways. The first enhancement is the use of an appropriate solving technique depending on the type of constraints present in QoS-based WS specifications. The second enhancement is the use of correct matchmaking metrics. Another enhancement is the use of optimization techniques especially for over-constrained demands. All implemented matchmaking algorithms were evaluated based on a testing framework producing random QoS-based WS descriptions. A final contribution of this thesis was a QoS-based WS selection algorithm overcoming the disadvantages of all other research approaches. Thus, as can be seen from the totality of the above contributions, a semantic framework for QoS-based WS description and discovery was produced in terms of this thesis.

Η επιτυχία του παραδείγματος των Διαδικτυακών Υπηρεσιών (ΔΥ) έχει οδηγήσει σε πολλαπλασιασμό των διαθέσιμων ΔΥ. Καθώς αυτές οι ΔΥ δημοσιοποιούνται σε αποθήκες, πρέπει να ανακαλυφθούν με βάση τις ανάγκες των χρηστών. Όμως, αυτές οι αποθήκες βασίζονται στη τρέχουσα στοίβα τεχνολογίας ΔΥ, η οποία χρησιμοποιεί τις γλώσσες /WSDL/ και /UDDI/ για την περιγραφή και ανακάλυψη ΔΥ. Δυστυχώς, αυτές οι δύο γλώσσες βασίζονται στη συντακτική περιγραφή λειτουργικών και μη ιδιοτήτων των ΔΥ. Αυτή η κατάσταση δημιουργεί δύο προβλήματα. Πρώτον, οι βασιζόμενες σε συντακτικά μοντέλα ερευνητικές προσπάθειες επιστρέφουν μη ακριβή αποτελέσματα κατά την ανακάλυψη ΔΥ. Δεύτερον, δεν υπάρχει μέσο επιλογής της καλύτερης ανάμεσα σε πολλαπλές ΔΥ που προσφέρουν την ίδια λειτουργικότητα. Το πρώτο πρόβλημα έχει λυθεί με το συνδυασμό τεχνολογιών /Σημασιολογικού Δικτύου/ (ΣΔ) (Semantic Web) και ΔΥ. Το δεύτερο πρόβλημα μπορεί να λυθεί λογαριάζοντας ένα μεγάλο υποσύνολο μη λειτουργικών ιδιοτήτων των ΔΥ που ονομάζεται /Ποιότητα Υπηρεσίας/ (ΠΥ) (Quality of Service). Η ΠΥ έχει στενή σχέση με την απόδοση των ΔΥ. Επομένως, η ΠΥ έχει ουσιώδη αντίκτυπο στις προσδοκίες των χρηστών από μια ΔΥ και μπορεί να χρησιμοποιηθεί ως παράγοντας διαχωρισμού ανάμεσα σε λειτουργικά ισοδύναμες περιγραφές ΔΥ. Συνεπώς, οι περιγραφές ΔΥ πρέπει να εμπλουτιστούν με περιγραφές ΠΥ. Επιπροσθέτως, οι αλγόριθμοι ανακάλυψης ΔΥ πρέπει να επιτελούν φιλτράρισμα και ταξινόμηση των ΔΥ με βάση την ΠΥ ώστε να παράγουν λιγότερα και ταξινομημένα αποτελέσματα. Μια προσφορά ή ζήτηση ΠΥ μιας ΔΥ είναι ένα σύνολο από περιορισμούς σε ορισμένες ιδιότητες ΠΥ. Στην πραγματικότητα, οι τρέχουσες προσπάθειες μοντελοποίησης των προσδιορισμών ΠΥ διαφέρουν μόνο στην εκφραστικότητα των εν λόγω περιορισμών. Όμως, όσον αφορά των μοντελοποίηση των ιδιοτήτων ΠΥ, οι τρέχουσες ερευνητικές προσπάθειες αποτυγχάνουν διότι χρησιμοποιούν ένα φτωχό, συντακτικό και στατικό μοντέλο ιδιοτήτων ΠΥ. Με βάση το παραπάνω πρόβλημα, το πρώτο μέρος αυτής της διατριβής πραγματεύεται την διεξαγωγή έρευνας σε όλες τις βασιζόμενες σε ΠΥ προσπάθειες περιγραφής ΔΥ ώστε να αποκαλύψει εκείνα τα χαρακτηριστικά που είναι απαραίτητα για ένα μοντέλο περιγραφής ΔΥ βασιζόμενο σε ΠΥ. Το αποτέλεσμα είναι ένα σύνολο από απαιτήσεις για πλούσιες, σημασιολογικές και επεκτάσιμες περιγραφές ΠΥ για ΔΥ. Με βάση τις παραπάνω απαιτήσεις, μια γλώσσα οντολογίας με όνομα ΟWL-Q δημιουργήθηκε επεκτείνοντας την γλώσσα OWL-S. Ένα σημαντικό μειονέκτημα της χρήσης οντολογιών είναι η δημιουργία διαφορετικών περιγραφών για μια οντότητα. Όσον αφορά το πεδίο γνώσης της ΠΥ, αυτό μπορεί να συμβαίνει για τις μετρικές ΠΥ. Υποστηρίζουμε ότι οι τελευταίας τεχνολογίας αλγόριθμοι ευθυγράμμισης οντολογιών δεν μπορούν να χρησιμοποιηθούν στην προκειμένη περίπτωση λόγω της χρήσης των μαθηματικών στην παραγωγή πολύπλοκων μετρικών ΠΥ από πιο απλές μετρικές. Για αυτό τον λόγο, έχουμε επινοήσει μια διπλή λύση σε αυτό το πρόβλημα: α) ένα σημασιολογικό αλγόριθμο ταιριάγματος μετρικών ΠΥ, β) με βάση αυτόν τον αλγόριθμο, ένα αλγόριθμο ευθυγράμμισης των OWL-Q περιγραφών. Υπάρχουν δύο κύριες προσεγγίσεις για το ταίριαγμα ΔΥ με βάση την ΠΥ: οντολογικές και βασισμένες στον Προγραμματισμό με Περιορισμούς (ΠΠ) (Constraint Programming) που όμως παρουσιάζουν σημαντικά μειονεκτήματα. Σε αυτή τη διατριβή υποστηρίζουμε ότι η δεύτερη προσέγγιση είναι καλύτερη αλλά πρέπει να επεκταθεί σε πολλές κατευθύνσεις. Η πρώτη επέκταση είναι η χρήση κατάλληλης μεθόδου επίλυσης περιορισμών ανάλογα με το είδος των περιορισμών που περιέχονται στις περιγραφές ΠΥ. Η δεύτερη επέκταση είναι η χρήση σωστών μετρικών ταιριάγματος. Μια άλλη επέκταση είναι η χρήση τεχνικών βελτιστοποίησης ειδικά για την περίπτωση υπερ-περιορισμένων αιτημάτων χρηστών. Όλοι οι αλγόριθμοι ταιριάγματος αποτιμήθηκαν εμπειρικά με τη χρήση ενός πλαισίου πειραμάτων το οποίο παρήγαγε τυχαίες περιγραφές ΠΥ για ΔΥ. Μια τελευταία συνεισφορά αυτής της διατριβής είναι ένα αλγόριθμος επιλογής ΔΥ βασισμένος σε ΠΥ, ο οποίος επιλύει όλα τα προβλήματα που παρουσιάζουν οι άλλες ερευνητικές προσεγγίσεις. Συνεπώς, όπως μπορεί να φανεί από το σύνολο των συνεισφορών, ένα σημασιολογικό πλαίσιο για την περιγραφή και ανακάλυψη ΔΥ με βάση την ΠΥ αναπτύχθηκε στα πλαίσια της εν λόγω διατριβής.