Mingdong Tang
email: tangmingdong@ict.ac.cn

Jianxun Liu

Guoqing Zhang
email: gqzhang@ict.ac.cn

Improved Compact Routing Schemes for Power-Law Networks

Keywords: compact routing, power law, stretch, routing table size, algorithm

Compact routing intends to achieve good tradeoff between the routing path length and the memory overhead, and is recently considered as a main alternative to overcome the fundamental scaling problems of the Internet routing system. Plenty of studies have been conducted on compact routing, and quite a few universal compact routing schemes have been designed for arbitrary network topologies. However, it is generally believed that specialized compact routing schemes for peculiar network topologies can have better performance than universal ones. Complex network research has uncovered that most realworld networks have degree distributions exhibiting power law tails, i.e., a few nodes have very high degrees while many other nodes have low degrees. Highdegree nodes play a crucial role of hubs in communication and networking. Based on this fact, we put forward two highest-degree landmark based compact routing schemes, namely HDLR and HDLR + . Theoretical analysis on random power law graphs shows our schemes can achieve a better space-stretch tradeoff than prior compact routing schemes. Simulations conducted on random power law graphs and real-world AS-level Internet graph validate the effectivity of our schemes.

Introduction

Routing is a basic function of a network on which many upper-layer applications rely.

For the efficient use of network resources (link capacities, etc.) it is desirable to design schemes which route along paths as short as possible. This is measured by the metric called stretch, which can be represented by ( , ) α β , meaning the path between any two nodes u, v is no longer than ( , ) d u v + α β , where ( , ) d u v is the length of the shortest path between u and v. A scheme with stretch ( , 0) α is said to have multiplicative stretch, whereas one with stretch (1, ) However, these two objectives are contradictive in that optimizing one will typically deteriorate the other. At one extreme, the shortest path routing ensures the minimum stretch (i.e. with a multiplicative stretch of 1) but requires a ( log )

O n n table size at each node (one entry for every node in the network). At the other extreme, the flooding scheme does not need to maintain any state information at each node, but has a worst-case multiplicative stretch O(n) for general graphs. Both of these two solutions do not scale well. It is evident that there is a tradeoff between the space requirement and the stretch. It is desirable, therefore, to develop schemes with good tradeoff between them. Such schemes typically have the property of near-optimal stretch but with substantially smaller routing tables.

The routing schemes that balance between routing table size and stretch are usually called compact routing schemes. Compact routing schemes on arbitrary network topologies (also termed as universal schemes) [START_REF] Thorup | Compact routing schemes[END_REF][START_REF] Cowen | Compact routing with minimum stretch[END_REF][START_REF] Gavoille | Space-Efficiency for routing schemes of stretch factor three[END_REF] and specific networks such as trees [START_REF] Fraigniaud | Routing in trees[END_REF][START_REF] Laing | Name-independent compact routing in trees[END_REF], planar graphs [START_REF] Lu | Improved compact routing tables for planar networks via orderly spanning trees[END_REF], growth bounded graphs [START_REF] Abraham | Name independent routing for growth bounded networks[END_REF] and graphs with low doubling dimension [START_REF] Konjevodg | Optimal scale-free compact routing schemes in networks of low doubling dimension[END_REF][START_REF] Abraham | Routing in networks with low doubling dimension[END_REF] have attracted wide research attentions. Presently, the most optimized universal compact routing scheme could restrict the routing table size on each node to

1/ 2 ( ) O n
1 bits, and meanwhile, achieve a multiplicative stretch of 3, i.e., the length of the path between any node pair taken by the routing is no more than 3 times the length of the shortest path between the node pair. Although it has been proved that no routing scheme can achieve multiplicative stretch less than 3 with sublinear space for generic networks [START_REF] Gavoille | Space-Efficiency for routing schemes of stretch factor three[END_REF], it is generally believed that routing schemes specialized for peculiar network topologies can achieve better performance than universal ones. This is because, unlike the TZ scheme, specialized routing schemes can exploit the topological properties of special networks.

Recent researches on complex networks have uncovered that many real-world networks, such as the Internet [START_REF] Faloutsos | On power-law relationships of the Internet topology[END_REF], P2P [START_REF] Ripeanu | Mapping the Gnutella network[END_REF], WWW [START_REF] Albert | Dimeter of the world wide web[END_REF], have scale-free topologies, i.e., the degree distribution follows a power law. Compact routing on power law networks has attracted increasingly more attention [START_REF] Krioukov | Compact routing on Internet-like graphs[END_REF][START_REF] Brady | Compact routing on power law graphs with additive stretch[END_REF][START_REF] Carmi | Searching complex networks efficiently with minimal information[END_REF][START_REF] Enachescu | Reducing maximum stretch in compact routing[END_REF][START_REF] Norros | Powernet: compact routing on Internet-like random networks[END_REF]. Many researchers even consider compact routing as a promising alternative to overcome the scaling limitations of the Internet routing system [START_REF] Meyer | Report from the IAB workshop on routing and addressing[END_REF][START_REF] Huston | Analyzing the Internet's BGP routing table[END_REF][START_REF] Krioukov | On compact routing for the Internet[END_REF]. Although previous work has experimentally showed that specialized routing schemes can outperform the optimal universal routing scheme on power law networks, they seldom give theoretical analysis and guaranteed performance on stretch and routing table size.

In this paper, we focus on compact routing in power law graphs, and present two high-degree landmark based routing schemes, namely HDLR and HDLR + . Based on the RPLG (Random Power Law Graph) model [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF][START_REF] Lu | Probabilistic methods in massive graphs and Internet computing[END_REF], theoretical analysis shows: 1) HDLR can achieve a multiplicative stretch of 3 and average routing table size of

Related Work

Since 1990s, several excellent compact routing schemes are proposed for generic networks [1-3][23], among which the Cowen scheme [START_REF] Cowen | Compact routing with minimum stretch[END_REF] and the TZ scheme [START_REF] Thorup | Compact routing schemes[END_REF] are two prominently referenced ones. Cowen scheme is the first universal compact routing scheme that reduces the stretch to ( . Both these two schemes are landmarkbased and differ only in how landmarks are selected. Cowen scheme adopts a greedy algorithm to find the dominating set of the graph, and obtains the landmark set based on this dominating set, whereas the TZ scheme relies on random techniques for landmark selection. Since Gavoille and Gengler [START_REF] Gavoille | Space-Efficiency for routing schemes of stretch factor three[END_REF] showed that no universal routing scheme with a multiplicative stretch < 3 can produce o(n) routing table size, and Thorup and Zwick [START_REF] Thorup | Approximate distance oracles[END_REF] proved that any routing scheme with multiplicative stretch strictly below 5 cannot guarantee space smaller than

1/ 2 ( ) O n
, it thus follows that the TZ scheme is nearly optimal as far as the stretch and routing table size are concerned.

All the above schemes are designed for generic networks. However, recent studies revealed that most real networks, for example, the Internet, WWW and unstructured P2P networks, can all be categorized as power-law networks [START_REF] Barabasi | Emergence of scaling in random network[END_REF][START_REF] Zhang | Evolution of the Internet and its cores[END_REF][START_REF] Zhou | The rich-club phenomenon in the Internet topology[END_REF][START_REF] Sommer | Compacting routing in power-law graphs[END_REF], i.e., the degree distribution p(k) satisfies

γ - k k p ) (
, where γ is called the power-law exponent, typically between 2 and 3. It has been shown that on power-law networks, high degree nodes play the hub role for network connectivity and routing [START_REF] Enachescu | Reducing maximum stretch in compact routing[END_REF][21], most nodes are directly connected to these nodes or separated by only a few hops, and the path between these high degree nodes are typically very small [START_REF]CAIDA[END_REF]. So recently, compact routing schemes on power-law networks have attracted much attention. Krioukov [START_REF] Krioukov | Compact routing on Internet-like graphs[END_REF] first evaluated the performance of the TZ scheme on Internet-like power-law graphs, and found that the performance is far better than the worst case theoretic results, e.g., the average multiplicative stretch is only 1.1. Brady and Cowen [START_REF] Brady | Compact routing on power law graphs with additive stretch[END_REF] introduced the concept of additive stretch, and proposed a compact routing scheme with additive stretch (1,d) and logarithmic routing table scaling, i.e. O(elog 2 n). Simulations showed that d and e can both take small values on power-law networks, and the average stretch is lower than the TZ scheme. Other specialized compact routing schemes on power-law networks can be found in recent works [START_REF] Carmi | Searching complex networks efficiently with minimal information[END_REF][START_REF] Enachescu | Reducing maximum stretch in compact routing[END_REF][START_REF] Norros | Powernet: compact routing on Internet-like random networks[END_REF].

Although the aforementioned work is effective, none of them gave theoretical bounds on stretch and routing table size. Most recently, Chen et al. [START_REF] Sommer | Compacting routing in power-law graphs[END_REF] proposes a compact routing scheme, which is the first routing scheme guarantees a better spacestretch tradeoff on power law graphs than universal ones. The theoretical analysis is based on the RPLG (Random Power Law Graph) model [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF][START_REF] Lu | Probabilistic methods in massive graphs and Internet computing[END_REF], and shows the routing table size can be reduced to

) ( ~3 / 1 n O or less using address length of ) log log (log n n O
bits and stretch of (3,0). However, Ref. [START_REF] Sommer | Compacting routing in power-law graphs[END_REF] makes no progress in the worst-case stretch compared to the universal optimal scheme. Our proposed scheme HDLR + is the first compact routing scheme that achieves a better stretch than (3,0) on power law networks. Furthermore, HDLR and HDLR + are superior to the scheme by Ref. [START_REF] Sommer | Compacting routing in power-law graphs[END_REF] by using addresses and packet headers both with O(logn) bits.

Definitions and Notations

We model a communication network as an undirected, unweighted graph G=(V,E), with vertices representing routers and edges representing communication links. For convenience, we use the terms vertex and node, edge and link interchangeably throughout this paper. The distance between any two nodes V v u ∈ , , is defined as the number of edges on the shortest path between them, denoted by d(u,v).

A routing scheme R is a distributed algorithm for packet delivery between any two nodes in the network. R can only be called compact if it has routing tables with sizes sublinear in n and message header sizes polylogarithmic in n. There are two classes of compact routing schemes: Name-dependent schemes are allowed to add labels to node addresses to encode useful information for routing purposes, where each label has length at most polylogarithmic in n. Name-independent schemes do not allow renaming of node addresses, instead they must function with all possible addresses. We consider name dependent routing in this paper. Denote the length of the path traversed by a packet from u to v according to a routing scheme R by ( , )

R d u v .
The quality of a routing scheme is primarily measured by two metrics: the storage space of the distributed data structures established by the preprocessing procedure, typically referring to the size of routing table; and the routing efficiency, measured by the stretch. Other metrics include packet header length, routing table convergence time and communication cost. In this paper, we only consider routing on static topologies, hence the convergence time and communication cost are out of our consideration.

Our Routing Schemes

This section introduces the design of our routing schemes-HDLR and HDLR + , which are both landmark-based schemes. The basic idea of landmark based routing is to select a small proportion of nodes from the network as landmarks. The routing table of each node only stores routing entries for the landmarks and its vicinity. As a result, suppose a node is sending a packet to some destination, if the destination node could be found in the source node's routing entries, then the packet can be delivered along the shortest path; otherwise, the packet is first sent towards the nearest landmark of the destination, and then will be delivered to the target by the landmark. HDLR is adapted from the TZ scheme by using a highest degree landmark selection method instead of a random one, and HDLR + extends HDLR by optimizing its stretch.

HDLR

Let A ⊆ V represent the landmark set. For any u∈ V, define u's ball B(u) to be B(u) = {v∈ V|d(u, v) < d(u, A)}, where d(u, A) is the minimum shortest path length among all the shortest paths from u to all the landmarks in A, and define u's cluster C(u) to be C(u) = {v∈ V|u∈ B(v)}. Take the graph in Fig. 1 as an example, Table 1 illustrates these definitions.

In HDLR, The preprocessing procedure consists of the following steps: 1) landmark selection: sort the nodes in decreasing order of their degrees, and choose the first x n nodes as the landmarks, where 1 0 < < x is a tunable parameter; 2) address assignment: for each non landmark u∈ V -A, assign (u, A(u), ) (

) ( u e u A )
as its address, denoted as Address(u), where A(u) is the name of the nearest landmark to u, and ) (

) ( u e u A
is the identifier of the port at A(u) that lies on the shortest path from A(u) to u; for each landmark, its address is identical to its name.

3) routing table setup: for each non landmark u∈

V -A, its routing table is Table (u) = {(v, e u (v))|v∈ A ∪ C(u)}.
In other words, u stores the routing entries to nodes in A and C(u), where e u (v) is the identifier of the port at u that lies on the shortest path from u to v; for each landmark l∈ A, its routing table only contains the routing information to other landmarks, i.e., Table(l) = {(v, e l (v))|v∈ A -{l}}. We can see the routing table at each node is much smaller than generic shortest path routing schemes. For example, in Fig. 1, the routing tables of u contain only 5 routing entries for {a, b, c, d, s}, as a contrast to 19 entries for all other nodes if a shortest path routing scheme is adopted. The packet forwarding procedure of HDLR is very similar to the TZ scheme. Assuming a packet with a destination address (v, A(v), e A(v) (v)) arrives at node u, u makes the following decision:

1) If u = v, then the packet reaches its destination; 2) otherwise, if u = A(v), then forward the packet using the port e A(v) (v) that found in the packet header; 3) otherwise, if Table(u) contains the routing entry for v, forward the packet using the port e u (v); 4) otherwise, forward the packet to A(v) using the port e u (A(v)) found in Table(u). The above forwarding algorithm is likely to use non-shortest paths, with a worstcase stretch of (3,0), as will been proved in Section 5. For example, in Fig. 1, when sending a packet from u to v, the actual forwarding path would be u -w -b -t -v, but the shortest path between u and v is u -s -v.

HDLR +

The HDLR + scheme is an extension of HDLR, with the purpose to optimize the worst-case stretch for compact routing in power law graphs. Based on HDLR, we store limited more information at each node u, by adding entries for nodes in B(u) to Table(u). Therefore, for any non-landmark node u, Table (

u) = {(v, e u (v))| v ∈ A ∪ B(u) ∪ C(u)}.
While for each landmark l, its routing table is still only composed by entries for nodes in A, as both B(l) and C(l) are empty. By this means, as we will show through analysis in Section 5, the worst-case stretch of HDLR + is superior to HDLR. Except the routing table setting, the other aspects of HDLR + such as the landmark selection and address assignment scheme, and the forwarding algorithm are identical to HDLR. Therefore, we omit unnecessary details of HDLR + .

Analytical Performance Analysis

In this section, we use the random power law graph theory [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF][START_REF] Lu | Probabilistic methods in massive graphs and Internet computing[END_REF] to analyze the space-stretch tradeoff of the proposed two schemes, and present the bounds for address length, stretch and routing table size.

Theory of Random Power-Law Graphs

The random power-law graph model extends the generic random graph theory for power-law networks.

Definition 1(Random Power Law Graph [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF][START_REF] Lu | Probabilistic methods in massive graphs and Internet computing[END_REF]). Let G(k) represent the ensemble of all random graphs satisfying the expected degree sequence k = (k 1 , k 2 , ..., kn), where k i is the expected degree of node v i . The probability that there is an edge connecting two nodes v i and v j is given by

∑ = n z z j i k k k 1 /
. If k = (k 1 , k 2 , ..., kn) follows power-law distribution, then G∈ G(k) is called a random power-law graph.

An important reason to work with this random graph model is that the edges are independent. This independence makes several graph properties easier to analyze. Actually, there are already many analytical results for the topological properties of random power-law graphs, in the following we introduce some useful ones, which offer basic proofs for the analysis in this section.

Let Proof. Readers can refer to Ref. [START_REF] Chung | The average distances in random graphs with given expected degrees[END_REF], page 62, Lemma 12, for the proof of this Lemma. □

From Lemma 1, we can see that the subgraphs induced by high-degree vertices of power law graphs usually have very small diameters, approaching some constant when the graph size increases. (apparently, when n is sufficiently large, ε could be very small). Let G is an instance of G(k), then for all u ∈ V(G), the following property holds with probability at least

2 3 1 - -n : |B(u)| = |{u∈ V(G): d(u, v′) < d(u, τ ) (k G S )}| = ) ( α n O
, where

' β τ n = .′
Proof. Please refer to Ref. [START_REF] Sommer | Compacting routing in power-law graphs[END_REF], Lemma 7, for the proof of this Lemma. □ Lemma 2 indicates that for power law graphs, if high-degree nodes are selected as landmarks, the ball size of any node u is high likely to has an upper bound much smaller than the size of the graph. This might be partly caused by the reason that ordinary nodes in power law graphs usually have very small hop distances to highdegree nodes, which limits the range of neighborhood expansions and thus ball sizes.

Analysis

In the following, we analyse the routing performance of HDLR and HDLR + on random power law graphs, using the metrics such as address length, stretch and routing table size.

The address length of HDLR or HDLR + is O(logn) bits, which arises from the following observations. For any node v, its address is (v, L(v), e A(v) (v)). Since the node name and interface identifier can both be represented using O(logn) bits, so the address length is O(logn). Because each packet of HDLR or HDLR + only includes the destination address, the packet header length of HDLR or HDLR + is also in O(logn) bits. For the stretch of HDLR or HDLR + , we have the following analytical results.

Theorem 1. The worst-case stretch of HDLR and HDLR + are (3, 0) and min{(3,0),(2,DA)} respectively, where

D A = ) , ( max , v u d A v u ∈

Simulations

In order to provide an insight into the real performance of our proposed scheme on power-law networks, we perform simulations on both the synthesized graphs generated by the random power-law graph (RPLG) model and the real AS-level Internet topology. The AS graph is acquired from CAIDA [START_REF]CAIDA[END_REF], having a total of 9204 nodes, 28959 edges, and a power law component about 2. ).

Diameter of the subgraph induced by landmarks

Fig. 3 reports A D , the diameter of the subgraph induced by the landmark set A , for random power law graphs with different network size and different power law exponents. We can see that A D remains relatively stable as the network expands.

Also, we observe that when γ increases, A D increases accordingly. This is because when γ increases, the degrees of landmarks in A will decrease, making the edges connecting landmarks more sparse, thus A D increases. It is worth noting, for AS graph, A D is only 2, much smaller than those in the corresponding random power law graphs. This is due to the rich-club structure in AS graph, i.e., high degree nodes are prone to connect with each other directly, which does not happen in random power law graphs.

Average Routing Table Size

Fig. 4 shows the average routing table size obtained by our schemes and the TZ scheme on random power law graphs with = γ 2.1 and AS graph. For each random power law graph, the number of landmarks is set to be It is evident that with our schemes, the routing table size can be significantly reduced compared to the TZ scheme. With our schemes, the average routing table size is very close to |A|, implying the size of the local cluster and the ball of a node are usually very small. For AS graph, the average routing table size achieved by HDLR or HDLR + is about 22 or 23. It is not surprising that the routing table size produced on AS graph is remarkably smaller than those on random power law graphs. The reason may be that in AS graph, the highest degree nodes have much higher degrees than those in a random power law graph with comparable size. For example, the highest degree of AS graph with 9204 nodes is 2070, while the highest degree of a random power law graph with similar size is only about 60. This implies that in AS graph a majority of nodes are directly connected with a very small set of highest degree landmarks, thus markedly decreasing the size of the routing table.

Average Stretch

Fig. 5 shows the average multiplicative stretch achieved by our schemes and the TZ scheme on AS graph and random power law graphs with different exponents. Again, for random power law graphs we set

A n = = .
It is observed that our schemes outperform the TZ scheme with non marginal improvement For random power law graphs, HLDR or HDLR + achieves a 1.06~1.09 average stretch, whereas the TZ scheme can only achieve a much higher average stretch in the range of 1.14~1.20. For AS graph, our schemes have an average multiplicative stretch about 1.09 while the TZ scheme with an average multiplicative stretch about 1.17. The average stretch of HDLR + is very close to that of HDLR, with only negligible improvement. This is due to the fact that the routing table size of HDLR + is only slightly larger than HDLR. We also notice that, when γ increases, the average stretch of all routing schemes are decreasing. The reason may be, when γ increases, the average routing table size increases, thus a node knows more routing information, resulting more shortened stretched paths.

Conclusions

In this paper we present two compact routing schemes, HDLR and HDLR + , aiming to improve the space-stretch tradeoff for routing in power law graphs. Based on the fact that in a power law network graph a few nodes usually have very high degrees, and play the important role of hub in communication and networking, we select highdegree nodes as landmarks. Analytic study on random power law graphs shows: 1) HDLR can achieve a multiplicative stretch of 3 and an average routing table size of

Tabel 1 .Fig. 1 .

 11 Fig.1. An example of the HDLR scheme. Filled nodes are landmarks. It illustrates the forwarding path form u to v taken by the HDLR scheme. Solid lines are the actual path used by HDLR scheme, and the dashed lines compose the shortest path.

Lemma 1 .

 1 the set of nodes in G(k) whose expected degrees are no less than k, then the following property holds for the subgraph induced by k Suppose G ∈ G(k) is a power-law graph instance with the power-law exponent satisfying 2 < γ < 3. Given t ≥ δ the diameter of the subgraph induced by t G S ) (k has probability 1-n -2 not exceeding (1 + o(1))

Fig. 3 .

 3 Fig.3. Diameter of landmarks on random power law graphs and AS graph.

Fig. 4 .

 4 Fig.[START_REF] Fraigniaud | Routing in trees[END_REF]. Average routing table size on random power law graphs and AS graph: comparison of our routing schemes and the TZ scheme.

Fig. 5 .

 5 Fig.5. Average stretch on random power law graphs and AS graph: comparison of our routing schemes and the TZ scheme.

  with high probability, where A D is the diameter of the sub-graph induced by the landmark set and is almost surely bounded by some constant. Both HDLR and HDLR + improve the space-stretch tradeoff obtained by the TZ scheme, whose bounds for stretch and routing table size are (3,0) and Simulations conducted on networks generated by synthetic random power law graph model with different parameter settings and real-world AS graph validate our results.

		1/ 3 ( ) O n	with high
	probability. 2) HDLR + can achieve a stretch of min{(3, 0), (2, )} A D	and an average
	routing table size of	1/ 3 ( ) O n
				1/ 2 O n (	)	.

Acknowledgments. The authors are supported by the National Natural Science Foundation of China under Grant No. 90818004 and 60973129.

is the maximum distance between any two landmarks. Proof. Let's first consider the HDLR scheme. Suppose a node u is to send a packet to node v. Let ( , ) R d u v denote the length of the route taken by HDLR between u and v. If v is stored in u's routing table, u can route along the shortest path to v, in this case the stretch is [START_REF] Thorup | Compact routing schemes[END_REF]0). Otherwise, u will forward the packet to A(v), as is shown in Fig. 2. When the packet reaches A(v), A(v) will forward the packet along the shortest path to v. Therefore we have ( , ) ( , ( )) ( ( ), )

According to the triangle inequality, we know ( , ( )) ( , ) ( ( ), ))

This produces a stretch (3,0) for HDLR.

For the HDLR + scheme, It's not difficult to see, Equation (1), ( 2), ( 3) and (4) also hold according to its forwarding algorithm and routing table setting. This means the

Fig. 2. Proving the stretch of HDLR and HDLR + . Filled nodes denote the landmark set. Assuming node u is to send a packet to node v, which is not stored in Tabel(u).

(1)

(2)

(3) (4) HDLR + scheme also has a worst-case stretch [START_REF] Gavoille | Space-Efficiency for routing schemes of stretch factor three[END_REF]0). Besides, we'll prove HDLR + can achieve another stretch (2,D A ).

As the dash lines in Fig. 2 show, according to the triangle inequality, we have ( , ( )) ( , ( )) ( ( ), ( )) [START_REF] Thorup | Compact routing schemes[END_REF] and Equation ( 5), we get ( , ) ( , ( )) ( ( ), ( )) ( ( ), ) 4) and Equation ( 7), we can see HDLR + can achieve the stretch min{(3, 0), (2, )}

A D . □

In Theorem 1, one critical problem is what the D A will be on a typical power-law network. In the following, we show that with high probability D A is bounded by a constant in random power-law graphs.

Corollary 1. Let G to be an instance of G(k), and the landmark set A to be composed of the n x (0 < x < 1) nodes with the highest expected degrees, then D A has probability 1 n -2 to be bounded by a constant.

Proof. Assuming the degree distribution of G(k) follows P(k) ∝ k -r , then the cumulative degree distribution can be represented by P(z≥k) = ck 1 -r , where c is a constant. Denote the smallest expected node degree in A as τ . According to the cumulative degree distribution, we have

where c 1 is a constant depending on γ and c.

A can be treated as

. Since γ ,c and x can all take constant values, this expression will be bounded by a constant as n → ∞. According to the definition of D A , D A is no greater than the diameter of the subgraph induced by A, hence D A is bounded by a constant with probability 1-n -2 . □

The routing table size of HDLR and HDLR + can be analyzed separately for landmarks and non landmarks. For each landmark l, HDLR and HDLR + have the same routing table setting, i.e., ) (l Corollary 2. Let G be an instance of G(k), A be the landmark set consisting of the n x nodes with the highest expected degrees, then for any u∈ V(G), the probability that

, ξ is sufficiently small. Proof. According to Corollary 1, the least expected degree

, which can be rewritten as

, where '

According to Lemma 2, we know that Proof. According to the definitions of C(u) and B(u), it follows that for any v ∈ B(u), we have u ∈ C(v), and vice versa. Since these u, v occur pairwise, so Lemma 3 holds. □ Based on the above analysis, we have the following Theorem.

Theorem 2. Let G be an instance of G(k), and let A be the landmark set containing the n x nodes with the highest expected degrees, then for any non landmark node u ∈ V(G), with probability at least


Joonmin Gil
email: 3jmgil@cu.ac.kr

Daeyong Jung

Sungho Chin

Kwangsik Chung

Heonchang Yu

An Efficient Checkpointing Scheme Using Price History of Spot Instances in Cloud Computing Environment

Keywords: Cloud computing, Checkpointing, Spot instances, Price history

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

Introduction

Cloud computing is a type of parallel and distributed system consisting of a collection of interconnected and virtualized computers that are dynamically provisioned and presented as one or more unified computing resources based on service-level agreements established through negotiation between the service provider and consumers [START_REF] Buyya | Market-Oriented Cloud Computing: Vision, Hype, and Reality for Delivering IT Services as Computing Utilities[END_REF]. Typically, cloud computing services provide high level of scalability of IT resources with combined Internet technology to multiple customers [START_REF] Van | SLA-Aware Virtual Resource Management for Cloud Infrastructures[END_REF]. Many definitions of cloud computing have been suggested [START_REF] Armbrust | Above the Clouds: A Berkeley View of Cloud Computing[END_REF][START_REF] Youseff | Toward a Unified Ontology of Cloud Computing[END_REF][START_REF] Foster | Cloud Computing and Grid Computing 360-Degree Compared[END_REF]. Recently, several commercial cloud systems have been developed, such as Amazon EC2 [START_REF]Elastic Compute Cloud (EC2)[END_REF], Go-Grid [START_REF] Gogrid | [END_REF], and FlexiScale [START_REF] Flexiscale | [END_REF]. Open-source cloud computing middlewares such as Eucalyptus [START_REF] Nurmi | The Eucalyptus Open-Source Cloud-Computing System[END_REF], OpenNebula [START_REF]OpenNebula[END_REF], and Nimbus [START_REF] Nimbus | [END_REF] have been also provided in this literature. In the most of these clouds, the concept of an instance unit is used to pro-vide users with resources in a cost-efficient way. An instance means the VM (Virtual Machine) which is suitable for users' requirements. Generally, instances are classified into two types: on-demand instances and spot instances. The on-demand instances have a task execution for compute capacity by the hour with no long-term commitments. This frees users from the costs and complexities of planning, purchasing, and maintaining hardware and transforms what are commonly large fixed costs into much smaller variable costs [START_REF]Elastic Compute Cloud (EC2)[END_REF]. While, the spot instances allow users to bid on unused cloud computing capacity and run those instances for as long as their bid exceeds the current spot price. The spot price changes periodically based on supply and demand, and users whose bids meet or exceed it gain access to the available spot instances. If users have flexibility in when applications can run, spot instances can significantly lower users' costs [START_REF]Elastic Compute Cloud (EC2)[END_REF]. For task completion, therefore, spot instances have lower costs than on-demand instances. However, there is a problem that task failures can be occurred in the use of spot instances with higher cost than user suggested bid.

In this paper, we attempt to find a solution for an efficient checkpointing scheme in unreliable cloud computing environments and propose a price history based checkpointing scheme, by which users can pay the optimal cost based on SLA (Service Level Agreement). In the scheme, SLA management is done by the coordinator. The coordinator supports and manages SLA between users and instances. The failure of instances results in the delay of task completion time, so we design the cost-efficient checkpointing algorithm to solve the failure problem. In our proposed scheme, the checkpoints are taken on two points. One is the checkpoint taken on the rising edge in an execution bid when spot prices are more than a given threshold. The other is the checkpoint taken on the point when failure occurrence time is predicted by average execution time and failure possibility in an execution bid. Moreover, we carry out simulations to demonstrate the effectiveness of our scheme. Simulation results show that our scheme outperforms the existing schemes, such as hour-boundary checkpointing [START_REF] Yi | Taking point decision mechanism for page-level incremental checkpointing based on cost analysis of process execution time[END_REF] and rising edge-driven checkpointing [START_REF] Yi | Reducing Costs of Spot Instances via Checkpointing in the Amazon Elastic Compute Cloud[END_REF], in term of the reduction of both the number of checkpoint trials and total costs per spot instances for user' bid.

The rest of this paper is organized as follows: Section 2 briefly describes related work on checkpoint and SLA in cloud computing. Section 3 presents our system architecture and its components. Section 4 presents our SLA and checkpoint algorithms based on the price history of spot instances. Section 5 presents performance evaluations with simulations. Lastly, Section 6 concludes the paper.

Related Work

The unreliable cloud computing environment (spot instances) is less cost than reliable cloud computing environment (on-demand instances) in task processing environment. However, in unreliable cloud computing, it is difficult to estimate the total execution time of tasks and the total cost to be paid by users. Moreover, since task failures frequently occur according to the supply of instances and the demand of users on instances in unreliable cloud computing, many systems have used the checkpoint mechanisms to minimize task loss and reduce the rollback time of tasks.

In [START_REF] Andrzejak | Decision Model for Cloud Computing under SLA Constraints[END_REF], authors proposed spot instance scheme that users can decide a minimum cost according to an SLA agreement between users and instances in Amazon's EC2. The scheme is based on a probabilistic model for the optimization of cost, performance and reliability and improved the reliability of service by changing dynamically conditions to satisfy user requirements. To improve the reliability of the services, this paper focuses on user costs rather than the point to be taken a checkpoint.

Due to the dynamic nature of the cloud computing, continuous monitoring on Quality of Service (QoS) attributes is necessary to enforce SLAs. In [START_REF] Patel | Service Level Agreement in Cloud Computing[END_REF], authors proposed a mechanism for managing SLAs in cloud computing environment using the Web Service Level Agreement (WSLA) framework developed for SLA monitoring and SLA enforcement in a Service Oriented Architecture (SOA).

In [START_REF] Van | SLA-Aware Virtual Resource Management for Cloud Infrastructures[END_REF], cloud platforms host several independent applications on a shared resource pool with the ability to allocate computing power to applications on per-demand basis. This paper proposed an autonomic resource manager to control the virtualized environment which decouples the provisioning of resources from the dynamic placement of virtual machines. This manager aims to optimize a global utility function which integrates both the degree of SLA fulfillment and computational costs.

In [START_REF] Patel | Service Level Agreement in Cloud Computing[END_REF] and [START_REF] Van | SLA-Aware Virtual Resource Management for Cloud Infrastructures[END_REF], authors focuses on cloud resource management in the reliable cloud computing environment, but this paper focuses on the unreliable cloud computing environment for the resource management applied to the SLA.

[14] introduced spot instances in the Amazon Elastic Compute Cloud (EC2) offer lower resource costs in exchange for reduced reliability. Based on the actual price history of EC2 spot instances, authors compared several adaptive checkpointing schemes in terms of monetary costs and the improvement of job completion time.

In this paper, we propose checkpoint scheme based on SLA to satisfy user requirements. Moreover, we compare our proposed checkpointing scheme with the existing checkpointing schemes (hour boundary checkpointing [START_REF] Yi | Taking point decision mechanism for page-level incremental checkpointing based on cost analysis of process execution time[END_REF] and rising edge checkpointing [START_REF] Yi | Reducing Costs of Spot Instances via Checkpointing in the Amazon Elastic Compute Cloud[END_REF]).

3

System Architecture Fig. 1. Cloud computing environment Fig. 1 shows the cloud computing environment assumed in this paper. This cloud computing environment basically consists of four entities: a cloud server, a storage server, cluster servers, and cloud users. The cloud server is connected to cluster servers and storage servers. The cluster server is composed of a lot of nodes. The cloud users can access the cloud server via the cloud portal to utilize the nodes in the cluster servers as resources. Therefore, the cloud server takes the responsibility of finding virtual resources to satisfy the user's requirements, such as SLA requirements and QoS requirements. The coordinator in the cloud server manages tasks and is responsible for the SLA management. We focus on the coordinator and the VM, which play an important role in our checkpointing scheme.

Layer Structure

Fig. 2. The structure of Coordinator Fig. 2 shows the structure of coordinator in the cloud server that is composed of scheduler, VM Information Manager, History Manager, SLA Manager, QoS Manager and VM Information Collector. In the coordinator, the four managers are responsible for generating and maintaining a list of available VMs, based on the information collected from VM Information Collector. The VM Information Collector collects VM information and provides it for VM information Manager. The VM Information Manager generates a list of CPU utilization, available memory and storage space, network bandwidth, and so on. The History Manager manages the history data, in which the past bid and execution time of spot instances are accumulated. SLA Manager and QoS Manager manage the SLA requirements and the QoS requirements, respectively. When a cloud user requests job execution, the Scheduler allocates the requested job to the selected VM.

Instances types

An instance means the VM that a cloud user uses. The instances are classified into two types: on-demand instances and spot instances. In on-demand instances, users can use VM resources after paying a fixed cost to lend instances per hour. On the other hand, using the spot instances, users can use VM resources only when the price of instances is smaller than other users' bid. The difference between the two instance types is as follows: in on-demand instances, a failure does not occur during task execution, but the cost is comparatively high. On the contrary, the cost of spot instances for task completion is lower than that of on-demand instances. However, task failures are inevitably encountered when there exist the instances with higher price than a user's bid.

Fig. 4. Price history of EC2's spot instances

Amazon allows users to bid on unused EC2 capacity provided as 42 types of spot instances [START_REF]Amazon EC2 spot Instances[END_REF]. Their prices that are called spot prices are changed dynamically based on supply and demand. Fig. 4 shows examples of fluctuations of spot price for c1xlarge (Standard Spot Instances -Extra Large) and m1-xlarge (High-Memory Spot Instances -Extra Large) during 7 days on November 2010 [START_REF]Cloud exchange[END_REF]. Our proposed system model is based on the characteristics of Amazon EC2's spot instances.

 The system provides a spot instance when user's bid is greater than the current price.  The system stops immediately without any notice when user's bid is less than or equal to the current price. We call this an out-if-bid event or a failure.  The system does not charge the latest partial hour when the system stops an instance.  The system charges the latest partial hour when the user terminates an instance.

 The system provides the history of spot price.

4

The SLA based checkpointing scheme

In this section, we propose the SLA (Service Level Agreement) based checkpointing scheme in the spot instances.

SLA based on price history using spot instances

Fig. 5. SLA processing Fig. 5 shows the process of SLA between a user and an instance. A user determines an instance type and the user's bid to begin tasks in the instance. The coordinator calculates a task execution time based on user configurations, such as the user's bid and the instance type. Then, the coordinator sends a request message to the selected instance to investigate the performance of the instance and calculates the expected execution time, the expected failure time and the expected cost. In addition, the coordinator sends a user the expected execution time and cost. When a task is completed in the selected instance, the coordinator receives task results from the instance and sends them to the user. In Fig. 5, the prediction function plays an important role in our SLA processing because it performs the estimation process of the expected failure time, the expected execution time, and the expected cost using price history. The following shows a detailed description for the prediction function.

Fault tolerance mechanisms using checkpoints

In the spot instance environment, a task fails when the cost exceeds the user's bid. Typically, this problem has been solved by using the checkpointing scheme, one of fault tolerance mechanisms [START_REF] Yi | Reducing Costs of Spot Instances via Checkpointing in the Amazon Elastic Compute Cloud[END_REF]. In this section, we explain the existing checkpointing schemes and our proposed checkpointing scheme.

Hour-boundary checkpointing scheme

Rising edge-driven checkpointing scheme

Fig. 8. Rising edge-driven checkpointing Fig. 8 shows the rising edge-driven checkpointing scheme. This scheme takes a checkpoint when the cost is less than user's bid and the cost of spot instances is raised. It will increase the number of checkpoints significantly when cost is frequently fluctuated. The critical problem associated with this scheme is that the rollback time becomes long in case that the rising edge is not appeared in spot price for a long period after a checkpoint is taken. This leads to longer task completion time.

Our proposed checkpointing scheme

Fig. 10. Checkpointing and recovery algorithms

Using these two thresholds, our proposed checkpointing scheme performs checkpoint operations according to two cases: first case is that a checkpoint is performed when there is a rising edge between the user's bid and the price threshold. Second case is based on the failure probability and average execution time of each price. A checkpoint is performed when the time threshold exceeds the execution time of current price. Fig. 10 shows the checkpointing and recovery algorithms used in our proposed scheme. In the algorithms, the flag representing the occurrence of a task failure is initially set to false. The checkpointing process repeats until all tasks are completed. When task execution is normal (i.e., the flag is false), the scheduler performs checkpoint process to provide against job failure (lines 2-20). Recovery process is performed when the flag is true (lines 4-7). Two cases of checkpoints are performed (lines 8-15). If the rising spot price is between user's bid and price threshold, the scheduler performs checkpointing operation (lines 9-11). If the execution time is greater than the time threshold, the scheduler also performs checkpointing operation (lines [START_REF] Andrzejak | Decision Model for Cloud Computing under SLA Constraints[END_REF][START_REF] Patel | Service Level Agreement in Cloud Computing[END_REF][START_REF] Yi | Reducing Costs of Spot Instances via Checkpointing in the Amazon Elastic Compute Cloud[END_REF]. When task failure event occurs, the flag is set to true to invoke the recovery function (lines [START_REF] Yi | Taking point decision mechanism for page-level incremental checkpointing based on cost analysis of process execution time[END_REF][18][19]. Lines 21-24 and 25-28 show a detail process of the checkpointing and recovery, respectively.

Our proposed scheme can reduce checkpointing overhead because the number of checkpoints is less than that of the existing checkpointing schemes (hour-boundary checkpointing and rising edge-driven checkpointing). In our proposed scheme, the two thresholds and expected failure time are calculated based on price history. The thresholds are dynamically changed according to the price behavior of instances in the price history.

Performance Evaluation

In this section, we evaluate the performance of our checkpointing scheme using simulations and compare it with that of the other checkpointing schemes.

Simulation Environments

Our simulations are conducted using the history data obtained from the Amazon EC2's spot instances [START_REF]Cloud exchange[END_REF], which is accumulated during a period from 11-15-2010 to 11-22-2010 as shown in Fig. 4. The history data before 11-18-2010 are used to extract the expected execution time and failure occurrence probability for our checkpointing scheme. The applicability of our checkpointing scheme is tested using the history data after 11-18-2010, which are also used for hour-boundary checkpointing and rising edge-driven checkpointing schemes.

In the simulations, two types of spot instances are applied to show the effect of two different resource types on the performance of three checkpointing schemes; one resource type is a computing-type instance and another type is a memory-type instance. Table 1 shows the resource types used in our simulation. In this table, c1.xlarge offers more compute units than other resources and can be used for compute-intensive applications. On the other hand, m1.xlarge offers much memory capacity than other resources and can be used for high-throughput applications, including database and memory caching applications. Under the simulation environments, we compare the performance of our checkpointing scheme with that of the two checkpointing schemes in terms of the task execution time, the failure time, the number of failures, and the number of checkpoints.

The analysis of computing-type instances

Before analyzing the performance of our checkpointing scheme, we firstly extract parameter values from the spot history presented in Fig. 4(a). Table 2 shows the simulation parameters and values used for the analysis of computing-type instances. We also extract the failure occurrence probability for each price from the spot history (11-15-2010 ~ 11-18-2010) presented in Fig. 4(a). The extracted failure occurrence probability is used to determine the time threshold in our checkpointing scheme. Fig. 11 shows the failure occurrence probability for c1.xlarge instance. In this figure, X and Y-axis mean spot price and failure occurrence probability per spot price for a given user's bid, respectively. From this figure, we can find that our checkpointing scheme achieves performance improvements in an average task execution time of 7.9% over the hour-boundary checkpointing scheme and in an average task execution time of 14.3% over the rising edge-driven checkpointing scheme. We can also find that our scheme reduces the number of checkpoints by average of 17 times over the hour-boundary checkpointing scheme and by average of 18 times over the rising edge-driven checkpointing scheme. boundary checkpointing scheme and by average of $2.42 over the rising edge-driven checkpointing scheme.

The analysis of memory-type instances

Now, we present the performance evaluation of our checkpointing scheme when memory-type instances are used. As the analysis presented in previous subsection, we firstly extract parameter values from the spot history presented in Fig. 4(b). Table 3 shows the simulation parameters and values used for the analysis of memory-type instances. We also extract the failure occurrence probability for each price from the spot history (11-15-2010 ~ 11-18-2010) in Fig. 4(b). Fig. 14 shows the failure occurrence probability for m1.xlarge instance. In this figure, X and Y-axis mean spot price and failure occurrence probability per spot price for a given user's bid, respectively. From this figure, we can find that our checkpointing scheme achieves performance improvements in an average task execution time of 14.35% over the hour-boundary checkpointing scheme and in an average task execution time of 23.83% over the rising edge-driven checkpointing scheme. We can also find that our scheme reduces the number of checkpoints by average of 28 times over the hour-boundary checkpointing scheme and by average of 31 times over the rising edge-driven checkpointing scheme. 16 shows the total costs in each user's bid. From this figure, we can see that our checkpointing scheme reduces the costs by average of $5.15 over the hourboundary checkpointing scheme, and by average of $5.93 over the rising edge-driven checkpointing scheme.

Conclusion

In this paper, we proposed an efficient checkpointing scheme using the price history of spot instances to improve the stability of task processing in unreliable cloud computing environment. Our proposed scheme basically performs checkpointing operation based on two kinds of thresholds, price threshold and time threshold. These two thresholds were extracted from the price history of spot instances and used to determine checkpointing position in cost-efficient way in the presence of the failures of spot instances arisen from price fluctuation. As a result, our scheme can significantly reduce the number of checkpoint trials compared to the existing checkpointing schemes. Furthermore, the rollback time of our scheme can be much lesser than that of the existing checkpointing schemes because our scheme can adaptively perform checkpointing operation according to the time and price of spot instances. Simulation results showed that our scheme can achieve cost efficiency by reducing rollback time per instance for a given user's bid regardless of the resource types of spot instaces. In the future, we have a plan to expand our environment into a combination of spot instances and on-demand instances for various cloud computing services.

Fig. 3 .

 3 Fig. 3. The structure of Virtual Machine

Fig. 6 .

 6 Fig. 6. Extraction of expected execution time from price history

Fig. 7 .

 7 Fig. 7. Hour-boundary checkpointing

Fig. 9 .

 9 Fig. 9. Our proposed checkpointing scheme Fig. 9 illustrates our proposed checkpointing scheme. This scheme basically performs checkpointing operation using two kinds of thresholds, price threshold and time threshold, based on the expected execution time of the price history. Now, let a t and b t denote, respectively, a start point and an end point in the expected execution time. Based on a t and b t , we obtain the price threshold ( PriceTh ) and the time threshold (

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Failure occurrence probability for c1.xlarge instance

Fig. 13 .

 13 Fig. 13. Comparison of total costs in c1.xlarge

Fig. 14 .

 14 Fig. 14. Comparison of fault occurrence probability in m1.xlarge

Fig. 15 .Fig. 16 .

 1516 Fig. 15. Performance comparison of checkpointing schemes in m1.xlarge

Table 1 .

 1 Resource types

	Instance type name	Compute	Virtual	Memory	Storage	Platform
		unit	cores
	c1.xlarge	8 EC2	4core	15GB	1690GB	64-bit
	(computing Instance)		(2 EC2)
	m1.xlarge	6.5 EC2	2core	17.1GB	420GB	64-bit
	(high-memory Instance)		(3.25 EC2)

Table 2 .

 2 Simulation parameters and values for c1.xlarge instance

	Simulation	Task	Max	Average	Min	Checkpoint	Recovery
	parameter	time	Bid	bid	bid	time	time
	Value	259200(s)	0.336($)	0.319($)	0.304($)	300(s)	300(s)

Table 3 .

 3 Simulation value of m1.xlarge instance

	Simulation	Task	Max	Average	Min	Checkpoint	Recovery
	parameter	time	bid	bid	bid	time	time
	Value	259200(s)	0.76($)	0.32($)	0.304($)	300(s)	300(s)

Acknowledgments. This research was supported by Basic Science Research

Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2010-0015637).


Qian Zhou
email: zhouqian@xju.edu.cn

Jiong Yu
email: yujiong@xju.edu.cn

Feiran Yu
email: yufeiran@yahoo.com.cn

A Trust-based Defensive System Model for Cloud Computing

Keywords:

Because of the dynamic and open characteristics of the cloud computing, continuing malicious attacks happen frequently. Combining the idea of trusted cloud, a trust-based defensive system model for cloud computing has been constructed to guarantee the cloud security. Through real-timely monitoring, users' behavior evidences have been obtained and standardized; a new method for users' trust evaluation based on fuzzy AHP (Analytic Hierarchy Process, AHP) has been presented, it gradually determines the weights of behavior evidences, achieves quantitative assessment of behavioral trust; to provide great security defense for users, multiple detection engines have been used to conduct a comprehensive inspection of suspicious files and integrated decisions have been made.

Experimental results show the system model can effectively eliminate the malicious behaviors from undesirable users, reduce users' damages caused by virus and achieve a two-way defense for both cloud and client.

Introduction

In the face of continuing malicious attacks, the simple methods of intrusion detection, virus detection and secure login protocol have been unable to cope with a variety of network attacks and damages, therefore cloud security and trusted cloud [START_REF] Hong | The key technology and realization of trusted cloud security[END_REF] came into being. Cloud security is intended to eliminate existing viruses, trojans and malicious files in the network. Trusted cloud is guaranteed safe from the user terminals; combining the idea of trusted network [START_REF] Chuang | Research on trustworthy networks[END_REF] , it evaluates, forecasts, monitors and manages user behaviors to eliminate malicious attacks to data center from undesirable users and hackers in the cloud to enhance the security of the cloud environment.

In recent years, many scholars began the research of the trust mechanism to make up the defect of traditional security mechanisms that the trust of user behaviors was not considered. Song et al. [START_REF] Song | Fuzzy trust integration for security enforcement in grid computing[END_REF] propose a dynamic trust model based on fuzzy logic under grid environment, this model has better capacities of detecting and defending malicious entities, while the downside is that the convergence of computing and system scalability are poor, it does not consider the calculation of the indirect trust and the trust can not reflect the overall credibility. Power-Trust [START_REF] Zhou Rong-Fang | Power-Trust: A robust and scalable reputation system for trusted Peer-to-Peer computing[END_REF] is a P2P reputation system based on the power law distribution, the system uses power law to collect feedback from local nodes, and gets global reputation through the super-nodes generated from queuing mechanism, significantly improves the accuracy of global reputation and accelerates the rate of polymerization. Jameel introduces vector operation mechanism to establish the trust model [START_REF] Jameel H | A trust model for ubiquitous systems based on vectors of trust values[END_REF] , its most notable feature is the introduction of the trust factor, historical factors and the time factor to reflect dynamic trust relationship, but it can not solve the cheating behaviors when recommending and has no risk analysis. A new trust quantitative model based on multi-dimensional decision-making properties is proposed in paper [START_REF] Xiao-Yong | Trust quantitative model with multiple decision factors in trusted network[END_REF] ; it introduces direct trust, risk function, feedback trust, activation function and physical activity level and other decision-making attributes to assess the complexity and uncertainty of trust relationship from various angles.

Through analyzing and comparing the existing trust models, studying the trusted cloud and reputation technology of the client cloud [START_REF]A white paper of the network defense solutions of Secure Cloud from Trend Micro[END_REF] , in this paper we change traditional ideas of network defense which are for their own business and propose a trust-based defensive system model in the cloud environment. This model has integrated trust and risk evaluation mechanisms and provides maximum security defense to customers in the cloud and the network security and defense functions are provided as services to end customers.

Architecture of Defensive Model

Cooperation between network services, resources, applications provided by cloud computing and customers depends on the trust relationship between them. In this paper, the system model is built by borrowing the idea of trusted network, therefore the network entities' behavioral states can be monitored, behavioral outcomes can be assessed and abnormal behaviors can be controlled [START_REF] Chuang | Research on user behavior trust in trustworthy network[END_REF] .

Physical Structure

The system consists of Cloud Client (CC), File Monitoring and Analyzing center (FMA), Behavior Monitoring center (BM) and Trust Management center (TM) in which CC is a lightweight terminal located in the client and the rest are high-performance large-scale servers in the cloud. Figure 1 shows model's physical structure. TM is consisted of a behavior database, a behavioral trust evaluating module and a trust database.

It stores users' behavioral evidences, evaluates users' trust degree and saves users' overall trust degree.

Logical Structure

To provide security and defensive services for the massive clients, this model is designed to take full advantages of the high computing power and storage power of the cloud computing. At the same time, the system monitors and assesses users' behaviors to eliminate malicious attacks from undesirable users which are in interaction in the cloud to achieve a two-way defensive purpose. Figure 2 shows the flow chart of the model. The system's processing flow is composed by two extensions: 'a' process provides defense for the cloud through evaluating the user's behavior trust and giving the appropriate operating authorities to the user; 'b' process contains detecting and analyzing malicious files uploaded by the end user, establishing the latest and most complete trusted/malicious file database to provide maximum defense for users in the cloud.

Relevant

C i ∩C j =Ф(i≠j), C 1 <C 2 <…<C,
                 1 1 2 1 2 1 0 1 C Tr , Se C Tr C , Se Tr C , Se Tr fs k k  (1)
Where C k etc. are defined by definition 3. When a user requests to the cloud for services, the user will be decided his service level based on his trust level to reduce existing potential risk of the user.

For example, some cloud operator provides 3 levels of services, then Se={Se 1 , Se2, Se3}. Which, Se 1 denote services are denied, Se 2 denote files are read only, Se 3 denote files can be edited. Trust level space is set to C={C 1 , C2}={0.3, 0.6}, the decision-making function for services is So, the decision-making function for suspicious files trust levels is

              3
              1 2 1 2 0 1 V Trp , Malicious V Trp V , Unknown Trp V , Trusted
Trp fp (2) 3 Behavioral Evidences

Obtaining Evidences

User's behavioral evidences (evidences for short) can be obtained directly from the detection of system software and hardware, which are the base values for quantitatively assessing user's overall behaviors [START_REF] Tie-Guo | AHP-based user behavior evaluation method in trustworthy network[END_REF] . Current methods for obtaining evidences are: intrusion detection systems, such as Snort, which can detect worms, vulnerabilities, port scanning and a variety of suspicious behaviors; network traffic detection and analysis tools, such as Bandwidthd, you can view highly detailed IP traffic and network status; professional network data collection tools, such as Flunk's NetFlow Tracker, which can get real-time network bandwidth utilization and bandwidth usage of different users and so on.

Standardizing Evidences

Evidences have many forms: specific values, such as the number of scanning an important port; percentage, such as CPU utilization; binary, such as data integrity (1 if data is complete, 0 if data is incomplete). In order to facilitate numerical calculation and assessment to user behavior, evidences need to be standardized as positive increasing dimensionless values in the interval [0, 1].

Let A= (a ij ) m×n denote initial evidences matrix and we normalize A to evidences matrix E=(e ij ) m×n , the rules are: ① Evidences of percentage and binary forms are already in [0,1] and they are translated into positive increasing values using equation ( 3)

     g sin decrea positive is a when , a g sin increa positive is a when , a e ij ij ij ij ij 1 (3)
② Evidences of specific values are normalized into positive increasing values in [0,1] using equation ( 4)

                        g sin decrea positive is a when , a a a a g sin increa positive is a when , a a a a e ij min ij max ij ij max ij ij min ij max ij min ij ij ij (4)
Where, (a ij ) min and (a ij ) max respectively express the minimum and maximum evidence.

Evaluation Model based on FAHP

AHP (Analytic Hierarchy Process) is a system analysis method combining qualitative and quantitative analysis [START_REF] Lian-Fen | The introduction of AHP[END_REF] . The traditional AHP has following shortcomings [START_REF] Lei | Evaluation method of service-level network security situation based on fuzzy analytic hierarchy process[END_REF] : it uses nine scales to construct judgment matrix and this is too complex in practice; it needs to judge and build matrix continuously until the matrix meets consistency verification with large calculation and low precision.

In order to overcome the problems in AHP, this paper uses fuzzy analytic hierarchy process (Fuzzy AHP). FAHP uses three scales to construct a judgment matrix to facilitate decision-makers easily decide in two factors which is relatively important; and the initial judgment matrix is transformed into the fuzzy consistent matrix that satisfies the consistency condition without consistency test.

A Hierarchical Structure of Evidences

Evidences are divided into several trust properties gradually by layer, and then broken down into specific evidences' types, which can effectively resolve the general and uncertain problems of user's behavioral trust under cloud computing. A hierarchical structure of evidences is shown in Figure 3.

  m m ij ep EP                        j c i c , j c i c , j c i c , . ep ij 0 1 5 0 (5)
Where, c(i)=c(j)) express evidence ep i is equally important as ep j ; c(i)>c(j) express evidence ep i is important than ep j ; c(i)<c(j) express evidence ep i is less important than ep j .

(2) Steps of sum and transformation of line are used to convert the initial judgment matrix EP=(ep ij ) m×m to the fuzzy consistent matrix Q=(q ij ) m×m without consistency verification.

5 0. a q q q j i ij    (6)            m k ik i m a ; m , , , i , ep q 1 2 2 1 
(3) When conducting sum of line for the fuzzy consistent matrix Q, self-comparison (i.e., diagonal element) is not contained. The weight vector W= (w 1 ,w 2 …w m ) T is Calculated using equation ( 7)

  i i i i l l w (7)
Where, l i denote evidence p i 's importance relative to the upper performance character

     m k ik i m . , , i , . q l 1 2 1 5 0  (8)      i i m m l 2 1 (9)

The assessment of user behavior character

Suppose user behavior contains n items of features, and k denote the largest item value of the feature (if the item number does not reach k, the corresponding elements are 0); we use Section 3.

The overall trust evaluation of user behavior

Set the user feature vector is F=(f 1 ,f 2 ,…,f n ) T , the weight vector of the features is W f T =(w 1 ,w 2 ,…,w n ) T , user's overall trust degree Tr is calculated using equation ( 11)

       n i i i T f w f W F Tr 1 1 1 (11)

Evaluation Model for Suspicious Files

Suspicious files may be user's normal files, original virus files, files infected by virus, files corrupted by virus, malicious software and so on. In order to reduce the losses caused by viruses and malicious software, we use multi -engine detection mechanism and dynamic behavior analysis to test comprehensively the suspicious files uploaded by the user.

Multi-engine detection mechanism

As a single engine can not conduct a comprehensive inspection to suspicious files, file detection engine in File Monitoring and Analysis center (FMA) then uses multi-engine detection mechanism.

(1) Suppose we use n kinds of detection engines denoted as Eg={Eg 1 ,Eg 2 ,…,Eg n } and the accuracy of the engines is Per={Per 1 ,Per 2 ,…,Per n }.

(2) Using n kinds engines to test a single suspicious file, we can get n kinds detection results R= {R 1 , R 2 , …R n } (R i ∈{0,1}, 0 indicates that no virus is found, 1 indicates virus is found) . Integrated trust property value Trp of the suspicious file is calculated using equation ( 12)

n R Per Trp n i i i      1 1 (12)
(3) According to equation ( 2), the file's trust level can be determined. When the file is Trusted or Malicious, FMA will directly return the results to the user for the final decision.

Dynamic behavior analysis of suspicious files

When the file's trust level is Unknown, FMA will hand the file to the file behavior analyzing engine, which is consisted of feature database of malicious files and the virtual machine. The Unknown file will be run in the virtual machine for real-timely dynamic analysis of behaviors.

Experimental simulation and description

Experimental environment consists of 3 servers, 1 router and 6 clients. We use C#.Net to realize the certification and authorization module, the behavioral evidence standardizing module, the file detection engines and the behavioral trust evaluating module; suspicious files are run in VMware workstation and analyzed dynamically; kinds of services under the experimental environment are monitored continuously by NetFlow Tracker and the test scenario is a small cloud storage system.

(

) 1

Files

Trust level Malicious Unknown Trusted

(2) When a user is in the process of interaction with the cloud, BM continuously monitors the user and puts his behavioral evidences into the behavior database, the trust evaluating module assesses the trust degree of the user to identify and predict the possible unforeseen circumstances and real-timely informs the certification and authorization module to revise to the service level of the user.

(3) This system uses multiple detection engines and their accuracy Per are shown in the following [START_REF]A test report of anti-virus softwares[END_REF] : GData(Per=99.9%)、 AntiVir(Per=99.8 %)、 AVAST (Per=99.3%)、 Norman(Per=96.6%)、 Trend Micro(Per=90.3%)、Kingsoft(Per=80.1%).

Example of trust evaluation

12 kinds of evidences (see evidence level in Figure 3) in a half-hour from a client are obtained by Behavior Monitoring center. Through Section 3.2, evidences are normalized and convert to average evidence values that are shown in Table 2.

Q

The weight vector of evidences relevant to the performance character can be calculated by equation ( 7 According to Section 6.1 we can see, this user has high credibility level that can edit and download files in the small cloud storage system.

Experimental Comparison

Experiment 1: The experimental comparison result of two different trust evaluation mechanisms respectively based on FAHP and AHP Figure 4 shows the following circumstance: In the interaction between the client and the cloud, when we gradually increase the proportion of malicious acts such as illegal connections and scanning important port, the changes of the overall trust degree. With increase in the proportion of malicious behaviors, trust value calculated by mechanism based on FAHP has a large decline compared to that of AHP and is more compatible with human reasoning. Combined with the settings in Section 6.1, we find that user with low credibility can be monitored out by FAHP earlier and faster than AHP, which is conducive for certification and authorization module to update the client's service level and reduce the risk of the cloud. Experiments were carried out for the following three cases: 1) case is using multi-engines detection mechanism proposed in this paper to conduct a comprehensive inspection to suspicious files and determine their trust level; 2), 3) are using different single-engine to test, as a reference for the first case. Test results of suspicious files are shown in Table 3. From Table 3, we can see that even for the same suspicious files, test results show great difference because of different detection engine (AntiVir and AVAST), so Trusted file could be mistaken for the Malicious one, thereby the client may be affected to make final decisions to suspicious files. Our system is based on multi-engines detection mechanism and conducts the integrated decision-making to test results, which can effectively avoid the above situations.

Performance Comparison

Using AHP to determine the weight of evidence, consistency test is needed. Because AHP uses nine scales to conduct the judgment matrix, excessive subjective judgments can easily bring deviation so that the matrix does not meet the consistency condition. At this point, the matrix need to be adjusted by number of experts' re-determine and a series of iterative computing, as the evidence layer is larger and the order of judgment matrix is higher, which means a large computing and communication overhead. In this paper, the experiment found that the average adjusted time is 3 when conducting the judgment matrix that meet the consistency condition using AHP method.

Without iterative calculation, FAHP method used in this paper can construct the fuzzy consistent matrix that meets the consistency condition just one-off. Therefore, under the same computation and communication, the computing time of our model can be shortened 1/3, so user's trust level and authorities can be judged faster. Therefore, the complex and time cost is greatly reduced.

Conclusion

Due to the severe security problems that cloud computing faces, combining the idea of trusted cloud, this paper presents a defensive system model based on trust. Taking the diversity of users' behavioral evidences into account, in order to conduct a more scientific and accurate trust evaluation, our system introduces FAHP to achieve the quantitative assessment of behavioral trust; considering the huge losses caused by viruses to the user, this system model uses multiple detection engines to conduct a comprehensive inspection of suspicious files. Experiments show that our model can not only effectively monitor and assess users' behaviors, but also provide users with security and protection services to achieve a two-way defense.

Fig. 1 .

 1 Fig.1. Physical structure of the defensive system CC is responsible for submitting samples of suspicious files and executes the final decision. FMA is composed of file detecting engines and file behavior analyzing engine. Using virtualization technology and multi-engine detection mechanism, FMA takes a full inspection to the uploaded suspicious files and returns the test results to the customer.BM is consisted of a behavioral evidence obtaining module and a standardizing module. It monitors customers' behaviors continuously, obtains and standardizes users' behavioral evidences.

Fig. 2 .

 2 Fig.2. Flowchart of the defensive system The system flow can be divided into the following steps: 1) When a user login to the cloud, the cloud's certification and authorization module queries Trust Management center to give the user a trust level and the corresponding operating authorities; 2)a The user is monitored by Behavior Monitoring center continuously and behavioral evidence obtaining module gets the user's behavioral evidences; 3)a Evidences obtained from the user will be standardized by Behavioral standardizing module; 4)a Behavior Monitoring center dumps standardized behavioral evidences to the behavior trust database in Trust Management center; 5)a Trust evaluation module uses the data in the behavior database to evaluate the user's trust value; 6)a Trust evaluation module sends the user's trust value to the trust database; 7)a In the basis of the user's trust value, the certification and authorization module authorizes real-time permission to the user; 2)b Suspicious file samples are submitted to File Monitoring and Analyzing center through Cloud Client by the client; 3)b Suspicious files that are unable to be determined by file detecting engines are submitted to file analyzing engine for real-timely dynamic behavioral analysis; 4)b The final decisive results of the suspicious files are returned to the client by Files Monitoring and Analysis center and the final decision is taken by the user.

Description Definition 1 .Definition 2 .

 12 Suppose there are m measure items for measuring users trust degree, let E={E 1 , E 2 , …, E m } denote m kinds of behavioral evidence and the measured values are expressed as I={I 1 , I 2 , …, I m }. Let w i (1≤i≤m) represents the importance of the ith piece of evidence relative to the other evidences, and meet Let Tr denote the overall trust degree of the user evaluated by the cloud, denoted as Overall Trust Degree (OTD) and OTD is the basis for the user to get authorities during the interaction with the cloud. Definition 3. Suppose set C is the behavior trust classification space, denoted as C={C 1 , C 2 ,…,C p }, respectively represents p+1 trust levels for Tr, where 0<C p <1 and 1≤p≤m. C has following properties:

  and C k+1 is stronger than C k , then we say C is an ordered partition class. Definition 4. Suppose the cloud provides k levels of services denoted Se={Se 1 , Se 2 ,…, Se k }, Se is an ordered partition class, and the mapping function between Se and Tr is

  0.7, then the decision-making process is fs (Tr) =f (0.7) =Se 3 = file can be edited. Definition 5. Let Trp(0≤Trp≤1) denote the trust properties of the suspicious files after being detected by the cloud; suspicious files trust level space is denoted by V={V 1 ,V 2 }, and V 1 <V 2 ∈(0, 1).

Fig. 3 .

 3 Fig.3. Hierarchical structure of user's behavioral evidences

  2 to get standardized evidence matrix E=(e ij ) m×n , e ij ∈[0,1] represents the j th evidence of the i th character and its weight is w ij ∈[0,1]. Matrix diagonal values calculated by equation(10) are the assessment values of user character.

  matrix is converted from EP by equation (6):

  )~(9): W P T ={0.161,0.107,0.071,0.161,0.071,0.161,0.161,0.107} T . Through pairwise comparison, the importance of evidences relevant to security character is [c(S 3 )=c(S 2 )]>c(S 1 )>c(S 4 ), similarly, the results of their weight vector is: W S T = {0.208, 0.333, 0.333, 0.125} T . The importance of user behavior character is c(P)<c(S), then the weight vector of the characters is W f T ={0.25, 0.75} T . According to equation (10), the assessed values of user behavioral characters are F=E × W T =(0.656,0.222) T , then the evaluated value of user behaviors is calculated by equation (11): Tr=0.67.

Fig. 4 .

 4 Fig.4. Changes of a client's trust value When using FAHP to construct the initial judgment matrix, because of the subjectivity of decision makers, determination of each element should be comprehensively evaluated by a number of experts. Also, the environment of the client should be considered when constructing a judgment matrix, if the client is in an unsafe environment (such as Internet cafes), the security character is important than performance character. Thus for the same client, even if evidences obtained are the same, the judgment matrix would be different under different environment, so do the assessed values of their behaviors. Experiment 2: The comparison result of suspicious files detection based on multi-engines and single engine 100 suspicious files are uploaded to the cloud and comprehensively detected by FMA.

  According to Section 2.3 Definition. 3, the user trust level is set C={0.3, 0.6}; user is authorized according to Definition. 4, this small cloud storage system provides three levels of service Se={Se 1 ,Se 2 ,Se 3 } (Se 1 denote services are denied, Se 2 denote files are read only, Se 3 denote files can be edited and download); according to Definition. 5, suspicious files trust level is set V={0.4, 0.5}.Parameter settings are shown in Table1.

		Table 1. Parameter Settings
		OTD: Tr	[0,0.3)	[0.3,0.6)	[0.6,1)
	User	Trust level	Low	Normal	High
		Service level	S1	S2	S3
		Trp	[0,0.

Table 2 .

 2 The average evidence values in a half-hour of a client they are of equal importance, therefore [c(P 1 )=c(P 4 )=c(P 6 )=c(P 7 )]>[c(P 2 )=c(P 8 )]> [c(P 3 )=c(P 5 )]. Construction of the Initial judgment matrix is constructed by equation(5)

			Performance Character (P)
	P1	P2	P3	P4	P5	P6	P7	P8
	0.62 0.51 0.88 0.83 0.74 0.67 0.73 0.54
	Security Character (S)
	S1	S2	S3	S4
	0.33 0.28 0.15 0.08

We use Section 3.2 to determine the weight of performance and security characters respectively and take per-formance character for instance: Experience has shown that response time of IP packet, IP transmission rate, throughput and bandwidth share are the best reflection to user's performance character and

Table 3 .

 3 Test results of suspicious files

		Trusted Unknown Malicious
	Multi-engines	70.8%	4.2%	25%
	Single-engine (AntiVir)	16.7%	0	83.3%
	Single-engine (AVAST)	76%	0	24%