Dezhong Yao
email: dyao@hust.edu.cn

Chen Yu
email: yuchen@hust.edu.cn

Hai Jin
email: hjin@hust.edu.cn

Jiehan Zhou

Energy Efficient Task Scheduling in Mobile Cloud Computing

Keywords: Mobile cloud computing, Energy-efficient, Task scheduling, Offloading

Cloud computing can enhance the computing capability of mobile systems by offloading. However, the communication between the mobile device and the cloud is not free. Transmitting large data to cloud consumes much more energy than processing data in mobile device, especially in a low bandwidth condition. Further, some processing tasks can avoid transmitting large data between mobile device and server. Those processing tasks (encoding, rendering) are as the compress algorithm, which can reduce the size of raw data before it is sent to server. In this paper, we present an energy efficient task scheduling strategy (EETS) to determine what kind of task with certain amount of data should be chosen to be offloaded under different environment. We have evaluated the scheduler by using an Android smartphone. The results show that our strategy can achieve 99% of accuracy to choose the right action in order to minimize the system energy usage.

Introduction

With a rapid development of embedded systems, high speed wireless networks and could computing, mobile devices (e.g., smartphone, tablets, wearable devices, etc.) are increasingly becoming a common stuff of human daily life. We use mobile devices to do many of our jobs that we used to do on desktop. Mobile cloud computing technique allows those ideas to become a reality. Nonetheless, the more mobile devices we have, the less happiness we are with the battery lifetime. This is because we are still using the traditional power supplying method and materials.

Computing offloading technique is proposed with the objective to migrate the complex computation works from resource-limited devices to powerful machines. This avoids taking a long application execution time on mobile devices which results in large amount of power consumption. However, current offloading studies do not consider about the energy consumption used by data transport. Offloading mechanisms just focus on avoiding use local CPU resource in order to save energy spent on processing. They pay limit attention on long time data transmission problem and they consider best case scenarios: ideal high speed networks. Unfortunately, long wireless network latencies are a fundamental obstacle [START_REF] Satyanarayanan | The case for vm-based cloudlets in mobile computing[END_REF]. Some researches [START_REF] Dinh | A survey of mobile cloud computing: architecture, applications, and approaches[END_REF][START_REF] Baliga | Green cloud computing: Balancing energy in processing, storage, and transport[END_REF] prove that it can significantly save energy when we minimize the use of network. For example, speech recognition utility is a heavy processing task, it should be processed in cloud servers according the offloading scheduling algorithm [START_REF] Barbera | To offload or not to offload? the bandwidth and energy costs of mobile cloud computing[END_REF]. While voice data is usually larger than text data, it will take more energy to send the big data to server than to process the recognition algorithm locally and then send the text result to server.

In this paper, we propose an energy efficient task scheduling strategy (EETS) which focuses on reducing the amount of data transmission. Our goal is to identify which kind of task is suitable for offloading and which is not. To address this problem we build an energy consumption model for each task. At last, we give an evaluation work on a suite of Mediabench [START_REF] Lee | Mediabench: a tool for evaluating and synthesizing multimedia and communicatons systems[END_REF] programs to show the efficiency of our scheduling mechanism. Our main contributions of this paper are as: 1)We present a task allocation algorithm which is based on a task's input/output data's size and storage path. 2)We study the data compression that is helpful to achieve energy saving between mobile device and cloud. 3)We give an energy consumption model for each task. Using this model, we can calculate the energy consuming difference between offloading or not offloading. We prove our model using real data from Android phones.

The rest of the paper is organized as follows. Section 2 presents the related work. Section 3 introduces task execution scenario. In section 4, we describe energy consumption modeling technique for application task and explain task scheduling algorithm. Then we carry out a performance evaluation of all considered methods in section 5. Section 6 discusses our work and future works, whereas our conclusions are drawn in section 7.

Related Work

Could computing can provide computing resource, and users can use these to reduce the amounts of computation on mobile systems and save energy. Thus, cloud computing can save energy for mobile users through computation offloading [START_REF] Yang | On effective offloading services for resourceconstrained mobile devices running heavier mobile internet applications[END_REF][START_REF] Kumar | Cloud computing for mobile users: Can offloading computation save energy?[END_REF]. However, to migrate large amount of data in a low-bandwidth network will cost much more energy than local computation.

Offloading [START_REF] Yang | On effective offloading services for resourceconstrained mobile devices running heavier mobile internet applications[END_REF] is a method to offload part of the computation from mobile device to another resource rich platform. A number of recent works propose different methodologies to offload computation for specific applications [START_REF] Portokalidis | Paranoid android: versatile protection for smartphones[END_REF][START_REF] Chen | Virtual smartphone over ip[END_REF]. In another part, lots of works discuss on how to pre-estimate the actual gain in terms of energy [START_REF] Wen | Energy-optimal mobile application execution: Taming resource-poor mobile devices with cloud clones[END_REF]. For a code complication, offloading might consume more energy than that of local processing when the size of codes is small [START_REF] Rudenko | Saving portable computer battery power through remote process execution[END_REF].

The research work [START_REF] Kumar | Cloud computing for mobile users: Can offloading computation save energy?[END_REF] suggests a program partitioning based on the estimation of the energy consumption (communication energy and computation energy) before the program execution. The optimal program partitioning for offloading is calculated based on the trade-off between the communication and computation costs. To do offloading in the dynamic environments, Tang et al. [START_REF] Tang | A dynamic mechanism for handling mobile computing environmental changes[END_REF] consider three common environmental changes: power level, connection status and bandwidth. But they just explain the suitable solutions for offloading for different environments separately. Chun et al. [START_REF] Chun | Dynamically partitioning applications between weak devices and clouds[END_REF] present a system to partition an application in dynamic environments. The proposed system follows three steps with different requirements related to the application structuring, the partitioning choice, and the security. Cuervo [START_REF] Cuervo | Maui: making smartphones last longer with code offload[END_REF] introduces an architecture to dynamically partition an application at a runtime in three steps. However, all those works do not consider more about the task input and output data, which may cost a lot of energy in communication. None of the previous works related to mobile cloud computing explicitly studies the actual input data and output data location problem. They assume that the data comes from local and to be stored in local device. Otherwise, we need to spend much energy on useless data transmission work.

Task Execution Scenario

Simple task does not take too much time to execute, so it does not need offloading [START_REF] Kumar | Cloud computing for mobile users: Can offloading computation save energy?[END_REF]. Complex applications will consume more energy than the simple one. So in this section we will classify the applications with complex computation task.

With the offloading's help, we can put the rendering work on cloud, as shown in Fig. 1(a). After the rendering result is ready, the data will be sent back to mobile device. The energy spent on computation part will be saved with an extra cost of data communication. Sometimes, it is not worth to offload rendering work from mobile client to server when the data size is big and the network bandwidth is slow. The mobile device will keep communication with cloud servers for a long time. For some compression like applications, we would better to do compress work on mobile device than to do it on the cloud servers. The data size can be reduced after it is processed. So the communication time will be saved. This progress is shown in Fig. 1(b).

Energy Efficient Task Scheduler

In this section, we will talk about the energy consumption model. Our proposed task scheduler makes following assumptions: 1) Each task can be processed on mobile device. 2) Each task has a fixed compress ratio of input data and output data.

3) The network bandwidth between mobile device and remote cloud is fixed and stable. 4) The computational power required by a task has a liner relationship with the processing time.

Energy Model

Energy consumption of mobile devices depends on the computation and communication loads. To explore the energy consumption of each task, we suppose the task computation requires I instructions. The task needs to deal with D bytes of data and will generate D ′ bytes result. We use B to stand for current network bandwidth. It will task D/B seconds to transmit and receive data. We define our task as follows:

Definition 1. [Application Task] T (I, D, D ′ ).
A mobile application task T has I instructions to be executed. The task uses D bytes input data and generates D ′ bytes output data.

The mobile system consumes P c (watt per instruction) for computing and P tr (watt per second) for sending and receiving data.

If we choose to execute our task using offloading, we need to send our code and data to server, as shown in Fig. 1(b). So the total energy consumption is:

E of f = P tr * D B ( 1
)
Suppose the output data D ′ is k times smaller than the original data D, we use compress ratio k to describe the relationship between input data and output data: (D ′ = D * k). In order to simplify the compression algorithm impact on the size of output data when the size of input data is different, we just consider the application task with fixed compression ratio. If the mobile device performs the task, the energy consumption is:

E nonof f = P c * I + P tr D ′ B ( 2
)

Definition 2. [Energy saving value S]

The amount of energy that can be saved, when the task chooses to do offloading.

The amount of energy saved is:

S = E of f -E nonof f (3) = P tr * D B -P c * I -P tr * D ′ B = P tr * D B -P c * I -P tr * D * k B = P tr * (1 -k) D B -P c * I (4)
If offloading use less energy to finish a task than non-offloading, this formula produces a negative result: S < 0. It's better to choose offloading. When we try to transmit large amount of data D for a compression task (k < 1), Eq. ( 3) will be positive. It means that it is better to execute the task locally.

Execution Model

It is a big advantage to do offloading in cloud environment, if a task has to download a large number of data from remote servers. In the previous studies, researchers focus on determining whether to offload computation by predicting the relationships among the three factors: network bandwidth B, the amount of processing instructions I and the amount of data to be transmitted D. However, there is a fundamental assumption underling this analysis: the server does not already contain the input data and all the data must be sent to the server to do offloading. The mobile client has to offload the program code and data to the server. Now, cloud computing changes this assumption. Many mobile devices have cloud storage service. Offloading can use the data stored in the cloud. This will significantly reduce the energy consumption on data transmission. The execution workflow is shown in Fig. 2. The input file of an application could come from local files or remote storage service. The execution code is only on mobile device. Then, we can choose to offload computation task to virtual machine or run locally in mobile device. How to store the output result data of the application is depended by user settings.

Processing

Cloud Storage

Cloud VMs Mobile Client

Server Client

Fig. 2. Execution workflow of a mobile application

The detail of each possible workflow is listed in Fig. 3. The computing code is only stored in local mobile device. Compare with offloading and non-offloading mechanism, the main difference is processing code in cloud or in mobile device. There are 8 executing mode depending on where we get the input data and where we store the output data. In the next section, we will present a cost model for how much energy can be saved for the same input and same output situation.

The Cost Graph

In this section, we will consider the energy consumption cost for each situation shown in Fig. 3. We use the energy consumption model in section 4.1 to describe the power spent on computation part and data transmission part. Fig. 4 shows the cost map of data communication with different data storage. Task is executed on the mobile device while the other shown task runs on the cloud server after offloading. The input data of task could be D m in the local mobile device or D s from cloud storage service. As the instruction code is usually smaller than the data, the cost of transmitting code could be ignored. The cost of transmitting the input data is described as D i,j (i, j ∈ m, s). After the execution, the result data, D ′ j,l (j, l ∈ m, s), needs to be transported to the target place. As we process the same code in mobile device and VM, it will generate the same result. The size of data file should be the same.

Based on above discussion, we calculate the energy consumption for each suitable shown in Fig. 3 in mobile device, D ss = 0. For the output data, which does not need to be transported to another place, it will not consume the energy on mobile device. So we have D ′ mm = D ′ ss . As the result computed by the VM is the same data have computed in the mobile, the data exchange between mobile and server is equal:

D ′ ms = D ′ ms .
Table 1. The energy saved S for different storage place Following the energy saving computation model in Eq. ( 4), we calculate the amount of energy saving for the 8 situations described in Fig. 3. Table 1 presents the different energy saving results according to the place data stored. If the energy is saved, the formula should be negative. Table 1 shows that:

1. Input data comes from local and output data to be stored in local.

Offloading could take a great advantage in saving energy when computation work consumes more power than data communication. Otherwise, we should not choose offloading. 2. Input data comes from local and output data to be stored in cloud.

Offloading can save lots of energy when the task compression ratio is above 1. It means that when the output data is larger than the input one, we should choose offloading. When the compression ratio is below 1, it also depends on the amount of data to be transmitted, network bandwidth and the amount of processing time. when the compression ratio is below 1. When the task compression ratio is above 1, it is more valuable to do offloading when computation part uses more energy than data transmission. 4. Input data comes from cloud and output data to be stored in cloud.

In this situation, it should always choose to do offloading that can save large amount of energy.

Task Scheduling Strategy

In this section, we will present a cost graph based task scheduling algorithm for saving energy on mobile devices. The scheduling algorithm, as shown in Fig. 5, will decide whether the task should be processed locally or offloading. If the answer is true then the task is placed in the scheduling queue. Otherwise, the task will be executed locally. Part of the algorithm is presented as produce T ask Scheduler in Fig. 5, which uses cost-graph and task profile as input data.

The scheduling algorithm will be executed before each task. After check if current task is suitable for offloading, the scheduler will decide where to process the task.

Experiments Results

Our experiments are based on an Android-based platform device. In this section we describe the experiment setup, and performance evaluation results of all execution models as shown in Fig. 3. As processing time is also an important consideration for the use, there is a tradeoff between performance and energy consumption. In our paper, we only focus on energy issues on smartphone.

Experiments Setup

In the experiments, we assume that the WiFi network is always connected. In addition, we use dropbox [15] as our cloud data storage service. The software clones is running on virtual machines supplied by Amazon EC2 [START_REF][END_REF] platform. We use "Google Nexus One" as our test-device. Before each test program, the device will be continued charging for 2 hours after it is fully charged. The Android OS is restored to the factory settings to start a new test in order to make sure that there is only one test program installed. We use the percentage changes of the battery to show how much energy is used by the program.

Performance Evaluation

We implement our algorithm in Java and C using Android NDK. The task scheduler and data transmission parts use Java and the computation part uses C. To obtain a preliminary evaluation of the effectiveness of our method, we manually apply our algorithm to a suite of Mediabench [START_REF] Lee | Mediabench: a tool for evaluating and synthesizing multimedia and communicatons systems[END_REF] programs. Test Programs. We select 9 execution models: h264edc, h264dec, cjpeg, djpeg, rawcaudio, rawdaudio, ghostscript, mpeg2encode, and mpeg2decod. The processing time for the application is measured at mobile device. Our task scheduling algorithm will determine determine to do offloading according to current data file size, data path, compression ratio and bandwidth.

In our performance studies, we will compare our method with offloading and non-offloading as described in Eq. ( 1) and Eq. ( 2).

Test Measurement. By applying our algorithm to the 9 programs, we find that 6 of those 9 programs can get better energy saving by offloading. We evaluate our programs for four different groups which has different path of input data and output data. Then, we arrange each of our programs to do offloading and execute locally. After that, we use our proposed task scheduling algorithm to determine whether to do offloading. For each processing step, we record how much energy used before task finished. In Android mobile, we use how much percentage changes after the phone is fully charged. There is no other application running on the mobile device except system applications.

We use dropbox [15] as our cloud storage service, which has 100kbps network bandwidth. From Fig. 6(a), the offloading uses much more energy when the data is stored on mobile devices. The x-axis lists the test programs. The y-axis tells us how much percentage of energy used on test-phone to archive different programs. when they are running on mobile device. It is better to do offloading. When we use the cloud data, we would use offloading to save our energy, which is shown in Fig. 6(d). As we can see from those figures, the proposed method also uses the minimum energy consumption to achieve the work.

For the case: "input=mobile&output=mobile", the data does not need to be transmitted to the server, so our proposed strategy (EETS) performs like non-offloading case, as shown in Fig. 6(a). H264 and MPEG are complex video encoding/decoding algorithms, they always use the most energy on smartphone. Those algorithms need to encode/decode each frame in a video. So they will use more energy than the jpeg algorithms. When those methods run on remote server, the smartphone only spends energy on data communication. EETS chooses the right strategy to schedule the data. Fig. 6(b), Fig. 6(c) and Fig. 6(d) are the some situations.

Efficiency Analysis. Based on the experimental results, we can conclude how efficient of our algorithm. First, we will try to find which one costs the minimum energy consumption to execute the task. We use a minimum function to calculate the smaller value between offloading and non-offloading: min(percentage of offloading, percentage of nonoffloading). Then we compare the minimum value with the proposed task scheduling method. The accuracy of our proposed schemer is above 99% in average, which means our scheduling algorithm efficiently choose the best solution to allocate the tasks.

Discussion and Future Work

The proposed task scheduler is limited in some respects by it initially setups. It needs to collect the profile information of each task at the beginning. After learned the compression ratio and processing time, the scheduler can deal with new tasks. To solve this problem, we need to try some test programs to collect execution information or learn from system record after the task executed once.

The framework presented in this paper does not consider the power consumption on idle time waiting for task result and disk usage. While the task dose not execute for a long time, we think the power consumption is as same as the normal usage. The power consumption on disk usage is related to the type of storage device. HDD device uses much more energy than flash storage device. We plan to add this impact to our determine strategy in our future works.

Conclusion

In this paper, we present a novel energy aware dynamic task allocation strategy over mobile cloud computing environment. This scheme introduces a cost graph to determine offloading the work or not. The evaluation work shows that, our strategy can efficiently choose to offload or not on mobile device with 99% accuracy. The energy consumption on mobile device is controlled in minimum.

Fig. 1 .

 1 Fig. 1. Offloading scheme

Fig. 3 .

 3 Fig. 3. Execution mode for different input/output situation

Fig. 4 .

 4 Fig. 4. Graph based cost map of data communication for offloading and non-offloading

  m) Cloud(j = s) Local(i = m) Ptr * (1 + k) Dms B -Pc * I Ptr * (1 -k) Dms B -Pc * I Cloud(i = s) Ptr * (k -1) Dms B -Pc * I Ptr * (-1 -k) Dms B -Pc * I

Fig. 5 .

 5 Fig. 5. Cost graph based task scheduling algorithm

From Fig. 6 (Fig. 6 .

 66 Fig. 6. Energy consumption on benchmark

  3. Input data comes from cloud and output data to be stored in local. It is a little different with above situation. The offloading can save energy

	Procedure Task_Scheduler
	Input: (1) costgraph (2) task_profile
	Output: offloading decision for each task
	Procedure:
	I, D, k, input_path, output_path
	Procedure Scheduler(task_profile)
	...
	If the task can be processed
	if input_path is local
	if output_path is local
	use costgraph evaluate energy saved value S
	if S>0
	return False
	else
	return True
	else
	use costgraph evaluate energy saved value S
	if S>0
	return False
	else
	return True
	else
	...

Acknowledgements

The work is supported by NSFC (No.61003220).


Kai Zhang

Chen Shuming

Wei Liu

Ning Xi

A Fine-Grained Pipelined Implementation of LU Decomposition on SIMD Processors

The LU decomposition is a widely used method to solve the dense linear algebra in many scientific computation applications. In recent years, the single instruction multiple data (SIMD) technology has been a popular method to accelerate the LU decomposition. However, the pipeline parallelism and memory bandwidth utilization are low when the LU decomposition mapped onto SIMD processors. This paper proposes a fine-grained pipelined implementation of LU decomposition on SIMD processors. The fine-grained algorithm well utilizes data dependences of the native algorithm to explore the fine-grained parallelism among all the computation resources. By transforming the non-coalesced memory access to coalesced version, the proposed algorithm can achieve the high pipeline parallelism and the high efficient memory access. Experimental results show that the proposed technology can achieve a speedup of 1.04x to 1.82x over the native algorithm and can achieve about 89% of the peak performance on the SIMD processor.

Introduction

The solving of dense linear algebra with large scale is the key problem of many scientific computation applications. The famous LINPACK benchmark [START_REF] Dongarra | The LINPACK benchmark: past, present and future[END_REF] [2], which is used to test the performance of super computers, runs the computation of a set of linear equations. There are two methods for linear algebra systems, which are direct methods and iterative methods. Usually, the direct method is very suited to dense matrices [START_REF] Michailidis | Implementing parallel LU factorization with pipelining on a multicore using OpenMP[END_REF]. The typical direct method is solving the linear algebra with the help of LU decomposition, which makes efficient implementations, either purely in software or with hardware assistance, is therefore desirable.

Libraries for linear algebra [START_REF] Dongarra | Software libraries for linear algebra computations on high performance computers[END_REF] [5] with optimized subroutines have been highly tuned to run on a variety of platforms. The GPUs based system is a popular method. On the CPU/GPU hybrid architecture, the performance can be high up to 1000 GFLOPs for single precision as well as 500 GFLOPs (1 GFLOPS = 10 9 Floating Point Operations/second) for double precision. However, the memory hierarchy of GPUs is complex. Michael [START_REF] Anderson | A predictive model for solving small linear algebra problems in gpu registers[END_REF] tailored their implementation to the GPUs inverted memory hierarchy and multi-level parallelism hierarchy. They proposed a model that can accurately predict the performance of LU decomposition. Leandro [START_REF] Cupertino | LU Decomposition on GPUs: The Impact of Memory Access[END_REF] evaluated different types of memory access and their impact on the execution time of the algorithm. They showed that coalesced access to the memory leads to 15 times faster than the non-coalesced version. The task scheduling between CPUs and GPUs is also important. Optimized task scheduling can effectively reduce the computation [START_REF] Galoppo | LU-GPU: Efficient algorithms for solving dense linear systems on graphics hardware[END_REF][START_REF] Lifflander | Dynamic Scheduling for Work Agglomeration on Heterogeneous Clusters[END_REF][START_REF] Donfack | Hybrid static/dynamic scheduling for already optimized dense matrix factorization[END_REF][START_REF] Lifflander | Mapping dense lu factorization on multicore supercomputer nodes[END_REF][START_REF] Venetis | Mapping the LU decomposition on a many-core architecture: challenges and solutions[END_REF], which is corresponding to the idea on general purpose processors [START_REF] Grigori | Communication avoiding Gaussian elimination[END_REF]. Reconfigurable platforms always focus on designing high performance float-point computation units and the scalable architecture [START_REF] Jaiswal | Nitin Chandrachoodan: Fpga-based high-performance and scalable block lu decomposition architecture[END_REF][START_REF] Zhuo | High-performance and parameterized matrix factorization on FPGAs[END_REF][START_REF] Zhuo | High-performance designs for linear algebra operations on reconfigurable hardware[END_REF]. However, the high cost of reconfigurable hardware leads that they are not widely used.

The previous methods pay much attention on the optimization among system nodes. And the optimization on each unique node lacks of architecture transparence. The common idea of various platforms is that try to exploit sufficient parallel resources, which makes the single instruction multiple data (SIMD) technology been a popular method to accelerate the LU decomposition. This paper extends the work to optimize the LU decomposition on each node chip implemented with the modern SIMD architecture. When the LU decomposition is mapped onto SIMD processors, the native data dependences of the algorithm lead to the low pipeline parallelism and too much memory access. And the large amount of non-coalesced memory access existed in the algorithm results in much more memory access time.

To address these issues, a fine-grained pipelined implementation of LU decomposition is designed to increase the performance on SIMD processors. The proposed algorithm well utilizes data dependences to explore the fine-grained pipeline among all the computation resources. The pipeline parallelism is highly increased on the SIMD processor. The memory access operations are reduced by immediately reusing the temporary result. By using external loop unrolling method, the noncoalesced memory accesses are smartly transformed into coalesced version, which effectively reduces most of the memory access time.

The rest of the paper is organized as follows: in Section 2, we show a basic SIMD architecture which is taken as our optimization platform. Section 3 analyzes the basic LU decomposition on SIMD processors. In Section 4, we describe the proposed finegrained pipelined algorithm. The experimental results are presented in Section 5. Finally, Section 6 concludes the paper.

SIMD architecture

The SIMD technology can operate on multiple data in parallel by the control of a single instruction. Thanks to the simple control logic and the low cost hardware, it can provide high performance at low power consumption and is well applied to the design of processors, such as GPUs, AnySP [START_REF] Woh | AnySP: Anytime Anywhere Anyway Signal Processing[END_REF], Cell [START_REF] Flachs | The Microarchitecture of the Synergistic Processor for a Cell Processor[END_REF] and VT [START_REF] Krashinsky | The vector-thread architecture[END_REF]. Based on the above modern state-of-the-art SIMD processors, we setup a basic framework for SIMD processors. The basic SIMD processor is shown in Fig. 1 and is chosen as our platform to optimize the LU decomposition.

As is depicted in Fig. 1, a SIMD processor generally consists of a Scalar Unit (SU) and multiple Vector Processing Elements (VPEs). The SU is used to execute the communication and scalar computation. Multiple VPEs are used to accelerate the parallel computation. The number of VPEs is referred as SIMD width. Each VPE usually contains functional units such as ALU, Multiply-Accumulate (MAC) and Load/Store (LS). The adder tree performs the reduction add operation among VPEs. The shuffle unit can rearrange the vector data among all VPEs. The LS controls the access to the on-chip vector memory (VM) which consists of multiple parallel banks. A coalesced memory access can increase the bandwidth efficiency and therefore the performance of memory-bound kernels. The shared-registers (SR) can be accessed by the SU and all VPEs.

LU Decomposition

For solving a set of linear equations of the form Ax = b, where x and b are n×1 column vectors. The LU decomposition is used to factor a n×n matrix A into a n×n lower triangular matrix L (the diagonal entries are all 1) and a n×n triangular matrix U. Such that, LUx = b. Figure 2 shows the procedure of the basic LU decomposition of a matrix. The computation amount of the algorithm is O(n 3 ). And the communication amount is O(n 2 ). The matrix A is replaced by matrices L and U after the decomposition. The loop can be divided into two segments, which are separated by dotted lines in Fig. 2. The first segment is used to update the k th column, where the computation amount is O(n 2 ). The second segment is used to update the right lower sub-matrix, where the computation amount of the algorithm is O(n 3 ). As shown in Fig. 2, this algorithm has high data dependences. The updated k th column of A is used to update the right lower sub-matrix. The matrix updating segment can only be executed after all the iterations of k th column updating computation. As the matrix for decomposition is always large, the updated k th column cannot all reside in local registers and must be written back to memory. Although it is time cost, the updated k th column must be read from memory when performing the matrix updating segment, which causes large amount of memory access operations.

for k = 1 to n-1 In the segment of updating the k th column, A[k,k] is shared among all VPEs to perform the computation in parallel. The updated results cannot totally reside in registers, thus they must be stored into memory. We assume that the SIMD width is N. Totally N iterations can be executed in parallel in the segment of updating the right lower matrix, where N elements of the k th column must be loaded into registers from memory. As we can see, there are three apparent deficiencies in the above algorithm. Firstly, the high data dependences lead to the low pipeline parallelism. The two segments are totally executed in sequence. Secondly, all the temporary results, which are possible to reside in registers for reusing, are written back to the memory. Thirdly, the column data access, which causes non-coalesced access to parallel memory banks, is low efficient. To address this issue, we propose a fine-grained pipelined LU decomposition algorithm. The detail of this algorithm is explained in the next section.

for i = k + 1 to n A[i,k] = A[i,k]/A[k,k]; end for for j = k + 1 to n for i = k + 1 to n A[i,j] = A[i,j] -A[i,k] ╳ A[k,

Fine-grained Pipelined LU Decomposition

To achieve the high pipeline parallelism and the high efficient memory access, a direct way is reducing data dependences and transforming the non-coalesced access to coalesced version. To reduce the amount of memory access, we must try to keep the temporary results, which will be reused, in local registers. Thus, we must make a detailed analysis on the program. We analyze data dependences among the two task segments of the program code. Fig. 3 shows data dependences of the basic LU decomposition algorithm.

The loop unrolling technique is a traditional method for loop accelerating. For nested loop optimization, the universal method is internal loop unrolling with software pipelining. However, this method causes the non-coalesced memory access to k th and j th columns of matrix A. As shown in Fig. 3,the updated A[i,k] is used to update A[i,j] (j=k+1 to n) which is the i th row of matrix A. As the updating of the i th row is executed in the external loop of the second segment, we can unroll the external loop instead of the internal loop. The unrolled loop is dispatched to all VPEs. Each VPE execute an iteration of the external loop of segment 2. Then all VPEs access the i th row of matrix A in parallel. The non-coalesced memory access is smartly replaced by the coalesced memory access.

Iteration k = 1 A[2,1] A[3,1] A[4,1] A[5,1] A[6,1] A[2,2:n]; A[3,2:n];
A [4, The SIMD execution of the i th row updating only requires the updated A[i,k] but not the whole updated k th column. We can start the updating of i th row as soon as the

A[i,k] is updated. As the A[i,k] is a scalar element,

we can employ the SU to compute the A[i,k]. The updated A[i,k] is fast shared with all VPEs by using the SR without writing back to memory. The shuffle unit can broadcast A[i,k] to all VPEs. Then all VPEs immediately execute the updating of i th row in SIMD way after receiving A[i,k].

We can see that, the above method introduces a fine-grained pipelined algorithm for LU decomposition. The updating of sub-matrix is divided into a series updating processes for each matrix row. The updating of k th column is divided into a series updating processes for each column element. As soon as each column element is updated, it is immediately used to update the corresponding matrix row. Compared with the basic algorithm, the proposed method provides more fine-grained parallelism for the software pipeline.

The proposed software pipeline greatly corresponds to the data dependences. By software method assistance, the fine-grained pipelined LU decomposition can be easily implemented. Thus a high pipeline parallelism can be achieved. The proposed fine-grained pipelined algorithm has the following advantages: efficiently utilization of all the computation resource on the modern SIMD processor, reducing the memory access amount and transforming the non-coalesced memory access to coalesced version. The problems of low pipeline parallelism, too much memory access and low efficient memory bandwidth utilization are well solved.

Fig. 4 shows the data flow of the proposed algorithm on the SIMD architecture. As shown in Fig. 4, the k th column updating task is executed on SU. The right lower submatrix updating task is executed on all VPEs in SIMD way. To transform the noncoalesced memory access to coalesced version, the external loop of the sub-matrix updating segment is unrolled to be executed on all VPEs in parallel. And each VPE performs the internal loop. The SU and SIMD tasks are executed in parallel to achieve the high pipeline parallelism. The software pipelining technology is used to keep the native data dependence of the algorithm.

A[i,k] SU / VPE 1 ╳ - for i=k+1 to n A[i,j] = A[i,j] - A[i,k] ╳ A[k,j] A[i,k] = A[i,k]/A[k,k] A[k,k] A[i,k] A[k,j] A[k,j+1] A[k,j+N-1] VPE 2 ╳ - VPE N ╳ - for i=k+1 to n A[i,j+1] = A[i,j+1] -A[i,k] ╳ A[k,j+1] for i=k+1 to n A[i,j+N-1] = A[i,j+N-1] -A[i,k] ╳ A[k,j+N-1]
Fig. 4. The data flow of the proposed algorithm. Fig. 5 shows the code example of the proposed fine-grained pipeline algorithm. The software pipelining is not shown to simplify the description. As shown in Fig. 5, the SU task and SIMD task can be executed in parallel. The SU task is executed in the scalar unit to update the k th column. As soon as each element of the k th column is updated, it is written to the SR. Then the shuffle unit broadcasts the updated element to all VPEs. Each VPE employs this element to update a matrix row. All VPEs updates the sub-matrix in parallel. We have implemented a cycle-accurate simulator FT-Matrix-Sim based on our previous single-core simulator [START_REF] Chen | YHFT-QDSP: High-performance heterogeneous multi-core DSP[END_REF] for the SIMD architecture as shown in Fig. 1. In FT-Matrix-Sim, the VM is organized as scratchpad memory and simulated with a cycle-driven system. There are 16 VPEs, each having a 32-entry register file. Each VPE contains four function units: ALU, two L/S and MAC. The MAC unit supports one float-point operation each cycle. The SU has the same units with each VPE. The VM has 16 banks. Manually optimized assemble code is used as the input of the simulator.

for k = 1 to n-1 Initial SU task for i = k + 1 to n A[i,k] = A[i,k]/A[k,k]; end for Initial SIMD task for j = k +1 to n broadcast A[i,k] to all VPEs; for i = k + 1 to n A[i,j] = A[i,j] -A[i,k] ╳ A[k,j]; end for for i = k + 1 to n A[i,j+1] = A[i,j+1] -A[i,k] ╳ A[k,j+1]; end for for i = k + 1 to n A[i,j+N-1] = A[i,j+N-1] -A[i,k] ╳ A[k,j+N-1]; end for j = j +N; end for end for . . .
The architecture established by the simulator has also been implemented in Verilog hardware design language. The RTL implementation has been synthesized with Synopsys Design Complier under TSMC 65 nm technology in order to obtain the operating speeds and the cycle accurate performance simulation. The clock frequency of the synthesized circuit can be up to 500 MHz. Fig. 6 shows the performance of the proposed fine-grained pipelined LU decomposition algorithm. As can be seen, the speedup of the fine-grained algorithm over the basic algorithm can be up to 1.04x to 1.82x. The average speedup is 1.15x. The performance of the fine-grained algorithm can be up to 15.98 GFLOPS, where GFLOPS is a popular metrix for numerical computations. The peak performance of the synthesized circuit is 18 GFLOPS. Thus, we achieve 88.78% of peak performance on the SIMD processor by using the proposed fine-grained algorithm. The delectable result is that we can obtain better performance with the increasing of matrix size. The performance improvement resulting from the fine-grained algorithm is due to the following two factors: the high pipeline parallelism and the high efficient memory access. The fine-grained method greatly corresponds to the native data dependences of the algorithm. It well explores the fine-grained parallelism between the SU and multiple VPEs, which can effectively increase the pipeline parallelism and reduce the memory access amount. The external loop unrolling method of the fine-grained pipelined algorithm transforms all non-coalesced memory access to coalesced version, which is the high efficient memory access way. The coalesced method can reduce most of the memory access time. Table I shows the reduced memory access time of the fine-grained algorithm compared with the basic version. As can be seen, the proposed algorithm can reduce the memory access time by 90% to 96%.

The main contribution of the proposed algorithm is reducing the communication amount and hiding the computation time of updating the k th column. Both complexities of the above two tasks are O(n 2 ). However, the total computation amount of the algorithm is O(n 3 ). So the proportion of the performance increments brought by the proposed method goes smaller when the matrix size goes larger. But the absolute performance of the proposed algorithm is always high.

Conclusions

This paper proposed a fine-grained pipelined LU decomposition implementation on SIMD processors. The main performance improvement is achieved by the high pipeline parallelism and the high efficient memory access. The new algorithm well corresponds to data dependences of the native algorithm and effectively transforms the non-coalesced memory access to coalesced version, which increases the pipeline parallelism, reduces the memory access amount and increases the efficient of memory access. To illustrate our ideas, we implemented a cycle-accurate simulator and a RTL design. The RTL design was synthesized under TSMC 65 nm technology and achieved a frequency of 500 MHz. With the proposed algorithm, we can obtain a performance speedup about 1.04x to 1.82x over the basic LU decomposition algorithm. Most of the peak performance on the SIMD processor is well utilized by the proposed technology.

Fig. 1 .

 1 Fig. 1. The basic SIMD architecture.

  Fig. 2. The basic LU decomposition algorithm.

Fig. 3 .

 3 Fig. 3. Data dependences in the LU decomposition.

Fig. 5 .

 5 Fig. 5. The proposed fine-grained pipelined LU decomposition algorithm.

Fig. 6 .

 6 Fig. 6. The performance of proposed algorithm.

Table 1 .

 1 Reduced memory access time.

	Size	Reduced (%)	Size	Reduced (%)	Size	Reduced (%)
	128	90.15%	1024	94.85%	1920	95.85%
	256	91.62%	1152	95.01%	2048	95.92%
	384	92.65%	1280	95.23%	2176	95.95%
	512	93.41%	1408	95.39%	2304	95.96%
	640	93.81%	1536	95.53%	2432	95.97%
	768	94.19%	1664	95.64%	2560	95.99%
	896	94.54%	1792	95.74%	3000	95.99%

Acknowledgement

This work is supported by the National Natural Science Foundation of China (No.61070036) and HPC Foundation of NUDT.


Zhenxi Sun

Yuebin Bai
email: yuebinb@gmail.com

Songyang Wang

Yang Cao

Shubin Xu

A Virtual Network Embedding Algorithm based on Graph Theory

Keywords: Virtual Network, VN Embedding, Graph Theory, Node Similarity

Network virtualization is becoming a promising way of removing the inherent ossification of the Internet, and has been steadily attracting more and more researchers' attention during the decades. The major challenges in this field are improving the efficiency of virtual network embedding procedure and raising the rate of virtual network requests being successfully accepted by the substrate network. This paper introduces a new virtual network embedding algorithm based on node similarity, which means the similarity between the virtual nodes and the substrate nodes. For more details, by calculating the degree of nodes both in virtual network and substrate network, which is actually the number of links associated with them, the algorithm achieves better mapping results between virtual network and the substrate network on the topology aspect.

Introduction

For recent years, Internet is not only greatly changing the ways that people communicating with each other, but also making a profound influence on the whole society. During the past four decades, the internet architecture has proven its great worth by meeting most of the requirements of distributed applications, which is improving the life of whole world. However, the remaining problems and defects of the current internet are becoming more and more prominent, such as extendibility, manageability, quality of service and power-saving, and so on. In order to solve these problems fundamentally, some researchers propose an idea of designing the architecture of future network from clean-slate so that to break the constrains of current internet. However, no matter how to change the architecture of internet, what must be kept in mind are the following three requirements: firstly, researchers must be able to experiment easily with new architectures on live traffic from the existing networks. Secondly, there must be a plausible deployment path for putting validated architectural ideas into practice. Thirdly, the proposed solutions should be comprehensive so that they can address the broad range of current architectural problems facing the Internet [START_REF] Anderson | Overcoming the internet impasse through virtualization[END_REF], instead of focusing on a single narrow problem.

To keep up with such requirements, network virtualization shows the elegant charm and powerful vitality. It allows users create virtual networks which can be viewed as the normal networks used in real life and work, then maps them to the substrate networks which can be the networks with traditional internet architectures or other already deployed networks. In this way, the users can use the virtual network to meet their demands, for example, trying the new network architecture or providing services for companies or single users. By enabling a plurality of diverse network architectures to coexist on a shared physical substrate network, virtualization mitigates the ossifying forces at work in the current internet and enables continual introduction of innovative network technologies. Such a diversified Internet would allow existing architectural deficiencies to be holistically addressed as well as enable the introduction of new architectures supporting new types of applications and services [START_REF] Turner | Diversifying the internet[END_REF].

Currently, virtual network embedding algorithms mainly parted in two periods: virtual node mapping period and virtual link mapping period [START_REF] Chowdhury | Network virtualization: state of the art and research challenges[END_REF]. What's more, virtual network embedding problem, with constrains on virtual nodes and virtual links, can be reduced to the NP -hard multi-way separator problem [START_REF] Chowdhury | Network virtualization: state of the art and research challenges[END_REF], even if all the request are known in advance. Even when all the virtual nodes are already mapped, embedding the virtual links with bandwidth constraints onto substrate paths is still NP -hard in the indivisible flow scenario. As a result, there are many heuristic algorithms appears in this research area [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Houidi | A distributed and autonomic virtual network mapping framework[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Alkmim | Optimal mapping of virtual networks[END_REF]. Although the efforts on network virtualization research view the problem in case of the fixed networks or stable networks, the efficiency on mapping virtual networks to the substrate networks still has a huge improving space. What's worse, the mobile substrate networks are paid little attentions. What will happen if the substrate network is an unstable network environment, such as MANET (Mobile Ad hoc Networks).

In order to address the network virtualization of such environments, we devise a novel mapping algorithms with forecasting techniques in this paper. Firstly, we divide the nodes in physical networks into several small groups by the state of link between nodes, then map the virtual nodes to nodes of physical networks. Secondly, after all the virtual nodes have been mapped to physical nodes, the virtual link mapping phase is finished with multi-commodity flow algorithms.

The rest of the paper is organized as follows. Section II shows the related work in network virtualization field. Section III formulates and models the virtual network embedding problem. Section IV introduces the virtual network embedding algorithms. With the experiments result of the whole algorithm analyzed in section V, the paper will draw a conclusion in section VI.

Finding the optimal VN mapping solution that satisfies multiple objectives and constraints can be formulated as an NP -hard problem. The aspects of VN mapping algorithms appears until now include independent virtual node mapping and virtual link mapping, introduce better correlations between the two phases by facilitating the latter phase when mapping the virtual nodes to substrate networks, and simultaneously mapping virtual nodes and virtual links to the physical networks.

Being different from the embedding algorithms [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Houidi | A distributed and autonomic virtual network mapping framework[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Alkmim | Optimal mapping of virtual networks[END_REF] that separate the virtual node mapping procedure and the virtual link mapping procedure, authors in [START_REF] Chowdhury | Vineyard: virtual network embedding algorithms with coordinated node and link mapping[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF] introduces better correlation between the node mapping and the link mapping phases by proposing two new VN embedding algorithms D-ViNE (Deterministic VN Embedding) and R-ViNE (Randomized VN Embedding). The VN embedding problem deals with the mapping of a VN request, with constraints on virtual nodes and links, onto specific physical nodes and paths in the substrate network that has finite resources. Since multiple VNs share the underlying physical resources, efficient and effective embedding of online VN requests is of utmost importance in order to increase the utilization of substrate network resources and InP revenue [START_REF] Chowdhury | Vineyard: virtual network embedding algorithms with coordinated node and link mapping[END_REF]. Authors in [START_REF] Chowdhury | Vineyard: virtual network embedding algorithms with coordinated node and link mapping[END_REF] use mixed integer programming (MIP) formulation [START_REF] Schrijver | Theory of linear and integer programming[END_REF]to solve the embedding problem with binary constraints on the meta edges and linear constraints on actual substrate network links. Once all the virtual nodes have been mapped, they use the multi-commodity flow algorithm to map the virtual links onto substrate network paths between the mapped virtual nodes [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF]. While the algorithms are not taking the changing topology of the substrate network into account, [START_REF] Cheng | Virtual network embedding through topology-aware node ranking[END_REF] introduces a topology-aware note ranking method. Inspired by Google's PageRank measure, authors devise a Markov random walk model, for computing topology-aware resource ranking of a node to reflect both the resource and the quality of connections of the node in the network.

The authors in [START_REF] Houidi | A distributed virtual network mapping algorithm[END_REF] have proposed a distributed algorithm that simultaneously maps virtual nodes and virtual links without any centralized controller, but scalability and performance of their algorithm is still not comparable with the centralized ones. Another distributed and autonomic virtual network mapping framework is proposed in [START_REF] Houidi | A distributed and autonomic virtual network mapping framework[END_REF], where the substrate nodes integrates autonomous and intelligent agents which exchange messages and cooperate to carry out the proposed VN mapping algorithm. The paper takes nodes integration into account, but not estimate the influence from node movements brings to VN mapping efficiency. Although these algorithms have been verifying the mapping procedure in wireless network environments, physical node mobility of wireless network in the physical network environment is not taken into consideration.

Network Model and Problem Description

For clearly describing the VN embedding problem in MANET environments, the notation of the key elements should be defined in the very starting point. On the one hand, the notations can facilitate describing VN embedding algorithms; on the other hand, they will show what aspects the solutions have taken into consideration.

Substrate Network Description

We model substrate network an undirected and weighted graph, and note it as G s = (N s , E s ), where G s denotes the substrate network, N s denotes the set of nodes in substrate network and E s denotes the set of substrate links. Each node of substrate network n s ∈ N s is associated with CPU capacity c(n s ) and location information loc(n s ). And each link of substrate network e s ∈ E s is associated with the bandwidth b(e s ), where e s (i, j) denotes the bandwidth from the node i to node j.

What the most obvious difference between MANET and traditional internet is that the influence of node mobility must be taken into consideration in the former environments. Due to the movements of substrate nodes, the substrate links would be disrupted frequently. And the topology of the substrate network finds itself in a dynamically changing state. The initial reason is the mobility of the substrate nodes, while the ultimate result is the connected and disconnected states switching in substrate links. In order to applied network virtualization into such circumstance, the link state must be taken into consideration. Thus, we define the stability of the substrate link e s as s(e s ) ∈ [0, 1], where the bigger value represents the more stable state of e s .

Resources of Substrate Network

Each virtual network request should meet the following requirements. The computation requirements of virtual nodes is ultimately the computing speed of the CPU. When the virtual nodes need a 1Ghz computing speed, then the physical node should be 1GHz at least, and the higher the better. So the first requirement must be satisified is c(n v ) ≤ c(n s ). Similarly, the bandwidth requestment of virtual link should be smaller than the mapped physical links of substrate network. In another word, when mapping the virtual link to phsical links, the physical links bandwidth should be greater than that of the virtual link. Thus, the second requirements must be meet is b(n v ) ≤ b(n s ). While, the above two requirements should be applied when the physical nodes have not been mapped any virtual nodes. If not so, we should consider the remaining resources of the physical nodes and links of substrate network. The remaining computing resources (i. e. CPU capacity) is denoted by

R N (n s ) = c(n s ) - ∑ ∀n v ↑n s c(n v )
which means that the substrate computing resources of the substrate node n s is the total computing resouces subtract the resouces that already allocated to virtual nodes. In the same way, the substrate bandwidth is denoted by

R E (e s ) = b(e s ) - ∑ ∀e v ↑e s b(e v )
Thus, the more widely applied constraints on mapping virtual nodes to substrate nodes is as follows

c(n v ) ≤ c(n s ) -R N (n s )
For the virtual link mapping procedure, there is a little difference from the above node mapping procedure. The fact is that one virtual link usually was mapped onto several substrate links end to end, which are called path. Thus, the remaining bandwidth of the path is decided by the smallest one.

R E (P ) = min ∀e s ∈P (e s )
Therefore, the requirements must be satisfied in virtual link mapping procedure should be b(e v ) ≤ R E (P ), ∀P ∈ {All the mapped substrate links}

Network Description

A virtual network is similar as the substrate network, which is consisted of virtual nodes and virtual links. So the most fittable notations are G v = (N v , E v ), and G v denotes the virtual network topology, N v denotes the set of nodes in virtual network, E v denotes the set of virtual links of virtual network. The requirements of computation of each virtual node is described by c(n v ), where n v ∈ N v represents the subset of virtual nodes. In the same way, the bandwidth of each virtual link is marked by b(e v ), where e v ∈ E v , and denotes the subset of virtual links in virtual network.

VN Embedding Problem Description

When a virtual network request arrives, the substrate network should decide whether to accept the request or not. If the request accepted, a suitable mapping solution should be proposed by the substrate network. Generally, there are two phases in the mapping procedure, which are virtual node mapping and virtual link mapping. The node mapping phase usually is followed by the virtual link mapping phase.

Figure 1 describes the process of virtual network request being mapped to the substrate network with node constraints and link constraints. The two virtual network request finally mapped to the two separate part of the substrate network. This is merely an example of virtual network mapping, the more common case is several virtual network sharing the same part of the substrate network. The leftside of figure 1 depicts the virtual network request 1 and 2, which need to be mapped onto the substrate network on the right side. The numbers in Fig. 1. Mapping virtual network request to substrate network.

black rectangle represent the computaton capacity, in more details, that in virtual network is the VN request's requirements to the physical nodes and that in substrate network is the computation capacity the physical nodes can offer. Similarly, the number on lines shows the bandwidth of links, one for requirements, and the other one for the provided.

Virtual network embedding problem is defined as

M : G v (N v , L v ) → G s (N s , L s ) from G v to a subset of G s , where N v ⊂ N s and L v ⊂ L s .
Node Mapping Virtual nodes from the same virtual network must be mapped to different substrate nodes. In the mapping

M N : N v → N s , for all n v , m v ∈ N v , M N (n v ) ∈ N s M N (m v ) = M N (n v ), if f m v = n v subject to c(n v ) ≤ c(M N (n v )) - ∑ i v ∈N v c(i v ) dis(loc(n v ), loc(M N (n v )) ≤ D
where dis(a,b) is the distance of node a and node b in substrate network.

In figure 1, the first VN request has the node map of { a → B, b → D, c → H}, and the second VN request has the node map of { d → K, e → J, f → G, g → L }. Note that in this case, there is no virtual nodes from different VN request sharing the same substrate node. But it may be appeared that virtual nodes from different VN request be mapped onto the same substrate node in the real virtual network environments.

Link Mapping

The virtual links from VN request should be mapped to one or more substrate links with path splitting and migration. It is defined by a mapping M E : E v → P s from virtual links to a subset of substrate links such that for all

e v = (m v , n v ) ∈ L v , M E (m v , n v ) ⊆ P s (M N (m v ), M N (n v )) subject to b(e v ) ≤ R E (P), ∀P ∈ M E (e v )

Objectives

For the work in this paper, the major concentration is on improving the performance of the embedding procedure such as increasing the revenue of the virtual network and decreasing the cost of vitual network embedding which is similar to all the previous works in [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Vineyard: virtual network embedding algorithms with coordinated node and link mapping[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Cheng | Virtual network embedding through topology-aware node ranking[END_REF]. Besides, we also try our best to apply the network virtualization into wireless environments, more accurately, the Moile Ad Hoc Network environments, which is different from the works in [START_REF] Yun | Virtual network embedding in wireless multihop networks[END_REF][START_REF] Kokku | Nvs: a virtualization substrate for wimax networks[END_REF][START_REF] Kokku | Nvs: a substrate for virtualizing wireless resources in cellular networks[END_REF]. Similar to previous efforts [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Vineyard: virtual network embedding algorithms with coordinated node and link mapping[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Cheng | Virtual network embedding through topology-aware node ranking[END_REF],the revenue of the virtual network request as :

R(G v ) = ∑ e v ∈E v b(e v ) + ∑ n v ∈N v c(n v )
While revenue gives an insight into how much an InP will gain by accepting a VN request, it is not very useful without knowing the cost the InP will incur for embedding that request. We define the cost of mapping a virtual network request as the sum of total resources allocated to virtual network.

C(G v ) = ∑ e v ∈E v ∑ e s ∈E s f e v e s + ∑ n v ∈N v c(n v )
where f e v e s denotes the total bandwidth allocated on substrate link e s for virtual link e v .

Algorithms of VN Embedding

In graph thoery [START_REF]Graph thoery[END_REF], each node in the undirected graph has a degree noting that how many links are associated with. With the notion of node degree in mind, we divide the VN embedding into two greedy stage as most previous efforts. For the first stage, the node mapping algorithm take the effect, in which each node of the virtual network will be sorted by its degree in descending order. The reason for such processing is that the larger of the node degree means that the node will be more important in the virtual network. Further more, the node with larger degree being mapped onto the substrate network, the consequence nodes will be mapped more easily. In addition, such dealing with node mapping will increase the probability of accepting the virtual network request. The calculations of node degrees is as follows.

Algorithm 1 Calculations of node degrees

Require:

The set of virtual network request G v = (N v , E v ) Ensure: The vector of virtual nodes with descending order on node id vN odeRank 1: for each e v ∈ E v do 2: id← Get the first vertex id of e v 3: vNodeRank[id]++ 4:

id← Get the second vertex id of e v 5:

vNodeRank[id]++ 6: end for 7: return vN odeRank;

The notion is similar with the idea in [START_REF] Cheng | Virtual network embedding through topology-aware node ranking[END_REF] on a certain extent, but the most obvious difference is that the virtual nodes with highest node ranking will be mapped onto the substrate nodes with highest node ranking in [START_REF] Cheng | Virtual network embedding through topology-aware node ranking[END_REF]. In our work, the virtual nodes with highest node ranking might not be mapped onto the substrate nodes with the same highest node ranking. We sort both the nodes in virtual network request and the substrate network by the note degree which is decided by the associated links in descending order. In order to increase the accepted ratio of VN request and improve the utilization of substrate nodes, we map the virtual nodes with highest degree and lowest cpu requirements to the substrate nodes who obtains the highest degree in substrate network environments. The virtual node mapping algorithm is as follows.

Algorithm 2 Virtual node mapping algorithm

Require:

The set of virtual network request

G v = (N v , E v ) Ensure:
The sequence of virtual nodes being mapped onto substrate nodes 1: Sort the virtual nodes N v by node degree 2: Sort the substrate nodes N s by node degree 3: for each n v ∈ N v do 4: maxdegree=degree(n s )*1.2 5: mindegree=degree(n s )*0.8 6:

for each n s ∈ N s do 7:

if degree(n s ) ∈ (mindegree, maxdegree) then 8:

potentialN odeSet ← n s 9:

end if 10:

end for 11:

find n s ∈ potentialN odeSet with least remain computing resource 12:

n s ← n v 13: end for For the virtual link mapping phase, we use the greedy algorithm as follows.

Algorithm 3 Virtual link mapping algorithm

Require:

The set of VN request G v = (N v , E v ) , with all the edges in Q Ensure:

The state that shows the mapping procedure succeeded or failed. 1: while Q ̸ = ∅ do 2:

E v =Q. dequeue(); 3:

Remove those substrate links that cannot satisfy the bandwidth requirement of E v . Use the shortest path algorithm to find a link mapping solution for E v . 4:

if cannot find a path for E v then 5:

return FAILED 6: end if 7: end while 8: return SUCCESS

Performance Evaluations

In this section, we first describe the performance evaluations and then present our main evaluations result with analysis. Our evaluations mainly on the ratio of accepting VN request for substrate network, the revenue of the VN and the utilization of substrate nodes and links.

Simulation Environments

Our VN embedding simulation environment is based on the simulator called ViNE-Yard. It is a discrete event simulator with about five thousand lines of code implemented by C++ language. The simulator is freely available in the address [START_REF] Chowdhury | Vine-yard simulator[END_REF]. According to the previous work [START_REF] Chowdhury | Vineyard: virtual network embedding algorithms with coordinated node and link mapping[END_REF], the substrate network topology in our experiments are randomly generated with 50 nodes using the GT-ITM tool [START_REF] Zegura | How to model an internetwork[END_REF] (25×25) grids. Each pair of substrate nodes is randomly connected with probability 0.5. The CPU and bandwidth resources of the substrate nodes and links are real numbers uniformly distributed between 50 and 100. It's assumed that VN requests arrive in a Poisson process with an average rate of 4 VNs per 100 time units, and each one has an exponentially distributed lifetime with an average of = 1000 time units. In each VN request, the number of virtual nodes is randomly determined by a uniform distribution between 2 and 10 following similar setups to previous works [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF]. The average VN connectivity is fixed at 50%. The CPU requirements of the virtual nodes are real numbers uniformly distributed between 0 to 20 and the bandwidth requirements of the virtual links are uniformly distributed between 0 to 50.

Result Analysis

There are four performance metrics which are described in the former section, the accepted ratio of VN request, the revenue of VN, and utilization of substrate nodes and substrate links. The main observations we want to summarize are as follows. Firstly, figure 2 shows the changing of VN request accepted ratio over time. From the very beginning, due to the sufficient resources, both the computing resources and bandwidth in substrate network, the VN request is quickly accepted by the substrate network. While, with the passage of time, the available resources in substrate network decreases dramatically, which causes the drop down of the VN accepted ratio. After a period, the balance is established between the VN request incoming and VN cancelling. From the figures 3,4,5, it can be seen that the utilization of substrate nodes and substrate links has an obvious improving space.

Conclusions and Future Work

Besides the frameworks of virtual network systems, the major problems in network virtualization is the virtual network embedding problem. Improving the acceptance ratio of virtual network request is the most important aspect, not only because it can increase the revenue but also make full utilization of the resources in substrate networks. In this paper, we devised a virtual network mapping algorithm based on the similarity between the nodes in virtual networks and that in substrate networks.

The unstable link state in MANET environments is caused by the movements of nodes, we just define the link state categories without deep into the regular pattern of node movements in the paper. But the estimation against the link state is not accurate enough, we shall discover the distributions of node mobility. For example, let the node follow the random walk movement model or some other models. In other words, the link state should be estimated by finding the accurate assessment of node movement.

Current works all define the problem space by fixed CPU capacity and link bandwidth, but in the real world, they are varying all the time. So there is still spaces on improving the usage of the computing resources and resources. What's more, the standard on selecting the appropriate nodes and links for virtual network be mapped to is various, current major works just define a fixed one on the selection standard, this is not widely applied in real environments. From the previous works, researchers propose the methods on path migration and splitting, which raise large amount of the ratio on virtual network request acceptance. While if the node migration and splitting is supported, then a virtual network request is rejected only if the total amount of bandwidth and the ability of computing required by virtual networks exceed from that of substrate networks.

Fig. 2 .Fig. 3 . 1 timeFig. 4 . 1 timeFig. 5 .

 231415 Fig. 2. VN request accepted ratio over time

Acknowledgments

We would like to thank the anonymous reviewers for their comments and suggestions. This work is supported by the project of the National Science Foundation of China under Grant No. 61073076, Ph.D. Programs Foundation of Ministry of Education of China under Grant No.20121102110018, the 2013 Open Funds of Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory, and the Postgraduate Innovation Practice Fund (YCSJ-02-02) in Beihang University.