Implementation of XMIDDLE
This material is extracted from Mirco Musolesi's Master degree thesis.
In this document we present the implementation of the prototype of our middleware, underlining some remarkable aspects and identifying possible general solutions to common design issues.
Before describing the architecture of our system, we point out some general design choices that we made during the development of XMIDDLE.
The key words of the implementation of XMIDDLE are modularity and extensibility; this approach is a natural consequence of the adoption of object-oriented techniques in the design of our system [Jac94]. We use the Java language that allows developers to define complex object-oriented architecture providing a complete set of programming structures such as classes, abstract classes, interfaces and packages and inheritance mechanisms.
Essentially, the XMIDDLE prototype consists of two parts, an abstract framework and its implementation. The de-coupling between framework and implementation adds flexibility and introduces modularity in the project, according to the principle of reusability; at the same time, the definition of a general framework specifies the structure for the future implementations of the middleware. The classes of the XMIDDLE framework are packaged under edu.UCL.xmiddle.framework, the classes of the implementation under edu.UCL.xmiddle.
As already discussed, the current implementation of XMIDDLE is based on UDP over IP. UDP has been chosen over TCP, as it is more suitable than TCP for a mobile ad hoc setting. In fact, even if TCP provides a more reliable service, it needs to establish a connection before the communication and introduces remarkable packet overhead not appropriate in relation to the average wireless bandwidth usually available. On the other hand, UDP does not guarantee packet delivery and does not prevent duplicate data messages. For this reason XMIDDLE needs to handle data packet duplication and loss. However, during our testing process, we used the 802.11 wireless technology, observing an appreciable reliability as concerns packet loss.
XMIDDLE uses DOM technology [W3C02b] to access XML documents; this was an important preliminary decision in the design of our middleware. In fact another alternative solution to parse XML documents using the SAX standard interface [SAX02] (that stands for Simple API for XML); this provides an event-based framework for accessing XML documents, that are parsed sequentially: when the SAX parser encounters an element or a processing instruction, it treats them as events and calls the corresponding registered listeners. The most remarkable advantage of this technology is that it does not require a large amount of memory in order to perform the parsing process.
DOM is an object-oriented technology for fast random access and manipulation of XML documents (we describe it in Appendix A). We chose DOM technology on the basis of the following considerations. Firstly, random access to data is essential for a large number of applications and this is not provided by SAX parsers. Secondly, DOM represents data using trees that are classic and powerful structures, providing also a complete API in order to traverse and manipulate them; this is a fundamental feature, since we need to perform complex operations especially during the reconciliation process. Finally, in an object-oriented context, DOM is preferable, since it maps XML documents to object structures in a very easy and elegant way.
We implemented XMIDDLE using Java [Sun02e], the widely used platform independent language from Sun Microsystems. We chose it because of its outstanding characteristics: firstly, it provides a platform independent networking and multi-threading support; secondly, a very large number of reliable and optimised XML technologies are available for this platform; finally, in recent years wireless-oriented versions of this language have been developed. The current implementation of XMIDDLE is compliant with the PersonalJava specification [Mah02]. We used Xerces Java Parser [Apa02a] as XML and DOM parser and Xalan-Java [Apa02b] as XPath processor [ClaD99]; they were chosen for their wide distribution and appreciation in industry and in the research community. More in details, Xerces Java Parser supports the XML 1.0 recommendation and also provides a support for the W3C’s XML Schema Recommendation version, DOM Level 1 and DOM Level 2. Xalan-Java is essentially an XSLT processor for transforming documents into other formats (such as HTML or WML); it implements the W3C Recommendations for XSL Transformations (XSLT) [Cla99] and XPath standard language. These software components are very easy to use, since they provide a simple API, supported by a detailed documentation. It is possible to find a presentation of the essential aspects of these technologies in Appendix A.
Now we analyse the XMIDDLE architecture considering its fundamental components and fundamental entities; the platform is essentially composed of the following modules:
- Manager, which provides the access point to the middleware services for applications, supplying a simple API for these to access data, request linking, view hosts that are in reach, connect and disconnect, and to perform other secondary operations; moreover, it is worth noticing that XMIDDLE applications have only access to this component, which, in a sense, abstracts away from the rest of the middleware;
- Network Controller, which handles all network connections and manages all communications among hosts;
- Locator, which identifies the hosts that are in reach and is responsible for keeping the list of available hosts up-to-date;
- Tree, which stores all application information;
- LocalHost, which is responsible for accessing and modifying the local data tree structure. It also manages protocols requests (for example linking operation and reconciliation process);
- Protocol, which represents the protocols that XMIDDLE can handle;
- ProtocolChooser, which essentially controls the execution of protocols; it is worth underlining that our middleware also supports a mechanism that allows the negotiation of protocols and their dynamic load.
The Manager module provides a “high-level view” of the XMIDDLE platform; it represents the only access point that applications have to the middleware, providing a unified and simple API to developers. It is implemented by edu.UCL.xmiddle.SimpleManager, which inherits from the interface edu.UCL.xmiddle.framework.Manager. Manager includes methods to connect and disconnect from the network, initiate protocols, send data to other hosts, access data from the tree, load and manipulate XML documents.
The most important ones are the following:
- void init() starts the XMIDDLE platform, initialising each module of the system.
- boolean connect() performs the connection to the network. It returns the boolean value true if this operation has been successful, false otherwise. This provides a mechanism to request an explicit connection to the network. After a connection, the platform searches for the hosts that are currently in reach and eventually reconciles the local data with other nodes.
- boolean disconnect() allows applications to disconnect explicitly from the network.
- void link (Host host, Integer appID, String remoteElement, Integer localAppID, Element localRoot) allows applications to link a remote element stored on another host. host is the host on which the exported element resides; appID is the identifier of the remote application; remoteElement is an XPath expression that specifies the position of the element to be linked; localAppID is the local application identifier; localRoot is the local root element under which the linked element will be placed.
- void unlink (Element element, Integer appID) stops linking to the specified element. appID is the identifier of the application running on the host on which the element is stored.
- void export(String path, Integer appID) allows applications to export a sub-tree of the local tree specified by the path string, which is an XPath expression that must identify a unique element in the document. The second argument is the application ID of the application that exports this branch of the local tree. This method also creates the version 0 related to this exported element.
- Element open (String path, Integer appID) returns the latest version or edition of the sub-tree specified by the path string (an XPath expression). This must identify a unique element of the tree. appID is the identifier of the application that creates the tree structure.
- public void close(Element element, Integer appID) “commits” the performed changes. In fact, an application after accessing element, must close it, allowing the middleware to update the local tree and start the reconciliation process.
- public void send Data(Data data) allows applications to send data (using the XMIDDLE object Data, which contains the receiver address and the information to be sent).
We will introduce other methods of the XMIDDLE application interface later in this document, when we will discuss in details some communication issues.
The network layer of XMIDDLE is implemented by the edu.UCL.xmiddle.framework.controller package. The corresponding framework package is edu.UCL.xmiddle.controller.
The most important classes of this package are Data, UDPNetwork and UDPLocator.
The Data class provides a representation of the data packets that are exchanged by hosts; it includes methods to set (and get) the data contained in the packet and the host to which the data are addressed (or from which the data were received).
The UDPNetwork class (which inherits from the framework class Network) implements the thread that manages all network connections; it is responsible for sending and receiving Data packets, including protocol requests, which are queued to the LocalHost module. It also provides other functionalities related to the execution of protocols that we will describe later.
Finally, the UDPLocator class (which inherits from the framework class Locator) is responsible for detecting the hosts that are currently in reach. Clearly, it includes methods to get an up-to-date list of the host in reach.
The elaboration of the messages received from other hosts and the coordination of the operations performed on the local tree are provided by the LocalHost class (which implements the Runnable interface).
As the name suggests, this models the local host (as concerns elaboration and coordination), providing methods for queuing protocol requests, handling the local tree and exporting elements. For example, it provides methods to load an XML document into the local data structure and to manage the local tables describing the relationships with other hosts (i.e., the exportLink, linkedBy and linkedFrom tables).
The class that is used to represent the tree structure stored by the middleware is LatestTree, which inherits from the abstract class of the framework Tree. It includes methods to access or modify specific elements or collections of elements using XPath expressions. It encapsulates the latest version of the tree and the previous editions released by the host that stores the data structure. It is worth noting that we implement the versioning system of XMIDDLE in an optimised way to avoid an excessive amount of different versions stored in the memory of each host, keeping only the versions that are really necessary to perform the reconciliation process.
Another interesting aspect is the modelling of the tables containing the linking relations between hosts. This information is represented by means of the LinkTable class; this class provides methods in order to create, access and modify the exportLink, linkedBy and linkedFrom tables. It is possible to retrieve the instance of the LocalHost class by using the getLinks() method of the LocalHost class.
In this section we present some issues related to the implementation of protocols in XMIDDLE, focusing, in particular, on the reconciliation process.
Registration of new protocols
The XMIDDLE framework provides a mechanism to dynamically load new protocols; each class that implements a protocol must inherit from edu.UCL.xmiddle.framework.lib.protocols.Protocol and must follow some specific guidelines that we will describe in the following sections.
The registration procedure of protocols is handled by the Manager (using the Manager.registerProtocol() method); new protocols are registered in an instance of the ProtocolRegistry class; this can return any registered protocol by its name.
The implementation of the XMIDDLE prototype includes the linking and the reconciliation protocols.
A protocol session is defined as a structured network communication between two or more XMIDDLE hosts. The module that manages the negotiation in order to start a protocol session is LocalHost; the first step is the generation of a request of a new session to the involved hosts (these requests are handled by the corresponding LocalHost instances). Requests can be sent automatically by the middleware (for example, this is the case of the automatic reconciliation process) or applications can explicitly send requests by calling the send() method provided by the Manager class. With respect to the first case, we may consider, for example, the reconciliation process, that is triggered automatically by the middleware.
Modules involved in the negotiation before a Linking protocol session
As it is possible to observe in this figure, remote protocol requests received by the Network thread are automatically passed to the LocalHost thread.
When a LocalHost module receives a protocol request, it starts a ProtocolChooser thread in order to perform the service.
The ProtocolChooser thread is responsible for the following tasks during the execution of a protocol:
- negotiating the appropriate protocol to be executed;
- supervising communications between hosts;
- finding the negotiated protocol from the ProtocolRegistry instance or downloading it from one of other hosts;
- starting and synchronizing the protocol during its execution.
When it starts, the ProtocolChooser thread firstly generates a unique session identifier corresponding to that particular protocol session. This is generated independently on each host and, at the same time, it has to be univocal. XMIDDLE uses the primary identifiers of all participants concatenated in descending order and parts of the protocol request to create the session identifier. For example, we may consider two hosts HA and HB that are performing a linking protocol; let us assume that HA is identified by the primary identifier 4444, whereas HB by 5555 and the request is “LINK to /root/one”. In this case, the session identifier will be automatically set to LINK/root/one5555-4444.
After the generation of the session ID, ProtocolChooser registers the session with the Network instance. This uses this information to create the UDPListener (which inherits from the framework class Listener) and UDPSender (which inherits from the framework class Sender) objects and returns the corresponding object references to the ProtocolChooser. UDPListener and UDPSender are responsible respectively of receiving from and sending data to a specific host (which is specified upon the creation of the instances).
Furthermore, it is worth noting that the ProtocolChooser threads can also negotiate directly the communication protocol, bypassing the networking modules. Protocols are stored in a protocol registry (modelled by the ProtocolRegistry class); if the agreed code for the protocol is not available, it can be transferred from another host. Afterwards, instances of the Protocol objects are created and their references are passed to the UDPListener and UDPSender objects.
Example of a linking protocol session
Another interesting issue is the order of transmission (in other words, the choice of the host that has to send the first message). XMIDDLE deals with this problem defining two types of sessions, active and passive. Each host involved in the execution of a protocol performs a type of session: we label as active the host that sends information first and with the term passive to the host that waits a message from another one before starting interaction. In order to decide on the type of the session, XMIDDLE exploits the numerical order of the primary identifiers of the involved hosts.
The ProtocolChooser thread is also responsible for the operations that are performed at the termination (that may be successful or not) of the execution of the protocol: for example, they have to free memory and network resources and de-register themselves from the networking modules. We also point out that it is possible to interrupt the execution of a protocol using the ProtocolChooser.abort() method.
Development of a protocol for XMIDDLE
In this section we will describe the process of the development of a protocol for XMIDDLE in details. First of all, XMIDDLE protocols have to inherit from edu.UCL.xmiddle.framework.lib.protocols.Protocol. Furthermore, essentially, they must implement two methods, execute() and abort(). The first one starts the execution of the protocol and it is called by the ProtocolChooser class; the second one aborts the execution. It is also expected that every protocol is able to provide rollback functionalities in case of the failure of transaction-oriented operations.
Moreover, as we have discussed before, protocols must have a unique name, under which they will be registered with the ProtocolRegistry module; they are also expected to provide the implementation for the two types of XMIDDLE protocol sessions (active and passive).
The constructors of protocols have to be designed to accept the following values (in this order): a Listener object (from which the protocol can receive data sent by the other hosts involved in the protocol session), a Sender object (using which, the protocol can send data to the other hosts that are involved in the session), the session type (which can assume two values Protocol.ACTIVE and Protocol.PASSIVE), a LocalHost object (using which, the protocol is able to access the data structures that are stored in the host), the session identifier, the identifier of the remote host involved in the session and an array of Java objects that contains the parameters that are necessary to perform the protocol (for example, the reconciliation protocol uses an additional parameter to specify the sub-tree that has to be reconciled).
One of the future improvements of XMIDDLE will be a mechanism that allows applications to specify and use new protocols defined by developers.
Implementation of the reconciliation algorithm
The reconciliation algorithm is implemented through a set of classes that are responsible of handling the protocol and representing the structures that are involved during its execution (i.e., editions). The class that implements the reconciliation protocol is Reconciliation. The execution of the protocol is based on the functionalities provided by a certain number of classes that are responsible for implementing the algorithms that enable the reconciliation of distributed and inconsistent replicas of XML documents. These classes are essentially the following:
- LevelTreeDiff class, which implements the LevelTreeDiff algorithm;
- LevelTreeMerge, which implements a “merge” algorithm using a base XML document and a “diff” XML document (it can be considered as the “inverse operation” of the LevelTreeDiff algorithm);
- LevelTreeReconcile, which implements the reconciliation algorithm.
The LevelTreeDiff class
The LevelTreeDiff class allows to compare two XML documents, returning a “diff file”, which is an XML documents that contains the differences between them according to an “operational” notation. Given two documents DocA and DocB, this file specifies the operations that have to be performed on DocA to obtain DocB.
The main method of this class is compute() that, given a base document and a “changed” DOM document as arguments, produces a “diff” document with the format defined by the following DTD specification:
<?xml version="1.0" encoding="UTF-8"?>
<!ELEMENT treediff (addsubtree,delsubtree,changeattr,changepcdata)*>
<!ELEMENT addsubtree ANY>
xpathparent CDATA #REQUIRED
xpathleftsibling CDATA #REQUIRED
insertOrder CDATA #REQUIRED>
<!ELEMENT delsubtree EMPTY>
xpath CDATA #REQUIRED>
<!ELEMENT changeattr (attribute)>
xpath CDATA #REQUIRED>
<!ELEMENT attribute EMPTY>
name CDATA #REQUIRED
oldvalue CDATA #REQUIRED
newvalue CDATA #REQUIRED>
<!ELEMENT changepcdata EMPTY>
xpath CDATA #REQUIRED
oldvalue CDATA #REQUIRED
newvalue CDATA #REQUIRED>
The LevelTreeMerge class
The “diff “ document that is produced by the compute()method of the LevelTreeDiff class (with two documents in input as arguments, a base document and a modified one) is used by LevelTreeMerge.
This class, applying the modifications described by means of the “diff” document to the base document, is able to generate the modified document that has been used as an argument of the LevelTreeDiff algorithm. In other words, this class is used to reconstruct an XML document from a base document, knowing the changes that have been made on it. We have described this merge operation as the inverse of the operation performed by the LevelTreeDiff algorithm; we can motivate this assertion using the example showed in the following figure.
Use of the LevelTreeDiff and LevelTreeMerge classes
As you can see from this example, the LevelTreeDiff class (by means of the compute() method) generates the “diff” document Docdiff that contains the operations that must be performed on DocA in order to obtain DocB; moreover, using the LevelTreeMerge class (by means of the merge() method) it is possible to reconstruct DocB from DocA using Docdiff.
The LevelTreeReconcile class
The LevelTreeReconcile class is responsible of implementing the reconciliation algorithm. Its most important method is reconcile(); the arguments of this method are the two XML documents that have to be reconciled; the output of this class is the reconciled document. The order of the arguments is not important in this case. LevelTreeReconcile exploits the LevelTreeDiff algorithm in order to find the differences between the two XML documents.
The exploration of the DOM tree structures is performed using recursion in an optimised way. LevelTreeReconcile is able to deal with the reconciliation of ordered and unordered trees, analysing the order attribute of the root node of the two XML documents to be reconciled. If the order attribute is not expressed, this class treats these documents as ordered trees.
Implementation of the reconciliation process
To better understand the reconciliation algorithm, we analyse an example from an implementation point of view, without considering all the details (i.e., generation of the edition numbers, etc.).
HostB starts the reconciliation protocol; we define the operations performed by the application that is running in this host as local; we identify the other host involved in this process as HostA; it receives the request to perform the protocol from HostB and therefore we name the operations performed in this host as remote. It is worth noting that we also used this terminology in the development of the Reconciliation class: the two main methods corresponding to the active and the passive sessions are respectively called ExecuteLocal() and ExecuteRemote(). In other words, in order to perform the reconciliation, after the identification of the type of sessions (active or passive), the middleware on HostA uses the ExecuteRemote() method and on HostB the ExecuteLocal() method.
Moreover, we refer to the copy of the document stored on HostA as DocA and that maintained on HostB as DocB. Let us also suppose that, after the execution of the first part of the protocol, the document Doccom has been choosen as Latest Common Edition, in other words as base document of the LevelTreeDiff algorithm. The documents that are involved in the reconciliation process are represented by DOM Document objects; we use the Xerces and Xalan packages that we present in Appendix A.
ExecuteRemote() on HostA calls the compute() method of the LevelTreeDiff class with Doccom and DocA as arguments (Doccom is the base document, whereas DocA is the modified document). The output of the execution of this method will be the “diff” document Docdiff,, which will be sent to host HB as you can see in the following figure. The exchange of the DOM Document objects is based on object serialization provided by the Java language.
Generation of the “diff” document on host HA from the latest common edition and the local replica of the data document using the LevelTreeDiff class.
After receiving Docdiff, the middleware running on host HA calls the merge() method of the LevelTreeMerge class with Doccom and Docdiff as arguments in order to reconstruct DocA locally.
Therefore, on host HB now there are a local copy of DocA and, naturally, DocB. Thus, the reconciliation between these two documents is performed on host HB without exchanging information with host HA during the execution of the algorithm. This process is illustrated in the following figure.
Using the common latest edition a local copy of the replica stored in the other host is generated.
It is possible to reconcile DocA and DocB using the method Reconcile() of the LevelTreeReconcile() class. The arguments of this method are the local copy of the document (DocB), the remote copy (DocA) and the latest common edition (Doccom). The output will be a “reconciled document” called Docrec (as you can see in the following figure).
In host HB by means of the LevelTreeReconcile class the reconcilied document of the two inconsinstent replicas is generated.
The final step is the generation of the reconciled document on host HA; the middleware uses the compare() method of the LevelTreeDiff class again, with Doccom and Docrec as arguments, in order to compute a new “diff” document. Afterwards, this is sent to HA (in the following figure we call it Docdiffn).
Using the LevelTreeDiff algorithm, the middleware generates the “diff” document between Doccom and Docrec.
The middleware then reconstructs the reconciled copy in the usual manner, exploiting the merge() method of the LevelTreeMerge class with Doccom and Docdiffn as arguments. Now, HostA and HostB store the reconciled copy, which will be the new latest common edition.
The versioning system is implemented by a certain number of classes, such as LatestTree (which inherits from Tree). LatestTree provides methods to navigate and modify the versioning tree. We also point out that the new edition number is released on HostB after the generation of the reconciled document.
The reconciled document is generated on HostA using the LevelTreeMerge again. Now Docrec is present in both hosts.
It is worth noting that all these computations rely on Xerces and Xalan. This limits the performance of the system, since these packages require a large amount of memory and, for this reason, they are quite unsuitable for resource-poor devices. One of the future improvements will be the replacement of these components with more lightweight ones such as NanoXML [Des02] or kXML [GHKP02].
As we have discussed before, the current implementation of XMIDDLE relies on UDP over TCP. In this section we discuss some solutions that has been adopted in order to implement the modules that are responsible for network communications.
XMIDDLE uses the java.net.MulticastSocket class to verify the presence of other
hosts in reach (independently from the wireless communication technology
used by mobile devices). This class allows programmers to send and receive IP
multicast packets. A Java multicast socket is a datagram socket (in fact java.net.MulticastSocket inherits from java.net.DatagramSocket), with additional capabilities for
joining IP-multicast groups. A multicast group is specified by a class D IP
address and by a standard UDP port number. Class D IP addresses are in the
220.127.116.11, inclusive; therefore, the address 18.104.22.168
is reserved and should not be
used. We chose the class D IP address 22.214.171.124 and the port number 6789.
The class edu.UCL.xmiddle.controller.UDPNetwork (which extends edu.UCL.xmiddle.framework.controller.Network), is responsible for creating the multicast socket and joining the group, when the host is connected to the network, and leaving the group and closing the socket, when the host disconnects from it. It is worth noting that two hosts may be in the same radio coverage (if they relies for example on 802.11 technology) and may be disconnected, since connection and disconnection are not automatic operations, but are decided by applications (in fact, the middleware provides primitives in order to perform connections and disconnections).
In addition, each XMIDDLE host has a private socket for the requests that are sent only to it; the port number is not fixed and is specified by the application. The UDPNetwork thread opens the socket (using java.net.DatagramSocket) and listens for requests sent to the host, when this is connected to the network; the UDPNetwork thread is also responsible for parsing the packets received and queueing the corresponding requests to the LocalHost module (in the case of protocol request). After a disconnection, UDPNetwork closes the socket and stop the thread that is responsible for receiving message from other hosts.
Now we can analyse in detail how XMIDDLE is able to provide host-awareness, which is an essential feature for a middleware system that has been designed to support the development of applications for an ad-hoc network context.
As we have discussed in the previous section, when an XMIDDLE host is connected, it maintains two sockets to interact with other hosts, a multicast socket and a private socket. Using the first one, it periodically multicasts to any other hosts a message containing information that are necessary to enable communication between two hosts that get in reach for the first time. This message includes the primary and secondary IDs of the transmitting host, its IP address number, the number of the port bound to the private socket, the ExportLink and the LinkedFrom tables.
The edu.UCL.xmiddle.controller.UDPNetwork.OnlineMessage class is responsible for multicasting this information at predefined intervals, while the edu.UCL.xmiddle.controller.UDPLocator class is responsible for receiving information by the other hosts that are in reach, parsing it and updating the InReach table. UDPLocator also checks the presence of a new host in reach in the exportLink and linkedFrom tables. If the two hosts are sharing information, UDPLocator starts the automatic reconciliation process, queuing a request to LocalHost. If the new host in reach is present in the inReach table, UDPLocator updates its LinkTable. To detect possible disconnections UDPLocator checks the time that has occurred since a host has last multicast its message. If this value is greater than a pre-defined threshold, the host is deemed to be out-of reach and consequently the inReach table is updated.
In order to provide an example of this mechanism, let us consider a host with primary ID 555 and secondary ID pda32, with 192.168.0.4 as assigned IP address, which has a private socket bound to port 2000. We also assume that this host exports the /shared_data/data1 branch. In this case the message that is multicast to other hosts will be:
UDPLocator includes methods to retrieve the hosts that are currently in reach by IP address and by their primary IDs; exploiting this feature, it is possible to identify which host has sent a specific message. However, we underline that the implementation is not based on IP addresses, since they are not assumed as fixed. The only piece of information that is expected to be constant and unique (in order to identify univocally each host) is the primary ID. Moreover, when a host becomes in reach, UDPLocator queues a request to the LocalHost in order to start the reconciliation process.
Last update: January 2003 by Mirco Musolesi