Search

The problem of constructing independent spanning trees (ISTs) dates back to as early as late 1980s. Given a network G of a certain topology, the question is whether we can, as well as how to, construct a set of independent spanning trees in G . ISTs have proven to be of great importance in many network tasks. The past decade has seen a particularly remarkable increase in the literature on ISTs, manifesting a significant growth of interest. ISTs can be classified into edge-independent spanning trees (edge-ISTs), node-independent spanning trees (node-ISTs), and completely independent spanning trees (CISTs). For a network G , node-ISTs (edge-ISTs) rooted at u are a set of spanning trees rooted at u in G such that there are no common internal nodes (edges) between u and any other node among the paths in these spanning trees. If every node in a set of node-ISTs can act as a root node, the set of trees are called CISTs. This survey aims at bringing together important works on ISTs that have been reported in the literature. It provides a historical perspective of how the field has evolved, and can serve as an integrated useful resource of references for future research on ISTs.

Network representation learning (NRL) advances the conventional graph mining of social networks, knowledge graphs, and complex biomedical and physics information networks. Over dozens of network representation learning algorithms have been reported in the literature. Most of them focus on learning node embeddings for homogeneous networks, but they differ in the specific encoding schemes and specific types of node semantics captured and used for learning node embedding. This survey paper reviews the design principles and the different node embedding techniques for network representation learning over homogeneous networks. To facilitate the comparison of different node embedding algorithms, we introduce a unified reference framework to divide and generalize the node embedding learning process on a given network into preprocessing steps, node feature extraction steps and node embedding model training for a NRL task such as link prediction and node clustering. With this unifying reference framework, we highlight the representative methods, models, and techniques used at different stages of the node embedding model learning process. This survey not only helps researchers and practitioners to gain an in-depth understanding of different network representation learning techniques but also provides practical guidelines for designing and developing the next generation of network representation learning algorithms and systems.

For the sake of achieving higher reliability, conditional connectivity has gradually become well-known. Component connectivity, as a kind of conditional connectivity, is an extension of the classical connectivity. Given a simple and undirected graph G and a nonnegative integer r, the ( r + 1 ) -component connectivity of graph G, say c κ r + 1 ( G ) , is the minimum number of a vertex cut whose removal causes the surviving graph to have at least r + 1 components. Another basic parameter of reliability, diagnosability is often related to the number of components in the surviving graph. The ( r + 1 ) -component diagnosability, say c t r + 1 ( G ) , is the maximum size of fault sets subject to at least r + 1 components in the surviving graph, provided that all faulty vertices can be detected. A graph is t / k -diagnosable if all faulty vertices can be isolated into a set in which up to k vertices are fault-free, provided that the number of faulty vertices is at most t. As a two-level interconnection network, the hierarchical folded cubic network H F Q ( n ) possesses a great deal of nice properties. In this paper, we first show that the n-dimensional hierarchical folded cubic network is tightly super connected. Then, we explore that c κ r + 1 ( H F Q ( n ) ) = r ( n + 1 ) − ( r 2 ) + 1 ( n ≥ 4 , 1 ≤ r ≤ n − 4 ) , and obtain that c t r + 1 ( H F Q ( n ) ) = ( r + 1 ) n − ( r 2 ) + 2 ( n ≥ 4 , 1 ≤ r ≤ n − 4 ) under the PMC and MM* models. Last, we show that the hierarchical folded cubic network H F Q ( n ) is [ ( k + 1 ) n − ( k 2 ) + 2 ] / k -diagnosable, where n ≥ 4 and 1 ≤ k ≤ n − 4 .

Hypercubes are popular topologies of massive multiprocessor systems due to their super properties. Cross-cubes are significant variations of hypercubes and they have smaller diameters and higher fault-tolerant capability than hypercubes at the same dimensions. In this paper, we construct node-to-set disjoint paths of an n-dimensional cross-cube, $$C_{n}$$ , whose maximum length is limited by $$2n-3$$ . Furthermore, we propose an $$O(N \text {log}^{2}N)$$ algorithm with a view to finding node-to-set disjoint paths of $$C_{n}$$ , where N is the node number of $$C_n$$ . And we also present the simulation results for the maximal length of disjoint paths obtained by our algorithm.

In order to satisfy the rapidly increasing demand for data volume, large data center networks (DCNs) have been proposed. In 2019, Zhang et al. proposed a new highly scalable DCN architecture named HSDC (Highly Scalable Data Center Network), which can achieve greater incremental scalability. In this paper, we give the definition of the logical graph of HSDC, named $$H_n$$ , which can be treated as a compound graph of hypercube and complete graph of the same dimension. First, we prove that the connectivity and tightly super connectivity of $$H_n$$ are both n. Then, we give an O(n) shortest unicast algorithm to find a shortest path between any two distinct nodes in $$H_n$$ , and prove the correctness of this algorithm. In fact, we also prove that the length of the shortest path constructed by this algorithm is no more than $$2d+1$$ if $$d

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQn is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n ≢ 3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQn. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQn is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in A Q n ( 00...0 ︸ n−k )(n≥k≥4) by proposing an ingenious way of construction and propose a corresponding O(NlogN) time algorithm, where N = 2k is the number of nodes in A Q n ( 00...0 ︸ n−k ) .

With the development of scalability and application of multiprocessor system, the components of the system possibly become faulty. It is desirable to know the reliability of the system. However, the exact reliability of a complicated network system is usually difficult to determine. A typical approach is to decompose the system into smaller ones based on a graph-theory model in which nodes are assumed to fail independently with known probabilities to measure the subsystem-based reliability, which is defined as the probability that a fault-free subsystem of a specific size is still available when the system has faults. In this paper, we use the probability fault model to establish upper and lower bounds on the subsystem-based reliability of k-ary n-cube networks, by taking into account the intersection of no more than five or four subgraphs. In addition, some numerical simulations of the subsystem-based reliability of k-ary n-cube networks are conducted.

BCube is one kind of important data center networks. Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks. So far, there have been many results concerning fault-tolerant Hamiltonicity and fault-tolerant Hamiltonian connectivity in some data center networks. However, these results only consider faulty edges and faulty servers. In this paper, we study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity of BCube(n, k) under considering faulty servers, faulty links/edges, and faulty switches. For any integers n ≥ 2 and k ≥ 0, let BCn,k be the logic structure of BCube(n, k) and F be the union of faulty elements of BCn,k. Let fv, fe, and fs be the number of faulty servers, faulty edges, and faulty switches of BCube(n, k), respectively. We show that BCn,k − F is fault-tolerant Hamiltonian if fv +fe + (n − 1)fs ≤ (n − 1)(k + 1) − 2 and BCn,k −F is fault-tolerant Hamiltonian-connected if fv + fe + (n − 1)fs ≤ (n − 1)(k + 1) − 3. To the best of our knowledge, this paper is the first work which takes faulty switches into account to study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity in data center networks.

Reliability assessment of interconnection networks is critical to the design of multiprocessor systems. Extra connectivity and extra diagnosability are two important metric parameters for the reliability evaluation of interconnection networks. In this paper, we first establish that the i-extra connectivities of regular networks with some conditions G n are ( i + 1 ) n − 2 i for i = 1 , 2 , where n ≥4, and then determine that the i-extra diagnosabilities of the networks under the PMC model and the MM* model are ( i + 1 ) n − i for i = 1 , 2 , where n ≥4. Furthermore, two polynomial time diagnostic algorithms of regular interconnection networks under the PMC and MM* model are described. Finally, the corresponding extra connectivities and extra diagnosabilities of some networks, including the star networks, the pancake networks and the burnt pancake networks, can be derived by our results.

Fault tolerance and reliability are the crucial issues for data center networks (DCNs). Both the g-extra conditional diagnosis (g-ECD) precise strategy and the t / k -diagnosis imprecise strategy play essential role in the reliability of networks. For the data center network based on DCell structure D m , n , we prove that: 1) the g-ECD of D m , n under the MM⁎ model is ( g + 1 ) m + n − 1 with n ≥ 4 , m ≥ 3 , and 1 ≤ g ≤ min ⁡ { n 4 , m − 2 } ; 2) D m , n is [ ( k + 1 ) ( m − 1 ) + n ] / k -diagnosable under the MM⁎ model with n ≥ 2 , m ≥ 2 , and 0 ≤ k ≤ n − 1 . Furthermore, for N-server DCN, we propose the first t / k -diagnosis algorithm on D m , n under the MM⁎ model, namely t / k - D m , n -DIAG with O ( N log N ) time complexity. Comparing with the traditional t-diagnosable algorithm by Ziwich and Duarte (2016) [11] , on D m , n , the t / k - D m , n -DIAG can identify the number of faulty vertices is almost k times larger than the t-diagnosable algorithm, where the time complexity of t-diagnosable algorithm is about O ( N ( log N ) 3 ) . These results provide a quantitative analysis for the reliability and availability evaluation of a large-scale DCN.

Due to the application in reliable communication, reliable broadcasting, secure message distribution, etc., node/edge-independent spanning trees (ISTs) have attracted much attention in the past twenty years. However, node/edge conjecture is still open for networks with node/edge-connectivity ≥ 5. So far, results have been obtained on a lot of special networks, but only a few results are reported on the line graphs of them. Hypercubes play important roles in parallel computing systems, and the line graphs of which have been recently adopted for the architectures of data center networks. Since the line graph of n -dimensional hypercube Q n , L ( Q n ) , is ( 2 n − 2 ) -regular, whether there exist 2 n − 2 node-ISTs rooted at any node on L ( Q n ) is an open question. In this paper, we focus on the problem of constructing node-ISTs on L ( Q n ) . Firstly, we point out that L ( Q n ) can be partitioned into 2 n − 1 complete graphs. Then, based on the complete graphs and n − 1 node-ISTs rooted at 0 on Q n − 1 0 , we obtain an “independent forest” containing 2 n − 2 trees on L ( Q n ) . Furthermore, we present an O ( N ) time algorithm to construct 2 n − 2 node-ISTs rooted at node [0, 2 n − 1 ] isomorphic to each other on L ( Q n ) based on the independent forest, where N = n × 2 n − 1 is the number of nodes on L ( Q n ) . In addition, we point out that the 2 n − 2 node-ISTs on L ( Q n ) is a new method to prove the node/edge-connectivity and the upper bound of ( 2 n − 2 ) -node/edge-wide-diameter of L ( Q n ) .

Connectivity and diagnosability are two important metrics in evaluating the fault tolerability of a network. The g-extra connectivity and the g-extra conditional diagnosability are both defined under the restraint that every component of the network removing a faulty vertex set has at least g + 1 fault-free vertices. The t / k -diagnosability is an outstanding diagnosis strategy, in which the identified faulty vertex set is allowed to contain at most k fault-free vertices. As a well-known model for a large-scale data center network (DCN) with a server-centric structure, the m-dimensional DCell with n-port switches and t m , n servers, D m , n , has many desirable properties. In this paper, we first investigate the g-extra connectivity of D m , n for 0 ≤ g ≤ n − 1 . Based on this, we establish the g-extra conditional diagnosability of D m , n under the PMC model for 0 ≤ g ≤ n − 1 . Finally, we evaluate the t / k -diagnosability of D m , n under the PMC model for 1 ≤ k ≤ n − 1 .

The 3-ary n-cube, denoted as $$ {Q}_n^3 $$ , is an important interconnection network topology proposed for parallel computers, owing to its many desirable properties such as regular and symmetrical structure, and strong scalability, among others. In this paper, we first obtain an exact formula for the minimum wirelength to embed $$ {Q}_n^3 $$ into grids. We then propose a load balancing algorithm for embedding $$ {Q}_n^3 $$ into a square grid with minimum dilation and congestion. Finally, we derive an O(N2) algorithm for embedding $$ {Q}_n^3 $$ into a gird with balanced communication, where N is the number of nodes in $$ {Q}_n^3 $$ . Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.

As users increasingly befriend others and interact online via their social media accounts, online social networks (OSNs) are expanding rapidly. Confronted with the big data generated by users, it is imperative that data storage be distributed, scalable, and cost-efficient. Yet one of the most significant challenges about this topic is determining how to minimize the cost without deteriorating system performance. Although many storage systems use the distributed key value store, it cannot be directly applied to OSN storage systems. And because users’ data are highly correlated, hash storage leads to frequent inter-server communications, and the high inter-server traffic costs decrease the OSN storage system’s scalability. Previous studies proposed conducting network partitioning and data replication based on social graphs. However, data replication increases storage costs and impacts traffic costs. Here, we consider how to minimize costs from the perspective of data storage, by combining partitioning and replication. Our cost-efficient data storage approach supports scalable OSN storage systems. The proposed approach co-locates frequently interactive users together by conducting partitioning and replication simultaneously while meeting load-balancing constraints. Extensive experiments are undertaken on two realworld traces, and the results show that our approach achieves lower cost compared with state-of-the-art approaches. Thus we conclude that our approach enables economic and scalable OSN data storage.

The foundation of information society is computer interconnection network, and the key of information exchange is communication algorithm. Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols. Nowadays, people can build complex interconnection networks by using very large scale integration (VLSI) technology. Locally exchanged twisted cubes, denoted by (s + t + 1)-dimensional LeTQs,t, which combines the merits of the exchanged hypercube and the locally twisted cube. It has been proved that the LeTQs,t has many excellent properties for interconnection networks, such as fewer edges, lower overhead and smaller diameter. Embeddability is an important indicator to measure the performance of interconnection networks. We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQs,t − (fv + fe), with faulty vertices fv and faulty edges fe. Firstly, we prove that an LeTQs,t can tolerate up to s − 1 faulty vertices and edges when embedding a Hamiltonian cycle, for s ⩾ 2, t ⩾ 3, and s ⩽ t. Furthermore, we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQs,t with up to (s − 2) faulty vertices and edges. That is, we show that LeTQs,t is (s − 1)-Hamiltonian and (s − 2)-Hamiltonian-connected. The results are proved to be optimal in this paper with at most (s − 1)-fault-tolerant Hamiltonicity and (s − 2) fault-tolerant Hamiltonian connectivity of LeTQs,t.

The k -ary n -cube is one of the most attractive interconnection networks for parallel and distributed computing system. In this paper, we investigate hamiltonian cycle and path embeddings in 3-ary n -cubes Q n 3 based on K 1 , 3 -structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph K 1 , 3 . We show that for two arbitrary distinct healthy nodes of a faulty Q n 3 , there exists a fault-free hamiltonian path connecting these two nodes if the number of faulty element is at most n − 2 and each faulty element is isomorphic to any connected subgraph of K 1 , 3 . We also show that there exists a fault-free hamiltonian cycle if the number of faulty element is at most n − 1 and each faulty element is isomorphic to any connected subgraph of K 1 , 3 . Then, we provide the simulation experiment to find a hamiltonian cycle and a hamiltonian path in structure faulty 3-ary n -cubes and verify the theoretical results. These results mean that the 3-ary n -cube Q n 3 can tolerate up to 4 ( n − 2 ) faulty nodes such that Q n 3 − V ( F ) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Q n 3 .

Graph embedding is an important technology in simulating parallel structures and designing VLSI layout. Hypercube is one of the most significant interconnection networks in parallel computing systems. The exchanged hypercube is an important variant of the hypercube, which is obtained by systematically deleting edges from a hypercube. It not only retains several valuable and desirable properties of the hypercube, but also has lower hardware cost. In this paper, we first give an exact formula of minimum wirelength of exchanged hypercube layout into a grid. Furthermore, we propose an O(N) algorithm for embedding exchanged hypercube into a gird with load 1, expansion 1 and minimum wirelength and derive a linear layout of exchanged hypercube with minimum number of tracks and efficient layout areas. Finally, we present simulation experiments of our embedding algorithm on network overhead and total wirelength, which conduce to estimate the total wirelength and chip area.

With the wide application of cloud computing, the scale of cloud data center network is growing. The virtual machine (VM) live migration technology is becoming more crucial in cloud data centers for the purpose of load balance, and efficient utilization of resources. The lightweight virtualization technique has made virtual machines more portable, efficient and easier to management. Different from virtual machines, containers bring more lightweight, more flexible and more intensive service capabilities to the cloud. Researches on container migration is still in its infancy, especially live migration is still very immature. In this paper, we present the locality live migration model where we take into account the distance, available bandwidth and costs between containers. Furthermore, we conduct comprehensive experiments on a cluster. Extensive simulation results show that the proposed method improves the utilization of resources of servers, and also improves the balance of all kinds of resources on the physical machine.

Globally distributed data centers provide an opportunity to deploy geo-distributed Online Social Networks (OSNs). For so big data generated by users, how to store them among those data centers is a key issue in the geo-distributed storage system. Today's popular OSN providers store users’ data in each deployed data center, so as to guarantee access latency. However, the full replication manner brings relatively high storage cost and traffic cost, which extremely increases the economic expenditure of OSN providers. Data placement based on social graph partitioning is an efficient way to minimize cost, but it requires the information of entire social graph and cannot fully guarantee latency. Recently, accomplished by partitioning replication is proposed to optimize cost as well as guarantee latency, but it has two drawbacks: (1) the separated manners of optimization cannot efficiently reduce the cost; (2) the placement of master replicas and slave replicas influence each other, and eventually reduces the optimization effects. In this paper, we explore an integrated manner of optimizing partitioning and replication simultaneously without distinguishing replica's role. We propose a lightweight replica placement (LRP) scheme, which conducts optimizations in a distributed manner and is well adapted to dynamic scenarios. Evaluations with two datasets from Twitter and Facebook show that LRP significantly reduces the cost compared with state-of-the-art schemes.

The capability of the data center network largely decides the performance of cloud computing. However, the number of servers in the data center network becomes increasingly huge, because of the continuous growth of the application requirements. The performance improvement of cloud computing faces great challenges of how to connect a large number of servers in building a data center network with promising performance. Traditional tree-based data center networks have issues of bandwidth bottleneck, failure of single switch, etc. Recently proposed data center networks such as DCell, FiConn, and BCube, have larger bandwidth and better fault-tolerance with respect to traditional tree-based data center networks. Nonetheless, for DCell and FiConn, the fault-tolerant length of path between servers increases in case of failure of switches; BCube requires higher performance in switches when its scale is enlarged. Based on the above considerations, we propose a new server-centric data center network, called BCDC, based on crossed cube with excellent performance. Then, we study the connectivity of BCDC networks. Furthermore, we propose communication algorithms and fault-tolerant routing algorithm of BCDC networks. Moreover, we analyze the performance and time complexities of the proposed algorithms in BCDC networks. Our research will provide the basis for design and implementation of a new family of data center networks.

The WK-recursive network has received much attention due to its many favorable properties such as small diameter, large connectivity, and high degree of scalability and expandability. In this paper, we consider the super spanning connectivity properties of the WK-recursive network. We use K ( d , t ) to denote the WK-recursive network of level t, each of which basic modules is a d-vertex complete graph, where d > 1 and t ≥ 1 . We prove that for any two distinct vertices μ and ν, there exist m node disjoint paths whose union covers all the vertices of K ( d , t ) for d ≥ 4 , t ≥ 1 and 1 ≤ m ≤ d − 1 . Since the connectivity of K ( d , t ) is d − 1 , the result is optimal in the worst case.

Edge-independent spanning trees (EISTs) have important applications in networks such as reliable communication protocols, one-to-all broadcasting, and secure message distribution, thus their designs in several classes of networks have been widely investigated. The n-dimensional augmented cube (AQn) is an important variant of the n-dimensional hypercube. It is (2n1)-regular, (2n1)-connected (n3), vertex-symmetric and has diameter of n/2. In this paper, by proposing an O(NlogN) algorithm that constructs 2n1 EISTs in AQn, where N is the number of nodes in AQn, we solve the EISTs problem for this class of graphs. Since AQn is (2n1)-regular, the result is optimal with respect to the number of EISTs constructed.

The complete binary tree is an important network structure for parallel and distributed computing, which has many nice properties and is often used to be embedded into other interconnection architectures. The locally twisted cube L T Q n is an important variant of the hypercube Q n . It has many better properties than Q n with the same number of edges and vertices. The main results obtained in this paper are: (1) The complete binary tree C B T n rooted at an arbitrary vertex of L T Q n can be embedded with dilation 2 and congestion 1 into L T Q n . (2) When there exists only one faulty node in L T Q n , both the dilation and congestion will become 2 after reconfiguring C B T n . (3) When there exist two faulty nodes in L T Q n , then both the dilation and congestion will become 3 after reconfiguring C B T n . (4) For any faulty set F of L T Q n with 2 < | F | ź 2 n - 1 , both the dilation and congestion will become 3 after reconfiguring C B T n under certain constraints. We prove that the complete binary tree can be embedded with dilation 2, congestion 1, expansion 1, and load 1 into Locally twisted cube.We present three effective algorithms for fault-tolerant embedding of complete binary trees in locally twisted cubes with respect to one faulty node, two faulty node, and any faulty set F of 2 < | F | ź 2 n - 1 nodes, respectively.

The DCell network is suitable for massively scalable data centers with high network capacity by only using commodity switches. In this paper, we construct n + k - 1 vertex-disjoint paths between every two distinct vertices of the DCell network. Their longest length is not greater than 2 k + 1 + 3 , where it was proved that the diameter of a k -dimensional DCell, D C e l l k , has an upper bound 2 k + 1 - 1 . Furthermore, we propose an O ( k 2 k ) algorithm for finding vertex-disjoint paths between every two distinct vertices in DCell networks. Finally, we give the simulation result of the maximal length of disjoint paths gotten by our algorithm. Construct n + k - 1 vertex-disjoint paths between every two distinct vertices of the DCell. Their longest length is not greater than 2 k + 1 + 3 , where it was proved that the diameter of a k -dimensional DCell, D C e l l k , has an upper bound 2 k + 1 - 1 .Propose an O ( k 2 k ) algorithm for finding vertex-disjoint paths between every two distinct vertices in DCell.Give the simulation result of the maximal length of disjoint paths gotten by our algorithm.

The connectivity of a network - the minimum number of nodes whose removal will disconnect the network - is directly related to its reliability and fault tolerability, hence an important indicator of the network's robustness. In this paper, we extend the notion of connectivity by introducing two new kinds of connectivity, called structure connectivity and substructure connectivity, respectively. Let H be a certain particular connected subgraph of G. The H-structure connectivity of graph G, denoted ? ( G ; H ) , is the cardinality of a minimal set of subgraphs F = { H 1 ' , H 2 ' , ? , H m ' } in G, such that every H i ' ? F is isomorphic to H, and F's removal will disconnect G. The H-substructure connectivity of graph G, denoted ? s ( G ; H ) , is the cardinality of a minimal set of subgraphs F = { J 1 , J 2 , ? , J m } , such that every J i ? F is a connected subgraph of H, and F's removal will disconnect G. In this paper, we will establish both ? ( Q n ; H ) and ? s ( Q n ; H ) for the hypercube Q n and H ? { K 1 , K 1 , 1 , K 1 , 2 , K 1 , 3 , C 4 } .

We propose an approach to embed the complete binary tree into the n-dimensional Mbius cube Mn.We prove that the complete binary tree with 2n1 vertices can be embedded with dilation 1, congestion 1, load 1 into Mn and expansion tending to 1.The research result in this paper demonstrates that embeddability of the complete binary tree in the n-dimensional Mbius cube is superior to that in the n-dimensional hypercube. The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The Mbius cube Mn is an important variant of the hypercube Qn. It has many better properties than Qn with the same number of edges and vertices. In this paper, we prove that the complete binary tree with 2n1 vertices can be embedded with dilation 1, congestion 1, load 1 into Mn and expansion tending to 1.

Personal cloud storage provides users with convenient data access services. Service providers build distributed storage systems by utilizing cloud resources with distributed hash table DHT, so as to enhance system scalability. Efficient resource provisioning could not only guarantee service performance, but help providers to save cost. However, the interactions among servers in a DHT-based cloud storage system depend on the routing process, which makes its execution logic more complicated than traditional multi-tier applications. In addition, production data centers often comprise heterogeneous machines with different capacities. Few studies have fully considered the heterogeneity of cloud resources, which brings new challenges to resource provisioning. To address these challenges, this paper presents a novel resource provisioning model for service providers. The model utilizes queuing network for analysis of both service performance and cost estimation. Then, the problem is defined as a cost optimization with performance constraints. We propose a cost-efficient algorithm to decompose the original problem into a sub-optimization one. Furthermore, we implement a prototype system on top of an infrastructure platform built with OpenStack. It has been deployed in our campus network. Based on real-world traces collected from our system and Dropbox, we validate the efficiency of our proposed algorithms by extensive experiments. Copyright © 2016 John Wiley & Sons, Ltd.

In order to limit the damage of key exposure for identity-based encryption, we propose a new paradigm called intrusion-resilient identity-based encryption (IRIBE) in this paper. Compared with key-insulated identity-based encryption and forward-secure identity-based encryption, IRIBE can achieve a stronger level of security. In our proposed scheme, the ciphertexts in any other time periods are secure even after arbitrarily many compromises of the base and the user, as long as compromises do not happen simultaneously. Furthermore, the intruder cannot decrypt the ciphertexts pertaining to previous time periods, even if it compromises the base and the user simultaneously. Therefore, our IRIBE scheme can greatly enhance the security of identity-based encryption. We also formalize the definition and the security notions of this paradigm. The proposed scheme is proven secure in the standard model.

Data center networks have been becoming more and more important with the development of cloud computing. For any two integers k ? 0 and n ? 2 , the k-dimensional DCell with n-port switches, D k , n , has been proposed for one of the most important data center networks as a server centric data center network structure. D k , n can support millions of servers with outstanding network capacity and provide good fault tolerance by only using commodity switches. A disjoint path cover has significant applications in data center networks. In this paper, we prove that D k , n is one-to-one r-disjoint path coverable for any integer 1 ? r ? n + k - 1 , except for D 1 , 2 . Moreover, we propose an O ( t k ) algorithm for finding a one-to-one r-disjoint path cover in D k , n for any integer 1 ? r ? n + k - 1 , where t k is the number of servers in D k , n .

The alternating group graph, denoted by AG n , is one of the popular interconnection networks, which has many attractive properties. In this paper, we prove that for any two distinct nodes µ and ?, there exist m node-disjoint paths for any integer n ? 3 with 1 ? m ? 2 n - 4 whose union covers all the nodes of AG n . For any node of AG n has exactly 2 n - 4 neighbors, 2 n - 4 is the maximum number of node-disjoint paths can be constructed in AG n .

The complete binary tree as an important network structure has long been investigated for parallel and distributed computing, which has many nice properties and used to be embedded into other interconnection architectures. The parity cube is an important variant of the hypercube. It has many attractive features superior to those of the hypercube. In this paper, we prove that the complete binary tree with $$2^n-1$$ 2 n - 1 vertices can be embedded with dilation 1, congestion 1, load 1 into the $$n$$ n -dimensional parity cube $$PQ_n$$ P Q n and expansion tending to 1. Furthermore, we provide an $$O(NlogN)$$ O ( N l o g N ) algorithm to construct the complete binary tree with $$2^n-1$$ 2 n - 1 vertices in $$PQ_n$$ P Q n , where $$N$$ N denotes the number of vertices in $$PQ_n$$ P Q n and $$n\ge 1$$ n ? 1 .

The concept of metric basis is useful for robot navigation. In graph G, a robot is aware of its current location by sending signals to obtain the distances between itself and the landmarks in G. Its position is determined uniquely in G if it knows its distances to sufficiently many landmarks. The metric basis of G is defined as the minimum set of landmarks such that all other vertices in G can be uniquely determined and the metric dimension of G is defined as the cardinality of the minimum set of landmarks. The major contribution of this paper is that we have partly solved the open problem proposed by Manuel et al. [9] , by proving that the metric dimension of HDN1 ( n ) and HDN2 ( n ) are either 3 or 4. However, the problem of finding the exact metric dimension of HDN networks is still open.

Meshes are widely used topologies for Networks on Chip (NoC). Honeycomb meshes have better topological properties than Meshes. In order to communicate efficiently in a linear or cyclic manner, it is benefited that there is a Hamiltonian path or Hamiltonian cycle in NoC. In this paper, we give a necessary and sufficient condition for the existence of Hamiltonian path between any pair of vertices in a honeycomb mesh and for the existence of Hamiltonian path in a honeycomb mesh with one faulty vertex. Besides, we give a systematic method to construct a Hamiltonian path in Honeycomb meshes.

Multiple independent spanning trees (ISTs) can be used for data broadcasting in networks, which can provide advantageous performances, such as the enhancement of fault-tolerance, bandwidth, and security. However, there is a conjecture on the existence of ISTs in graphs: If a graph G is n-connected (n>=1), then there are n ISTs rooted at an arbitrary vertex in G. This conjecture has remained open for n>=5. The n-dimensional crossed cube CQ"n is a n-connected graph with various desirable properties, which is an important variant of the n-dimensional hypercube. In this paper, we study the existence and construction of ISTs in crossed cubes. We first give a proof of the existence of n ISTs rooted at an arbitrary vertex in CQ"n(n>=1). Then, we propose an O(Nlog^2N) constructive algorithm, where N=2^n is the number of vertices in CQ"n.

Independent spanning trees (ISTs) have increasing applications in fault-tolerance, bandwidth, and security. In this paper, we study the problem of parallel construction of ISTs on crossed cubes. We first propose the definitions of dimension-adjacent walk and dimension-adjacent tree along with a dimension property of crossed cubes. Then, we consider the parallel construction of ISTs on crossed cubes. We show that there exist n general dimension-adjacent trees which are independent of the addresses of vertices in the n-dimensional crossed cube CQ"n. Based on n dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity O(2^n) is proposed to construct n ISTs on CQ"n, where n>=1.

Independent spanning trees (ISTs) on networks have applications to increase fault-tolerance, bandwidth, and security. Mobius cubes are a class of the important variants of hypercubes. A recursive algorithm to construct n ISTs on n-dimensional Mobius cube M n was proposed in the literature. However, there exists dependency relationship during the construction of ISTs and the time complexity of the algorithm is as high as O(NlogN), where N=2 n is the number of vertices in M n and n?2. In this paper, we study the parallel construction and a diagnostic application of ISTs on Mobius cubes. First, based on a circular permutation n?1,n?2,?,0 and the definitions of dimension-backbone walk and dimension-backbone tree, we propose an O(N) parallel algorithm, called PMCIST, to construct n ISTs rooted at an arbitrary vertex on M n . Based on algorithm PMCIST, we further present an O(n) parallel algorithm. Then we provide a parallel diagnostic algorithm with high efficiency to diagnose all the vertices in M n by at most n+1 steps, provided the number of faulty vertices does not exceed n. Finally, we present simulation experiments of ISTs and an application of ISTs in diagnosis on 0-M 4.

BC graphs are important interconnection networks, which include hypercubes, crossed cubes and other hypercube's variants. In this paper, we propose a new model, named BC-VoD model, to approach VoD system, which utilizes BC graphs. At the same time, we use independent spanning trees for content distribution. The simulation results show that this model has advantageous performance.

Independent spanning trees have applications in networks such as reliable communication protocols, one-to-all broadcasting, reliable broadcasting, and secure message distribution. Thus, the designs of independent spanning trees in several classes of networks have been widely investigated. However, there is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an arbitrary vertex. This conjecture still remains open for n>=5. In this paper, by proposing an algorithm to construct n independent spanning trees rooted at any vertex, we confirm the conjecture on n-dimensional parity cube PQ"n -- a variant of n-dimensional hypercube. Furthermore, we prove that all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n>=2.

The n-dimensional twisted-cube, TN"n, is a variation of the hypercube. In this paper, we study embedding of meshes into TN"n. We prove three major results in this paper: (1) For any integer n>=1, a 2x2^n^-^1 mesh can be embedded into TN"n with dilation 1 and expansion 1. (2) For any integer n>=4, an mxk(m>=3,k>=3) mesh cannot be embedded into TN"n with dilation 1. (3) For any integer n>=4, two node-disjoint 4x2^n^-^3 meshes can be embedded into TN"n with dilation 2 and expansion 1.

Bijective connection graphs (in brief, BC graphs) are a family of hypercube variants, which contains hypercubes, twisted cubes, crossed cubes, Mobius cubes, locally twisted cubes, etc. It was proved that the smallest diameter of all the known n-dimensional bijective connection graphs (BC graphs) is @[email protected]?, given a fixed dimension n. An important question about the smallest diameter among all the BC graphs is: Does there exist a BC graph whose diameter is less than the known BC graphs such as crossed cubes, twisted cubes, Mobius cubes, etc., with the same dimension? This paper answers this question. In this paper, we find that there exists a kind of BC graphs called spined cubes and we prove that the n-dimensional spined cube has the diameter @?n/[email protected]?+3 for any integer n with n>=14. It is the first time in literature that a hypercube variant with such a small diameter is presented.

The connectivity is an important criteria to measure the fault-tolerant performance of a graph. However, the connectivity based on the condition of the set of arbitrary faulty nodes is generally lower. In this paper, in order to heighten this measure, we introduce the restricted connectivity into bijective connection networks. First, we prove that the probability that all the neighbors of an arbitrary node becomes faulty in any n-dimensional bijective connection network X"n is very low when n becomes sufficient large. Then, we give a constructive proof that under the condition that each node of an n-dimensional bijective connection network X"n has at least one fault-free neighbor, its restricted connectivity is 2n-2, about half of the connectivity of X"n. Finally, by our constructive proof, we give an O(n) algorithm to get a reliable path of length at most n+3@?log"2|F|@?+1 between any two fault-free nodes in an n-dimensional bijective connection network. In particular, since the family of BC networks contains hypercubes, crossed cubes, Mobius cubes, etc., our algorithm is appropriate for these cubes.

The security of traditional identity-based signatures wholly depends on the security of secret keys. Exposure of secret keys requires reissuing all previously assigned signatures. This limitation becomes more obvious today as key exposure is more common with increasing use of mobile and unprotected devices. Under this background, mitigating the damage of key exposure in identity-based signatures is an important problem. To deal with this problem, we propose to integrate forward security into identity-based signatures. In this paper, we firstly formalize the definition and security notions for forward-secure identity-based signature scheme, and then construct an efficient scheme. All parameters in our scheme have, at most, log-squared complexity in terms of the total number of time periods. The scheme is provably secure without random oracles.