Chien-Erh Weng
email: ceweng@mail.nkmu.edu.tw

Chien-Hung Chen

Chiung-Hsing Chen

Jyh-Horng Wen
email: jhwen@thu.edu.tw

The Performances Study of EDCF with Block_Ack in WLANs

Keywords: EDCF, Acs, QoS, Block_Ack 1

IEEE 802.11e Enhanced Distributed Coordination Function (EDCF) is a new wireless technology in wireless local area networks (WLANs). It defines a new supplement to the existing IEEE 802.11 MAC protocol. In IEEE 802.11e EDCF, the aim is providing a QoS support in WLANs. While the system services different Access categories (ACs), IEEE 802.11e EDCF does not perform well under high load conditions. In order to improve the efficiency, we pay attention to the EDCF of IEEE 802.11e with Block_Ack mechanism. We first proposed a markov chain model and studied the behavior. We extend the model to support IEEE 802.11e EDCF, and presented a more accurate analysis under non-ideal channel environment. We also compared it with that without Block_Ack mechanism under channel error environment.

INTRODUCTION

In recent years, the WLANs market is experiencing an explosive growth. The medium access control (MAC) protocol is the key element that provides the efficiency in accessing the channel, while satisfying the quality of service (QoS) requirements. IEEE 802.11e EDCF is a new wireless technology which is an enhanced version of IEEE 802.11 distributed coordination function (DCF). The IEEE 802.11e EDCF aims at improving the capabilities and efficiency of the IEEE 802.11 MAC protocol by defining a new mechanism to support the QoS services. While the system services different ACs, EDCF does not perform well under high load conditions. In order to improve the efficiency, EDCF provides two mechanisms named as transmission opportunity (TXOP) and Block_ACK. These two mechanisms are allowed to offer new data transmission services that include the multiple frame delivery [START_REF] Xiao | QoS guarantee and provisioning at the contention-based wireless MAC layer in the IEEE 802.11e wireless LANs[END_REF][START_REF] Gu | QoS enhancement in IEEE 802.11 wireless local area networks[END_REF][START_REF] Choi | IEEE 802.11e contention-based channel access (EDCF) performance evaluation[END_REF]. There have been many performance analyses of the IEEE 802.11e EDCF. Deng and Chang [START_REF] Deng | A priority Scheme for IEEE 802.11 DCF Access Method[END_REF] proposed a priority scheme by differentiating the backoff window. Aad and Castelluccia [START_REF] Aad | Differentiation Mechanisms for IEEE 802[END_REF] proposed a priority scheme by differentiating inter-frame spaces (IFS's), in which a higher priority class uses IFS, whereas a lower priority class uses a space that equals the sum of IFS and the maximum window size. In [START_REF] Veres | Supporting Differentiation in Wireless Packet Networks Using Distributed Control[END_REF] Veres and Campbell et al. proposed priority schemes by differentiating the minimum backoff window size and the maximum window size. These performance studies neglected that high load situation. They can't truly reflect the real operation of EDCF with priority schemes. In order to improve the efficiency, IEEE 802.11e EDCF provides two mechanisms named as TXOP and Block_Ack mechanisms. In this paper, we pay attention to the EDCF of IEEE 802.11e with Block_Ack mechanism. We proposed a markov chain model and studied the behavior. We extend the model to support IEEE 802.11e EDCF, and present a more accurate analysis of the IEEE 802.11e EDCF under a non-ideal channel environment. We also compared it with that without Block_Ack mechanism under channel error environment.

The rest of this paper is organized as follows. In section 2, a general description of our proposed model with Block_Ack mechanism is presented. Analytical performance deviations of proposed model including throughput analysis under non-ideal channel scenario are presented in section 3. The numerical results are given with discussion in section 4. Finally, conclusions are drawn in section 5. The contention method of EDCF is the same as that in DCF. Each STA having a frame to transmit has to wait for the channel to be idle without interruption for a period AIFS[AC], and then it should start a random backoff process with its own CW[AC]. For each time slot interval, during which the channel stays idle, the random backoff value is decremented. When the backoff counter reaches zero, the frame is transmitted. AIFS[AC] is calculated as follows:

AIFS[AC] =AIFSN[AC] aSlotTime + aSIFSTime,  (1)
where the backoff time is calculated as follows:

backoff time = random_integer aSlotTime, 

where random_integer is uniformly and randomly chosen in the range [0,CW(AC)], instead of [0,W-1] in the DCF. The value of CW min is 15 and CW max is 1023 [12]. Initially, CW of each AC is equal to CW min [AC]. After each collision, CW is doubled up to:

    [ ] 2 , m max min CW AC CW AC  (3)
where m is called the maximum backoff stage. Once it reaches CW max [AC], it remains at this value until it is reset.

The System Model

We assume in the following that for a given station in the priority i class, ( , ) b i t is defined as a random process representing the value of backoff counter at time t, and s(i,t) is defined as the random process representing the backoff stage j , where

2 j i j i W W  and   ,0 i min W CW i  .
Let p i denote the probability that a transmitted frame collides in the priority i class. A Markov chain { ( , ), ( , )} s i t b i t can be established to analyze the contention process. Therefore, the state of each station in the priority i class is described by {i, j, k}, where i is just an index standing for the priority i class, j stands for the backoff stage and takes values (0,1,...,m), and k stands for the backoff delay and takes values   , 0,1,..., 1 ij W  in time slots. The state transition diagram for the priority i class is shown in Fig. 1, where the state {i, 1, 0} stands for the state that the station senses when the channel is idle and when a previous frame transmits successfully, the STA can transmit a frame immediately without activating the backoff stage. The transmission probabilities are listed as follows:

1. The backoff counter freezes when the STA senses that the channel is busy in the priority i class:

, { , , , , } , 0 1, 0 .

i i j P i j k i j k p k W j m       (4)
2. The backoff counter decrements when the STA senses the channel is idle in the priority i class:

, { , , , , 1} 1 , 0 2, 0 .

i i j P i j k i j k p k W j m         (5)
3. The STA enters the {i, -1, 0} state if it has a successful transmission with the previous frame in the priority i class:

{ , 1,0 , ,0} 1 , 0 .

i P i i j p j m      (6)
4. The STA transmits it frame without entering the backoff process at {i, 1, 0} state if it detects that its previous transmitted frame was successfully received and the channel is idle in the priority i class:

{ , 1,0 , 1,0} 1 .

i P i i p     (7)
5. The STA defers the transmission of a new frame and enters stage 0 of the backoff process if the STA finds a collision has occurred at {i, 1, 0} state in the priority i class:

,0 ,0 { ,0, , 1,0} , 0 1.

i i i P i k i p W k W      (8)
6. The STA chooses a backoff delay of the next stage j after an unsuccessful transmission at stage j-1 in the priority i class:

,, { , , , 1,0} , 1 , 0 1.

i i j i j P i j k i j p W j m k W        (9)
Let ,, lim { ( , ) , ( , ) } i j k r b P s i t j b i t k    be the stationary distribution of the Markov chain. We can derive the following relations by chain regularities:

                    , 1,0 ,0 ,0 2 2 1 1 2 . 2 2 1 1 2 1 2 1 1 2 1 2 i i i i m m i i i i i i i i i p p p b p p p W p p W p p             (10)
Let i  be the probability that a STA in the priority i class transmits during a time slot e. We then have 1 , 1,0 , ,0 , ,0 , 1,0 0 1 . 1

m i i i j i m i i j b b b b p            (10)
,

1, 0 i j  , , , 1
i j i j W  , , , 2
i j i j W  , , 2 i j , ,1 i j , , 0 i j 1 i p  1 i p  1 i p  1 i p  1 i p  i p i p i p i p , 1 i i p W , i i j p W , 1 i i j p W  , 0 , 0, 1 i i W  , 0 , 0, 2 i i W  , 0, 2 i , 0,1 i , 0, 0 i 1 i p  1 i p  1 i p  1 i p  1 i p  i p i p i p i p 1 i p  1 i p  1 i p  1 i p  1 i p  i p i p i p i p (1 ) i p  (1 ) i p  (1 ) i p  (1 ) i p  , 1,0 i  (1 ) i p  , 0 i i p W , ,1 i m , , 0 i m , , 2 i m , , , 2
i m i m W  , , ,
1 i m i m W  , i i m p W , 0 1 i W Fig. 1.
Markov chain model for the priority i with the backoff window size

Block_Ack Mechanism

In IEEE 802.11e, a STA must receive an ACK frame to confirm a successful transmission. The Block_Ack is defined in order to reduce the channel wastes due to the ACK transmission. The Block_Ack mechanism improves channel efficiency by aggregating several ACKs into one frame. This mechanism allows a block of frames to be transmitted, each separated by a SIFS period, and to be acknowledged by a final aggregated ACK frame, which is called Block_Ack (B_ACK) frame as shown in Fig. 2. The Block ACK contains information about the reception of the whole block through a corresponding bitmap, and it is transmitted after an explicit transmitter makes a request, which is named Block ACK Request (BAR). In the B_ACK mechanism, the sender STA only contends for the channel access before the first frame of a block. If the STA wins the channel access, the STA sends out a whole block and a Block ACK Request frame and then waits for the Block ACK frame. Upon receiving the B_ACK frame correctly, the STA must defer a DIFS interval and a backoff process before sensing the channel again. At the same time, the other STAs should wait until the STA ends the B_ACK mechanism and then defer another DIFS interval before counting down their backoff counters for the next round of contention.

In general, the STA sends out a whole block of frames and a BAR frame. If the receiver STA detects a collision, the receiver STA will not send back the B_ACK frame. If the sender STA cannot receive the B_ACK frame, it must retry the transmission again. The saturation throughput is defined as the frame information in a slot time that is successfully transmitted in slot duration. There are four types of states in the B_ACK mechanism: 1) None of the STAs transmit at any time slot, i.e., the channel is idle. 2) Only one STA transmits at the time slot and the transmission is successful. 3) There is at least two STAs transmit at the same time slot, i.e., the channel has a collision. 4) There is at least one frame corrupted in a block, i.e., the channel has an error. We then can obtain that

      , , 1 1 , , , , , , , , , , , , 0 0 1 . (1 ) 1 [
                (12) , 2 ( ) ( ) ( ) ( 2)
.

i S i RTS CTS SIFS i L SIFS BAR SIFS BA i H T T T T N T T AIFS i T T T N T            (13) , , , 2 ( ) ( 1) , ( ) . i
C i RTS CTS SIFS i L SIFS BAR i H EIFS i EIFS i H BA SIFS T T T T N T T T N T T T T T AIFS i T              (14)
Where i N denotes the number of frames in a block. , Si T is the time of the whole block transmission due to a successful transmission for priority i class.  is the du- ration of an empty time slot.

Simulation Results

The Fig. 3 and Fig. 4 show the saturation throughput performances of different priority STAs using the RTS/CTS CSMA/CA scheme with/without the B_ACK mechanism under a non-ideal channel scenario. From the results, we can conclude that the STA with B_ACK mechanism got better performance than that without B_ACK mechanism because the B_ACK mechanism improves channel efficiency by aggregating several ACKs into one frame.

Conclusions

In this paper, we studied the backoff process characteristics of Markov chain model with RTS/CTS CSMA/CA scheme under non-ideal channel scenario. In order to increase the system throughput we integrated the B_ACK mechanism into the model. The model with the B_ACK mechanism under a channel error scenario can achieve a higher performance than that without the B_ACK mechanism due to fact that the model with the B_ACK mechanism is allowed to aggregate several ACKs into one frame.

  0jm  and m is the maximum backoff stage. The value of the backoff counter is uniformly chosen in the range  

Fig. 2 .

 2 Fig. 2. The B_ACK frame structure

  following simulation results have been obtained assuming the parameters are as follows: Frame payload = 1023 bytes, MAC header = 34 bytes, PHY header = 16 bytes, ACK = 14 bytes, RTS = 20 bytes, CTS = 14 bytes, SIFS = 20 us, DIFS = 50 us, propagation delay = 1 us, slot time = 20 us,

Fig. 3 .Fig. 4 .

 34 Fig. 3. Saturation throughput of the different priority STAs with the B_ACK mechanism

2 Enhanced DCF of IEEE 802.11e

	IEEE 802.11e EDCF is a new wireless technology which is an enhanced version of
	IEEE 802.11 DCF. It defines a new supplement to the existing IEEE 802.11 MAC
	protocol. The IEEE 802.11e EDCF aims at improving the capabilities and efficiency
	of the IEEE 802.11 MAC protocol by defining a new mechanism to support the QoS
	services.
	2

.1 IEEE 802.11e EDCF Scheme

	EDCF specifies four default access categories (ACs). Each STA contends for the
	channel access and independently starts its backoff depending on its associated AC.
	Each AC uses AIFS[AC], CW min [AC] and CW max [AC] instead of DIFS, CW min and
	CW max of the DCF [11].

  ]

	i S	N			s i p	i i L N P N T e i
	i p		s i p	e i P T S i	i p p T s i C i	RTS RTS e i e i p P T s i	CTS CTS e i e i P T	i L L i e i e i P T
		i				i


Huajian Mao

Hang Zhang

Xianqiang Bao

Nong Xiao

Weisong Shi

Yutong Lu
email: ytlu@nudt.edu.cnweisong@wayne.edu

EaSync: A Transparent File Synchronization Service across Multiple Machines

Keywords: file synchronization, multiple machines, deduplication, EaSync

In our daily life, people increasingly use multiple machines to do their daily work. As platform switching and file modification are so frequent ly that a way for file synchronization across multiple machines is required to make the files in synchronized. In this paper, we propose EaSync, a transparent file synchronization service across multiple machines. EaSync proposes several key technologies for file synchronization oriented service, including a timestamp based synchronization protocol, an enhanced deduplication algorithm DS-Dedup. We implement and evaluate the EaSync prototype syst em. As the result shown, EaSync outperforms other synchronization system in operation latency and other metrics.

Introduction

In our daily life, people increasingly use mult iple mach ines to do their daily work. They intermittently work on different platforms in different places, and nomad ically do their routine work like docu ment processing, presenting and so on. During the processing of the files on these machines, files may be created, read, modified and deleted which will make different mach ines have different views and versions of files and folders. As platform switching and file mod ification are so frequent that a way for file synchronization across mult iple mach ines will be required to make the files on different work platforms in synchronization.

With diving into how users typically process documents on multiple mach ines, we find that, the essential requirement for a convenience file synchronization service needs to be satisfied is that it should be pervasively accessible and transparent to the applications, and make nomad ic access with intermittent connection always latest guaranteed at any location. However, several challenging issues arise in file synchronizat ion across mult iple mach ines. First, data should be accessed at anywhere; ho wever, the network may be partit ioned or client may go offline. Second, service should keep working correctly with multip le clients; however conflicts always show up. Third, data consistency should be assured; however, network is always partitioned, and it is not easy to keep data consistency in the synchronization service across mu lt iple machines. Forth, synchronization service should be transparent to the applications in the client; however, most of the applications can only do local file operations.

Several new methods like Dropbox[1], UbuntuOne and DBank have been provided as a service for the Internet users. However, Dropbo x so metime does not synchronize the files very well, especially when you have multip le person share the files. A lso they are all close source project, especially at the server, where much mo re research issues and large scale data center challenges may be d iscovered. Also, they only work with the support of connection with their servers, wh ich means, when you only have a local area network connection, the file synchronization will fail, even if the connected machines are actually connected directly.

In this paper, we propose EaSync, a transparent file synchronization service across mu ltip le mach ines. EaSync enables users to store and sync files online and across mu ltip le co mputers. EaSync gives users the probability to work anywhere with the freshest data. This paper describes our experience fro m conception to imp lementatio n and evaluation. The main contributions presented in this paper are as follows: First, EaSync states the problem about the file synchronization across multip le mach ines and make an open source project for both client and server side. Second, several key designs for file synchronization oriented service are proposed in this paper. The designs include a dual-timestamp based synchronization protocol, an enhanced deduplication algorith m DS-Dedup for deduplication. Third, we imp lement and evaluate the EaSync prototype system. The experiment results show that EaSync outpe rforms the other platforms in many aspects.

The rest of this paper is organized as fo llo ws. We then outline the system model and design of EaSync in detail in Section 2, followed by th e implementation in Section 3. We show our experimental results in Section 4. Section 5 presents the prior related work. We conclude our paper and present the future work in Section 6.

Design of EaSync

EaSync includes four main co mponents which are EaSync Client, EaSync Gateway, MetaStore, and DataStore. Figure 1 is an overview of EaSync architecture. EaSync client consists of three components which are Local Update Observer (LObsvr), Remote Update Observer (RObsvr), and the synchronization daemon (Syncer). EaSync client runs synchronization protocol with the EaSync Gateway. The synchronization protocol will be discussed in Section 2.2. EaSync client monitors the file update on the client, and starts the synchronization to EaSync Server.

Gateway is the entry of EaSync service. It deals with the requests from both the EaSync clients and the web browser. In order to scale up, load balancing is considered. The main work of the gateway is to route the requests (with Logic Controller) to help the clients to fetch metadata fro m MetaStore (with a metastore manager instance) and data fro m DataStore (with a datastore manager instance). MetaStore manages all of the metadata information for the users. Also the synchronization log records are also managed in MetaStore. Another important co mponent in server side is the DataStore where all of the data are store.

Synchronization Protocol

We propose a hybrid timestamp based synchronization protoco l to keep the managed files in sync. In this protocol, t wo timestamps are used, one is the client -side timestamp as local t ime, and the other one is server-side one as a global timestamp.

The local time is used to record when the update is made, while the global one is used to record when the update is submitted to the EaSync server (by reading the gateway at server side system time). Figure 2 gives the steps of file synchronization between EaSync client and server. We describe this protocol in detail as following. L.1) The Lobsvr observes the mod ification of the candidate objects with the notificat ion mechanis m. And once an object is modified, client runs step L.2), which inserts a change log into a local to-be-synced pool, and marks the change type to be "changed by local". In this step, the local timestamp is recorded. After this, L.3) is executed by the Syncer. It reads the updates with type of "changed by local", and starts step L.4) to fetch the freshest data in local, and synchronizes it to the server with step L.5).

Fig. 2. Timestamp based synchronization protocol.

When the gateway receives an update request, L.6) it first starts conflict detection, and if no conflict happens, it then create an g lobal timestamp by read ing the server side clock, and updates the record in server side. In L.7), the server responses the EaSync client with the global timestamp, and the client record it in a local snapshot table. On the other side, R.1) The Robsvr periodically polls the server with a global timestamp, which is returned by the last polling, to fetch the change log on server to find which files are changed, and then R.2) inserts the change log batches into the tobe-synced pool, with setting the change type to be "changed by remote". At the meantime, the client will record the responded time as the next query time. Just like L.3) when the periodical Syncer daemon is executed, R.3) will be called. In this step, Syncer firstly query the to-be-synced pool to find the record sets where a remote synchronization is needed. Then Syncer literately runs R.4) and R.5). The former fetches the updated data from EaSync server and the later store them in local.

Consistency Model

It is co mmon that the network is always partitioned. Also, in some situation, the client even can only access the data in its own device. So it is not possible to maintain all the replications on different machines in a strong data consistency. In EaSync we provide an eventual consistency [START_REF] Vogels | Eventually consistent[END_REF] for the file synchronization. However, in the eventual consistency model, conflicts are unavoidable. To solve conflict problems, there are two key questions to be answered, and they are 1) when to discover the conflict, and 2) whose duty to resolve the conflict. For the first question, EaSync detects the conflict at the synchronization phase by the client. Basically, in a partitioned network there are two conflict forms: RAW (Read-After-Write) in which a client reads the value of a data item that is being concurrently updated by a second client, and WAW (Write-After-Write) in wh ich two clients update the same data item in incompatible ways.

For both of these two conflict types, we provide an optimistic strategy for conflicts detection: we accept all the user operations in the client and leave the conflict detection at the synchronization phase. When EaSync client starts to synchronize their data, it detects conflicts first. It firstly check whether there is a same file exists on the server side whose global update time is later than the last global update time stored in the client. If it is true, it means that some other clients have updated the data before this synchronization. In this situation, a WAW conflict is detected. RAW conflicts may happen in the eventual consistency schema too. For examp le, if client A updated some data, and before it is synchronized to the server, client B will not get the freshest data. This can also be resolved at the synchronization phase by either synchronizing the data in which client B does not update this file, or turning RAW conflict into WAW conflict in which client B updates the file. W ith this optimistic conflict detection strategy, EaSync can detect the conflicts at the synchronization phase.

After the conflicts are detected, we need to resolve these conflicts. As we analy zed in previous, the main conflict is the WAW conflict at synchronization phase. In detail, the problem is how to resolve the situation when there is a file whose update time is later than the last update time on the client. EaSync resolves these conflicts by creat-ing a new version on the server side with a suffix .t imestamp.clientname. After the EaSync client fin ishes its synchronization phase, the user will find the conflict ve rsions. EaSync leaves it to the users, relying on humans effort for resolving conflicts.

Optimization and Implementation

In the file synchronization service like EaSync, user data is always revised frequently. There will be a bundle of data which is very similar. If we split th e files into chunks, there will be a nu mber of same chunks fro m different files. In EaSync, we use a deduplication method at the client side. EaSync uses deduplication together with S-RSync [START_REF] Zhang | S-rsync: An efficient differencing algorithm with locally chunk digests generating for file synchronization services[END_REF] and we name this method as DS-Dedup. Figure 3 shows the overview of DS-Dedup. When a file is modified, EaSync will send a request to the DS-Dedup module to synchronize the data to serve. DS-Dedup serves EaSync request by the Intelligent chunker. It splits the data into chunks intell igently according to the frequent of file modification. DS-Dedup uses content defined chunking (CDC) to split for the frequently updated files, and static chunking (SC) for the files not frequently updated. After the file data is split into chunks, the ch unks enter into the AAplication-aware Deduplicator (AADedup) [START_REF] Fu | Aa-dedupe: An application-aware source deduplication approach for cloud backup services in the personal computing environment[END_REF]. AADedup controls the deduplication of DS-Dedup. When a chunk arrives, it first calculates the fingerprint, and searches in the Hash Fingerprints Repository. It the fingerprint of a chunk exists, AADedup will generate a point to the chunk data and stores it in the On Disk pointer List. This is done by Block Mapping Metadata Handler. Otherwise, if there is no fingerprint for the new co ming data chunk, AADedup will generate a new fingerprint by Hash Handler and add it to the Hash Fingerprints Repository. In order to synchronize data to the EaSync server side with S-Rsync differencing algorith m, an File Chunk Digests Container component is used in DS-Dedup to store the chunks informat ion including the chunk finger print of the file. When S-Rsync start to check the differences, it reads the chunk fingerprint info rmation and generate the differences with S-RSync algorith m. After that the difference is then transferred to the EaSync server side with S-RSync algorithm.

Evaluation

We set up an experimental platfo rm with 2 PCs and 1 laptop as EaSync clients and Panasas ActiveStor cluster for Gateway, MetaData and DataStore server. The clients and server are connected by a local area network. With this experiment platform, we evaluate EaSync as follows: First, we evaluate EaSync by comparing with an open source project named with iFolder. Second, we have evaluated the EaSyn c in the aspect of synchronization protocol, in wh ich we co mpare S -Rsync with Rsync. Finally, we evaluate the benefit and cost of deduplication.

Performance Comparison

In this section, we co mpare EaSync with iFolder for the operations latency of crea ting, updating, renaming and deleting. We have collected a set of workload which is used and modified in our daily work. We select operations on files with different sizes and different types. The sizes are about 50KB, 100KB, 500KB, 1M B, 5M B, 10M B, 50M B, 100M B, 500M B, 1GB. We do not present the latencies for files smaller than 50KB and files larger than 1GB. The latencies of EaSync and iFo lder for files smaller than 50KB are very close. Also, the files larger than 1GB are not common in our usage schema of file sy nchronization between different devices.

In the experiments, for creating operation, we put the files with different sizes into the folder wh ich are monitored by EaSync and iFolder, then we get the latencies as the creating operation latency. For updating operation, we modify the files by appending 1KB data to the files, and then record the latencies of data synchronization, and make these latencies as the updating latency. Figure 4 shows the latencies of different operations.

As the result shows, EaSync outperforms iFolder for most of the operations including create, update, rename and delete. The main reason for the larger latencies for create and update is that iFolder uses RSync synchronization algorith m to synchronize the differences of the files. While RSync will read data fro m the server first, then compare the data with that in client side. However, EaSync uses our proposed SRSync algorith m to do the operations, it reduces the cost a lot, as shown in the figure. Another informat ion included in the figure is that when the size of the file increases, the latencies of iFolder increases faster than that of our EaSync. In su mmary, compared to iFolder, EaSync outperforms in the operation latencies.

Effect of Ds-Dedup

EaSync uses deduplication to reduce the capacity and transmission cost. In this section we evaluate the effect of deduplication for EaSync. First, we evaluate the storage capacity used by a frequently revised file. We co mpare DS-Dedup with other strategies with different chunk size settings. As the deduplication method is dependent on the chunk size of file split. In our experiments, we uses static chunk split method with the chunk sizes of 0.5KB, 1.0KB, 1.5KB, and 2.0KB. Figure 5 shows the result of storage capacity used under different strategies. As the result shown, Rsync uses about 20.8M B fo r the storage capacity. However, S-Rsync uses a little b it mo re. This is mainly because of that S-Rsync needs to store the chunk digest information for the files. While as S -dedupe uses deduplication method for both the data chunks and the metadata, it costs the least space. For the same reason as S-Rsync to Rsync, DS-Dedup uses a little mo re space than S-dedupe because of the space cost of chunks digest information.

Fro m the result we can find that, comparing with the strategies with no deduplic ation methods, DS-Dedup and S-dedup is always better. DS-Dedup can reduce the storage cost to about half of that of Rsync and S-Rsync. Also, it can be found that the storage cost is dependent on chunk size. When deduplication is used, the chunk size should be selected carefully. In this experiment setting, 1.5KB is the best size for deduplication. Another benefit of client side deduplication comes fro m the transmission cost to synchronize the updated data to the server. As the redundancy of the data is deleted, EaSync only needs to transfer part of the whole data which is enough to reproduce the original data.

Related Work

EaSync shares several considerations with the other prior wo rks. Services like Dro pbox, UbuntuOne DBank, and Wukong [START_REF]Wukong: A cloud-oriented file service for mobile Internet devices[END_REF] are probably the closest existing work to our EaSync. We share the overall architecture, which is client-server based. However, EaSync is designed not only for the file synchronization service, but also for research purpose, which is designed to be an open source project. While the existing services like Dropbox, UbuntuOne are always close source projects, especially the server side design where much more research issues and large scale data center challenges may be discovered. So EaSync shares these services with similar ideas, but contains more values for research commun ity. EaSync also shares a lot of technologies and ideas with some synchronization methods, like Rsync [START_REF] Rasch | In-place rsync: File synchronization for mobile and wireless devices[END_REF][START_REF] Tridgell | The rsync algorithm[END_REF], and the version control services. However, most of the traditional synchronizers are invoked explicitly by an action fro m the user (issuing a synchronization co mmand, clicking the synchronization button, etc.), wh ile EaSync runs a background daemon and synchronize the updates a utomatically and transparently for the users. It definitely improves the user experience and eases the user's operations which may introduce unconscious errors. Differencing algorithm is an important technology in file synchronization service. Recently, there are some d ifferencing algorith ms aiming at special applicat ion or special occasion. Rsync [START_REF] Tridgell | The rsync algorithm[END_REF] is widely used for synchron ization, backup and recovery system. And there are also some other algorith ms adopting other consideration like, Delta-encoding. The work [START_REF]Potential benefits of delta encoding and data compression for http[END_REF] uses "delta" vcdiff [START_REF] Korn | The VCDIFF generic differencing and compression data format[END_REF] encoding way to improve perfo rmance of HTTP traffic. The algorith m vcdiff is one of the best delta encoding algorith ms. Every differencing algorithm has its own advantages on the reasonable size of difference or co mputing overhead, according to its special scene. Because of the simplicity and efficiency, Rsync is used widely in synchronization s ystem.

Conclusion

We present EaSync, a t ransparent file synchronization service across mult iple machines in this paper. EaSync characterizes itself with several unique features: First, it supports file synchronization in local area network environ ment. Second, it proposes several key technologies for file synchronization oriented service, including a dualtimestamp based synchronization protocol, DS-Dedup. Third, it explorers an open source implementation for research community.

Fig. 1 .

 1 Fig. 1. An overview of EaSync architecture.

Fig. 3 .

 3 Fig. 3. Overview of DS-dedup.

Fig. 2 .

 2 Fig. 2. Operation latencies.

Fig. 3 .

 3 Fig. 3. Storage capacity used.

Acknowledg ments. The authors would like to thank the anonymous reviewers for their co mments and kindly suggestions. This work is supported by the National Nat ural Science Foundation of Ch ina under Grant No. 60736013, Grant No. 61120106005, Grant No. 61025009 and Grant No. 60903040.


Qiuming Luo

Chenjian Liu

Chang Kong

Ye Cai
email: caiye@szu.edu.cn

MAP-numa: Access Patterns Used to Characterize the NUMA Memory Access Optimization Techniques and Algorithms

Keywords: Memory Access Patterns, NUMA, Benchmark, Oprofile

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

NUMA has been the source of performance problems for high performance computing on large scale distributed shared memory platforms for years. In these systems a processer core can access nearby memory faster than remote memory. To maximize the aggregate memory bandwidth all processes must simultaneously access data from their own local memory location. It means that multithreaded codes in NUMA platform should sustain sufficient locality of memory access and minimize access to remote data to obtain a high performance.

The importance of the data locality is well documented [START_REF] Zhang | Performance Prediction and Evaluation of Parallel Processing on a NUMA Multiprocessor[END_REF][2][3] [START_REF] Holliday | Performance Evaluation of Hierarchical Ring-Based Shared Memory Multiprocessors[END_REF] and there are some OS-provided NUMA APIs to control it [START_REF] Drepper | What every programmer should know about memory[END_REF][6] [START_REF] Ribeiro | Memory Affinity for Hierachical Shared Memory Multiprocessors[END_REF] [START_REF] Lameter | Local and remote memory: Memory in a Linux/NUMA system[END_REF]. Linux traditionally had ways to bind threads to specific CPUs/Cores and NUMA API extends that to allow programs to specify on which node memory should be allocated. Some more complicated APIs are based on these basic policies, such as MAi [START_REF] Ribeiro | Memory Affinity for Hierachical Shared Memory Multiprocessors[END_REF] and MaMI [START_REF] Broquedis | ForestGOMP: An Efficient OpenMP Environment for NUMA Architectures[END_REF].It is not an easy task to apply these API because it is much difficult to find the communication pattern in shared memory platform than message passing platform, because it is implicit and occurs through the memory accesses. Recently, some tools are available to guide a program developer on where to judiciously apply these API within a large parallel code [START_REF] Yang | Profiling Directed NUMA Optimization on Linux System: A Case Study of the Gaussian Computational Chemistry Code[END_REF][11] [START_REF] Cruz | Using Memory Access Traces to Map Threads and Data on Hierarchical Multi-core Platforms[END_REF]. But it is still a hard problem to find the best mapping of the access patterns, which is considered NP-Hard [START_REF] Diener | Evaluating thread placement based on memory access patterns for multi-core processors[END_REF]. [START_REF] Cruz | Using Memory Access Traces to Map Threads and Data on Hierarchical Multi-core Platforms[END_REF] used a heuristic algorithm to map threads and data on the machine based on the Edmonds matching algorithm [START_REF] Osiakwan | The maximum weight perfect matching problem for complete weighted graphs is in pc[END_REF]. [START_REF] Rodrigues | Multi-core aware process mapping and its impact on communication overhead of parallel applications[END_REF] presents a strategy which used the Dual Recursive Bipartition algorithm for process placement to reduce communication time of parallel applications that have a steady communication pattern on clusters of multi-core machines. [START_REF] Hursey | Locality-Aware Parallel Process Mapping for Multi-Core HPC Systems[END_REF] introduced the Locality-Aware Mapping Algorithm (LAMA) for distributing individual processes of a parallel application across the processing resources in an HPC system paying particular attention to on-node hardware topologies and memory locality.

But all those works are using the traditional test tools or benchmarks to evaluate their efforts. To our best knowledge, there are no benchmark dedicate to validate the various optimizations for memory access on NUMA platform. How to qualify and characterize an optimization technology or algorithm is still need further study. One benchmark that can tell how the memory locality leakage can be remedied by an optimization would be the answer. And this benchmark should be an abstraction of typical applications which is architecture independent. This is the motivation of MAPnuma (Memory Access Patterns for NUMA, short for MAP).

The rest of the paper is organized as follows. In section 2, we discuss related work. Section 3 focuses on MAP and the memory access patterns. In section 4 we present an application example of MAP in a NUMA optimization based on memory traces (obtained via Oprofile). Finally in section 5 the conclusion is drawn and some future work is discussed.

Related Work

There exist plenty of researches that focus on NUMA memory access optimization. They can be classified into three categories if the verification method is considered. Some of them use well-known benchmarks for high performance computing, some use a particular application, and some other use memory benchmarks.

Memphis [START_REF] Mccurdy | Memphis: Finding and Fixing numa-related performance problems on Multi-core platforms[END_REF] evaluated its effectiveness by applying the NPB (NAS Parallel Benchmarks), HYCOM (a production ocean modeling application), XGC1 (a production Fortran90 particle-in-cell code that models several aspects of plasmas in a tokamak thermonuclear fusion reactor) and CAM (the Community Atmosphere Model). MAi [START_REF] Ribeiro | Memory Affinity for Hierachical Shared Memory Multiprocessors[END_REF] used two kernels (FFT and CG) from NPB and ICTM [START_REF] Castro | NUMA-ICTM: A Parallel Version of ICTM Exploiting Memory Placement Strategies for NUMA Machines[END_REF]. SPLASH2, PARSEC and Advention (a part of the Brazilian Regional Atmosphere Modeling System) were used in [START_REF] Diener | Evaluating thread placement based on memory access patterns for multi-core processors[END_REF]. NPB is also used in [START_REF] Cruz | Using Memory Access Traces to Map Threads and Data on Hierarchical Multi-core Platforms[END_REF][16] [START_REF] Tudor | Understanding Off-Chip Memory Contention of Parallel Programs in Multicore Systems[END_REF]. They measured the runtime before and after the optimization with the well known scientific benchmarks to demonstrate their effectiveness.

The second category use particular applications other than using benchmarks. Gaussian computational chemistry code is used in [START_REF] Yang | Profiling Directed NUMA Optimization on Linux System: A Case Study of the Gaussian Computational Chemistry Code[END_REF]. H.264 video encoding code is used in [START_REF] Tudor | Understanding Off-Chip Memory Contention of Parallel Programs in Multicore Systems[END_REF]. Essentially, they are similar to the first category.

The last category try to setup some memory testing code customized to NUMA characteristic. ForestGOMP [START_REF] Broquedis | ForestGOMP: An Efficient OpenMP Environment for NUMA Architectures[END_REF] made some modification to STREAM benchmark. STREAM measures sustainable memory bandwidth and the corresponding computation rate for simple vectors. The first modification is called nested-STREAM, which creates the threads by two steps. The threads in outer parallelism create a team of threads in inner parallelism. Each team works on its own set of STREAM vectors. The other modification is called twisted-STREAM. It contains two distinct phases. The first one behaves exactly as nested-STREAM. During the second phase, each team works on a different data set instead the one it was given in the first phase. ForestGOMP also considered the irregular applications with imbalanced parallelism and derived a modified version call imbalanced-STREAM.

Using the well known high performance computing benchmarks can demonstrate the effectiveness of various optimizations to sustaining the memory locality on NUMA. And so do those particular applications. But it cannot give us more details about how and what the optimization really contributes, except the reduction of running time. Nested-STREAM, twisted-STREAM and imblanced-STREAM reveal some more details about how and what ForestGOMP help to improve the memory performance in these three different circumstances. Keeping that idea in mind, we are trying to figure out one set of code that can help to understand characteristics of various optimization techniques and algorithms.

MAP-numa

MAP is designed under some guide lines or objectives. First of all, it should represent the typical memory access patterns used in today's high performance computing, or it will be useless. Secondly, it should cover a wide range of applications. The third objective is to be capable of revealing different kinds of potential memory locality leakages, and to be able to characterize an optimization in various aspects. The forth objective is to achieve platform independence. And the last one is to limit the use of cache, or the NUMA effect will be conceal under the enormous cache hits.

Data set and Thread affinity

Most computing programs used 1D array, 2D matrix (2D array) or 3D cubic (3D array) as their work data set. MAP uses those types of data sets too. But what is more important is the relationship between the computing threads and the data subset they access.

The first type of data set used by MAP is 1D array and the access patterns include shared, divided, interleaved and partial shared. Fig. 1-(a) stands for the shared case, where all the threads share the entire array equally. The access sequence can be serialized of randomized. Fig. 1-(b) stands for the divided case, where each thread accesses the dedicated memory zone separately. Fig. 1-(c) stands for the interleaved case, where each thread accesses the entire memory area in an interleaved pattern. Fig. 1-(d) stands for the case between shared and divided, each thread accesses its dedicated memory and shares a portion of it with its neighbor. These access patterns should have cover most applications that using 1D array as their working data set.

Fig. 1. Data sets in MAP

For 2D matrix cases, the data set can be accessed in more patterns. If it is shared, the access sequence may be scanning in horizontally or vertically, or randomly. As for divided cases, it can be divided in horizontal, in vertical or in 2D mesh. All the patterns are drawn in Fig. 1-(

The STREAM benchmark uses four types of operations (COPY: a(i) = b(i), SCALE : a(i) = q*b(i) SCALE : a(i) = q*b(i), SUM : a(i) = b(i) + c(i) and TRIAD : a(i) = b(i) + q*c(i) ).While in MAP, the emphasis is NUMA memory access and the arithmetic operation should be eliminated. The basic operations (read, write and read/write) are chosen to perform without any arithmetic operations.

In order to achieve the objective of architecture independence, no architecture information is adopted in MAP. When programming MAP in C, it is completely based on the concept of one shared memory platform, and let the OS and compiler to handle the thread binding and data allocating. In order to eliminate the cache influence, each data element of the data set accessed by each thread is as big as one cache line. Each element in the array is padded by some blank field to make it long enough to occupy one cache line. Currently, MAP has two versions, which are programmed using pthreads library API and OpenMP directives respectively. The later one, OpenMP directive code, would be compiled by GCC with pthreads library or other thread library.

Application example

An application example is provided in this section to demonstrate the value of MAP. Some optimizations are applied to MAP and the physical patterns are captured for evaluation.

4.1

The NUMA Hardware platform

An HP 32-core NUMA platform is used as the test bed. Each 4 cores consists one memory node. 8 NUMA nodes are connected by HT. There are three different NUMA factors (relative latency values), 10 stands for native one, 16 and 22 stand for remove latency values.

4.2

The tuning steps based on Oprofile

In this example, the optimization adopts the memory trace scheme similar to [START_REF] Yang | Profiling Directed NUMA Optimization on Linux System: A Case Study of the Gaussian Computational Chemistry Code[END_REF] [START_REF] Diener | Evaluating thread placement based on memory access patterns for multi-core processors[END_REF]. By analyzing the memory trace, physical patterns (contrast to the logical access patterns) can be drawn and represented in memory access matrix or communication matrix [START_REF] Cruz | Memory-aware Thread and Data Mapping for Hierarchical Multi-core Platforms[END_REF].

On AMD Opteron, with the Instruction-Based-Sampling (IBS) [START_REF] Drongowski | Instruction-Based Sampling: A New Performance Analysis Technique for AMD Family 10h Processors[END_REF], it can provide the following information for sampled instructions that load data or store data.

The precise program counter of the instruction. The virtual address of the data referenced by the instruction. The physical address of the data referenced by the instruction. Only the samples with correct TID are kept and analyzed. Then they are classified into load and write categories. They are further labeled by node number according their physical address. The communication matrix is generated by accumulating the item with same source node and target node. The whole process is shown by Fig. 2.

Fig. 2. The optimization steps

The experiment results

Three optimization methods, Linux NUMA API functions, numactl command-line tools and rewriting the source code manually, are applied to MAP's 1D data set to make comparison. The following communication matrices (vertical axis represents the nodes ID that issue the accesses and the horizontal axis represents the accessed nodes ID, the darker means more accesses) are obtained by Oprofile sampling. For 1D shared pattern (Fig. 1-a), OS allocates the data without particular policy and with influence from other processes' memory allocation (Fig. 3, 1D-sh R/def and 1Dsh W/def). Because the allocation tends to take place in one node, the communication matrix is focus on one (or a few) node. While applying numactl command-line tools (with --interleave option) to binary executable file or NUMA API functions into source file, the matrix become more flattened(Fig3, 1D-sh R/CL, 1D-sh W/CL, 1D-sh R/API and 1D-sh W/API). For 1D divided pattern (Fig. 1-b), the default matrix (Fig. 3, 1D-div R/def and 1D-div W/def) still focus on one (or a few) node. Using numactl command-line tools (with --interleave option) can make the matrix more flattened (Fig. 3 1D-div R/CL and 1D-div R/CL). By adding NUMA API functions into source code, the matrix can be diagonalized (Fig. 3 1D-div R/API and 1D-div R/API), which means no memory locality leakage. For 1D interleaved pattern (Fig. 1-c), default allocation remains. But this time, API functions have the same result as numactl command-line tools. They both flatten the matrix. If manually modify the code and applying NUMA API functions, a diagonal matrix can be obtained (Fig. 3 1D-int R/M and 1D-int W/M). Fig. 4 give the execution time of all the cases mentioned above, which make the effectiveness of these optimization obvious. From the experiment results, we can distinguish the abilities of different optimization methods. The OS tends to allocate memory on one node and then move to another node, which will give rise to the memory contention and become a bandwidth bottleneck. The numactl command-line tools can deal with 1D-shared and 1D-divided (not perfectly), but fail to handle 1D-interleaved and multi-patterns cases. NUMA API can handle 1D-shared, 1D-divided and multi-patterns. If source code can be rewritten manually, all the patterns can be handled nicely.

1D-sh R / def 1D-sh R / CL 1D-sh R / API 1D-sh W / def 1D-sh W / CL 1D-sh W / API 1D-div R / def 1D-div R / CL 1D-div R / API 1D-div W / def 1D-div W/ CL 1D-div W / API 1D-int R / def 1D-int R / CL 1D-int R / API 1D-int R / M 1D-int W / def 1D-int W / CL 1D-int W / API 1D-int W / M
The change of the matrices (physical patterns) reveals the remedy of locality leakage. If a matrix with large number focus on one or a few columns was converted to a more flat matrix, which means the potential memory bandwidth bottleneck is removed. If a matrix with large number focus on one or a few rows was converted to a more flat matrix, which means the threads are distribute to more nodes and improving the parallelism. If an evenly distributed matrix is converted to a diagonalized matrix, it means the best placement is achieved where there is no remote memory access.

So, we used MAP is applicable to the source code methods as well as the methods modify binary executable file. The optimizations made by manually coding, or with the help of compiler, don't make any difference when being evaluated. So MAP is good start point of a general purpose benchmark to evaluate all kinds of optimizations.

As future work,we intend to profile some real world parallel applications to get the memory access patterns ,which are contained by our MAP access patterns.Further more,we can use the proper way described in Table 1 to optimize the applications.

  e)~(i). The 3D array in MAP is accessed in three fashions shown as Fig. 1-(j)~(l).

Fig. 3 .

 3 Fig. 3. Communication matrices of MAP-numa before and after the optimizations (1D stands for 1D data set, sh/div/int stand for shared/divided/interleave, R/W stands for read or write, def/CL/API/M stand for default/command line tools/NUMA API functions/Manually rewrite)

Fig. 4 .

 4 Fig. 4. Execution time of default/CL/API/M methods on MAP's 1D data set

Table 1 .

 1 table 1 to summarize their ability. It is hard to compare two optimizations, if they are only applied to one particular application. Instead, MAP consists of various typical access patterns and is able to verify whether (and what) locality leakages can be remedied by an optimization method. Actually, Table 1 can have more details if all the patterns are applied. Abilities of nuamctl, NUMA API and rewrite manually methods

	default 1D-divided ×	√	√	√
	1D-interleaved	×	×	×	√
	multi-patterns	×	×	√	√

Acknowledgements

This work was supported by the project (NO. 2011A090100037) funded by Guangdong Province and Chinese Academy of Sciences, and the project funded by State Key Laboratory of Computer Architecture,ICT,CAS.


Zhiming Zhao

Paola Grosso

Cees De Laat

OEIRM: An Open Distributed Processing based Interoperability Reference Model for e-Science

Keywords: e-Science, Open Distributed Processing, Interoperability, Cloud, Grid

E-Science applications are often interdisciplinary and require resources from different infrastructures; the interoperability between heterogeneous infrastructures is an important requirement for constructing large scale experiments. Analyzing interoperability issues by including both application and infrastructure aspects promotes a global view on interoperability of different layers, and we argue it can converge to an optimal reference model to guide the development of service layers in e-Science infrastructures. This paper proposes an Open Distributed Processing based interoperability reference model for e-Science.

Introduction

E-Science applications are characterized by big data and interdisciplinary approaches, and require not only large computing and storage capacities, but also effective cooperative computing model to handle the application complexity [START_REF] Francis | Big data[END_REF]. Collaborating different infrastructures essentially enable the construction of large scale experiments; however, the technical diversities between infrastructures often make such collaboration difficult, and the service layer interoperability between different infrastructures has been highlighted as a key functional requirement [START_REF] Geraci | IEEE Standard Computer Dictionary: Compilation of IEEE Standard Computer Glossaries[END_REF].

Historically, e-Science infrastructures are often developed for specific application domain(s); the diverse application requirements result in different focuses on the infrastructure services. Even started with homogenous architecture, the evolution of technologies may still push the infrastructure upgrade towards different directions. Therefore, the interoperability between different infrastructures and the compatibility with the legacy applications from the early infrastructures will remain as a requirement in e-Science for a long term [START_REF] Charalabidis | Introduction to cloud infrastructures and interoperability minitrack[END_REF]. Many of the existing interoperability solutions focus on specific layers in the context e-Science: between infrastructures [START_REF] Ngan | Enabling interoperability across heterogeneous semantic web services with owl-s based mediation[END_REF][START_REF] Arcieri | A layered it infrastructure for secure interoperability in personal data registry digital government services[END_REF], between middleware [START_REF] Blair | Emergent middleware: Tackling the interoperability problem[END_REF], and between workflows [START_REF] Zhao | Using jade agent framework to prototype an e-science workflow bus[END_REF], and typically via iterative steps: building adapters or connectors between two infrastructures and then deriving new service layer models for standardization via certain community efforts. Such iterations can continuously promote the evolution of standards for infrastructures and the above service layers, but will not completely solve the interoperability problems when the diversity between infrastructures and the missing links between standards remain [START_REF] Riedel | Interoperation of worldwide production e-science infrastructures[END_REF]. Providing interoperability solutions only at a specific layer without a global view of the entire e-Science context hampers the convergence of service layer evolution. An interoperability reference model is needed to complement the model of the application and infrastructure [START_REF] White | Understanding interoperable systems: Challenges for the maintenance of soa applications[END_REF].

In this paper, we propose an interoperability reference model to analyze related issues and review the existing solutions in e-Science. We discuss how the interoperability issues should be handled in the context of the application life-cycle. The research is conducted in the context of EU F7 project ENVRI [START_REF]EU 7th framework programme. Common operations of environmental research infrastructures[END_REF].

An Open Distributed Processing based reference model

The Open Distributed Processing (ODP) model captures the design and development issues in complex distributed systems into five viewpoints, namely enterprise, information, computational, engineering and technology [START_REF] Linington | Building enterprise systems with ODP[END_REF]. Although it is originally developed in the enterprise IT context, its decomposed view on system design and development contributes valuable model for analyzing the interoperability in e-Science. Following the ODP methodology, we highlight five viewpoints in analysing the interoperability in the e-Science context: scientific, information, computational, middleware and infrastructure, as shown in Fig. 1. In the next section, we will review the available solutions of the interoperability using this model.

Scientific interoperability (Enterprise viewpoint) -Scientific problem -Approach

Information interoperability (Information viewpoint)

Interoperability in e-Science: from infrastructure to application

The five viewpoints proposed in Fig. 1 model the interoperability related issues not only in the service layers in infrastructure but also the characteristics of scientific domain and applications.

The scientific interoperability

From the scientific viewpoint, e-Science activities often require technologies or software components originally developed by different domains. The interoperability between different scientific domains and disciplines has been highlighted as the basic approach in e-Science. For instance, modeling and simulation based computing methods extend traditional laboratory based experimental sciences such as chemistry, physics and finance [START_REF] Cassel | Interdisciplinary computing is the answer: now, what was the question?[END_REF][START_REF] Smarkusky | An interdisciplinary approach in applying fundamental concepts[END_REF], and semantic web technologies have been promoted as basis for building information models and system integration in large collections fields [START_REF] Vattan | Semantically annotating research articles for interdisciplinary design[END_REF]. Moreover, many simulation models have also exhibited their power in different contexts, for instance finite element simulation model shows its strong power not only in fluid dynamics but also in studying financial problems [START_REF] Qiu | Understanding the complex dynamics of stock markets through cellular automata[END_REF]. In specific fields, the BRIDGE project aims at the distributed optimization using different simulation models and cross both ChinaGrid and EU SIMDAT [START_REF] Wang | Cross-domain middlewares interoperability for distributed aircraft design optimization[END_REF]. These types of interoperability comprises of the basis of the interdisciplinary activities in e-Science.

The information interoperability

The information interoperability refers to not only data content but also meta metadata, information models and all kinds of descriptions of the services that e-Science applications need. The solutions can be roughly classified into two groups. The first one is to map diverse information models using connectors, for instance the Advanced Resource Connector ARC between EGEE and NorduGrid [START_REF] Ellerta | Advanced resource connector middleware for lightweight computational grids[END_REF]. Semantic level interoperability enables the data exchange at the meta level, for instance the Linked Open Data principles proposed by the EU environmental sciences is for sharing scientific data [START_REF] Hausenblas | Utilising linked open data in applications[END_REF], semantic web services based mediators [START_REF] Ngan | Enabling interoperability across heterogeneous semantic web services with owl-s based mediation[END_REF], and semantic information preprocessing framework [START_REF] Zhao | Resource discovery in large scale network infrastructure[END_REF]. The second one is to synchronize diverse information representation mechanisms to one common model, for instance OGF promotes a solution named Grid Laboratory Uniform Environment (GLUE) [START_REF] Field | Grid information system interoperability: The need for a common information model[END_REF]. TPT (Taiwan prescription template) is an information level interoperability solution proposed by Kuo to enable the medical exchange among different infrastructure, and is promoted as the standards for improving the patient information [START_REF] Kuo | An interoperability infrastructure with portable prescription for improving patient safety -the framework of a national standard in taiwan[END_REF]. The information interoperability potentially realizes the semantic level information exchange between different e-Science domains.

The computational interoperability

From the computational viewpoint, 1) the application can be interoperable with the others by sharing and exchanging the intelligence in e-Science applications, i.e. the composition of the application logic 2) the execution engine of the application can be interoperable to execute applications from the other engines. Currently, the scientific workflow management systems from scientific computing context, and the MapReduce related Cloud computing model from large internet companies such as Google are two main forces pushes the evolution of the cooperative computing model. Although aiming at different types of data and application contexts, these two models merging from different perspectives to get benefits from each other, for instance MapReduce is included as an execution model in Kepler [START_REF] Kuo | An interoperability infrastructure with portable prescription for improving patient safety -the framework of a national standard in taiwan[END_REF], or DAG is include in MapReduce to extend its flow control [START_REF] Budiu | Dryadopt: Branch-and-bound on distributed data-parallel execution engines[END_REF]. Workflow bus was proposed to realize engine level interoperability between different systems [START_REF] Zhao | Vle-wfbus: a scientific workflow bus for multi e-science domains[END_REF]. The computational interoperability focuses on the runtime issues of the e-Science applications.

The middleware interoperability

The middleware interoperability refers to cross invocation of services among different service layers, and mainly deals with the diversity between middleware in invoking services, in managing data involved by the service invocation. Typical approach is to provide a gateway node to map the invocation interface of both sides. Wang proposed a gateway between the submission tool in gLite and the CNGrid GOS environment, and a scheduler decides the jobs from the gateway queue to middleware of which side [START_REF] Wang | Interconnect egee and cngrid einfrastructures through interoperability between glite and gos middlewares[END_REF]. Another way to solve such interoperability issues is to adopt a standardized service interface for job submission, storage and network management; OGF promoted a standards named HPC basic profile (HPCBP) towards this direction [START_REF] Ruiz-Alvarez | Bes++: Hpc profile open source c implementation[END_REF]. Web services interoperability (WS-I) is another initiative to promote the interoperability for the web service stacks [START_REF] Schoenberger | Has ws-i's work resulted in ws-* interoperability? Web Services[END_REF], although it faces several challenges to commit is final mission. An important problem that in the middleware interoperability is how to efficiently utilize the resources from different domains after the middleware interoperability has been enabled. Saga deals with the load balance issue in this context by proposing a HPCBP gateway, so that the jobs from other infrastructures will be checked against the allocation table of the local infrastructure scheduler with certain load balance constraints [START_REF] Kazushige | Mutual job submission architecture that considered workload balance among computing resources in the grid interoperation[END_REF]. The Grid meta scheduler (GMS) can schedule computing tasks of workflows among several middleware gLite, Unicore and Globus environments, but mainly batch and job farming based tasks [START_REF] Mirto | A grid meta scheduler for a distributed interoperable workflow management system[END_REF]. GridARS is another example but focuses on reserving the resources among different infrastructures [START_REF] Takefusa | Gridars: a grid advanced resource management system framework for intercloud[END_REF].

The infrastructure interoperability

From the infrastructure viewpoint, distributed resources have been aggregated and virtualized as different stack of services; from Clusters, Grids and Clouds. There are several standardization initiatives for Cloud models, for instance Open Cloud Computing Interface(OCCI) [START_REF]Open cloud computing interface infrastructure[END_REF], Open Virtualization Format [START_REF]Distributed management task force. Open virtualization format specification[END_REF], and Cloud data management interface (CDMI) [START_REF]Storage networking industry association[END_REF]. Moreover, whole organization related issues such as management policies for sharing data and resources, including authorization, authentication and accounting issues are included, for instance security level interoperability [START_REF] Cantor | Assertions and protocols for the oasis security assertion markup language[END_REF][START_REF] Moses | extensible access control markup language[END_REF], using model checking approach to verify the policies and rules [START_REF] Maarabani | Verification of interoperability security policies by model checking[END_REF].

Table . 1 summarizes the existing work in one table.

Table 1. Interoperability in e-Science.

-Authentication/Authrization/Accounting: SAML, X.509 [START_REF] Cantor | Assertions and protocols for the oasis security assertion markup language[END_REF][START_REF] Moses | extensible access control markup language[END_REF], XACML [START_REF] Maarabani | Verification of interoperability security policies by model checking[END_REF] -OCCI [START_REF]Open cloud computing interface infrastructure[END_REF], OVF [START_REF]Distributed management task force. Open virtualization format specification[END_REF], CDMI [START_REF]Storage networking industry association[END_REF] -Authentication/Authorization/ Accounting/Security/Policy -Infrastructure model

Infrastructure interoperability

-Gateway based protocol mapping [START_REF] Wang | Interconnect egee and cngrid einfrastructures through interoperability between glite and gos middlewares[END_REF] -HPCBP [START_REF] Ruiz-Alvarez | Bes++: Hpc profile open source c implementation[END_REF], WS-I [START_REF] Schoenberger | Has ws-i's work resulted in ws-* interoperability? Web Services[END_REF] -GridARS [START_REF] Takefusa | Gridars: a grid advanced resource management system framework for intercloud[END_REF], GMS [START_REF] Mirto | A grid meta scheduler for a distributed interoperable workflow management system[END_REF],

-Cross data access -Cross job submission -Cross infrastructure load balance

Middleware interoperability

-MapReduce in Scientific workflow [START_REF] Kuo | An interoperability infrastructure with portable prescription for improving patient safety -the framework of a national standard in taiwan[END_REF], flow control in MapReduce [START_REF] Budiu | Dryadopt: Branch-and-bound on distributed data-parallel execution engines[END_REF] -Runtime engine: Workflow bus [START_REF] Zhao | Vle-wfbus: a scientific workflow bus for multi e-science domains[END_REF],

-Joint computing model -Runtime embedding -cross invocation

Computational interoperability

-Community based ontology framework, Linked Open Data [START_REF] Zhao | Using jade agent framework to prototype an e-science workflow bus[END_REF] -Ontology mapping , Semantic based information preprocessing [START_REF] Zhao | Resource discovery in large scale network infrastructure[END_REF], ARC [START_REF] Ellerta | Advanced resource connector middleware for lightweight computational grids[END_REF], Semantic Web Services mediators [START_REF] Ngan | Enabling interoperability across heterogeneous semantic web services with owl-s based mediation[END_REF], -Standardized information model, GLUE [START_REF] Zhao | Resource discovery in large scale network infrastructure[END_REF], TPT [START_REF] Field | Grid information system interoperability: The need for a common information model[END_REF],

-Scientific data -Resource description, meta data, information model

Information interoperability

-Problem to large system scale, and involve different domains. Interdisciplinary optimization, Bridge project [START_REF] Wang | Cross-domain middlewares interoperability for distributed aircraft design optimization[END_REF].

-Computational sciences in many fields [START_REF] Cassel | Interdisciplinary computing is the answer: now, what was the question?[END_REF][START_REF] Smarkusky | An interdisciplinary approach in applying fundamental concepts[END_REF] Simulation models extended to different fields [START_REF] Qiu | Understanding the complex dynamics of stock markets through cellular automata[END_REF] -Scientific problems -Scientific methods

Scientific interoperability

Approach and examples Involved issues -Authentication/Authrization/Accounting: SAML, X.509 [START_REF] Cantor | Assertions and protocols for the oasis security assertion markup language[END_REF][START_REF] Moses | extensible access control markup language[END_REF], XACML [START_REF] Maarabani | Verification of interoperability security policies by model checking[END_REF] -OCCI [START_REF]Open cloud computing interface infrastructure[END_REF], OVF [START_REF]Distributed management task force. Open virtualization format specification[END_REF], CDMI [START_REF]Storage networking industry association[END_REF] -Authentication/Authorization/ Accounting/Security/Policy -Infrastructure model

Infrastructure interoperability

-Gateway based protocol mapping [START_REF] Wang | Interconnect egee and cngrid einfrastructures through interoperability between glite and gos middlewares[END_REF] -HPCBP [START_REF] Ruiz-Alvarez | Bes++: Hpc profile open source c implementation[END_REF], WS-I [START_REF] Schoenberger | Has ws-i's work resulted in ws-* interoperability? Web Services[END_REF] -GridARS [START_REF] Takefusa | Gridars: a grid advanced resource management system framework for intercloud[END_REF], GMS [START_REF] Mirto | A grid meta scheduler for a distributed interoperable workflow management system[END_REF],

-Cross data access -Cross job submission -Cross infrastructure load balance

Middleware interoperability

-MapReduce in Scientific workflow [START_REF] Kuo | An interoperability infrastructure with portable prescription for improving patient safety -the framework of a national standard in taiwan[END_REF], flow control in MapReduce [START_REF] Budiu | Dryadopt: Branch-and-bound on distributed data-parallel execution engines[END_REF] -Runtime engine: Workflow bus [START_REF] Zhao | Vle-wfbus: a scientific workflow bus for multi e-science domains[END_REF],

-Joint computing model -Runtime embedding -cross invocation

Computational interoperability

-Community based ontology framework, Linked Open Data [START_REF] Zhao | Using jade agent framework to prototype an e-science workflow bus[END_REF] -Ontology mapping , Semantic based information preprocessing [START_REF] Zhao | Resource discovery in large scale network infrastructure[END_REF], ARC [START_REF] Ellerta | Advanced resource connector middleware for lightweight computational grids[END_REF], Semantic Web Services mediators [START_REF] Ngan | Enabling interoperability across heterogeneous semantic web services with owl-s based mediation[END_REF], -Standardized information model, GLUE [START_REF] Zhao | Resource discovery in large scale network infrastructure[END_REF], TPT [START_REF] Field | Grid information system interoperability: The need for a common information model[END_REF],

-Scientific data -Resource description, meta data, information model

Information interoperability

-Problem to large system scale, and involve different domains. Interdisciplinary optimization, Bridge project [START_REF] Wang | Cross-domain middlewares interoperability for distributed aircraft design optimization[END_REF]. -Computational sciences in many fields [START_REF] Cassel | Interdisciplinary computing is the answer: now, what was the question?[END_REF][START_REF] Smarkusky | An interdisciplinary approach in applying fundamental concepts[END_REF] Simulation models extended to different fields [START_REF] Qiu | Understanding the complex dynamics of stock markets through cellular automata[END_REF] -Scientific problems -Scientific methods

Scientific interoperability

Approach and examples Involved issues

Related work

Interoperability has been recognized as a key issue in different contexts, and several reference models have been proposed. Riedel proposed an Infrastructure Interoperability Reference Model (IIRF) [START_REF] Riedel | e-science infrastructure integration invariants to enable htc and hpc interoperability applications[END_REF], which is now in the OFG community effort. The main idea of the IIRF is to fill the missing links between the existing earlier interoperability related middleware or standards, in particular the interoperability between infrastructure for High performance computing and high throughput computing. Open Grid Forum set up a working group called Grid Interoperability Now! (GIN) [START_REF] Riedel | Interoperation of worldwide production e-science infrastructures[END_REF]. The IIRF focuses on the different standards in the existing Grid middleware; however, its basic concepts are compatible with model presented in this paper.

Summary

The research presented in this paper is conducted in the context of the EU ENVRI project; we aim at an interoperability model for promoting the resource sharing among infrastructures from different environmental science domains [START_REF]EU 7th framework programme. Common operations of environmental research infrastructures[END_REF]. Using the Open Distributed Processing (ODP) model, we proposed an interoperability reference model named OEIRM, and analyzed the interoperability issues in the life cycle of e-Science applications using five different viewpoints of the model.

The diversity of the scientific domains drives the interdisciplinary research in e-Science from various angles; solving the diversity by providing interoperability support only promotes the evolution of scientific domains and all kinds of support technologies, but will not eventually remove such diversity. From this point of view, interoperability will be a continuous problem exists in the e-Science context. Different interoperability technologies as we see from the above analysis play a central role in enabling the collaborations in different contexts, but they also raises a challenge problem for the e-Science researchers: how we should deal with the interoperability issues in an evolutionary vision of the infrastructure and e-Science applications? As the next step, we will develop the reference model to guide the development of future e-Science application and service layers of infrastructures.

Fig. 1 .

 1 Fig. 1. An Open e-Science Interoperability Reference Model (OEIRM).

workflow e-Science Interoperability

		Computational interoperability
		(Computational viewpoint)
	-Meta data -Data schema -Information model	-Process modelling -Computing model -Application logic /
	Middleware interoperability	Infrastructure interoperability
	(Engineering viewpoint)	(Technology viewpoint)
	-Software management	-Providers (Virtual/Physical)
	-Storage management	-Authorization/Authentication/
	-Computing task management	Accounting
	-Network management	-Policy

Acknowledgments. We would like to thank the FP7 EU funded Integrated project ENVRI project (project number 283465) and the Dutch national and education network SURFnet, through the GigaPort Research on Network (RoN) project for sponsoring this research..