Adrien Lèbre

Renaud Lottiaux

Erich Focht

Christine Morin

Reducing Kernel Development Complexity in Distributed Environments ⋆

Setting up generic and fully transparent distributed services for clusters implies complex and tedious kernel developments. More flexible approaches such as user-space libraries are usually preferred with the drawback of requiring application recompilation. A second approach consists in using specific kernel modules (such as FUSE in Gnu/Linux system) to transfer kernel complexity into user space. In this paper, we present a new way to develop kernel distributed services for clusters by using a cluster wide consistent data management service. This system, entitled kDDM for "kernel Distributed Data Management", offers flexible kernel mechanisms to transparently manage remote accesses, cache and coherency. We show how kDDM simplifies distributed kernel developments by presenting the design and the implementation of a service as complex as a fully symmetric distributed file system. The innovative approach of kDDM has the potential to boost the development of distributed kernel services because it relieves the developers of the burden of dealing with distributed protocols and explicit data transfers.

Introduction

Clusters are today a standard computation platform for both research and production. A lot of work has already been done to simplify efficient use of such architectures: batch schedulers, distributed file systems, new programming models, . . . and it is likely to continue as cluster constraints are still changing: more cores per CPU socket, faster interconnects, larger scale.

Setting up generic and fully transparent distributed services for clusters implies complex and tedious kernel developments. More flexible approaches such as user-space libraries are usually preferred with the drawback of requiring application recompilations. However a lot of applications are mainly based on standards such as POSIX and recompliation is sometimes not possible (in particular for legacy codes). In such cases, distributed services have to be perfectly transparent, requiring kernel extensions. However, only few kernel mechanisms have been suggested. Current approaches consist in completing major kernel components by modules to bring back kernel complexity to user space. As an example, the FUSE module from the Gnu/Linux system makes distributed file system implementation easier. If such an approach solves the transparency issue, it impacts performance by the multiple copies from user to kernel and symmetrically. On the other side, userland cluster services are designed by levering generic libraries such as MPI making their design and their implementation much easier.

In contrast with userland, only few work has focused on providing generic layers to faciliate distributed kernel services. From our best knowledge, developers are only aware about the remote procedure call protocol. The SUN RPC model [START_REF] Morin | Rpc: Remote procedure call protocol specification version 2[END_REF] is based on a client server where a node (the client) asks for a service delivered by another node (the server). This model offers some flexibility but has several drawbacks. For instance, it only enables point to point communication and is not well designed to share data structures at a fine grain.

In this paper, we present a new way to design and implement kernel distributed services for Gnu/Linux clusters by using a cluster wide consistent data management service. From our point of view, providing such a service is really innovative. First, this system, entitled kDDM for kernel Distributed Data Manager, is built with the purpose to ease the design and the development of more complex distributed services. Second, it provides a real different way to exchange and share kernel data between distinct nodes within a cluster. By using the kDDM mechanism, programmers are able to focus on the real purpose of cluster kernel sevices instead of dealing with distributed protocols. The kDDM infrastructure helps reducing cluster kernel development complexity to a level comparable to the development on a SMP node.

We show how kDDM makes distributed kernel developments easier by presenting the design and the implementation of a service as complex as a fully symmetric distributed file system. This file system, named kDFS enables to:

-Aggregate storage resources available within a cluster, -Provide a unique cluster wide name-space, -Provide cooperative cache for both data and meta-data. More generally, the use of kDDM could be exploited in almost all local kernel services to extend them to cluster scale. Cluster wide IPC, distributed namespaces (such as /proc) or process migration are only a few of the candidates.

The document is organized as follows. Section 2 outlines the kDDM mechanisms. Section 3 is focused on kDFS design and its implementation. Related work is addressed in Section 4. Finally, Section 5 concludes the document and gives some perspectives.

Kernel Distributed Data Manager

The Kernel Distributed Data Manager, kDDM [START_REF] Lottiaux | Containers: A sound basis for a true single system image[END_REF], allows consistent and transparent data sharing cluster wide. This concept was formerly called container and has been renamed to kDDM to avoid confusion with current kernel container mechanisms.

The latest implementation of the kDDM service allows to share at kernel level collections of objects between the nodes of a cluster. In kDDM, an object is a set of bytes defined by the kDDM user (data structure, memory page content, etc). Objects of the same kind are stored in a set. An object is then identified using a pair (set identifier; object identifier).

The main goal of the kDDM mechanism is to implement distributed kernel services. Assuming that an OS could be roughly divided into two parts: (1) system services and (2) device managers, developpers could design and implement their own cluster wide services (cf. Figure 1 (a)) or extend the existing ones by using interface linkers (cf. Figure 1 (b)). In both cases, kDDM sets are plugged to device managers thanks to IO linkers.

kDDM Sets

A kDDM set is a collection of similar objects a kernel developer wants to share cluster wide. Each set can store up to 2 32 objects. Objects are managed by the kDDM service without any assumptions on contents and semantics. In other words, developers have the opportunity to share any kind of objects.

For each kind of object to share, a new kDDM set family is created to host this kind of object. It is then possible to create several sets of the same family.

For instance, it is possible to define a kDDM set family to share clusterwide all pages of a system V memory segment. From this kDDM set family, we can create a new set for each system V segment.

Defining a new kDDM set family mainly consists in creating a new IO linker designed to manage the kind of object they are intended to host.

IO Linkers

Each kDDM set is associated to an IO linker depending on the family set it belongs to. For each family there is a different IO linker. During the creation of a new kDDM set, an IO linker is associated to it. Doing this instantiation, the set can be attached to a physical device or simply attached to a dedicated memory allocator (memory pages allocator, specific slab cache allocator, etc). Indeed, the IO linker defines how objects are allocated, freed, transfered from one node to another, etc.

Right after the creation of a kDDM set, the set is completely empty, i.e. it does not contain any data. Memory is allocated on demand during the first access to an object through the IO linker. Similarly, data can be removed from a kDDM set when it is destroyed, when an object is no more in use or in order to decrease the memory pressure when the physical memory of the cluster is saturated. Again, these operations are performed through the IO linker.

Interface Linkers

Existing kernel services can be extended to a cluster scale thanks to interface linkers. An interface linker is the glue between existing services and kDDM sets.

Moreover, it is possible to connect several system services to the same kDDM set by using different interface linkers. For instance, a kDDM set can be used to map pages of a file in the address space of a process P1 on a node A using an interface linker L1, while a process P2 on a node B can access the same kDDM set through a read/write interface using another interface linker L2.

Manipulation Functions

Objects are handled using manipulation functions which ensure data replication and coherence. These functions can be compared to read/write locking functions. They are mainly used to create kDDM critical section enabling to safely access kDDM objects regardless of data location in the cluster.

Objects stored in a kDDM set are handled using a dedicated interface. This interface is quite simple and mainly relies on three functions used to create kDDM critical sections: get, grab and put.

The get function is close to a read-lock : it places a copy of the requested object in local memory and locks it cluster wide. This locking ensures that the object can not be written on any other node in the cluster. However, concurrent read accesses are allowed.

The grab function is close to a write-lock : it places a copy of the requested object in local memory and locks it cluster wide. No other concurrent access (read or write) is allowed cluster wide (cf. Section 2.5).

The put function is used to unlock an object. In addition to these main functions, a few other ones are used, such as remove, flush or sync. The remove function removes an object from the memory cluster wide since the flush function only removes an object from local memory and ensures that there is at least one node still hosting a copy.

Finally, the sync function synchronizes an object with its attached physical device, if any. This function is useful for instance to write back data to disk.

Replication and Coherence

During a kDDM critical section, object data is stored in the memory of the node doing a get or a grab and can be accessed using regular memory operations. Outside a kDDM critical section, there is no guarantee that the object is still present in node local memory. In most cases the data is still present, but the kDDM semantics does not guarantee coherency outside a kDDM critical section.

As suggested in the previous section, objects are moved from one node to another during a grab operation and can be replicated on different nodes for efficiency reasons during a get. Replication introduces a data coherence issues. Coherency is managed using an invalidation on write protocol, derived from the one presented by Kai Li [START_REF] Li | Shared Virtual Memory on Loosely Coupled Multiprocessors[END_REF]. The grab function, semantically equivalent to a write, is used to catch object modifications. In this case, all the existing remote copies are invalidated before the grab returns. During the grab critical section, the object is locked on the node (where the grab has been done) and cannot be moved or replicated.

Kernel Distributed File System

In order to show the interest of generic distributed kernel mechanisms such as the kDDMs, we chose to design and implement a service as complex as a fully symmetric file system. To our knowledge, only few distributed file systems have been designed with fully symmetric constraints [START_REF] Anderson | Serverless network file systems[END_REF][START_REF] Li | Bfxm: a parallel file system model based on the mechanism of distributed shared memory[END_REF]. The implementation complexity of such systems is generally dissuasive and the current trend consists in setting up distributed file systems composed by one or two meta-data servers and several I/O servers [START_REF] Carns | PVFS: A parallel file system for linux clusters[END_REF][START_REF] Schwan | Lustre : Building a file system for 1,000-node clusters[END_REF]. By dividing meta-data and data management, such solutions, entitled parallel file systems, make the implementation of the client stack easier. However such a model can lead to a non balanced architecture between distinct nodes. For example: the scalability limitation imposed by a single metadata server does not exist in a fully symmetric file system. Thanks to kDDM, we were able to quickly design and implement a symmetric file system, kDFS, providing a cooperative cache for both data and meta-data.

The evaluation of kDFS is behind the scope of this paper. Several parameters have been arbitrarily chosen and advanced mechanisms such as data-striping, redundancy or distributed I/O scheduling are addressed in a more technical document [START_REF]Design and implementation of high performance disk input/output operations in a federation[END_REF]. The innovative work, addressed in this article, consists in setting up such a fully distributed file system at kernel level without dealing with distributed protocols or consistency issues.

The design of kDFS relies on two main concepts: -Using native file systems available on each node -Using kDDM sets to provide a consistent cluster wide name space. The use of kDDM sets facilitates the implementation of a global distributed cache with Posix semantics since kDDM mechanisms directly ensure meta-data and data consistency. Figure 2 illustrates the overall architecture of kDFS.

After describing how kDFS uses native file systems to store data, we present how kDDM mechanisms have helped kDFS be implemented with elegance and simplicity.

Disk Layout

To avoid block device dependencies and make storage management easier, we have chosen to build kDFS upon native file systems provided by the cluster nodes. As a consequence, each node has to specificy if it takes part in the kDFS storage space or not. Storage space provided by a particular cluster node is considered as a kDFS partition only if it has been kDFS formatted. As kDFS does not directly manipulate block devices, a kDFS partition actually refers to a local directory with a particular hierarchy. This section introduces different sub-directories and different files contained in a kDFS partition.

To format a directory which can be used afterwards in the kDFS storage space, administrators have to use the mkfs.kdfs command. This command takes two arguments: DIR_PATHNAME and ROOT_NODEID. The first one corresponds to the absolute path to store kDFS meta-data and data, the second one is the node identifier for the kDFS root entry (the node that stores the kDFS root inode).

mkfs.kdfs creates the kDFS "superblock" file (...) for the node. This file is stored on the local native file system in the given directory. If the current node identifier (last byte of the IP address) equals to the given id, mkfs.kdfs creates the root entry (the '/' of the file system).

Table 1 describes the creation of a kDFS structure over two nodes: For each entry (a directory or a file) of the kDFS hierarchy, a "native" directory is created on one kDFS partition within the cluster. it contains two files:

-The .meta file that stores meta-data associated with the entry (size, timestamp, rights, striping information, . . . ) -The .content that stores real data (directory and file contents).

The name of the "native" directory is defined by the kDFS local inode identifier (each kDFS superblock file contains an identifier bitmap to define the next free inode id ).

To avoid scalability issues with large directories, we have arbitrarily chosen to sort each kDFS partition in groups of one hundred entries. For instance, when mkfs.kdfs creates the kDFS root entry, the command first creates a subdirectory 'DIR_PATHNAME/0-99/'. Then, it creates the corresponding "native" directory which is the DIR_PATHNAME/0-99/1/ directory. Finally, the file '.meta' and the file '.content' are created inside this latest directory. Every hundred entries, kDFS adds a new sub-directory corresponding to the appropriate range ('DIR_PATHNAME/100-199/', 'DIR_PATHNAME/200-299/', . . . ).

Once the partition is formatted, users can access the kDFS file system thanks to the mount command: mount -t kdfs ALLOCATED_DIR|NONE MOUNT_POINT where ALLOCATED_DIR corresponds to the native file system directory formatted with mkfs.kdfs and MOUNT_POINT is the traditional mount point. Since files and directories are stored in a distributed way on the whole cluster, we need mechanisms to find the kDFS entry point and thus be able to join the file system. kDFS provides two ways of retrieving the root inode. The first one is based on the superblock file stored in the formatted kDFS partition. As mentioned, the kDFS superblock file provides several information including the kDFS root inode id. Thus, when a mount operation is done, the '...' file is read from 'ALLOCATED_DIR' and the root inode id is used to retrieve the kDFS root entry. The second mechanism relates to diskless nodes or nodes which do not want to take part in the kDFS physical structure. In such a case, users do not specify a "device" but have to provide the kDFS root inode id as an additional mount parameter.

File System Architecture

The use of kDDM in our symmetric file system enables to propose a simple design based on two layers. The highest one, in charge of forwarding local requests to the kDDM serivce, is directly plugged under the VFS. The lowest one, composed by the different I/O linkers, applies kDDM requests on proper kDFS partitions previously presented.

Currently, kDFS has been implemented using three families of kDDM sets: -Inode kDDM set, one cluster wide. It provides a cache of inodes recently accessed by processes. -Dir kDDM set, one per directory. Each Dir kDDM set contains directory entries (roughly names of subdirectories and files). -File kDDM set, one per file. It stores data related to the file contents.

Figure 3 depicts the kDDM entities for several kDFS entries. To make reading and understanding easier, we also provide a potential representation of the regular files for each kDFS entry on the native file systems.

Next sections introduce each of these three families of kDDM sets. A fourth kDDM set is depicted in Figure 3: the dentry kDDM set. This unique kDDM set provides a distributed cache to manage all dentry objects. It is currently not implemented and requires deeper investigations.

kDFS Inode Management

kDFS inode management relies on one global kDDM set. This set exploits a dedicated I/O linker for inserting/removing and maintaining each kDFS entry on the corresponding local file system (sub-directory creation/deletion and updating of the '.meta file'). The inode set is created during the first kDFS mount operation within the cluster. At the beginning, it only contains the kDFS root inode. Then, when a process wants to access one file/directory, its corresponding kDFS inode is added into the set (providing by this way a fully distributed inode cache). All file/directory creations are performed locally whenever possible. That means, when a process wants to create a new file or a directory, kDFS looks for a kDFS partition. If there is one directly available on the node, a new inode identifier is obtained from the superblock file. Otherwise, kDFS stores the new entry on the same node as the parent directory.

When a mount operation is done, the root inode identifier is used to retrieve the root inode structure directly inside the inode kDDM set (cf. Section 3.1). If the kDDM set already exists, the structure is already cached and the inode is simply returned to the node. Otherwise, the request is forwared by the kDDM kDFS Directory Management When an application tries to list the contents of a directory stored in the kDFS storage space, kDFS creates a new directory kDDM set. This new set is linked to the inode object stored in the inode kDDM set and caches all directory entries on a page basis. In other words, all file and subdirectory names stored in the directory are loaded in objects of this new kDDM set (one object corresponding to one page). After that, all filename manipulations such as create, rename and remove apply modifications of these pages. The associated dir I/O linker is in charge of propagating changes to the proper hard drive into the '.content' file.

kDFS File Management In this first prototype, kDFS file management is similar to directory management: when an application tries to access a file f , if f is not already "cached", kDFS creates a new file kDDM set. As for directory management, this new set is linked to the corresponding inode object of the file f . The associated file I/O linker is in charge to read/write data from/to the .content file of f and remove/put pages in the set.

Related Work

While distributed applications programmers can choose between a multitude of parallelization concepts, libraries and languages, infrastructure extensions for supporting distributed operating systems are rather rare. Most distributed services such as the Linux ones (the global filesystems Redhat GFS and Oracle's OCFS2, the distributed lock manager or the clustered logical volume manager) are each using their own protocols for communicating across nodes and have their own notion and view of what group of nodes they regard as "the cluster".

All these services are implemented on top of the socket interface, with no cluster abstraction or communication layer in between.

A component worth mentioning as piece of infrastructure specially built to ease distributed computing is SunRPC [START_REF] Morin | Rpc: Remote procedure call protocol specification version 2[END_REF]. It is used heavily in the network file-system NFS implementations and offers mechanisms to register, locate and invoke remote procedures, while transfering data in the exchangeable data format XDR, allowing nodes of different architectures to interoperate transparently. Programming with RPCs has been adopted widely in both user and kernel space and has contributed significantly to the development of distributed computing.

A further step towards distributed operating systems is the introduction of cluster aware network stacks like the Transparent Inter Process Communication protocol TIPC [START_REF] Maloy | Tipc: Providing communication for linux clusters[END_REF]. It uses a cluster oriented addressing scheme, implements features like reliable multicast, cluster membership with subscription to membership change notifications, cluster-wide services and name-spaces. TIPC provides a socket interface to ease transition of socket based codes, as well as a raw kernel-only interface which allows full control over all features. kDDM is leveraging TIPC by using it as low level cluster communication infrastructure.

All former solutions are based on the message passing model. Another approach close to the kDDM one has been proposed by the PLURIX project [START_REF] Goeckelmann | Plurix, a distributed operating system extending the single system image concept[END_REF]. Built on top of distributed JAVA objects, this system shows that a shared object model can make the design of distributed services easier. The PLURIX object consistency is based on a transactional model whereas kDDM service exploits an invalidation-on-write protocol.

Conclusion and Future Work

The paper has introduced kDDM as infrastructure component suitable for building cluster-wide services in a simple and natural way. The symmetric filesystem kDFS was presented as one highly complex distributed service leveraging kDDM functionality. Its implementation shows how the complexity of managing distributed data transfers and protocols can be reduced dramatically by using the kDDM's distributed shared objects concept (no additional network protocol has been required).

The paper also aimed at pointing to a general method of designing and implementing distributed services by extending their well-known non-distributed variants with kDDM functionality. This methodology has been applied in the past years and lead to the Kerrighed single system image system, one of the most complete implementations of SSI. Kerrighed is a distributed operating system where all distributed components are implemented on top of the kDDM infrastructure.

Future work aims at providing kDDM as component loadable as module for normal unpatched Linux kernels, and increasing the number of stand-alone distributed services built on top of kDDM. Work on the symmetric file system kDFS will continue 4 , next planned steps being: improvement of stability, evaluation and tuning of performance.

Fig. 1 .

 1 Fig. 1. kDDM overview

Fig. 2 .

 2 Fig. 2. Overview of the kDFS system

Table 1 .

 1 kDFS structure creation (two nodes)

	On node A: (nodeid = 1)	on node B: (nodeid = 2)
	mkfs.kdfs /PATH1 1	mkfs.kdfs /PATH2 1
	Create kDFS local '...'	Create kDFS local '...'
	Create kDFS root entry

Table 2

 2 describes kDFS mounting procedure from two nodes:

	On node A: (nodeid = 1)	on node B: (nodeid = 2)
	mount /PATH1 /mnt/kdfs	mount /PATH2 /mnt/kdfs

Table 2 .

 2 Mount kDFS partitions /mnt/kdfs is now a global kDFS namespace for both nodes

The prototype is available at: http://www.kerrighed.org/wiki/index.php/KernelDevelKdFS

⋆ The authors from INRIA and NEC carry out this research work in the framework of the XtreemOS project partially funded by the European Commission under contract #FP6-033576.

service to the proper I/O linker within the cluster. Finally, the I/O linker exploits the inode id to retrieve required information from the hard drive. KDFS inodes are currently based on 32 bits, the 8 MSB bits provide the node id within the cluster and the 24 LSB ones correspond to the local id.

kDFS Content Management

Since kDFS file hierarchy is based on native file systems, both directories and files are stored as regular files. In contrast to traditional file systems, the management of a large kDFS directory containing a huge number of directory entries is similar to the management of a kDFS file content. Regardless of the kDFS entry, its content is stored in its respective '.content' file.


Christine Morin

Alain Gefflaut

Michel Banâtre

Anne-Marie Kermarrec

Coma: An

COMA: an Opportunity for Building Fault-Tolerant Scalable Shared Memory Multiprocessors

published or not. The documents may come


Nazih Ouwayed
email: nazih.ouwayed@loria.fr

Abdel Belaïd
email: abelaid@loria.fr

Separation of Overlapping and Touching Lines within Handwritten Arabic Documents

Keywords: Handwriting line segmentation, Arabic documents, Overlapping and Touching lines, Calligraph morphology

In this paper, we propose an approach for the separation of overlapping and touching lines within handwritten Arabic documents. Our approach is based on the morphology analysis of the terminal letters of Arabic words. Starting from 4 categories of possible endings, we use the angular variance to follow the connection and separate the endings. The proposed separation scheme has been evaluated on 100 documents contains 640 overlapping and touching occurrences reaching an accuracy of about 96.88%.

Introduction

The text line and word extraction from a handwritten document, is seen as a labored task. The difficulty rises from the characteristics of the handwritten documents especially when they are ancient. These documents present irregular spacing between the text lines. The lines can overlap or touch when their ascenders and descenders regions belong to each other (see figure 1). Furthermore, the lines can be skewed which constitutes new orientations. In the literature, several methods have been proposed dealing with skewed lines [START_REF] Lüthy | Using hidden Markov models as a tool for handwritten text line segmentation[END_REF][START_REF] Zahour | Text Line Segmentation of Historical Arabic Documents[END_REF][START_REF] Bukhari | Segmentation of Curled Text Lines using Active Contours[END_REF][START_REF] Shi | Line Separation for Complex Document Images Using Fuzzy Run length[END_REF][START_REF] Ouwayed | Multi-oriented Text Line Extraction from Handwritten Arabic Documents[END_REF]. Few methods have been proposed for the separation of connected words in the adjacent lines. From them, an Independent Component Analysis (ICA [START_REF] Hyvarinen | Survey on Independent Component Analysis[END_REF]) segmentation algorithm is proposed by Chen et al. in [START_REF] Chen | Independent Component Analysis Segmentation Algorithm[END_REF]. The ICA converts the original connected words into a blind source matrix and calculates the weighted value matrix before the values are re-evaluated using a fast model. The readjusted weighted value matrix is applied to the blind source matrix in order to separate the word components. Louloudis et al. propose in [START_REF] Louloudis | Line And Word Segmentation of Handwritten Documents[END_REF] a skeletonbased algorithm. In [START_REF] Takru | Separation of touching and overlapping words in adjacent lines of handwritten text[END_REF], Takru and Leedham propose a technique that employs structural knowledge on handwriting styles where overlap is frequently observed. All above approaches are applicable to Latin scripts which are not easy adaptable to Arabic because of specific morphology.

In this paper, we propose a novel method considering the morphology of the terminal letters in the PAWs. The rest of the paper is organized as follows: overlapping and touching types in the Arabic document are listed in section 2. The Arabic script morphology is discussed in section 3. In section 4, our separation approach is detailed. Experiments results are showed in section 5 and last section concludes the paper.

Overlapping/Touching Types

The Arabic alphabet is composed of 28 letters. Among of them, 21 letters have an ascender (alif , Ta , DHa , kaf , lam , heh ), right descender (ra , zïn , sïn , shïn , Sad , Dad , qaf , mïm , nün , waw , yeh ) or Statistically, we have found 4 overlapping/touching types in handwritten Arabic documents. In the first type (see table 1.a), a right descender with a loop overlaps/touches a vertical ascender. In the second type (see table 1.b), a left descender with a loop overlaps/touches a vertical ascender. In the third type (see table 1.c), a right descender overlaps/touches the curving top of lower letter. In the fourth type (see table 1.d), a left descender overlaps/touches the curving top of lower letter. In each type, the top letters stretches out to overlap/touch the bottom letters.

Arabic Morphology Analysis

In all cases of connection, we notice the presence of a descender connecting a lower terminal letter (see table 1, column overlapping/touching zones). These descenders are clustered in two categories : (a,c) when the descender comes from right and (b,d) when the descender comes from left. To face this connection problem, the analysis will be focused on the connection zones (see figure 3). The zones are determined considering a rectangle around the intersection point S p of the two connected components which size is fixed manually (see section 4.2). The starting ligature point B p is the highest point in the zone close to the baseline. The descender direction is determined according to B p relative to S p (see section 4.2).

According to these characteristics, our idea consists to follow the skeleton pixels within the zone using the starting point B p and the right descender direction. The follow-up will then cross the intersection point S p and continues in the right direction that we have to determine.

Right Follow-up Direction

The determination of the right direction follow-up requires the study of curves in the skeleton image (i.e. each zone in the figure 3 has two curves).

In the literature, there are two main categories of curve detection methods [START_REF] Dori | Stepwise recovery of arc segmentation in complex line environments[END_REF]. In the first category, the Generalized Hough Transform (GHT) is used [START_REF] Ballard | Generalizing the Hough Transform to detect arbitrary shapes[END_REF]. This technique is not efficient in our case because the present curves have few points and GHT needs much points for correct detection. In the second category, the chains (some of connected skeleton pixels) of points, or segments yielded by the polygonal approximation of such chains are used. The basic idea is to compute an estimation of the curvature for these chains [START_REF] Rosin | Segmentation of Edges into Lines and Arcs[END_REF]. This technique is insufficient because it does not study the continuity and the morphology of the curve.

The proposed method is based on the skeleton pixels follow-up and the angular variance. The follow-up starts from B p and continues to the intersection point S p . At this point S p , the follow-up continues in multiple directions (see figure 4.a). The follow-up continues in each direction to extract the possible curves (C 1+2 , C 1+3 and C 1+4 ). The next step is to find the curve that represents the descender terminal letter. By experience, we found that the Arabic terminal letters have a minimum angular variance. This is explained by the fact that the terminal Arabic letters have the same orientation angle along the descender curve.

Angular Variance:

The angular variance represents the dispersion of the orientation angles along the curve. It is estimated using the statistical variance formula:

V ar(Θ) = n i=1 (θ i -µ) 2 (1)
where Θ is the angles variation vector of the curve and µ is the average of Θ.

The angles variation vector Θ of the curve is estimated using an iterative algorithm that calculates the angle θ i between two successive pixels p i and p i+2 using the formula below (see figure 4.b):

θ i = Arctan dy i,i+2 dx i,i+2 (2)
Because of the symmetric branches, the angle value must be always positive. For example, in figure 4, the angular variances are: V ar(C 1+2 ) = 703.19, V ar(C 1+3 ) = 299, V ar(C 1+4 ) = 572.37. In this example, the minimum angular variance V ar(C 1+3 ) is given by the right follow-up direction.

Proposed Method

The method involves four steps as follows:

Step 1: Overlapping and Touching Connected Components Detection

The present paper is a continuation of our work published in [START_REF] Ouwayed | Multi-oriented Text Line Extraction from Handwritten Arabic Documents[END_REF]. The lines are extracted in [START_REF] Ouwayed | Multi-oriented Text Line Extraction from Handwritten Arabic Documents[END_REF] from the handwritten Arabic documents. Some adjacent lines can be connected in one or more connected components. This components belonging to two adjacent lines are considered as connected (see figure 5.a).

Step 2: Curve Detection

To detect the curves, the skeleton is first extracted using a thinning algorithm descried in [START_REF] Lam | Thinning Methodologies-A Comprehensive Survey[END_REF]. Then, the intersection points of each connected component are detected (see figure 5.b). An intersection point is a pixel that has at least three neighbor pixels. As in Arabic script, the overlapping or touching may occur at just one intersection point S p near the minima axis (valley between two connected lines in the projection histogram of the document, see figure 5.c). For this, S p is the nearest point of the minima axis (see figure 5.d). Once the S p is located, we look for the connected components zone. The center of this zone is S p and its width (resp. height) is equal to w ccx /4 (resp. h ccx /4) where w ccx (resp. h ccx ) is the width (resp. height) of the overlapping or touching connected component (4 is a determined experimentally). Since this zone is extracted from the initial document, it is cleaned by removing the small connected components.

To do it, the connected components are labeled and we keep only the connected component containing S p (see figure 5.e). After the pre-processing, the skeleton of the zone is extracted and an skeleton follow-up algorithm is applied using the descender follow-up starting point B p (the pixel that has the minimum y i in the zone) and the direction follow-up (right to left if x(B p ) > x(S p ) and left to right if x(B p ) < x(S p ), see figure 5.f).

Fig. 5. Separation of overlapping and touching connected components approach steps.

Step 3: Curve Angular Variance Estimation

The angular variance of each curve is estimated using the algorithm detailed in the section 3.

Step 4: Pixels Assignment

In the figure 5.g, there are two curves and three different pixels types (intersection point "by red", first connected component "by green" and second connected component "by blue"). This step consists in assigning each black pixel in the initial image (see figure 5.e) to its appropriate curve. To do it, the image is scanned pixel by pixel and the 48-connected pixels of each image pixel p i are regarded in the skeleton image. The closest branches pixel value is assigned to the initial image pixel (see figure 5.h). Finally, the pixels assigning is done at the initial document in order to obtain the final result (see figure 5.i).

Experimental Results and Discussion

The approach was applied to 100 handwritten Arabic documents belonging to the Tunisian National Library, National Library of Medicine in the USA, National

Library and Archives of Egypt that contain 640 overlapping and touching connected components. The tests were prepared after a manual indexing step of the overlapping and touching connected components of each document. Then, these components are clustered in 4 types (see section 2): 253 occurrences of type (a), 194 occurrences of (b), 117 occurrences of (c), 76 occurrences of (d) have been detected. The Table 2 describes the results for each type. The weighted mean of these results is equal to 96.88%. The 3.12% rate error is due to the intersection point detection algorithm because in some cases the overlapping/touching do not hold near the minima, and to the angular variance criterion because in some cases the minimum angular variance can occur for a false direction. Figure 6 illustrates the effectiveness of the algorithm on a sample of 12 representative connected components chosen from 640 occurrences.

Conclusion and Future Trends

An original method of separation overlapping and touching connected components in the adjacent text lines from the handwritten Arabic documents has been proposed in this paper. The proposed method is based on the Arabic calligraph where overlapping and touching is most frequently observed. The approach is armed by statistical informations about Arabic writing structures. Experiments showed the efficiency and the performance of our approach. The future step of this work is related to the segmentation of the lines into single words.

Fig. 1 .

 1 Fig. 1. Extract of a document representing some overlapping and touching lines.

  left descender (jïm , h . a , kha , 'ain , ghain ) causing the connecting lines (left or right indicates the descender starting, see figure 2.a). The connection in Arabic documents can happen in two cases: when the interlines spacing is small (see figure 2.b) or when we use a calligraph with big jambs (descenders) as Diwani (see figure 2.c).

Fig. 2 .

 2 Fig. 2. (a) The Arabic alphabet chart (arrow indicates the writing direction, source: [14]), (b) Connection is due to the small interlines spacing, (c) Overlapping/touching due to the script type (Diwani).

Fig. 3 .

 3 Fig. 3. Overlapping/touching connected components zones and descenders direction (rectangles represent the connection zones, right direction indicated by red arrow and the false by blue).

Fig. 4 .

 4 Fig. 4. (a) Example of Arabic overlapping connected components ("ra " overlaps "alif "), (b) Angles variation vector estimation algorithm.

1 . 1 .

 11 In the figure 5.f, the first touching components have V (C 1 ) = 538.2099 and V (C 2 ) = 754.2284. The C 1 having the minimum angular variance is the descender. The second overlapping components have V (C 1 ) = 1160.8, V (C 2 ) = 438.4 and V (C 3 ) = 1208. The C 2 having the minimum angular minimum variance is the descender.

Fig. 6 .

 6 Fig. 6. Samples of our results.

Table 1 .

 1 The

	Types		Terminal Letters	Overlapping/	Samples
						Touching Zones
	a	Top:	, , , ,	,	, , , ,
		Bottom:			, , , ,
	b	Top:			, , , ,
		Bottom:			, , , ,
	c	Top:			, , ,
		Bottom:			,	,
	d	Top:			, , , ,
		Bottom:

4 overlapping/touching types in the handwritten Arabic documents.

Table 2 .

 2 Results of the separation of overlapping and touching connected components approach.

	Overlapping/ Occurrences Connections Separations	Correctly
	touching types		missed	failed	separations rate %
	a	253	2	3	98.02%
	b	194	4	2	96.90%
	c	117	3	1	95.73%
	d	76	1	2	94.75%


N Ouwayed
email: nazih.ouwayed@loria.fr

A Belaïd
email: abelaid@loria.fr

F Auger

Cohen's Class Distributions for Skew Angle Estimation in Noisy Ancient Arabic Documents

This paper presents an adaptive method for the skew angle estimation of noisy handwritten Arabic documents using the energy distributions of Cohen's class. The presence of noise in raw document images can create local maxima which disturb the projection histogram analysis. To avoid this drawback, we propose to use Cohen's class distributions on the projection histogram profiles obtained using different projection angles. These distributions reduce the importance of these local maxima and are fitted to the nonstationary nature of these histogram profiles. The orientation of the document is given by the highest maximum. The proposed skew angle detection technique has been evaluated on 864 skewed documents. The results of each distribution are presented at the end of this paper.

INTRODUCTION

Ancient Arabic textual archives contain a heavy volume of handwritten documents that need to be scanned and indexed. Some of these documents can be skewed which may handicap their recognition. Figure 1 shows some examples stemmed from the database studied [1, 2, 3]. We are looking for a method that can detect this orientation, whatever the size of the document. The literature proposes some solutions for image document skew angle estimation. The projection techniques [START_REF] Pavlidis | Page segmentation and classification[END_REF] seem the most appropriate ones but need to be adapted to Arabic documents. In fact, in Arabic, the words are composed of PAWs (Parts of Arabic Words) which are almost vertical or oblique, distorting the line orientation calculation. Furthermore, the gaps between PAWs and words are very narrow, essentially in the case of handwritten texts (see figure 2.b). This prevents to apply techniques like nearest neighbors as in [START_REF] Pal | An improved document skew angle estimation technique[END_REF] because of the alignment absence, or techniques based on the Hough Transform [START_REF] Jiang | A fast approach to the detection and correction of skew documents[END_REF] because of the difficulty of locating voting points in the box bottoms. Sharif et al. [START_REF] Sharif | On skew estimation of persian/arabic printed documents[END_REF] proposed two projection techniques for printed Persian and Arabic documents, based on black and white line strips. As these methods fail in large skew angles, they propose a slope seeker algorithm based on the Hough transform. Sarfraz et al. [START_REF] Sarfraz | A novel approach for skew estimation of document images in ocr system[END_REF] used the Haar wavelet to decompose the image into sub-images at various level. In each level, they apply Principal Component Analysis(PCA) to estimate the orientation of the main axis (i.e. horizontal, vertical and diagonal). Although these techniques fit well to printed documents, they remain inadequate to handwritten documents, in which the interline distance is random and the skew angle can be large. E. Kavallieratou et al. [START_REF] Kavallieratou | Skew angle estimation in document processing using cohen's class distributions[END_REF] employed Cohen's class distributions on Latin documents. But no explanation was given on the relationship between the distributions properties and the results. We propose in this article to explore these properties and to find, thanks to them, the best distribution to use. This paper is organized as follows. In section 2, we present the projection histogram profile analysis and the orientation estimation principle. In section 3, the Cohen's class is briefly presented, considering its distributions and their properties. In section 4, we show the application of the Cohen's distributions to the skew angle estimation. We present some experimental results in section 5 and a conclusion and future trends of this work in section 6.

ORIENTATION ESTIMATION

The idea of the usual projection technique is to find the projection angle for which the number of peaks of the histogram profile is as close as possible to the number of lines. The document orientation will then be equal to that angle. As the line number is usually unknown, we traditionally base the projection analysis on the peak sharpness and the valley depth. The orientation angle corresponds to the projection that gives the maximum difference between peaks and valleys [START_REF] Akiyama | Automatic entry system for printed documents[END_REF][START_REF] Pavlidis | Page segmentation and classification[END_REF] (see figure 2.a with an angle equal to (0 • ) and where the high difference between peaks and valleys is representative to the three horizontal lines). But this method does not always yield the correct skew estimation because of line distortions and variabilities, as is usually the case in ancient Arabic documents.

TIME-FREQUENCY DISTRIBUTIONS

Traditional signal processing approaches of such as the Fourier transform cannot describe the signal variation over both time and frequency. The energetic time-frequency distributions go beyond by analyzing the "non-stationarity" of a signal and distribute the energy of a signal in a time and frequency plane.

According to [START_REF] Hlawatsch | Time-frequency analysis: concepts and methods[END_REF], the energy Ex of a signal x(t) has the following expression:

Ex = +∞ -∞ |x(t)| 2 dt = +∞ -∞ | x(f )| 2 df (1)
where x(f ) is the Fourier transform of the signal x(t). The value Ex is quadratic. Therefore, the time-frequency distributions should keep this property.

In 1966, Cohen [START_REF] Hlawatsch | Time-frequency analysis: concepts and methods[END_REF][START_REF] Cohen | Generalized phase-space distribution functions[END_REF] proved that a significant number of timefrequency distributions can be seen as particular cases of the following general expression:

Cx(t, f ) = +∞ -∞ +∞ -∞ φ r-d (τ, ξ)Ax(τ, ξ)e j2π(tξ-f τ ) dξdτ, (2)
where Ax(τ, ξ) is the ambiguity function defined by:

Ax(τ, ξ) = +∞ -∞ x(t + τ /2)x * (t -τ /2)e -j2πξt dt
The Cohen's class contains all the time-frequency distributions that are covariant under time-and frequency-shifts. The members of this class are identified by a particular kernel φ dD (τ, ξ), (expressed here in the delay-Doppler plane dD) which determines their theoretical properties and their practical readability. The properties related to the skew angle estimation problem are summarized in Table 1. For the problem considered here, we think that properties P1, P2, P3 and P4 are highly necessary, whereas properties P5, P6 and P7 may help to obtain accurate estimations.

APPLICATION OF THE COHEN'S DIS-TRIBUTIONS TO THE SKEW ANGLE ES-TIMATION 4.1 Justification of the proposed method

When computing the histogram profile of a document along one direction of projection, we obtain, if this direction is the real orientation of the document, a histogram in which each line leads to a clearly localized local maximum (see figure 2). Each block of the document leads in the projection histogram to a succession of periodic peaks and valleys, whose period is relatively constant. This periodic succession is delimited by the block size ("time" support) and oscillates at a frequency determined by the space width between the lines.

As all the pixels are accumulated in the same positions, the local maxima have higher energy levels than with other projection directions. This explains why we can estimate the orientation of a document by seeking the projection angle for which the time-frequency distribution localizes a large energy level on a small area of the time-frequency plane. For example, Fig. 4 shows the increase of the maximum of the Wigner-Ville distribution when the number of peaks and valleys increases and when the valleys become wider.

Implementation Details

To estimate the orientation angle, we use the analytic signal xa(t) of the centered projection profile x(t) of the document or of the selected area. The analytic signal is the signal x(t) without its negative frequencies. The profile x(t) is determined by projecting

Property Formula Explanation P1 Real-valued ∀t, f, Cx(t, f ) = C * x (t, f ), where C * x (t, f ) is the conjugate of Cx(t, f )
Allows to associate a real number to each point of the timefrequency plane and not a complex number: this reduces the amount of memory for the storage of the distribution and to find the highest value of a distribution (see figures 3.a and 3.b) P2

Translation invariance

∀t1, f1, y(t) = x(t -t1)e j2πf 1 t ⇒ Cy(t, f ) = Cx(t -t1, f -f1)
A simple shift of the text in the image will result in a shift of the time-frequency representation: this shows that the distribution is not sensitive to the text location in the document (see figure 3.b and 3.c) P3

Scale change covariance

∀a > 0, y(t) = a -1/2 x(t/a) ⇒ Cy(t, f ) = Cx(t/a, af )
An expansion or reduction of the document will result in an expansion or compression of his projection profile: this will result in a correct change of its energy distribution (see figure 3.b) P4

Energy conservation

+∞ -∞ +∞ -∞ Cx(t, f )dtdf = +∞ -∞ |x(t)| 2 dt
The energy of the projection profile is exactly distributed in the time-frequency plane P5 Positivity ∀x(t), ∀t, f, Cx(t, f ) ≥ 0 Enables us to more easily interpret the values of representation as energy measurements P6 Signal null value conservation

x(t0) = 0 ⇒ ∀f, Cx(t0, f ) = 0
Allows to get a null representation at all the "frequencies" at "instants" where the profile projection is zero: this correctly localizes the valleys in the projection profile (see figure 3.d) P7

Signal support conservation

if ∀t, |t| > T ⇒ x(t) = 0 then ∀t, |t| > T ⇒ Cx(t, f ) = 0

Allows to get a null time-frequency representation outside the range within which the projection profile has non-zero values

Table 1: Properties that a time-frequency distribution can satisfy and which are interesting for the skew angle estimation problem.

Distribution Kernel Properties P1 P2 P3 P4 P5 P6 P7 Wigner-Ville 1 x x x x x Pseudo Wigner-Ville h(τ ) x x x x Smoothed Pseudo Wigner-Ville h(τ ) g(ξ) x x x Margenau-Hill cos(πξτ ) x x x x x x Pseudo Margenau-Hill h(τ )cos(πξτ ) x x x x x Spectogram A * h (τ, ξ) x x x x Choi-Williams exp(-4π 2 ξ 2 τ 2 /σ) x x x x Born-Jordan sinc(πξτ ) x x x x x Zhao-Atlas-Marks h(τ ) |τ | sinc(πξτ ) x x x
Table 2: Some time-frequency distributions of the Cohen's class, their kernels and their properties. each document with a chosen orientation. To calculate all possible profiles, we turn the image around its center of gravity (which gives us a point deduced from the image content and not from its size and framing) and we choose the horizontal axis as an arbitray reference for the zero degree angle. Then, we compute a timefrequency representation for each projection profile. The angle corresponding to the profile with the highest maximum value of its time-frequency representation is chosen as the estimated angle of the document.

EXPERIMENTAL RESULTS AND DISCUS-SION

To study the effectiveness of our approach, we have experimented it on 864 Arabic handwritten documents. These documents have different sizes, contain several types of writing, layout (1 column, 2 columns), a mix of text and tables, etc. The experiments were prepared after a manual orientation of the documents into different angles ranging from -75 • to +90 • . The tests were carried out on a PC equipped with a microprocessor Pentium M 1.4 GHz and 1 GB of memory under Windows XP. The execution time is measured in seconds. It depends on the size of each document and the distribution. Table 3 (third column), shows that the precision obtained is very high, varying around 0.5 • .

As shown on Table 3, the Wigner-Ville distribution reaches the highest estimation rate (100%). The other distributions yield a lower estimation rate, either because they do not satisfy properties that are important for the skew angle estimation problem, such as the scale invariance property and the support conservation, because their localization of the signal components is not sufficiently precise to provide a skew angle estimation with the maximum of the representation, or because the parameters of these distributions are not fitted the the analysed histogram profiles. These parameters are

• the time smoothing window g(t);

• the frequency smoothing window h(τ );

• the width of the Choï-Williams kernel distribution σ.

To simplify the comparisons, all smoothing windows have been chosen of Kaiser-Bessel type [START_REF] Kaiser | On the use of the io-sinh window for spectrum analysis[END_REF]. The best results have been obtained when the length of the time smoothing window and the length of the frequency smoothing window are constant and respectively equal to 19 and 91 time samples. Table 3 also shows the results obtained with the projection profile analysis method recalled in section 2, which is classically used for handwritten documents. The skew angle estimated with the Wigner-Ville distribution is much better than the projection method one and moreover, it is faster.

CONCLUSION AND FUTURE WORK

We have proposed in this article an original approach which seeks to estimate the orientation of an Arabic document. Because of the local variation of the handwritten lines and because of the vertical and slant ligatures in the Arabic script, the classical methods based on nearest neighbours or on the Hough transform often fail. Hence, we used the time-frequency distributions of the projection profile for the angle determination. We first studied the Cohen's class distributions and examined their properties. We have chosen the Wigner-Ville distribution whose properties fit to the document analysis requirements. This distribution allows us to precisely determine the orientation angle by maximizing the signal energy. Unlike the other distributions, the Wigner-Ville distribution verifies two interesting properties: scale invariance and time support conservation. This method has been experimented on 864 skewed handwritten Arabic documents. The estimation rate varies depending on the characteristics of each distribution. The Wigner-Ville distribution gives the highest estimation rate which is equal to 100%. In a previous work [START_REF] Ouwayed | Multi-oriented text line extraction from handwritten arabic documents[END_REF], we used this approach for the analysis of multi-oriented Arabic documents. The distribution was applied on small windows and orientation zones were delimited by the local extension of similar orientation windows. We are going to improve this approach by testing it on more complex documents including different orientations. The next step will concern the effective line extraction exploiting the local orientation knowledge.

AKNOWLEGEMENTS

Figure 1 :

 1 Figure 1: Samples of skewed Arabic handwritten documents.

Figure 2 :

 2 Figure 2: Depth and sharpness of the histogram profile computed for projection angles of -30 • , 0 • and 30 • and for a document made of three handwritten Arabic lines(a); Orientation error provided by local PAWs in an Arabic horizontal line (b).

Figure 3 :

 3 Figure 3: This figure showing on some projection histogram profiles more or less sharp, the property of the Cohen's class distributions and especially those of the Wigner-Ville ((a),(b),(c)) and Margenau-Hill (d) (the signal x(t) used in (a) and (b) is equal to max(sin(2π t 64 ), 0).

Figure 4 :

 4 Figure 4: Examples of maximum value of the Wigner-Ville distribution obtained for different projection profiles.

Figure 5 :

 5 Figure 5: Intensity energy chart giving the Wigner-Ville distribution of the projection histogram profile of the document of the figure 1.a, by varying the projection angle by +1 • .

Fig. 5

 5 shows the highest values of the Wigner-Ville distribution (WVD) of the histogram profiles of the document shown on Fig. 1.a. The third column of Table 3 shows the skew angle of the document shown on Fig. 1.a. estimated with some Cohen's class distributions. The correct value is 15.4 • .

Table 3 :

 3 For a chosen set of Cohen's class distributions, estimated skew orientation angle for the document shown on Fig. 1.a, average computation time and average estimation rate obtained with 864 skewed documents.

	Pseudo Wigner-Ville	90	7.1	+13.1 •
	Smoothed Pseudo Wigner-Ville 96	6.9	+14.3 •
	Margenau-Hill	95	7.2	+13.7 •
	Pseudo Margenau-Hill	98	8.1	+15.1 •
	Spectrogram	90	7.9	+12.9 •
	Choi-Williams	97	7.6	+15.2 •
	Born-Jordan	87	7.8	+11.8 •
	Zhao-Atlas-Marks	92	8.5	+12.6 •
	Projection profile	93	6.4	+14.9 •

•

We wish to thank the libraries that provide these documents (Tunisian National Library [1], National Library of Medicine in the USA [2] and the National Library and Archives of Egypt [3]).


Distributed Gradient Optimization for Epidemic Routing: a preliminary Evaluation

Keywords: Delay tolerant networks, epidemic routing, online optimization, distributed gradient optimization

In this research report we address the problem of designing adaptive epidemic-style forwarding mechanisms for message delivery in Delay Tolerant Networks. Our approach is based on a new analytical framework for multi-agent optimization through distributed subgradient methods. We investigate how this framework can be adapted to the considered networking problem and we perform a preliminary evaluation, which shows promising results in terms of convergence speed.

Introduction

Delay Tolerant Networks (DTNs) are sparse and/or highly mobile wireless ad hoc networks where no continuous connectivity guarantee can be assumed [START_REF] Burleigh | Delay-tolerant networking : an approach to interplanetary internet[END_REF][START_REF] Pelusi | Opportunistic networking : data forwarding in disconnected mobile ad hoc networks[END_REF]. One central problem in DTNs is related to the routing of packets towards the intended destination. Protocols developed in the mobile ad hoc networks field, indeed, fail since a complete route to the destination may not exist most of the time. One common technique for overcoming such problem is to disseminate multiple copies of the message in the network, enhancing the probability that at least one of them will reach, within a suitable time-frame, the destination node [START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks : The multi-copy case[END_REF]. This is referred to as epidemic-style forwarding [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF]. Alike the spread of infectious diseases, each time a message-carrying node encounters a new node not having a copy thereof, it may infect this new node by passing on a message copy ; newly infected nodes, in turn, may behave similarly. The destination receives the message when it meets an infected node.

An unconstrained epidemic forwarding scheme (in which an infected node spreads messages to all nodes it encounters) is able to achieve minimum delivery delay at the expense of an increased use of resources such as buffer space, bandwidth, and transmission power. Variations of epidemic forwarding have been recently proposed in order to exploit the trade-off between delivery delay and resource consumption. This family includes, among others, K-hop schemes [START_REF] Groenevelt | Message delay in mobile ad hoc networks[END_REF], probabilistic forwarding [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF], and spray-and-wait [START_REF] Spyropoulos | Spray and wait : an efficient routing scheme for intermittently connected mobile networks[END_REF]. These schemes differ in their "infection process," i.e., the spreading of a message in network.

Depending on the specific application scenario, different performance metrics could be envisaged, such as the probability to successfully deliver a message to destination, the delivery time, the total energy consumption in the system or a combination of the previous ones. Optimal policies have been identified for specific metrics in restricted set of policies. For example [START_REF] Neglia | Optimal delay-power tradeoff in sparse delay tolerant networks : a preliminary study[END_REF] and [START_REF] Altman | Decentralized stochastic control of delay tolerant networks[END_REF] focus on 2-hop schemes (only the source can copy the message and infected nodes act as relays to the destination) and derive optimal configurations for the two following cases : 1) the source can select the maximum number of copies that minimizes a weighted sum of the delivery time and the energy consumption [START_REF] Neglia | Optimal delay-power tradeoff in sparse delay tolerant networks : a preliminary study[END_REF] ; 2) the source copies a message with a (time-dependent) probability to maximize the delivery probability under energy consumption constraints [START_REF] Altman | Decentralized stochastic control of delay tolerant networks[END_REF]. In both cases, parameters configuration depends on the specific network scenario, e.g., on the number of nodes in the system and on their mobility patterns. In many cases, these characteristics may not be known at system design and deployment time and may drastically change across time and space. Consider for instance a personal digital assistant (PDA) carried by a user in its daily activities. During the day, the PDA may travel at different speeds (e.g. from zero up to car speed), moving from highly crowded areas (supermarkets, classrooms, etc.) to sparse ones, with very different trajectories (straight along a highway or following a random walk from shop to shop) and different levels of power availability. Interestingly, [START_REF] Altman | Decentralized stochastic control of delay tolerant networks[END_REF] proposes also an algorithm based on stochastic approximation for online learning. Nevertheless the problem of deriving optimal forwarding policies for general optimization goals and in large sets of possible behaviours is mainly open.

For this reason, our interest is to develop online adaptive policies able to optimize generic performance metrics. A previous attempt in such direction has been carried on by some of the authors who have applied concepts and tools from the Genetic Algorithms (GAs) field. Each node employs a (potentially different) forwarding policy, which prescribes the operations to be undertaken when receiving a message destined to another node. Such a policy is described by an array of parameters called the genotype. Genotypes are associated with a fitness measure which, roughly speaking, indicates the ability of the current set of parameters to achieve good performance in the local environment. Fitness is evaluated using local information and feedback which is sent from the destination backwards. Some results have been presented in [START_REF] Alouf | Embedding evolution in Epidemic-Style forwarding[END_REF] and in [START_REF] Alouf | Autonomic information diffusion in intermittently connected networks[END_REF]. A criticism to this approach is that GAs (and evolutionary algorithms in general) are suited for problems with ill-behaved functions having multiple minima for which gradient based methods would fail. On the contrary, it seems natural to expect that network performance metrics of possible interest exhibit a more regular behaviour. For this reason, in this work, we start exploring how to implement a distributed gradient algorithm. Our approach is based on the analytical framework recently proposed in [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF] : the authors study a distributed computation model for optimizing a sum of convex objective functions corresponding to multiple agents. The method involves every agent minimizing its own objective function while exchanging information locally with other agents in the network over a time-varying topology. The contribution of this work is twofold : first, we show how this approach can be used to optimize routing in a DTN, and second, we perform a preliminary evaluation in terms of convergence speed and quality of the solution identified.

The report is organized as follows. Section 2 provides the required background on the distributed subgradient method proposed in [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF]. In Section 3, we show how this approach can be adapted to work in a DTN scenario and stress the key issues to be solved. Section 4 presents a preliminary evaluation of a case study and finally Section 5 concludes the report and illustrates future research directions.

Background on Distributed Gradient Methods

In [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF], the authors study a distributed computation model for optimizing a sum of convex objective functions corresponding to m agents. The method involves every agent minimizing a local convex cost function f i : R n → R while exchanging information locally with other agents in the network over a deterministically time-varying topology.

INRIA

Distributed Gradient Optimization for Epidemic Routing: a preliminary Evaluation5

The agents want to cooperatively solve the following unconstrained optimization problem : minimize

x∈R n F (x); F (x) := m i=1 f i (x). (1)
Let F * be the minimum value of F and S * be the optimal solution set, i.e., for all x in S * , F (x) = F * .

To solve (1), the distributed gradient method works on a time slot basis. At any point in time, each agent has available an estimate of an optimal solution of the problem [START_REF] Burleigh | Delay-tolerant networking : an approach to interplanetary internet[END_REF]. During a time slot, an agent can communicate its estimate to a subset of the other agents. We denote by xi (k) the estimate maintained by agent i at the k-th slot.

At the end of a time slot, each agent updates its estimate according to the following relation :

xi (k + 1) = m j=1 a i j (k)x j (k) -ζd i (k), (2)
where a i (k) is an m-length vector of non-negative weights such that

m j=1 a i j = 1, ζ > 0 is a tunable step size and d i (k) is a subgradient of the function f i at the point xi (k). 1 In this report, we consider d i (k) to be the gradient of the function f i , i.e., d i (k) = ∇f i (x)| x=x i (k)
. Hence, the last addend in (2) acts in the direction of minimizing the function f i (not F ). At the same time, the first sum corresponds to averaging the estimate of all the other nodes, similarly to what is done in consensus protocols. In order to present the main results of [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF] in a simple form, we consider that agent i sets the weights in the following way : if the estimate of agent j is available at agent i = j during time slot k then a i j (k) = 1/m, otherwise a i j (k) = 0 ; last, a i i (k) = 1j =i a i j (k). In [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF], it is shown that the update rule (2) leads the estimate xi (k) to converge near the optimal solution set if the following assumptions are satisfied :

-Connectivity : The information of each agent influences the information of any other agent infinitely often (eventually through a sequence of intermediate agents). Formally, consider the graph (V, E ∞ ), where V is the set of agents and E ∞ is the set of links such that link (i, j) exists if and only if i and j communicate directly infinitely often. Then, the connectivity assumption corresponds to the graph (V, E ∞ ) being connected. -Bounded intercommunication interval : The time between two consecutive communications between two agents that communicate infinitely often is upper bounded. Formally, there exists a positive integer B such that for every (i, j) ∈ E ∞ , i and j exchange information status at least once every B consecutive time slots. -Bounded gradients : There exists L such that ||∇f i || ≤ L. Under the above assumptions, the authors of [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF] prove that

F (x i (k)) -F * ≤ m dist 2 (y(0), S * ) 2ζk + ζL 2 C(m), (3)
where

x i (k) := 1 k k-1 h=0
xi (h) is the time average vector, y(0

) := 1 m m i=1
xi (0) is the average initial estimate, dist(y(0), S * ) denotes the 2-norm distance between the vector y(0) and the set S * , and

C(m) = 1 2 + 6m + + 6m 2 (1 + m (m-1)B )/(1 -1/m (m-1)B ) 1 -1 -1/m (m-1)B 1 (m-1)B .
Inequality (3) states that, at any time slot k, the distance between the function F evaluated at x i (k) and its minimum is bounded by the sum of two terms. The first of these terms converges to zero as k goes to infinity, but the second one is constant and can be reduced only by decreasing the step size ζ. We observe that the bound in (3) is not very tight, in fact C(m) is larger than m (m-1)B which is very large already for a system with tens of nodes. This observation also justifies our numerical analysis in Section 4.

Application to Epidemic Routing

In this section, we explore how the analytical framework presented in the previous section can be adapted to optimize routing performance metrics in a DTN.

Consider a DTN with m nodes. Each of them implements its own forwarding policy that can be different from node to node, e.g., a node could implement a K-hop scheme, i.e., it would not forward a message that has already traveled more than K hops, while another one could implement a probabilistic scheme, where each message is forwarded with probability p. Even nodes applying the same kind of policy could have different values of the parameters.

Let us denote z i ∈ R si the array of s i parameters characterizing the policy of node i. Routing performance in the network is determined by the vector

z = (z 1 , z 2 • • • , z m ) ∈ R n , where n = m
i=1 s i , which we refer to as the system status. It will prove useful to simply identify the component of a vector in R n which corresponds to the parameters of node i's policy. Hence, we introduce the notation [x] i to refer to the following subvector of x : (x li+1 , x li+2 , • • • , x li+si ), with l i = i-1 j=1 s j . Using this notation, we have [z] i = z i . We consider that node i can change its parameters at runtime in order to optimize a global performance metric. For simplicity, we assume that such changes occur synchronously at all nodes every T seconds, so that the system can be modeled as a discrete-time system where the slot length is T . Let z(k) denote the set of parameters used during the time slot k.

We next show that there is a large class of interesting performance metrics that can be mapped to the problem [START_REF] Burleigh | Delay-tolerant networking : an approach to interplanetary internet[END_REF]. Most of the performance metrics are related to nodes (e.g., energy consumption at each node) or to messages (e.g., delivery time, delivery probability or energy consumption per message). In either case, the performance metrics can naturally be expressed as a sum of local cost functions relative to each node. Let us develop a specific example (that we will consider in Section 4 as a case study). Our target is to minimize a weighted sum of the message delivery time T D and the number of copies C done for each message, the latter number being roughly proportional to the energy consumption needed to deliver the message. Such quantities are random variables because they depend on the underlying node random mobilities. Hence, we can define our performance metric as :

F (z) = E[T D + γC], (4)

INRIA

where the parameter γ can be interpreted as the time-equivalent cost of a copy, and we put in evidence that F depends on all the policy parameters of all the nodes in the network (it depends also on the traffic matrix, but we assume that it is given). The optimization problem we are interested in is to find a parameter vector z that minimizes F . We observe that (4) can be rewritten as

F (z) = m i=1 E λ i λ T T D,i + µ i µ T γC i , (5)
where T D,i is the expected delivery time of a packet generated at node i, C i is the expected number of copies done by node i for a generic message (generated or not at node i), λ i is the message generation rate at node i (message for which node i is the source), µ i is the message arrival rate at node i (accounting for messages generated at or forwarded to node i), λ T = m i=1 λ i and µ T = m i=1 µ i . According to [START_REF] Groenevelt | Message delay in mobile ad hoc networks[END_REF], F is the sum of functions f i , each of which is relative to a specific node :

f i (z) = E λ i λ T T D,i + µ i µ T γC i . (6)
Even if the optimization problem looks similar to the one stated in (1), there are two capital differences :

1. f i is not in general convex, 2. a closed form expression of f i (nor of ∇f i ) is not in general available at node i. Convexity in problem (1) guarantees the absence of local minima. Having nonconvex f i no longer assures that ; nevertheless, the algorithm would in any case converge to a local minimum that may have acceptable performance.

The second point requires a more thorough discussion. Node i cannot evaluate f i at a generic point z, but, at the end of the k-th time slot, it can estimate f i (z(k)) where z(k) is the set of policy parameters used by nodes during time slot k. 2 For instance, in order to have an estimate of E[T D,i ], node i can average the delivery times of the messages it has generated during the slot. This means that a possibly noisy estimate of f i (z(k)) can be available. Evaluating the gradient is more complex. We believe that derivative-free optimization techniques [START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF] can be introduced in order to rely only on the estimations of f i at each node. We do not address this issue in this work, but assume from now on that the gradient of f i at a given point can be evaluated.

Relying on measurements has another implication for the original algorithm (2). In fact, according to [START_REF] Pelusi | Opportunistic networking : data forwarding in disconnected mobile ad hoc networks[END_REF], each node should be able to evaluate the gradient in a solution estimate xi (k) that is potentially different for each node. On the contrary, in a real DTN setting, every node may only have an estimation of its own function f i evaluated at the same point z(k). Estimating the value of f i (or of ∇f i ) at different points appears difficult. We discuss more this issue in the next paragraph.

Let us consider what would an immediate implementation of (2) be, referring to the following set of equations :

z i (k) = [x i (k)] i , (7a) xi
(k + 1) = m j=1 a i j (k)x j (k) -ζ∇f i (ẑ i (k)). ( 7b
)
At the end of the (k -1)-st time slot, node i has available a new estimate of an optimal solution xi (k). It can extract from this estimate the set of parameters z i (k) to use during the k-th time slot (cf. (7a)). We observe that the system status is

z(k) = (z 1 (k), z 2 (k), • • • , z m (k)
) and it is unknown to node i, but for the component z i (k). During the k-th time slot node i spreads its current estimate xi (k) and collects other nodes' estimates. If node i has collected all estimates xj (k), with j = i, it can exactly reconstruct z(k), but in general only a subset of estimates is available so that it can only produce an estimate of system status denoted ẑi (k). 3 Once such estimate has been obtained, the gradient ∇f i can be evaluated at ẑi (k) yielding a new estimate of an optimal solution (cf. (7b)).

We note two problems in the above algorithm. First, it is not clear how ẑi (k) should be produced. In fact if node i has not met node j, then it has no information about z j (k). Second, letting each node select its policy parameters from its own solution estimate xi (k) leads to a biased system status. In fact, ∇f i contributes to changing all the components of the vector xi (k + 1) and subvectors of ∇f i relative to node i's policy and to other nodes' policies have different directions in general. 4 However, only the i-th component of xi (k + 1) will effectively be used (by node i) ; thus, ∇f i only affects [z(k + 1)] i .

In order to solve these two issues we have changed the algorithm (7) as follows :

xi (k + 1) = ẑi (k) -ζ∇f i (ẑ i (k)), (8a) ẑi
(k + 1) = m j=1 a i j (k)x j (k + 1), ( 8b
)
z i (k + 1) = [ẑ i (k + 1)] i . (8c)
In this new procedure a time slot is split into two parts. Since the beginning of the k-th time slot the node has an estimate of the current system status ẑi (k).

During the first part of the time slot, it estimates ∇f i (ẑ i (k)). At the end of the first part, it will produce a new estimate of the optimal solution by correcting ẑi (k), taking into account only the gradient ∇f i (cf. (8a)). The second part of the time slot is then devoted to spreading such estimate and collecting other nodes' estimates. Then, an estimate of the system status in slot k + 1, ẑi (k + 1), is obtained by averaging optimal solution estimates (cf. (8b)). This estimate determines also the policy parameters used by node i in slot k + 1 (cf. (8c)). We observe that the accuracy of status estimation ẑi (k) increases as nodes communication opportunities increase. In particular, if every node can collect estimates of every other node in the second part of time slot k, then a i j (k) = 1/m for any i and j and it follows that ẑi (k + 1) = z(k + 1) for any i. Hence all nodes have the same estimate of the vector of parameters used in the system during the slot k + 1. We believe results similar to those proved in [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF] for (2), and in particular bounds like (3), also hold for our variant ( 8), but we currently do not 3. Note the difference between ẑi (k), the estimate of status z(k) produced by node i, and z i (k), the vector of parameters used by node i and a subvector of z(k).

4. For example, in a completely symmetric scenario, nodes will have the same type of policy and any two nodes can exchange their policy vectors without affecting the total cost F . More formally, F (z 1 , z 2 , • • • , zm) is invariant to permutations of z i . For x * ∈ S * , we naturally have ∇F (x * ) = 0 and this implies, due to the symmetry, that [∇f i (x * )] i = -(m -1)[∇f i (x * )] j for j = i. The corrections introduced by f i have opposite directions.

INRIA

Distributed Gradient Optimization for Epidemic Routing: a preliminary Evaluation9

set α β γ δ ǫ ζ λ i m A 0.01 1 10 1 0.1 3.35e -5
1 ∀i 20 B 0.02 1 10 1 0.1 10 -4 → 0.5 1 ∀i 10 Table 1 -Parameters settings have a proof. For the particular case when all estimates are available at every nodes in every time slot, then it can be proved that (8) reduces to a distributed implementation of a classic gradient method, so that all standard convergence results apply. We will refer to this case as the global knowledge scenario.

A Case Study

In this section we perform a preliminary numerical evaluation of the algorithm (8) for cost function

F (x) = E[T D + γC].
In particular, we are interested to investigate if the algorithm converges, how much time is required and how good is the final selected operation point.

We consider a DTN with m mobile nodes, all of them implementing probabilistic forwarding with a different probability value : p i (k) is the value used by node i during slot k. The system status vector during the k-th slot is

z = p = (p 1 (k), p 2 (k), • • • p m (k)) ∈ R m .
We assume a global knowledge scenario.

For our purpose we have considered the following approximation for the local cost function f i () :

f i (p) = λ i p i + α j =i p j + ι + γ 1 -e -βpi λ i δ + ǫλ -i , (9)
where λ -i = j =i λ j . In fact, for opportune values of the parameters α, β, γ, ǫ and ι, this function can produce the same qualitative behaviour of our cost function. For example Fig. 1 shows contour plots for the total cost F = f i for a network with 100 nodes, where half of them adopt probability p1 and the other adopt probability p2. Values in Fig. 1(a) have been obtained by simulations5 , while those in Fig. 1(b) have been obtained through [START_REF] Altman | Decentralized stochastic control of delay tolerant networks[END_REF] with an appropriate choice of the parameters. Unless otherwise specified, results in this report have been obtained for one of the two sets of parameters specified in Table 4. The ζ value in set A has been selected inversely proportional to the maximum gradient of the function F (p). This choice prevents algorithm oscillations. In set B we explore a large range of values for parameter ζ. Fig. 2 shows a temporal evolution of the cost function for the parameter set A. After 10 5 iterations p(k) converges to a homogeneous vector (p i ≈ 0.3241 ∀i) and the value of the total cost is F ≈ 112.6. We conducted different experiments changing the initial vector p(0) but the algorithm has always converged to the same value. Moreover by sampling directly the function F (p) it seems that the algorithm has correctly identified the global minimum. For different values of α, e.g. for α = 0.1, the function has multiple local minima, in particular the set of global minima seems to be the set of all the heterogeneous vector p, where 5 components have value equal to 1 and the others equal to zero. Most of the time the algorithm has been converging to one of these equivalent configurations. In a few cases it has converged to a different local minimum.

The order of magnitude of the convergence time in the above example is around 10 5 iterations, that is probably unacceptable in a real implementation. In fact, during each iteration, a node has to estimate ∇f i for the current setting and this can require the delivery of many messages in order to have acceptable Figure 3 shows the convergence time starting from a given initial system status z(0) for different values of the parameter ζ. The convergence time is evaluated as the number of iterations of (8) until the value of each component of ẑ(k) does not change more than 10 -15 (Matlab floating point precision). Whenever convergence has been reached, the final value of F (z) -say it F stophas been equal to 56.53, which seems to be the global minimum of the function (again by sampling directly the function F ). Spikes for ζ > 0.2 correspond to ζ values for which the algorithm does not converge by 10 7 iterations (we stop calculations when such iteration number is reached). This is the case for all the values larger than 0.43. Analyzing some of these time series, it appears that z(k) reaches a periodic orbit. In any case, if we average the last 10 values of F (z) we obtain again 56.53. This means that such periodic orbits are very close to It is interesting to observe the behaviour of the convergence time if we filter away the spikes. As ζ increases, the convergence time first decreases and then increases (for ζ > 0.31). This can be explained as follows. There are two phases that can be in general identified in a sequence z(k) that converges to z * . In the first phase, z(k) moves more or less in the same direction approaching z * , then it start bouncing around z * until it does not fall in the interval of values that are considered equivalent to z * . As ζ increases, the length of the first phase decreases (less jumps are needed to arrive close to z * ), but, on the other side the length of the second phase increases (more jumps are needed to fall exactly in the interval). Finally, we observe that under the best setting, only 30 iterations are needed to reach the optimal configuration.

The convergence time can be further reduced if we sacrifice the accuracy of the solution. In Figure 4 the algorithm is stopped once F (z(k)) falls below F = 56.62. This value has been calculated as F = F * +0.01|F -F * |, where F * = 56.3 is the minimum of the function and F is its average value 6 . Figure 4(a) shows a reduction of one order of magnitude of the convergence time ; in some cases Finally, we wanted to study how the convergence time scales with the number of nodes m. Being that it is not easy to select the optimal value of ζ for each m and performance are very sensitive to such value, we have considered a variant of (8a), where at each step the correction to the status vector has a constant module equal to φ. This is achieved by replacing Eq. (8a) with xi (k + 1) = ẑi (k) -φ ∇f i (ẑ i (k)) || j ∇f j (ẑ j (k))|| . (10a)

Figure 5 shows the convergence time until F (z(k)) < F for φ = 0.017 . Interestingly, the convergence time appears to scale less then linearly with the number of nodes.

Conclusions

In this report we have proposed to use the new analytical framework for multi-agent optimization proposed in [START_REF] Nedic | Distributed subgradient methods for Multi-Agent optimization[END_REF] in order to optimize routing in Delay Tolerant Networks. In Section 3, we have pointed out some issues to be addressed in order to apply this framework in a realistic case where no analytical expression is available for the function to optimize nor for its derivatives, but estimates can be obtained from measurements. We have changed the original algorithm in order to partially addresses these issues, but further research is needed in order to complement the framework with derivative-free optimization techniques. The preliminary evaluation in Section 4 shows promising results. The convergence of the algorithm does not seem to be significantly dependent on the gradient step size ζ and a careful tuning of such value allows to achieve practically useful convergence time values. Finally, the algorithm appears to scale well with the number of nodes.

Figure 1 -

 1 Figure 1 -Total cost F (p) when half of the nodes adopt probability p1 and half adopt probability p2

FFigure 2 Figure 3 -

 23 Figure 2 -Convergence time plot

Figure 4 -

 4 Figure 4 -Convergence to an interval

6 .Figure 5 -

 65 Figure 5 -Convergence time vs nodes number

Figure 4 (

 4 b) shows the corresponding loss of accuracy (remember that the minimum is F * = 56.3).

RR n°7016

By definition of a subgradient, the vectord i (k) satisfies d i (k)(x -xi (k)) ≤ f i (x)f i (x i (k)) for any x in R n . RR n°7016

In reality, as we discuss in the following of this section, node i does not know in general the system status z(k), but it has an estimate ẑi (k).RR n°7016

The complete description of the network setting (mobility model, network area, transmission range, message generation process . . .) can be found in Section 4.2 of[START_REF] Alouf | Autonomic information diffusion in intermittently connected networks[END_REF]. For the purpose of such qualitative comparison, we thought it was not needed to provide a complete description.RR n°7016

Note that F has to be evaluated separately for each m. In fact the function F depends on m, so that both minimum and average values changes as m change.RR n°7016

Neglia & et al.