Min Zhu
email: zhumin@csnet1.cs.tsinghua.edu.cn

Ke Xu
email: xuke@csnet1.cs.tsinghua.edu.cn

Qi Li
email: liqi@csnet1.cs.tsinghua.edu.cn

Access Path based Source Address Validation in Mobile IPv6

Mobile IPv6 runs high risk of being attacked by IP spoofing due to the introduction of mobility and route optimization. In this paper, an authentic IP address validation scheme is proposed to protect mobile nodes in Mobile IPv6 against IP spoofing attack. The mobile nodes' historical traffic information is leveraged to validate the authenticity of its claimed home address in the scheme. Compared with other authentication schemes, this scheme is much simpler to implement and easier to deploy based on the usage of real data, and does not require additional computational overhead. It also solves the address ownership problem and the unauthenticated binding update issue in Mobile IPv6. Real traces are used to demonstrate the applicability of the scheme in this paper. The experimental results show that only three consecutive historical packet records are required to construct a unique authentication key, which can identify forged home address efficiently.

Introduction

As an enhancement to IPv6, Mobile IPv6 provides more flexible and open communication with support of the binding update protocol and the route optimization protocol, which allows mobile nodes to roam freely in the network with two addresses [START_REF] Johnson | Mobility support in ipv6[END_REF]. When the mobile node is in the home subnet, it is identified by its home address. When it moves to a foreign subnet, it obtains a new address as care of address. The key point of mobile node is to notify the home agent and the correspondent node its current care of address in a reliable and timely way through binding update request.

However, exploiting the security vulnerability of unauthenticated binding update, an attacker can masquerade as a mobile node (MN) and send a binding update request to the home agent (HA) and the correspondent node (CN) easily [START_REF] Mankin | Threat models introduced by mobile ipv6 and requirements for security in mobile ipv6[END_REF]. As IP address plays an important role in Internet, it is a disaster if such request is trusted and accepted: the normal traffic direction in the network will be changed, and the network resources will be consumed. Moreover, the victim's confidential information may be stolen [START_REF] Elgoarany | Security in mobile ipv6: a survey[END_REF]. Obviously, mechanisms to authenticate the identity of the mobile nodes are crucial to network communication and management.

The IETF has proposed IPsec [START_REF] Arkko | Using ipsec to protect mobile ipv6 signaling between mobile nodes and home agents[END_REF] and return routability (RR) [START_REF] Johnson | Mobility support in ipv6[END_REF] mechanism to verify the identity of the mobile nodes. Some cryptography-based mechanisms with the mobility support such as AIP [START_REF] Andersen | Accountable internet protocol(aip)[END_REF] and CGA [START_REF] Aura | Cryptographically generated addresses(cga)[END_REF] have also been proposed to generate accountability address in order to verify the identity of the source address. But these mechanisms have not been widely applied yet, because of their computation complexity, heavy storage overhead and long communication latency. As a result, further studies on source address validation in Mobile IPv6 are strongly needed.

The main reason behind the success of masquerade attack in Mobile IPv6 is that the home agent and the correspondent node cannot determine the ownership of the address claimed by the mobile node with unauthenticated binding update. If the mobile node can prove its identity after its move, the masquerade attack can be distinguished. SAVA [START_REF] Wu | A source address validation architecture (sava) testbed and deployment experience[END_REF][START_REF] Wu | Source address validation: Architecture and protocol design[END_REF] is the first method that proposed authentic source IP address. SAVA guarantees address authenticity in a hierarchical way. First, it completes the source address validation in local subnet by exploiting the dynamic binding relationship between the switch port and the valid source IP address. Second, it completes authentication at Intra-AS level through the ingress/egress filtering. Finally, it completes Inter-AS source address validation by alliance. SAVA has currently been deployed in CNGI-CERNET2 1 , which is a large-scale pure IPv6 backbone. However, SAVA does not consider the authentic source IP address issue in Mobile IPv6. Our work is an extension of SAVA, and we will solve the authentic source address validation problem in Mobile IPv6 in this paper.

Identity authentication is not unique to network security, but exists in our daily life. For example, in credit cards customer service, some authentication questions will be asked to verify our identity, such as credit card number, home address, phone number, and the amount of recent consumption. These information together forms a key for a certain card holder. Following the same logic, our study attempts to address the following questions:

-Is there any information only known to the mobile node and the home agent or correspondent node that can be used to verify the node's identity? -How does a mobile node use such information to signal its ownership of an IP address? -How to determine the effectiveness of the authentication information?

In this paper, we try to extract authentication information from historical traffic generated by users (or end hosts/nodes). This is possible because users' traffic is private and very diverse in certain dimensions. For example, our analysis of the data collected from DragonLab 2 (Dataset 1 described in Section 5) suggests that different users access the Internet at different time and sequence (Section 2). The result shows that although 67.11% of the access behaviors are concentrated on only 2 of the 21 monitored destinations, the online activities of different users actually happen at very different times and in very different sequences. As a result, users in Dataset 1 need no more than two consecutive packets to differentiate themselves from each other. If the mobile node can tell when and what it has done correctly, its identity can be verified.

Such evidence allows us to propose an authentic source address validation scheme in Mobile IPv6 based on the historical traffic of the mobile nodes. To implement this scheme, we first collect the mobile nodes' traffic at both the home agent and the mobile node, and then construct the consecutive packets of each mobile node in time as access path. We also employ some storage techniques to strengthen the security of the access path to defend against the eavesdropped traffic used by the attackers. Such access path can serve as authentication key to validate the ownership of the home address claimed by the mobile node after its move (Section 3). Theoretical analysis on performance shows that our scheme has light overhead and is able to complete the source address validation in a secure way(Section 4). Our experimental results with real traces demonstrate that the access path with only three consecutive packets can differentiate a mobile node in a subnet completely under reasonable settings (Section 5). Our scheme has the following advantages:

-Accountability: The mobile node can prove the ownership of its claimed home address efficiently using access path generated from its historical traffic. -Light overhead: Without using cryptography, our scheme has no computational overhead. It has light storage overhead also because it needs a few packets for validation. -Easy to implement: Leveraging the real traffic generated in the network, the implement and the deployment of the scheme is easy. Minimum data collection is required in this scheme.

The rest of the paper begins with the motivation for our research in Section 2. Section 3 describes the trustable communication architecture in Mobile Ipv6, the construction of the access path, and the source address authentication details. The performance and security analysis of our scheme are presented in Section 4. The applicability of the scheme is demonstrated in Section 5 with real traces. Section 6 introduces related work. Section 7 concludes the paper.

Problem Statement

Since it is a complicated and daunting task to generate a key to complete authentication with cryptography and PKI's support, we look for alternative ways in this paper.

As is commonly known, numerous historical traffic will be generated in the network when the nodes access the Internet. However, only information that satisfies the three criteria of privacy, uniqueness and anti-replay attack ability can be used for the authentication purpose. Our mission in this paper is to extract information from the historical traffic to generate the authentication key satisfying above three criteria.

Since it is impossible for attackers to monitor the network all the time, we can assume that the traffic is only known to the nodes that send it and the devices that collect it. Even though some traffic may be eavesdropped by attackers, we can use some techniques to make them useless to attackers. In essence, we assume that the traffic information is not known to attackers in authentication.

It is a great challenge to ensure the uniqueness of the authentication key generated from the historical traffic because the traffic of different nodes can be same at the same time. However, our analysis based on real traces reveals that online activity differences always occur among individual users even though they may behave exactly the same at some time (Figure3 and Figure 8). For example, only 1.81% of 2856 users in Dataset 1 have exactly the same access behavior at some particular point of time, and all the nodes can be differentiated with access behaviors of two visits. Therefore, it is feasible to construct a unique authentication key according to time (access sequence) and space (packet composition information) properties of the traffic.

The ability of anti-reply attack is important to validation because attackers may eavesdrop the traffic in the network. In general, there are two classes of methods to protect the authentication key. One is using encryption, and the other is generating a new key whenever it is needed. The volume of the traffic information in the network allows us to take the second approach because the nodes usually generate a large number of packets every day.

In summary, it is possible to construct authentication key from mobile nodes' historical traffic that satisfying the three criteria of privacy, uniqueness, and antireply attack ability.

Access Path based Trust Communication Architecture in Mobile IPv6

The purpose of this paper is to validate the home address claimed by the mobile node using its historical traffic after its move. There are three important issues to address. The first is what traffic we should collect, where to collect it and how to store it for easy access. The second is how to construct the authentication key. And the third is how to validate the home address of the mobile node according to the authentication key. We discuss these issues in this section. Figure 1 presents our trustable communication architecture based on mobile nodes' historical traffic information. It consists of two modules. The first one is collecting module, which resides in the home agent and the mobile node. This module decides what information to collect and how to store it. The second one is communication module. This module accomplishes the mobile nodes' authentication after its move. It involves binding update authentication both to the home agent and to the correspondent node. We elaborate on the function of each module below.

Overview

Information Collecting and Recording

As the basis of our scheme, traffic collection is a crucial part in our study. We think that the best location to collect and record the traffic is the home agent and the mobile node because of their positions. Packet is chosen as the collection unit because it is easy to collect by both the home agent and the mobile node.

Because of the privacy and overhead issues, we will not collect packet payload in this paper. Generally, we need use a 5-tuple <srcIP,dstIP,srcport,dstport,protocol> to denote a flow in the traffic. But in this paper, we only need use the 4-tuple <srcIP,dstIP,srcPort,dstPort> to construct the authentication key because we find that the information protocol has marginal effect in determining the distribution of the traffic. This can be seen from the entropy statistics of Dataset 2 shown in Figure 2. Entropy is a concept to measure the probability of particular information in information theory. It has been shown to contribute to network monitoring [START_REF] Hu | Entropy based adaptive flow aggregation[END_REF] recently. The smaller the entropy is, the more regular the information distribution is. Therefore, it is more difficult to distinguish between mobile nodes when the entropy is low. From Figure 2, we can see that the traffic's entropy of 5-tuples is almost identical to that of 4-tuples and the entropy of 4-tuples is bigger than the others. This suggests that the choice of 4-tuple is the most suitable one to construct the authentication key because the packets of 4-tuples is much easier to differentiate. We will verify this conjecture with real data in Section 5.

To guarantee the consistency between the traffic collected in the home agent and that collected in the mobile node, we collect the traffic through the asynchronous transmission. We also focus on the packet order instead of the precise time in the procedure of authentication to further reduce the impact of time difference between the traffic in the home agent and that in the mobile node.

After determining the information to be collected, the home agent and the mobile node find a way to store the collected traffic in easy-to-access types. The traffic collected is usually stored in a database in the home agent. However, it is inconvenient to access such information if all users' traffic is stored in one table. So, each home agent in our work builds a table for each mobile node to record their traffic in time order. To reduce the access time, the home agent also creates a hash table to maintain the relationship between the mobile nodes and their traffic table. Compared with traffic storage in the home agent, the traffic storage in the mobile node is much simpler. Each mobile node only needs maintaining its own traffic table in time order.

As there is so much traffic in the network, it is impossible to collect all the packets generated by the mobile nodes. In our work, we use stationary space to store the traffic for each mobile node. Meanwhile, we apply several strategies to reduce the frequency and quantity of data collection.

First, we reduce the collection frequency by just collecting special data. Some measurements based on mobile circumstance find that the traffic generated by the mobile nodes largely focuses on individual ports and services [START_REF] Kivi | Mobile data adoption in finland 2005-2006[END_REF][START_REF] Riikonen | Mobile internet usage -network traffic measurements[END_REF], such as port 80 or web service. This allows us to collect the packets of special application, such as the packet whose destination port is 80. This collection strategy not only reduces the storage overhead but also reduces the risk of attackers' eavesdropping, as attackers need more time and energy to get the special application information they want.

Second, we update the storage depending on the availability of the space and the frequency of collection. Once the storage space is full, the collection will be stopped temporarily. So, even if the nodes do not access the Internet for a long time, or they have a prolonged absence from the local subnet, the traffic records will be sustained unless the space is full and new collection begins. This collection method increases the difficulty of attackers' eavesdropping because they do not know what information to collect and what sequence to store it.

Access Path Construction

As shown in Figure 3, there may be many nodes in a subnet and they may exhibit the same online activities at a particular point of time. Therefore, it is insufficient to use just one packet to differentiate different users. However, we can combine the time and space properties of the traffic to construct the authentication key. In order to do so, we define the list of consecutive packets from one mobile node N as its access path indicated by Apath N,timestart = {(number i , P i )}, where,

P i = {srcIP i , dstIP i , srcP ort i , dstP ort i }.
The parameter timestart represents the collection time of the first packet in the access path. The parameter number i indicates the sequence number of the packet in the storage. It is an auxiliary parameter to strength the security of the authentication key in the construction of the access path. The parameter P i is used to denote the packet in the list and it is represented by a 4-tuple. P 1 is named starting point of the access path. We call the length of the access path access hop in our paper, which is equal to the number of packets in the list. The most important question for our architecture is how many hops we should use to construct a unique access path. We answer this question in Section 5.

Access Path based Authentic Source Address Validation

The access path based source address validation includes two parts, as shown in Figure 4. In the first part, the home agent validates the home address of the mobile node once it receives a binding update request from the mobile node. It searches through traffic records table according to the home address claimed by the mobile node, constructs a challenge question and sends it to the mobile node with message Auth Init as shown in Figure 4. After the mobile node gets the question, it looks for the answer in its own storage table, builds the corresponding authentication key, and returns the key back to the home agent through message Auth Ack to prove its identity. The home agent can compare the answer from the mobile node with the records in its own table to validate the identify of the mobile node.

In the second part, the correspondent node needs to validate the identity of the mobile node as well after it receives a binding update request from the mobile node. The authentication to the correspondent node is more complicated because it has no records of mobile nodes' historical traffic. Usually, the correspondent node is a server that has large access volumes. The cost of monitoring and collection on the correspondent node is very expensive. However, the correspondent node can depend on the home agent to complete validation. The procedure is shown in Figure 4. After the correspondent node receives a binding update request, it sends an authentication request to the home agent through message Auth Proxy. The home agent then sends a new challenge question to the mobile node through message Auth Ask. At the same time, the home agent also sends the correspondent node the hash value of the right answer to the challenge question. After the correspondent node receives the answer from the mobile node through message Auth Ack, it computes the hash value of the answer and compares the result with that from the home agent. Such comparison allows the correspondent node to distinguish the identity of the mobile node.

How to construct the challenge question is an important task in authentication. Since our validation is based on the access path, it is easy to construct a challenge question. For example, we can ask "what information do you have between number 5 and 8?" or "what did you do after you accessed the 120.23.*.* at port 80 at 11:00?". Since neither storage order nor the accurate content can be known by the attacker, a right answer must come from the right mobile node. Of course, we can ask more than two questions to strengthen the security.

Performance and Security Analysis

Storage Overhead

We illustrate the storage overhead of our scheme using the example of our campus network (see Section 5). Suppose all 48,000 users in the campus network are mobile nodes, and each packet record in our case is 40B. The relationship between the storage overhead and the number of packet records for each mobile node is shown in Figure 5.

From Figure 5, we can see that only 0.076MB of overhead is needed to store 2000 packet records for each mobile node, and only 3.58G of overhead is needed to store all the packet records for all mobile nodes in the home agent. Obviously, this light storage overhead will not lead to overhead burdens on the home agent or the mobile nodes. Since our experimental results show that only three consecutive packets are sufficient to complete validation (see Section 5.2), the actual overhead in real practice should be much smaller than that in Figure 5.

Security Analysis

Attackers are most likely to eavesdrop at three locations in the network: on the path between the home agent and the correspondent node (HA-CN path), on the path between the home agent and the mobile node (HA-MN path), and on the path between the mobile node and the correspondent node (MN-CN path). We analyze the security of our scheme under scenarios of attacks to these three paths.

-On HA-CN path: The only useful message to the attacker on the HA-CN path is the hash value of the authentication key generated by the home agent.

Even if the attacker is able to get the hash value, it is almost impossible for the attacker to decode the original authentication key from it. -On HA-MN path: In our scheme, the messages transmitted on the HA-MN path include the mobile nodes' traffic, the binding update request, the challenge question and the authentication key. The authentication key is useless for attackers, because it changes all the time. The mobile nodes'traffic is also useless for attackers, because the attackers cannot know the sequence number of the packets required to construct the access path unless they collect the traffic continuously from the very beginning. But this is impossible. -On MN-CN path: The eavesdropping on the MN-CN path is not a concern to our scheme because that the authentication key will change in every communication under our scheme.

Feasibility Analysis

The authentication key used in our scheme comes from real traffic data. No additional device or software is needed except for a collection module. As a result, it is simple to deploy our scheme in practice. Moreover, most core routers have collected the historical traffic passing by for the purpose of measurement and management. Our scheme can use the data collected by routers directly, or add some additional features to the collecting function of routers without introducing too much overhead.

Experimental Study

In this section, we demonstrate the optimal choice of access hops in the construction of authentication key. We use two datasets collected from Campus Network of Tsinghua University (TUNET), which serves for about 40,000 hosts and 48,000 connected end users. TUNET connects to the CERNET (China Education and Research Network) that connects to the Internet through a 2 Gbps full-duplex link.

One dataset was collected from the platform of DragonLab (Dataset 1). It monitored the Web/HTTP traffic of TUNET that interacts with online map sites including Google Map, Microsoft Live Maps, Yahoo Maps, Baidu Maps, Koubei Maps, Sogou Maps, Edushi and Dushiquan. This dataset consists of about 2GBs of map traffic data for the 18 days between April 7 th and 24 th of 2009.

The other dataset was collected by a core router in TUNET (Dataset 2). It includes all the packets without payload for ten minutes between 16:40 and 16:50 on December 7 th of 2006. The size of the data is around 2GBs.

Notice that these datasets are used for methodology analysis, other datasets with packet records can also be used.

Effectiveness Evaluation Algorithm

Before determining how many access hops are needed to construct a unique authentication key, we first propose a standard used to evaluate the effectiveness of an access path. In order to do so, we design an access path based forest through three steps (To strengthen the security, we do not consider the packet sequence number of the access path in the construction of the forest):

-Create an access path graph for the nodes that have the same behaviors at the same point of time. We first create a graph to cluster all the nodes that have the same behaviors at the same point of time. In the graph, each point (node) represents a packet in the access path, which is denoted by P i; and each directed link reflects the sequence of packets. We illustrate the graph construction with an example. Suppose we need to validate a mobile node N1. First, an access path Apath N 1,t0 = {P 1, P 2, P 3, P 4} is chosen from the home agent's records table randomly and a graph is constructed as shown in Figure 6. Next, all the nodes that have the same packet P 1 around the same point of time are extracted from the database. Suppose four nodes are found and their access paths are Apath N 2,t0 = {P 1, P 2, P 3, P 5}, Apath N 3,t0 = {P 1, P 2, P 6, P 7}, Apath N 4,t0 = {P 1, P 7, P 8, P 8} and Apath N 5,t0 = {P 1, P 6, P 7, P 8} respectively. These access paths are then inserted into the directed graph one by one as shown in Figure 6. In order to improve the security, we do not require other nodes to access P 1 exactly at t0 as node N1 does, but allow other nodes to access P 1 between t0 -t and t0 + t, where t is a threshold (We use 0.5 second as the threshold in this paper). -Construct the access path forest. The forest can be constructed according to the following steps: First, we make layers for the access path graph shown in Figure 6. The layer of the starting point P 1 is defined as layer 0. The layer number is one less than the corresponding access hops. Second, we set the starting point of the access path as the origin node of the forest and define the number of mobile nodes in the access path graph as the in-degree of the origin node. As shown in Figure 6, the in-degree of the point P 1 is 5. Third, we consolidate the points in the graph layer by layer to construct the forest. The same points at the same layer in the graph are consolidated into one point in the forest at the same layer. The in-degree of the point in the forest is the number of the mobile nodes that have accessed this point at the same layer of the graph. In effect, the in-degree of the point means the number of users that have the same starting point and the same access path up until this point. We call points whose in-degree is one as "leaf nodes", and we do not add points under them in the next layer of the forest. Point P 6 in Figure 6 is an example of leaf point. -Compute the effectiveness of the access path.

The ultimate goal of constructing the access path forest is to determine how many hops are needed to construct an effective authentication key. Based on the in-degree of the points in the forest, the effectiveness of the access path with hops i can be defined as follows:

Disc i =      0 (if i=1 & N>1 ); 1 (if i=1 & N =1) ; ∑ ( k=1 i-1)(leaf k ) N (if i>1); (1)
In formula [START_REF] Andersen | Accountable internet protocol(aip)[END_REF], the parameter N represents the in-degree of the origin node, the parameter leaf k denotes the number of leaf points at layer k, and Disc i defines the effectiveness of the access path with i hops. The result of Disc i allows us to find the most suitable access hops needed for authentication purpose. For example, the effectiveness of the access path in Figure 5 is illustrated in formula [START_REF] Arkko | Using ipsec to protect mobile ipv6 signaling between mobile nodes and home agents[END_REF]. The result suggests that the access hops must be at least 4 in order to construct an authentication key to identify node N1 or differentiate all the mobile nodes. However, the number of access path hops can be less under certain circumstances.

Disc i =          0 (i=1 ); 40% (
i=2 ) ; 60% (i=3); 100% (i=4);

(2)

Choice of Access Hops

The authentication key constructed with different information may have different effects on validation efficiency. In this section, we detect the optimal number of access hops under different tuples to construct the authentication key. To eval- represents the frequency of a m-tuple packet re-appear (does not consider srcIP information since it is the producer of the packet). In fact, it reflects the number of mobile nodes that have the same behaviors at the same point of time. For example, the first column of the first group in Figure 7(a) stands for the number of unique 2-tuple <srcIP,dstIP> packets in Dataset 1; and the second column stands for the number of 2-tuple <srcIP,dstIP> packets that is common to 2 different mobile nodes in their access history at some point of time. Apparently, the 4-tuples packets have a lower probability to re-appear than others. Using the effectiveness evaluation algorithm discussed earlier, we compute the smallest number of access hops needed to construct the authentication key as the choice of the tuples changes for both Dataset 1 and Dataset 2. The result is shown in Figure 8. We can see that most nodes (98.19%) in Dataset 1 can be distinguished by one 3-tuple <srcIP,dstIP,dstPort> packet, and all nodes can be distinguished by one 4-tuple <srcIP,dstIP,srcPort,dstPort> packet. For Dataset 2, at most three access hops are needed to construct a unique authentication key. We can also notice from Figure 8 that the access hops needed for Dataset 2 is much longer than that for Dataset 1. This is because the traffic in Dataset 1 is more special. In general, the access hops based on special application traffic is always much shorter. However, it may need more time to collect.

Related Work

The IETF uses the IPsec [START_REF] Arkko | Using ipsec to protect mobile ipv6 signaling between mobile nodes and home agents[END_REF] to assure the authenticity of the binding update to the home agents. It is secure in theory. However, it has not been widely deployed because of its complexity and computational overhead.

The IEFT has also proposed return routability (RR) [START_REF] Johnson | Mobility support in ipv6[END_REF] mechanism to overcome the security vulnerability introduced by the route optimization. The RR mechanism uses reachable check to assure the right mobile node is sending the binding update message. When the mobile node moves to a new location, it sends two Init messages to the correspondent node through two paths. One is sent directly to the correspondent node. The other is sent via the home agent. The correspondent node generates two tokens for these two Init messages according to a secret only known by himself and sends them back to the mobile node through the same two paths. After that, the mobile node sends back a binding management key (named kbm in IETF) that is constructed from these two tokens to the correspondent node to prove its identity. Although it is difficult for attackers to intercept on two paths at the same time, some have managed to do so [START_REF] Ren | Routing optimization security in mobile ipv6[END_REF]. [START_REF] Li | Improved security mechanism for mobile ipv6[END_REF][START_REF] Nikander | Mobile ip version 6 (mipv6) route optimization security design[END_REF][START_REF] Song | A secure and light weight approach for routing optimization in mobile ipv6[END_REF] propose some improvements to RR mechanism, but they have not been able to make it applicable to a larger extent.

Our scheme shares some similarities with RR mechanism in design. Both RR mechanism and our scheme rely on the home agent to help the correspondent node to complete the binding update authentication. However, there are two essential differences in our scheme. First, the source of the authentication key is different in these two mechanisms. It is generated by the mobile node in our scheme but generated by the correspondent node in RR mechanism. This makes our scheme more secure than RR mechanism. For example, if the attackers manage to eavesdrop on the HA-CN path, they are able to obtain one token of the RR mechanism. If they obtain the other token directly from the correspondent node, they can generate kbm to win the correspondent node's trust. While our scheme has no such kind of risk. Second, the implementation of RR mechanism requires the support of the security tunnel between the home agent and the mobile node. However, the security tunnel such as IPsec has not been deployed widely because of its complexity. As a result, RR mechanism is not widely employed although the concept of security tunnel is theoretically sound. In the contrast, our scheme does not require the support of a pre-created security tunnel.

The idea of accountability is widely applied in IPv6 to validate the identity of the nodes, such as in AIP [START_REF] Andersen | Accountable internet protocol(aip)[END_REF], CGA [START_REF] Aura | Cryptographically generated addresses(cga)[END_REF] and HIP [START_REF] Moskowitz | Host identity protocol (hip) architecture[END_REF]. These mechanisms often bind the source address onto public key to generate a self-certification address, and most of them support mobility as well. However, the computational complexity caused by encryption limits their deployment. For example, the CGA(Cryptographically Generated Addresses) is composed of subnet prefix (64 bits) and interface identifier (64 bits) that is generated by two hash changes according to the address owner's public key and some CGA parameters. The corresponding private key and the interface identifier that is unchanged no matter how host roaming assert the senders identity in mobility. Unfortunately, the time required for generating a valid high secure CGA address is overwhelming from a practical perspective [START_REF] Bos | A nalysis and optimization of cryptographically generated addresses(cga)[END_REF]. In this paper, the scheme we proposed also builds on the notion of accountability. However, our scheme only requires existing data in the network, which solves the overhead and deployment issues of traditional cryptography-based mechanisms.

Conclusion

In this paper, we propose an authentic source IP address validation scheme in Mobile IPv6. Using historical traffic generated by the mobile nodes, our methodology generates a unique authentication key to validate the home address claimed by the mobile node after its move. This key is a sequence of access paths composed by 4-tuple <srcIP, dstIP, srcPort, dstPort> packets. It is difficult for attackers to forge because the access path and the sequence number of the packets in the storage is only known by mobile nodes and the home agent. In addition, any effort from attackers to extract authentication key is meaningless because authentication key is changing all the time.

Our experiment with real traces demonstrates that a unique authentication key can be constructed using only three 4-tuple <srcIP, dstIP, srcPort, dstPort> packets. Compared with other cryptography-based methods, our scheme consumes no computational overhead and less storage overhead. Most important of all, it is easy to deploy using available data existing in the network.

Fig. 1 .

 1 Fig. 1. Historical traffic based trustable communication architecture in Mobile IPv6

Fig. 2 .

 2 Fig. 2. The entropy of traffic which is composed of different tuples

Fig. 3 .

 3 Fig. 3. The map sites access path of five users in some time interval in Dataset 1.

Fig. 4 .

 4 Fig. 4. The procedure of home address validation. In this way, the home agent and the correspondent node can authenticate the binding update and distinguish the ownership of the home address claimed by the mobile node.

Fig. 5 .

 5 Fig. 5. Storage overhead in the home agent and the mobile node.

Fig. 6 .

 6 Fig. 6. The construction of the access path graph and forest. Each node represents a packet and the directed link denotes access order.

Fig. 7 .

 7 Fig. 7. Packets distribution under different tuples in Dataset 1(a) and Dataset 2(b)uate the impact of alternative choices of tuples on authentication key, we change the definition of packet from 2-tuple to 4-tuple to calculate the distribution of mobile nodes' traffic for both Dataset 1 (as shown in Figure7(a)) and Dataset 2 (as shown in Figure7(b)). In both Figures, each column in the m-tuple group represents the frequency of a m-tuple packet re-appear (does not consider srcIP information since it is the producer of the packet). In fact, it reflects the number of mobile nodes that have the same behaviors at the same point of time. For example, the first column of the first group in Figure7(a) stands for the number of unique 2-tuple <srcIP,dstIP> packets in Dataset 1; and the second column stands for the number of 2-tuple <srcIP,dstIP> packets that is common to 2 different mobile nodes in their access history at some point of time. Apparently, the 4-tuples packets have a lower probability to re-appear than others.Using the effectiveness evaluation algorithm discussed earlier, we compute the smallest number of access hops needed to construct the authentication key

Fig. 8 .

 8 Fig. 8. Nodes' discrimination rate in different hops

http://www.edu.cn/cernet2_7948/

http://dragonlab.org/

Acknowledgment

We are greatly indebted to Wenlong Chen for fruitful discussion. We also owe our deepest gratitude to Bingqing Xu and Kaijun Zhang for data collection support.


Du Yimo

Liu Fang
email: fangliu@nudt.edu.cn

Chen Zhiguang
email: chenzhiguanghit@gmail.com

Ma Xin

WeLe-RAID: A SSD-based RAID for System Endurance and Performance

Keywords: SSD, RAID, wear-leveling, endurance, performance, reliability

Due to the limited erasure/program cycles of flash memory, flashbased SSDs need to prolong their life time using wear-leveling mechanism to meet their advertised capacity all the time. However, there is no wear-leveling mechanism among SSDs in RAID system, which makes some SSDs wear out faster than others. Once any one of SSDs fails, reconstruction must be triggered immediately. But, the cost of this process is so high that the reliability and availability is affected seriously. We propose WeLe-RAID which introduces Wear-Leveling mechanism among flash SSDs to enhance the endurance of entire SSD-based RAID system. As we know that under the workload of random access pattern, parity stripes suffer from much more updates because every update to the data stripe would cause the modification to the related parity stripe. Based on this principle, we introduce age-driven parity distribution scheme to guarantee the wear-leveling among flash SSDs. At the same time, because of age-driven parity distribution, it brings into the performance benefit with better load balance. Compared with conventional RAID mechanism, it significantly improves the life span and performance with ignorable overhead.

Introduction

SSD (Solid State Drive) exhibits higher speed and lower power consumption than disk. To some degree, it alleviates the I/O bottleneck in computer system by replacing disk. For the compatibility, it offers standard interfaces like disk, which can use previously calculated hardware and software based on disks. However, there are three critical technical constraints for flash memory [START_REF] Chen | CAFTL: A Content-Aware Flash Translation Layer Enhancing the Lifespan of Flash Memory based Solid State Drives[END_REF]: [START_REF] Chen | CAFTL: A Content-Aware Flash Translation Layer Enhancing the Lifespan of Flash Memory based Solid State Drives[END_REF] No in-place update, that means the whole block must be erased before overwriting data in any page; [START_REF] Patterson | A Case for Redundant Arrays of Inexpensive Disks (RAID)[END_REF] No random write in a page, for the reliability, pages in a block need to be programmed in a sequential order rather than random writes. (3)Life limits, block will wear out after a certain number of program cycles. To cope with these obstacles, many strategies have been proposed respectively. In this paper, we mainly focus on the problem of the third constraint that flash memory has the limited erasure/program cycles. Actually, almost all the SSD products in the market supplied by kinds of vendors adopt the wearleveling schemes to make all blocks in the SSD wear out evenly to guarantee their advertised capacity. Over provision of capacity also has the same goal, while not just meet the requirement of garbage collection. These two strategies work together to prolong the lifespan of SSD, although they cannot increase the total program cycles of all the blocks. RAID mechanism has already been a very effective and popular method to construct high performance and reliable storage system since it is firstly published in 1988 [START_REF] Patterson | A Case for Redundant Arrays of Inexpensive Disks (RAID)[END_REF]. It uses redundancy scheme to improve reliability and stripe scheme to promote throughput. In this case, using inexpensive disks with a little cost, it can construct a high performance storage system.

As SSD has wider applicable area, it would be a nature idea to construct storage system using the techniques mixed with RAID mechanism and state-of-the-art SSD. SSD has internal wear-leveling strategies to prolong its lifespan with advertised capacity. Once it cannot afford equivalent capacity as what vendors claimed in their product introductions, it no longer can supply the good service to meet users` requirements. So, wear-leveling is very necessary in SSD. As we know that, RAID controller does not have the wear-leveling mechanism to guarantee that all the SSDs in the RAID system wear out synchronously. Once a disk fails because of reaching its life limit, it costs too much time to replace it and reconstruct data on it using the algorithm based on parity. In this paper, we propose a novel method which adopts parity distribution based wear-leveling scheme among SSDs named WeLe-RAID to make the entire RAID system effectively work longer. The WeLe-RAID has three properties as follows:

(1) Age-driven parity distribution. As we know that, RAID4 assigns parity in unique device, and RAID5 assigns parity evenly which means every device has the same fraction of parity, while WeLe-RAID distributes parity according to its age dynamically. If some SSDs have higher erased number than others, and once this gap reaches the previously assigned critical value, we need reallocate the parity on these SSDs: more parity on younger SSDs and less parity on older SSDs.

(2) Less replacement in the lifecycle of entire RAID system. Since using the wearleveling mechanism in the entire SSD-based RAID system, every device has afforded a part of workload so that all the devices can serve longer comparatively. It will be a long time until all the devices simultaneously approach their life critical value. Before that point, we have enough time to back up all the data on other new devices. Then totally replace the old ones. Consequently, in the lifecycle of the entire RAID system, less replacement needed than the previous system without weal-leveling mechanism among SSDs.

(3) Optimized addressing method with age-driven parity distribution. Conventional RAID mechanism adopts round-robin data layout [START_REF] Zhen | FastScale: Accelerate RAID Scaling by Minimizing Data Migration[END_REF], which the mapping relationship can be represented through simple function. However, age-driven parity distribution makes addressing more complex. In this paper, we give the original and optimized data layout and addressing method respectively. And the optimized one is much more effective.

The rest of the paper is organized as follows: Section 2 gives the motivation of this paper by analyzing previously main work which cannot meet the needed requirement. Section 3 describes the design and related algorithms in detail. Section 4 is the evaluation of WeLe-RAID. Section 5 introduces some related work. The last part is conclusion summing up the works in this paper.

Problem Description

2.1

Why need wear-leveling SSD has the internal wear-leveling mechanism to prolong its life span with the capacity advertised by the vendors. However, Diff-RAID [START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF] figures out that wearleveling mechanism among SSDs will lead to high probability of correlated failures.

On the contrary, it attempts to create and maintain the age difference among SSDs to guarantee at least some devices have lower bit error rate to avoid high correlated failure rate. We think it is very useful when the bit error rate of flash chip gradually rises in its whole life. Actually, for SLC, the bit error rate of flash chip does not have linear relationship with its age, even almost maintain zero until they reach their rated lifetime. For most MLC models, the bit error rate increases sharply shortly after their rated life times, and some start to increase sharply even earlier. Before they hit their rated lifetime, they can maintain comparatively stable bit error rate. And with the correctness of ECC, this climbing trend will be slowed down further [START_REF] Grupp | Characterizing flash memory: anomalies, observations, and applications[END_REF]. In order to keep the age difference while the oldest SSD is retired, Diff-RAID has to replace the retired one with the new one, then reconstruct data and redistribute parity. We use a common equation 1 [START_REF] Geist | An analytic Treatment of the Reliability and Performance of Mirrored disk subsystems[END_REF] to approximately evaluate the reliability of SSD-based RAID5 system. In this equation, MTTDL (Mean Time To Data Lose) is marked as the metric of system reliability. MTTF means Mean Time To Failure of single device. MTTR means Mean Time To Repair a failed device. From the equation 1, we can see that if the procedure of reconstructing data and redistributing parity is complex and high time-cost, it will be apt to loss data because any device failing at this moment could cause data corruption. If we use wear-leveling among SSDs, we can prolong the endurance of the entire system, which reduces the number of replacement to avoid more fragile moments.

2

( 1)

MTTF MTTDL N N MTTR = - (1)
Otherwise, wear-leveling among SSDs brings into the performance benefit with better load balance since parity stripes suffer from much more updates because every update to the data stripe would cause the modification to the related parity stripe.

Why not RAID5

Through the above discussion, we know that, in most occasions, wear-leveling in the entire RAID system is useful and necessary. Since parity is the key factor of affecting wear-leveling because devices allocated more parity wear out faster, RAID5 adopting evenly parity distribution scheme may work well on wear-leveling in system level. However, through the experiment, we find that RAID5 cannot ensure the wearleveling among devices either under some workloads. Figure 1 has proven that by showing the result of wear distribution under different workloads. This experiment is done on the simulator described in paper [START_REF] Du | A Customizable and Modular Flash Translation Layer(FTL) Design and Implementation[END_REF]. Set a counter in each SSD and increase itself when meet an erasure. After running the trace, total counter number on each device is its wear situation. This situation is resulted from that some workloads access some certain parity more often so that devices holding this parity suffer more updates and wear out faster than others.

Why not other schemes

Wear-leveling mechanism among SSDs in RAID system has been referred in previously paper. Kwanghee Par etc [START_REF] Park | Reliability and Performance Enhancement Technique for SSD array storage system using RAID mechanism[END_REF] give a brief design of wear leveling for SSDbased RAID5. It uses a big table to restore the erased number of stripe in each SSD respectively. When some parity hit the previously sat number, exchange the hot parity and cold parity with the greedy algorithm. This method costs much extra space and greedy algorithm is so complex that the performance is restricted seriously. WeLe-RAID can balance the wear grade among devices based on parity distribution to prolong endurance and improve performance. Meanwhile it is simple to implement and has tolerable time cost and space cost.

3

WeLe-RAID

The architecture of WeLe-RAID

Figure 2 illustrates the architecture of WeLe-RAID. WeLe-RAID has two controllers. One is RAID controller which manages a group of running SSDs called active devices in figure 2 to offer the service; the other is migration controller triggered when the entire system approaching the end of its lifetime to migrate the data from the active devices to the prepared ones, then replace the old devices with prepared ones. After replacement, prepared devices have become the active ones and new devices are brought in as prepared ones. Because wear-leveling scheme among SSDs is incorporated in our RAID mechanism, all SSDs of RAID system can be promised to maintain the same level of wear grade and can be totally replaced in one time. If any one of devices failed earlier before its life limit, the corresponding prepared one would replace it at once and reconstructing process would be triggered to resume the data on it. Control flow and data flow both can be seen from figure 2. RAID controller administrates active devices below it and connects with migration controller to activate it when active devices nearly approach their life limits. Then migration controller put on the switch between active devices and prepared ones to create data path between them. In common cases, data flows merely through RAID controller to supply service for users. RAID controller has the implementation of basic RAID mechanism and our proposed parity distribution schemes. Migration controller doesn`t need much complex hardware because it only needs the function of migration which copies data from old devices to the same address of the new ones. Certainly, this process usually proceeds when the system is idle to avoid competition of responding I/O requests.

Data Layout

WeLe-RAID introduces dynamic age-driven parity distribution strategy like Diff-RAID [START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF]. We describe this relationship between parity distribution and age distribution quantitatively as follows. Given the age of RAID system consisting of n SSDs represented by a N-tuple (a 1 , a 2 , … a n ) which a 1 , a 2 , … a n has no prime number, we can compute its variance (S) to evaluate its age difference. If it exceeds the critical value (CA), the process of parity redistribution must be called to make the entire RAID system retain the similar wear grade. The parity distribution represented with (p 1 , p 2 , …, p n ) can be made according to the age distribution through following two steps: 1. Sort a 1 , a 2 , … a n in descend order; 2. p k equals the k th value in age`s descend order. Figure 3 is the basic data layout of WeLe-RAID. It exhibits some characteristics. At the first beginning, we suppose the devices are new and their age distribution is (1, 1, 1, 1) shown in figure 3-(a). For wear-leveling, we make parity distribution be (1, 1, 1, 1). Actually, it is the RAID5 scheme assigning parity evenly across all devices. However, just like what we said in section 2.2, RAID5 cannot ensure wearleveling completely among SSDs either. After a running period, the age gap among SSDs appears which age distribution is [START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF][START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF][START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF][START_REF] Chen | CAFTL: A Content-Aware Flash Translation Layer Enhancing the Lifespan of Flash Memory based Solid State Drives[END_REF]. The age difference can be described as variance (S) which the value is 3. If it exceeds CA, parity redistribution needs to be called to mitigate age difference: more parity on younger device and less parity on older device. Figure 3-(b) illustrates the data layout of new parity distribution (1, 1, 1, 3) made according to age distribution. Then, after another running period, the age distribution is (2, 2, 1, 1) whose variance is 1. Compared with last variance, its difference gap significantly becomes smaller. Suppose it still exceeds CA, then parity redistribution need to be called again. Figure 3-(c) shows the data layout of corresponding parity distribution.

In figure 3, data layout adopts round-robin striping scheme that has simple addressing policy but causes huge migration once parity distribution scheme changed. Figure 4 gives an improved data layout. Adopting this data layout, every parity redistribution operation brings small amount of shifts between data and parity. The procedure of parity shift from an original distribution to a new distribution can be depicted as follows:

1. Compute the region number. The region number is determined by computing the minimum common multiple of last region and sum of each fraction in new distribution. The first region is the sum of each fraction in the original parity distribution. From figure 4-(a) to figure 4-(b), we can compute the region number which is 12 equaling to minimum multiple common of 4 (sum of (1, 1, 1, 1)) and 6 (sum of (1, 1, 1, 3)).

2. Amplify the fraction in each part of parity distribution equation according the region number. So the parity distribution is changed from figure 3-(a 3. Exchange the parity and data block in corresponding area according to the newly computed parity distribution.

Compared with basic data layout, improved data layout migrates less data. Although it cannot guarantee parity distribution according to age evenly in the finest grain, it is quite uniform from the point of the whole layout.

Addressing method

The key to implement WeLe-RAID is to design the mapping mechanism between logical address and physical address in the controller. When the controller receives an I/O request, it uses striping scheme to partition the data into several parts. And send the data and parity to the certain related devices according to the mapping relationship. Round-robin placement scheme is popularly used in RAID system. In this method, data layout is ascertained before. So any logic block address can be mapped to physical address easily through function without looking up operation. However, it lacks a little flexibility. The other method seldom used is mapping table. It is more flexible, but lead to high pressure on time cost and space cost. Usually, dynamic parity distribution like WeLe-RAID needs more flexible mapping data structure just like mapping table. But, in this paper, we use former method which still meets our requirement.

Traditional RAID scheme distribute parity either to a dedicated device like RAID4 or across all devices evenly like RAID5. From their different data layouts, we can compute the physical address using a linear function respectively. The addressing function of RAID4 can be summarized as follows:

( )

/ -1 SN LBA N = 1 PN N = - (2)
( )

mod 1 DN LBA N = -
In above equations, LBA means logical block address of the data unit after partition. N means the number of devices including data devices and parity devices. SN means stripe group number representing the stripe group allocated for the data. PN means the number of device that stores parity related with current data. DN means the number of device that stores current data. RAID5`s addressing function is displayed as follows:

( )

/ -1 SN LBA N = mod PN SN N = (3) ( ) ( ) ( ) ( ) mod 1 1 mod 1 m od 1 mod 1 LBA N if LBA N PN DN LBA N f LBA N PN i -+ ->= = - -< ⎧ ⎨ ⎩
For WeLe-RAID, in different time period, it has different parity distribution caused by age difference of devices. Every device`s age can be denoted by the average number of all blocks` age. If we use the data layout as figure 3 shows. The address function can be stated as follows:

( )

/ -1 SN LBA N = ( ) ( ) ( ) 1 2 1 1 1 2
+ + + <= + + + - - ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ (4) ( ) ( ) ( ) ( ) mod 1 1 mod 1 m od 1 mod 1 LBA N if LBA N PN DN LBA N f LBA N PN i -+ ->= = - -< ⎧ ⎨ ⎩
We have pointed out the drawback of data layout shown in figure 3. Then we present an improved data layout to reduce the data migration. With improved data layout, we can give the algorithm depicted in pseudo code 1 to solve addressing problem. This addressing algorithm is run when redistribution has been completed according to the layout depicted in last section.

In the algorithm, parity redistribution history and region history must be recorded as permanent variables. SN can be computed directly like any previous RAID mechanism. Because of exchange between parity and data when parity redistribution occurred, only using one function cannot meet the requirement of addressing parity device number (PN) and data device number (DN). Hence, we reserve all region history parity distribution history in order to attain the current physical address of parity and common data through the algorithm described in pseudo code 1. Actually, there is another way to deal with addressing problem. We could use a table to reserve the number of device to which the data and correlated parity should be sent. Through looking up the table, we can get its physical address of any logical block. But the operation of looking up may cost too much time and the table must be huge to accommodate all the mapping relationship which causes extreme pressure to the space in the RAID controller. Compared with this mapping table method, what we proposed is more effective. We know that the time of redistribution is very few because it is only called when the age difference exceeds the critical value which is usually a little high. So the algorithm described in pseudo code 1 costs little time and absolutely saves space since it has no complex data structure.

Evaluation

We measure the performance, endurance and reliability of WeLe-RAID compared with other SSD-based RAID system. We have constructed a SSD simulator in paper [START_REF] Du | A Customizable and Modular Flash Translation Layer(FTL) Design and Implementation[END_REF]. In order to compare the performance and endurance between WeLe-RAID and other RAIDs, we implement these RAID schemes respectively in software RAID mode. Then we run some traces [START_REF] Chang | An Adaptive Stripping Architecture for Flash Memory Storage Systems of Embedded Systems[END_REF] collected from PC and servers under the real workloads. Through the simulation experiment, we can attain the average latency which can be used as a metric of performance. After running the traces, we check the average erased number of each block on each SSD which represents the endurance of the entire RAID system. For reliability, we adopts mathematic model to analyze the MTTDL (mean time to data lose) that is the common criteria to evaluate reliability.

Performance of WeLe-RAID

The performance experiment is done on the state that redistribution has been completed, and the data layout is stable. Figure 5 shows the average latency for different RAID mechanism under kinds of workloads. We can see from the figure that the performance of WeLe-RAID is better than another two: outperforms RAID5 about 10% and outperforms Diff-RAID 30% approximately sometimes even 40%. The reason for that is WeLe-RAID adopts age-driven parity distribution. Since the device that has the higher wear grade means it suffers from more writes, transforming some parity from older device to younger device, to some degree, balances the write workload. That is why it outperforms RAID5 although RAID5 distributes parity absolutely evenly. Diff-RAID distributes more parity on the older device to create age gap to improve reliability. However, it makes older device which has already been responsible for more requests to undertake more coming ones. It aggravates the unbalance of loads among SSDs and lead to the bottleneck of some certain device. Consequently, its performance is extremely influenced which is the worst among the three methods.

Endurance of WeLe-RAID

After running each trace, we collect the erased number of each block on each SSD. We use average erased number of total blocks in each SSD to represent the age of each SSD. Figure 7 displays the age difference of different RAID schemes under different workloads. We use standard deviation of all SSDs` erased number to evaluate the devices` age difference. Apparently, WeLe-RAID has the most uniform age distribution which means the endurance of entire WeLe-RAID system has been prolonged. Currently, reliability is a tough problem for flash-based SSD. For one thing, reliability constrains the speed of market development of flash. For other thing, there is no dependable model on reliability for SSD. For traditional disks, some research has been done on their failure models. In term of these models, various methods have been proposed such as Markov model [START_REF] Geist | An analytic Treatment of the Reliability and Performance of Mirrored disk subsystems[END_REF], simulation and shortcut method. [START_REF] Thomasian | Shortcut method for reliability comparisons in RAID[END_REF] This paper analyzes the reliability of SSD-based RAID system with mathematic method. Before we measure the reliability of SSD-based RAID system, we must understand the reliability of single flash chip. Figure 8 shows the relationship between raw bit error rate (RBER) and age for MLC flash. RBER can be reduced prominently with ECC, which is called uncorrectable bit error rate (UBER). And UBER is some orders magnitude lower than RBER because ECC in every page can correct most errors.

WeLe-RAID and Diff-RAID are both one failure tolerant RAID like RAID5 belonging to 1-of-N system. For disk-based RAID5, we can use equation 1 referred in section 2 to estimate the reliability. When disks are replaced by SSD, the failure rate of each device cannot be treated as same constant any more. Due to the uniform age of each device in WeLe-RAID, we can assume the failure rates of all devices are the same. For SLC flash, RBER is stable before flash approaches its rated lifetime. Especially, it is almost changeless with ECC. For MLC, RBER rises along with the increase of the age. But the change is not obvious when it is far away from its rated lifetime, and ECC has narrowed down the changing speed. WeLe-RAID transforms data from old devices to prepared ones before they reach their life limits. So no device whose age approaches life limit is in service of storing data. Based on this point, we can use a constant to approximately express the failure rate. Therefore, we can still use equation 1 to evaluate the reliability of WeLe-RAID. The data loss possibility (DLP, reciprocal of MTTDL) of Diff-RAID converges to steady state after several replacements [START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF]. We can attain the DLP of Diff-RAID and RAID5 from paper of Diff-RAID. Given the UBER of flash used in Diff-RAID [START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF], we can compute the DLP of WeLe-RAID and compare it with Diff-RAID in table 1. We can see from table 1 that WeLe-RAID`s DLP is approaching the Diff-RAID`s.

Related work

RAID mechanism can improve the performance and reliability of storage system based on flash memory. We classify flash storage system as two categories according to the grain of device applied with RAID mechanism. One is coarse grain which uses RAID mechanism on SSDs. This mode is completely compatible to previous RAID technology including software and hardware. But while solid state disks hide the difference with hard disks by flash translation layer (FTL), the potential advantages of flash is hidden too. So the fine grain which uses RAID mechanism on flash chips can exploit the characteristic of flash totally. Mao Bo, Jiang Hong etc [START_REF] Mao | HPDA: A Hybrid Parity-based Disk Array for Ehnaced Performance and Reliability[END_REF] have designed a hybrid RAID4 named HPDA composed by disk and SSDs. It uses disk to respond to the write-intensive accesses as dedicated parity device which is the shortage of SSD. It improves the performance and reliability compared with RAID4 composed totally with SSDs. But it also has the drawback of traditional RAID4 that parity device is the bottleneck. Kadav Asim etc [START_REF] Balakrishnan | Differential RAID: Rethinking RAID for SSD reliability[END_REF] have proposed a novel SSD-based RAID called Diff-RAID which has been discussed in detail in section 2.

Meanwhile, some research has been done on constructing RAID system with flash chips. Lee Yangsup etc [START_REF] Lee | FRA: A Flash-aware Redundancy Array of Flash Storage[END_REF] design a flash-aware redundancy array abbreviated FRA. It separates the parity updating from the write procedure, and deal with it when the system is idle. Thereby, this lazily parity updating method improves write performance prominently. Yu-Bing Chang etc [START_REF] Chang | A Self-Balancing Striping Scheme for NAND-Flash Storage Systems[END_REF] have proposed a self-balanced flash array. It encodes hot data into several replicas stored on different banks. Thus, requests on hot data can be directed to cold banks that are responsible for fewer requests. However, every update brings modification of parity extremely affecting the write performance and causing high space cost. Sooju Im etc [START_REF] Soojun | Flash-Aware RAID Techniques for Dependable and High-Performance Flash Memory SSD[END_REF] present a flashaware RAID technique for dependable and high-performance flash memory SSD. It delays the parity update accompanied with every data write to decrease parity handling overhead.

Conclusion and future work

In this paper, we propose a novel SSD-based RAID called WeLe-RAID. It uses dynamic parity distribution scheme which is adaptive to age of SSD. Based on the principle that parity stripe suffers from more modification, we allocate more parity to younger SSD and less parity to older SSD which ensures wear-leveling among SSDs and to some degree alleviates unbalance of write loads on devices. We give the data layout and addressing algorithm of WeLe-RAID in detail. To implement this method, what we need is only some simple data structure to record a little redistribution history information. Through the experiment, we can see that with ignorable overhead, WeLe-RAID outperforms other RAIDs in average response time. And it has comparable reliability with Diff-RAID. What this paper discussed is one device failure tolerant RAID such as RAID4 and RAID5. Two or more devices failure tolerant RAID like RAID6 has not been introduced currently. It is more complex because multiple parity in one stripe group. In future work, we will intend to design the good layout for RAID6 to decrease the migration when redistribution.

Fig. 1 .

 1 Fig. 1. Erased number of each SSD for RAID5. Here RAID5 consists of four SSDs.

Fig. 2 .

 2 Fig.2. The architecture of WeLe-RAID. Prepared devices in dash line frame are not in the system all the time. They are plugged in only when they are needed.

Fig. 3 .

 3 Fig.3. Basic data layout of WeLe-RAID. (a) shows the data layout under parity distribution (1, 1, 1, 1); (b) shows the data layout under parity distribution (1, 1, 1, 3); (c) shows the data layout under parity distribution (1, 1, 2, 2).

  ) (1, 1, 1, 1) to figure 4-a (3, 3, 3, 3) and from figure 3-(b) (1, 1, 1, 3) to figure 4-(b) (2, 2, 2, 6).

Fig. 4 .

 4 Fig.4. Improved data layout of WeLe-RAID. (a) shows the data layout under parity distribution (1, 1, 1, 1); (b) shows the data layout under parity distribution (1, 1, 1, 3); (c) shows the data layout under parity distribution (1, 1, 2, 2).

Fig. 5 .

 5 Fig.5. Average latency of different RAID systems under various traces Parity redistribution is necessary in the WeLe-RAID and Diff-RAID. But this procedure must cost so much time that the performance is extremely decreased. Diff-RAID has not given the implementation of parity redistribution in detail. If it does not make any improvement in parity migration, it will cost too much time.Figure 6 displays parity redistribution time of WeLe-RAID under different data layouts with optimization and without optimization. It shows that improved layout has much smaller overhead.

Fig. 6 .

 6 Fig.6. Redistribution time of WeLe-RAID with unimproved data layout and improved data layout under various traces

Fig. 7 .Fig. 8 .

 78 Fig.7. Devices` age difference of different RAID under various traces

Table 1 .

 1 Reliability of Diff-RAID and WeLe-RAID

	Diff-RAID	WeLe-RAID
	Data lose possibility 1e-06	5e-06

Acknowledgments. We appreciate Lipin Chang, Po Liang and Joshon for some of the traces, and anonymous reviewers for valuable suggestions to improve this paper. This work is partially supported by National Natural Science Foundation of China grants NSFC60736013 and NSFC60903040.