Kai Li

Yuhui Deng
email: tyhdeng@jnu.edu.cn

Accelerating the Reconstruction Process in Network Coding Storage System by Leveraging Data Temperature

Over the past few years, network coding has been employed in data reconstruction process of storage systems to minimize the recovery bandwidth. However, the time consumption of the decoding operations incurs a significant performance degradation. In this paper, we propose a data temperature-based reconstruction optimization algorithm and integrate it into the reconstruction process of a Network-Coding-Based File System (NCFS) which adopts regenerating code as its storage coding scheme. We conduct extensive experiments to evaluate the impacts on the data reconstruction process of regenerating codes. The experimental results demonstrate that our method outperforms the conventional approach both in reconstruction time, throughput and average response time with up to 33.17%, 60.61%, 37.77% improvement, respectively.

Introduction

Distributed storage systems have been widely deployed in industry to provide massive data storage service [START_REF] Ghemawat | The Google File System[END_REF][2] [START_REF] Calder | Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency[END_REF]. In such storage systems, data is allocated into a number of nodes in a stripe manner which enhances read/write performance in parallel ways. Since node failures are common [START_REF] Ghemawat | The Google File System[END_REF], when a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. Therefore, redundancy must be introduced to reconstruct data. The simplest redundancy method is replication, which places several copies of same data in different nodes.. Erasure coding provides the same reliability as replication but requiring much less storage space [START_REF] Rodrigues | High availability in DHTs: Erasure coding vs.replication[END_REF] [START_REF] Weatherspoon | Erasure coding vs. replication: A quantitative comparison[END_REF]. This technique departs one piece of data into d pieces and then encodes them into n pieces (n>d), then stripe encoded data. Such that any d of them are sufficient to reconstruct the original data. So, when we want to reconstruct a failed node, at least k times size data must be read from surviving nodes to participate in the decoding process, while in replication the repair of one replica needs that only one other replica is read.

Dimakis [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF] proposed Regenerating Codes that stem from the concept of network coding [START_REF] Ahlswede | Network Information Flow[END_REF] and minimize the repair traffic among storage nodes. They exploit the optimal trade-off between storage cost and repair traffic, and there are two optimal points. One optimal point refers to the minimum storage regenerating (MSR) codes, which minimize the repair bandwidth subject to the condition that each node stores the minimum amount of data as in Reed-Solomon codes. Another optimal point is the minimum bandwidth regenerating (MBR)codes, which allow each node to store more data to further minimize the repair bandwidth. The construction of MBR codes is found in [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF], while that of MSR codes based on interference alignment is found in [START_REF] Rashmi | Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage[END_REF], [START_REF] Suh | Exact-Repair MDS Code Construction using Interference Alignment[END_REF]. We focus on MBR codes in this paper.

Therefore, using minimum bandwidth regenerating (MBR) codes can improve the performance of data recovery in case of node failure, while requiring less download bandwidth than traditional replication and erasure coding. However, recent work [START_REF] Duminuco | A Practical Study of Regenerating Codes for Peer-to-Peer Backup Systems[END_REF] has shown that regenerating codes takes too much computation overhead during data reconstruction which significantly increases the reconstruction time. Meanwhile, the time to rebuild a single disk has lengthened as the disk capacity far outpaces the disk bandwidth. Furthermore, the longer the period of single disk repair takes, the higher the possibility of a disk failure, which would probably lead to unrecoverable data loss. Hence, accelerating the data reconstruction process is becoming a pressing problem.

In this paper, we propose a data temperature-based reconstruction optimization algorithm in a network-coding-based file system, which uses data temperature to schedule reconstruction sequence in node recovery process. The frequently accessed data is called hot data, and the infrequently accessed data is determined as cold data. The hot data would be reconstructed prior to the cold data during the reconstruction process. Since the user request stream normally couple with the data rebuilding stream, we intend to reduce the disk seek time and disk head shuttling, so as to improve the rebuilding performance. The method is implemented atop network coding file system (NCFS) [START_REF] Hu | NCFS: On the Practicality and Extensibility of a Network-Coding-Based Distributed File System[END_REF]. Extensive experiments indicate that our approach significantly outperforms the existing reconstruction schemes in terms of reconstruction time, throughput and average response time.

The rest of the paper proceeds as follows. Section II states background and motivation, and Section III describes the design and implementation issues. Section IV presents our experimental results. Section V concludes this paper.

Background and Motivation

Definitions

Maximum-Distance Separable codes(MDS codes):

An MDS code can be defined in the following way for storage: We can divide a file of size M into k blocks, each of size M/k, encode them into n (n>k) encoded blocks and spread them to n nodes. Then, the original file can be reconstructed by any k coded blocks. This mechanism is optimal in terms of the redundancy-reliability tradeoff because k blocks, each of size M/k, provide the minimum data for reconstructing the file, which is of size M. The repair degree d is introduced for data repair, such that the repair for the lost blocks of one failed node are achieved by connecting to d nodes to recover the lost blocks. Both traditional storage codes RAID5 and RAID6 are MDS codes. . RAID-6 can tolerate at most two node failures with two code blocks known as the P and Q parities (corresponding to c1 and c2 in Fig. 1). The P parity is generated by the bitwise XOR-summing of the k = n -2 native blocks similar to RAID5, while the Q parity is generated by coefficient XOR-summing. In reconstruction, if single or double failures happen, then each lost block can be repaired from the blocks of the same segment in other surviving nodes.

+ - + - =( ) , ( β α . When β = 1, we have 2 ) 1 ( - - = k k kd B
and α = d.

E-MBR Codes

In regenerating codes, there are generally three data repair approaches [START_REF] Dimakis | A survey on network codes for distributed storage[END_REF]: (i) exact repair, which builds exactly the lost blocks in a new node, (ii) functional repair, simply reconstructs a new block that combined with the existing ones still forms an (n,k) MDS code, and (iii) a hybrid of both. Dimakis [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF] proposed regenerating codes. However, they gave only a theoretical description of the codes without discussing implementation issues or computational costs. Recently, some practical MSR codes [START_REF] Suh | Exact-repair mds codes for distributed storage using interference alignment[END_REF] and exact MBR codes [START_REF] Rashmi | Optimal exact-regenerating codes for distributed storage at the msr and mbr points via a productmatrix construction[END_REF][15] are proposed. Specifically, NCFS [START_REF] Hu | NCFS: On the Practicality and Extensibility of a Network-Coding-Based Distributed File System[END_REF] implemented exact MBR (E-MBR) code [START_REF] Rashmi | Explicit construction of optimal exact regenerating codes for distributed storage[END_REF] into its system, along with RAID5, RAID6 coding schemes. In this paper, we focus on a particular case where d = k = n 1 . For example, when n = 4 [Fig. 1 (c)2], specially, according to the formula 2

) 1 ( - - = k k kd B
, the number of total native blocks is

6 2 ) 1 ( = - - = k k kd B
. For each native block, we create a duplicate copy, so the number of duplicate blocks in each segment is also

B/(1-1/n) B RAID6 B/(1-2/n) B E-MBR 2B 2B/n
Block allocation mechanism is shown as Fig. 1. We consider a segment of B native blocks M 0 , M 1 ,…M B-1 and their duplicate blocks M

-- 0 , M -- 1 ,…M --
B-1 。 Thus, the total number of blocks in one segment is 2B = n(n-1), which means each node stores (n-1) blocks for each segment. There are n(n-1) fields for allocating if we regard it as a matrix. For each block M i , we search for a free field from top to bottom in a columnby-column manner, starting from the leftmost column; for duplicate block M -i , we search for a free field from left to right in a rowby-row manner, starting from the topmost row. Until all blocks have been distributed.

To reconstruct the data in failed node, we note that each native block has a duplicate copy, and the block and its copy are stored in two different nodes. Thus, for each lost block, we retrieve its duplicate copy from another survival node and write it to the new node. Note that based on the block allocation mechanism, each survival node contributes exactly one block for each segment. The theoretical comparison of storage cost and reconstruction traffic between RAID5, RAID6 and E-MBR is presented in Table 2.

Motivation

On the one hand, most of the distributed storage systems switch to a recovery mode after node failure to reconstruct data on a new node. On the other hand, systems continue to serve I/O requests. So we have reconstruction data stream and user request data stream contend the disk I/O simultaneously, which leads to frequent long seeks to and from the different separate data districts. Another problem is that regenerating codes take more computation than erasure codes [START_REF] Hu | NCFS: On the Practicality and Extensibility of a Network-Coding-Based Distributed File System[END_REF][12], as a result, it needs more time to reconstruct data. Based on the test results in NCFS from our research, E-MBR suffers much more reconstruction time than either RAID5 or RAID6. They are 1.326s/MB, 0.133s/MB, 0.159s/MB respectively.

We believe that scheduling reconstruction sequence with user access patterns is a fundamental way to improve effectiveness of reconstruction process. The main idea is to reconstruct the hot data prior to the cold data so as to relieve disk I/O contentions. Tian et al. [START_REF] Tian | PRO: A Popularity-based Multi-threaded Reconstruction Optimization for RAID-Structured Storage Systems[END_REF] proposed a popularity-based multi-threaded reconstruction optimization algorithm (PRO) to optimize the reconstruction process deployed in RAID-Structured Storage Systems by integrating the popularity and locality of workloads into the reconstruction process. To the best of our knowledge, our method is the first work that combines data temperature with the regenerating codes in reconstruction process.

Design and Implementation

System Architecture

The proposed idea has to track data temperature in the node so that reconstruct thread can conduct the repair sequence according to the temperature of each segment. In our architecture, there are four modules (Fig. 2.). Two of them, Scheduler and Taskexecuter, are inherent modules in NCFS. While the other two, Client and Tracker, are added by us for data temperature tracing. Data streams are represented by arrows with numbers in the Fig. 2. Streams 1,2 and 9,10 are user request data streams and reconstruction data streams respectively.

Client: It sends I/O requests to the NCFS with user access pattern, which implemented by using zipf distribution. Only read requests are considered in this paper. If the request falls on the failed segment on the failed node, reconstruct the data immediately and return it; otherwise, return the request data directly.

Tacker: Father process monitors I/O requests of Client to keeps track of access frequency of each segment, and maintain a segment number for next reconstruction. Child process communicates with Taskexecuter, conducts reconstruction sequence by using data temperature.

We then perform the recovery operation by starting reconstruction thread, that is, reading data from surviving disks, reconstructing data, and writing data to a new node. In the meantime, client loads requests on the NCFS with the Zipf-like distribution workload mentioned above. Each result is the average value of at least three times experimental evaluation.

Impact of alpha.

The value of alpha indicates the dispersion degree of frequent access location. As we can see from Fig. 4. The lager the value of alpha is, the more centralized the hot data are. Apparently, the centralization of hot data is beneficial for data retrieval by reconstruction data stream and user access data stream simultaneously during the reconstruction process. The results show that DTemp perform over E-MBR at all alpha value in reconstruction time, throughput and average response time. As alpha value grows, the advantage expands. Impact of block size. We evaluate how different block sizes influence the reconstruction performance because block sizes directly affect I/O efficiency. Fig. 6 (a) shows the reconstruction time (s/MB) for different block sizes using conventional E-MBR and our method DTemp, respectively. We observe that as the block size increases, the reconstruction time decreases. The reason is that given the same amount of data, the block number decreases for a larger block size. In this way, the times of getting duplicate node and duplicate block are reduced greatly, which highly saves the Impact of node number. In this paper, we only discuss E-MBR the case of (n,d) where d = n-1. According to the coding scheme of E-MBR, each segment contains n(n-1) blocks, and every nodes own n-1 blocks of one segment while each of these n-1 has a duplicate in other n-1 nodes respectively. When a node corrupts, all need to do is to find the duplicate blocks and copy them to the replacement node to accomplish reconstruction. As node number grows, segment size grows as well, but segment number in one node will reduce. As a result, it leads to access reduction of duplicate block read operation on one single node but gain more nodes contributing duplicate blocks together in a parallel way. That's why with node quantity grows, reconstruction performance improves. In this paper, we exploit data temperature into the reconstruction process of regenerating codes, which reconstruct the hot data prior to the cold data. We implement our method, call DTemp, alongside with NCFS reconstruction mechanism. Our experimental results prove that DTemp does better performance than existing E-MBR reconstruction with up to with up to 33.17%, 60.61%, 37.77% improvement in terms of reconstruction time, throughput and average response time. We believe that there are still many directions for future research on our work. One direction is to include more regenerating code schemes to evaluate reconstruction performance using data temperature for horizontal comparison. Another idea is to investigate the impacts of DTemp in distributed storage system with real workload.

RAID5:

  In Fig. 1 (a), for special case n = 4, RAID5 is a (4,3) MDS code where n = 4, k = d = 3. RAID5 can tolerate at most a single node failure. In each segment, the sole code block is generated by the bitwise XOR-summing of the k = n -1 native blocks. In reconstructing, the lost block can be rebuilt from the other n -1 blocks in the same segment via bitwise XOR-summing. RAID6: In Fig. 1 (b), RAID6 is a (4,2) MDS code where n = 4, k = d = 2

Fig. 1 .

 1 Fig. 1. The data layout of RAID5, RAID6, and E-MBR code for the case n = 42.2 MBR Codes

6 .

 6 According to formula α = d, we have α = d = 3, which means each node stores 3 blocks. When a node fails, each of living d = 3 contributes β = 1 block to reconstruct data on a new node.

5 .

 5 Impact of alpha on average response time Fig. Impact of alpha. E-MBR is not affected by alpha. The E-MBR curve on the graph just for comparison.

6 .

 6 computational cost. On the other side, average response time (Fig.6(c)) increase because reconstruction time of each block lengthened. Impact of block size on reconstruction time (b) Impact of block size on throughput Impact of block size on average response time Fig. Impact of block size

  Impact of node number on reconstruction time (b) Impact of node number on throughput

7 .

 7 Impact of node number on average response time Fig. Impact of node number 5 Conclusions and Future Work

Table 1 .

 1 Parameters of a regeneration code.

	dβ	reconstruct bandwidth, the total amount of data downloaded to reconstruct a failed node

Parameters Descriptions n number of storage nodes B size of the source data to be stored, in terms of number of blocks α storage capacity of each node, in terms of number of blocks k the original file is recoverable from the data in any k nodes d and β on failure of a node, the replacement node connects to any d of the existing nodes, downloading at most β blocks from each of them

Table 2 .

 2 The Theoretical Overhead of RAID and E-MBR

	Codes	Storage Cost	Reconstruction Traffic
	RAID5

Acknowledgments

. This work is supported by the National Natural Science Foundation (NSF) of China under grant (No.61272073, No. 61073064), the key program of Natural Science Foundation of Guangdong Province (no. S2013020012865), the Scientific Research Foundation for the Returned Overseas Chinese Scholars (State Education Ministry), the Educational Commission of Guangdong Province (No. 2012KJCX0013). The corresponding author of this paper is Yuhui Deng.

Fig. 2. System Architecture

Data reconstruction process: When node failure occurs, NCFS starts Scheduler and Taskexecuter. In the meantime, Client and Tracker begin to work. Scheduler receives reconstruction parameters and schedules reconstruction task, then sends task parameter struct to Taskexecuter telling it which task is going to be executed. Before task begins, Taskexecuter obtains data temperature characteristic from Tracker, then Taskexecuter launches reconstruction algorithm to rebuild data on the new node, until all the data have been reconstructed. The two major algorithms are detailed as below: Example: We describe our idea by Fig. 3, which shows a (4,3) E-MBR code and failures node 0. After node 0 failed, client continue to access data from node 0, the requests land up in different segments, which makes segment 1 the hottest zone, segment 0 and segment 2 in node 0 are relatively cold. When reconstruction thread starts, it selects segment 1 to rebuild data first. Inside segment 1, block rebuilding shall be at sequence order by finding corresponding duplicate blocks and copying them from other living nodes. In this case, reconstruction order should be segment 1:block 0 → segment 1:block 1 → segment 1:block 2 → segment 0:block 0 → segment 0:block 1 → segment 0:block 2 → segment 2:block 0 → segment 2:block 1 → segment 2:block 2.

Implementation Issues

Reconstruction unit. Compare to the original approach reconstructing data block by block, our method use segment as a reconstruction unit. Considering that the data in the same segment are organized by the same allocation mechanism, it is more computational saving to recover all blocks in a segment once at a time than to recover each of them separately. On the other hand, spatial locality indicates that likelihood of referencing a resource is higher if a resource near it was just referenced. So blocks in the same segment would be very likely to be accessed by one request. Furthermore, preserving the inherent sequentiality segment is more conform to the disk drive I/O pattern which is at many times the bandwidth of random accesses. This will lead to reduction of disk head rotations so as to save more reconstruction time.

4

System Evaluation

Experimental Settings

Our testbed is built on an open-source Network-Coding-Based Distributed File System (NCFS) [START_REF] Hu | NCFS: On the Practicality and Extensibility of a Network-Coding-Based Distributed File System[END_REF], which supports a specific regenerating coding scheme called Exact Minimum Bandwidth Regenerating (E-MBR) codes [START_REF] Rashmi | Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage[END_REF]. We implement our approach DTemp on NCFS in the reconstruction process of E-MBR exploiting data temperature. The platform consists of 2.4GHz CPU, 2G DDR3 Memory, WDC WD5000AADS-00S9B0 disk, CentOS release 6.3 (Final), and NCFS 1.2.1. User access pattern is usually in accord with Pareto principle. Therefore, we use Zipf's law to imitate the distribution of workload characteristic from client. The Zipflike distribution formula [START_REF] Breslau | Web Caching and Zipf-like Distributions: Evidence and Implications[END_REF] depict this rule, given by , ) (

Workloads

Let N be the total number of blocks in the node. So Ω is also a constant, while P N (i) should be the conditional probability of the ith block. For example, we have 10 blocks accessed by 10000 requests, then the Zipf-like distribution is shown in Figure 5. When α = 1, block 0 and block 1 receive 7369 read requests while the other 8 blocks receive 2631 requests in total, which almost conform to the 80-20 rule.

Performance Evaluation

We are mainly interested in the metric of reconstruction performance including Reconstruction time, throughput and average response time. We obtain the experimental results as follows. We write 100MB of data into each node via NCFS using E-MBR. We disable one of the nodes in the array to make a single node failure.


Yuan Gao

Rui Wang
email: rui.wang@jsi.buaa.edu.cn

Ning An

Yanjiang Wei

Depei Qian

Speedup Critical Stage of Machine Learning with Batch Scheduling in GPU

Keywords: convolution neural network, framework, GPU, batch process

As a superior data analysis method, Machine Learning suffers the bottleneck from limited computing capability for many years. With the advent of numerous parallel computing hardwares, modern G-PU is becoming a promising carrier for the tasks of Machine Learning. In this paper, we propose an efficient GPU execution framework to speedup the forward propagation process of convolution neural network. By extending the convolution unrolling method to fit this batch mode, we get a significant increase of throughput but very little overhead.

Introduction

With the fast-development of computer hardware, GPU has become a type of important computation carriers with dramatic speedup and better energy efficiency. More and more computing-intensive applications with natural data parallelism have been migrated to GPU environment. However, although the NVIDIA CU-DA can help programmers to develop faster applications, programming on GPU is much more difficult than that on CPUs. Programmers need to determine the timing of copying the data from the host to the GPU, the number of blocks or threads that should be divided reasonably to take full advantage of computing resources, and the size of data slice that should be allocated to each thread. It is quite difficult to develop a framework for a beginner to write efficient GPU programs in any purpose. However, research on high productivity method both in coding and in execution for special domains is promising.

CNN GPU Execution Framework

In this section, we take the image recognition application as an example to illustrate the operating mechanism of our framework.

Batch Process

Improving the GPU computing resource utilization is a good way to speed up the forward propagation since the computing hardware resource of GPU is quite rich and forward propagation cannot take full advantage of GPU's ability if only handle one small size image at a time. What we can do, however, is to try to increase the throughput in a single task, which means the CNN processes several images in one forward propagation. The figure 1 presents the proposed framework which shows two of the most important modules: the input organization module and the convolution module. The input organization module automatically splices tiny input images into a larger one before CNN executes on GPU. The convolution layer requires the most amount of the calculation and is also the optimization emphasis of our framework while the traditional convolution layer speeding up method involves unrolling convolution

In our framework, we extend the simple unfolding of a convolution technique to a batch mode which enables the convolution layer to process multiple images (input features) at the same time.

When the spliced image (input features) arrives at the convolution layer which came from the host or last layer a split operation is necessary at first. As we know, each layer of the neural network has its fixed input size that is obviously the processing layer's input size is 3 × 3 in the figure 2. According to this input size, the framework will split the spliced images (input features) into the standard size before unrolling convolution. The convolution operation works in a similar way except the unrolled input features from different images need to be added to the bottom of input feature matrix. As shown in the figure 2, the spliced image (input features) will be divided into nine 3 × 3 input features and be unrolled to a 12 × 12 input feature matrix and the kernel matrix is exactly same as the traditional unrolling convolution. After multiplying input features matrix by the kernel matrix, we get a 12 × 2 output feature matrix that is still able to find the boundary of different images. Instead of convoluting the three images in a row, the batch mode unrolls three images to one matrix and does only one multiplication to get the output features.

0 1 1 0 0 0 2 1 3 0 0 0 1 2 0 1 0 1 1 1 0 2 0 2 1 0 2 0 2 1 0 0 0 0 3 1 0 1 0 1 1 1 0 3 0 2 1 2 1 0 2 1 2 1 1 0 3 0 2 1 0 3 1 1 1 0 0 3 0 1 1 3 2 1 1 0 1 0 2 0 2 1 1 1 1 1 0 1 0 3 0 1 1 3 1 3 2 0 1 3 2 0 1 0 1 0 0 3 0 0 3 1 0 1 0 1 0 0 3 0 1 3 2 1 1 0 3 1 0 3 1 1 3 1 1 3 0 1 1 2 3 0 1 3 1 9 9 6 6 6 6 6 6 6 6 6 6 6 6 1 1 1 1 1 14 14 12 10 15 Img2 1 1 13 9 9 1 1 13 9 9 9 9 9 9 9 9 9 9 1 1 1 19 9 13 16 10 12 1 1 Img2 1 1 1 1 13 3 1 1 1 13 16 2 1 1 1 1 1 13 3 1 1 1 1 1 1 1 16 1 1 1 1 12 8 10 9 10 1 0 1 14 4 1 1 1 12 2 1 15 5 8 9 8 13 Img1 3 3 3 3 3 2 2 2 2 0 0 0 0 0 1 1 1 1 1 2 1 1 2 2 1 1 1 1 0 0 3 3 0 0 2 2 1 1 0 0 0 3 3 3 1 1 1 1 1 1 2 1 1 0 2 2 0 0 1 1 3 3 2 2 0 0 1 1 0 0 Figure 3 and compared the execution time between the two methods, and in the experiment, the filter size is 5 and the number of output features is fixed by 10. We, however, still take the image dimension and the splicing number as variables.

0 2 1 2 0 1 1 1 2 1 1 0 0 1 1 1 2 0 2 0 1 1 0 * =
1 1 1 0 0 0 3 0 1 2 1 3 1 1 3 Img2 2 0 1 1 0 1 3 1 2 Img3 1 1 2 Img 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 0 0 0 2 1 0 1 0 3 2 0 1 Img2 2 0 0 1 3 1 2 1 3
Img1 1 2 2 1 1 1 0 1 1 0 0 1 0 1 0 1 2 1 0 1 2 2
0 0 0 0 1 0 3 2 1 1 1 0 1 Img2 2 2 0 0 1 Im Img g g2 2 3 3 3 1 1 1 2 2 0 0 1 1 g g g 1 1 3 3 1 1 1 0 0 0 0 0 1 2 1 0 1 2 0 1 Img1 0 0 0 1 1 1 1 3 3 1 2 2 1 1 1 1 1 0 0 0 2 2 0 0 0 Im Im Img g g2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 1 1 1 1 1 1 Im Im Img g g 2 2 2 2 2 2 2 2 2 2 2 1 1 1 0 0 1 2 1 1 0 0 3 Img1 0 0 0 0 0 0 2 2 2 1 1 1 1 1 0 0 0 Im Im Img2 2 1 1 0 0 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 Im Im Img2 2 3 3 3 3 0 0 0 3 0 2 0 0 2 3 1 2 Img1 3 3 3 0 0 0 0 0 0 0 0 0 1 1 2 2 0 0 1 1 1 1 0 2 0 1 1 1 2 2 2 0 0 0 1 1 0 0 0 0 2 2 1 1 0 1 1 1 3 3 0 0 0 0 0 0 0 2 0 2 1 1 0 0 2

Conclusion

In this paper, we propose an efficient neural network framework on GPU platforms. Our framework addresses the gap in abstraction between domain experts and current GPU programming frameworks, and accelerates the process of CNN forward propagation. The framework can organize the input data automatically to make use of GPU resources as much as possible for better performance. We demonstrate the advantage of our framework in each CNN phase with five experiments. According to the power of GPU, framework can extremely increasing the throughput of CNN. The optimization method that we adopt in the framework doesn't modify the structure of CNN or require training extra neurons, which can combine with other optimization method to achieve better performance.

Fig. 1 .

 1 Fig. 1. Proposed GPU execution framework schematic.

Fig. 3 .

 3 Fig. 2. Example batch mode unrolling convolution.

Acknowledgment

This research is supported by 863 Program of China under grant 2012AA010902, and by the NSFC under grant 61133004, 61073011, 61202425, and Huawei company under grant No.YB2012120105.


Shu-Ching Wang

Shih-Chi Tseng

Hsin-Met Chuan

Kuo-Qin Yan

Szu-Hao Tsai

The New Territory of Lightweight Security in a Cloud Computing Environment

The cloud computing is an Internet-based resource sharing system in which virtualized resources are provided over the Internet. Cloud computing refers to a class of systems and applications that employ distributed resources for use in various applications; these computing resources are utilized over a network to facilitate the execution of tasks. However, cloud computing resources are heterogeneous and dynamic, connecting a broad range of resources. Thus, there are a large numbers of application and data center in the cloud computing environment. Therefore, the security issues of authentication and communication in application services and data center need to be considered in the cloud computing environment

Result

In this study, two security methods for client user are presented. (1) Group Key Authentication (GKA) is proposed for user to obtain the services from multiple servers quickly. And. (2) Authentication and Authorization within Two Factors (AATF) provides a more stringent authentication and authorization, and the security of cloud computing can be enhanced.

.

6. Key Req.: After AUTH Server receives the service request, it will send the Key Request and ID to Service Servers. 7. Key Res.: When Service Server receives the request and ID, an authentication key is generated, and the key and ID are stored. In addition, Service Server sends the authentication key to AUTH Server. When AUTH Server receives the authentication key; then the Group Key will be assembled and stored. When the user authentication group key is established, a one-time identity verification for several services is available to users. The format of Group Key = (SERVICE 1 ||SERVICE 2 ||… ||SERVICE n ||ID). If a new service requirement is presented by user, the key of the certification of the new service will be given, and the new authentication key is combined to the GK. Moreover, every authentication key is generated by Service Server randomly.

AATF security mechanism for the user during authentication and authorization process is used to strengthen the legitimacy of authenticating users and improve the security of user accounts. The execution flow of AATF is shown in Fig. 2.

Step 1. The user generates a set of random numbers, and then a random number RN with Request sent to the application server side.

Step 2. Application server-side receives a random number RN with Request, return the SC to the user, and will direct users to the authentication server-side. Step 3. Users will send UN, PWD and SC to the authentication server-side for authenticating.

Step 4. When the authentication is successful, the authentication server-side will sent the AuT and S to the user, if authentication fails then return a failure message to the user. Step 5. The receiving AuT and S by user will be retrieved in accordance with the number of RN to generate sRN, and then S and sRN are sent to the application server-side authentication. Step 6. The compare action of authentication and authorization will be started when application server received the S and sRN; the ApT is returned to user when authentication and authorization is passing; if fail, the fail message is returned.

Step 7. When Users receive the ApT, ApT and AuT are combined into a Token, and then Token can be passed to the application for using the service. There are a lot of services and users in the cloud computing environment, will be carried out to verify the identity through authentication and authorization protocol [4]. Therefore, the authentication and authorization are always making in cloud computing environments. When authentication and authorization requires a lot of steps and a large number of parameters, data exchange will be increased and the amount of resources needed to make authentication and authorization will be increased. Therefore, the number of steps, the total number of parameters and the amount of data exchanges will be used for comparison. Then, the authentication protocols proposed in this study can be verified as the lightweight computing security protocols. Form Table 1, the steps of certification, the total number of parameters and the amount of data exchange of GKA by AATF are less than OAuth [1] and the SAML [1]. Overall, our proposed lightweight security mechanisms can provide the security of information and communication and authentication, without wasting computing resources to enhance the security of cloud computing environment. Therefore, Group Key Authentication (GKA) is used to provide the services that users can quickly obtain multiple servers to improve security by reducing the transmission of secret information in the cloud computing environment. GKA also can reduced the number of users must be logged conversion services and waiting time. Authentication and Authorization within Two Factors (AATF) in the cloud computing environment at both ends of the server-side two-factor authentication through the authentication server-side services can provide more stringent authentication and authorization in order to verify the legitimacy of the identity of the user to enhance the cloud computing security.

Cloud computing is a concept in distributed systems. It is currently used mainly in business applications in which computers cooperate to perform a specific service together. In addition, the Internet applications are continuously enhanced with multimedia, and vigorous development of the device quickly occurs in the network system. As network bandwidth and quality outstrip computer performance, various communication and computing technologies previously regarded as being of different domains can now be integrated, such as telecommunication, multimedia, information technology, and construction simulation. Therefore, cloud computing is currently used many commodity computers that can cooperate to perform a specific service together [2]. Thus, applications associated with network integration have gradually attracted considerable attention.

In a cloud-computing environment, users can access the operational capability faster with Internet application, and the computer systems have the high stability to handle the service requests from many users in the environment [5]. Today, a new application service of operation system is emerged and it changes the user's usage in the past. Originally, the Internet infrastructure is continuous grow that many application services can be provided in the Internet. The reliability is improved in a cloud computing by using the low-power hosts. In addition, cloud computing has greatly encouraged distributed system design and application to support user-oriented service applications. Furthermore, there are a large number of cloud applications and data centers provided in the cloud computing environment, so the information and communications, and authentication is one of the important security issue that must be considered. In other words, the security is one of the most important aspects of cloud computing as it ensures overall reliability and fluency. To ensure the cloud computing is safety, a mechanism to ensure the security of information and communication is thus necessary.

Therefore, Group Key Authentication (GKA) is used to provide the services that users can quickly obtain multiple servers to improve security by reducing the transmission of secret information in the cloud computing environment. GKA also can reduced the number of users must be logged conversion services and waiting time. Authentication and Authorization within Two Factors (AATF) in the cloud computing environment at both ends of the server-side two-factor authentication through the authentication server-side services can provide more stringent authentication and authorization in order to verify the legitimacy of the identity of the user to enhance the cloud computing security.

Through the above description, the proposed method can enhance the security in the cloud-computing environment. According to the characteristics of cloud computing, by using the proposed methods, the cost of resources can be reduced and the quality of service can be improved. The proposed security mechanisms can meet the cloud computing security step to ensure that users and service providers to enjoy the security of cloud computing environment with the service provider.

Fig. 1 2

 12 Fig.1 Group Key generatingFig.2The processes of AATF

Table 1

 1 The comparisons with OAuth and SAML

		Step (times)	Parameter	Data Exchange
	OAuth	10	11	30/time
	SAML	8	12	14/time
	GKA	7	4	8/time
	AATF	7	11	13/time

Acknowledgments

. This work was supported in part by the Ministry of Science and Technology MOST 102-2221-E-324-008 and MOST 103-2221-E-324-025.


Guofeng Yan
email: gfyan@nudt.edu.cn

Yuxing Peng
email: pengyuxing@nudt.edu.cn

Performance Analysis of End-to-end Services in Virtualized Computing Environments ⋆

In this paper, we present a novel stochastic analyzing model for e2e virtualized cloud services using hierarchical Quasi-Birth Death structures (QBDs). We divide the overall virtualized cloud services into three sub-hierarchies, and then, analyze each individual sub-hierarchy using QBDs. Our approach reduces the complexity of performance analysis. Our results are useful to prevent the cloud center from entering unsafe operation, and also reveal practical insights into load balancing and capacity planning for virtualized computing environments. . . .

Introduction

Theoretical analyses on cloud services mostly rely on extensive research in performance evaluation of M/G/m queuing systems, as outlined in [START_REF] Ma | Approximation of the mean queue length of an M/G/c queueing system[END_REF]. Using the distribution of response time, researchers discover the relationship among the maximal number of requests, the minimal service resources and the highest level of services [START_REF] Yang | Quantitative survivability evaluation of three virtual machine-based server architectures[END_REF]. However, as solutions for distribution of response time and queue length in M/G/m systems cannot be obtained in closed form, suitable approximations are sought. To ensure that the quality of service (QoS) perceived by end clients is acceptable, in [START_REF] Khazaei | Performance analysis of cloud computing centers using M/G/m/m+r queueing systems[END_REF], the performance of cloud server farms with general service time is analyzed. The researchers propose a general analytic model for e2e performance of cloud services. However, the proposed model is limited to the single arrival of requests and the start up delay of cold physical machines (PMs) has not been captured. The effect of virtualization on e2e cloud QoS need to be further studied based on these previous research.

System model

We assume that L different servers, M distinct users, and N types of requests for each user. A type-k request, Req k , is specified a type-k VM-conf iguration V M k , and V M i k is the provisioning V M k on server i. Assume that a global resource provisioning and deploying decision machine (RP&DDM) processes requests on a FCFS principle in our system and each request arrives stochastically at RP&DDM, and we define the size of the request Req k as |Req k |. Let S = {active, passive} be the state set of RP&DDM. In active, an arriving request can be served immediately; in passive, an arriving request can only be processed after PMs are redeployed. Assume that the requests of user k arrive according to a Poisson process with rate λ k (λ 1 = • • • = λ M ), each server maintains N different queues (i.e., q i1 , q i2 , • • • , q iN ) for N different types of requests, and the processing time of Req k on each server is exponentially distributed with parameter

µ k (µ 1 = • • • = µ N = µ).

QBDs Stochastic Model for cloud computing system

Let λ = ∑ M i=1 λ i = M λ i and Q req denote the finite queue of all requests. We consider two state spaces: Λ and Λ i k . Λ = {Y (t), s t } describes the general characters of RP&DDM, where Y (t) = 0, 1, 2, • • • , Q denotes the number of requests in Q req , and s t ∈ S refers to the state of RP&DDM at time t.

Λ i k = {(Y i k (t), r i kj , s i t ) : j = 1, 2, • • • , Q; r i kj 0; s i t = 0, 1} captures the charac- ters of type-k request on server i, where r i kj , Y i k (t)
and s i t refer to the remaining size of the jth type-k request on server i, the the number of requests in q ik at time t, and the current state of server i, respectively. Let s t = 0 and s t = 1 denote that s t is passive and active, respectively. Then, each state of Λ can be expressed as a combination (Y (t), s t ). We compute the transition rates of the QBDs according to [START_REF] Yan | Performance analysis for (X, S )-bottleneck cell in large-scale wireless networks[END_REF]. Let the probabilities of RP&DDM being in active, and passive at time τ i be 1 -e -p (τi) , and e -p(τi) , respectively. Hence, we obtain the transition probabilities of RP&DDM from time τ i to τ i+1 from p Λ 00 = e -p(τi)-p(τi+1) , p Λ 01 = e -p(τi) -e -p(τi)-p(τi+1) , p Λ 11 = 1 -e -p(τi) -e -p(τi+1) + e -p(τi)-p(τi+1) , and p Λ 10 = e -p(τi+1) -e -p(τi)-p(τi+1) . For the state space Λ i k , let r i kj (t) be the remaining request size of the jth type-k request on server i at time t, and r i k (t) the queue state of type-k request on server i. Then,

Y i k (t) = {r i k (t)} k,i is QBDs on Λ i k [1].

Performance evaluation

Rejection probability of Req k . Let p f ull reject and p passive reject be the rejection probabilities of Req k due to Q req full and no active VM-conf iguration, respectively. Assume that s and π (Q,s) are the state of RP&DDM and the stationary state probability of the first hierarchical QBDs, respectively, 1 γpassive is the mean searching delay to find a passive server, π ik (n, passive) and λ ik are the stationary state probability. We can obtain p f ull reject and p passive reject from p f ull reject =

1 N ∑ s∈{active,passive} π (Q,s) and p passive reject = ∑ L i=0 ∑ Q n=0 γpassive•1-π i passive •π ik (n,passive) λ ik .
Then, the rejection probability p reject is:

p reject = ∑ s∈{active,passive} π (Q,s) + L ∑ i=0 Q ∑ n=0 γ passive • p i passive • π ik (n, passive) λ ik (1)
We use simulations to evaluate the acceptance probability (i.e., 1 -p reject ). Let L ∈ {50, 100, 150, 200} and M ∈ [50, 600] users. We carry out our simulation with δ = 0.75, λ k = 0.05, µ = 0.5, and 1/γ passive = 5. The experiment results and the calculative results are shown in Fig. 1. From Fig. 1, the calculating results of our analytical model and the simulation results are very similar. When M > 350, the acceptance probabilities seriously decrease with the increasing of M and it means that the system capacity of cloud computing is not enough for more than 350 users. Furthermore, we find that the acceptance probabilities for L = 200 are steady for all M and more than 0.95. These results show the benefits of adding more servers are reflected by having higher acceptance probabilities of user requests for a fixed µ and λ k . E2e response delay. Let T w denote the waiting time in the steady state, and W (x) and W * (y) be the CDF of T w and its LST, respectively. Let f (z) be the generation function of Q l , and we can obtain , respectively, where 1/γ active and 1/γ passive are the mean search delay when server i being in states active and passive. Therefore, the mean e2e delay of Req k , T e2e , is:

f (z) = W * (λ(1 -z)). Let z = 1 -y/λ and we have W * (y) = ∑ k=L-1 k=0 π (k,s) + ∑ k=2L k=L π (k,s) (1 -y/λ) k-L according to [1]. Hence, we get E[T w ] = ∑ k=2L k=L (k-L)π (k,
T e2e = E[T w ] + E[T d ] + E[T e ] (2)
The calculating results and simulation results in Fig. 2 show increasing the number of users will increase the response delay. For a small cloud server cluster (for example, L < 50), increasing the number of user will increase rapidly the response time of request. But for a large cloud server cluster (for example, L > 200), the response delay of request does not distinctly varies due to its enough capacity. Based on these information, cloud computing systems can achieve an more effective admission control policy to guarantee e2e cloud QoS.

Conclusion

We analyze the effect of virtualization on the IaaS cloud service quality. Our model is flexible in terms of scalability and diversity of requests and cloud computing clusters. However, we do not consider the remaining time of time slots when a request is finished before the given time slot terminates. Therefore, how to improve the precision of the analytical results is our further work.

Fig. 1 .

 1 Fig. 1. Effective request acceptance probability of Req k vs different number of users with µ = 0.5 and λ k = 0.05

Fig. 2 .

 2 Fig. 2. Mean response time vs different number of users with µ = 0.5 and λ k = 0.05

  s) λ . Similarity, let T d and T e be the resource deploying delay and the mean request executing time, respectively. Then, E[T d ] and T e can be calculated by E[T d ] =

	1/γactive+p i passive /γpassive paccept	and T e =	∑ N k=1	λ ik (Lδp t 11 +L(1-δ)p t 01 ) λµ k

⋆ This work was supported by the National 973 Basic Research Program of China under Grant Number 2011CB302601, China Postdoctoral Science Foundation under Grant Number 2013M542561, and Scientific Research Fund of Hunan Provincial Education Department under Grant 14B040.


Mohammad Aazam
email: aazam@ieee.org

Eui-Nam Huh

Resource Prediction for Inter-Cloud Broker

Media content over the Internet has massively been increasing, resulting in popularity gain of cloud computing. Cloud computing is the only solution in hand to handle rapidly increasing digital media content. Through cloud computing, digital media can be manipulated, stored, and communicated in a much better and easier way. But due to increase in user's demands and diversity of applications, it is, at times, not possible for a single cloud to fulfill all the requests. At that point, multiple clouds have to communicate and share resources through an intermediary, called cloud broker. To handle requests properly, broker has to predict the amount of resources required when a service is requested. This paper focuses on this particular issue. We present resource prediction part of our model here, along with its implementation and evaluation using CloudSim toolkit.

Introduction

The rapidly increasing digital media content has already surpassed traditional media, as a result of which long-term and vast changes are required for the contents shared over the Internet. In 2010, Internet video traffic had surpassed global peer-to-peer (P2P) traffic [START_REF] Tan | Media Cloud: When Media Revolution Meets Rise of Cloud Computing[END_REF]. Excluding the amount of video exchanged through P2P file sharing, at the time being, Internet video is 40 percent of consumer Internet traffic. Since 2012, it has become over 50 percent and will reach 62 percent by the end of 2015. Counting all form of videos, the number will be approximately 90 percent by 2015 [START_REF]Cisco-White-Paper[END_REF]. This media revolution not only brings great opportunities, but also bears some challenges. To meet those challenges, much better infrastructure, sophisticated technologies, and powerful capabilities are required to be incorporated.

Cloud computing still faces some open challenges, but to provide better reliability, availability, cost-efficiency, and QoS, inter-cloud computing has already been envisioned. Research on inter-cloud computing is still in its start, but its effectiveness cannot be denied by any means [START_REF] Grozev | Inter-Cloud Architectures and Application Brokering: Taxonomy and Survey[END_REF]. Cloud Service Providers (CSPs) have their customers dispersed all around the globe. To serve them optimally, CSPs have to setup many of their data centers at different geographical locations. Existing systems are not capable enough to coordinate dynamically the load distribution among data centers, to determine optimal location for hosting services to achieve desired performance. Furthermore, users' geographical distribution cannot be predicted as well. Thus, load coordination and service distribution has to be done automatically. Inter-cloud computing is meant to counter this problem. It provides scalable provisioning of services with consistent performance, under variable workload and dynamically changing requirements. It supports dynamic expansion and contraction of resources, to handle abrupt variations in service demands [START_REF] Buyya | Intercloud: Utility-oriented federation of cloud computing environments for scaling of application services[END_REF]. In inter-cloud computing, an intermediary, broker, is responsible to identify appropriate CSP, according to the needs of its customer, through cloud exchange. Broker negotiates with the gateway to allocate resources, according to user and service requirements [START_REF] Buyya | Intercloud: Utility-oriented federation of cloud computing environments for scaling of application services[END_REF]. Resource management is a key attribute of broker. So far, the available literature addresses resource management issue in a trivial way.

In this paper, we present a part of our resource management model, in which we focus mainly on advanced reservation of resources, according to the type of customer and service. Implementation and simulation of our model was performed on CloudSim 3.0.3 toolkit.

Resource Prediction and Premium Amount Calculation

When a cloud service customer (CSC) [START_REF] Wenwu | Multimedia Cloud Computing[END_REF] requests the broker [START_REF] Aazam | Inter-Cloud Architecture and Media Cloud Storage Design Considerations[END_REF] for a particular service, broker has to further contact cloud service provider (CSP) and negotiate the contract, including service level agreement (SLA) [START_REF] Díaz-Sánchez | Media Cloud: An Open Cloud Computing Middleware for Content Management[END_REF]. For some services, broker performs ad hoc allocation of resources, while for others; resources are required to be predicted. Based on the type of service, broker's resource prediction is formulated as under:

=∑ { ( ( | )) ( ( | )) ( ) (1)
Where is required service, is the maximum cost a particular user can afford or willing to pay, n is the number of cloud customers, ( | ) is the probability of a particular customer of giving up the resource. For simplicity, we have categorized it into two, as low ( ) or high ( ) probability. ,

' ' is User Characteristic, which represents the characteristic of the requesting user, based on its history. This value is assigned by the broker, on the basis of previous resource consumption log-file of a particular user. For an altogether new user, this characteristic is set to maximum positive value for the first time. After predicting the resources, broker asks its users to pay a particular premium amount, based on following formulation:

(

Where, determines premium amount, represents probability as "low". Actual and final price is paid once the resources are started to be consumed. Therefore, in equation 3, relinquish probability is set as low, instead of both low and high. Same is the case with user characteristic, which is set as positive for low relinquish probability customers.

The implementation and evaluation of this part of model was done on CloudSim 3.0.3 toolkit. Results are presented below. Shown in figure 1, the unit is greater for L customers, having low relinquish probability, since they are more loyal, as compared to H customers. Prices for a total of 9 services have been shown, ranging from USD 100 to USD 500. On vertical axis, unit of resources to be reserved increase with the higher valued service. Better and costly service require more resources, hence, the unit of resources increase accordingly.

Figure 2 shows the premium amount to be paid, according to service type. Premium amount is shown on the top of the bars, in USD, while the values at the bottom represent the total price of services, in USD. Premium amount of each of the 9 services is shown.

Fig. 1 .

 1 Fig. 1. Resource prediction for different types of customers, according to different services.

Fig. 2 .

 2 Fig. 2. Premium amount, according to service type.

Acknowledgment. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education(No.NRF-2013R1A1A2013620). The corresponding author is Prof. Eui-Nam Huh.


Hao Xu

Baoyuan Kang
email: bbaoyuankang@aliyun.com

Yongzheng Niu

An Efficient Certificateless Blind Signature Scheme in the Random Oracle Model

Keywords: Certificateless blind signature, Certificateless public key cryptography, Random oracle model, Computational Diffie-Hellman problem

The blind signature schemes are useful in some applications where the anonymity is a thorny issue. The certificateless public key cryptography (CL-PKC) can eliminate the certificate management problem and solve the key escrow problem. In this paper, we put forward a secure and efficient CLBS scheme. We then illustrate that our new scheme is secure in the random oracle model. Also, we theoretically validate that our proposed scheme is more efficient than those existing ones in terms of computational complexity. We hope to transfer our scheme into applications.

Introduction

The blind signature was first proposed by Chaum *1+, which can provide the anonymity of signed message. Informally, blind signature allows the message owner blind the message by the blind factors, and then lets the signer sign the blinded message. At last, the message owner eliminates the blind factors of signature to get the signer's signature of the original message. Blind signature is a special digital signature, it must also meet the property of blindness differing from other signatures. Therefore, blind signature schemes can used in order to eliminate the possible abuse of linkability.

Up to now, even if there have been a lot of researches for blind signature, most of works have been based on a traditional public key infrastructure (PKI) or an identity-based public key cryptography (ID-PKC). In the traditional PKI, the trusted Certificate Authority (CA) needs a large amount of storage and computing time to manage the certificates, which are signatures of CA on the public keys of users. This is called certificate management problem. In the ID-PKC, an inherent problem of ID-PKC is that a Key Generation Center (KGC) generates any user's private key with a master key of KGC. Obviously, a malicious KGC is able to forge the signature of any signer. This is key escrow problem. To tackle the prob-lems above, Al-Riyami and Paterson *2+ put forward a new paradigm named certificateless public key cryptography (CL-PKC) in 2003, which avoids the certificate management problem in traditional PKI and eliminates the key escrow problem in ID-PKC.

Blind signature and CL-PKC have gotten fruitful achievements since they were introduced. However, to our best knowledge, little attention has been paid to the design of provably secure blind signature scheme in CL-PKC *3+. In this paper, we propose an efficient CLBS scheme based on bilinear pairings, then show that our CLBS scheme is existentially unforgeable in the random oracle model under the Computational Diffie-Hellman (CDH) problem.

The remainder of this paper is organized as follows: In Section 2, we present the construction of our new CLBS scheme. We will show that our scheme is security in Section 3. Section 4 shows efficiency comparison with the existing schemes.

Certificateless Blind Signature Scheme

In this section, we propose a secure and efficient CLBS scheme. It consists of the following seven algorithms. The details are shown as follows:

 Setup:On the input of a security parameter k , the KGC firstly selects a cyclic additive group 1 G generated by a generator P of prime order q , a cyclic multiplicative group 2 G with the same order q and a bilinear map

  3 , , , AA h H m ID P R   ,   2 , A A A T H ID P  , then check if the equation:           , , , , h A pub

Security

About the security of our CLBS scheme, we have the following two theorems. Theorem 1. The CLBS scheme is blindness. Theorem 2. The CLBS scheme is existentially unforgeable under assuming that the CDH problem in a cyclic additive group 1 G is intractable.

Efficiency Analysis

We compare our scheme with other three available CLBS schemes *4-6+ based on bilinear pairings in terms of secret key size and the required computational cost of signing and verifying. For our scheme, we omit the computation efforts which can be pre-computed by the verifier, for example, the computation of   be the binary length of an element in q Z , m P be the scalar multiplication on the curve, ex P be the exponentiation operator in 2

G and e P be the bilinear pairing operation. 1, we can clearly see that a prominent merit in our scheme is that no pairing operator is required in the whole signing process. To our best knowledge the computation of the pairing is the most time-consuming in pairing based cryptosystem. Besides, the length of the secret key is also shorter than other schemes. Thus, our scheme is more useful and efficient than the previous schemes.

Conclusion

In this paper, we put forward a new CLBS scheme on the bilinear pairings, and give some theorems of the security and efficiency analysis of our scheme, which show that the new proposed CLBS scheme is much more efficient and satisfy both blindness and unforgeability properties. Our CLBS scheme may have applications in areas such as electronic cash systems using CL-PKC.



  , picks the master key master-key * Rq sZ  at random and keeps s secret, then sets pub P sP  as the public key. Choose three secure hash functions: Partial-Private-Key-Extract: For a user with identity as the public identity of the user, and sends A D to the user as his partial private key via a secure channel, where AA D sQ  . Set-Secret-Value: Given params, the user with identity A ID selects a random Set-Public-Key: This algorithm accepts params, a user's identity A ID and secret value A x , then outputs the public key AA Set-Private-Key: This algorithm takes as input params, the signer's identity A ID , partial private key A D , public key A P and secret value A x to produce the signer's private key the following steps with the signature requester: (a) Request: The requester requests the signer for a CLBS. After receiving the request, the signer chooses * Rq rZ  at random and computes R rP   , then sends R to the requester. (b) Blind: Upon receiving R , the requester randomly picks h back to the signer. (c) Sign: The signer sends S  to the requester, where A pub S hSK rP   . (d) Unblind: The requester unblinds S  by computing

1 G

 1 . For convenient comparison, we include the following presentation, the notion denotes the bit length of an element in 1 G , q

Table .

 .

				1. Performance comparison of different schemes
	Scheme			Sign				Verify	Secret key length
	[4]	e P 3	ex P  4	7	m P	e P P ex 1 1 	2	m P	1 qG 
	[5]	2	e P P ex 1 	8	m P	e P P ex 3 1 	2	m P	1 qG 
	[6]	e P 3	ex P  2	9	m P	e 21 PP  ex	1 qG 
	Our scheme			7	m P				e 21 PP  ex

1

G

From Table


Soomi Yang
email: smyang@suwon.ac.kr

Distributed Ontology Integration Model for Cooperative Inference in Context Aware Computing

In this paper, an efficient ontology integration model for cooperative agent framework is proposed. Context aware computing with inference based on ontology investigates distributed entities on surveillance devices such as smart cameras or sensors which may carry heterogeneous data. However, even smart devices have small memory and power capacities which can only manage a portion of the ontology data. In the proposed ontology integration model, each of the agents that are built into devices get services not only from a region server, but also from peer agents with proper access control and data management.

Introduction

Context aware computing is indispensable for the construction of ubiquitous surveillance systems. Networked smart surveillance devices provide huge raw sensed data and inferred feature data. The available information is distributed over various information resources. The information resources are heterogeneous in their content, data format, organization, information management and the like. Heterogeneity of the information resources makes their integration difficult. Furthermore content within the information resources is changeable as it is continuously updated and modified. The agents installed in each smart device have constraints with regard to the memory and the power. Therefore the efficient management of their limited resources and the information is required.

Distributed Ontology Integration Model

Context aware computing regarding such as location trace requires the cooperation among the sensors [START_REF] Sankaranarayanan | Object Detection, Tracking and Recognition for Multiple Smart Camaras[END_REF]. For regional surveillance networks, a hierarchical tree infrastructure of the regional surveillance networks at the regional and administrative level similar to R-trees [START_REF] Manolopoulos | R-Trees: Theory and Applications[END_REF].

Ontology describes contexts such as concepts and relationships about target environment for the surveillance. None of single agent can accommodate the whole ontol-ogy. Each agent with a part of ontology forms a distributed graph structure. They can communicate each other freely within access control permission to perform their own intelligent distributed inference based on their own ontology [START_REF] Pan | A Flexible Ontology Reasoning Architecture for the Semantic Web[END_REF]. We intend to refine each of the local ontology groups and then develop knowledge bases by integrating several related neighboring ontologies. The regional surveillance network forms a tree structure by administrative level. If the number of children that each non-leaf node is between m and M where 2

/ 2 M m £ £ , the height of the tree is bounded by ] log , [log N N m M
when N is the number of ontology agents. Bandwidth between the agents is regulated by the tree level.

The data source agents need to carry out the indexing and retrieval of the information distributed across the agents in an efficient manner. To aid the task, a communication protocol is defined according to ONVIF standard [4]. As peers exchange information, they can negotiate and utilize caches based on the messages exchanged. For an adaptive cache management, weight of data is measured using

f s r d ki k i w h l d m =
where l is the access frequency, d is the size of data, m is the service interval and h is the distance between the agents similarly to [START_REF] Paknikar | A Caching and Streaming Framework for Multimedia[END_REF]. As a result, better utilization of their limited cache space and higher system performance can be obtained.

Performance Evaluation

To evaluate the performance of the model, a simulation to count the number of packet transmissions for accomplishing context aware computing is carried out to inspect the effects on the average packet transmission. Fig. 1 shows the expected packet transmission by packet loss p and service interval μ. When the packet loss is small, the difference is small. However, as the packet loss gets bigger, it suffers more increasing packet transmission. When the packet loss is large, the performance can be managed by controlling the caching ratio q and adjusting the network structure. Several context ontologies reflecting various types of situation are under development, and the prototype system described in this paper is operated with inference based on ontology integration. Fig. 2 shows a portion of the ontology developed in TopBraid[6]. In the prototype system, surveillance environments are identified for context aware computing into knowledge bases. Final implementation of the proposed ontology integration model will be merged into wide area surveillance system named CUSST(Center for U-city Security and Surveillance Technology) [7].

Conclusion

In this paper, the distributed ontology integration model for cooperative inference in context aware computing is proposed. Data source agents exchange information with each other freely within access control in accordance to ONVIF standard. Agents perform their own integrated inference based on their own ontology knowledge base and others. The flexible cache scheme and scalable agent structure which is adaptive to the actual device demands and that of its neighbors help cooperative inference. Context inference including distributed multimedia data and biomedical feature data is widely used in surveillance environment including health surveillance [START_REF] Shaban-Nejad | An Enhanced Graph-Oriented Approach for Change Management in Distributed Biomedical Ontologies and Linked Data[END_REF]. In [START_REF] Shaban-Nejad | An Enhanced Graph-Oriented Approach for Change Management in Distributed Biomedical Ontologies and Linked Data[END_REF], biomedical ontologies are integrated in a graph approach. It can be combined with our ontology integration model.

The simulation and implementation are conducted to show the effectiveness of the proposed model. The expected packet transmission is inspected and the trend is analyzed. Realistic data is collected also to make the prototype system merge into wide area surveillance framework.

Fig. 1 .

 1 Fig. 1. A comparison of the expected packet transmissions

Fig. 2 .

 2 Fig. 2. An ontology description view

Acknowledgements

This work was supported by the GRRC program of Gyeonggi province. [GRRCSUWON2014-B1, Center for U-city Security and Surveillance Technology]


Chau-Yi Chou
email: cychou@nchc.narl.org.tw

Jiunn-Horng Lee

Yu-Fen Cheng

Chih-Wei Hsieh

Weichung Wang

Different Solvers Evaluation for a Bucking Problem

The linear system solver plays a key role in scientific computing. This paper evaluates the performances of PETSc (Portable, Extensible Toolkit for Scientific Computation) and HIPS (Portable, Extensible Toolkit for Scientific Computation) solving a singular matrix arising from a bucking problem from UF matrix collection. We employ preconditioned (Level-based ILU) iterative methods (GMRES) for PETSc while HIPS adopts the Schur complement method, named iterative or hybrid mode. Moreover, HIPS proposed HID (Hierarchical interface decomposition) to improve the parallel efficiency. We hope to transfer these results into industrial applications.

Results

These results were performed on ALPS in National Center for High-performance Computing (NCHC). The hardware of computing nodes on NCHC ALPS consists of 600 of Acer AR585 and are connected together with Qlogic InfiniBand in 4x QDR (40Gb). Each node contains 48 cores sharing 128 GB RAM in 4-memory-controller non-uniform memory access architecture.

The singular matrix was proposed by Arthur Raefsky for a buckling problem for container models in 1993. The id number in UF matrix collection [START_REF] Davis | The university of Florida sparse matrix collection[END_REF] is 817. Table 1 presents the matrix characteristic. From Table 1, we know that this matrix is a singular matrix because of her dimension unequal to her rank. The stopping criteria were used the scaled residual < 1E-7 [START_REF] Gould | A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations[END_REF]. This study first evaluated the performance of different k levels of ILU(k) preconditioned GMRES iterative method via PETSc. Table 2 depicted the results (the number of iterations, elapsed time in second, scaled residual, peak fill-in ratio) of different levels via PETSc. The "peak fill-in ratio" denoted the ratio of the memory to the original one in order to show the memory increment. It had to pay the penalties of the elapsed time and the memory for increasing levels. Because that the infinity norm [START_REF] Golub | Matrix computations. 3rd edn[END_REF] of the computed solutions between 7 and 100 levels was near 7.55E-7, we adopted 7 levels for PETSc hereafter. HIPS used the Schur complement method, HID, threshold ILUT preconditioned GMRES iterative method, named iterative or hybrid mode [START_REF] Gaidamour | A parallel direct/iterative solver based on a Schur complement approach[END_REF] to solve the linear system. Iterative mode used the ILUT preconditioned GMRES iterative method; however, hybrid mode first divided the linear system into the interior system and the Schur complement. Then, the direct method dealt with the interior system while the ILUT preconditioned GMRES iterative method dealt with the Schur complement. Therefore, the hybrid mode used both the direct and iterative methods to solve this linear system.

Take 100 Krylov subspaces and let the maximal number of iterations be 100. Use the scaled residual to check the accuracy of the computed solutions. Fig. 1 shows the breakdown of the iterative mode compared with PETSc_seq. HIPS outperforms because of HID. Fig. 2 illustrates the breakdown of the hybrid mode. From Fig. 1 and Fig. 2, the hybrid mode lightly outperforms iterative mode when MPI jobs are less than 16; however, the iterative mode shows lightly faster than the hybrid mode on 16 MPI jobs.

Fig. 1. Breakdown of PETSc and HIPS (iterative mode)

Fig. 3 shows the speedup of the iterative and hybrid modes via HIPS. Both modes via HIPS have near speedup because of problem size limit. Fig. 4 shows the number of iterations via HIPS. Parallel affects the accuracy in the iterative mode; however, the hybrid mode doesn't.

No. of MPI Jobs

Solver

Precond.

Symbolic factorization HID

tuning via PETSc to suggest the best solution among these packages. Moreover, we will systematically analyze the linear solver performances for an application field, for example, solid and structural mechanics.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Breakdown of HIPS hybrid mode

Fig. 4 .

 4 Fig. 4. The number of iterations via HIPS

Table 1 .

 1 Matrix Characteristic

	Name	N	NNZ	Condition Number	rank
	raefsky4	19779	1316789	3.13E13	19771

Table 2 .

 2 Results of ILU(k) preconditioned GMRES iterative method via PETSc

	ILU(k)	No. iter.	Elapsed time (Sec.)	Scaled residual	Peak fill-in ratio
	7	37	2.75E1	8.30E-6	11.70
	10	24	4.88E1	3.63E-6	15.89
	100	2	1.80E2	4.38E-6	25.19

Acknowledgments. We are grateful to the National Center for High-Performance Computing for computer time and facilities.


Kuo-Qin Yan

Yung-Hsiang Su

Hsin-Met Chuan

Shu-Ching Wang

Bowei Chen

Quality of Service Enhancement by Using an Integer Bloom Filter Based Data Deduplication Mechanism in the Cloud Storage Environment

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

Quality of Service Enhancement by Using an Integer Bloom Filter based Data Deduplication Mechanism in the Cloud Storage Environment

Kuo-Qin Yan 1 , Yung-Hsiang Su 1 , Hsin-Met Chuan 2 , Shu-Ching Wang 1* , Bo-Wei Chen

Result

As network bandwidth and quality outstrip computer performance, various communication and computing technologies previously regarded as being of different domains can now be integrated, such as telecommunication, multimedia, information technology, and construction simulation. Thus, applications associated with network integration have gradually attracted considerable attention. Similarly, cloud computing facilitated through distributed applications over networks has also gained increased recognition. In a cloud-computing environment, users have access to faster operational capability on the Internet [START_REF] Aymerich | An approach to a cloud computing network[END_REF], and the computer systems must have high stability to keep pace with this level of activity.

In the data deduplication strategy, the block-level strategy is used. The blocklevel strategy has higher reduction ration than file-level but must consume more computing resource that is not suitable in cloud computing [START_REF] Tsuchiya | DBLK: Deduplication for Primary Block Storage[END_REF]. In this study, an integer Bloom Filter [START_REF] Wang | HDDS: Hybrid data DeDuplication Strategy over Cloud Storage[END_REF] based Lightweight Deduplication Mechanism (LDM) under cloud storage is presented to solve this problem. In the proposed LDM system architecture, several storage nodes are grouped into a cluster, each cluster has a storage node acts cluster are called Namenode, the other storage node are called Datanode. Namenode is responsible for perform LDM and placement data to Datanode, Namenode also provides the storage capacity. Each Namenode has two components, LDM and Metadata Table . The LDM is used to perform deduplication strategy, and Metadata Table is responsible for the metadata of stored data. The proposed system architecture is shown as Fig. 1. The main job of Transfer Agent System (TAS) is used to upload data when the requests of user are received. The data is partitioned into n chunks and translated into unique identifier by SHA-1. Then, the unique identifier of data chunks is delivered to cluster by TAS for comparison data.

Fig. 1 The LDM System Architecture In the proposed system architecture, each cluster executes LDM. The steps are described in below:

1. Set the number of hash function (k). For example, Cloud Service Provider (CSP) chooses seven hash functions. 2. Calculate the quantity of data that each cluster can store (n max ). For example, if the capacity of cluster is 40 GB and data chunk capacity is 64 MB, then this cluster can store 640 data (40 GB/64 MB). (2) Through formula (2), the probability of "Positive False" is 0.0078 that means the average 1000 times query will occur 8 times "Positive False". 5. CSP chooses an accept probability of "Positive False", and then the initialization of Bloom Filter is completed. If CSP cannot accept an accept probability of "Positive False", then return to Step 1. In addition, a bigger k is chosen that can get smaller probability of "Positive False".

Calculate the length of Bloom

A linked structure is used by LDM to store the metadata. When a data is added, to calculate the unique identifier by k hash functions and mapping to Bloom Filter firstly, then the hash value is computed to decide the starting position of link. The calculator formula is shown in [START_REF] Tsuchiya | DBLK: Deduplication for Primary Block Storage[END_REF], where val(h i ) is the i th hash value, m is Bloom Filter length, % symbol is mod function.

Link(position) = ( (h i )) % m

(3) By formula (3), a position in Bloom Filter can be obtained, and then link to the metadata of data chunk. For example, if there are 4 hash functions, val(h 1 ) = 6069, val(h 2 ) = 36, val(h 3 ) = 5, val(h 4 ) = 642, and m =6463, by using formula (3), the link start position is 289 [(6069+36+5+642) % 6463 = 289], therefore, this data will be linked to intBF index number 289. When the same result is gotten by different data through formula (3), then a links is generated by the last linked list. The progression of LDM is shown as Fig. 2.

Fig. 2 The progression of LDM

In the data deduplication, the process of comparison is same as the process of data added. In the comparison process, the unique identifier is calculated by k hash functions firstly. Then, LDM judges the status of data existence by using intBF. If this data is not exist, do not perform the compare process, else if intBF judge this data is existence, to find the link position through formula (3), and search all link nodes to find the same data. However, the average comparison times in data duplication of our proposed LDM is compared with iBF (indexed Bloom Filter) proposed by Antichi et al. [START_REF] Antichi | Achieving Perfect Hashing through an Improved Construction of Bloom Filters[END_REF]. The capacity of storage node was generated by NS2, include current consume capacity and maximum capacity. The unique identifier was generated by md5database [5], md5-database can transform data in to a unique identifier by MD5, SHA1, SHA256, and SHA512. However, SHA-1 was used in this experimental. There are 250 original data, include 150 movie data (2441 data chunk after partition), and 100 backup data (2518 data chunk after partition). Original data are partitioned by 64 MB, and there are 4959 data chunks totally. C++ is used to write the proposed mechanism. Finally, MS Excel 2010 is used to record experimental result. In addition, when a new data is uploaded, the unique identifier of data will be compared with storage system. In this experiment, data deduplication is performed in storage system which stored different number of data (25%, 50%, 75%, 100% of total data).

In this experiment, there are 20 data be uploaded in four kinds of situation and perform the data deduplication comparison processes. Fig. 3 is the results of average comparison times. X-axis is the different number of data; Y-axis is the average comparison times. According to the results shown in Fig. 3, whether in more or less number of data, the comparison times in LDM were keep in a constant time nearly. From the experiment results, LDM can use less computing resource to complete data deduplication process that is more suitable in cloud storage. In this study, LDM through rapid judge the status of data existence and compare the same data position can reduce the computing resource of data deduplication compare process, and then LDM more suitable in cloud computing.

  Filter (m) by using: k=(m/n)ln 2=m/n*0.69314 (1) Through formula (1), Bloom Filter length (m) is 6463. 4. Calculate the probability of "Positive False" by using: f'=(1-(1/m) kn ) k

Fig. 3 .

 3 Fig. 3. The average comparison times in Data Duplication

  1 1 Chaoyang University of Technology, Taiwan, R.O.C. {kqyan, s10033905, scwang * , s10114603}@cyut.edu.tw

2

Hsing-Kuo University, Taiwan, R.O.C. hn88780752@yahoo.com.tw * : Corresponding author Abstract. Network bandwidth and hardware technology are developing rapidly, resulting in the vigorous development of the Internet. A concept, cloud computing, uses low-power hosts to achieve high quality service. According to the characteristics of cloud computing, the cloud service providers can support the service applications on the Internet. There are a lot of applications and data centers in the cloud-computing environment, then the loading of storage node is heavier than before. However, data deduplication techniques can greatly reduce the amount of data. Therefore, an integer Bloom Filter based Lightweight Deduplication Mechanism (LDM) under cloud storage is proposed. The proposed LDM can reduce the extra cost that traditional data deduplication technique needed.

Acknowledgments

. This work was supported in part by the Ministry of Science and Technology MOST 102-2221-E-324-008 and MOST 103-2221-E-324-025.


Minhwan Ok
email: mhok@krri.re.kr

Fault-Tolerant Storage Servers for the Databases of Redundant Web Servers in a Computing Grid

Keywords: Scalable Web service, computing Grid, Fault-tolerant, Storage virtualization

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1

Constructing the Computing Grid

In the system model, the applications are provided to the users by Web service. A client computer connects to the Web server of the coordinator. Coordination Service is composed of user interfaces to log-on the computing Grid and to input parameters with user input/output data transfer. DB Organizer is the manager of information including parameters input, software title selected, and details concerned with user ID. It also selects appropriate computing site for the user. DB Connector is a client of DB Organizer and read/write information/report from/to the management database. Applications are launched, controlled and landed through Application Manager, which would be a kind of RFB Service. In Fig. 1, Application Manager delivers the commands included in the order, which is received via DB Connector, to the Application. When transferring the output data, Application Server should be re-authenticated for the security of user data. On writing information to the management DB of the originator coordinator, the originator writes the same information to the management DBs of the other coordinator, if one or more coordinator does not respond to the writing, the coordinator is presumed crashed-down. This is broadcast to the remained coordinators. On reading information from the management DB of the originator coordinator, the originator initiates reading from the management DB of the next coordinator, after reading the information from the its own management DB. The reading is relayed returning to the originator, thus it is named Circulated Read Request. If one or more coordinator does not respond to this reading, the coordinator is presumed crashed-down and this is also broadcast to the remained coordinators. Fig. 2 illustrates the circulated read request/response, the broadcast write is illustrated in Fig. 3. In both information writing and information circulated reading, the originator creates Replay Roll if it detects any crashed-down coordinator. Replay roll is the list of DB transactions from the point the crash-down is detected to the point the crashed-down coordinator broadcasts its restart. Then the coordinator updates its management DB following the replay roll the originator has sent. Keeping up the recorded information identical is the major issue in this follow-up scenario.

Multiple Storage Servers

Ancillary to the selected one among local computing sites the software installed, one of storage servers is designated for sizable storage space to process large quantities of data with the storage farm. The storage space for application running is confined within the application server in the previous work [START_REF] Ok | A Consolidation Model of Web Application Servers toward a Simplified Computing Grid[END_REF]. It is also confined in the application server in this work, except that the whole data is partitioned and the partitions are replaced to be processed in the application server in the manner similar to the virtual memory. The application has restarted in the case of the storage server failure in the previous work, however the application rolls back to the previous phase of the current partition in this work. For active/standby failover, the allocation Since multiple storage servers govern the storage farm, the write to a storage device is allowed while the storage manager has the token of the device that the token is traversing storage servers otherwise. Once the storage manager wrote to a storage device, it broadcasts allocation information of the written file to other storage managers so that storage managers sharing the storage space would update their allocation tables. The storage devices could constitute one single storage space spanned from one device to another, for availability losing an advantage of parallelized access of striping. When one storage device fails, it is broadcast among the storage managers by a storage manager detected the fault. The storage space of the device is marked 'missing' at all the storage managers, analogous to bad blocks, and access to files located at the space is restricted from then. A storage manager should have the token of a device when it has to write to the device and it waits for the token. The investigation protocol is described in Fig. 5 for the case the token of a device is not returned before the failure of a storage manager.

• The storage manager waited for a predefined duration broadcasts the request for the last use time of that token. • If all the other managers responds the storage manager wait for another predefined duration. After the duration the storage manager queries the manager of the latest use whether the writing is done.

• On reply of 'In-Use' the storage manager waits for another predefined duration, and Repeat the querying/waiting. Otherwise, the storage manager creates other token and sends 'Alternative Token' to the manager it queried. • If the manager it queried does not reply with 'Token Destroy', the storage server broadcasts the failure of the respective storage server.

Fig. 5. Investigation into the storage manager which is queried whether its writing is done.

Fig. 1 .

 1 Fig. 1. System architecture of the computing Grid

Fig. 2 .Fig. 3 .

 23 Fig. 2.Information reading from either management DB is relayed, which will be circulated to the originator and the originator responds with the information last.

Fig. 4 .

 4 Fig. 4. Computing Grid Organization and storage management on partitioned data

  table is mirrored to the other storage server. A couple of storage servers are assigned to backups of each other, and the storage manager has dual modes between active/standby in normal status and active/active in abnormal status, of the other server. Coupling two storage servers is static and conducted by the administrator.

	Application Server	Application Server	Application Server		Application Server	Application Server	Application Server
					Coordinator
		Gateway					Gateway
	Storage Server	Storage Server	Coordinator	Storage Server	Storage Server	Storage Server
		Storage Farm				Storage Farm
			Application Server
			Storage Server


Show-Shiow Tzeng
email: sstzeng@nknucc.nknu.edu.tw

Ying-Jen Lin

Sequential Sensing and Transmission for Real-Time Traffic in Cognitive Networks

Keywords: sequential sensing, real-time traffic, frame loss ratio, multiband, cognitive networks

This paper proposes a sequential sensing and transmission algorithm for real-time data in time-slotted multi-band cognitive networks. The proposed algorithm includes the backlog in a queue and the delay constraint of real-time data to select an appropriate band to send data such that more real-time data can be transmitted before being dropped. Simulation results show that the proposed algorithm reduces frames loss ratio and increases effective real-time throughput.

Introduction

Cognitive networks have been introduced to utilize the temporarily idle bands in licensed networks [START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF]. To access an idle spectrum band, the first step of a mobile user in cognitive networks (i.e. cognitive user) is to sense the band and determine whether the band is idle or busy. In a multi-band networks, a cognitive user can use sequential sensing to sense bands one by one. Once one idle band is found, the cognitive user can send out data on the band; otherwise, the user senses the next band. Sequential sensing allows cognitive users to sense two or more bands, which then leads to that cognitive users send out data more quickly in a cost-effective manner [START_REF] Shu | Throughput-efficient sequential channel sensing and probing in cognitive radio networks under sensing errors[END_REF][START_REF] Tzeng | Cross-layer sequential sensing with effective throughput maximization in time-slotted cognitive networks[END_REF].

Previous sequential sensing algorithms implicitly assume that (i) frames are always available from an upper layer at any time and (ii) frames can tolerate long delay. Frames arriving from an upper layer are usually placed into a queue and then be transmitted latter. Due to the first assumption, the number of the frames in a queue is infinite and previous sequential sensing stops to send frames on the band which maximum throughput is the greatest among the sensing bands. However, the number of the frames in a queue is finite and is possibly variable. It is meaningless that a band which can transmit all the frames in a queue is found but we abandon the band and sense the next band due to the reason that the next band may have higher throughput. Therefore, we suggest that sequential sensing may stop on the band which can send out all the frames if the band is found, instead of the band which maximum throughput is the greatest; from this viewpoint, the frames can be sent more quickly. Under the second assumption, previous sequential sensing does not consider that real-time frames have the requirement of delay constraint; that is, frames are dropped when the frames suffer a specified delay time. Although sensing more bands may have more opportunity to find a throughput-maximum band, more frames may be also dropped. This paper designs a sequential sensing procedure for real-time traffic in a realistic network environment removing the two assumptions.

The proposed sensing and transmission algorithm

The radio environment herein is a licensed network in which radio spectrum is divided into spectrum bands and each band is further divided into time slots. M possible transmission rates are assumed to be available on a band; each rate is denoted by r m , 1 ≤ m ≤ M . The frames, consisting of header and payload, are real-time traffic with the constraint of delay time. The time that a frame stays in a queue is queuing time. The time that a frame is sent out is transmission time. For a frame, if the sum of queuing time and transmission time is greater than the delay requirement, the frame is dropped. Given a set of bands, the amount of real-time data successfully sent in a slot on the bands excludes sensing overhead, header overhead, and the failed data due to miss-detection and dropping. Then, the estimated real-time throughput (ERT) is defined as the ratio of the average amount of real-time data successfully sent in a slot on the bands to a slot time. In the following, we introduce the notation used in the equations to calculate the ERT, and then the equations are presented. The header length and payload length of a frame are denoted by L h and L d respectively. Let T c , T s , T l , and T p respectively denote the time of changing bands, sensing time, slot time, and the probing time of a band. Let T j q denote the queuing time of the q-th frame in a queue at the beginning of slot j. The probability that a slot is busy (or idle) is denoted by P busy (or P idle ). The probability that a user correctly detects a busy slot is denoted by P d . The probability that a user incorrectly identifies an idle slot as a busy slot is denoted by P f . Let E j i,k denote the ERT of slot j on bands {b i , b i+1 , ..., b N }, where 1 ≤ i ≤ N and k, 0 ≤ k ≤ i -1, is the number of probing operations performed before band b i . Let e j i,k (x) represent the ERT of slot j on band b i , where x is the transmission rate of band b i and k is the number of probing operations performed before band b i . We in turn derive e j i,k (x) and E j i,k as follows. When a cognitive user attempts to send frames in a queue in slot j on band b i , the user experiences i sensing times, (i -1) times of changing bands, and at least one probing time. Since the user may have probed k bands before band b i , the q-th frame can be sent at a rate x if (i) the frame is sent completely before the end of slot j, i.e. iT s + (i -1)T c + (k + 1)T p + q(L d + L h )/x < T l and (ii) the delay constraint D of the frame is satisfied, i.e. T j q + iT s + (i -1)T c + (k + 1)T p +q(L d +L h )/x < D, which can be expressed by an indicator function δ j q (x). The value of δ j q (x) is 1 if the frame is sent successfully; otherwise, the value is 0. The maximum number of frames which can be sent at a rate x in the remaining time of slot j is q∈Q δ j i,k,q (x), where Q is the set of frames in a queue at the beginning of slot j. Then, the ERT, e j i,k (x), is calculated as follows:

e j i,k (x) = 1 T l q∈Q δ j i,k,q (x)L d . ( 1
)
When a user is in slot j on band b i , the ERT of bands {b i , b i+1 , ..., b N }, E j i,k , is discussed into three cases: (i) the sensing result of idle band b i is idle, which probability is P idle (1 -P f ), (ii) the sensing result of busy band b i is idle, which probability is P busy (1 -P d ), and (iii) the sensing result of idle or busy band b i is busy, which probability is P busy P d +P idle P f . In the first case, if the ERT, e j i,k (x), of band b i is greater than or equal to the ERT of bands {b i+1 , b i+2 , ..., b N }, the user determines to send frames on band b i ; i.e., E j i,k is e j i,k (x). Otherwise, the user continues to sense the next band b i+1 ; i.e., E j i,k is E j i+1,k+1 . Let δ j i,k (x) be an indicator function which value is 1 if the user sends frames in slot j on band b i , i.e. e j i,k (x) ≥ E j i+1,k+1 , and which value is 0 if the user continues to sense. Let δj i,k (x) denote the complementary of the δ j i,k (x). The ERT of bands {b i , b i+1 , ..., b N } in the first case is

M m=1 P rm [δ j i,k (r m )e j i,k (r m ) + δj i,k (r m )E j i+1,k+1 ], (2)
where P rm denotes the probability that the transmission rate of band b i is r m , m = 1, 2, ..., M . In the second case, when a user probes the rate of band b i , the user receives no response due to busy band b i . The user continues to sense the next band b i+1 ; then, the ERT, E i,k , is E j i+1,k+1 . In the third case, the user continues sensing from the next band b i+1 ; then, the ERT, E j i,k , is E j i+1,k . The ERT of bands {b i , b i+1 , ..., b N } is summarized in recursive Eq. (3) which can be solved by backward induction.

E j i,k =              P idle (1 -P f ) M m=1 P rm [δ j i,k (r m )e j i,k (r m )+ δj i,k (r m )E j i+1,k+1 ] + P busy (1 -P d )E j i+1,k+1 + (P busy P d + P idle P f )E j i+1,k 1 ≤ i ≤ N -1, P idle (1 -P f ) M m=1 P rm e j i,k (r m ) i = N . (3)
Fig. 1 shows the ERT and frame loss ratio (the ratio of the number of loss frames to the total number of frames) of the proposed algorithm and the two other algorithms; one is the algorithm in [START_REF] Tzeng | Cross-layer sequential sensing with effective throughput maximization in time-slotted cognitive networks[END_REF], which produces maximal effective throughput (MET) without considering delay constraint and the backlog in a queue, and the other is the algorithm, called first-fit herein, which merely sends frames on a band which is first found on a slot and its bandwidth is sufficient to send all the frames in a queue. The unit of the ERT in Fig. 1 is the percentage of the load which can be successfully transmitted. From the figure, we observe that the proposed algorithm reduces frame loss ratio and increases effective real-time throughput because the proposed algorithm includes the backlog and the delay constraint to select an appropriate band to send frames as soon as possible.

  In the proposed algorithm, a cognitive user starts to sense a time slot on band b i , i = 1. If sensing result is busy, the user checks whether band b i+1 exists. If band b i+1 exists, the user senses the same slot on the next band b i+1 ; otherwise, the user waits the beginning of the next slot and then repeats the proposed algorithm. If sensing result is idle, the user calculates (i) the ERT of band b i and (ii) the ERT of the bands {b i+1 , b i+2 , ..., b N }; then the user compares the values of the both ERTs. If the ERT of the bands {b i+1 , b i+2 , ..., b N } is higher, the user continues to sense the next band b i+1 ; otherwise, the user sends frames in the residual time of the slot on band b i .

Fig. 1 .

 1 Fig. 1. Frame loss ratio and ERT

Acknowledgement

This research was partially supported by the National Science Council, Taiwan, under grants NSC 101-2221-E-017-011-and NSC 102-2221-E-017-006-.