Piyush Harsh
email: piyush.harsh@inria.fr

Yvon Jegou
email: yvon.jegou@inria.fr

Roberto G Cascella
email: roberto.cascella@inria.fr

Christine Morin
email: christine.morin@inria.fr

Contrail Virtual Execution Platform Challenges in Being Part of a Cloud Federation

Cloud computing is quickly defining the computing paradigm in the modern networked age. Users can run their large computations online using cloud services at a fraction of the cost compared to setting their own data centers. Clearly cloud computing offers many advantages, and yet many large organizations including governments, financial sector, and health care sector are reluctant in transitioning to cloud computing. Contrail project will address the major concerns behind this reluctance namely mistrust in cloud platforms, lack of Service Level Agreements (SLAs) and Quality of Protection (QoP) of data. Contrail will provide a federation layer support for bringing a multitude of cloud providers, both private and public, together. This will allow multi-tenancy and cloudbursting capability to end user cloud applications while supporting SLAs and QoP agreements desired by several privacy aware sectors including governments, banks, health care providers to name a few. This paper describes the novel features we are building into the Contrail Virtual Execution Platform (VEP) that will be closely interfaced with the IaaS layer of cloud providers. VEP upgrades the supported cloud providers and brings trust in cloud computing by adding SLAs and QoP features missing at typical IaaS layer. Further this paper outlines challenges faced in being part of a large federation and how VEP will address some of those.

Introduction

Cloud offerings are becoming more mature with increasingly sophisticated services available to the consumers. End users and corporations have tools available today that enable them to configure and operate their own private cloud services. These tools are available as commercial products, e.g., VMWare's vCloud [START_REF]VMware vCloud[END_REF],

as well as open source IaaS alternatives such as OpenNebula [START_REF] Opennebula | The Open Source Toolkit for Cloud Computing[END_REF] and OpenStack [START_REF]OpenStack.org -Open source software for building private and public clouds[END_REF]. In addition, there are public clouds that operate on pay-as-you-go model such as Amazon's EC2 [START_REF]Amazon Elastic Compute Cloud (Amazon EC2)[END_REF], Microsoft's Azure [START_REF]Microsoft Azure[END_REF], and Google AppEngine [START_REF]Google App Engine[END_REF] into which consumers can launch their applications and services as needed.

The above scenario is definitely a huge improvement from traditional data center models of last decade. Even though clouds offer much better price/performance ratio over non-virtualized environments, the true power of cloud computing can only be achieved with seamless federation among different cloud technologies.

A true cloud federation will bring both private and public clouds under the umbrella of one federation where users will have the option to deploy services using resources of multiple providers. The federation will present to the user uniform API/billing/monitoring features regardless of the nature of actual cloud service providers. Moreover, any organization can become part of this federation being both a cloud provider, when its IT infrastructure is not used at its maximal capacity, and a cloud customer in periods of peak activity. Resources that belong to different operators can be integrated into a single homogeneous federated cloud, shown in Figure 1, that users can access seamlessly.

The Contrail project (www.contrail-project.eu) aims to achieve these goals by developing an integrated approach to virtualization, offering Infrastructure as a Service (IaaS), services for federating IaaS clouds, and Platform as a Service (PaaS) on top of federated clouds. This calls for the deployment of a transparent, trusted, and reliable Contrail federation with operations governed by Service Level Agreements (SLAs) providing support for strong Quality of Protection (QoP) and authentication.

No cloud implementation, commercial or open source, currently implements all features to be supported by Contrail: federation, IaaS as well as PaaS, security, quality of service and protection enforced by service level agreements. Open source cloud platforms such as OpenStack [START_REF]OpenStack.org -Open source software for building private and public clouds[END_REF], Nimbus [START_REF]NIMBUS[END_REF] or OpenNebula [START_REF] Opennebula | The Open Source Toolkit for Cloud Computing[END_REF] only support the IaaS layer with no quality of service and protection guarantees. However, some of these platforms such as OpenNebula partially support cloud federation.

Full PaaS support is provided by some commercial products such as VMware vCloud T M [START_REF]VMware vCloud[END_REF] through the OVF distributed application open format [10]. But these platforms are currently limited to private cloud management only.

A Contrail federation integrates both private and public clouds under a common umbrella. User identities, data, and resources are interoperable within the federation, thanks to common supports for authentication and authorization, and to common policy definition, monitoring, and enforcing mechanisms (SLA, QoP, etc.), as well as to a common economic model [START_REF] Consortium | Requirements on Federation Management, Identity and Policy Management in Federations[END_REF].

The way the Contrail federation is conceived and its open source deployment nature will enable seamless access to provider resources, avoiding potential vendor lock-in for the end users. These users can now deploy their distributed applications on demand on different providers by negotiating resources with the federation, which will choose the best providers based on the application requirements.

In such a scenario, Contrail technology is able to satisfy the user needs for the deployment of elastic and salable applications guaranteeing performance dependability. The run time performance of the application can scale with the number of assigned resources, the user only needs to specify the desired perfor-mance level and the Contrail's automatic provisioning system can add resources on demand during the execution of the application in order to guarantee the desired performance (thus providing elasticity).

A challenging aspect of Contrail is the management of computing resources to guarantee this performance dependability and QoS of active virtual execution platforms. Indeed, cloud providers might have different efficiency policies given that the individual resources being contributed to this federated cloud will be highly heterogeneous in their hardware configuration and system-level organization, thus making their interoperability challenging.

The support for efficient cooperation and resource sharing within cloud federation is critical for the Contrail technology. This is achieved through Contrail Virtual Execution Platform (VEP), an open source technology implementing standards that exploits resource virtualization to provide virtualized distributed infrastructures for deployment of end-user applications independently from the underlying platform. VEP operates above IaaS layer as shown in the figure 1. In Contrail, each cloud provider will run a copy of VEP software which in turn will seamlessly integrate its resources with the Contrail federation.

VEP offers reliable application deployment platform that is resilient to operational failures and which supports secure management of user data with a strong guarantee for QoS. These requirements are critical to make the provider resources trustworthy so that users can obtain performance guarantees of their application, bring trust in cloud computing solutions making them suitable to run the users' businesses safely.

This paper presents the detailed information on VEP, which is one of the components of Contrail service stack deployed at the cloud resource providers end in order to seamlessly integrate the resources under Contrail federation.

The remainder of this paper is organized as follows -section 2 outlines the key challenges inherent in a large cloud federation, section 3 describes the role of VEP in cloud computing, section 4 describes the components and the design rationale of the Contrail VEP development effort, and finally section 5 describes the Contrail progress report, VEP development road map and recap of important contribution and key points presented in this paper.

Challenges of a large Federation

In a federation many independent members operate together governed by the agreed upon federation laws. Just like in a society where a federation is successful only if the individual members operate properly, the same set of challenges and opportunities exist in a federated cloud. In this section we will list few major issues that may arise in a federation of clouds. Later on we will see how VEP helps address some of these concerns.

Authenticity of reported statistics

An end user of a federation of clouds may not know a priori which provider her application will run on. The user agrees to pay the resources used by her application and in turn may require some form of validation of the reported resource usage. The provider may fudge the reported statistics in order to fleece the end users. It would be the task of the federation to ensure such a case does not arise. Clear code of conduct and penalties for violation must be defined. Even then, the enforcement could be problematic. Surprise audits of provider logs by federation officials could be one deterrent against frauds by providers. But, the logs themselves may be modified. Fool-proof implementation of anti-fraud measures may be impossible to achieve. Further, for a successful federation, the terms of participation by individual provider must not be too stifling and must not favor large providers against small providers. Finding the correct participation terms and condition balance may prove a key for the success of the federation and yet this may be the most difficult balance to achieve.

Verification of SLA adherence

Whenever there is a contract agreed between two parties, the contract enforcement becomes a legally binding obligation. Service Level Agreements (SLAs) in the context of cloud computing could contain agreements on the operating environment and placement restrictions of virtual machines (VMs) at the provider's location. An example SLA object could contain condition that some VMs in an application must not be placed on the same cluster rack as others. There might be CPU load conditions, memory requirements to name a few SLA parameters that could be present.

In a large federation where negotiated SLAs are supported between the user and the provider, the verification of the SLA contract adherence could prove to be challenging. If the user deploys her own VMs as part of the application, the user could embed her own verification code to periodically check if the execution environment is within the negotiated SLA parameters or not. The provider must maintain adequate logs for auditing if need arises.

Typically, initial SLA adherence is not a major issue because the provider checks for locally available resources before accepting an OVF and corresponding SLA object for provisioning. If adequate resources are not available at deployment stage, the SLA contract and OVFs are rejected. Ideally, such rejection should take place at the federation level itself before the deployment request reaches a provider. But the SLA enforcements for dynamic characteristics such as CPU usage should best be done by SLA enforcement agent based on periodic monitored data.

Scalability of interface APIs

A single private cloud operator if operating by itself may not have huge customer base, but becoming part of a federation could suddenly change that. The provider APIs throughput that were once sufficient to deal with influx of requests from non-federation customers may prove a serious bottleneck if not properly provisioned for the large federations. As an example, if the provider supports REST interfaces, it would be advisable to stress test the REST APIs and check for scalability and other issues of being part of a large cloud federation. In Contrail, since VEP will be at the interface between the provider and the federation layer, all federation request will first come at VEP and therefore the VEP REST and other APIs will be stress tested for sudden influxes from a large federation customer base.

Authorization/Authentication nightmare

Authorization and authentication are required whenever a provider resource needs to be accessed. Primarily it is required to keep track of resource usage for billing and accounting purposes, but also for keeping the compute and storage resources secure from malicious access. Private providers can easily maintain user accounts for authentication/authorization of their users. But once being part of a larger federation, it is not possible to keep account details of all possible users. The provider now must support means to allow resource access to federation users and at the same time keep at bay the malicious users.

One solution is to adopt a two-tier approach and keep the local authentication system intact for the non-federation users, and incorporate a federation authentication module in order to be able to validate the federation users' credentials before allowing access to local resources to federation users.

Other solution could be to elevate all local users as federation users, incorporate local accounts into the federation and provide all local users their new federation account details. But in this approach, the provider risks to loose the business of local users to competing providers under the federation while gaining the simplicity of one unified authentication mechanism.

Regardless of what solution one adopts, there are bound to be headaches in the integration process with respect to users' authentication and authorization with the (likely heterogeneous) providers in a large cloud federation.

Issue of trust in the federation

A federation of cloud providers brings several disparate cloud providers under one umbrella. Every cloud provider has different guiding principles and motives. The issue of trust in the federation is very important for proper operation of the system. The cloud providers must trust the federation. They have certain expectations from the federation, they expect the federation to properly filter out malicious users, they expect the federation to be honest in its accounting and billing practices. In the similar manner, the federation expects the participating cloud providers to adhere to a minimum code of conduct, be truthful in reporting resource usage, properly honor any negotiated SLA contracts, etc. The federation and cloud providers can both maintain some sort of trustworthiness rating system. It need not be uniform across all participating parties, each provider can adopt any suitable rating system (or not).

Need for VEP in cloud computing

With the growing importance of cloud based services in the computing of tomorrow, it is only a matter of time when there will be a real need for merging disparate IaaS platforms in order to support increasingly complex applications of the future.

The Virtual Execution Platform (VEP) could provide that aggregating glue for bringing different cloud platforms under one umbrella. The standard APIs exported by the VEP software would allow other developers to quickly and easily develop tools for making their own federated platforms tuned for specific tasks that other federations including Contrail may not support.

There are several open source tools already available for accessing public clouds (Amazon EC2), integrating such tools together with VEP would allow quick and easy solution for bringing public and private clouds together. Thus a well designed VEP solution could usher in the next wave of cloud research and open up new vistas for cloud innovations. Keeping this motivation for developing a quality VEP, let us next look at Contrail's VEP design in detail.

Contrail Virtual Execution Platform

Virtual Execution Platform (VEP) is a Contrail service that sits just above IaaS layer at the service provider end of the Contrail cloud federation. Some major design goals were kept in mind while designing the VEP architecture. Support for open virtualization standards including Open Virtualization Format (OVF) has been one of the major requirement. Scalability of the API interface in order to support potentially large customer base, interoperability with various open IaaS technologies in order to bring several kinds of cloud providers under the Contrail umbrella, and providing support for elasticity in accordance with the negotiated SLAs have been other major requirements that VEP will satisfy.

It will have selectable built in drivers for various open source IaaS platforms such as OpenNebula and OpenStack. The VEP layer will integrate clouds composed using different technologies under the ambit of Contrail federation. VEP will be very closely integrated with the IaaS layer and will expose uniform APIs to higher layers in the Contrail architecture. It will enable seamless deployment of OVF applications over any underlying supported cloud platform.

In case the federation module suspects that none of the participating Contrail cloud providers can satisfy a user's application resource requirements, it may enable part-deployment of the appliance over public clouds such as Amazon EC2 (cloud-bursting) using user credentials for such public clouds. This capability will be handled by the federation layer and not VEP directly.

Since support for Service Level Agreements (SLAs) and providing Quality of Protection (QoP) to end users is a major feature that Contrail aims to provide, the VEP layer has also been designed keeping the larger Contrail requirements in the picture. The following subsections describe major VEP components and supported features in some detail.

OVF deployment subsystem

Open Virtualization Format (OVF) [10] is an open standard that is used to compose virtual applications. It allows inclusion of multiple VM templates, allows description of interconnect between VMs, individual VM's contextualization to name a few features provided by the OVF standard. It has been developed by the Distributed Management Task Force (DMTF) [3]. It is an up-and-coming standard with increasing vendor support.

VEP will provide full support for OVF v 1.1 standard [START_REF] Crosby | Open Virtualization Format Specification[END_REF]. The support for OVF in VEP will enable deployment of virtual applications described in OVF XML document over supported IaaS platforms regardless of their native support for OVFs.

OVF deployment subsystem in VEP is responsible for deploying user appliances described within OVF XML document. Figure 2 shows the simplified design of the VEP's OVF deployment module. The user's OVF file is received from the federation layer using REST protocol (refer figure 2 subcomponent a). The user's credentials and authentication parameters are sent as part of HTTP headers in the Contrail REST scheme. Once the request for OVF deployment has been verified, the OVF document along with the corresponding SLA object is sent to the OVF deployment subsystem of VEP stack (refer figure 2 subcomponent b).

Once the OVF document and the corresponding SLA object is received at the VEP layer, the OVF document is validated for correctness against DMTF OVF standard schema document (currently VEP supports OVF v 1.1)(refer figure 2 subcomponent c). If the OVF document fails the validation process, the deployment effort is terminated and a suitable response is reported to the federation layer.

Upon successful validation, the OVF document is parsed (refer figure 2 components including VM elements, network elements etc. are then linked to their corresponding SLA contracts deconstructed from the SLA object. These linked elements are then used as input in the IaaS translation function which, depending on the type of IaaS environment, generates the template/deployment files for the underlying IaaS platform. For the initial release, VEP aims to provide support for OpenNebula IaaS clouds (refer figure 2 subcomponent f). Later on support for other open source cloud technologies will be developed.

If a virtual machine is stored at a remote location, the OVF deployment subsystem has modules for authenticated remote file transfer (refer figure 2 subcomponent e). The remotely hosted resources (VMs) will be transferred onto the cloud provider's shared file system before the actual virtual appliance deployment takes place at the cloud provider. The Contrail project will incorporate a Global Autonomous File System (GAFS) based on the XtreemOS project. The users' virtual machine image files will be hosted at remote GAFS shares and the OVF subsystem will log on behalf of the user and transfer image files from remote GAFS locations to the cloud provider shared file system.

REST APIs for other Contrail modules

REST [START_REF] Fielding | Architectural styles and the design of network-based software architectures[END_REF] stands for Representational State Transfer and is a simple yet elegant way to support API development. Using REST, one can provide simple CRUD -Create, Read, Update, and Delete operations over identified resources. REST provides a very clean way of developing APIs and enables quick adoption from cloud developers. Since we desire VEP to be easily integrable in other projects, VEP will provide clear REST APIs for developers. In addition VEP will have clearly defined RESTful APIs for other contrail modules to communicate with it. All requests from other modules including federation layer to VEP layer will be made using REST. The details of the APIs are beyond the scope of this paper. The REST APIs are built over Hyper Text Transfer Protocol (HTTP) protocol messages with support for HTTP GET/PUT/POST/DELETE messages only. Not all methods are available for all users and /or resources. Depending on the nature of the request and the access rights of users' a few or all methods are made available. The VEP REST interface will be stress-tested for scalability.

OCCI support

Open Cloud Computing Interface (OCCI) [START_REF]Open Cloud Computing Interface[END_REF] is a set of open standards [START_REF]OCCI Specification[END_REF] for managing cloud resources that have been developed through Open Grid Forum (OGF) [START_REF]Open Grid Forum[END_REF]. The VEP component in the Contrail project will have an extended OCCI support. Again the need to incorporate OCCI in VEP arises from our requirement to be extensible and integrable in other projects. Additionally, as a result of our work and the experiences gained in providing support for OVFs and SLAs, Contrail project will propose an extension to the current OCCI draft for inclusion in the standardization effort within the OCCI community. These extensions will allow the OCCI framework to support OVF deployments along with providing support for SLAs which the standard lacks in its current format.

The support for OCCI in VEP will hopefully allow the platform to be integrated in future cloud projects and will allow the open source community to develop feature enhancements and add-ons to the VEP layer in the federation of clouds.

Application monitoring and reporting module

Application monitoring subsystem is a very integral part of the VEP as it provides support for the proper enforcement of the SLA contracts. Every application that is deployed on provider's IaaS infrastructure is monitored by the VEP module periodically. The collected data is stored in the VEP database for on-demand retrieval on user's behalf by the federation, but few statistics are pushed periodically on the monitoring bus to be used by the SLA enforcement module to check for compliance and for making elasticity decisions. Figure 3 shows the simplified Each deployed application is assigned a Universally Unique Identity (UUID) that is assigned by the Contrail federation. The same UUID is included as part of the reported data that helps various modules in the SLA/monitoring system in the federation link the data with the correct application and the negotiated SLA object for verification. The federation monitoring bus over which the periodic data is sent will be a distributed messaging system (example: Apache ActiveMQ [START_REF]Apache ActiveMQ[END_REF]) that supports Java Messaging Service (JMS) APIs.

IaaS drivers

The VEP software is envisioned for use with multiple open source IaaS clouds. Contrail VEP software eventually plans to support several major IaaS platforms including OpenNebula, OpenStack, Nimbus scientific cloud [START_REF]NIMBUS[END_REF], etc. We will provide appropriate drivers that can be enabled by the cloud providers as desired for interfacing with appropriate IaaS platforms.

Federation authentication/authorization support

The VEP layer helps a cloud provider become part of the larger Contrail cloud federation. The VEP layer handles all communication to/from the cloud provider and the federation. All requests on behalf of the federation user to the provider comes from the federation layer. Each such request has to be properly authenticated and only authorized requests should be forwarded to the IaaS layer. This check is necessary to prevent resource abuse and is also required for accounting and billing purposes.

Since VEP communicates to federation through REST APIs, each request carries with it the user authorization credentials embedded in the HTTP headers. User certificates and a trusted chain of certificates are used for verification of authorization credentials. The federation maintains the registered user accounts and the resource access rights and other details. The VEP is only interested in finding whether the presented credentials are authentic or not. Once the credentials are verified, the provider's resource access request is forwarded to the proper IaaS cluster.

The VEP also maintains a temporary access control table for active users and their applications that have been deployed through itself. An additional check against this table may also be performed if deemed necessary against the type of access requested.

Virtual Organization

The Contrail VEP supports the notion of a Virtual Organization (VO). The cloud provider / administrator will have the ability to configure the parameters of the virtual organization including list of hosts, networking connections, storage. The VO users' can submit OVFs for deployment making use of already provisioned VO resources. The billing for such resources will be sent to the VO and not the individual VO users. The VEP will support VOs even if the underlying IaaS platform does not support such a notion of organization. If a supported IaaS platform supports VOs natively (example OpenStack), VEP will make an effort to utilize the supported feature as much as feasible. Thus VEP will provide a uniform notion of VO to end users regardless of the underlying IaaS support of VOs.

Concluding remarks

In this paper, we presented a detailed design of Contrail VEP implementation and rationale for our design. We have discussed the Contrail cloud federation briefly. We have explored the major challenges any cloud provider would face, and must address if they plan to become part of a larger federation. Contrail VEP software proposed support for a broad set of open cloud platforms would help significant number of private cloud operators to seamlessly join Contrail federation. Further, VEP's support of open standards and well defined API set will enable cloud researchers and developers to easily extend its features to suit their future requirements and thus making VEP somewhat future proof.

VEP's full integrated support for Contrail federation authentication and authorization mechanisms, and fully stress tested REST and OCCI interface will address some of the challenges (see 2.3, 2.4) we outlined for being part of a federation. The open source mindset and access to the source code would allow independent verification of monitoring modules and other features and thus would help build some level of trust in VEP and Contrail federation (see 2.5).

The Contrail project road map is well defined, in the initial release the VEP effort will provide complete integration with OpenNebula IaaS platform. Support for other cloud platforms including OpenStack will follow in the subsequent releases. There will be basic scheduling support in the first release, but we plan to provide a full resource scheduling feature in the second release. A full support for OCCI will also be provided in subsequent releases. The first release will also see basic OVF support with more complete support in subsequent releases.

Fig. 1 .

 1 Fig. 1. A simple cloud federation

Fig. 2 .

 2 Fig. 2. OVF subsystem in Contrail VEP (simplified version)

Fig. 3 .

 3 Fig. 3. Reporting subsystem in Contrail VEP (simplified version)

This work is supported by the FP7 257438 Contrail integrated project funded by the European Commission.


Lokesh Kumar Bhoobalan

Piyush Harsh

An Experimental Study and Analysis of Crowds based Anonymity

Keywords:

Crowds provides probable innocence in the face of large number of attackers. In this paper, we present the experimental results of the behavior of Crowds in a dense network. We begin by providing a brief description about Crowds followed by the experimental environment in which the simulations were carried out. We then present the results of our simulations and the inferences made out of them. We will also show that the obtained results match the predictions made by others.

Introduction

Anonymous communication involves communicating without revealing the identity to each other and to the outside world. There are three types of anonymity namely sender anonymity, receiver anonymity and the unlink-ability of sender and receiver. Sender anonymity means that the information about the sender will be hidden while the receiver may not. Receiver anonymity on the other hand hides the information about the receiver. Unlink-ability of sender and receiver refers to the phenomenon that, both the sender and the receiver may be found to involve in communication but cannot be identified as communicating with each other.

Many solutions exist to achieve anonymous communication over a network. They can be broadly classified under three heads:

1) Web Proxies 2) Mix based systems 3) Other Communication systems. In a proxy based system, additional trusted third parties called proxy remain in between the sender and receiver. Requests and responses go through this proxy, by which the identities of the communicating parties are hidden. Some of the available proxies for anonymous web browsing include: Anonymizer [START_REF] Cottrell | Your IP Address is Your ID[END_REF], Proxify.com [START_REF]Proxify®anonymous proxy protects your online privacy[END_REF], and Proxy.org [3].

Mix based system was introduced by David Chaum in 1981 [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF]. A mix in short is an enhanced proxy employing public key cryptography to achieve anonymity. It hides the sender's identity by cryptographically altering the messages being exchanged. Mixes utilize techniques such as buffering, and circulation of dummy traffic during idle time, in order to preclude an attacker from retrieving information about the nature and the parties involved in a communication.

Other prominent communication systems include Onion Routing [START_REF] Reed | Anonymous connections and onion routing[END_REF] and Crowds. In Onion Routing, the sender builds a virtual circuit by determining a path between it and the receiver using layered objects called "Onions". Every layer in the layered object contains information about the session key and next address of the node in the path. These onions that travel down the path are unwrapped using the session keys at each node. When the layers are fully removed, the session keys are destroyed.

The final system of interest and also has been the subject of analysis in this literature is the Crowd. They operate by forming a large group of users who may be geographically distributed. Crowds try to hide the actions of an individual with in that group by forwarding the requests randomly between the members before sending it to the final destination. The rest of the paper is organized as follows -section 2 provides a brief description about crowds, section 3 describes the relevant literature review with respect to crowds research, section 4 describes our simulation environment, section 5 presents the experimental results and the inferences drawn from the data, and then we end this paper with conclusion and future direction our research will take.

Crowds: A Brief Description

Crowds provide a mechanism for anonymous web browsing. Though there were other systems such as mix nets and DC-Nets [START_REF] Melchor | From dc-nets to pmixes: Multiple variants for anonymous communications[END_REF] to accomplish the same, crowds were preferred because of the low latency and less computational overhead.

Every member of the crowd runs a process named jondos that registers itself with the central server called blender. Every jondos knows about every other jondos in this architecture. The blender is responsible for the distribution of symmetric keys between every pair (jondos). When a request for a web page begins at one of the nodes, the jondos running in the originator node forwards the request to one of the randomly chosen node by encrypting the message with the corresponding symmetric key. The latter node then either forward the same to another randomly selected node or to the web sever. The decision is taken based on forwarding probability with which it operates.

When a jondos receives a message, it does limited processing to preclude certain attacks and continues to transmit the message. The request and the response of the message follow the same virtual path. These paths are torn down and new paths are constructed on the regular basis whenever Fig. 1: A Typical Crowd Architecture there is a change of member count with in the crowd or there is a node failure. A jondos cannot decide by itself, if the request originated from the preceding node or the one before it.

In this architecture, the adversary can observe the server receiving messages. He/she cannot determine the source of the message. Similarly, when the server transmits the response back in the same path, it is difficult to ascertain the final receiver. In addition, even if the attacker finds that there are clients and servers communicating, he /she cannot find out as to which client talks to which server. Hence the anonymity goals that the crowds achieve include sender anonymity, receiver anonymity and as well as the unlink-ability of sender and receiver. However all of these depend on the kind of attacker that we are talking about while determining the anonymity. For example, there is no sender anonymity against a local eaves dropper and, receiver anonymity against the end server. In addition, none of these anonymity schemes work against a global eavesdropper if the scope of the crowd is only with in LAN. This in turn necessitates spanning the crowd across multiple administrative domains.

Literature Review

In this section we will provide brief descriptions and summaries from literature significant in the domain of crowds. Reiter and Rubin [START_REF] Reiter | Crowds: anonymity for web transactions[END_REF](Crowds: Anonymity for Web Transactions), were the first to introduce the concept of Crowds. They discussed the ways by which crowds can be formed and operated. Measuring anonymity provided by Crowds by employing the concept of degree of anonymity was also discussed. Finally, it was proved that the expected length of hop count for a message to reach the end server is 1 1-P f + 1, and the expected participant payload in a crowd of 'n' nodes is bounded by O( 1(1-P f ) 2 ×(1+ 1 n )).Here P f is the forwarding probability. They also provided information regarding design, implementation, security, performance and scalability of the system. The bounds for the participant payload proposed by Reiter and Rubin was further improved in [START_REF] Sui | The cost of becoming anonymous: on the participant payload in crowds[END_REF](The cost of becoming anonymous: on the participant payload in Crowds). This paper provides a precise formula that expected payload of a participant also tends to 1 1-P f + 1. In addition, the authors also showed that participant payload in Crowds is entirely independent of its size which in turn made evident that the Crowds possess good scalability feature.

In [START_REF] Díaz | Towards measuring anonymity[END_REF] Towards measuring anonymity by Claudia, Stephen, Joris and Bart, the author discusses about measuring the degree of anonymity of systems including Crowd through entropy H(X). In this literature, H(X) for Crowds is measured as,

N -p f (N -C-1) N log 2 [ N N -p f (N -C-1) ] + p f N -C-1 N log 2 [ N p f ]
Here N , p f and C are the total number of crowd members, probability of forwarding to the another member, total number of collaborators respectively. This measure is in addition to the suggestion made in [START_REF] Reiter | Crowds: anonymity for web transactions[END_REF] where the degree of anonymity is defined as (1 -P sender ) where P sender is the probability assigned by the attacker to a particular user.

Trust plays a major role in deciding your forwarder. Hence Vladimiro, Ehab and Sardaouna in their paper titled [START_REF] Sassone | Trust in crowds: probabilistic behaviour in anonymity protocols[END_REF] Trust in Crowds: probabilistic behavior in anonymity protocols, proposes a Crowds-Trust protocol that uses trust information to achieve the desired level of anonymity. They also derive expressions for different level of anonymity required.

Simulation Environment

Network topology consisting of 2500 nodes was generated using Georgia Tech Network Topology Generator (GT-ITM) [START_REF] Zegura | Georgia Tech Internetwork Topology Models[END_REF].The output of the same was converted to a understandable format using the utility sgb2alt that accompanies the software. The output comprised of source,destination node and the path length between them. The path length was interpreted as delay in the simulation. This was followed by computing the shortest path between all pairs of nodes using Floyd-Warshall's Algorithm [START_REF] Floyd | Algorithm 97: Shortest path[END_REF]. This is how we generated the network topology: Included here is a portion of the output that was generated by the topology generator: GRAPH (#nodes #edges id uu vv ww xx yy zz): 2500 188354 geo(0,{2500,2500,3,0.030,0.000,0.000}) 2500 VERTICES (index name u v w x y z): 0 0 805 682 Crowd network was an overlay network on top of this generated network. Hence although there remain direct connections between two nodes in a Crowd network, the message passes through numerous other nodes in the underlying network before reaching the destination. The delay that was precomputed at the end of topology generation was taken as the delay between the nodes due to the underlying network configuration. The simulations were run for different node count and probabilities. Sampling of nodes that are part of Crowd network for every simulation were generated from the underlying topology using a randomized algorithm.

The simulator that we used, was written in Java and ran on Linux machines. The server (blender) was started and made to wait for a predefined period (specified in the configuration file) to accept connections from the clients (members interested in becoming part of the network). At the end of this registration phase, every member was provided information about itself and every other member. The number of client processes to spawn, depending on the node count, were performed using a batch file. These client processes were ran on different machines. The parameters for the client such as the probability with which to operate, time at which to generate and send messages and as well as the delay incurred in transmitting message to its successive member were specified in the client configuration file. Every scenario was run for 100 iterations and the data (hop count, total delay) collected.

Experiments and Outcomes

The simulations were run for member counts ranging from 10 to 1000 with predefined intervals in between this range. The forwarding probability was allowed to vary from 0.1 to 0.95. Measurements were taken after running every scenario for 100 iterations.

The graphical outputs for some of the runs are presented below. The graphs are plotted between the following parameters:

a Count of nodes participating in Crowd and delay incurred in transferring message. b Count of nodes participating in Crowd and the measured hop count. Figures 2,3

Results Interpretation

When the forwarding probability associated with the nodes increased, the average hop count that the message took to reach the destination increased and mostly followed the derived entity 1 1-P f + 1 except under very high probability. This is clearly evident from the fact that the lesser the likelihood of reaching the target, the more it takes to reach it. Also since the crowds neither generate cover traffic nor increase the work load of CPU by encrypting and decrypting the content, the very slow increase of hop count for huge increase in the member count is beneficial for community adopting this service.

Though the hop count is minimum,the delay is more since the hop count overlooks the underlying nodes in between the member nodes.As the result, this service cannot be adopted for systems that require faster response.The delay in the response may not be acceptable for interacting users even for queries such as the one that provides some location information. The standard deviation of the hop count increased on increasing probability. The standard deviation of the hop count decreased on increasing the number of nodes for the same probability. The hop count increases gradually for every increase in probability except at above 0.9 where there is a huge increase in the hop count.

Crowds neither generate cover traffic nor increase the work load of CPU caused due to a series of encryption and decryption. The encryption and decryption performed using path key is very minimal in Crowds. Hence they are preferred over mix nets and onion routing specially in situations where security of the content is not of prime importance. From the simulations, it is observed that the hop count increases very slowly and reaches the value 8 until the probability value hit 0.85, after which it increases drastically even for the large number of nodes. This seems to be reasonable in the light of the service that it provides.

Although Crowd is meant to provide efficient service, the delay associated in sending a message to the destination is significant. This is evident from the graphs above where delay value is quite high even for minimum node count.

Conclusion

This paper provides the experimental results that we carried out to validate the operation of a crowd anonymity network. We have described our simulation strategy and provided the results we got. The results are in line with theoretical predictions made in several of the pioneering work in this field. In the very near future, we are planning on analyzing crowds and the degree of anonymity it provides by incorporating it within a utility function that would include the notion of cost versus degree of anonymity, transmission delay and other relevant parameters. It is still a work in progress and would take some time before we can comment on the strategy here in this paper. We are also planning on using the same utility function to compare other anonymity schemes such as onion routing, mix nets, etc.

#

  <method keyword> <number of graphs> [<initial seed>] # <n> <scale> <edgemethod> <alpha> [<beta>] [<gamma>] geo 3 2500 2500 3 .03

  , 4, 5, and 6 show the message transmission delays incurred in milliseconds between the source and destination when transmitted through the crowds network with varying transmission probability and with crowds composed of different node counts.The next set of figures shows the hop count a message has to travel before reaching the destination if sent through the

Fig. 2 :Fig. 4 :Fig. 5 :Fig. 6 :Fig. 7 :

 24567 Fig. 2: Transmission delay for probability 0.95

Fig. 8 :Fig. 9 :Fig. 10 :Fig. 11 :

 891011 Fig. 8: Number of hops traveled for probability 0.65

Acknowledgment

The authors would like to thank Dr. Richard Newman for providing suggestions on experimental methodology. The CISE systems administrators were also helpful by allowing us run experiments on several of their nodes (albeit after hours) even though the study conducted was not part of any approved research work and was purely voluntary work conducted on our part.


Luis Salomon

Jean-Claude Fort
email: jean-claude.fort@parisdescartes.fr

Estimation of the Hurst parameter in some fractional processes

We propose to estimate the Hurst parameter involved in fractional processes via a method based on the Karhunen-Loève expansion of Gaussian process.We specifically investigate the cases of the Fractional Brownian motion(FBm) and the Fractional Ornstein-Uhlenbeck(FOU) Family. The main tool is the analysis of the residuals of a convenient linear regression model. We numerically compare our results with the ones obtained by the maximum likelihood method, which show the validity of our proposal.

Introduction

Our goal is to propose an estimator of the hurst parameter of a fractional gaussian process that performs almost as the maximum likelihood estimator but is more robust to computational problems.

Our framework is quite simple : we have observations of a random process at equally spaced or randomly distributed times, X(t 1 ), . . . , X(t n ). Assuming that the model which rules these observations is a gaussian fractional process (Brownian motion, Ornstein Ulhenbeck process, Brownian bridge) we estimate the hurst parameter denoted by θ, θ ∈ (0, 1)]. We are strictly in the parametric estimation framework.

Obviously the best estimator is obtain by maximizing the likelihood. It involves the numerical computation of the inverse of the covariance matrix, which is tedious when n is of magnitude larger than 500, even using LU decomposition.

Our alternative method relies on the Karhune-Loève decomposition, but in practice only needs a short expansion, say less than 10 terms.

The next section presents our framework and recall some basic results about Karhune-Loève decomposition. In section 3 we define our estimator and give some asymptotic results that prove its consistency. Finally a section is devoted to numerical comparison with the Maximum Likelihood Estimator (M.L.E.) on several examples.

Framework and basic results

In this section we introduce a method based in the Karhunen-Loève expansion of Gaussian process to estimate the Hurst parameter involved in fractional processes, specifically the Fractional Brownian motion(FBm) and the Fractional Ornstein-Uhlenbeck(FOU) Family. Our aim is to compare our results with the ones obtained by the maximum likelihood method and show the validity of our proposal.

In the sequel for all the fractional process we will consider, we deal with only one unknown parameter of interest: the hurst parameter θ. This parameter describes the roughness of the path we partially observe.

In many cases other parameters are to be considered as mean, variance, drift parameter... We will discuss these cases further on.

For instance for the Fractional Ornstein-Ulhenbeck family we assume that µ = 0 and that α the drift parameter and σ the spatial scale are known.

Karhune-Loève decomposition

We will consider from now on that X belongs to one of the family (X θ ) of centered fractional Gaussian process mentioned before with Hurst parameter θ in [0, 1]. We assume that the observation time interval is [0, 1]. Let us denote by θ 0 the real and unknown parameter of the process actually observe, X θ 0 . It is well-known that a Gaussian process has a unique representation in the basis of Karhunen-Loève. This basis is given by the diagonalisation of the so-called covariance operator Γ of the process X, which is assumed to be a Hilbert-schmidt operator:

Γ θ (f )(t) = E(f (X θ (s))X θ (t)X θ (s)) = R f (t)cov(X θ (t), X θ (s))ds.
For each value of θ we denote by (λ θ i , ϕ θ i ) i≥1 the eigenvalues and associated normalized eigenfunctions of Γ θ in decreasing order. Then there exists a an i.i.d. sequence of standard normal random variables ξ θ i , such that in L 2 [0, 1]:

X θ (t) = i≥1 λ θ i ξ θ i ϕ θ i (t), (1)
This is the Karhunen-Loève decomposition of X θ .

For N an integer, splitting the sum in equation (1) we have:

X θ (t) = i≥1 λ θ i ξ θ i ϕ θ i (t) = N j=1 λ θ i ξ θ i ϕ θ i (t) + j≥N +1 λ θ i ξ θ i ϕ θ i (t).
This can be seen as a linear regression model with noise

ε θ (t) = j≥N +1 X θ , ϕ θ j ϕ θ j (t) = j≥N +1 λ θ j ξ θ j ϕ θ j (t),
so that we may write :

X θ (t) = N j=1 λ θ i ξ θ i ϕ θ i (t) + ε θ (t) (2) = 1≤j≤N X θ , ϕ θ j ϕ θ j (t) + ε θ (t). (3)
The covariance function of ε θ (t) is given by

C θ (t, s) = E θ (ε θ (t)ε θ (s)) = j≥N +1 λ θ j ϕ θ j (t)ϕ θ j (s). (4)

The observations

We assume observing the path of the process X θ 0 at n times t 1 , . . . , t n , which could be regularly spaced or uniformly distributed. Let t = (t 1 , • • • , t n ) ′ , in view of (3) we write:

X θ (t) =    X θ (t 1 )
. . .

X θ (t n )    = M θ N (t)Ξ θ N + ε θ N (t),
where

M θ N (t) = X θ , ϕ θ j 1≤i≤n 1≤j≤N , Ξ θ N =    ξ θ 1 . . . ξ θ N    , ε θ N (t) =    ε θ (t 1 ) . . . ε θ (t n )    ,
This is a classical multiple regression model:

X θ (t) = M θ N (t)Ξ θ N + ε θ N (t). (5)
From this we derive the estimator of Ξ θ N and consequently the estimate of ε θ N (t). We also have the covariance matrix of ε θ N (t), defined by

Σ θ N = j≥N +1 λ θ j ϕ θ j (t k )ϕ θ j (t l ) 1≤k≤n 1≤l≤n . ( 6
)
Since we work with Gaussian process ε θ N is gaussian vector, ε θ N (t) ∼ N (0, Σ θ N ), and it follows that

η N = (Σ θ N ) -1 2 ε θ N (t) ∼ N (0, I n ), and then η N 2 ∼ χ 2 (n). The estimator of Ξ θ N is Ξ θ N = (M θ N (t) ′ (Σ θ N ) -1 M θ N (t)) -1 M θ N (t) ′ (Σ θ N ) -1 X θ (t),
and the estimate of the residuals is ε θ N (t) which writes

ε θ N (t) = (I n -H θ )X θ (t),
where H θ is the hat matrix of the model with the following expression

H θ = M θ N (t)(M θ N (t) ′ (Σ θ N ) -1 M θ N (t)) -1 M θ N (t) ′ (Σ θ N ) -1 . therefore ε θ N (t) ∼ N (0, (I n -H θ )Σ θ N (I n -H θ ) ′
). Now we observe X θ 0 (t) with true unknown parameter θ 0 and the regression model ( 5) is given by the expansion on the Karhunen-Loève basis associated to θ. Hence we must write:

X θ 0 (t) = i≥1 ρ θ,θ 0 i ϕ θ i (t), (7)
where

ρ θ,θ 0 i = 1 0 X θ 0 (t)ϕ θ i (t)dt,
and when θ = θ 0 , ρ θ 0 ,θ 0 i = λ θ 0 i ξ θ 0 i . The regression model ( 5) becomes:

X θ 0 (t) = M θ,θ 0 N (t)Ξ θ,θ 0 N + ε θ,θ 0 N (t), (8)
where M θ,θ 0 N (t) and Ξ θ,θ 0 N are:

M θ,θ 0 N (t) = X θ 0 , ϕ θ j 1≤i≤n 1≤j≤N , Ξ θ,θ 0 N =    ξ θ 1 . . . ξ θ N    and ε θ,θ 0 N (t) = (ε(t 1 ) θ,θ 0 , • • • , ε(t n ) θ,θ 0 ) ′ , with ε θ,θ 0 (t i ) = j≥N +1 X θ 0 , ϕ θ j ϕ θ j (t i ) = j≥N +1 ρ θ,θ 0 i ϕ θ j (t i ).
Our procedure of estimation decomposed in three steps :

1. Observe the real process X θ 0 (t) with unknown parameter θ 0 .

2. Adjust the regression model ( 8) for X θ 0 (t), for "all" values θ in (0, 1).

3. Construct a function based on the estimation of the parameters of the model with the property that discrepancy appears when θ = θ 0 .

As previously, the covariance function of the process ε θ,θ 0 (t) is calculated as:

C θ,θ 0 (t, s) = E(ε θ,θ 0 (t)ε θ,θ 0 (s)) = cov ε θ,θ 0 (t), ε θ,θ 0 (s) = E i≥N +1 j≥N +1 X θ 0 , ϕ θ i X θ 0 , ϕ θ j ϕ θ i (t)ϕ θ j (s) = E i≥N +1 j≥N +1 1 0 1 0 X θ 0 (u)X θ 0 (v)ϕ θ i (u)ϕ θ j (v)dudv ϕ θ i (t)ϕ θ j (s) = i≥N +1 j≥N +1 1 0 1 0 Γ θ 0 (u, v)ϕ θ i (u)ϕ θ j (v)dudv ϕ θ i (t)ϕ θ j (s),
where we recall that

Γ θ 0 (u, v) = E(X θ 0 (u)X θ 0 (v))
is the covariance function for the process X θ 0 (t).

If we denote

A θ,θ 0 i,j = 1 0 1 0 Γ θ 0 (u, v)ϕ θ i (u)ϕ θ j (v)dudv, (9)
the final expression for the covariance function of the process ε θ,θ 0 (t) is

C θ,θ 0 (t, s) = i≥N +1 j≥N +1 A θ,θ 0 i,j ϕ θ i (t)ϕ θ j (s). (10)
Therefore the covariance matrix of ε θ,θ 0 N (t) is

Σ θ,θ 0 N =     i≥N +1 j≥N +1 A θ,θ 0 i,j ϕ θ i (t k )ϕ θ j (t l )     1≤k≤n 1≤l≤n , (11)
Our idea is to use Σ θ N and Σ θ,θ 0 N to construct a "contrast function" h that measures the strength of the estimation for all value of θ. This "contrast function" will be built on the residuals of the regression. Actually h will not be a contrast but its derivative, which is enough for our purpose.

So we leave the issue of estimation of the parameters in our model. Let us focus our attention on the random vector of the "standardized" residuals:

η θ,θ 0 N = (Σ θ N ) -1 2 ε θ,θ 0 N (t) ∼ N (0, (Σ θ N ) -1 2 Σ θ,θ 0 N (Σ θ N ) -1 2 ).
This involves the actual covariance matrix (unknown) and the covariance matrix for a model depending on θ, and we have:

E η θ,θ 0 N 2 = E ε θ,θ 0 N (t) ′ (Σ θ N ) -1 ε θ,θ 0 N (t) = tr(Σ θ,θ 0 N (Σ θ N ) -1 ).
Then we define the contrast function h N by:

h N (θ; θ 0 ) = lim n→+∞ tr(Σ θ,θ 0 N (Σ θ N ) -1 ) n = lim n→+∞ E η θ,θ 0 N 2 n (12) If θ = θ 0 , then Σ θ 0 ,θ 0 N = Σ θ 0 N , η θ 0 ,θ 0 N = η N and tr(Σ θ 0 ,θ 0 N (Σ θ 0 N ) -1 ) n
= 1, so that h N (θ 0 ; θ 0 ) = 1. Furthermore we know the behaviour of h N when θ = θ 0 :

Theorem 2.1. We assume that X θ (t) is a fractional Brownian motion or a fractional Ornstein-Ulhbeck with Hurst parameter θ ∈ (0, 1) defined on [0, 1] and X θ 0 (t) for t = (t 1 , • • • , t n ) is the partial observation of a path of the process X θ 0 . The times of observation t are assumed to be equally spaced or random i.i.d. variables uniformly distributed on [0, 1], independent of X θ 0 . The function

h N (θ; θ 0 ) = lim n→+∞ tr(Σ θ,θ 0 N (Σ θ N ) -1 ) n ,
with Σ θ N and Σ θ,θ 0 N defined in ( 6) and ( 11) respectively satisfies the following property:

If θ = θ 0 then h N (θ; θ 0 ) = 1. If θ > θ 0 then h N (θ; θ 0 ) = ∞. If θ < θ 0 then h N (θ; θ 0 ) = 0.
The proof is postponed in Annex A.

The previous result is obtained in a rather theoretical setting : the Karhunen-Loève decomposition is known, N is fixed and the limit n → ∞ is taken. In practice we have to choose N , use an approximation of the Karhunen-Loève basis, n is finite, we only can compute estimations of h N , and finally it is not possible to estimate h N at every possible value of θ 0 . The question of the choice of N will be studied by simulation. Now we estimate h N . We use:

h N (θ; θ 0 ) = η θ,θ 0 N 2 n -N = ε θ,θ 0 N (t) ′ (Σ θ N ) -1 ε θ,θ 0 N (t) n -N , where ε θ,θ 0 N (t) = (I n -H θ )ε θ,θ 0 N (t) ∼ N (0, (I n -H θ )Σ θ,θ 0 N (I n -H θ ) ′ ).
Conditionally to the time values t, η θ 0 ,θ 0 N 2 is a χ 2 with n -N degrees of freedom, so that E h N (θ 0 ; θ 0 ) = 1 and h N (θ 0 ; θ 0 ) converges in probability toward 1.

Hence we propose to estimate the parameter θ 0 by :

θ = Argmin θ | h N (θ; θ 0 ) -1| (13)
To compute this estimator we need an approximation of the Karhunen-Loève basis. For this we built a database with the values of the covariance matrix Γ θ (t, s) for a suitable collection of θ on a discretization of[0, 1] and for each fractional process we studied. It remains to numerically computatie Σ 1 which is possible even for about thousand points. We avoid the term log(det Σ) that appears in the M.L.E. estimation.

As we focus onto the method itself we do not discuss the numerical implementation of this data basis, but we easily obtain good numerical approximations by simulation, and we do it only once for all.

Then θ is computed by interpolation of the grid values.

Simulation Study and Numerical Results

Fractional Brownian

We conduct a simulation study to compare the estimates from our method (KL method) with the M.L.E.. Both procedures were used to give estimates of the Hurst parameter in fractional processes. This study shows that the KL method performs well.

The simulation study has been organized in two parts 1. A first simulation study to find a good choice of N when n is fixed and the same for n for N fixed (it is reasonable order). 2. A simulation study with good choices of n and N in order to find the estimation of the Hurst parameter for the fractional processes.

For the Fractional Brownian motion we set

• n = 300,

• N = 5; 10; 30; 50; 100; 150; 200, and

• θ 0 = 0.1 and θ 0 = 0.7.
The first values of θ 0 is close to 0 and is not easy to estimate. The second one illustrate an easier case. We tried many values of N , but we knew that only small values (5 to 10) would be of practical use. The value n = 300 is in the range of easy computation of the M.L.E.. For each combination of previous values we generate 50 random samples of the fractional process. Then we calculate the value of h(θ; θ 0 ) on a grid of values of θ from 0.05 to 0.95 by step of 0.01. Finally we interpolate the results obtained to compute θ 0 for which h(θ; θ 0 ) = 1. We use a parabolic interpolation because of the behavior of h.

Table 1 shows that the KL method gives good results for any value of N . This is confirmed observing the box-plot representation for each case (see Figure ??). However, it is important to highlight that for the greatest values of N more variability in the estimations is observed.Thus, using small values of N produce best results for estimating θ 0 . Here it is worth pointing out that the theoretical assumption needed for N (N ≫ 1) can be relaxed in numerical calculations. This make our KL method easily tractable in any case. In the second part of the simulation study we analyze of the behavior of θ with nwhen N is fixed.

In the light of the previous simulation study we consider the following settings.

N Mean STD 5 0,1018 0,0078 10 0,1018 0,0075 30 0,1018 0,0074 50 0,1021 0,0071 100 0,1023 0,0083 150 0,1027 0,0094 200 0,1038 0,0115 N Mean STD 5 0,7004 0,0060 10 0,7004 0,0060 30 0,7003 0,0061 50 0,7001 0,0061 100 0,7002 0,0075 150 0,7010 0,0083 200 0,7025 0,0091 Table 1: Mean and standard deviation for the estimation of θ 0 for each value of N by using 50 random observations of the FBm with the true parameter and n = 300. (Left: θ 0 = 0.1. Right: θ 0 = 0.7).

• N = 5,

• n = 10; 50; 100; 150; 200; 300, and

• θ 0 = 0.1 and θ 0 = 0.7.
For each combination of the previous values we generate 50 random samples of the fractional process. Then we calculate the value of h(θ; θ 0 ) as described previously.

n Mean STD 10 0,1236 0,0377 50 0,0828 0,0451 100 0,1025 0,0167 150 0,1006 0,0119 200 0,0977 0,0094 300 0,0997 0,0071 n Mean STD 10 0,7200 0,0349 50 0,6848 0,1007 100 0,7029 0,0122 150 0,7005 0,0082 200 0,6992 0,0075 300 0,6991 0,0064 Table 2: Mean and standard deviation for the estimation of θ 0 for each value of n by using 50 random observations of the FBm with the true parameter and N = 5. (Left: θ 0 = 0.1. Right: θ 0 = 0.7).

The numerical results in Tables 2 andFigure ?? allows to thinkthat our estimator converges, and that the speed of convergence is of the correct magnitude.

Therefore we conclude that a choice of N between 5 and 10 is appropriate. if we a priori suspect small value of θ 0 N = 10 would be enough since the eigenvalues of the covariance operator decrease slowly, a contrario when θ 0 is large the eigen values decreases faster and N = 5 would be better According to the previous conclusions we perform a last simulation study to compare the performances of the KL method and the M.L.E..

The study provides quantitative results for different values of the parameter. For the simulation scheme we set θ 0 ∈ {0.1, 0.3, 0.7, 0.9}, n = 200, N = 10 for the first two values of θ 0 and N = 5 for the other two.

For the M.L.E. we maximize the:

h mle (θ; θ 0 ) = -ln(det(D θ 0 n Γ θ (t))) -(X θ 0 t ) ′ Γ θ (t)X θ 0 t ,
where Γ θ (t) = (Γ θ (t i , t j )) 1≤i,j≤n , D θ 0 n is the function who assure that det(D θ 0 n Γ θ (t)) > 0 in the numerical implementation. The matrix Γ θ (t) is definite positive for any t hence det(Γ θ (t)) > 0. But due to the small values of the eigenvalues associated to Γ θ (t) we faced numerical difficulties. We easily avoided this numerical problem.

For both methods we improved the numerical precision by a quadratic interpolation in each case. The results can be seen in Table 3.

Mean STD Mean STD 0.1 0,1004 0,0100 0,0993 0,0119 0.3 0,3009 0,0085 0,2998 0,0078 0.7 0,7008 0,0082 0,7007 0,0081 0.9 0,9004 0,0051 0,9007 0,0081 The results of table 3 clearly prove that the two methods are are numerically equivalent. Of curse the M.L.E. estimator is the by the Cramer Rao bound, but the KL method provides an almost as precise estimator as the M.L.E. This partial conclusion for the Fractional Brownian motion has been confirmed by the study of fractionnal ornstein-ulhlhenbeck(F.O.U.) of the third kind.

Fractional Brownian motion (fBm)

In this case we will use the results of Bronski (?). This article provides expansion of the eigenvalues appearing in the Karhunen-Loève decomposition of the fBm, more precisely

λ θ n = v θ n 2θ+1 + o n -(2θ+2)(4θ+3) 4θ+5 +δ ∀ δ > 0, n ≫ 1, where v θ = sin(πθ)Γ(2θ + 1) π 2θ+1 ,
and Γ is the usual Gamma function.

In the proof of the previous result the author define an integral operator A in the orthonormal basis { √ 2 sin (n + 1 2 )πx} ∞ n=0 , which is the Karhunen-Loève basis of the Wiener process. The A m,n element for θ = θ 0 writes:

A m,n = 1 0 1 0 (u 2θ 0 + v 2θ 0 -|u -v| 2θ 0 ) sin(m * u) sin(n * v)dudv,
where n * = (n + 1/2)π and likewise m * .

Bronski shows that A can be written as A = D + O, where D is a diagonal piece and O an off-diagonal piece (the expressions for both are in ?). In our case is easy to see that

A 1/2,θ 0 i,j = A i,j .
We have to study the quotient A θ,θ 0 i,i /λ θ i , hence we focus on the diagonal entries of A. Therefore it follows

A 1/2,θ 0 n,n = sin(πθ 0 )Γ(2θ 0 + 1) n * 2θ 0 +1 + O(n -2(θ 0 +1) ), thus A 1/2,θ 0 n,n λ 1/2 n = sin(πθ 0 )Γ(2θ 0 + 1)n 2θ 0 -1 + O( (n + 1/2) 2 n 2(θ 0 +1) ). Now it is straightforward that lim n→+∞ 1 n n+N i≥N +1 A 1/2,θ 0 i,i λ 1/2 i = +∞ if θ 0 > 1/2 0 if θ 0 < 1/2
With this result we just get the result in the case θ = 1/2, but the general follow the same way. In Bronski (?) is established an asymptotic expansion of the eigenvalues and eigenfunctions of the FBm

λ θ n ∼ v θ n 2θ+1 n ≫ 1, (14) ϕ θ n (x) ∼ √ 2 sin(n * x) n ≫ 1 Hence setting A m,n = 1 0 1 0 (u 2θ 0 + v 2θ 0 -|u -v| 2θ 0 )ϕ θ n (u)ϕ θ n (v)dudv,
and using ( 14) we obtain A θ,θ 0 n,n = A n,n ∼ A n,n = sin(πθ 0 )Γ(2θ 0 + 1) n * 2θ 0 +1 + O(n -2(θ 0 +1) ). A θ,θ 0 i,i

That leads us to

λ θ i = +∞ if θ 0 > θ 0 if θ 0 < θ . ( 15
)
This ends the proof for the fBm. Here we assume that α and σ are known.

There is no closed form for the covariance function or its eigenvalues, but one can relate them to the corresponding values for the fBm.

Let us denote Γ θ,B , (ϕ θ,B j (t)) j≥1 and (λ θ,B j ) j≥1 the covariance function, KL eigenfunctions and eigenvalues respectively for the fBm. The process X θ,1 t can be expanded on (ϕ θ,B j (t)) j≥1 , which is an orthonormal basis of L 2 ([0, 1]). Then

X θ 0 ,1 (t) = i≥1 ρ θ,θ 0 i ϕ θ,B i (t), (17)
where ρ θ,θ 0 i = 1 0 X θ 0 ,1 (t)ϕ θ,B i (t)dt, therefore the expression for A θ,θ 0 ij in (9) still takes the form

A θ,θ 0 i,j = 1 0 1 0 Γ θ 0 (u, v)ϕ θ,B i (u)ϕ θ,B j (v)dudv, (18)
where Γ θ 0 is the covariance function of the fOU. We have:

Σ θ,θ 0 N =     i≥N +1 j≥N +1 A θ,θ 0 i,j ϕ θ,B i (t k )ϕ θ,B j (t l )     1≤k≤n 1≤l≤n . ( 19
)
As in (??) we have:

h N (θ; θ 0 ) = lim n→+∞ 1 n n+N i≥N +1 A θ,θ 0 i,i λ θ i

  Ornstein-Uhlenbeck (fOU) of first kind (see (??)). It is the solution of the Stochastic Differential Equation driven by a fractional Brownian motion dX H

Table 3 :

 3 Mean and standard deviation for the estimation of several θ 0 .

Σ θ N,N ⋆ = Ψ N ⋆ Λ N ⋆ Ψ ′ N ⋆ and Σ θ,θ 0 N,N ⋆ = Ψ N ⋆ A N ⋆ Ψ ′ N ⋆ .Since tr(AB) = tr(BA) for any matrices A, B such as AB and BA are square matrices it follows thattr(Σ θ,θ 0 N,N ⋆ (Σ θ N,N ⋆ ) -1 ) = tr(Ψ N ⋆ A N ⋆ Ψ ′ N ⋆ (Ψ N ⋆ Λ N ⋆ Ψ ′ N ⋆ ) -1 ) = tr(A N ⋆ Λ -1 N ⋆ ) Assuming N ⋆ ≥ n + N and large enough, rank(Ψ ′ N ⋆ ) = n (a.s. if t is random) and the matrix Λ 1/2 N ⋆ Ψ ′ N ⋆ (Ψ N ⋆ Λ N ⋆ Ψ ′ N ⋆ ) -1 Ψ N ⋆ Λ 1/2 N ⋆is the matrix of the orthogonal projection on the column of Λ1/2 N ⋆ Ψ ′ N ⋆ . Hence the matrix A N ⋆ Ψ ′ N ⋆ (Ψ N ⋆ Λ N ⋆ Ψ ′ N ⋆ ) -1 Ψ N ⋆ is conjugate with Λ -1/2 N ⋆ A N ⋆ Λ -1/2 N ⋆ . We have obtained: tr(Σ θ,θ 0 N,N ⋆ (Σ θ N,N ⋆ ) -1 ) = tr(A N ⋆ Λ -1 N ⋆ ) = N ⋆ i≥N +1 A θ,θ 0 i,i λ θ i .

Fractional Ornstein-Uhlenbeck. First Kind

For this case has not interest in perform a simulation study. As we state before we need to construct a FBm using the FOU of the first kind and conduct the KL method to the obtained FBm. In that sense we use the inverse of

Obviously for the simulation study we construct first the FBm to obtain the FOU of first kind. Therefore the reversal formula is used. It is an obvious consequence that we will obtain the same FBm that was generated. Hence is not necessary to conduct a simulation study because in this case the general setting for the FBm applies.

Annex A : proof of theorem 2.1

We suppose θ = θ 0 . We begin by taking "approximations" of the matrices Σ θ N , Σ θ,θ 0 N . Let N ⋆ we define the following matrices in order to approximate Σ θ,θ 0 N , Σ θ N :

, where λ θ ij = λ θ i if i = j and zero otherwise. Therefore we have the following approximations:

Again we note the spatial scale invariance of our estimator. Yet there still remain another unknown parameter α.

3.0.6. Somme comments about the fractional Ornstein-Uhlenbeck (Second and third Kind)

The process X θ,2 , fOU of the second kind, satisfies:

where a t,θ = θσ 2 e θt/θ /θ, thus we propose a different approach. We use the previous equation to revert the fractional Process of second kind into a fractional Brownian motion. This method can also be used for the fOU of first kind. For both cases we can construct a FBm W θ (t) with Hurst parameter θ ∈ (0, 1) in t = (t 1 , • • • , t n ) and t = (e θt 1 /H , • • • , e θtn/H ) respectively. Theorem ?? applies with the correct modifications for the fOU of second kind. This assertion state that a correct estimation of the Hurst parameter on a fBm leads us to a correct estimation for the associated fOU.

For the FOU of third kind X θ,3 (t) we know the exact expression of the covariance function. Hence the same procedure can be used. However,due to Rosenblatt, we only have asymptotic for the eigenvalues: λ θ,3 n ∼ n -(1+2θ) , we refer the reader to ? and ? for details. Therefore we are not in position to give a proof of our theorem for this process.