Zhiguang Chen
email: chenzhiguanghit@gmail.com

Fang Liu
email: liufang@nudt.edu.cn

Yimo Du

Reorder the Write Sequence by Virtual Write Buffer to Extend SSD's Lifespan

Keywords: flash memory, SSD, lifespan, virtual write buffer, storage

The limited lifespan is the Achilles's heel of Solid State Drive (SSD) based on NAND flash memory. NAND flash has two drawbacks that degrade SSD's lifespan. One is the out-of-place update. Another is the sequential write constraint within a block. To extend the lifespan, SSD usually employs a write buffer to reduce write traffic to flash memory. However, existing write buffer schemes only pay attention to the first drawback, but fail to overcome the second one. We propose a virtual write buffer architecture, which covers the two aspects simultaneously. The virtual buffer consists of two components, DRAM and the reorder area. DRAM is the normal write buffer which aims at the first drawback. It endeavors to reduce write traffic to flash memory as much as possible by pursuing higher hit ratio. The reorder area is actually a part of SSD's flash address space. It focuses on reordering write sequence directed to flash chip. Reordering write sequence helps to overcome the second drawback. The two components work together just like the virtual memory adopted by operating system. So, we name the architecture as virtual write buffer. Our virtual write buffer outperforms traditional write buffers because of two reasons. First, the DRAM can adopt any existing superior cache replacement policy, it achieves higher hit ratio than traditional write buffers do. Second, the virtual write buffer reorders the write sequence, which hasn't been exploited by traditional write buffers. We compare the virtual write buffer with others by trace-driven simulations. Experimental results show that, SSDs employing the virtual buffer survive longer lifespan on most workloads.

Introduction

Flash memory is of hot topic in recent years. Solid State Drives (SSDs) based on NAND flash have been widely deployed in storage systems. Different from hard disks, flash memory is absolute semiconductor chip without any mechanical components. Flash chip is hierarchically organized. Typically, a chip is comprised of thousands of blocks. A block is further divided into tens of pages. Flash memory supports three basic operations, write, read and erase. Write must be preceded by the erase. An alternation between write and erase is named as an E/W (Erase/Write) cycle. Read and write are performed at the granularity of page, while, erase is performed at block level.

Even though flash memory exhibits some superior features, there still exist some critical drawbacks, which hinder much wider deployment of SSDs. We focus on three of these drawbacks. One is the limited lifespan of flash memory. Generally, each block could only survive limited E/W cycles. When a block has been written and erased too many times, it becomes unreliable and even leads to bit flips. Another concerned drawback is the out-of-place update. It's unable to directly overwrite a page for flash memory. If a page that has already contained data will be rewritten again, it must be erased beforehand. Exactly, the whole block containing the page must be erased because erase is performed at block level. The last concerned drawback is the sequential write constraint within a block. Pages in a physical block cannot be written randomly. They must be written one by one in the same order as they are arranged in the block.

To overcome the first drawback discussed above, SSD employs a write buffer to reduce write traffic, thus extends its lifespan. Correspondingly, various write buffer management schemes have been proposed [e.g. 1, 2, 3, 4, 5, 6 and 7]. These schemes mostly aim at decreasing the write traffic directed to flash memory. However, the number of write requests is not the only one factor affecting lifespan. Actually, SSD's lifespan is impaired by both out-of-place update and sequential write constraint, which are the last two drawbacks as discussed above, respectively. Unfortunately, existing write buffer schemes mostly pay attention to the out-of-place update. They endeavor to reduce the quantity of updates to flash memory, but neglect to optimize the write sequence.

In this paper, we propose a novel virtual write buffer architecture to extend SSD's lifespan. The virtual write buffer consists of two components. One is the DRAM, which is also employed by traditional write buffers. The other is a part of SSD's address space. Actually, our virtual buffer is the same with virtual memory employed by Operating Systems (OS). These two components focus on the two factors affecting SSD's lifespan, respectively. DRAM is used to overcome the out-of-place update drawback. It buffers the frequently updated pages to reduce write traffic directed to flash chips. The flash based component is responsible for reordering the write sequence, which helps to overcome the sequential write constraint.

The DRAM can adopt any existing high performance cache replacement policy, such as 2Q [START_REF] Johnson | 2Q: a low overhead high performance buffer management replacement algorithm[END_REF], ARC [START_REF] Megiddo | ARC: a self-tuning, low overhead replacement cache[END_REF], and LIRS [START_REF] Jiang | LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance[END_REF]. So, it achieves higher hit ratio, therefore reduces write traffic significantly compared with other SSD-oriented write buffers. The flash based component reorders the write sequence directed to flash memory. This optimization is neglected by traditional write buffers completely. As the virtual buffer covers both two factors affecting the lifespan, it's not surprising that, our virtual buffer outperforms other write buffers constantly. We carry out trace driven simulations to evaluate our virtual buffer. Experimental results show that, the virtual write buffer erases less blocks on most workloads compared with CLC [START_REF] Kang | Performance trade-offs in using nvram write buffer for flash memory-based storage devices[END_REF], PUD-LRU [START_REF] Hu | PUD-LRU: An Erase-Efficient Write Buffer Management Algorithm for Flash Memory SSD[END_REF], and BPLRU [START_REF] Kim | Bplru: A buffer management scheme for improving random writes in flash storage[END_REF]. Operating Systems name the part of hard disk used for virtual memory as swap area. Similarly, the flash based component in the virtual write buffer is named as reorder area, just as its function implies.

The rest of paper is organized as follows. Section 2 introduces the backgrounds and related works. Section 3 presents the principle of our virtual buffer elaborately. Section 4 evaluates different write buffers. The last section concludes our work.

Backgrounds and related works

The first subsection reviews the typical architecture of SSDs briefly. The second subsection analyzes the negative impacts imposed on SSD's lifespan by the two drawbacks of flash memory. They are the motivations of our work. The last subsection introduces some related works.

SSD Overview

Compared with hard disks, flash memory has some peculiarities. It cannot be applied to traditional storage system directly. To be compatible with existing software stack, several flash chips are packaged into an SSD. A typical architecture of SSD is shown in Figure 1. SSD exhibits the same interface with hard disks by employing the Flash Translation Layer (FTL). FTL hides these peculiarities of flash memory. Due to the out-of-place update characteristic, flash memory can't overwrite a page. An alternative method to accommodate updates is to direct updated data to other free physical pages. The original pages are marked as invalid. In other words, a logical page can be written to any free physical page. Correspondingly, a logical address would point to a new physical page once its data are updated. The dynamic mapping relationship between logical and physical addresses is maintained by FTL. Ideally, a logical address can map with any physical page. However, the fully-associative mapping between physical and logical pages requires a large table to maintain the mapping entries. Instead, practical SSDs usually map a logical block with a physical block. Logical pages (in the logical block) and physical pages (in the physical block mapping with the logical block) that have the same offset in respective blocks maps with each other by default. This mapping scheme is usually named as block-level mapping. This coarse-grained mapping scheme leads to a more compact mapping table. Besides the address mapping, FTL is also responsible for reclaiming invalid pages. As updated data is directed to other free pages, the original data is invalid. FTL must convert these invalid pages to be free to guarantee that, SSD supplies constant storage capacity to users. The erase operation is used for converting invalid pages to be free. The process reclaiming invalid pages is called garbage collection.

As shown in Figure 1, there is a write buffer between SSD's interface and FTL. Write buffer is mostly used for decreasing write traffic to flash array. Since the write requests are reduced, fewer pages become invalid. Garbage collection erases fewer blocks to reclaim these invalid pages. Thus, SSD's lifespan is extended. However, we argue that, the lifespan is not determined by the quantity of write traffic completely. Usually, SSD's lifespan is depleted by inner-generated write traffic, rather than user's write requests. Reducing the inner-generated write traffic is a more attractive way to extend SSD's lifespan. Supposing that a block contains some invalid pages, to reclaim these invalid pages, the whole block must be erased (erase operation is performed at block level). Unfortunately, the block still contains some valid pages, which must be moved to other locations. Moving these valid pages leads to additional write requests generated by SSD itself, rather than by user. This phenomenon is called write amplification [START_REF] Hu | Write amplification analysis in flash-based solid state drives[END_REF]. So, write buffer should not only reduce write traffic, but also overcome write amplification.

Write Amplification Analysis

Practical SSDs usually map physical address with logical address at the granularity of block. Pages in the two blocks are mapped sequentially. Block is the atomic unit of address management. So, updates to any page in a logical block lead to rewriting the entire block to another physical block. Figure 2 shows this drawback elaborately. Figure 2 presents the negative impacts imposed on SSD's lifespan by out-of-place update and sequential write constraint. As shown in the figure, we assume that a block contains 8 pages. Pages marked by V contain valid data. Pages marked by U had been updated. Pages marked by F are free and have not been written.

In Figure 2, all pages of block A are originally valid. Two pages (marked by U) are to be updated. Since flash cannot overwrite these pages, it must direct updated data to other pages. Consequently, another block B is allocated to accept the updates. As block-level mapping scheme demands that two pages (coming from logical and physical blocks, respectively) with the same offset map with each other, ideally, we expect that updates are directed to the new block with their page offset unmodified. As shown in block B, two pages contain valid data. Unfortunately, this is not permitted by flash memory due to the sequential write constraint. Pages in a block must be written sequentially beginning from the first one. Instead, we update the two pages in another manner illustrated by block C. In this manner, not only are the updated pages written to block C, but also these unchanged pages are moved to block C as well. This update policy conforms to the principle of block-level mapping scheme. Pages in physical and logical blocks are mapped with their offsets unmodified. However, this policy requires moving valid pages. Even though there are only two pages updated, SSD moves six additional pages. The process of moving these still valid pages to the new block is named as padding [START_REF] Kim | Bplru: A buffer management scheme for improving random writes in flash storage[END_REF]. Padding leads to write amplification directly.

Based on the discussion, we can conclude that, two factors lead to write amplification. One is out-of-place update. The other is the sequential write constraint. The first factor requires that, updated data must be written to a new block. The second factor does not allow writing the new block randomly. Ultimately, it needs to rewrite the whole block, which results in write amplification. Write amplification impairs the lifespan remarkably. Write buffer is an effective way to reduce write amplification. But, existing write buffer management policies mostly focus on reducing write traffic, which helps to reduce the chance of out-of-place updates. They scarcely pay attention to overcome the sequential write constraint. The next subsection will introduce some typical write buffer policies in detail. By contrary, our virtual write buffer not only reduces the updates, but also makes write sequence to be sequential. So, it achieves superior performance.

Related Works

Write buffers for SSDs are different from buffers of hard disks. Buffers of hard disks try to encapsulate several trivial requests into a long sequence, reducing the chance of seek and rotation of disk heads. Buffers of SSDs aim at reducing write traffic and alleviating write amplification. The first goal requires frequently updated pages to be kept in write buffer for as long time as possible. The last goal demands to reduce padding. They conflict with each other sometimes. Write buffers for SSDs mostly compromise between the two. CFLRU. Clean first LRU (CFLRU) [START_REF] Park | CFLRU: a replacement algorithm for flash memory[END_REF] is a policy used for managing the cache of both write and read requests. For flash memory, write is more expensive than read, so, write requests should be kept in cache for a longer time. CFLRU always attempts to select a clean page as the replaced victim. Dirty pages are protected. CFLRU is found to be able to reduce the average replacement cost by 26% compared with LRU. But, it deals with the cache containing both read and write. The scope of this paper is constrained to write buffer only.

FAB. Flash aware buffer (FAB) [START_REF] Jo | Fab: flashaware buffer management policy for portable media players[END_REF] is also a policy for write buffer of SSDs. In the write buffer, all pages coming from the same block are packed into a group. All the groups are organized into an LRU list. Once a group is accessed, or a new page joins the group, the group is moved to the MRU-end (most recently used). If replacement is needed, FAB selects the group having most pages as the victim. If more than one groups meet this demand, the least recently used group is evicted. FAB evicts the group with most pages to reduce padding pages, despite that the evicted group may be accessed frequently. The arbitrary policy may lead to thrash. BPLRU. Just like FAB does, Block Padding LRU (BPLRU) [START_REF] Kim | Bplru: A buffer management scheme for improving random writes in flash storage[END_REF] also packs pages belonging to a block into a group. It selects the least recently used group as the victim. Maybe, some pages of the block are not in write buffer. BPLRU reads them from flash memory and pads the block, then writes the whole block to flash memory. PBLRU pads blocks explicitly before they are written to flash.

CLC. FAB evicts the largest group. BPLRU evicts the least recently used group. CLC [START_REF] Kang | Performance trade-offs in using nvram write buffer for flash memory-based storage devices[END_REF] incorporates these two policies together. It divides the write buffer into two parts. One part employs BPLRU policy, the other employs FAB. Compared with FAB, it protects some of the recently used large groups. Compared with BPLRU, it gives higher priority to large groups to be replaced, because replacements of large groups reclaim more free capacity for write buffer.

PUD-LRU. Hu et. al. proposed a new erase-efficient write buffer management algorithm called PUD-LRU, PUD-LRU [START_REF] Hu | PUD-LRU: An Erase-Efficient Write Buffer Management Algorithm for Flash Memory SSD[END_REF] divides blocks in the write buffer into two groups based on a combined measure of frequency and recency, Predicted average Update Distance (PUD). One group is used for keeping frequently or recently updated blocks. The other is used for selecting replaced blocks. It evicts the block with the largest PUD value, because the block is considered to be the least frequently and recently updated. By doing so, PUD-LRU maximizes the efficiency of destaging operation.

Wu.

[3] et. al. proposed a hybrid page/block write buffer architecture along with an advanced replacement policy, called BPAC [START_REF] Wu | BPAC: An Adaptive Write Buffer Management Scheme for Flash-based Solid State Drives[END_REF]. BPAC also divides the buffer into two parts. One exploits temporal locality, the other exploits spatial locality. BPAC analyzes the workloads constantly and adapts to workloads dynamically. Sun. et. al. had made use of Phase Change Random Accessed Memory (PCRAM) as SSD's write buffer [START_REF] Sun | A hybrid solid-state storage architecture for the performance, energy consumption, and lifetime improvement[END_REF]. Griffin [START_REF] Soundararajan | Extending ssd lifetimes with disk-based write caches[END_REF] extends SSD's lifespan by disk-based write buffer.

In conclusion, write buffers described above mostly focus on reducing write traffic by caching frequently updated pages. Some of them reduce padding pages by evicting the block containing the most updated pages. All of them fail to optimize write order.

3

The Virtual Write Buffer Architecture

Our virtual write buffer consists of two components. The DRAM is used to cache frequently updated pages, thus reduce write traffic. The reorder area is responsible for reordering write sequence, thus decreasing padding pages. They are introduced in the next two subsections, respectively.

The DRAM Component

DRAM used in the virtual write buffer is absolutely a traditional cache. It attempts to achieve as higher hit ratio as possible. By contrary, write buffer management schemes described above do not center around hit ratio completely. Take CLC as an example, it not only pursues higher hit ratio, but also tries to evict the largest group to decrease padding pages. These two goals may conflict with each other. Therefore, write buffers adopting CLC usually obtain poor hit ratio.

To achieve higher hit ratio, we manage the DRAM at page level (Contrarily, several write buffers described above pack some pages belonging to a block into a group, they are managed at block level). Only frequently accessed pages are prevented from being evicted. As the DRAM purely exploits temporal locality, which is also pursued by traditional caches, so, some classical cache replacement policies, such as 2Q [START_REF] Johnson | 2Q: a low overhead high performance buffer management replacement algorithm[END_REF], ARC [START_REF] Megiddo | ARC: a self-tuning, low overhead replacement cache[END_REF], and LIRS [START_REF] Jiang | LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance[END_REF], can be reused. This is an important superiority of our virtual buffer over the others. Exactly, we adopt ARC [START_REF] Megiddo | ARC: a self-tuning, low overhead replacement cache[END_REF] as the replacement policy for DRAM. ARC is so superior a cache replacement policy that, it has been adopted by ZFS [START_REF]ZFS Introduction[END_REF] and IBM DS8000 storage server. The rationale of ARC is explained as follows.

ARC is well-known due to its simplicity and high performance. It maintains two caches, a physical cache and a virtual cache (the virtual cache is also named as ghost cache). The physical cache is organized into two lists. One list focuses on frequency, the other focuses on recency. The ghost cache contains pages that had been evicted out of the physical cache recently. Actually, the ghost cache only keeps the index entries of these pages. Data in these pages are discarded. In other words, the ghost cache just stores replaced history. Replacements in the physical cache are guided by the feedback of the ghost cache. If a page hits in ghost cache, and it had been evicted from the recency list in physical cache, it means that pages in the recency list are more valuable. ARC gives priority to replacing the pages in frequency list. On the other hand, if an access hits in the ghost cache, and the target page had been evicted from the frequency list in physical cache, ARC is prone to replace pages in the recency list. ARC adapts itself to the workloads continually and dynamically by changing the size of each list. So, it achieves high hit ratio on most workloads.

Compared with conventional write buffers of SSDs, the DRAM achieves high hit ratio for two reasons. The first is to manage the buffer at page level, which helps to exploit temporal locality aggressively. The second is to inherit the classical high performance cache replacement policy. Higher hit ratio means that, the write traffic is reduced significantly.

Reorder area

The reorder area is a part of SSD's flash address space. It is used for accommodating out-of-order updates. To explain the reordering process clearly, we first introduce a concept, prior page. For a given page, its prior pages are those belonging to the same block, but their page offsets are smaller than that of the given page. For example, in logical block 0, Page 2 has smaller offset than Page 3 does, Page 2 is one of the prior pages of Page 3. Similarly, Page 1 is also a prior page of Page 3. The rationale of reordering write sequence can be summarized as follows. When a page is evicted from DRAM, the virtual write buffer detects whether there are some prior pages of the evicted page existing in DRAM. If there is such a page in DRAM, the evicted page cannot be written to its physical block sequentially, because a page prior to it hasn't been written to the block. Instead, the page is written to the reorder area to wait for the right sequence. The process will be explained in detail by resorting to Figure 3. In the figure, there are seven scenarios denoted by S i , where i belongs to {0, 1, 2, 3, 4, 5, 6}. On each scenario, DRAM evicts a page out. On Scenario 0, the size of DRAM is five pages. The page numbered by 6 is in the reorder area. In another word, Page 6 had been written to flash due to its out-of-order update. A free physical block is prepared for accepting replaced pages. As DRAM is full, the page numbered by 0 is going to be replaced.

On Scenario 1, Page 0 is replaced. As it is the first page of a logical block, it should be written to the first page of a physical block as well, because a page in the logical block has to locate in the same offset in corresponding physical block for block level mapping scheme. Since there is no prior page of Page 0 in DRAM, Page 0 can be written to its physical block directly. There is no need to write it to the reorder area.

On Scenario 2, Page 3 is replaced. However, Page 2 is still in DRAM, and it is a prior page of Page 3. Therefore, Page 3 cannot be written to the physical block sequentially. Instead, it's directed to the reorder area.

On scenario 3, Page 2 is replaced from DRAM. As none of the pages prior to it (such as Page 0 and 1) is in DRAM, Page 2 could be written to its physical sequentially. However, it requires reading Page 1 from flash memory to pad the block. As shown in the figure, Page 1 and 2 are written to the physical block sequentially. Reading Page 1 and writing it back to flash are I/O requests generated by SSDs, rather than by users.

On Scenario 4, Page 4 is replaced. In order to write Page 4 in the physical block sequentially, it needs to pad Page 3 beforehand. As a result, Page 3 and 4 are written to the physical block. So, when Page 5 is replaced, it can be written to the block directly, as presented on Scenario 6. When Page 7 is replaced from the DRAM, we pad Page 6 as well, as shown on the last scenario.

In conclusion, the DRAM doesn't concern about the write sequence. It evicts pages depending on temporal locality and the adopted cache replacement policy. If a page is replaced, the write buffer considers whether it is able to be written sequentially. If so, the page is written to flash directly, otherwise, the page is directed to reorder area, which is also a part of flash address space. Whether a page can be written to flash directly is determined by whether there are some prior pages in the DRAM. If there are no prior pages in DRAM, the replaced page can be written to flash directly. But maybe, it needs to pad some pages.

The virtual buffer can be compared with other write buffers as follows. For a write buffer mentioned in the related works, when a page is evicted out of buffer, the entire block containing the page is replaced. All the absent pages are padded to the block. Then, the block is written to flash. For our virtual write buffer, replacement of a page does not influence other pages in the same block. This is the first improvement to traditional write buffers. We don't write the entire block to flash arbitrarily, but write its pages one by one. For a given page, its prior pages won't be padded to the block until the given page is replaced from DRAM. As these prior pages haven't been written to the target physical block, updates to them will not lead to write amplification. Delaying page padding as late as possible is the second improvement to traditional write buffers. To keep the sequential write order, we employ the reorder area to register these out-of-order replaced pages.

Actually, the reorder area is a part of flash address space. Directing out-of-order replaced pages to reorder area still shortens SSD's lifespan. But, as the DRAM is able to filter more updates than other write buffers do, and the padding pages is less as well, our virtual buffer erases less blocks all the same compared with others, as shown in the next section.

Performance Evaluation

This section evaluates the performance achieved by our virtual write buffer. The first subsection introduces the experimental setup. Subsection 2 compares our virtual write buffer with other buffers. Actually, the virtual buffer is similar with an FTL called FAST (Fully Associative Sector Translation) [START_REF] Lee | A Log Buffer based Flash Translation Layer Using Fully Associative Sector Translation[END_REF]. The last subsection compares the virtual write buffer with FAST.

Experimental Setup

We evaluate different write buffers by trace driven simulations. Write buffers mostly aim at extending SSD's lifespan, so, performance is measured by the number of erased blocks. We expect that the erased blocks are as few as possible.

Characteristics of adopted traces are listed in Table 1. They are all enterprise class traces delegating typical applications. Among these traces, SRC, USR, Proj and Proxy were gathered from servers at Microsoft Research Cambridge. LiveMaps was gathered from LiveMaps backend server for duration of 24 hours. Develop was collected from Developers Tools Release server for a duration of a day. MSNFile was collected from MSN Storage file server for duration of 6 hours. Exchange was collected from Exchange Server for duration of 24 hours. All the traces can be downloaded from internet [16]. They were used by Dushyanth N. [START_REF] Narayanan | Write Off-Loading: Practical Power Management for Enterprise Storage[END_REF].

The flash chip configuration adopted in experiments is summarized as follows. The size of a page is 4KB. A block contains 64 pages. These parameters come from the specification of a flash chip with small blocks from Sumsung [START_REF] K9 | U5M-KCJ0 Datasheet[END_REF].

Comparison with Other Buffers

We compare the virtual write buffer with BPLRU [START_REF] Kim | Bplru: A buffer management scheme for improving random writes in flash storage[END_REF] and PUD-LRU [START_REF] Hu | PUD-LRU: An Erase-Efficient Write Buffer Management Algorithm for Flash Memory SSD[END_REF]. BPLRU is a classical write buffer policy for SSDs. It has been extensively evaluated. PUD-LRU is a recently proposed policy achieving high performance. It inherits the design principle of classical cache replacement policies.

The experimental results are presented in Figure 4. As shown in the figure, SSDs employing the virtual write buffer erase the least physical blocks on most workloads. To further explain why the virtual buffer achieves higher performance, we compare the hit ratios and the numbers of padding pages related to different write buffers, which are presented in Figure 5 and 6, respectively. Higher hit ratio means that the write traffic is reduced more remarkably. So, we expect the hit ratio to be as high as possible. Inversely, padding pages are additional write traffic generated by background operation. A superior write buffer should help to reduce padding pages, thus alleviate write amplification. So, we expect that padding pages are as few as possible. As padding a block indicates migrating pages from one physical block to another, hereafter, we refer padding pages as padding pages or migrated pages, interchangeably.

BPLRU and PUD-LRU pack updated pages in a logical block into a group. Groups are the atomic units for replacement in write buffer. BPLRU organizes these groups into an LRU list. It always replaces the least recently updated group. Hu et al. argued that, the LRU list only focuses on recency, but neglects access frequency [START_REF] Hu | PUD-LRU: An Erase-Efficient Write Buffer Management Algorithm for Flash Memory SSD[END_REF]. They proposed PUD-LRU to exploit both of the two aspects. PUD-LRU improves BPLRU by employing a new measurement called Predicted average Update Distance, rather than the simple recency. So, PUD-LRU usually erases less blocks compared with BPLRU, as shown in Figure 4. Actually, the importance of frequency is extensively evaluated in the research domain of cache replacement policy.

Policies discussed above mostly aim at improving hit ratio and reducing write traffic to flash memory. But, as shown in Figure 5, hit ratios achieved by different write buffers are low. Even when the cache size is 64MB, the write buffer still cannot reduce write traffic significantly. Only on workloads Prxy, the erased blocks are reduced with the expanding of buffer size. So, simply using write buffer to reduce write traffic is not an effective way to extend SSD's lifespan.

(a) (b) (c) (d) (e) (f) (g) (h) (i)
Fig. 4. SSDs employing our virtual write buffer erase the least blocks on most workloads. That's because our virtual write buffer optimizes both cache replacement and write sequence.

We propose to reorder the write sequence in virtual write buffer. Reordering write sequence avoids writing physical blocks randomly. Usually, random write results in write amplification, which will shorten SSD's lifespan. As shown in Figure 6, SSDs employing the virtual write buffer move the least pages for padding. It means that the write amplification is prohibited. That's why SSDs equipped with the virtual buffer erase fewer physical blocks. Actually, out-of-order written pages are directed to the reorder area, which is a part of flash address space. These pages also deplete SSD's lifespan. But, these pages can be written to any physical pages in flash chips. There is no need to migrate any page for them. They will not bring about write amplification. So, the erased blocks induced by out-of-order written pages are negligible.

Except for the reordering optimization, our virtual buffer does not neglect hit ratio. The DRAM devotes to improving hit ratio. DRAM is managed at the page level. It is able to exploit temporal locality completely. Furthermore, it can reuse existing high performance cache replacement policies. So, the DRAM achieves higher hit ratios on most workloads, as shown in Figure 5. Higher hit ratio means to reduce write traffic. This is pursued by traditional write buffers. Based on the two aspects (higher hit ratio and reordering optimization), the virtual write buffer reduces erased blocks.

(c) (d) (e) (f) (g) (h) (i)
Fig. 5. The virtual write buffer achieves higher hit ratio than others do.

Comparison with FAST

Reorder area is similar with the log area adopted by FAST [START_REF] Lee | A Log Buffer based Flash Translation Layer Using Fully Associative Sector Translation[END_REF]. So, we compare the virtual write buffer with FAST further. The rationale behind FAST can be described as follows. FAST allocates a set of blocks called log blocks. Left blocks used by users are called data blocks. Data blocks contain most of the user's data. Log blocks are prepared to accept updated pages. The log set is shared by all data blocks. Updates to any data blocks are directed log blocks sequentially. If the log set is used up, FAST merges valid data in the log set to data blocks. And another log area is allocated. These log blocks are similar with the reorder area adopted by our virtual write buffer.

To compare the two schemes fairly, we assume that FAST is equipped with the same DRAM as our virtual write buffer owns. And it adopts ARC [START_REF] Megiddo | ARC: a self-tuning, low overhead replacement cache[END_REF] as the cache replacement policy as well. The difference between two schemes relies on the direction of updated pages evicted from DRAM. For FAST, pages evicted from DRAM are written to log blocks arbitrarily. When the log set is used up, log blocks are merged with data blocks. For our virtual buffer, SSD tries its best to write pages to data blocks directly. Only when a page is evicted from DRAM in out-of-order manner, the page is written to the reorder area. As two schemes adopt the same cache replacement policy to manage DRAM, they achieve the same hit ratios. But, the virtual buffer usually erases fewer blocks. FAST writes all updates to log area arbitrarily. When the log area is used up, it merges log blocks with data blocks. The merge operation requires to moving many pages. As shown in Figure 6, FAST usually moves more pages than the virtual write buffer does. On the contrary, the virtual buffer gets rid of merge operation. It reorders the write sequence, and then writes pages of a logical block to a physical block with page offset unchanged. There are no page migrations except for padding. So, the virtual buffer erases less blocks.

Conclusion

SSDs usually employ write buffer to extend the lifespan. However, existing write buffers haven't optimized the write sequence. We propose a virtual write buffer. The buffer consists of two components, the DRAM and reorder area. DRAM devotes to improving hit ratio, as pursued by traditional write buffers. Since DRAM is managed at page level and adopts existing superior cache replacement policy, it gets higher hit ratio. The reorder area reconfigures the write sequence, thus prohibits write amplification. Based on the two optimizations, the virtual write buffer enables SSDs to erase less physical blocks, and thus to extend the lifespan.

Fig. 1 .

 1 Fig. 1. Overall architecture of SSDs.

Fig. 2 .

 2 Fig. 2. Write amplification induced by out-of-place update and sequential write constraint.

Fig. 3 .

 3 Fig. 3. The process of reordering.

Fig. 6 .

 6 Fig.6. SSDs employing the virtual write buffer migrate the least number of pages.

Table 1 .

 1 Characteristics of trace.

	Traces	Read	Write	R/W
	USR	41362884	3837166	10.78/1
	SRC1	43544675	2155325	20.2/1
	SRC2	21110497	16289503	1.3/1
	Proj	47281632	9818368	4.82/1
	Proxy	110389290	58210710	1.9/1
	LiveMaps	38616344	11033656	3.5/1
	Develop	12324273	5865727	2.1/1
	MSNFile	19725455	9614545	2.05/1
	Exchange	25246721	31823279	1/1.26

Acknowledgments. We are grateful to the anonymous reviewers for their valuable suggestions to improve this paper. This work is supported by the National Natural Science Foundation of China (NSFC60736013, NSFC60903040, NSFC61025009), Program for New Century Excellent Talents in University (NCET-08-0145).


Chuck Zhao

Nan Hua

Ashwin Lall
email: lalla@denison.edu

Ping Li
email: pingli@cornell.edu

Jia Wang
email: jiawang@research.att.com

Jim Xu

Towards a Universal Sketch for Origin-Destination Network Measurements

Despite its importance in today's Internet, network measurement was not an integral part of the original Internet architecture, i.e., there was (and still is) little native support for many essential measurement tasks. Targeting the inadequacy of counting/accounting capabilities of existing routers, many data streaming and sketching techniques have been proposed to estimate the important statistics of traffic going through a network link. Most of these techniques are, however, developed to track one specific statistic and/or answer a specific type of query. Since there are a large number of such statistics and queries of interest, it is very difficult, if not impossible, for network vendors and operators to implement and deploy data streaming/sketching solutions for all of them, due to router resource (memory, CPU, bus bandwidth, etc.) constraints. In this paper, we propose a general-purpose solution that can not only answer a wide range of queries, but also be able to answer types of queries that were not known a priori. In particular, we introduce the use of the Conditional Random Sampling (CRS) sketch data structure for succinctly capturing network traffic data between a set of nodes in the network. This sketch is the first step towards a "universal" sketch data structure in the sense that it is not tied to measurement of a single quantity. We show that the CRS sketch can compute unbiased estimates for any linear summary statistic in the intersection of a pair of traffic streams, e.g., traffic and flow matrix information, flow counts, and entropy. We present detailed experiments, using data collected at a tier-1 ISP, that show that our sketch is capable of estimating this wide range of statistics with fairly high accuracy.

Introduction

As the Internet continues to grow and evolve, network traffic measurement is essential to Internet service providers (ISPs) and application service providers (e.g., Google, Yahoo, Akamai) for a variety of network operation tasks and business decision-making. Despite its importance in today's Internet, network measurement was not an integral part of the original Internet architecture, i.e., there was (and still is) little native support for many essential measurement tasks. Besides some basic SNMP counters (e.g., total packet and byte counts across a link) and simple flow collection facilities (e.g., Cisco Netflow), today's routers still lack sophisticated measurement functionality. Such limitations have constrained many network management tasks, and forced significant research and engineering efforts to be expended on finding creative solutions. In particular, targeting the aforementioned inadequacy of counting/accounting capabilities of existing routers, many data streaming and sketching techniques (e.g., [START_REF] Krishnamurthy | Sketch-based change detection: Methods, evaluation, and applications[END_REF][START_REF] Kumar | Data streaming algorithms for efficient and accurate estimation of flow size distribution[END_REF][START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF]) have been proposed to estimate the important statistics of, and to approximately answer various queries concerning, traffic going through a network link.

Most existing data streaming and sketching techniques are developed to track one specific statistic (e.g., second moment [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF]) and/or answer a specific type of query (e.g., existence and identities of elephants [START_REF] Estan | New directions in traffic measurement and accounting[END_REF][START_REF] Kumar | Sketch guided sampling-using on-line estimates of flow size for adaptive data collection[END_REF]). Since there are a large number of such statistics and queries of interest, it is very difficult, if not impossible, for network vendors and operators to implement and deploy data streaming/sketching solutions for all of them, due to router resource (memory, CPU, bus bandwidth, etc.) constraints. We believe this partly explains the lack of commercial success of these solutions. An emerging solution to this problem is so-called universal data sketches, each of which is a single versatile data structure that can track several different types of statistics and/or answer a wide range of queries, including those that were not known a priori, simultaneously. Overall a universal sketch consumes much less resources than individual sketches for tracking/answering all these statistics/queries combined. A conceivable tradeoff here is that a universal sketch might not provide as accurate answers to a type of query as data sketches designed specifically for it, given the same resource consumption.

In this paper we introduce the Conditional Random Sampling (CRS) sketch [START_REF] Li | Using sketches to estimate associations[END_REF][START_REF] Li | Conditional random sampling: A sketch-based sampling technique for sparse data[END_REF][START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF], a universal sketch for succinctly summarizing network traffic data. The CRS sketch, if deployed across multiple routers, can perform a type of "coordinated" sampling wherein the flows sampled at different locations can be highly correlated. This permits the accurate computation of statistics of the intersection of the data at both locations (i.e., origin-destination measurements) using the sketches at each. Moreover, CRS is not tied to measurement of a single quantity. We show that it is capable of computing any linear summary statistic of the intersection of streams. Examples of these statistics include (but are not limited to) computation of the traffic matrix, counting numbers of distinct flows, entropy estimation, and computation of higher moments for detection of large changes in the traffic distribution. A key contribution of this paper is to show that the estimator for the sketch is unbiased, settling an open problem raised implicitly in [START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF].

We perform a thorough analysis of CRS on packet trace data collected from a tier-1 ISP at the core of the Internet. Whereas CRS has been studied before [START_REF] Li | Using sketches to estimate associations[END_REF][START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF] for natural language applications, we had to tune parameters and make non-trivial adaptations to make it work on networking data. We were able to show that for most applications, such as traffic matrix, entropy estimation, etc., the sketch performed remarkably well while using very little memory. For most of the common measurement statistics that we estimated, it gave low measurement error while using memory comparable with a specialized algorithm for any single statistic.

The rest of this paper is organized as follows. Section 2 defines the problem that we solve in this paper. Section 3 presents the CRS sketch and how we apply it on network traffic measurement. We evaluate the CRS sketch using data collected from a tier-1 ISP in Section 4. Finally, we discuss related work in Section 5 before concluding in Section 6.

Problem Statement

Throughout this paper, we assume that there are spatially-separated nodes (say, ingress and egress nodes in a network). Each node encounters a stream of tuples of the form i, c , where i is an element from a universe of size n (e.g., in the case of IP flows, n = 2 96 , where 96 = 32 + 32 + 16 + 16 is the length of the flow label consisting of source and destination IP addresses and port numbers) and c is the increment to the count for this element (e.g., the packet size in bytes). The classic streaming problem is to compute functions of the frequency distribution of the streams at individual nodes. In this paper, we expand this definition to answering queries for arbitrary pairs of nodes based on the sketches at the nodes. Note that this is a much harder problem since we must be able to answer 2 = Θ ( 2 ) queries from just sketches. While previous work in data streaming has focused on sketches for a specific query/statistic, our goal is to have a single sketch that can be used to compute unbiased approximations for multiple types of queries performed on the intersection of traffic seen at any pair of nodes. In particular, we aim to compute any linear summary statistic, i.e., any function of the form ∑ x g(x) where the sum is over the flow sizes in the OD-flows between pairs of streams. Examples of the types of queries that we expect to answer include:

1. The F 1 count between pairs of distributed streams, or simply put, the amount of traffic between two nodes in the network. Using the sketch proposed in this paper, we can estimate the traffic between all pairs of nodes and hence construct the traffic matrix [START_REF] Gunnar | Traffic matrix estimation on a large ip backbonea comparison on real data[END_REF]. 2. The F 0 count is simply the number of distinct flows that are in the intersection of the two streams. This quantity is useful for network provisioners to determine the number of flows between a source-destination pair, rather than the aggregate traffic. 3. Prior work [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF] has looked at the computation of the entropy norm of traffic between origin-destination pairs. This is defined as ∑ x ln x, where the sum is over the all the flows in OD-flow between a given pair of nodes. It is also often useful to compute the entropy, which is defined to be log L -(1/L) ∑ x ln x, where L is the F 1 count of the OD-flow. 4. The higher-order moments F 2 , F 3 , . . . (where F p is defined as ∑ x x p ) are also useful for detecting skewness and major shifts in the traffic distribution.

Conditional Random Sampling

We propose the use of Conditional Random Sampling [START_REF] Li | Using sketches to estimate associations[END_REF][START_REF] Li | Conditional random sampling: A sketch-based sampling technique for sparse data[END_REF][START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF] to sketch network data at ingress and egress nodes in the network. The CRS sketch has been shown to be capable of computing arbitrary linear summary statistics of the intersection of pairs of streams, and we evaluate its performance on networking data. Additionally, we show in Section 3.3 that it is possible to extract an unbiased estimate of any linear statistic of the intersection, a fact that was unknown to the authors of [START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF].

Algorithm 1 CRS Sketch

The CRS Algorithm

The CRS algorithm is executed independently at any set of ingress and egress points in the network (more generally at any router or interface of interest), and produces a sketch of the local stream. There is no requirement of universal deployment (e.g., allowing it to be run on only a subset of routers) and is capable of answering queries for any pair of participating routers.

At the heart of CRS lies a random permutation of the flow records in the streams. By ensuring that all the measurement interfaces all use the same permutation, we are able to perform "coordinated" sampling to accurately estimate statistics of the intersection of multiple streams. More precisely, each copy of the CRS sketch is maintained by retaining the k flows with smallest permuted flow IDs in a balanced max-heap data structure that is pruned to have at most k items in it at any time. 5 Here, k is the maximum number of flow records that can be retained in the sketch. Flows in the sketch are updated, and whenever a new flow enters the sketch (by replacing a flow with a larger permitted flow ID) a new record is created for it. See Algorithm 1 for details. By the monotonicity of the min operation, we are guaranteed to have complete counts for all the records in the sketch at the termination of the stream.

The CRS sketch strictly controls its memory consumption by guaranteeing that it never maintains more than k records. In contrast, most other sampling mechanisms such as uniform sampling, flow sampling [START_REF] Duffield | Estimating flow distribution from sampled flow statistics[END_REF][START_REF] Duffield | Flow sampling under hard resource constraints[END_REF], sample-and-hold [START_REF] Estan | New directions in traffic measurement and accounting[END_REF], etc., can only provide probabilistic guarantees on how much space they will consume.

After the sketches are computed, they can be shipped (due to their small size) to a central location for storage. To compute any linear summary statistic of an arbitrary pair of sketches, we compute the sum of the statistic over the set of flows that are in the intersection of the two sketches, excluding the max element of the two sketches. This sum is a sample of the desired statistic, and we can compute an estimate by reverting by sum := sum + g( f .size) 9: end for 10:

OUTPUT sum × n/(Z -1)
factor n/(Z -1), where n is the cardinality of the space of flow IDs and Z is the minimum of the largest permuted ID of the two sketches. This is illustrated is Algorithm 2. In Section 3.3 we show that this factor is precisely the one needed to get an unbiased estimate for any linear summary statistic. We next discuss some implementation issues for the CRS sketch.

Implementation Details

Since a random permutation is expensive to implement, in an actual implementation we would use a hash function with a large range and maintain the k flows with the smallest hash signature. Such approximation has also been used in [START_REF] Broder | On the resemblance and containment of documents[END_REF]. The range can be smaller than the domain of flow IDs but should be much larger than F 2 0 so that the probability of hash collisions is negligible. In Algorithm 2 we replace n with the size of the range.

Since this sketch has to work on streaming packet data, it is critical that the update time per packet should be extremely fast: inter-packet arrival times may be as small as 10-20 nanoseconds. The CRS sketch is extremely well-suited for updating at high speeds. For almost all the packets in the stream, the only processing necessary is the computation of two hashes: one to compute the hash of the flow ID, and another to perform a hash table lookup of the flow in the table (in a real implementation, the heap will contain pointers to the flows in the hash table). Since the hashes do not need to be of cryptographic strength, low-complexity hash functions such as Carter-Wegman's H 3 hashes [START_REF] Carter | Universal classes of hash functions[END_REF] can be used. Alternatively, hardware support for hash functions are also available [START_REF] Ramakrishna | Efficient hardware hashing functions for high performance computers[END_REF]. For a very small subset of updates, specifically when the first k distinct flows are seen in the stream and when a flow is replaced in the heap (lines 9-12 in Algorithm 1), we have to perform heap operations that cost O(log k) operations for a balanced heap (e.g., Red-Black tree). The former case happens precisely k times in the stream and the latter can be shown experimentally to be infrequent, and hence these slower operations do not significantly affect the run-time performance of CRS.

Unbiasedness of CRS

The CRS algorithm described in [START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF] can handle multiple streams and any linear summary statistic over all the streams. The flow size distribution of each stream is viewed as a vector over the space of all flow IDs. Consider a matrix of m row vectors of length n, denoted {x i j }. If we construct a CRS sketch for each row, then we can get an estimate for any linear statistic of the form ∑ n j=1 g(x 1, j , • • • , x m, j ). The CRS algorithm we described in Section 3.1 is simply a special case, with m = 2, g(0, * ) = 0, g( * , 0) = 0, and the assumption that x 1, j = x 2, j whenever x 1, j = 0, x 2, j = 0.

While [START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF] only claimed CRS to be unbiased for F 0 estimation for one stream, we discovered that CRS is strictly unbiased in the general case. This follows as a corollary of the following theorem.

Theorem 1. Consider m rows of n balls each. The balls are either red or white, and we denote this as an m × n {0, 1}-valued matrix {a i, j } where 1 stands for red. Let k i ≥ 2, ∀1 ≤ i ≤ m be integer constants.

Let π : [n] → [n] be a random permutation that is applied to the column indices. We will collect the columns from the left until for at least one row i we have collected k i red balls. Let Z i be the index of the k th i red ball in the i th row of the permuted matrix, i.e., a i,π -1

(Z i ) = 1 and ∑ Z i j=1 a i,π -1 ( j) = k i .
If there are less than k i red balls in the i th row, let

Z i = n + 1. Let Z = min i Z i .
Then the first Z -1 columns are an unbiased sample of all the columns, i.e.,

E π 1 {1≤π( j 0 )≤Z-1} Z -1 = 1 n , ∀1 ≤ j 0 ≤ n. Remark: E π 1 {1≤π( j 1 )≤Z-1} = E π 1 {1≤π( j 2 )≤Z-1} is not true in general. Proof. Let h(m, n, a, k, j 0 ) ≡ E π 1 {1≤π( j 0 )≤Z-1} Z-1
. We want to prove by induction on n that h(m, n, a, k, j 0 ) = 1 n for any m, a, k, j 0 . When n = 1, since we require k i ≥ 2, we have Z i = 2, ∀i, so Z = 2, and the statement is true. Now assume it is true for n -1, and we prove it for n. We observe that if k i is larger than the number of red balls on the i th row, i.e., k i > ∑ n j=1 a i, j , then Z i = n + 1 always, and Z i has no effect on Z, so we can remove the i th row from a. If there is only one row left, and k 1 > ∑ j a 1, j , then Z = Z 1 = n + 1, and the equation holds true. So we only need to prove for the cases where k i ≤ ∑ n j=1 a i, j , ∀i. We write the expectation conditioned on which column is mapped to n:

h(m, n, a, k, j 0 ) = E E 1 {1≤π( j 0 )≤Z-1} Z -1 |π -1 (n) = n ∑ j =1 E 1 {1≤π( j 0 )≤Z-1} Z -1 |π -1 (n) = j Pr[π -1 (n) = j ].
For j = j 0 , i.e., π( j 0 ) = n, we get a zero term. This is because we assumed k i ≤ ∑ n j=1 a i, j , so Z i ≤ n, therefore Z -1 ≤ n -1, so 1 {1≤π( j 0 )≤Z-1} = 0. For j = j 0 , i.e., π( j 0 ) = n: Let us consider the same algorithm with the last column removed, i.e., with parameter m, n , a , k, j 0 where n = n -1, a is matrix a with the j th column removed, and j 0 is the position of j 0 among {1, ..., j -1, j + 1, ..., n -1}. Each permutation π with π( j ) = n has a one-to-one correspondence with a permutation π . We will argue that Z i = Z i , given our assumption that k i ≤ ∑ n j=1 a i, j .

-If a i, j = 0, i.e., it's a white ball; Or if a i, j = 1 and k i < ∑ n j=1 a i, j , i.e., it's a red ball but there are at least k i red balls left in the i th row of a , then the position of the k th i red ball is the same with or without the last ball, so Z i = Z i .

-If a i, j = 1, and k i = ∑ n j=1 a i, j , then Z i = n. There are less than k i red balls left in the i th row of a , so Z i = (n -1) + 1 = n.

Therefore Z = Z , so E 1 {1≤π( j 0 )≤Z-1} Z-1 |π -1 (n) = j = h(m, n -1, a , k, j 0 ) = 1 n-1 by induction assumption. So h(m, n, a, k, j 0 ) = ∑ 1≤ j ≤n j = j 0 1 n -1 1 n + 0 1 n = 1 n -1 n -1 n + 0 1 n = 1 n .
Corollary 1. Let ball (i, j) be assigned value x i, j . Let g : R m → R be any function. We have

E π 1 Z -1 Z-1 ∑ j=1 g(x 1,π -1 ( j) , . . . , x m,π -1 ( j) ) = 1 n n ∑ j=1 g(x 1, j , ..., x m, j ).
Proof.

E π 1 Z -1 Z-1 ∑ j=1 g(x 1,π -1 ( j) , . . . , x m,π -1 ( j) ) = E π 1 Z -1 n ∑ j=1 1 {1≤π( j)≤Z-1} g(x 1, j , . . . , x m, j ) = n ∑ j=1 g(x 1, j , ..., x m, j )E π 1 {1≤π( j)≤Z-1} Z -1 = 1 n n ∑ j=1 g(x 1, j , ..., x m, j ).
Thus we see that the CRS algorithm is unbiased for multiple streams for any linear summary statistic.

Experiments

In this section we evaluate the performance of our algorithm using real Internet traffic traces obtained from a tier-1 ISP. We will investigate the impact of different sketch sizes on the estimation of the F 0 , F 1 ,F 2 , entropy and entropy norm and also investigate the distribution of relative error of the estimations. The results are compared with the entropy norm estimated by [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF] and the F 2 estimated by stable random projection (SRP) [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF]. We would also investigate the impact of the number of flows on the estimation error.

The traffic traces in use were collected from an ingress router of the tier-1 ISP. We also obtained the routing table at the ingress router to determine the egress router for We use H 3 hash function [START_REF] Carter | Universal classes of hash functions[END_REF] in the simulations, since we notice that hash functions based on Linear Feedback Shift Register (LFSR) do not work well for our application. This is because some flows differ from each other by only a few bits in the flow label. For example, different HTTP sessions from the same client to the same web server only differ in the source port number field. An LFSR-based hash function often does not distribute the hash values uniformly in such cases while H 3 does. To compute an H 3 hash function, the input bit vector is multiplied by a fixed (randomly-chosen) {0, 1}valued matrix modulo 2 to get the hashed bit vector. This hash function has been also shown to be very amenable for hardware implementation [START_REF] Ramakrishna | Efficient hardware hashing functions for high performance computers[END_REF] since it involves only simple logic such as bitwise XOR and parity computation. Therefore, we recommend that H 3 functions be used in implementing CRS on future Internet routers.

We run the experiments 1000 times for each configuration of varying sketch sizes. Figure 1 depicts the median absolute relative error (MARE) for different statistics using different sketch sizes on all three egresses. The results for the three egresses are similar. We observe that for F 0 , F 1 , and entropy norm, the relative error decreases as sketch size increases, just as expected. For entropy, the error is very small even at small sketch sizes. On the other hand, the relative error of F 2 remains large even at large sketch sizes. The F 0 errors of Egress 1 and Egress 2 are similar, however the F 1 error of Egress 2 is worse than Egress 1 and 3 since the traffic to Egress 2 is actually more heavy-tailed than the other two. The errors of Egress 3 are smaller than Egress 2 due to the larger number of flows to Egress 3.

The entropy estimation error is much smaller than the error for F 1 and entropy norm, the two components for estimating entropy. This is because the CRS sketch will either overestimate both F 1 and entropy norm, or underestimate both, so the errors end up largely canceling each other out. Compared with the method in [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF], our method achieves MARE of around 10% with a sketch of 10, 000 entries for entropy norm, which is comparable with [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF] using 200, 000 entries. (The size of each entry in our sketch , however, is a little over twice that of [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF].) Our explanations for this is as follows: The estimation of entropy norm in [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF] is based on the estimation of F 1-α . The formulae (3) and ( 4) in [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF] show that any error for estimating F 1-α will go opposite ways for F 1 and entropy norm, thus causing larger errors for the estimation of entropy.

We now fix the sketch size to 10000 entries and investigate the distribution of the relative error. Figure 2 shows the distribution of relative errors of F 0 , F 1 , and F 2 estimates of traffic from the ingress to Egress 1. The distributions for Egress 2 and 3 are similar and hence omitted. We see that for F 0 and F 1 , the distribution function are both roughly bell curves centered slightly off 0. However, there are two modes of the distribution of F 2 error, one centered around -0.3 and the other around 7. This means that F 2 estimation most likely underestimates by 30%, and occasionally overestimates by 700%. This is caused by the presence of a large elephant in the OD flow.

An alternative algorithm for estimating F 2 is to use random stable projections (RSP) [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF]. In Figure 3 we compare the theoretical standard deviation (SD) of the CRS sketch and the random stable projection sketch for this dataset. We see that the stable projection sketch would perform better, due to the heavy tailed nature of this OD flow. However we need to emphasize that a single CRS sketch can be used to measure many quantities, while a stable sketch for F 2 can only be used for F 2 measurement alone.

We also plotted the sample SD of the CRS sketch from 1000 runs in Figure 3. We could see the sample SD is very close to the theoretical SD for large sketch sizes, which validates our experiments. However the variance of the SD is so high that for small sketch sizes the sample SD cannot accurately capture the true SD with 1000 runs, which explains that deviations for sketch sizes below 6000.

Finally, we change the number of flows for Egress 1 while maintaining the same set of OD flows. We plot the errors in Figure 4. We can see that the left side of the error curves are flat when the number of egress flows is no more than the number of ingress flows, but the right side goes up. This demonstrates that the performance of CRS sketch depends on the max of the number of flows of ingress and egress. In other words, the greater the traffic at either node relative to the OD traffic, the less accuracy we expect from the CRS sketch. This work is most similar to, and in fact was inspired by, the Conditional Random Sampling sketch [START_REF] Li | One sketch for all: Theory and application of conditional random sampling[END_REF]. The CRS sketch was initially proposed for sparse language data, and we show in this paper how it can be adapted to the networking context. Since the target goals and data characteristics are extremely different in these two domains, the issues in adapting this sketch were far from trivial. In addition, we present a novel proof in this paper that the CRS sketch can give unbiased estimates of arbitrary functions of the intersection of a pair of streams.

The key idea of bottom-k sketch [START_REF] Cohen | Bottom-k sketches: better and more efficient estimation of aggregates[END_REF][START_REF] Cohen | Summarizing data using bottom-k sketches[END_REF] is close to that of the CRS sketch. The bottom-k sketch also maintains the k items with the lowest-k hashed values, and its hashing can be also coordinated hence supporting queries on intersections. However, although the bottom-k sketch can be applied to streaming applications, it is only for the situations in which the weight of each item is known and fixed. The estimators derived are for the aggregate of functions of these weights. In comparison, the CRS sketch performs coordinated sampling of a subset and then estimates any function of the whole set based on the sampled set.

The idea of coordinated sampling can be traced back to Trajectory sampling [START_REF] Duffield | Trajectory sampling for direct traffic observation[END_REF]. Trajectory sampling samples and stores the flows with hashed flow IDs in the same range. Compared with our method, the size of sketch sampled by Trajectory sampling on each router would be in proportion to the amount of traffic passing through it. Hence it lacks flexibility with regard to traffic fluctuations and traffic imbalance among routers. A recent work c-Samp [START_REF] Sekar | csamp: A system for network-wide flow monitoring[END_REF] also leverages coordinated flow sampling. However, its design goal is to assign different sampling ranges for different routers in order to achieve larger monitoring coverage.

There has been a long line of work done on computing the traffic matrix within a network [START_REF] Vardi | Internet tomography: estimating source-destination traffic intensities from link data[END_REF][START_REF] Feldmann | Deriving traffic demands for operational IP networks: Methodology and experience[END_REF][START_REF] Medina | Traffic matrix estimation:existing techniques and new directions[END_REF][START_REF] Zhang | Fast accurate computation of largescale ip traffic matrices from link loads[END_REF][START_REF] Zhang | An information-theoretic approach to traffic matrix estimation[END_REF][START_REF] Papagiannaki | A distributed approach to measure traffic matrices[END_REF][START_REF] Nucci | Design of igp link weight changes for estimation of traffic matrices[END_REF][START_REF] Zhao | Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices[END_REF]. While much of the previous work in this area was done using SNMP link loads [START_REF] Vardi | Internet tomography: estimating source-destination traffic intensities from link data[END_REF][START_REF] Zhang | Fast accurate computation of largescale ip traffic matrices from link loads[END_REF][START_REF] Zhang | An information-theoretic approach to traffic matrix estimation[END_REF][START_REF] Nucci | Design of igp link weight changes for estimation of traffic matrices[END_REF], there has been some recent interest in using data streaming techniques to measure the matrices [START_REF] Feldmann | Deriving traffic demands for operational IP networks: Methodology and experience[END_REF][START_REF] Papagiannaki | A distributed approach to measure traffic matrices[END_REF][START_REF] Zhao | Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices[END_REF]. Our algorithm is closer to these latter works in that it directly uses traffic data, rather than SNMP.

Entropy has recently been proposed, in several different contexts [START_REF] Feinstein | Statistical approaches to DDoS attack detection and response[END_REF][START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF][START_REF] Wagner | Entropy Based Worm and Anomaly Detection in Fast IP Networks[END_REF][START_REF] Xu | Profiling internet backbone traffic: Behavior models and applications[END_REF], as a means for classifying and detecting anomalies in network traffic. Computing the entropy of OD-pairs was first proposed in [START_REF] Zhao | A data streaming algorithm for estimating entropies of OD flows[END_REF], in which the authors propose the use of a sketch at each ingress and egress node in a network that can be used to compute the entropy of any arbitrary pair of nodes. The sketch in this paper is able to solve the same problem, but it is not restricted to solving just this single problem.

Recently, there is a line of work on Compressed Counting [START_REF] Li | Improving compressed counting[END_REF][START_REF] Li | A new algorithm for compressed counting with applications in shannon entropy estimation in dynamic data[END_REF], which applied maximally-skewed stable random projections to estimate the F p frequency moment near p = 1 and then use the estimated F p to approximate the Shannon entropy with a very high accuracy. For example, [START_REF] Li | A new algorithm for compressed counting with applications in shannon entropy estimation in dynamic data[END_REF] conducted some comparisons with CRS to illustrate that, in order to achieve the same accuracy for estimating the Shannon entropy, Compressed Counting can reduce the required sample size of CRS by 2-fold to 113-fold (data-dependent).

In this paper we present and evaluate a sketch for computing any norm on the intersection of pairs of spatially separated streams. As data on the Internet gets more voluminous and more distributed, it will become increasingly important to be able to sketch and compare datasets at remote locations. The work in this paper is a first step towards addressing this challenging new problem.

The distinctive property of our sketch, as compared with prior work, is that it is not limited to a single type of query and can be used to execute arbitrary queries, even ones realized after the data has been collected. It is also designed to be lightweight, both in terms of memory requirements as well as update costs. We show that it is unbiased and that it performs well empirically by evaluating it on real Internet data collected at a tier-1 ISP.

Algorithm 2

 2 CRS Intersection 1: INPUT: A pair of CRS sketches c 1 and c 2 , function g 2: Z 1 := largest ID in c 1 3: Z 2 := largest ID in c 2 4: Z := min(Z 1 , Z 2 ) 5: n := total number of possible flows 6: sum := 0 7: for each record f in both c 1 and c 2 , and f .ID < Z do 8:

3 Fig. 1 .F 2 Fig. 2 .

 3122 Fig. 1. Median Absolute Relative Error with Varying Sketch Sizes. Summary statistics are listed in decreasing order of MARE.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Comparison with stable distribution sketch for F 2 estimation (varying sketch size)

Acknowledgement

The work of Hua, Lall, Xu, and Zhao was supported in part by the NSF grant CNS 0905169. The work of Ping Li was supported in part by the NSF grant DMS 0808864, the ONR grant YIP N000140910911, and a grant from Microsoft.


Xin Yang
email: yangxin@pku.edu.cn

Qingni Shen
email: qingnishen@ss.pku.edu.cn

Yahui Yang
email: yhyang@ss.pku.edu.cn

Sihan Qing

A Way Of Key Management In Cloud Storage Based On Trusted Computing

Keywords: cipher text, key management, symmetric keys, asymmetric keys, backup, public cloud Base Key(non-migratable):SRK Key1:Platform Mig Storage Key Key2:User 1 Mig Storage Key4:User 1 Non-mig Storage Key Data Encryption Service Data Decryption Service KeytoData Map RNG Backup Service Migration Key Sharing Service Figure 2: Architecture of PDPS 3.1 User1 Unmigratable key 1(b) Unmigratable Binding Key 1 Unmigratable Binding Key 2 Unmigratable Binding Key 2 AES Key1 AES Key2 AES Keyn

Cloud security has gained increasingly emphasis in the research community, with much focus primary concentrated on how to secure the operation system and virtual machine on which cloud system runs on. We take an alternative perspective to consider the problem of building a secure cloud storage service on top of a public cloud infrastructure where the service provider is not completely trusted by the customer. So, it is necessary to put cipher text into the public cloud. We describe an architecture based on Trusted Platform Module and the client of cloud storage system to help manage the symmetric keys used for encrypting data in the public cloud and the asymmetric keys used for encrypting symmetric keys. The key management mechanism includes how to store keys, how to backup keys, and how to share keys. Based on the HDFS (Hadoop Distributed File System), we put a way of key management into practice, and survey the benefits that such an infrastructure will provide to cloud users and providers, and we also survey the time cost it will bring to us.

Introduction

With the development in networking technology and the increasing need for computing resources, many companies have been prompted to outsource their storage and computing needs. This new economic computing model is commonly regarded as cloud computing and includes various types of services [START_REF] Kmara | Cryptographic Cloud Storage‖[END_REF] such as: infrastructure as a service (IaaS), where a customer makes use of a service provider's computing, storage or networking infrastructure; platform as a service (PaaS), where a customer *Corresponding Author leverages the provider's resources to run custom applications; and finally software as a service (SaaS), where customers use software that is run on the providers infrastructure. Cloud can be commonly classified as either private or public. In a private cloud, the infrastructure is managed and owned by the company or individual which means accessing to data is under its control and is only granted to parties they trusts. However, in a public cloud the infrastructure is owned and managed by a cloud service provider, which means that customer's data is beyond of its control and therefore could be acquired by illegal parties [START_REF] Christodorescu | Cloud Security is not (just) Virtualization Security[END_REF][START_REF] Jensen | On Technical Security Issues in Cloud Computing[END_REF].

Storage services based on public clouds such as Microsoft's Azure storage service and Amazon's S3 provide customers with scalable and dynamic storage. By moving their data to the cloud customers can avoid the costs of building and maintaining a private storage infrastructure, opting instead to pay a service provider as a function of its needs. For most customers, this provides several benefits including availability (i.e. we cannot access data from anywhere) and reliability (i.e. we do not have to worry about backups) at a relatively low cost.

Although the benefits of using a public cloud infrastructure are apparent, it introduces significant security and privacy risks. In fact, it seems that the biggest difficulty is how to guarantee the confidentiality and the integrity of data [START_REF] Wang | Ensuring data storage security in cloud computing[END_REF][START_REF] Jensen | On Technical Security Issues in Cloud Computing[END_REF]. While, so far, consumers have been willing to trade privacy for the convenience of software services (e.g., for web-based email etc), this is not the case for enterprises and governments, and especially for military departments. Any customers do not want to store missioncritical data or private data like personally identifiable information, or medical and financial records [START_REF] Christodorescu | Cloud Security is not (just) Virtualization Security[END_REF][START_REF] Dean | Mapreduce: Simplied data processing on large clusters[END_REF][START_REF] Haeberlen | PeerReview:Practical Accountability for Distributed Systems[END_REF]. So, unless the problem of confidentiality and integrity are addressed properly, many potential customers are reluctant to use the public cloud instead of the traditional computing facility.

As a customer, there are many reasons to consider that the public cloud is unsafe [START_REF] Dean | Mapreduce: Simplied data processing on large clusters[END_REF]. Importing our data into public cloud enables us to face at least the following threats.

First, as a result of the limit of our law and technology, while we can trust the cloud providers, they cannot guarantee if one of the operators of the cloud will steal our data directly, because they can have the capacity and the authority to get data easily.

Second, the traditional network attack. When we upload data into public cloud, it is totally possible that attackers can intercept or destroy our data.

Third, unlike data stored in our personal computer, the data stored in the cloud is not isolated from other people's data. As a result, the risk of being attacked of our data in the cloud is increasing.

Last but not least, the same to the traditional storage system, the public cloud is also faced the threat of attacker from all over the world.

To address the concerns stated above and increase the usage of cloud storage. We are suggesting designing Private Data Protecting Service (PDPS) based on the architecture of Trusted Computing and the client of public cloud. Such a service should aim to encrypt the data that will be uploaded into cloud and protect the keys used for encryption. More precisely, such a service should provide:  Confidentiality: the encryption before data is uploaded to the public cloud and decryption service after data is downloaded from the cloud.  Key management: be responsible for the protection the keys from various kinds of attack, at the same time, the relationship between data and keys will also be maintained in this part.  Data sharing: customers can share data by ways sharing their keys safely which are related to the data.  Key backup: it is possible that our client which stores keys will collapse suddenly. So there must be a mechanism for key backup, and more importantly the backup must not be used by illegal customer.

PDPS is built based on the client of public cloud, the coupling factor between the public cloud and PDPS is nearly zero, so we can retain the main benefits of a public cloud:  Availability: customer's data is accessible from any machine with a TPM and at all times.  Reliability: customer data is reliably backed up by backing up the keys.  Data sharing: customers can share their data with trusted parties by sharing keys.

Background and Motivation

With the development of Trusted Computing Organization, TPM 1.2 they produced (Trusted Platform Module) serves a very important part to key storage, data signing, IMA and remote attestation.

Key Management and Cloud

As shown in [START_REF] Ateniese | Scalable and efficient provable data possession[END_REF], there are tremendously large amount of files in the cloud, if we encrypt them one by one, there must be the same amount of keys we should manage safely. If we encrypt thousands of files by the same key, it is very easy for attackers to get the key by analysis of the encrypted text [START_REF] Stallings | Cyptography and Network Security Principles and Practices[END_REF]. One of techniques that TPM use for storing data and keys in a secure fashion is to use encryption to store data, and to use encryption and decryption to control access to that data. Although a TPM is somewhat similar to a smart card chip, one difference is that it is attached (through the PC) to a large amount of persistent storage. One of the design goals for secure storage is to take advantage of the persistent storage to store a large amount of private keys and symmetric keys [START_REF] Challener | A Practical Guide To Trusted Computing[END_REF]. As a result, we can store a large amount of encrypted data that is associated with the TPM. However, TPM does not help us to manage the map between the Keys and the data. So we should add the mapping service into the private data protecting service.

RNG

As stated in [START_REF] Challener | A Practical Guide To Trusted Computing[END_REF], in order to generate keys internally, it is necessary for the TPM to have an internal random number generator (RNG). Typically, instead of having a true random number generator (it is difficult to do), many TPMs have pseudo random number generators (PRNGs) that are periodically fed with entropy from timing measurements or other sources of entropy within the TPM itself. This entropy is then distilled into the current seed, so entropy is always increasing. The output of the PRNG or RNG is used to generate keys, nonce, and seeds in the PKCS#1 V2.0 blob creation. Hence, in the solution, the keys are provided by the TPM instead of customs. At the same time TPM provide a series of interfaces for legal customs to manage the keys in a simple way.

Key Structure

Figure 1 shows the basic setup of keys inside a TPM. In the figure, if Key 2 is directly below Key 1, then Key 2 is encrypted (Asymmetric Encryption ) with the public key corresponding to Key 1. Thus, we see that User 1 migratable storage is wrapped with the platform migratable key, which is in turn wrapped with the SRK. User 1's nonmigratable storage key is also wrapped with the SRK. Hence, the architecture of keys is a tree structure.

TPM

Migratable Keys Versus Non-migratable Keys

Migratable keys are meant for two purposes. As shown in [START_REF] Balacheff | Trusted Computing Platforms[END_REF], the first is to provide a quick way to transfer keys from one platform to another in the event that a user wants to change his or her facilities, either because of upgrading or other reasons. The second is to provide the capability for more than one system to use a key. Keys can be valuable if they have associated certificates, or store a lot of data. For example, if a key is used for signing e-mail, a person might want to use it at home and at work or on multiple systems. A key that is used to store symmetric keys might be shared among a group, so only members of that group have access to the keys necessary to decrypt a shared file.

Motivation

First, using persistent storage appears to have a major problem. It is possible that the computer that stores key collapses or some other disasters happen, our solution needs to take into account disaster recovery. So we add Backup Service into the architecture. Second, as a customer in the cloud, it is totally possible that customers need to share data with some other ones safely. In other words, he should send related keys to others. In our solution, we provide Key Sharing Service to help customers to share their keys safely by constructing a backup structure, and the whole process for sharing keys and backing up keys is maintained by the structure. Third, as to data that has high confidentiality, customers do not wanted them to be shared, so in this solution, we provide a interface to enable customer to decide the confidential level of their data neatly.

Architecture of a private data protecting service

We now describe a possible architecture for PDPS, as shown in Figure 2, the architecture includes four sub services (also called functional modules): data encryption service, which processes data before it is sent to the cloud; data decryption service: which processes data after it is received from the cloud; backup service, which backs up keys in a safe way; data sharing service, which enables customers to share data among trusted parties. In the figure, the right side shows four basic modules, among these modules RNG (random number generator), the structure of key tree, and the operation of migration are maintained by the function of TPM. The structure of key data mapping is implemented outside TPM. As shown in Figure 2, the thick lines represent the key flow between modules, while the thin ones indicate the call of function between functional modules.

Figure3:Key Structure of Cloud

 Upon activating the TPM (or upon reset), the TPM will use its random number generator to create a new base 2048-bit SRK key. The SRK is required to be non-migratable and to be a 2048 (or greater) storage key, but other parameters are left to the end user. The parameters include whether authorization is required to use the key and what that authorization is.  Create EK (Endorsement Key), especially this key does not involve in the Key Tree, When a TPM comes to a new user, it typically does not include anything other than an endorsement key (EK), EK is used for authentication when the user needs to share some keys or use others' keys.  Create a Cloud Platform Migratable Key which is wrapped by its father key-SRK, the construction of a RSA Key contains the following steps: first, call RNG method to generate a 1024 bits or 2048 bits pair that includes public key and a private key p(we choose 1024 bits); second, construct a structure that can be used by TPM, in this structure, we can configure a series of attributes like "migratable" or "non-migratable", after the construction, we will move the key from the inner of the TPM to persistent storage.  Create User1 Migratable Key which is wrapped by its father Platform Key. If the client end has another user, then create User2 Migratable Key.  User1 creates a Binding Key (used for encrypt symmetric key) which is wrapped by User1 Migratable Key.  If user1 want to encrypt a file, he will create a AES Key(a leaf in the key structure ) and wrap the key by one of his binding key.  If user1 have some classified data and he is sure that he does not need to share it with some other ones. hence, he can create a User1 Non-migratable Key, the rest steps are same to a Use1 Migratable Key.

Data Processing Service

Data Processing Service contains Data Encryption Service and Data Decryption Service.

A user Alice stores her data in the cloud. Before it is sent to the cloud, the data encryption service will call the function of RNG to generate a symmetric key (we adopt a 256 bits AES key), then the service uses the symmetric key to encrypt the upload filter of the data. After the encryption, the service encrypt the symmetric key by one of the user's binding key, then input the relation between the symmetric key and the binding key and the relation between the encrypted file and binding key into a map.

When Alice gets a file from the cloud, after the authentication of TPM, the client will open a download filter. The Data Decryption Service will get the key related to the file according to the map stated in the 3.2, then use the Key to decrypt the download filter, then Alice get the plaintext.

The Backup Service

As stated in Specification of Trusted Computing, the non-migratable key cannot be migrated out from the TPM. So, in this section, we talk about the backup of migratable keys. In addition, as all we know, public key in the migratable key is not sensitive. The goal we will achieve is to ensure the private key must not be got by illegal parties when we move this private part of key out of TPM.

1. We design a structure to describe the migration authentication. In Figure 4, TPM owner authorize three kind of authority to the migratable key. The first is use authority that means the key can be used by legal customers. The second is migration authority that means the key can be migrated by the owner of the key. The third is encryption authority that means the key can be encrypted by trusted third parties (generally, trusted third party indicates the customer whom you want to share your key with). Combine the three authorization we get a migration authentication structure: Migrationkey represents the public key provided by the trusted party. Migration Scheme represents the scheme in which key will be migrated. When TPM owner change, the TPM Proof changes too, hence the digest, at this case, the MIGRATIONKEYAUTH will be invalid. 2. Check the migration authentication structure to see if the key is migratable and if the wrapping key has the authority to wrap the migratable key. If both checks are passed, we can get the migratable key from key structure stated in Chapter 3.1. 3. Construct the backup structure, as shown in Figure 5, the construction contains three steps:  Use OAEP (defined in RSA PKCS1 V2.1) to codify the key object that is attained in the step 2. The process protects the key from being tampered by vicious cloud storage manager.  Call the RNG method to generate a random, and XOR it with OAEP(Key Object), then we get the inner layer.  Use the authorized public key to encrypt the inner layer, then we get the outer layer 4. The backup object can be stored in many ways. When we need to inject the backup object, the process contains 4 steps.  Customer input password get the authority to communicate with TPM in the target platform.  The target platform receives the backup object, and then, the TPM gets the private key from the key structure.  Decrypt the backup object with the private key, then we get the inner layer  After the Key owner provides the random which is used in the backup construction process, we can use the random to XOR the inner layer to get the key object.

The Key Sharing Service

The key sharing service will use the backup structure stated in Chapter 3.3. The sharing process concludes:  When customer Alice needs to share a file with Bob, first, Bob will send a public key (the corresponding private key has existed in the key tree in Bob's TPM) to

Alice.  Alice use the public key to create a backup object by the process stated in Chapter 3.3, after the process, Alice sends the backup object to Bob.  After Bob receives the backup object, he will use the process stated in the chapter 3.3 to inject the key object into Bob's TPM. After the injection, Bob can use the key freely.

Constructing the prototype and the performance evaluation

We implement PDPS in HDFS (Hadoop Distributed File System). Our experiment is constructed using four computers with an Intel Core 2 processor running at 1.86 GHz, 2048 MB of RAM, and a 7200 RPM Western Digital 250 GB Serial ATA drive with an 8 MB buffer -one namenode, two datanodes, and one client. As shown in Figure 6, they are all in the same Ethernet. Compared to HDFS without a PDSP, the time we will used for PDPS (when uploading a file) includes the time it costs to generate a symmetric key, the time it costs for encryption of the file upload filter, and the time it costs for encryption of the symmetric key and persistence of the symmetric key. Especially, the time cost for encrypting the file upload filter is offset by the time cost for uploading the file. Table1 shows the time we cost when we upload various kinds of data with the PDSP comparing the uploading without a PDSP.Table2 shows the time we cost when we download files of various amounts.

Table1: From Table1 and Table2, we can see the cost percentage decreases when the file size is growing. So we can make a conclusion that the PDSP suits for the cloud storage system that cope with files with large size like HDFS.

Conclusions and Future Work

In this paper, we have presented the architecture of private protecting service to keep the data in cloud safe. In the service, we explored a new fashion of data backup in a more flexible way. If user1 want to backup all his keys, he just needs to construct only one backup object-user1 migratable key. If the cloud system platform needs backup all its keys, it just needs to construct only one backup object-cloud platform migratable key. So, the same cost to the key sharing service. In the further study, we will implement the smaller unit of data process like Chunk in GFS, or block in HDFS and propose detailed designs for the authentication framework that will be used in key sharing service based on signature, remote attestation. The private data protecting service can be adopted by almost all of the cloud storage system, because it is based on the client end and have no interaction with the server or cloud provider.

Figure 1 :

 1 Figure 1: Basic key structure of TPM

Figure 4 :

 4 Figure 4: Migration Authentication Structure

Figure 5 :

 5 Figure 5: Backup structure

Figure 6 :

 6 Figure 6: Architecture of HDFS with PDPS

Acknowledgement. This work is supported by National Natural Science Foundation of China under Grant No. 60873238, 61073156, 61070237, 60970135, and our IBM SUR 2009 Project.