22/01/2005 - Pascal BIHLER - LIRIS Lyon
A PerSE service network (ServiceNet) consists of two main types of entities: PerSE Services, that means a long running application as well as any other data treating unit, a data source like a sensor, a transforming algorithm like an adopted classical Web Service as well as data drains, a video projector for example. Each service is managed (together with other - maybe related - services) by a so called PerseBase. These core entities are interconnected (with a wired connection or with a wireless link like Bluetooth or WiFi) and therefore responsible for these connections, too. By using this network, each PerseBase is able to run the services offered by any other PerseBase in the network in responding to a user demand (action). To do this efficiently, the PerseBase is using a precalculated p-graph which is based on its or the neighbor's p-graph history resp. the known entity descriptions.
The information about each entity (service, PerseBase) consist of a more or less statically description, the more dynamical context (managed by the service's PerseBase) and some meta-information (Entity-Identificator (EID), Entity-Type) combined on a so called InformationCard (This can be considered like an extended identity card of the entity). Each InformationCard is marked with a timestamp (to decide which the newest information set in doubts is) and a validity-time (used to help the management of InformationCards and to estimate the validity of p-graphs based on this information set). Each PerseBase is storing InformationCards in a database called InformationDock.
Apart from this descriptional knowledge, each PerseBase has (after a sufficient amount of time) as well a kind of "historical knowledge" in the form of ancient used p-graphs which maybe can be reused in future (if they are still valid). While the first steps in trying to react to an user action is the reuse of already existing p-graphs, the creation of new, specific p-graphs based on the current entities' InformationCards represents nevertheless an important part in PerSE's action treatment. This calculation is performed by the action handling PerseBase, so this base needs for the processes of service and base discovery a partial global knowledge of the ServiceNet, sufficient information about all the services, the base is "interested in". To assure that each PerseBase has the information needed for the p-graph calculation, a kind of intelligent distribution algorithm is needed.
By designing an information distribution algorithm for a pervasive computing environment one has to keep in mind, that the context of a service can change rapidly which means that the data stored on the service's information card changes and that this update has to be distributed to interested recipients as well. To increase the network's fault-tolerance and to avoid bottle-necks as well as single points of failure we have decided to provide in contradiction to classical attempts like Web Services (Service Registry, UDDI) or DAISGR/OGSA-DAI in computational grids a solution independent from a central server/directory. While the time for distributing information changes has to stay for the mentioned reasons in a pervasive environment as minimal as possible, we are also confronted with small bandwidth connections (like Bluetooth) or narrow-chested smart devices in some configurations demanding a minimization of the meta information transport and an optimization of the InformationDeck management.
To provide the possibility to calculate a new p-graph in time, the PerseBase's InformationDeck not only holds the InformationCards of the entities the base is responsible for (that means it's own InfoCard with information about connections to other PerseBases as well as the InfoCards of all connected services) but also the InformationCards from all entities it's interested in (services and the correspondig PerseBases). To obtain this knowledge, InfoCards can be exchanged among the bases sending Description Exchange Messages (DXMs) to each other. A Full DXM contains the entity's complete InformationCard as stored in the emitting PerseBase's deck, a Partial DXM, which is emitted after a record update in the InformationDeck, just contains the meta-information (EID, timestamp, previous timestamp (to assure integrity) and validity time) accompanied by the records which have changed. Combined with an algorithm of "Dull Discard" which means that each PerseBase just stores (and propagates) information about services it's interested in we receive a sparse flooding algorithm (EID + Card Timestamp provide a unique DXM identifier needed to avoid loops). Reasons for discarding a DXM are widespread and depend on the implementation and configuration of the PerseBase, this can be reasons like "information to old", "service to far away", "service to slow", "service not matching another quality criteria" or "already enough similar/better services in the InformationDeck" for instance. This mechanism leads to a reduction of information in the network in function of distance and service's value while still maximizing the user's satisfaction.
A second way to initiate the emission of a DXM message is a DXM Request for all or specific entities stored in a neighbor's InformationDeck. These requests are needed for the initial creation of an InformationDeck, to obtain information about entities mentioned in an (historical) p-graph, or to gain information about intermediate PerseBases and their connections. Another use case is the reaction to a received Partial DXM for an entity where no InformationCard can be found in the InformationDeck.
The mechanism of Dull Discard in combination with Partial DXMs and DXM Request can lead to an interesting ping-pong effect, called the "Stressing Neighbor Problem": A PerseBase (A) floods information about a service (S) to a neighbor PerseBase B which is assessing the service as "uninteresting" and discarding the DXM. Now S is adapting (e.g. the context of S is changing) and A is updating his InformationDeck followed by a Partial DXM emitted to its neighbors. B receives the message, is not able to determine the "level of interest" from the given values and therefore requesting a Full DXM from A. A has to response with a Full DXM just to help B to decide that it is still not interested in S and discards all information about S.
In small networks with cheap connections containing no loop reactions this superfluous communication does not lead into big troubles and can easily be ignored. To handle the Stressing Neighbor Problem, a PerseBase can remember why it suppressed the information of which entity and just request a Full DXM when a record changed that justified this decision. But by this, the PerseBase stores a lot of rubbish it's not interested in and it needs a management to maintain this mountain of garbage (LFU strategies, validity time…). Also transferring the problem to the neighbors (just send information to a neighbor when he didn't discard the last DXM) is not solving it but increasing the communication costs by introducing special deny messages and "I've changed my mind" notes.
Apart from settle this question, there are still a lot of other challenges connected to the introduced sparse flooding algorithm which are leading to further research: Which exactly are the records on the InformationCards, what can be considered as "description", what as "context"? How to estimate the values of this context (measurements, still-alive-packets)? How to interpret these values and to compare services with each other? One of the main objects is to define rules for assessing a DXM as "interesting" and "not interesting" representing the heart of the sparse flooding algorithm. At the level of implementation, decisions have to be made on how to represent the information on the entity's InformationCard (hierarchically or "flat"? Provide generic templates to reduce transportation costs further?) as well as defining a structure to organize the InformationDeck in a way it can be easily accessed and updated, but is also prepared to support a fast p-graph calculation. These considerations lead to open questions about the handling of physical limits which can likely be found when implementing PerseBases (together with their corresponding InformationDecks) on smart devices. Working in a pervasive and hereby inevitably vulnerable environment pose security questions, too: How to assure integrity of DXMs? How to assure authentication of DXMs? Is signing an appropriate way? But do we need different “level of trusts” then based on computational power of a PerseBase? At the moment, the sparse flooding algorithm seems to lead to a further improvement of the existing way of information distribution in PerSE, but the experiments to prove this superiority are not yet finished.