Review: Ontologies: Giving Semantics to Network Management Models

Cet article expose la même problématique concernant l'hétérogénéité des data model et l'insuffisance de la translation syntaxique d'un data model à un autre.

Pour commencer il expose l'intérêt d'ajouter de la sémantique tout en passant par les ontologies. Le papier continue par présenter les data model/les Information Model (GDMO, SMI, MIF, IDL, SMIng et CIM). Ensuite, l'auteur continue par une comparaison qui va permettre de savoir si on peux passer d'un modèle de données à un autre facilement. ça sera le cas si les deux data model supportent les même critères (d'ontologie).

Le modèle de donnée CIM (Common Information Model) est le candidat qui répond le mieux aux critères de comparaison (Inspirés par [1] et [2]), du point de vue Meta classes, Partitions, Attributs, Facets, Taxonomies, Relations et Comportement (Axiom et roles). En plus, CIM est le langage qui a le plus d'expressivité sémantique parmi les autres. Mais CIM a besoin des extensions.

Afin d'intégrer les ontologies aux modèles de données, les auteurs proposent deux approches:

1. Effectuer un mapping entre chaque deux modèle de données.
   
2. Définir un modèle de donnée (final ou pivot) qui inclut les autres modèles de données existants.

La seconde approche parait la plus adaptée dans le cas où le nombre des modèles de données est élevé.
Ils proposent de modifier la seconde approche car les sous-ensemble communs entre les modèles de données n'ont pas tous le même poids.
Donc ils prendront le modèle de données le plus grand, celui qui couvre le mieux le domaine d'administration. Ensuite, appliquer une extension avec les petites parties qu'il ne supportent pas afin de définir un modèle de données final.

Ce modèle de données final ou l'ontologie globale est CIM dont on va ajouter les extensions afin qu'il couvre d'autres aspects comme les axiomes et le comportement, contraintes etc. Le but est de pouvoir exprimer des contraintes comme par exemple: "L'espace libre d'une instance CIM_FileSystem doit être plus grande de 10% que la taille d'un sytème de fichier."


Conclusions:
CIM est un modèle de donnée avec une expressivité sémantique plus avancée que les autres modèles de données (GDMO, SMI, MIF, IDL, SMIng). Cependant, il lui manque la définition des taxonomies (subclass of, Not subclass of, composition disjointe (entre deux concepts), etc) et les relations afin de pouvoir exprimer des contraintes.
Lors du mapping entre les modèle de données, on peut utiliser les outils des ontologies déjà existants. D'après les auteurs, cette solution nécessite une intervention manuelle pour valider certaines taches, ce qui peut prendre un temps non négligeable lors de son application à des larges modèles de données.
Mais cette solution reste mieux adaptée que de faire le mapping à la main.

Références:
1 - A roadmap to ontology specification languages, Corcho et al., EKAW'2000.
2 - Ontology based integration of information - a survey on exisiting approaches, Wache et al, IJCAI 2001

Review: SENS - a Scalable and Expressive Naming System using CAN Routing Algorithm

This paper proposes a Scalable and Expressive Naming System (SENS) based on CAN routing algorithm. SENS is a descriptive naming scheme that uses a tuple of attribute/value pairs to name each resource. A resource such a computer is named as ( String OS= "Linux", string CPU-name = "Pentium 4", etc). Those informations are stored at a large number of name servers (NS).

Their design claims to achieve scalable and efficient resource information distribution and retrieval. SENS handles exact (MEMORY = 512 MB) and multi-attribute range queries (MEMORY > 512 MB) with small overhead as well as load balancing.

DESIGN OF SENS:
Mapping resource names to resource IDs:
A resource ID is considered as a set of d coordinates of a point in the d-dimensional resource ID space. (In the example below d = 6). A resource name is mapped to a resource ID by assigning the hash value of each attribute/value (a/v) pairs of the resource name to a coordinate value of the resource ID. Name servers are responsible for resource ID sets just like in the CAN system.
Ha is a function that uniformly hashes every attribute from 1 to d and Hv hashes every attribute value in a [1, 2^(m-1)] interval where m is the maximum size of coordinate value in bits.












If multiple attributes in a resource name are hashed to the same value Ha (attr i) = Ha (attr j) then the corresponding attribute values will be mapped to multiple coordinate values in the same dimension. This means that resource names are mapped to multiple resource IDs which are distributed on NSs.


Their mapping scheme is not injective, several resource names can be mapped to the same resource ID. Consequently resource ID is not a unique identifier of resource name, in order to identify a resource, the resource_ID (resulting form Hash) and its name are required to uniquely identify a resource.

In the case of numerical attribute values, a locality preserving hashing function is used. Such hashing function is defined as if (val1 > val2) then (Hval1 > Hval2). the main purpose behind using a locality preserving hashing function is to deal with range queries, in fact it ensures that a resource ID will be in a interval of resource IDs between a min and max value. By doing this they limit the number of NSs responsible for a query range.

If the attribute/value pairs number is lower than d then the resource ID is filled with zeros.
However when the attribute/value pairs number is higher than d then the set of attributes should be divided to multiple sets of attributes which corresponds to multiple resource names. (this aspect of fragmentation is not treated in this paper).

Resource Information Distribution:
Since their scheme is CAN based, zones are assigned to NS, consequently each NS manages resource information according to the resource ID.
In the case of a resource name mapping to multiple resource IDs. If the NS is responsible for several resource IDs of the same resource, only one copy in maintained at the NS. When resource IDs belongs to different zones i.e. different NS, they use a multicast routing algorithm based on Spanning Binomial Trees. Their algorithm sends minimum amount of messages to deliver information to a NS.
Resource IDs corresponding to a resource name construct a hypercube in the resource ID space according to this article (Optimum Broadcasting and Personalized Communication in the Hypercube) . (They don't explain how the hypercube is built, so further reviews will detail the construction algorithm of hypercubes).


The registration message containing information of the resource is first delivered to the NS responsible for the resource ID created from the lowest values of each resource IDs coordinates. (In this example root node is (0.0.0)). This NS becomes the root node and forwards the message to its descendants according to the tree. Those descendants also will forward the registration message to their descendants according to the tree. etc

Query resolution:
SENS supports:

• Exact queries: A query host sends a message to a NS which will map the query resource name to resource IDs and select the nearest destination resource ID. The message arrives to destination using the CAN routing algorithm. The NS responsible for the resource ID will lookup its database to find the queried information and send it back to the initial NS (the one first queried by the host).

• Range queries, in the case of a range query it will be limited by the hash values of the upper and lower limit of the queried value ranges in each dimension. When a host sends a range query message to a NS, the latter will map the query range to a range query segment in the resource ID space. A query message will be broadcasted to all NSs whose zones overlap the segment. They propose a broadcasting algorithm based on the SBT and hypercube in order to reduce the number of messages broadcasted. (Further details will be added once I read the article that treats the hypercube and SBT formation).

Related works:
This article propose a more expressive naming scheme than DNS which offers a value-limited resource name space without the possibility to realize the range query.
Other systems such as the Intentional naming system uses a descriptive name space based also on attribute/value pairs. The message routing for a name query is realized by look up of the query name on forwarding tables. Main limitation of such systems is scalability since the forwarding tables will grow with the number of resource names.
DHT-based routing protocols like Chord, CAN achieve a scalable and efficient lookup by hashing a resource name to a DHT key. Range query is the limitation of such systems, a query may spread to the hole DHT key space.
Other systems proposes range queries like MAAN where nodes are responsible for attribute values of an attribute in the query range. The node responsible for the attribute/value pairs (String OS = "Linux") must keeps information related to Linux OS. The main limitation is load balancing since popular attribute/value pairs may appear in resource names with high probability.

SENS is naming system capable of handling resource information with exact and multi-attribute range queries. They propose a multicast/broadcast algorithm to deliver/retrieve information.
However some issues remains unclear:
Several resource names might be mapped to same resource ID and the unique identification is done by resource ID and resource name. Is it enough to uniquely identify a resource? Is it possible to map 2 different resource names having same attribute values in common into the same resource ID? In 2005 Xiaoyun Wang and Hongbo Yu achieved collision on purpose in the MD5 hashing algorithm (2 different values were hashed to same ID).
Is SENS trying to merge between search engines and DNS-like systems?
Do we really need to merge between such systems? is it faster ? More reliable? More scalable ?
Is it a good approach when a resource is mapped to many resource IDs? Having multiple IDs will accelerate routing and finding the nearest ID? What if we mapped essential and important data to multiple IDs and restrained non important data to a single resource ID? How to design such a ranking system to classify data according to it's importance?
What if I updated my RAM from 512 MB to 1024 MB, how SENS manages such updates?
Is space partition efficient? when a node joins the system, a lot of information is handled to the new joining node ? Consequently huge messages are transmitted to the new node.

Link to the article

Review: The SATIN Component System—A Metamodel for Engineering Adaptable Mobile Systems

Readers might be wondering why is he writing about components now, well I am interested in the meta models. Such models can be useful when designing a naming and addressing system, the meta-data associated to each component will help to find a specific component.

This article suggests a component model in order to deal with mobile adaptation.
Applications are more often monolithic (one code block), which means hard to update and maintain when an event or change of context occurs.
Their model allows logical mobility defined as the migration of a partial or complete application or process from one host to another.

Component based development divide the system into interacting components with well defined interfaces. Traditional approaches do not support code migration and execution at runtime. They apply this mobility to components.

The SATIN component model allows to send and receive components dynamically at runtime. Instead of relying on the invocation of remote services, SATIN components are remotely cloned and instantiated locally.
This solution provides autonomy when networks are disconnected. Applications can introspect which components are available locally for a task, and dynamically change the system configuration by adding or removing components.

Component metadata is essential in order to best describe component's properties which are a set of its attributes (ID, version, dependencies with other components, hardware etc). The SATIN component system use attributes similar to the Debian packaging system. This allows applications running on heterogeneous hardware/framework to decide whether on not to deploy a component.
The central component of a SATIN system is the container component which acts as a registry, holds a reference to each component installed on the system. A registrar component is used for loading, removing components, managing dependencies etc.

They consider four aspects of Logical Mobility: components, classes, Instances and data types which is a bit stream. A Logical Mobility Entity (LME) is an abstract generalization of a class, instance or data types. Logical Mobility Unit (LMU) is an encapsulation of LMEs. LMU provides operations that permit inspection of the content, a handler class to deploy and manipulate it contents. Properties (set of attributes) of LMU are used to express dependencies, target environment etc. These LMUs and its contents are serialized/deserialized for transfer and deployment between physical hosts. LMU is always deployed in a reflective component which is able to adapt on runtime by receiving LMU from other hosts.
When a change in the context/environment appears (user/component triggered), the system asks the deployer for a component satisfying a set of attributes. The local deployer contacts a remote deployer and asks for a component. The container packs an LMU and sends it back to the host.
Component discovery and advertising is general. It can uses Jini, UPnP, etc.
In their implementation they used IP Multicast advertising group and a simple centralized publish/subscribe protocol.

So far my knowledge on mobile adaptively component systems is limited, comments on this topic will be added further.
However classic issues deserves to be explored such as:
How much time is needed to transfer a component in a mobile system?
Can we and how to guarantee such time in a dynamic and mobile system. Mobile nodes appears and disappears, the transfer of LMU will be interrupted due to node departure (this is MANET similar issues).
How to advertise for services and new nodes with a minimum overhead, message exchange between nodes?
How to manage resources allocated for every component in a limited resource environment/platforms?

Link to the article

Review: Toward a search architecture for software components

This paper proposes a design of a component search engine for Grid applications.
With the development of the component based programming model, applications are going to be more dynamically formed with the associations of components. Developers should be able to reuse already developed components that matches their needs. To do so, a component search engine seems to be essential.
The component search for Grid applications offers two facilities:

1. Developers will be able to find the best component for their need.
2. The framework can replace a malfunctioning or a slow component dynamically (at run time). The application should be able to decide the best component to be replaced with the malfunctioning.
   

They assume that open source Grid applications will appear and software components can be found on portals. These components will be ranked according to their usage, the more a component is used by applications the more important it is considered. This raking will establish a trust index. This approach is used by Google to rank the pages and improve search results.

One of the related works:
Agora components search engine supports the location and indexing of components and the search and retrieval of a component. Agora discovers automatically sites containing software components by crawling the web (Google's web crawler), when it finds a page containing an Applet tag, it downloads and indexes the related component. Agora supports JavaBeans and CORBA components. The database search is keyword based refined by users.

Workflows:
A workflow can be described as a process description of how tasks are done, by whom, in what order and how quickly.
Workflows are represented with low level languages such as BPEL4WS which requires too much user effort to describe a simple workflow.
Other high level language and Graphical User Interface on top of BPEL4WS are being introduced/build that generates BPEL code.

Their approach is workflow based: components can be adapted and coordinated through workflows. Applications should be able to choose and bind with other components from different sources on the Grid. Such applications searches first in its own local repository for components previously used or installed and uses a search engine to find suitable components.

The application development process can be divided into 3 stages:

1. Application Sketching is when developers specifies: (1) An abstract workflow plan containing the way information passes through the application's parts. (2) A place-holder describing the functions and operations to be carried out. This description will help finding a list of suited components.
2. Components discovering is based on 2 steps: First they resolve the place-holder query by searching in the local repository. If a suitable component is found locally than an identifier of this component is returned to the application. Second, If no component was found, a Query session is started on remote sites. A list of ranked components is returned and refined by user specifications.
3. Application assembling is the binding phase. Data or protocol conversion are often needed due to the heterogeneous input/output between components (string to array of double conversion etc).
   

GRIDLE is their component search engine: Google like Ranking, Indexing and Discovery service for a Link-based Eco-system of software components. The main modules are the following:

1. The Component Crawler is like a Web Crawler, it retrieves new components and updates links (bindings) between components and pass the results to the indexer.
   
2. The Indexer will build the index data structure of GRIDLE. Characteristics and meta data associated to the component should be carefully selected to be indexed. Actually the meta information associated to components will help retrieve the suited one. Such Meta data can be: (1) Functional information like interfaces (published methods, names, signatures) and runtime environment. (2) Non functional information such as QoS and textual description. (3) Linking information to other components.
   
3. The Query Analyzer resolves the queries on index basis, it uses a ranking module to retrieve the most relevant components, the search will be refined by the user.
   

To this stage, I don't have advanced knowledge in such systems and search engines but I find this approach interesting since the world of component development is emerging.
In the near future, thousands of components will be developed and ready to use. One of the main reasons of the wide adoption of the component based programming model is the ability to reuse already developed components and save time during the development process. A search engine seems to be necessary in order to find and locate suitable components.
Some issues in their approach remains unexplained or not clear such as:

• Components will be updated , deleted, added, so how to determine the crawler iteration frequency in order to update the indexing?
• The same question appears when dealing with Component binding, since the model is inspired from Web pages, I think that components are more dynamic when it deals with binding with other components. Bindings will dynamically (on runtime) appear/disappear when replacing a component, how to maintain the ranking of a component? What is the frequency of the component ranking algorithm ?
• In their approach, first they search locally for a suited component. What if remote sites holds better suited components with higher ranks than those already placed in the local repository? What policy to use in order to keep updating the local repository?
• The Crawling module searches for new components, do we need to insert an agent on every repository?
  
• How to manage the heterogeneous aspects between components? COM and CORBA components?
  
• Semantic web and ontology use might simplify the mapping and query even though it is considered to be a disadvantage for the designers of GRIDLE due to the unique usage of a unified taxonomy.
  

Link to the article
PS: According to the Ranking algorithm, the rank of the page hosting the article increased while the rank of my blog is decreasing, actually I am offering a portion of my page's rank.