Search

The efficiency of cloud computing is significantly impacted by the capabilities of data center networks (DCNs). However, with the increasing demands of applications, the number of servers in DCNs is growing exponentially. In general, networks become more vulnerable as they expand in size. Consequently, it is essential to assess the network's reliability. Subsystem reliability, a crucial parameter of network reliability, is the likelihood that a faultless subsystem with a specific size would function normally. Even though several networks have the same order, their subsystem reliability may differ. In this article, we compare two distinct subsystems of $m$-port $k$-dimensional DCNs BCube that have the same number of vertices and ascertain the critical time so that the reliability bound is robust. In addition, we discover that, when comparing two subsystems of BCube that have the same number of vertices, the smaller the dimension $k$, the greater the subsystem reliability of BCube will be for $m\geq 2$ and $k\geq 1$. This offers a theoretical foundation that allows us to choose a more reliable system in BCube that have the same number of vertices. Finally, we use numerical experiments to verify our findings.

Topology design is vital to the high performance data center networks. Due to the limited scalability, many traditional server-centric data center networks are confronting the updating and upgrading hurdles. To address the issue, this paper proposes a highly scalable DCell-based server-centric data center network topology, called HS-DCell, which can use inexpensive and typical switches and servers with only three network ports to achieve excellent network performance. HS-DCell can accommodate a large number of servers, and its diameter increases linearly with the growth of network levels, which is better than that of most existing server-centric networks. Furthermore, a fault-free routing algorithm and a fault-tolerant routing algorithm are developed based on HS-DCell. Compared with other mainstream server-centric network topologies, the experimental results show that HS-DCell has obvious advantages in many key performance indicators including scalability, fault tolerance, and server port utilization.

Networks of large scales are an essential component in supercomputing systems as well as in data centers. As the network scale increases, the probability of processor/server failures also inevitably increases. It is therefore a worthwhile undertaking to make efforts reducing, as much as possible, the effect of faulty processors/servers to the entire network. This paper introduces a new class of network architectures, called circulant-based recursive networks (CRNs), and investigates CRN’s diameter, connectivity, and in particular, the fault diagnosability under the two diagnostic models−the PMC and the comparison diagnostic models. CRNs are a generalization of some well-known interconnection networks−hypercube, k-ary n-cube network and the data center network BCube, as well as some other less-known networks. In addition to obtaining its diagnosability properties, the paper also presents a one-to-one (unicast) path construction algorithm named SPath. Based on SPath, we further propose an algorithm FTPath for CRNs finding a fault-tolerant path between any two vertices, provided that the number of faulty vertices is no more than its connectivity minus one. Three parameters−average distance, message density, and cost−are used to assess CRNs’ performance. Experimental comparisons are conducted, and the results indicate that the average path length obtained by the algorithm SPath (resp., FTPath) is shorter than that of the Depth-First Search algorithm (DFS) and is on a par with the Breath-First Search algorithm (BFS).

ABSTRACTIn parallel and distributed systems, interconnection networks and data center networks are two crucial networks. They are also crucial parts of high-performance computing and cloud computing services. With the rapid growth of high-performance computing and cloud computing, both networks are growing in size. At the same time, vertex faults are unavoidable. In computer/communication networks, unicast refers to one-to-one communication between the source vertex and the destination vertex. Fault-tolerant routing of vertices in networks is an important problem that has been widely discussed. In this paper, for a class of recursive networks with less than $g$g-restrict connectivity fault vertices and each fault-free vertex having at least $g$gfault-free neighbors, we provide a fault-tolerant unicast path design algorithm in this study. The algorithm’s correctness is then demonstrated and its time complexity is analyzed. In addition, the results obtained can be used for unknown and known networks, including the dragonfly network, DCell, and generalized DCell.

Most data center services are finished by the cooperation among the connected servers. However, the malicious attackers always try to divide the network into disconnected components to start some attacks, such as the address resolution protocol (ARP) attack, the denial of service (DoS) attack, the botnet attack, and so on. The connectivity is an excellent indicator to measure the reliability and fault-tolerant ability of the network. Whereas, the traditional connectivity and current conditional connectivity cannot well reflect the fault-tolerant performance of the network when attackers are a block or have a certain structure and the components of the remaining network still have a certain structure. Based on this fact, we propose a new measure: the double-structure connectivity, which can accurately reflect the fault-tolerant ability of the network when attackers are structured and each component of the network has a certain structure after removing the attacked servers. Meanwhile, a hypercube is a high-performance interconnection network that can also be used to design some data center networks. Therefore, we study the double-structure fault-tolerance of the hypercube and determine the double-structure connectivity of distinct structures of the hypercube. Furthermore, we propose algorithms to construct structures of attackers directly to measure the fault-tolerant ability of the hypercube under this attack. Our results can be applied not only to interconnection networks but also to some data center networks.

One of the important issues in evaluating an interconnection network is to study the fault-tolerant Hamiltonian cycle and Hamiltonian path embedding problems. The $k$-ary $n$-cube (denoted by $Q^{k}_{n}$) networks are used as interconnection networks for many parallel and distributed computing systems. In this article, we investigate the Hamiltonian cycle and path embeddings in the bipartite $k$-ary $n$-cube $Q^{k}_{n}$ based on $K_{1,1}$-structure faults. We show that there exists a Hamiltonian cycle in $Q^{k}_{n}-\mathcal {F}$ if $|\mathcal {F}|\leq 2n-2$ and there exists a Hamiltonian path between any two vertices from different partite sets in $Q^{k}_{n}-\mathcal {F}$ if $|\mathcal {F}|\leq 2n-3$ for $n\geq 2$ and even $k\geq 4$, where $\mathcal {F}$ is a set of vertex-disjoint subgraphs isomorphic to $K_{1,1}$ in $Q_{n}^{k}$. In some sense, the results mean that when a subset $S$ of at most $4n-4$ (resp. $4n-6$) processors is deleted from a bipartite $Q^{k}_{n}$, there exists a Hamiltonian cycle (resp. a Hamiltonian path between any two healthy processors from different partite sets) in the remaining network. Our results, in some sense, compensate the results in Lv et al. [J. Parallel Distrib. Comput., 120, 148–158, 2018] and [Comput. J., 60, 159–179, 2017], where authors studied the $K_{1,3}$-substructure fault-tolerant Hamiltonian cycle and path embedding problems in nonbipartite $k$-ary $n$-cubes. In comparison, the bipartite $k$-ary $n$-cube $Q^{k}_{n}$ can keep the same $K_{1,1}$-structure fault-tolerant Hamiltonian capabilities as the nonbipartite one.

Edge computing can help the resource-constrained Internet of Things (IoT) devices to perform some complex tasks. Edge computing has many advantages, such as the distributed architecture, low interaction latency, and good resilience. It can provide fast response and reliable service for the IoT applications. There exists an important application in the edge computing environment is to outsource the computationally intensive problems to nearby edge servers, which has become a research hotspot in the area of industry and academia. In this article, we propose a distributed and secure system DSOS for seeking the least squares solution to the overdetermined system of linear equations (OSLE) with the assistance of multiple nearby noncolluding edge servers. Solving this type of linear equations is one of the most common problems for statistics and data mining in IoT. In our system, the coefficient matrix is divided into multiple blocks according to rows. The different blocks are distributed to the different edge servers. All edge servers can help the user to obtain the correct solution to the OSLE by the interactive computation. Our system can ensure the private information about input parameters and final results is not leaked to the participating edge servers. In addition, the mutual verification between the edge servers can ensure the validity of the final results. The experimental evaluations show that the designed system outperforms the existing ones in terms of fast response between the edge server and the user, low computation overload on the edge server side, and high efficiency on the user side.

With the continuous attention to the parallel computing system, the reliability of the system, which is mainly measured by two parameters, connectivity and diagnosability, needs to be constantly studied and improved. At present, the component connectivities of some networks have been extensively studied, while the component diagnosabilities of these networks have rarely involved in. In this article, some networks with common characteristics are summarized as a class of regular networks. The definition of this kind of networks is given, and its reliability based on component failures is determined. To be specific, we prove that $c\kappa _{m+1}(G)=m(k-1)-\binom{m}{2}+1$ for $1\leq m\leq k-2$ and $ct_{m+1}(G)=(m+1)k-\binom{m}{2}-2\ m$ for $1\leq m\leq k-2$ under the PMC model, where $c\kappa _{m+1}(G)$ and $ct_{m+1}(G)$ represent the $(m+1)$-component connectivity and the $(m+1)$-component diagnosability of such networks $G$, respectively. Based on this, we design a low time complexity component diagnosis algorithm for this kind of networks. As applications, the above two component reliability parameters of many famous networks are explored. Furthermore, the proposed diagnosis algorithm is simulated on these networks, and the results show that the algorithm has high diagnosis accuracy for various networks.

With the increasing scale of parallel computer interconnection network, the possibility of processor failure or link failure between processors in the network is also increasing. In the design of supercomputers, not only link overhead and communication delay should be taken into account, but also fault-tolerant performance of networks should be emphasized. Locally exchanged twisted cube ($LeTQ$LeTQ) is a newly proposed interconnection network with lower link overhead and shorter diameter. With the increasing scale of supercomputers, fault-tolerant routing is indispensable. In this article, we propose a new load balancing fault-tolerant routing algorithm based on node contraction for $LeTQ$LeTQ networks. The proposed algorithm uses the node shrinkage method to evaluate the priority of nodes. The sending node adaptively adjusts the probability of forwarding packets to the neighbor node according to the priority of the neighbor node and the state of the network. The path can be adapted to the load state of the network. The simulation results show that the fault-tolerant routing algorithm has good performance in throughput and delay.

The public cloud data integrity auditing technique is used to check the integrity of cloud data through the Third Party Auditor (TPA). In order to make it more practical, we propose a new paradigm called integrity auditing based on the keyword with sensitive information privacy for encrypted cloud data. This paradigm is designed for one of the most common scenario, that is, the user concerns the integrity of a portion of encrypted cloud files that contain his/her interested keywords. In our proposed scheme, the TPA who is only provided with the encrypted keyword, can audit the integrity of all encrypted cloud files that contain the user’s interested keyword. Meanwhile, the TPA cannot deduce the sensitive information about which files contain the keyword and how many files contain this keyword. These salient features are realized by leveraging a newly proposed Relation Authentication Label (RAL). The RAL can not only authenticate the relation that files contain the queried keyword, but also be used to generate the auditing proof without sensitive information exposure. We give concrete security analysis showing that the proposed scheme satisfies correctness, auditing soundness and sensitive information privacy. We also conduct the detailed experiments to show the efficiency of our scheme.

Crowd sensing effectively solves the dilemma of massive data collection faced by most data-driven applications. Recently, mobile edge computing (MEC) is proposed to extend the frontier of cloud to the network edge so that it is quite suitable to integrate MEC with current crowd sensing systems. In this paper, we focus on the basic problem of task scheduling in such systems. The problem discussed here has some unique challenges, e.g., edge devices are not dedicated to perform sensing tasks, task scheduling on edge devices and edge servers are highly coupled, and it is hard to achieve long-term objectives. To this end, we first present a workflow framework that captures the unique execution logic of sensing tasks. Then we propose a staged scheme to decouple the original scheduling problem. Moreover, we leverage Lyapunov optimisation technique to achieve long-term objective. The experiment results verify the effectiveness and efficiency of our proposed algorithm.

Abstract The k -ary n -cube is one of the most attractive interconnection networks for parallel and distributed computing system. In this paper, we investigate the fault-tolerant capabilities of k -ary n -cubes with respect to the structure connectivity and substructure connectivity. Let H is a connected graph. The structure connectivity of a graph G , denoted by κ (G; H), is the minimum cardinality of a set of connected subgraphs in G , whose deletion disconnects the graph G and every element in the set is isomorphic to H. The substructure connectivity of a graph G , denoted by κs (G; H), is the minimum cardinality of a set of connected subgraphs in G , whose deletion disconnects the graph G and every element in the set is isomorphic to a connected subgraph of H. We show κ (Q n k ; H) and κ s (Q n k ; H) for each H ∈ { K 1 , K 1, 1 , K 1, 2 , K 1, 3 }. [ABSTRACT FROM AUTHOR]

ABSTRACTThe -dimensional exchanged crossed cube combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that has more attractive properties than other variations of the basic hypercube in terms of the smaller diameter, fewer edges, and lower cost factor. In this paper, we study the diagnosability of under the pessimistic diagnosis strategy based on two diagnostic models: the PMC model and the MM* model. And we obtain the following results: if , the diagnosability of the are both under the pessimistic diagnosis strategy based on the two models.

Abstract: 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. [Copyright &y& Elsevier]

Abstract: 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(N log2 N) constructive algorithm, where N =2 n is the number of vertices in CQ n . [Copyright &y& Elsevier]

Abstract: 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 2×2 n−1 mesh can be embedded into TN n with dilation 1 and expansion 1. (2) For any integer n ⩾4, an m × k(m ⩾3, k ⩾3) mesh cannot be embedded into TN n with dilation 1. (3) For any integer n ⩾4, two node-disjoint 4×2 n−3 meshes can be embedded into TN n with dilation 2 and expansion 1. [Copyright &y& Elsevier]

Abstract: 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⌈log2∣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, Möbius cubes, etc., our algorithm is appropriate for these cubes. [Copyright &y& Elsevier]

Abstract: As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ n (V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ⩾1, a 2×2 n−1 mesh can be embedded in LTQ n with dilation 1 and expansion 1. (2) For any integer n ⩾4, two node-disjoint 4×2 n−3 meshes can be embedded in LTQ n with dilation 1 and expansion 2. (3) For any integer n ⩾3, a 4 ×(2 n−2 −1) mesh can be embedded in LTQ n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2×2 n−1 mesh is also optimal in terms of expansion. We also present the analysis of 2p ×2q mesh embedding in locally twisted cubes. [Copyright &y& Elsevier]

Abstract: A DCC (disjoint consecutive cycles) linear congruential graph G(F, n) consists of n nodes and is generated by a set of linear functions F with special properties. It was proved that G(F, n) is a 2t-regular graph and has connectivity 2t, where and ( for some integer p). For a multiprocessor system, its diagnosability is critical to measure the performance. In this paper, we study the diagnosability of under the precise and pessimistic diagnosis strategies based on the PMC (Preparata, Metze, and Chien) diagnostic model. It is proved that is 2t-diagnosable and -diagnosable under the two diagnosis strategies, respectively, where and . In addition, the diagnosability of DCC linear congruential graphs is compared with that of BC (bijective connection) graphs. [Copyright &y& Elsevier]

Abstract: An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2 n nodes and n2 n−1 edges. The n-dimensional hypercube, crossed cube, Möbius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(X n , x, y)+2⩽ l ⩽2 n −1 can be embedded between x and y with dilation 1 in X n for x, y ∈ V(X n ) with x ≠ y in X n , where X n (n ⩾4) is a n-dimensional BC graph satisfying the three specific conditions and V(X n ) is the node set of X n . Furthermore, by this result, we can claim that X n is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes. [Copyright &y& Elsevier]

Abstract: Crossed cubes are important variants of hypercubes. In this paper, we consider embeddings of meshes in crossed cubes. The major research findings in this paper are: (1) For any integer n ⩾1, a 2×2 n−1 mesh can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 1. (2) For any integer n ⩾4, two node-disjoint 4×2 n−3 meshes can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 2. The obtained results are optimal in the sense that the dilations of the embeddings are 1. The embedding of the 2×2 n−1 mesh is also optimal in terms of expansion because it has the smallest expansion 1. [Copyright &y& Elsevier]

Abstract: Crossed cubes are popular variants of hypercubes. In this paper, we study path embeddings between any two distinct nodes in crossed cubes. We prove two important results in the n-dimensional crossed cube: (a) for any two nodes, all paths whose lengths are greater than or equal to the distance between the two nodes plus 2 can be embedded between the two nodes with dilation 1; (b) for any two integers n ⩾2 and l with , there always exist two nodes x and y whose distance is l, such that no path of length l +1 can be embedded between x and y with dilation 1. The obtained results are optimal in the sense that the dilations of path embeddings are all 1. The results are also complete, because the embeddings of paths of all possible lengths between any two nodes are considered. [Copyright &y& Elsevier]

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,thas 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 fvand faulty edges fe. Firstly, we prove that an LeTQs,tcan 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,twith up to (s− 2) faulty vertices and edges. That is, we show that LeTQs,tis (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.

Abstract: This paper proposes a novel tree kernel-based method with rich syntactic and semantic information for the extraction of semantic relations between named entities. With a parse tree and an entity pair, we first construct a rich semantic relation tree structure to integrate both syntactic and semantic information. And then we propose a context-sensitive convolution tree kernel, which enumerates both context-free and context-sensitive sub-trees by considering the paths of their ancestor nodes as their contexts to capture structural information in the tree structure. An evaluation on the Automatic Content Extraction/Relation Detection and Characterization (ACE RDC) corpora shows that the proposed tree kernel-based method outperforms other state-of-the-art methods. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

Abstract: 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. [ABSTRACT FROM AUTHOR]