With the rapid advancement of digital technologies such as cloud computing, big data, and artificial intelligence, large-scale data centers have become critical infrastructure supporting these technologies, imposing increasingly high demands on data center networks (DCNs). Traditional server-centric DCNs face challenges in large-scale distributed systems, such as difficulty in balancing bandwidth and latency, high expansion costs, and conflicts between fault tolerance and communication efficiency. To address these issues, this paper proposes ECQDC, a novel server-centric DCN based on exchanged crossed cube. Specifically, we present its logical structure ECD(s, t) and study the connectivity and edge connectivity of ECD(s, t). Furthermore,we develop efficient fault-free routing algorithm and faulttolerant routing algorithm for the ECD(s, t). The experimental results demonstrate that, compared with Dijkstra and BFS, the proposed ECDR and ECDFTR algorithms reduce the average running time by over 50% and cut the average path length by approximately 20% relative to BFS, while keeping path lengths close to Dijkstra’s optimal performance. Moreover, it exhibits excellent performance in scalability, fault tolerance, and communication efficiency, making it an ideal network topology for large-scale data center deployment.

With the proliferation of interconnection networks in mission-critical systems ranging from cloud computing infrastructures to large-scale data centers, the escalating structural complexity has intensified network vulnerability to malicious attacks and cyber warfare incidents. This article establishes a theoretical framework for evaluating network self-diagnostic capability through a novelh-extrar-component diagnosability metric, denoted as$\widehat{ec}_{r}^{h}(G)$, which quantifies a network’s resilience under compound fault patterns. The proposed metric requires that after removing specific nodes, the remaining subgraph is required to preserve at leastrconnected components where every component maintains a node count exceedingh. Through rigorous combinatorial analysis, we derive closed-form expressions for star networks$S_{n}$,$\widehat{ec}_{2}^{1}(S_{n}) = 4n - 9$and$\widehat{ec}_{3}^{1}(S_{n}) = 6n - 15$when$n \ge 6$, establishing the tight diagnosability bounds for this fundamental network topology. To enable practical implementation, we design a Trial System-based Fault Diagnosis Algorithm (TSFD) that features adaptive syndrome verification and parallel fault localization mechanisms. Extensive simulations demonstrate the accuracy of 98.99% fault detection with linear-time complexity$O(Nd)$inn-dimensional star networks. This work advances network reliability theory by introducing a multi-feature diagnosability measure for system-level diagnosis and developing an efficient diagnosis algorithm validated through large-scale network emulation.

The rapid growth of cloud computing, large-scale distributed systems, and AI-driven applications has placed stringent demands on the performance and reliability of data center networks (DCNs). As DCNs scale in size and structural complexity, they become increasingly vulnerable to multiple concurrent node and/or link failures, which can lead to severe service disruptions and significant performance degradation. Existing data transmission approaches typically address node and link failures in isolation, frequently mitigating one type while overlooking the other, and thus fall short in effectively handling complex multi-failure scenarios. This paper presents a novel and efficient data transmission scheme designed to ensure robust communication under multiple node and/or link failures in DCNs. The proposed solution integrates a proactive path redundancy mechanism with a failure-aware routing strategy to enable rapid identification and avoidance of faulty components. We adopt the generalized hypercube network (GHN), a regular and scalable topology, as the underlying network model. Firstly, leveraging the method of Yang and Chang [44], we construct multiple independent spanning trees (ISTs) in GHNs, which provide structural path diversity and fault isolation. Building upon these ISTs, we propose GFP-IST, an optimized routing algorithm with a time complexity ofO(NlogN), whereNdenotes the number of nodes. GFP-IST enables efficient route computation and resilient packet forwarding in the presence of multiple simultaneous failures. Extensive simulation results demonstrate that our approach outperforms several fault-tolerant routing schemes in terms of average path length, path construction time, and fault recovery success rate, especially in large-scale and high-failure-rate network environments.

With the rapid advancement of big data processing and artificial intelligence (AI), data center networks (DCNs) must deliver more efficient resource management and data transmission mechanisms. Unfortunately, due to the significant differences in bandwidth requirements, transmission patterns, and temporal characteristics across various traffic types in DCNs (such as short flows, long flows, and bursty flows), traditional buffer allocation strategies fail to adapt flexibly to these disparities. In this paper, we propose Enhanced Buffer Management (EBM), a novel buffer-sharing scheme designed for scenarios that require higher performance from DCNs. Unlike prior approaches, EBM employs a multi-level flow identification and adaptive threshold adjustment mechanism to enhance the flexibility and efficiency of buffer management under varying traffic conditions. Specifically, EBM first performs coarse-grained and fine-grained classification of traffic based on packet size, inter-arrival interval, and other flow characteristics. It then applies an improved threshold computation function to allocate buffer space differentially across traffic classes while maintaining allocation smoothness. Our evaluation results demonstrate that EBM significantly improves performance under realistic workloads. For instance, it reduces the 99th percentile Flow Completion Time (FCT) slowdown by 32.7% for short flows in the web-search workload and by 45.1% for incast flows in the hadoop workload, all without sacrificing overall throughput.

DNA mimic proteins are relatively obscure control factors that resemble DNA by mimicking its negatively charged distribution. They achieve this using negatively charged amino acids like aspartic acid (ASP/D) and glutamic acid (GLU/E). Known DNA mimic proteins control various cellular mechanisms, such as transcription, DNA repair, and gene regulation, by intervening in the binding of DNA to effector proteins. In addition to their biological functions, DNA mimic proteins may also be applicable in biotechnology, for example, by regulating CRISPR-Cas9 activity to enhance gene editing precision. Therefore, DNA mimic proteins warrant further research. However, most DNA mimic proteins cannot be identified using traditional bioinformatics methods owing to their unique amino acid sequences and structural features. We developed a new protein fingerprint, called relative distance protein fingerprint (RD-PFP), that can be used to analyze the distribution of amino acids on a protein surface. We optimized our RD-PFP by using machine learning and the characteristic feature of DNA mimic proteins (namely, their DNA-like negatively charged distribution) to more accurately predict DNA mimicry from protein structures. Our pioneering study contributes to the development of machine learning-based bioinformatics methods for screening DNA mimic proteins.

Abstract Increases in the complexity and detail of real-world graphs have engendered difficulties in reducing the memory and processing requirements of these graphs. Various distributed and single computer processing systems have been developed for processing large graphs. Out-of-core processing systems achieve enhanced processing efficiency by reducing input–output (I/O) processing requirements, increasing locality, or accelerating convergence. However, not all out-of-core systems can optimize every graph processing algorithm. Accordingly, this study proposes KedaGraph, an out-of-core graph processing system that offers three streamers to enhance its applicability across different algorithms. In addition, this system enables more flexible scheduling than do existing out-of-core processing systems, thus facilitating improved performance in different processing tasks. We also developed a compression scheme to reduce the I/O overhead of KedaGraph. Our evaluation results revealed that KedaGraph outperformed existing out-of-core systems in various graph processing tasks. Furthermore, the proposed system demonstrates sensitivity to memory budget and thread count on commodity single-node hardware, with performance improvements observed as available resources increase within the evaluated configuration range.

Cyclic fault diagnosis is crucial for ensuring system reliability, as it facilitates the early detection and resolution of recurring failures, minimizing downtime and maintenance costs. Existing methods often face challenges with high computational complexity and scalability, limiting their real-time applicability in complex networks like Bijective Connection (BC) networks, where rapid fault isolation is essential. In this paper, we explore the cyclic diagnosability ofg-BC networks under two classical system-level fault diagnosis models: the P/M/C model and the MM* model. Cyclic diagnosability, which focuses on maintaining connectivity with cycles in the residual subgraph after failures, is a more robust measure than traditional diagnosability. We prove that for anyg-BC networkg-Xnthat satisfies Definition 3, the cyclic diagnosability is given byct(g-Xn) = 5n− 8 −gforg= 1,n≥ 12 and 2 ≤g≤ 5,n≥ 11 under both models, thereby determining the maximum number of faults that can be accurately identified while preserving at least two cyclic components. To support practical diagnosis under these models, we propose two fast and scalable algorithms with low time complexity: TDPMC (Threshold-Based Fault Diagnosis under the P/M/C Model forg-BC Networks) and FBDMM (Suspicion-Score-Based MM* Fault Diagnosis with Dynamic Threshold forg-BC Networks). Both methods exploit the topological features of BC networks to efficiently identify cyclic faults. The time complexities of TDPMC and FBDMM areO(nN) andO(n2N), respectively. Experimental results on an 11-dimensional and 12-dimensionalg-BC networks validate the theoretical findings, demonstrating significant improvements in accuracy, recall, and fault detection reliability.

Different interconnection structures exert a significant impact on network communication ability, directly influencing system performance. The half hypercube Network has an excellent topology that can provide high network fault tolerance and communication efficiency while maintaining a low node degree. In this paper, we investigate efficient and reliable communication algorithms for half hypercube networks in distributed system. Firstly, we design a disjoint path construction algorithm for a half hypercube, which enables reliable communication of the optimal number of disjoint paths between any two nodes in the network. Secondly, we present a fault-tolerant path embedding algorithm for a half hypercube. When the number of faulty nodes does not exceed ⌈n/2⌉, this algorithm can obtain a fault-tolerant unicast path between any two non-faulty nodes in ann-dimensional half hypercube network. Finally, we evaluate the performance of communication algorithms through simulation experiments and real testbed. Experimental results demonstrate that the efficiency and buffer utilization rate of the proposed algorithms can be improved by at least 21.8% and 15.6%, respectively. Testbed results show that the data delivery rate increased by 21.8%, and the path interference degree decreased by 32.5%.

With the rapid development of cloud computing, big data, and artificial intelligence, data center networks have become the core of modern computing infrastructure. As an important type of data center network, determining theh-component diagnosability ofk-dimensional DCell networksDCellk,nwith n-port switch has become a critical issue for enhancing network’s diagnostic capabilities and assessing network’s vulnerability. However, there is currently scarce research on the h-component diagnosability ofDCellk,nbased on the mutual testing model. In this paper, we innovatively propose theh-component diagnosability and diagnostic algorithm of DCell networks based on the mutual testing model. We first theoretically prove and determine that the h-component diagnosability of DCellk,n is ctPMC h (DCellk,n) = (h− 1)n + hk− (2h− 2) for 2 ≤h≤ 3 andk≥ (h− 2)n+ (4 −h),n≥h+ 1. It implies that the data center networkDCellk,ncan identify (h− 1)n+hk− (2h− 2) faulty nodes when the count of remaining components is at leasth(2 ≤ h ≤ 3). Furthermore, we also propose a novel and broadly applicableh-componentt-diagnosable algorithm ICFD-P based on iterative testing, combinatorial properties and linearly many fault analysis to diagnose all faulty nodes inDCellk,n, effective as a general framework in interconnection networks. We apply the algorithm ICFD-P to simulated data and real data to diagnose faulty nodes. The simulation experiments highlight the effectiveness and robustness of the designed ICFD-P strategy within and even beyond the allowed range of diagnosability inDCellk,n, combined with its enhanced fault diagnosis capability and theoretical foundation for reliability and security, make it a valuable tool for maintaining the stability and security of such networks.

Data center DCell networks are particularly well-suited for large, reliability-critical data centers due to their scalability, fault tolerance, and efficient bandwidth utilization. The reliability and diagnosis of DCell networks are of paramount importance in ensuring smooth operation and continuous availability of data center services. Traditional fault diagnosis models, which focus on global fault detection, are more suited to simpler networks. In contrast, complex DCell networks require fault diagnosis under specific conditions to accommodate dynamic changes and constraints. This paper studies the cyclic diagnosability of DCell networks under different system-level diagnostic models, which is a novel fault diagnosis strategy. Cyclic diagnosability, denoted as$ct_{c}(G)$, represents the maximum size of a set of fault vertices$D$in a network$G$, so that the self-diagnosis system can identify all vertices in$D$under the condition that at least two connected components of$G-D$contain a cycle. We show that for$k$-dimensional DCell with$n$-port switches$DCell_{k,n}$, when$k \geq 2$,$3 \leq n \leq 5$, or$k \geq \frac {n}{2} + 1$,$n \geq 6$, the cyclic diagnosability is$4k+2n-5$under the PMC and MM* models based on the indistinguishability of the constructed set and the linear multiple fault analysis technology. Additionally, we propose two practical cyclic fault diagnosis algorithms with low time complexity: PMC-Based Cyclic Fault Diagnosis (PMCCFD) and MM*-Based Cyclic Fault Diagnosis (MMCFD) for the PMC and MM* models to improve fault detection and recovery in large-scale DCell networks. We also implement the PMCCFD and MMCFD algorithms on both synthetic and real data. Furthermore, we verify the availability/efficiency of algorithms PMCCFD and MMCFD in terms of accuracy rate, recall, false negative rate, negative predictive value, and F1Score.

As critical reliability metrics for multiprocessor systems, connectivity and diagnosability respectively determine network robustness against node failures and the capability to accurately identify faulty units. This article presents a comprehensive reliability analysis of bubble-sort networks (Bn), a class of Cayley graphs that implement adjacent-node swap operations, offering inherent advantages for distributed sorting systems. First, we investigate theh-extrar-component connectivity and diagnosability ofBnunder the Preparata-Metze-Chien (PMC) diagnostic model through rigorous topological analysis. Then, we characterize theg-good-neighborr-component connectivity and diagnosability ofBnunder the PMC model by establishing tight bounds through fault pattern analysis. In addition, we develop a three-round fault identification algorithm, TRFI-PMC, that achieves robust diagnostic performance in simulated experiments. Specifically, for the networkB8with 40320 nodes, the algorithm maintains superior performance (fault density achieving 25%) across five metrics: accuracy (98.81%), true negative rate (97.81%), false positive rate (2.18%), true positive rate (99.3%), and precision (98.98%). The theoretical results establish fundamental reliability limits forBnarchitectures, while the practical algorithm provides an efficient fault diagnosis solution forn-dimensional bubble-sort network.

As the core infrastructures in the information systems, the data center networks carry a large number of tasks of data processing and storage. In a data center network, intermittent faults are often difficult to be found and dealt with in time because of their hiddenness and uncertainty. Once these faults accumulate to a certain extent, they can cause serious network outages and even lead to the collapse of the entire data center. In order to discover and resolve these potential problems in a timely manner, it is crucial to apply intermittent fault diagnosis, thus ensures the continuous and stable operation of the data center. In this paper, we propose the intermittent fault diagnosabilitytPMCI(Cn) for ann-dimensional data center network CSDC under the Preparata/Metze/Chien model (PMC model) by establishing the fault tolerance of the network. Additionally, under the PMC model, we propose a probabilistic multiple intermittent fault diagnosis algorithm (PMIFDPMC) with time complexityO(nN) by preferentially generating weighted multiple test networks (GWMTN) whereNis the scale of CSDC. Moreover, we apply the algorithm PMIFDPMC to a 7-dimensional CSDC and a real-world dataset of the Internet of Things. Across different scenarios of intermittent fault nodes, we calculate the Accuracy, Recall, FNR, G-mean, and F1-score using various testing iterations. The experimental results demonstrate that, as the number of testing iterations of algorithm PMIFDPMC increases, the quantity of intermittent fault nodes that are correctly diagnosed also increases. This highlights the favorable performance and effectiveness of algorithm PMIFDPMC on the real-world dataset of the Internet of Things.

As the demand for cloud services and data-intensive applications continues to surge, the design of efficient and reliable data center network (DCN) topologies has become increasingly critical. However, traditional DCNs often face challenges of limited scalability, insufficient fault tolerance, and high communication latency. To address these issues, we introduce SFDC, a novel recursive and modular server-centric network topology. SFDC is built on a hierarchical element-layer structure that enables the construction of highly scalable and fault-tolerant networks. The modular design of SFDC supports flexible expansion, allowing for the integration of servers with varying network interface card (NIC) configurations without requiring significant redesigns. Furthermore, SFDC’s design effectively mitigates the growth of network diameter, ensuring low latency even at massive scales. We also propose a routing algorithm, SFRouting, which leverages SFDC’s hierarchical structure to efficiently compute unicast paths, while minimizing routing complexity and enhancing data transmission efficiency. Additionally, we present a multipath routing scheme based on disjoint path construction, which ensures robust communication by providing alternative paths in case of node or link failures, thus enhancing network fault tolerance. Experimental results demonstrate that SFDC outperforms existing DCN topologies such as BCube, DCell, and HS-DCell, exhibiting superior scalability, reduced network diameter, and enhanced fault tolerance while maintaining low latency and stable performance.

The proliferation of interconnection networks has intensified the demand for robust fault diagnosis methodologies. Although existing research focuses predominantly on single-condition diagnosability metrics, these approaches often fail to capture hybrid failure scenarios in large-scale networks. To provide a more comprehensive and realistic resilience assessment, this article introduces a new diagnosability metric termed the$g$-good-neighbor$r$-component diagnosability, denoted by$D_{g,r}(G)$. This metric imposes two stringent constraints on the network after removing a faulty node set$F$: i) the residual network must contain at least$r$connected components, and ii) every fault-free node must retain at least$g$fault-free neighbors. We focus on the hypercube ($Q_{n}$), a prevalent interconnection architecture renowned for its high symmetry, scalability, and fault tolerance. Under the PMC and MM* diagnostic models, we establish the exact value$D_{2,2}(Q_{n}) = 8n - 21$for$n \geq 24$. Leveraging the distinct characteristics of the PMC and MM* models, we propose two scalable fault localization algorithms tailored for hypercube architectures. Simulation experiments on$Q_{n}$networks demonstrate that the proposed framework achieves approximately 100% true positive rate (TPR) when faulty nodes constitute$\leq 20\%$of the network, maintaining TPR$> 98.7\%$even as fault densities approach 50% .

The rapid advancement of semiconductor technology has enabled the development of large-scale multiprocessor systems, which are crucial for high-performance computing systems, data centers, and cloud infrastructures. However, as these systems grow in complexity and scale, the assessment of reliability becomes an urgent issue that needs to be solved, which calls for effective fault diagnosis to detect failures and maintain system performance. To this end, the concept of$(t,k)$-diagnosis was introduced, which detects all failing nodes when their number is at most$k$, and otherwise identifies at least$k$failing nodes per iteration as long as the total number does not exceed$t$. While traditional fault diagnosis strategies are effective, they often encounter the restriction of objective circumstances. For instance, it is improbable that all nodes adjacent to a particular node fail simultaneously. To enhance the efficiency and accuracy of fault diagnosis, this work introduces the$g$-good-neighbor conditional$(t,k)$-diagnosis. It ensures each node owns no fewer than$g$neighbors that are fault-free to match actual environmental requirements. For a general multiprocessor system modeled by$G$, let$\kappa _{g}(G)$be the$g$-good-neighbor connectivity, and define$\delta$as the minimum degree and$\Delta$as the maximum degree of$G$. Under the PMC model, we not only propose two conditional$(t,k)$-diagnosis algorithms, but also prove that$G$is$g$-good-neighbor conditional$(\frac{g|V|-p}{\Delta +g-1}, \min \lbrace p, k_{g}(G)\rbrace)$-diagnosable when fathomed components arise, where$g\leq \lfloor \frac{\Delta +1}{2}\rfloor$and$p\geq 1$, while in the absence of fathomed components,$G$is$g$-good-neighbor conditional$(\frac{g|V| + |B| - 2}{\Delta +g-1}, \kappa _{g}(G))$-diagnosable, where$g\leq \min \lbrace \delta -2,\lfloor \frac{\Delta }{2}\rfloor \rbrace$,$\lambda = (g+1)|B|$,$|B| < \frac{2\lambda (|B| - 1)+(\delta \lambda - \hat{I}(\lambda))|V|}{(\Delta +\delta) \lambda - \hat{I}(\lambda)}$, and$\hat{I}(\lambda)$approximates the number of directed edges among$\lambda$nodes. Experimental results show that conditional$(t,k)$-diagnosis algorithms achieve perfect fault identification with low runtime and good scalability.

Federated learning is vulnerable to model poisoning attacks in which malicious participants compromise the global model by altering the model updates. Current defense strategies are divided into three types: aggregation-based methods, validation dataset-based methods, and update distance-based methods. However, these techniques often neglect the challenges posed by device heterogeneity and asynchronous communication. Even upon identifying malicious clients, the global model may already be significantly damaged, requiring effective recovery strategies to reduce the attacker's impact. Current recovery methods, which are based on historical update records, are limited in environments with device heterogeneity and asynchronous communication. To address these problems, we introduce FedHAN, a reliable federated learning algorithm designed for asynchronous communication and device heterogeneity. FedHAN customizes sparse models, uses historical client updates to impute missing parameters in sparse updates, dynamically assigns adaptive weights, and combines update deviation detection with update prediction-based model recovery. Theoretical analysis indicates that FedHAN achieves favorable convergence despite unbounded staleness and effectively discriminates between benign and malicious clients. Experiments reveal that FedHAN, compared to leading methods, increases the accuracy of the model by 7.86%, improves the detection accuracy of poisoning attacks by 12%, and enhances the recovery accuracy by 7.26%. As evidenced by these results, FedHAN exhibits enhanced reliability and robustness in intricate and dynamic federated learning scenarios.

Federated learning, as a distributed learning framework, aims to develop a global model while preserving client privacy. However, heterogeneity of client data leads to fairness issues and reduced performance. Techniques like parameter decoupling and prototype learning appear promising, yet challenges such as forgetting historical data and limited generalization persist. These methods also lack local insights, with locally trained features prone to overfitting, which affects generalization in global parameter aggregation. To address these challenges, we propose FedCPD, a personalized federated learning framework. FedCPD maintains historical information, reduces information loss, and increases personalization through hierarchical feature distillation and cross-layer feature fusion. Moreover, we utilize representation techniques like prototype contrastive learning and prototype alignment to capture diverse client data features, thus improving model generalization and fairness. Experiments show FedCPD outperforms state-of-the-art models, enhancing generalization by up to 10.40% and personalization by up to 4.90%, highlighting its effectiveness and superiority.

Model inversion and adversarial attacks in semantic communication pose risks, such as content leaks, alterations, and prediction inaccuracies, which threaten security and reliability. This paper introduces, from an attacker's viewpoint, a novel framework called RepObE (Representation Learning-Enhanced Obfuscation Encryption Modular Semantic Task Framework) to secure semantic communication. This framework employs dynamic encryption during semantic extraction and feature transmission to hinder attackers from reconstructing data through eavesdropping, thus strengthening system privacy. To combat image communication task challenges, we propose a prototype adversarial collaborative alignment training approach enhanced by representation learning. This method extracts and encodes semantic features while using dynamic perturbation and robust optimization to improve system resilience against adversarial threats. The approach ensures reliable semantic communication in complex environments, maintaining performance while countering attacks using feature obfuscation, adversarial training, and representation learning. Experimental results demonstrate that our method surpasses existing techniques by more than 2% in resisting model inversion attacks on classification tasks. Visually, our method excels with minimal decipherable images for attackers. It also shows a 3% to 5% improvement in countering adversarial attacks on classification tasks.

Optical Data Center Networks (ODCNs) are high-performance interconnect architectures in parallel and distributed computing, providing higher bandwidth and lower power consumption. However, current optical DCNs struggle to achieve both high scalability and incremental scalability simultaneously. In this paper, we propose an extendedExchanged hyperCube, denoted by ExCube, which is a highly scalable network architecture for optical data centers. Firstly, we detail the address scheme and constructing method for ExCube, including exponential, linear, and composite scalability, which can adapt to different scalability requirements. ExCube boasts flexible scalability modes, including exponential, linear, and composite scalability, meeting diverse scalability requirements. In particular, the diameter of ExCube remains unchanged as its size increases linearly, indicating superior incremental scalability. Secondly, an efficient routing algorithm with linear time complexity is presented to determine the shortest path between any two different ToRs in ExCube. Additionally, we propose a per-flow scheduling algorithm based on the disjoint paths to enhance the performance of ExCube. The optical devices in ExCube are identical to those in existing optical DCNs, such as WaveCube and OSA, facilitating its construction. Experimental results demonstrate that ExCube outperforms WaveCube in terms of throughput and reduces data transmission time by 5%-35%. Further analysis reveals that ExCube maintains comparable performance to WaveCube across several critical metrics, including low diameter and link complexity. Compared with advanced networks, the overall cost-effectiveness and energy efficiency of ExCube have been reduced by 36.7% and 46.5%, respectively.

The design and optimization of network topologies play a critical role in ensuring the performance and efficiency of high-performance computing (HPC) systems. Traditional topology designs often fall short in satisfying the stringent requirements of HPC environments, particularly with respect to fault tolerance, latency, and bandwidth. To address these limitations, we propose a novel class of hierarchical networks, termed Hypercube-Structured Hierarchical Networks (HHNs). This architecture generalizes and extends existing architectures such as half hypercube networks and complete cubic networks, while also introducing previously unexplored hierarchical designs. HHNs exhibit several advantages, particularly in high-performance computing. Most notably, their high connectivity enables efficient parallel data processing, and their hierarchical structure supports scalability to accommodate growing computational demands. Furthermore, we present a unicast routing strategy and a broadcast algorithm for HHNs. A fault-tolerant algorithm is also designed based on the construction of disjoint paths. Experimental evaluations demonstrate that HHNs consistently outperform mainstream architectures in critical performance metrics, including scalability, latency, and robustness to failures.

In mobile edge computing (MEC), edge servers and mobile terminals use federated learning distributed architecture to build a deep model, so that terminals can cooperate in training without sharing data. Distributed training requires network virtualization to provide high bandwidth and low latency characteristics to support large-scale parallel computing. Traditional virtual network embedding (VNE) relies on a static network topology, which lacks flexibility and incurs high resource costs during model training. To improve the efficiency of embedding distributed training tasks, we propose a novel Node Selection and Dynamic Topology resource allocation scheme for VNE of distributed training, NSDT-VNE, based on reconfigurable network topology. This algorithm divides the underlying network into static and dynamic topologies, enhancing low latency for small flows while providing high bandwidth for large flows as needed. Additionally, we introduce a two-phase coordinated alternating optimization algorithm that optimizes embedding decisions at both computational and topological levels, ensuring optimal node selection. Overall, NSDT-VNE follows demand-aware network design principles, allowing continuous optimization of the underlying topology. Compared to state-of-the-art heuristic and reinforcement learning-based virtual network algorithms, NSDT-VNE achieves superior performance, with request acceptance rates improving by 6.67% to 25.68% and embedding revenue increasing by approximately 7% to 32%.

Mobile Opportunistic Networks (MONs) often experience frequent interruptions in end-to-end connections, which increases the likelihood of message loss during delivery and makes users more susceptible to various cyber attacks. However, most currently proposed anonymous routing protocols are primarily designed for networks with stable connections, making it challenging to protect user identities in MONs. To address these challenges, we propose FLAG-POR (Forward Legal Anonymous Group Pairing-Onion Routing), a novel anonymous routing protocol specifically tailored to enhance message delivery anonymity and security in MONs. Specifically, we abstract the mobile opportunistic network as a contact graph. By introducing the concept of “groups” into the pairing-onion routing protocol, which encrypts messages and relay nodes layer by layer, we develop a novel group-based pairing-onion routing protocol. This protocol ensures message confidentiality and relay node anonymity, while also improving message forwarding rates, as any node within a group can potentially act as a relay. To ensure message authenticity, we employ the efficient SM2 signing algorithm to generate signatures for the message source. Furthermore, by incorporating parameters such as the public key validity period and master key validity period into the group pairing-onion routing protocol, we achieve forward security in message delivery. We conduct a thorough theoretical analysis of the protocol’s security and performance. The experimental results demonstrate that our FLAG-POR protocol outperforms baseline anonymous protocols in terms of delivery success rate, traceability rate, path anonymity, and node anonymity. Additionally, the FLAG-POR scheme effectively resists three potential threats to the routing system: collusion attack threat, node identification threat, and path identification threat, in any situation.

In recent years, due to the continuous expansion of the scale of multi-processor systems, processor fault diagnosis has become increasingly important in measuring system reliability. Diagnosability of many well-known multiprocessor systems has been extensively studied. Conditional diagnosability is a new system diagnostic measure that inserts an additional condition that all neighbors (adjacent nodes) of any node in the system cannot all fail at the same time. In this report, we evaluate the conditional diagnosability for enhanced hypercubes under the PMC model. We first give several properties about hypercubes and enhanced hypercubes, and then based on these properties, the conditional diagnosability of an$(n,k)$-enhanced hypercube$Q_{n,k}$is proved to be$4n-7$for$n\ge 5$and$k=3$, and to be$4n-3$for$n\ge 6$and$5\le k\le n$.

Fault diagnosability can reflect the actual self diagnosing capability of a multiprocessor system better. However, people usually focus on the overall information and neglect the important local information. In order to reflect the locality of a system at a node better, this paper proposes a novel fault diagnosis strategy, called x-block local fault diagnosability (x-BLFD), where the x-block condition requires more than x connected fault-free nodes. Then, we characterize some important properties about the x-BLFD of multiprocessors interconnected networks under the Preparata/Metze/Chien model (P/M/C), and further propose the x-BLFD in an$f(x)$-extended block network with the minimum$(x+1)$-subnetwork degree at some node. We also establish an approximate algorithm to calculate the x-BLFD of a large-scale diagnosable network at some node, and analyze the experimental performance of large-scale networks. Furthermore, we apply our proposed conclusion to obtain the x-BLFD of 16 well-known networks at some node directly under P/M/C, including dual cubes, hierarchical cubic networks, DQcubes, twisted hypercubes, Bicube networks, crossed cubes, folded hypercubes, k-ary n-cubes, balanced hypercubes, BC graphs,$(n,k)$-star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, split-star networks, data center networks, and$(n,k)$-arrangement graphs. Finally, we compare the x-BLFD with the diagnosability, conditional diagnosability, pessimistic diagnosability, and$t/k$-diagnosability by a large number of detailed numerical analysis. It can be seen that the x-BLFD is greater than all the other types of fault diagnosabilities.

Fault diagnosis is constantly crucial to maintain a high level of multiprocessor systems’ reliability. In multiprocessor systems, global fault diagnosis has been extensively investigated under both deterministic and probabilistic models, while local fault diagnosis has only been committed to the deterministic models, such as PMC model and MM$^*$model. This work focuses on a probabilistic approach for local diagnosis at a node within the mixed structure under the PMC diagnostic model so that the state of this node can be identified correctly by utilizing maximum a posteriori probability. This work is devoted to the quantitative metric on global reliability of multiprocessor systems in terms of local fault probability of node under microscale. The proposed strategy effectively reduces diagnostic delays and enhances system response in practical applications and thus improves the efficiency and accuracy of fault detection. In addition, the probabilistic approach reduces the effect of uncertainty on the fault diagnosis, which in turn improves the reliability and safety of the system. In this work, we first perform a more precise syndrome analysis for this mixed structure under the PMC model by virtue of local testing results, and suggest a modified local diagnosis algorithm calledMLDA. Subsequently, we implement the maximum a posteriori probabilistic local diagnosis algorithm calledMAPPLDAfor the mixed structure under the probabilistic PMC diagnostic model. Finally, numerical simulation results confirm the effectiveness of the syndrome analysis approach and the maximum a posteriori probability approach for the mixed structure when the node failure probability is very small.

As the multiprocessor systems are becoming large-scale, fault-diagnosis is crucial to ensure the reliability of multiprocessor systems. In order to improve the self-diagnosis capability of a multiprocessor system, a pessimistic fault diagnosis scheme such as$t/s$-diagnosis allows some fault-free processors to be mistakenly identified as faulty. All faulty processors in a$t/s$-diagnosable multiprocessor system ($t\leq s$) should be identified into a set with size up to$s$, when the total amount of faulty processors in the system does not exceed$t$. This article focuses on the$t/s$-diagnosis for the$n$-dimensional bijective connection network$X_{n}$. An adaptive$t/s$-diagnosis algorithm APDMM*$t/s$of complexity$O(M(log_{2}\,M)^{2})$under the comparison model is proposed, where$M$is the total amount of nodes in$X_{n}$. Then, the correctness of algorithm APDMM*$t/s$is proved by the fault-tolerant properties of the network itself. Moreover, we calculate the$t/s$-diagnosability of$X_{n}$by theoretical method in mathematics, which is$-\frac{1}{2}y^{2}+(n-\frac{1}{2})y+1$for$2 \leq y \leq n$under comparison model, where$s=-\frac{1}{2}y^{2}+(n-\frac{1}{2})y+y-1$. Furthermore, we apply algorithm APDMM*$t/s$on the hypercube and the real-world network WSN-DS to verify our main results, and analyze the experimental outcomes in terms of true positive rate, false positive rate, accuracy and precision. The experimental results reveal the advantage and high performance of our algorithm APDMM*$t/s$. Besides, we compare the$t/s$-diagnosability of$X_{n}$with traditional accurate diagnosability, and it turns out that as$n$gets larger, the$t/s$-diagnosability of$X_{n}$is significantly better than traditional accurate diagnosability.

With the application and rapid development of high-performance computing and cloud computing technology, the scale of the interconnection network has appeared to grow exponentially. Network attacks have become increasingly sophisticated and stealthy. To reach a high reliable network system, widespread attention has been paid to fault diagnosis. In this article, we put forward a reliable and adaptive self-diagnosis strategy, the$h$-extra$r$-component conditional diagnosability, denoted by$ct_{r}^{h}(G)$. Then, we provide a theoretical derivation to characterize the$h$-extra$r$-component conditional diagnosability of bubble sort networks$B_{n}$under the PMC model. Furthermore, we develop a fast and adaptive fault self-diagnosis algorithm FAFD-PMC to detect all faulty units. Extensive experiments are implemented and applied to synthetic networks and real networks in terms of accuracy (ACCR), true negative rate, false positive rate, recall, and precision, which demonstrates the ACCR/efficiency of our algorithm.

The underlying topology of the interconnection network of parallel and distributed systems is usually modelled by a simple connected graph$G$. In order to quantitatively analyze the reliability and fault tolerance of these networks more accurately, this study introduces a novel topology parameter. The$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(G)$of$G$, if any, is the smallest cardinality of faulty link set, whose malfunction yields a disconnected graph with at least$r+1$connected components, and with the neighboring edges of any vertex being at least$g$. When designing and maintaining parallel and distributed systems, the hypercube network$Q_{n}$is one of the most attractive interconnection network models. This article offers a unified method to derive an upper bound for$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(Q_{n})$of$Q_{n}$. When$n\geq 4$, this upper bound is proved to be tight for$1\leq 2^{g}\cdot r\leq 2^{\lfloor \frac{n}{2}\rfloor }$or$r=2^{k_{0}}$,$0\leq k_{0}< \lfloor \frac{n}{2}\rfloor$,$0\leq g\leq n-2k_{0}-1$. The conclusions for the$g$-good-neighbor edge-connectivity of$Q_{n}$from Xu and the$(r+1)$-component edge-connectivity of$Q_{n}$from Zhao et al. are contained as corollaries of our main results for$r=1$,$0\leq g\leq n-1$and$1\leq r\leq 2^{\lfloor \frac{n}{2}\rfloor }$,$g=0$, respectively.

The$(f_{1},f_{2})$-bounded symmetric comparison ($(f_{1}, f_{2})$-BSC) model, proposed by Fuhrman and Nussbaumer in 1996, is a hybrid of the symmetric comparison model and asymmetric one, which assumes that at most$f_{1}$processors fail while the upper threshold of faulty processors producing identical outcomes is$f_{2}$. Based on the$(f_{1},f_{2})$-BSC model, a novel model, abbreviated as the$f$-BSC model, is proposed by dropping the restriction on$f_{1}$but highlighting the hypothesis on maximum number of faulty processors producing identical outcomes is$f$. As a generalization of this model, a variant of MM$^*$model abbreviated as the$f$-BMM$^*$model is proposed by adding an upper threshold$f$to the number of faulty processors producing identical comparison outcomes, which are executed by a faulty comparator on two faulty neighbouring processors. Under this restriction, fewer possible syndromes are generated and therefore faulty processors can be diagnosed faster and more accurately. Subsequently, we present diverse characterizations regarding system-level diagnosis under the two new models. Moreover, we further establish the metric correlation between$g$-good-neighbor ($g$-GN) diagnosability under$f$-BMM$^*$model and$R^{g}$-connectivity of general networks. Finally, the$g$-GN diagnosabilities under$f$-BMM$^*$model are characterized among five preeminent interconnection networks.

The Augmented Intelligence of Things (AIoT) is an emerging technology that combines augmented intelligence with the Internet of Things (IoT) to facilitate advanced decision-making processes. In this paper, we focus on the detection of vehicle trajectory anomalies in a vehicle-road collaboration system by AIoT, aiming to improve the traffic safety and road operation efficiency. We transmit collaboration data collected by sensors to an IoT server, which enables the effective data analysis for vehicle trajectory information. We propose a self-supervised learning augmented intelligence algorithm to achieve precise and efficient detection of trajectory anomalies. First, we models the traffic road network as a topology graph. Subsequently, we sample the relevant subgraph contexts for each target node through a random walk algorithm. And the subgraphs with higher intimacy scores are selected as the contextual background to be input along with the target node. After that, the anomaly score of each target node is computed through the generative learning module and the contrastive learning module. To evaluate the effectiveness of our anomaly detection approach, we initially conduct pre-training of the model using four widely utilized graph machine learning datasets. The experimental results reveal that our approach surpasses previous methods in the accuracy of identifying graph anomaly nodes. In addition, we carry out our approach on two real traffic datasets with high accuracies of 86.47% and 85.2%, respectively. This result demonstrates the effectiveness of our proposed approach in detecting trajectory anomalies in real traffic scenarios.

Connectivity is one of important parameters for the fault tolerant of an interconnection network. In 1996, Fàbrega and Fiol proposed the concept of g-extra connectivity. A subset of vertices S is said to be a cutset if G−S is not connected. A cutset S is called an Rg-cutset, where g is a non-negative integer, if every component of G−S has at least g+1 vertices. If G has at least one Rg-cutset, the g-extra connectivity of G, denoted by κg(G), is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first obtain the exact value of g-extra connectivity for the lexicographic product of two general graphs. Next, the upper and lower sharp bounds of g-extra connectivity for the Cartesian product of two general graphs are given. In the end, we apply our results on grid graphs and 2-dimensional generalized hypercubes.

International audience

With the rapid growth of the number of processors in a multiprocessor system, faulty processors occur in it with a probability that rises quickly. The probability of a subsystem with an appropriate size being fault-free in a definite time interval is a significant and practical measure of the reliability for a multiprocessor system, which characterizes the functionality of a multiprocessor system well. Motivated by the study of subgraph reliability, as well as the attractive structure and fault tolerance properties of$(n, k)$-arrangement graph$A_{n, k}$, we focus on the subgraph reliability for$A_{n, k}$under the probabilistic fault model in this article. First, we investigate intersections of no more than four subgraphs in$A_{n, k}$, and classify all the intersecting modes. Second, we focus on the probability$P(q, A_{n, k}^{n-1, k-1})$with which at least one$(n-1, k-1)$-subarrangement graph is fault-free in$A_{n, k}$, when given a uniform probability$q$with which a single vertex is fault-free, and we establish the$P(q, A_{n, k}^{n-1, k-1})$by adopting the principle of inclusion–exclusion under the probabilistic fault model. Finally, we study the probabilistic fault model involving a nonuniform probability with which a single vertex is fault-free, and we prove that the$P(q, A_{n, k}^{n-1, k-1})$under both models is very close to the asymptotic value by both theoretical arguments and experimental results.

Endogenous security has the ability to discover, eliminate, and solve internal security problems and hidden dangers within the network, and is a superior technology to ensure future network security. The$t/k$-diagnosis strategy, as a strong and adaptive self-diagnosis strategy, is an important part for ensuring endogenous security. Moreover, the folded hypercube ($FQ_{n}$) as a data transmission network (e.g., optical network) topology offers new potential for the construction of large-scale, high data throughput, and low-latency systems, such as computing network, human-cyber-physical systems, and smart grid. However, there are few studies on endogenous security based on$FQ_{n}$networks. Therefore, this article designs an adaptive system-level fault self-diagnosis strategy, namely Fast t/k-Diagnosis Under Maeng-Malek Model (Ftk-DIAG-MM*) to diagnosis the faulty vertices in$FQ_{n}$network under the Maeng-Malek model (MM* mod). Then, we provide a proof of the algorithm correctness theoretically by the fault tolerance of$FQ_{n}$network. It is derived by theoretical derivation that the$t/k$-diagnosability inherent to the$FQ_{n}$network is$(n+1)\break(k+1)-k(k+3)/2$. The simulation experiments demonstrate that the designed Ftk-DIAG-MM* strategy can correctly diagnose all vertices within the range allowed by the diagnosability, and still has a great performance when it exceeds the range allowed by the diagnosability. It greatly enhances the fault diagnosis capability of$FQ_{n}$network in the circumstance of misdiagnosing a few vertices, which provides an important theoretical basis for the reliability and endogenous security of$FQ_{n}$networks.

The growing demand for high-performance computing and the acceleration of information processing have brought multiprocessor systems into the era of E-class computing. The reliability of interconnection networks built on multiprocessor systems is facing severe challenges with the rapid growth of the networks' scale. For example, a large-scale processor failure may disconnect the entire network and result in the appearance of many different components. Rapid fault diagnosis has great advantages in industry, especially in real-time systems, which means that rapid diagnosis of fault processors is particularly important. However, the fault diagnosis capability in a network is closely related to the amount of components that the network can tolerate in its application. The diagnosis method of faulty processors, which cause many components is called component diagnosis. In particular,$ct_{g}(G)$refers to the maximum number of faulty processors meeting the$g$-component condition that can be diagnosed in network$G$under certain system-level diagnostic model. In this article, based on the indistinguishability of the constructed set and linear multiple faults analysis technology, we propose the 2, 3-component diagnosabilities of star graph network$S_{n}$under P-M-C-M. Moreover, we propose a novel$g$-component$t$-diagnosable algorithm FCFDSn innovatively to diagnose all faulty processors, and we implement the algorithm FCFDSn on both synthetic data and real data. Furthermore, we verify the availability/efficiency of algorithm FCFDSn in terms of true positive rate, true negative rate, and accuracy rate.

The reliability of interconnection network ordinarily is measured by two significant indexes, namely, connectivity and diagnosability. The qualitative and quantitative reliability analysis relies on the choice of an appropriate mathematical modeling and assumptions consistent with the actual situation. The cyclic connectivity is a well-established index to evaluate the reliability of interconnection network. For a network$\mathbb{G}$, we use$\kappa _{c}(\mathbb{G})$to denote cyclic connectivity of$\mathbb{G}$, which is the minimum size of the node cut set$D$such that$\mathbb{G}-D$is disconnected and at least two of its components have cycles. Based on the cyclic connectivity, cyclic diagnosability ($ct(\mathbb{G})$) is proposed to measure the self-diagnostic capability of the networks. Up to this day, the cyclic connectivity of some special networks has been determined successfully, but the cyclic diagnosability of a great deal of networks is still up in the air. In this work, we investigate the measurable relationship between cyclic connectivity and 2-good connectivity under certain restrictions. Furthermore, we characterize the cyclic diagnosability of a class of networks in terms of character commonality of the networks. To be more specific, we show that$ct(\mathbb{G})=\kappa _{c}(\mathbb{G})+(l-k)$under the PMC model (PMC-M) and the MM$^\ast$model (MM$^\ast$-M), where$l$is the regular degree of network and$l\geq 3, 1\leq k< l$are constant. Then, we directly determine the cyclic diagnosability of hypercubes, locally twisted cubes, and alternating group networks. Finally, we compare the cyclic diagnosability of the network with other kinds of restricted diagnosabilities. The results show that cyclic diagnosability has excellent self-diagnostic capability.

Automatic liver tumor detection from computed tomography (CT) makes clinical examinations more accurate. However, deep learning-based detection algorithms are characterized by high sensitivity and low precision, which hinders diagnosis given that false-positive tumors must first be identified and excluded. These false positives arise because detection models incorrectly identify partial volume artifacts as lesions, which in turn stems from the inability to learn the perihepatic structure from a global perspective. To overcome this limitation, we propose a novel slice-fusion method in which mining the global structural relationship between the tissues in the target CT slices and fusing the features of adjacent slices according to the importance of the tissues. Furthermore, we design a new network based on our slice-fusion method and Mask R-CNN detection model, called Pinpoint-Net. We evaluated proposed model on the Liver Tumor Segmentation Challenge (LiTS) dataset and our liver metastases dataset. Experiments demonstrated that our slice-fusion method not only enhance tumor detection ability via reducing the number of false-positive tumors smaller than 10mm, but also improve segmentation performance. Without bells and whistles, a single Pinpoint-Net showed outstanding performance in liver tumor detection and segmentation on LiTS test dataset compared with other state-of-the-art models.

The most popular tools for predicting pathogenicity of single amino acid variants (SAVs) were developed based on sequence-based techniques. SAVs may change protein structure and function. In the context of van der Waals force and disulfide bridge calculations, no method directly predicts the impact of mutations on the energies of the protein structure. Here, we combined machine learning methods and energy scores of protein structures calculated by Rosetta Energy Function 2015 to predict SAV pathogenicity. The accuracy level of our model (0.76) is higher than that of six prediction tools. Further analyses revealed that the differential reference energies, attractive energies, and solvation of polar atoms between wildtype and mutant side-chains played essential roles in distinguishing benign from pathogenic variants. These features indicated the physicochemical properties of amino acids, which were observed in 3D structures instead of sequences. We added 16 features to Rhapsody (the prediction tool we used for our data set) and consequently improved its performance. The results indicated that these energy scores were more appropriate and more detailed representations of the pathogenicity of SAVs.

BCube is a well-known recursively defined network structure. It provides multiple low-diameter paths and good fault-tolerance for data center networks (DCNs). Its distributed routing algorithm, BCube Source Routing (BSR), can be deployed rapidly and conveniently to build multiple parallel path sets. But in the worst case, BSR may suffer from flow collisions and waste$50\%$of the capacity of each BCube link. In this paper, to decrease collisions and improve bandwidth utilization, we supplement the BCube topology with a central master computer and design two centralized dynamic parallel flow scheduling algorithms: CDPFS and CDPFSMP, for single-path and multi-path respectively. We focus on finding the least congested path for each flow by analyzing the information about the state of the global network. Furthermore, we allocate those paths to each flow in parallel. The simulation result shows that our proposed algorithms take advantage of BCube structure and deliver high-performance solutions for load balancing problems, which have improved 44.1% of the throughput in random bijective traffic pattern and 36.2% of throughput in data shuffle compared with BSR algorithm.

The traveling salesman problem (TSP) has been studied for many years. In particular, the multimodal optimization of the TSP is important for practical applications, because decision-makers can select the best candidate based on current conditions and requirements. In the Euclidean TSP, there are$n$points in$\mathbb {R}^{d}$space with Euclidean distance between any two points, that is,$d(x, y) =||x-y||_{2}$. The goal is to find a tour of minimum length visiting each point. In this article, we only focus on the case that$d=2$. Recently, in order to efficiently handle the multimodal optimization of the TSP, some methods have been developed to deal with it. Nevertheless, these methods usually perform poorly for large-scale cases. In this article, we propose a niching regression adaptive memetic algorithm (MA) to handle the multimodal optimization of the Euclidean TSP. We use the MA as the baseline algorithm and incorporate the neighborhood strategy to maintain the population diversity. In addition, we design a novel regression partition initialization and adaptive parameter control to enhance our algorithm, and propose the concept of the redundant individual to improve the search efficiency. To validate the performance of the proposed algorithm, we comprehensively conduct experiments on the multimodal optimization of TSP benchmark and the well-known TSPLIB library. The experimental results reveal that the proposed method outperforms other methods, especially for large-scale cases.

The fault diagnosability of a network indicates the self-diagnosis ability of the network, thus it is an important measure of robustness of the network. As a neoteric feature for measuring fault diagnosability, the r -component diagnosability ct r (G) of a network G imposes the restriction that the number of components is at least r in the remaining network of G by deleting faulty set X , which enhances the diagnosability of G . In this article, we establish the r -component diagnosability for n -dimensional hierarchical cubic network HCN n , and we show that, under both PMC model and MM* model, the r -component diagnosability of HCN n is rn -½( r -1) r +1 for n ≥ 2 and 1≤ r≤ n-1 . Moreover, we introduce the concepts of 0-PMC subgraph and 0-MM* subgraph of HCN n . Then, we make use of 0-PMC subgraph and 0-MM* subgraph of HCN n to design two algorithms under PMC model and MM* model, respectively, which are practical and efficient for component fault diagnosis of HCN n . Besides, we compare the r -component diagnosability of HCN n with the extra conditional diagnosability, diagnosability, good-neighbor diagnosability, pessimistic diagnosability, and conditional diagnosability, and we verify that the r -component diagnosability of HCN n is higher than the other types of diagnosability.

With the rapid increase of the number of processors in multiprocessor systems and the fast expansion of interconnection networks, the reliability of interconnection network is facing severe challenges, where the fast recognition of fault processors is crucial. In practice, most of the processor failures are intermittent faults. In this article, we first determine the intermittent fault diagnosability$t_{I}^{PMC}(S_{n}^{2})$of$n$-dimensional split-star network$S_{n}^{2}$under the PMC model. In addition, we propose a fast intermittent fault probabilistic diagnosis algorithm FIFPDPMC to identify the nodes with intermittent fault in the$n$-dimensional split-star network$S_{n}^{2}$under the PMC model, and we calculated the time complexity of the algorithm FIFPDPMC. Then we implement the algorithm FIFPDPMC in the IoT-based wireless sensor network (IoTWSN) and a randomly generated network (RGN) under different number of nodes with intermittent fault, and we evaluate the performance and efficiency of the algorithm FIFPDPMC in terms of accuracy, precision, recall (TPR), F1, G-mean, FPR, TNR and FNR. Experimental results show that, as the number of stages of executing the algorithm FIFPDPMC increases, the number of nodes with intermittent fault being diagnosed by the algorithm FIFPDPMC increases, which implies that the algorithm FIFPDPMC has good performance and efficiency in both IoTWSN and RGN.

The matroidal connectivity and conditional matroidal connectivity are novel indicators to measure the real faulty tolerability. In this paper, for the$n$-dimensional alternating group graph$AG_{n}$, the structure properties and (conditional) matroidal connectivity are studied based on the dimensional partition of$E(AG_{n})$. We prove that for$S\subseteq E(AG_{n})$under some limitation on the number of faulty edges in each dimensional edge set, if$|S|\leq (n-1)!-1$, then$AG_{n}-S$is connected. We study the value of matroidal connectivity and conditional matroidal connectivity of$AG_{n}$. Furthermore, simulations have been carried out to compare the matroidal connectivity with other types of conditional connectivity in$AG_{n}$. The simulation result shows that the matroidal connectivity significantly improves these known fault-tolerant capability of alternating group graphs.

In order to evaluate the reliability of a multiprocessor system, the fault diagnosability was introduced and utilized as a significant indicator. In the study of fault diagnosability, researchers usually concentrate on the diagnosability of the global system but ignore its local information. However, the local information also plays a crucial role in the reliability of a multiprocessor system. Thus, an innovative concept of fault diagnosability, called$y$-fault-free-block local fault diagnosability, is put forward to study the fault diagnosability of a multiprocessor system at local vertex, where the$y$-fault-free-block condition requires more than$y$connected vertices. In this article, we characterize several important properties about the$y$-fault-free-block local fault diagnosability of a multiprocessor interconnection network under the MM* model and propose its$y$-fault-free-block local fault diagnosability at local vertex. Furthermore, we apply our results to some well-known networks, and we obtain their$y$-fault-free-block local fault diagnosabilities at local vertex directly under the MM* model, including bijective connection graph, star graph, and$(n,k)$-star graph. Finally, we compare the$y$-fault-free-block local fault diagnosability of a graph at local vertex with other types of diagnosability, including the diagnosability, conditional diagnosability, good-neighbor diagnosability, and pessimistic diagnosability. It can be seen that the$y$-fault-free-block local fault diagnosability at vertex is larger than all the other types of diagnosability.

Intermittent faults are common in daily life and industrial manufacture, which have been drawing much attention from both academia and industry. In practice, intermittent faults will pose a great threat to system performance and equipment safety. Because of the randomness and unpredictability of intermittent faults, it is a great challenge to diagnose them. The fault diagnosis strategy under system-level diagnostic model plays a very important role in measuring the endogenous network security without prior knowledge, which can significantly enhance the self-diagnosing capability of network. However, as the networks become large-scale and complicated, the fault diagnosis using full syndromes from a system-level diagnostic model seems to reach its bottleneck. In this article, we first determine that the intermittent fault diagnosability of a general$r$-regular network$G$under comparison model is$(t^{\text{Intermittent}}(G))^{M}=r-2$. This results can be directly applied to 18 well-known networks. Then, we propose a reliable neural network enabled intermittent fault diagnosis algorithm RNNIFDCom to solve the problem of fault identification with partial syndromes for a general$r$-regular network$G$under comparison model. Finally, we implement our proposed algorithm RNNIFDCom in different networks and analyze its performance under different number of faulty nodes in terms of true positive rate, true negative rate, false positive rate, and false negative rate. The experimental results verify the theoretical results and show the advantage of our proposed algorithm RNNIFDCom.

Cloud services are experiencing a remarkable increase in the number of users and the resource required over the past few years. Thus, it has become a great challenge for the internet vendors to make a robust framework to serve the customers with low cost and delay. Congestion control is one of the essential topics of routing algorithms in cloud data center networks. In this paper, we propose a weighted optimal scheduling scheme WSPR for congestion control in cloud data center networks which prevents the congestion in advance with the global view so that it can make good use of vacant network resources. We choose BCube as our network model and modify the network topology to fit software-defined networks so as to have a full view of the topology. First, we design the SP graph which contains all shortest paths between a source server and a destination server. Second, we propose WSPR to allocate the most appropriate path to each flow for congestion control. We implement a system to simulate a data center, and evaluate our proposed scheme WSPR by comparing WSPR with other classical methods. The experimental results demonstrate that our proposed scheme WSPR has the best performance in terms of the maximum delay, average delay, and throughput among all compared methods.

A human contact network (HCN) consists of individuals moving around and interacting with each other. In HCN, it is essential to detect malicious users who break the data delivery through terminating the data delivery or tampering with the data. Since malicious users will pay more but gain less when breaking the data delivery of opportunistic contacts, we focus on the non-opportunistic contacts that occur more frequently and stably. It is observed that people contact with each other more frequently if they have more social features in common. In this paper, we build up topology structure for HCN based on social features, and propose a graph theoretical comparison detection model to perform malicious users detection. Then we present an adaptive detection scheme based on Hamiltonian cycle decomposition. Also, we define comparison-0-string and comparison-1-string to improve the detection efficiency. Moreover, we perform scenario simulations on real data to realize the detected process of malicious users. Experiments show that, when the number of malicious users is bounded by the dimension of HCN, our scheme has a detection rate of 100% with both false positive rate and false negative rate being 0%, and the running cost is also very low when compared to baseline approaches. When the number of malicious users exceeds the bound, the detection rate of our scheme decreases slowly, while the false positive rate and false negative rate increase slowly, but they are still better than the baseline approaches.

Considerable sequence data are produced in genome annotation projects that relate to molecular levels, structural similarities, and molecular and biological functions. In structural genomics, the most essential task involves resolving protein structures efficiently with hardware or software, understanding these structures, and assigning their biological functions. Understanding the characteristics and functions of proteins enables the exploration of the molecular mechanisms of life. In this paper, we examine the problems of protein classification. Because they perform similar biological functions, proteins in the same family usually share similar structural characteristics. We employed this premise in designing a classification algorithm. In this algorithm, auxiliary graphs are used to represent proteins, with every amino acid in a protein to a vertex in a graph. Moreover, the links between amino acids correspond to the edges between the vertices. The proposed algorithm classifies proteins according to the similarities in their graphical structures. The proposed algorithm is efficient and accurate in distinguishing proteins from different families and outperformed related algorithms experimentally.

Cyberspace is not a “vacuum space”, and it is normal that there are inevitable viruses and worms in cyberspace. Cyberspace security threats stem from the problem of endogenous security, which is caused by the incompleteness of theoretical system and technology of the information field itself. Thus it is impossible and unnecessary for us to build an “aseptic” cyberspace. On the contrast, we must focus on improving the “self-immunity” of network. Literally, endogenous security is an endogenous effect from its own structural factors rather than external ones. The$t/k$-diagnosis strategy plays a very important role in measuring endogenous network security without prior knowledge, which can significantly enhance the self-diagnosing capability of network. As far as we know, few research involves$t/k$-diagnosis algorithm and$t/k$-diagnosability of interconnection networks under MM* model. In this article, we propose a fast$f(r,k+1)/k$-diagnosis algorithm of complexity$O(Nr^2)$, say$G$MIS$k$DIAGMM*, for a general$r$-regular network$G$under MM* model by designing a 0-comparison subgraph$M_0(G)$, where$N$is the size of$G$. We determine that the$t/k$-diagnosability$(t(G)/k)^M$of$G$under MM* model is$f(r,k+1)$by$G$MIS$k$DIAGMM* algorithm. Moreover, we establish the$(t(G)/k)^M$of some interconnection networks under MM* model, including BC networks,$(n,l)$-star graph networks, and data center network DCells. Finally, we compare$(t(G)/k)^M$with diagnosability, conditional diagnosability, pessimistic diagnosability, extra diagnosability, and good-neighbor diagnosability under MM* model. It can be seen that$(t(G)/k)^M$is greater than other fault diagnosabilities in most cases.

Fault diagnosability is utilized as a significant measure that reflects the reliability of a multiprocessor system. However, people frequently pay close attention to the entire systems diagnosability while ignoring the systems important local information. The m-fault-free-neighbor local fault diagnosability (for short, m-FFNLFD) is a novel indicator, which describes the diagnosability of a system at a local node with m fault-free neighbors. In this paper, we propose the m-FFNLFD of general networks at local node under the Preparata Metze Chien model. Moreover, we also characterize some important properties of m-FFNLFD of a multiprocessor system under the comparison model. Furthermore, we apply our proposed conclusions to directly obtain the m-FFNLFD of 11 well-known networks under PMC-M and MM*-M, including hypercubes, locally twisted cubes, k-ary n-cubes, crossed cubes, twisted hypercubes, exchanged hypercubes, star graphs, (n, k)-star graphs, (n, k)-arrangement graphs, data center network DCells and BCDCs. Finally, we compare the m-FFNLFD with both diagnosability and conditional diagnosability, and it is shown that the m-FFNLFD is greater than all the other fault diagnosabilities.

Thet/kt/k-diagnosabilityandhh-extra connectivityare regarded as two important indicators to improve the network reliability. The t/k-diagnosis strategy can significantly improve the self-diagnosing capability of a network at the expense of no more thankfault-free nodes being mistakenly diagnosed as faulty. Theh-extra connectivity can tremendously improve the real fault tolerability of a network by insuring that each remaining component has no fewer than h+1 nodes. However, there is few result on the inherent relationship between these two indicators. In this article, we investigate the reason that caused the serious flawed results in (Liu, 2020), and we propose a diagnosis algorithm to establish the t/k-diagnosability for a large-scale connected networkGunder the PMC model by considering its h-extra connectivity. Let κh(G) be the h-extra connectivity of G. Then, we can deduce that G is κh(G)/h-diagnosable under the PMC model with some basic conditions. All κh(G)faulty nodes can be correctly diagnosed in the large-scale connected network G and at most h fault-free nodes would be misdiagnosed as faulty. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. We will apply the newly found relationship to directly obtain the κh(G)/h-diagnosability of a series of well known networks, including hypercubes, folded hypercubes, balanced hypercubes, dual-cubes, BC graphs, star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, alternating group graphs, split-star networks, k-ary n-cubes and (n,k)-star graphs.

With the emergence of the Big Data era, as multiprocessor systems consisting of multiple processors play a vital role in big data analytics, we are prompted to explore the qualitative and quantitative metric to characterize the reliability of the systems. As the size of the multiprocessor systems grows, the probability of the occurrence of failing processors increases. One metric of the macroscopic reliability of a system is the measure of the collective effect when its subsystems are out of function. The subsystem reliability of a system is the quantitative metric that a fault-free subsystem of specific size is operational as before with the occurrence of individual faults. Although some networks have the same order and similar topologies, there are differences in their subsystem reliabilities. In this work, we focus on the comparison of two distinct topologies of$k$-ary$n$-cube networks with the same order and calculate the robustness of reliability bounds of$k$-ary$n$-cube networks. We analytically show that the subsystem reliability is negatively correlated with the dimension$n$, even if two subsystems of$Q_{n}^{k}$are of the same order. That is, the smaller$n$is, the larger subsystem reliability of$Q_{n}^{k}$will be. This work provides a theoretical methodology to choose the more dependable topology of$k$-ary$n$-cube networks with the same order. Finally, we apply some numerical simulations to validate the results we established.

For interconnection network losing processors, it is considerable to calculate the number of vertices in the maximal component in the surviving network. Moreover, the component connectivity is a significant indicator for reliability of a network in the presence of failing processors. In this article, we first prove that when a set$M$of at most$3n-7$processors is deleted from an$n$-star graph, the surviving graph has a large component of size greater or equal to$n!-|M|-3$. We then prove that when a set$M$of at most$4n-9$processors is deleted from an$n$-star graph, the surviving graph has a large component of size greater or equal to$n!-|M|-5$. Finally, we also calculate the$r$-component connectivity of the$n$-star graph for$2\leq r\leq 5$.

Reliability evaluation of multiprocessor systems is of great significance to the design and maintenance of these systems. As two generalizations of traditional edge connectivity, extra edge connectivity and component edge connectivity are two important parameters to evaluate the fault-tolerant capability of multiprocessor systems. Fast identifying the extra edge connectivity and the component edge connectivity of high order remains a scientific problem for many useful multiprocessor systems. In this article, we determine the$h$-extra edge connectivity of the 3-ary$n$-cube$Q_n^3$for$h\in [1, \frac{3^n-1}{2}]$. Specifically, we divide the interval$[1, \frac{3^n-1}{2}]$into some subintervals and characterize the monotonicity of$\lambda _h(Q_n^3)$in these subintervals and then deduce a recursive closed formula of$\lambda _h(Q_n^3)$. Based on this formula, an efficient algorithm with complexity$O(\log _3\,N)$is designed to determine the exact values of$h$-extra edge connectivity of the 3-ary$n$-cube$Q_n^3$for$h\in [1, \frac{3^n-1}{2}]$completely. Moreover, we also determine the$g$-component edge connectivity of the 3-ary$n$-cube$Q_n^3(n\geq 6$) for$1\leq g\leq 3^{\lceil \frac{n}{2}\rceil }$.

The features of Internet of Things (IoT) is highly useful and have becoming popular recently. More and more countries and companies have starting to deploying numerous types of sensors for monitoring their machine or energy consuming. Smart grid systems are equipped with lots of IoT devices or sensors for data collecting and analyzing, for example, smart meters. However, these devices communicate frequently with the data center to report their measurement could burden the bandwidth and crashing or blocked our Internet infrastructure. Also, the smart grid may be attacked by foraged message because of unauthorized message sending and receiving. To resolve this problem, this study proposes a data compression method which integrated digital signature technique to protect the smart grid from being attack. This paper also conducts the experiment with the REDD dataset to show our outperformed results.

Abstract In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$ NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$ NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$ c > 1 , Matching Cut is $${\mathsf {NP}}$$ NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ ϵ > 0 , Matching Cut remains $${\mathsf {NP}}$$ NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$ δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree $$\delta \ge 3$$ δ ≥ 3 in $$O^*(\lambda ^n)$$ O ∗ ( λ n ) time, where $$\lambda$$ λ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$ x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$ O ∗ ( 1 . 0099 n ) on graphs with minimum degree $$\delta \ge 469$$ δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$ 1 < c < 4 and $$c^{\prime }\ge 0$$ c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$ δ ≥ 1 c n - c ′ .

The attackers in a network may have a tendency of targeting on a group of clustered nodes, and they hope to avoid the existence of significant large communication groups in the remaining network, such as botnet attack, DDoS attack, and Local Area Network Denial attack. Current various kinds of connectivity do not well reflect the fault tolerance of a network under these attacks. This observation inspires a new measure for network reliability to resist the block attack by taking into account of the dispersity of the remaining nodes. Let$G$be a network,$C\subset V(G)$and$G[C]$be aconnected subgraph. Then$C$is called an$h$h-faulty-blockof$G$if$G-C$is disconnected, and every component of$G-C$has at least$h+1$nodes. The minimum cardinality over all$h$-faulty-blocks of$G$is called$h$h-faulty-block connectivityof$G$, denoted by${FB}\kappa _h(G)$. In this article, we determine${FB}\kappa _h(Q_n)$for$n$-dimensional hypercube$Q_n$($n\geq 4$), a classic interconnection network. We establish that${FB}\kappa _h(Q_n)=(h+2)n-3h-1$for$0\leq h\leq 1$, and${FB}\kappa _h(Q_n)=(h+2)n-4h+1$for$2\leq h\leq n-2$, respectively. Larger$h$-faulty-block connectivity implies that an attacker will have to stage an attack to a bigger block of connected nodes, so that each remaining components will not be too small, which will in turn limit the size of large components. In other words, there will not be great disparity in sizes between any two remaining components, and hence there will less likely be a significantly large remaining communication group. The larger the$h$-faulty-block, the more difficult for an attacker to achieve that goal. As a consequence, the resistance of the network against the attacker will increase. Our experiments also show that as$h$increases, the$h$-faulty-block gets larger, and the size disparity between any two remaining components decreases. In turn, as expected, the size of the largest remaining communication group becomes smaller.

The protein folding problem (PFP) is an important issue in bioinformatics and biochemical physics. One of the most widely studied models of protein folding is the hydrophobic-polar (HP) model introduced by Dill. The PFP in the three-dimensional (3D) lattice HP model has been shown to be NP-complete; the proposed algorithms for solving the problem can therefore only find near-optimal energy structures for most long benchmark sequences within acceptable time periods. In this paper, we propose a novel algorithm based on the branch-and-bound approach to solve the PFP in the 3D lattice HP model. For 10 48-monomer benchmark sequences, our proposed algorithm finds the lowest energies so far within comparable computation times than previous methods.

A network's diagnosability is the maximum number of faulty vertices that the network can discriminate solely by performing mutual tests among vertices. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. The h-extra fault diagnosability is an important and widely accepted diagnostic strategy as a new measure of diagnosability, which guarantees that the scale of every component is at least h+1 in the remaining system. Moreover, it increases the allowed faulty vertices, hence enhancing the diagnosability of the network. There have been lots of state-of-the-art literatures concerning the h-extra fault diagnosability. Although there are some methods to theoretically prove the extra fault diagnosability of some other well-known networks under MM* model, these methods have some serious flaws when there exists a 4-cycle in these networks. In this article, we investigate the reason that caused the flawed results in some references, and we derive a different, broadly applicable, and complete fault tolerant method to establish the extra fault diagnosability in an n-dimensional alternating group graph AGnunder MM* model. The complete fault tolerant method adopts combinatorial properties and linearly many fault analysis to conquer the core of our proofs. Moreover, we compare the extra fault diagnosability of AGnwith various types of fault diagnosability, including the diagnosability, strong diagnosability, conditional diagnosability, t/k-diagnosability, and pessimistic diagnosability. It can be seen that the extra fault diagnosability is greater than all the other types of fault diagnosability.

For interconnection network losing processors, usually, when the surviving network has a large connected component, it can be used as a functional subsystem without leading to severe performance degradation. Consequently, it is crucial to characterize the interprocessor communication ability and efficiency of the surviving structure. In this article, we prove that when a subset$D$of at most$6n-17$processors is deleted from an$n$-dimensional alternating group graph$\text{AG}_n$, there exists a largest component with cardinality greater or equal to$|V(\text{AG}_n)|-|D|-3$for$n\geq 6$in the remaining network, and the union of small components is, first, an empty graph; or, second, a 3-cycle, or an edge, or a 2-path, or a singleton; or, third, an edge and a singleton, or two singletons. Then, we prove that when a subset$D$of at most$8n-25$processors is deleted from$\text{AG}_n$, there exists a largest component with cardinality greater or equal to$|V(\text{AG}_n)|-|D|-5$for$n\geq 6$in the remaining network, and the union of small components is, first, an empty graph; or, second, a 5-cycle, or a 4-path, or a 4-claw, or a 4-cycle, or a 3-path, or a 3-claw, or a 3-cycle, or a 2-path, or an edge, or a singleton; or, third, a 4-cycle and a singleton, or a 3-path and a singleton, or a 3-claw and a singleton, or a 2-path and a singleton, two edges, an edge and a singleton, or two singletons; or, fourth, two edges and a singleton, or a 2-path and two singletons, or an edge and two singletons, or three singletons.

Abstract In this paper, we propose a new digragh model for system level fault diagnosis, which is called the $(f_1,f_{2})$-bounded Preparata–Metze–Chien (PMC) model (shortly, $(f_1,f_{2})$-BPMC). The $(f_1,f_{2})$-BPMC model projects a system such that the number of faulty processors that test faulty processors with the test results $0$ does not exceed $f_{2}$$(f_2\leq f_{1})$ provided that the upper bound on the number of faulty processors is $f_{1}$. This novel testing model compromisingly generalizes PMC model (Preparata, F.P., Metze, G. and Chien R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Tran. Electron. Comput.,EC-16, 848–854) and Barsi–Grandoni–Maestrini model (Barsi, F., Grandoni, F. and Maestrini, P. (1976) A theory of diagnosability of digital systems. IEEE Trans. Comput.C-25, 585–593). Then we present some characterizations for one-step diagnosibility under the $(f_1,f_{2})$-bounded PMC model, and determine the diagnosabilities of some special regular networks. Meanwhile, we establish the characterizations of $f_1/(n-1)$-diagnosability and three configurations of $f_1/(n-1)$-diagnosable system under the $(f_1,f_{2})$-BPMC model.

MapReduce is a crucial framework in the cloud computing architecture, and is implemented by Apache Hadoop and other cloud computing platforms. The resources required for executing jobs in a large data center vary according to the job types. In general, there are two types of jobs, CPU-bound and I/O-bound, which require different resources but run simultaneously in the same cluster. The default job scheduling policy of Hadoop is first-come-first-served and therefore, may cause unbalanced resource utilization. Considering various job workloads, numerous job allocation schedulers were proposed in the literature. However, those schedulers encountered the data locality problem or unreasonable job execution performance. This study proposes a job scheduler based on a dynamic grouping integrated neighboring search strategy, which can balance the resource utilization and improve the performance and data locality in heterogeneous computing environments.

Fault diagnosis of processors has played an essential role when evaluating the reliability of multiprocessor systems. In many novel multiprocessor systems, their diagnosability has been extensively explored. Conditional diagnosability is a useful measure for evaluating diagnosability by adding a further condition that all neighbors of every node in the system do not fail at the same time. In this paper, we study the conditional diagnosability of n-dimensional alternating group networks ANn under the PMC model, and obtain the results tc(AN4) = 5, and tc(ANn) = 6n - 17 for n > 5. In addition, for the isomorphism property between ANnand Sn,kwith k = n-2, namely (n, n - 2)-star graphs Sn,n-2, the above results can be extended to Sn,n-2, and we have tc(S4,2) = 5 and tc(Sn,n-2) = 6n - 17 for n > 5. It is worth noting that the conditional diagnosability is about six times the degree of ANn andSn,n-2, which is very different from general networks with a multiple of four.

The h-extra node-connectivity of a graph G is the size of a minimal node-set, whose removal will disconnect G, but each remaining component has no fewer h + 1 nodes. Based on h-extra node-connectivity, the h-extra conditional fault-diagnosability of networks has been proposed for a better, more realistic measure of networks' fault-tolerability. It is the maximal x such that G is h-extra conditionally x-fault-diagnosable. This paper will establish a relationship between the h-extra node-connectivity and h-extra conditional fault-diagnosability for a regular graph G, under the classic PMC diagnostic model. We will apply the newly found relationship to a variety of well-known regular networks, to directly obtain their h-extra conditional fault-diagnosability. The significance of the paper's work is that it relates the notions of h-extra node-connectivity and h-extra conditional fault-diagnosability, so that a regular network's h-extra conditional fault-diagnosability may be known once its h-extra node-connectivity is known.

An advanced metering infrastructure (AMI) consists of a meter data management system, a concentrator, and a meter. Each component can communicate with all other components, through either wired or wireless connections. In an AMI local area networks, various protocols, such as Zigbee, WiFi, and power-line communication, have the potential to be used in AMI communication. Of these protocols, Zigbee offers self-constructing networks, low costs, and superior safety levels. Zigbee is adopted as the LAN communication protocol because of these advantages in this study. In a LAN, a concentrator may encounter many emergent situations, any of which might cause the concentrator to lose its network connection function. Consequently, additional time is required for network construction, which tends to reduce the reliability of smart grids with LANs of this type. To solve these issues, this paper proposes the fast join process (FJP) and enhanced FJP to shorten the time of Zigbee network construction. The strategy employed in this paper is to let every meter join a specified concentrator. The proposed FJP does not scan unnecessary channels. By simplifying association message exchange, we further propose a new method called the enhanced FJP. By using these methods, not only can message flow be managed easily, but the time of network construction can also be improved.

Cloud computing has become increasingly popular model for delivering applications hosted in large data centers as subscription oriented services. Hadoop is a popular system supporting the MapReduce function, which plays a crucial role in cloud computing. The resources required for executing jobs in a large data center vary according to the job type. In Hadoop, jobs are scheduled by default on a first-come-first-served basis, which may unbalance resource utilization. This paper proposes a job scheduler called the job allocation scheduler (JAS), designed to balance resource utilization. For various job workloads, the JAS categorizes jobs and then assigns tasks to a CPU-bound queue or an I/O-bound queue. However, the JAS exhibited a locality problem, which was addressed by developing a modified JAS called the job allocation scheduler with locality (JASL). The JASL improved the use of nodes and the performance of Hadoop in heterogeneous computing environments. Finally, two parameters were added to the JASL to detect inaccurate slot settings and create a dynamic job allocation scheduler with locality (DJASL). The DJASL exhibited superior performance than did the JAS, and data locality similar to that of the JASL.

Fault diagnosis has played a major role in measuring the reliability of multiprocessor systems. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel property of measuring diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of (n, k)-star graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of (n, k)-star graphs under the PMC model, and show that it is 1) ⌈2/n⌉ -1 for n ≥ 4 and k = 1, and 2) n + 3k - 6 for 2 ≤ k ≤ n-3.

Assume that there are at most t faulty vertices. A system is conditionally (t, k)-diagnosable if at least k faulty vertices (or all faulty vertices if fewer than k faulty vertices remain) can be identified in each iteration under the assumption that every vertex is adjacent to at least one fault-free vertex. Let κc(G) be the conditional vertex connectivity of G, which measures the vertex connectivity of G according to the assumption that every vertex is adjacent to at least one fault-free vertex. Let Δ(G) be the maximum degrees of the given graph G. When a graph G satisfies the condition that for any pair of vertices with distance two has at least two common neighbors in G, we show the following two results: 1) An r-regular network G containing N vertices is conditionally (r+1/n+√(r+1)(r-1)/4x(G)N)2, kc(G)) diagnosable, where r ≥ 3 and N ≥ 4x(G)/(r+1)(25r-9). 2) An irregular network G containing N vertices is conditionally (Δ(G)+1/N-1, kc(G))-diagnosable. By applying the above results to multiprocessor systems, we can measure conditional (t, k)-diagnosabilities for augmented cubes, folded hypercubes, balanced hypercubes, and exchanged hypercubes.

The g-restricted connectivity (g-RC) is the minimum vertex-set size of a network, whose deletion disconnects the network such that each remaining vertex has at least g neighbors in its respective component. The g-RC is a deterministic indicator of tolerability of a network with failing processors. The g-good-neighbor fault diagnosability (g-GNFD) is the largest set size of correctly identified faulty vertices in a network such that any good vertex has no fewer g good neighbors. This paper establishes the relationship between g-RC and g-GNFD of general regular networks, first under the PMC model and second under the MM* model. Moreover, this paper directly gives the g-GNFD of some well-known special networks by their g-RC and our proposed relationship.

Given a graph G=(V, E), an s-plex S\subseteq V is a vertex subset such that for v\in S the degree of v in G[S] is at least |S|-s. An s-plex bipartition \mathcal{P}=(V_1, V_2) is a bipartition of G=(V, E), V=V_1\uplus V_2, satisfying that both V_1 and V_2 are s-plexes. Given an instance G=(V, E) and a parameter k, the s-Plex Bipartition problem asks whether there exists an s-plex bipartition of G such that min{|V_1|, |V_2|\}\leq k. The s-Plex Bipartition problem is NP-complete. However, it is still open whether this problem is fixed-parameter tractable. In this paper, we give a fixed-parameter algorithm for 2-Plex Bipartition running in time O*(2.4143^k). A graph G = (V, E) is called defective (p, d)-colorable if it admits a vertex coloring with p colors such that each color class in G induces a subgraph of maximum degree at most d. A graph G admits an s-plex bipartition if and only if the complement graph of G, \bar{G}, admits a defective (2, s-1)-coloring such that one of the two color classes is of size at most k. By applying our fixed-parameter algorithm as a subroutine, one can find a defective (2,1)-coloring with one of the two colors of minimum cardinality for a given graph in O*(1.5539^n) time where n is the number of vertices in the input graph.

IP lookup and routing table update affect the speed at which a router forwards packets. This study proposes a new data structure for dynamic router tables used in IP lookup and update, called the Multi-inherited Search Tree (MIST). Partitioning each prefix according to an index value and removing the relationships among prefixes enables performing IP lookup operations efficiently. Because a prefix trie is used as a substructure, memory can be consumed and dynamic router-table operations can be performed efficiently. Experiments using real IPv4 routing databases indicated that the MIST uses memory efficiently and performs lookup, insert, and delete operations effectively.

The$t/k$-diagnosis strategy can significantly enhance the system’s self-diagnosing capability at the expense of no more than$k$fault-free processors (vertices) being mistakenly diagnosed as faulty under the PMC model. It is a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis on multiprocessor systems. It can detect up to$t$faulty processors (vertices) which might include at most$k$misdiagnosed processors (vertices), where$k$is typically a small number. In the case$k\ge 1$, to our knowledge, there is no known$t/k$-diagnosis algorithm for general regular networks. In this paper, we first propose a general$t/k$-diagnosis ($k\ge 1$) algorithm for some$m$-regular networks. These$m$-regular networks satisfying some conditions could establish the$t/k$-diagnosis algorithm, say$t/k$-$G$-$DIAG$, to determine the$t/k$-diagnosability. The complexity of this algorithm is only$O(N\log N)$(when$N\ge 2^m$) or$O(Nm)$(when$N< 2^m$) where$N$is the number of vertices in the network. Second, we present a complete proof that the network$G$is actually$t/k$-diagnosable. Finally, we establish the$t/k$-diagnosability ($1\le k\le 3$) of some regular networks, including an$n$-dimensionalalternating group graph, an$n$-dimensionalSplit-Star Network, a$l^n$-hypermeshand an$(n,l)$-star graph, which are well-known interconnection networks proposed for multiprocessor systems.

Profiling cancer molecules has several advantages; however, using microarray technology in routine clinical diagnostics is challenging for physicians. The classification of microarray data has two main limitations: 1) the data set is unreliable for building classifiers; and 2) the classifiers exhibit poor performance. Current microarray classification algorithms typically yield a high rate of false-positives cases, which is unacceptable in diagnostic applications. Numerous algorithms have been developed to detect false-positive cases; however, they require a considerable computation time. To address this problem, this study enhanced a previously proposed gene expression graph (GEG)-based classifier to shorten the computation time. The modified classifier filters genes by using an edge weight to determine their significance, thereby facilitating accurate comparison and classification. This study experimentally compared the proposed classifier with a GEG-based classifier by using real data and benchmark tests. The results show that the proposed classifier is faster at detecting false-positives.

Connectivity is a classic measure for fault tolerance of a network in the case of vertices failures. Extra connectivity and restricted connectivity are two important indicators of the robustness of a multi-processor system in presence of failing processors. An interconnection network's diagnosability is an important measure of its self-diagnostic capability. The conditional diagnosability is widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbors of any node in a multiprocessor system. In this paper, we analyze the combinatorial properties and fault tolerance ability for the Split-Star Network, denoted by Sn2, a well-known interconnection network proposed for multiprocessor systems, establish the g-extra connectivity, where 1 ≤ g ≤ 3. We also determine the h-restricted connectivity (h = 1; 2), and prove that the conditional diagnosability of Sn2(n ≥ 4) is 6n - 16 under the comparison model, which is about three times of the Sn2's traditional diagnosability. As a product, the strong diagnosability of Sn2is also obtained.

Extra connectivity is an important indicator of the robustness of a multiprocessor system in presence of failing processors. The g-extra conditional diagnosability and the t/m-diagnosability are two important diagnostic strategies at system-level that can significantly enhance the system's self-diagnosing capability. The g-extra conditional diagnosability is defined under the assumption that every component of the system removing a set of faulty vertices has more than g vertices. The t/m-diagnosis strategy can detect up to t faulty processors which might include at most m misdiagnosed processors, where m is typically a small integer number. In this paper, we analyze the combinatorial properties and fault tolerant ability for an (n, k)-arrangement graph, denoted by An,k, a well-known interconnection network proposed for multiprocessor systems. We first establish that the An,k's one-extra connectivity is (2k - 1) (n - k) - 1 (k ≥ 3, n ≥ k + 2), two-extra connectivity is (3k - 2)(n - k) - 3 (k ≥ 4, n ≥ k + 2), and three-extra connectivity is (4k - 4)(n - k) - 4 ( k ≥ 4, n ≥ k + 2 or k ≥ 3, n ≥ k + 3), respectively. And then, we address the g-extra conditional diagnosability of An,kunder the PMC model for 1 ≤ g ≤ 3. Finally, we determine that the (n, k)-arrangement graph An,kis [(2k - 1)(n - k) - 1]/1-diagnosable (k ≥ 4, n ≥ k + 2), [(3k - 2)(n - k) - 3]/2-diagnosable (k ≥ 4, n ≥ k + 2), and [(4k - 4)(n - k) - 4]/3-diagnosable (k ≥ 4, n ≥ k + 3) under the PMC model, respectively.

(t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and repaired in each iteration when there are at most t faulty processors, where t ≥ k. Based on the assumption that each vertex is adjacent to at least one fault-free vertex, the conditional (t, k)-diagnosis of graphs was investigated by using the comparison diagnosis model. Lower bounds on the conditional (t, k)-diagnosability of graphs were derived, and applied to obtain the following results. 1) Symmetric d-dimensional grids are conditionally (N/2d+1 -1, 2d -1)-diagnosable when d ≥ 2 and N (the number of vertices) ≥ 4d. 2) Symmetric d-dimensional tori are conditionally (1/5 (N + min{8/5 N2/3, 2N-20/15} - 2), 6)-diagnosable when d = 2 and N ≥ 49 and ( N/2d+1 -1, 4d-2)-diagnosable when d ≥ 3 and N ≤ 4d. 3) Cube-connected cycles are conditionally (N/4 - 1, 4)-diagnosable. 4) k-ary trees are conditionally (N/k+1 - 1)-diagnosable.

We consider a generalization of both the classic Steiner tree problem and the terminal Steiner tree problem. Given a complete graph${ G = (V,E)}$with a metric cost function${ c:E \rightarrow {\BBQ_ \geq }}$and two proper subsets$ R \subset V$and$ R^\prime \subseteq R$, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in$\it R$such that all vertices in$R^\prime$must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum cost in$G$. The previously best-known approximation ratio of the problem is$ 2\rho$, where$\bf \rho$is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from$ 2\rho$to$ 2\rho - {\rho \over {3\rho - 2}} - f$, where$f$is a non-negative function whose value is between 0 and$ \rho - {\rho \over {3\rho - 2}}$.

Processor fault diagnosis has played an essential role in measuring the reliability of a multiprocessor system. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of Cayley graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model and show that it is 4n-11 for n ≥ 4 except for the n -dimensional star graph for which it has been shown to be 8 n -21 for n ≥ 5 (refer to Chang and Hsieh [2014]).

A graph G is called k-edge-fault edge-bipancyclic (k-edge-fault edge-r-pancyclic) if after deleting k edges from G, every edge in the resulting graph lies in a cycle of every even length from 4 to IV (G)I (a cycle of every length from r to IV(G)I), inclusively. In this paper, given two graphs G and H, which satisfy some specific properties, the edge-fault edge-bipancyclicity and edge-fault edge-r-pancyclicity (r is decided on the properties of G and H) of Cartesian product graphs G x Hare efficiently evaluated. The obtained results are applied to two multiprocessor systems, the nearest neighbor mesh hypercubes and generalized hypercubes, both of which belong to Cartesian product graphs.

The (n,k)-star graph, denoted by Sn,k, is an enhanced version of n-dimensional star graphs Sn, that has better scalability than Sn, and possesses several good properties, compared with hypercubes. Diagnosis has been one of the most important issues for maintaining multiprocessor-system reliability. Conditional diagnosability, which is more general than classical diagnosability, measures the multiprocessor-system diagnosability under the assumption that all neighbors of any processor in the system cannot fail simultaneously. In this paper, we investigate the conditional diagnosability of Sn,kfor ( n ≥ 3 and k=1) and ( n ≥ 4 and 2 ≤ k ≤ n) under the comparison diagnosis model.

Given a graph${\mbi{G}}$and a non-negative integer${{g}}$, the${{g}}$-extra connectivity (resp.${{g}}$-extra edge connectivity) of${\mbi{G}}$is the minimum cardinality of a set of vertices (resp. edges) in${\mbi{G}}$, if it exists, whose deletion disconnects${\mbi{G}}$and leaves each remaining component with more than${{g}}$vertices. This study shows that the 3-extra connectivity (resp. 3-extra edge connectivity) of an${\mbi{n}}$-dimensional folded hypercube is${4}{{n}} - {5}$for${{n}} \geq {6}$(resp.${4}{{n}} - {4}$for${{n}} \geq {5}$). This study also provides an upper bound for the${{g}}$-extra connectivity on folded hypercubes for${{g}} \geq {6}$.

Diagnosability is an important metric for measuring the reliability of multiprocessor systems. This article adopts the MM* model and outlines the common properties of a wide class of interconnection networks, called component-composition graphs (CCGs), to determine their diagnosability by using their obtained properties. By applying the results to multiprocessor systems, the diagnosability of hypercube-like networks (including hypercubes, crossed cubes, Möbius cubes, twisted cubes, locally twisted cubes, generalized twisted cubes, and recursive circulants), star graphs, pancake graphs, bubble-sort graphs, and burnt pancake graphs, all of which belong to the class of CCGs, can also be computed.

Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system; the diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability. It includes a condition whereby any fault set cannot contain all the neighbors of any node in a system. In this paper, the conditional diagnosability of star graphs by using the PMC model is evaluated. Several new structural properties of star graphs are derived. Based on these properties, the conditional diagnosability of an$n$-dimensional star graph is determined to be$8n-21$for$n\geq 5$.

A graph$G$is$k$-fault Hamiltonian (resp. Hamiltonian-connected) if after deleting at most$k$vertices and/or edges from$G$, the resulting graph remains Hamiltonian (resp. Hamiltonian-connected). Let$\delta_{i}$be the minimum degree of$G_{i}$for$i=0$, 1. Given$(\delta_{i}-2)$-fault Hamiltonian and$(\delta_{i}-3)$-fault Hamiltonian-connected graph$G_{i}$for$i=0, 1$, this study shows that the Cartesian product network$G_{0} \times G_{1}$is$(\delta_{0}+\delta_{1}-2)$-fault Hamiltonian and$(\delta_{0}+\delta_{1}-3)$-fault Hamiltonian-connected. We then apply the result to determine the fault-tolerant Hamiltonicity and Hamiltonian-connectivity of two multiprocessor systems, namely the generalized hypercube and the nearest neighbor mesh hypercube, both of which belong to Cartesian product networks. This study also demonstrates that these results are worst-case optimal with respect to the number of faults tolerated.

High-performance routers require high-speed IP address lookup to achieve wire-speed packet forwarding. This study proposes a new data structure, the Multi-Index Hybrid Trie (MIHT), for dynamic router table designs. This data structure was constructed by combining the useful characteristics of the B+tree and priority trie. IP lookup operations can be performed efficiently by associating each prefix with a key value in the MIHT. Furthermore, because the required tree height and number of prefixes were reduced, dynamic router table operations were performed efficiently using the MIHT. To reduce the memory requirement, each prefix stored its corresponding suffix in a node of the MIHT, rather than storing a full prefix. Experiments using IPv4 and IPv6 routing databases indicated that the proposed data structure has efficient memory usage and performs well for lookup, insertion, deletion operations. This study reports the results of the experiments performed to compare the proposed data structure with other structures using the benchmark IPv4 and IPv6 prefix databases AS1221, AS4637, AS6447, AS65000, AS1221*, and AS6447* with 407,067, 219,581, 417,995, 406,973, 12,155, and 12,278 prefixes, respectively, where AS1221* and AS6447* are IPv6 BGP routing tables.

(t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let \kappa (G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t,k)-diagnosability for a class of component-composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω (h), κ (G))-diagnosable, where h= {(2m-2m-1)/2m-1×lg(m-1)} if|V(G)|≥m! if 2m-1≤|V(G|<;m! and κ(G) and |V(G)|denote the node connectivity and the number of nodes in G, respectively. Based on this result, the (t,k)-diagnosability of several multiprocessor systems can be computed efficiently.

Processor fault diagnosis plays an important role in measuring the reliability of multiprocessor systems and diagnosing many well-known interconnection networks. Conditional diagnosability is a novel measure of diagnosability that adds the additional condition that any faulty set cannot contain all of the neighbors of any vertex in a system. This study investigates some topological properties of k-ary n-cubes, where k ≥ 4 and n ≥ 4, and shows that the conditional diagnosability of k-ary n-cubes under the comparison diagnosis model is 6n - 5.

Using the comparison diagnosis model, this study proposes some useful sufficient conditions for determining the strong diagnosability ts(G) and the conditional diagnosability tc(G) of a system G. Applying these results to an n-dimensional folded hypercube FQnshows that ts(FQn) = n + 1 for n ≥ 5 and tc(FQn) = 3n - 2 for n ≥ 5. Moreover, tc(FQ3) = 3 and tc(FQ4) = 7.

A system is t/t -diagnosable if, given any collection of test results, the faulty nodes can be isolated to within a set of at most t nodes provided that the number of faulty nodes does not exceed t . Given an N -vertex graph G that is regular with the common degree d and has no cycle of three or four vertices, this study shows that G is (2d − 2)/(2d − 2) -diagnosable if N ≥ 4 d − 30 > 0. Based on this result, the t/t -diagnosabilities of several classes of graphs can be computed efficiently.

An efficient ternary content addressable memory (TCAM) encoding scheme using a binary reflected Gray code (BRGC) and the concept of elementary intervals is presented for efficiently storing arbitrary ranges in TCAM. The proposed layered BRGC range encoding scheme (L-BRGC) groups ranges into BRGC range sets in which each range can be encoded into a single ternary vector. The results of experiments performed on real-life and synthesized rule tables show that L-BRGC consumes less TCAM than all the existing range encoding schemes for all rule tables, except that the direct conversion scheme (EIGC) using elementary intervals and BRGC codes performs best for a small real-life ACL rule table.

A graph G is conditional k-edge-fault Hamiltonian if it remains Hamiltonian after deleting at most k edges and each vertex incident to at least two nonfaulty edges. A graph G is k-edge-fault Hamiltonian-connected if it remains Hamiltonian-connected after deleting at most k edges. This study shows that the conditional edge-fault Hamiltonicity of the Cartesian product network G x H can be efficiently evaluated given two graphs G and H that are edge-fault Hamilton-connected and conditional edge-fault Hamiltonian. This study uses the result to evaluate the conditional edge-fault Hamiltonicity of two multiprocessor systems, the generalized hypercubes and the nearest neighbor mesh hypercubes, both of which belong to Cartesian product networks.

Comparison-based diagnosis is a realistic approach to detect faults in multiprocessor systems. The Maeng, Malek (MM) model for comparison-based diagnosis defines a strategy based on sending the same input (or task) from a processor to some pair of distinct neighboring processors, and then comparing their responses. Sengupta and Dahbura proposed a further modification of the MM model, called the MM* model, in which any processor v has to test another two processors if v is adjacent to them. Sengupta and Dahbura presented a O(N5)-time diagnosis algorithm for general diagnosable systems under the MM* model, where N is the number of processors in the system. By exploiting the cycle decomposition property, we improve the above result by presenting a O(N(log2N)2)-time diagnosis algorithm for a class of hypercube-like networks under the MM* model.

In this paper, a new data structure, called the classified multisuffix trie (CMST), is proposed for designing dynamic router-tables. CMST achieves a better performance than existing data structures because each node can store more than one prefix and the longest matching prefix may be found in an internal node rather than on a leaf. Furthermore, with the classification in each node, the dynamic router-table operations can be performed efficiently. To reduce the memory requirement, we store each prefix's corresponding suffix in a CMST node, instead of storing a full binary string. Based on the CMST, we also propose another data structure, called the Partitioning Classified Multisuffix Trie (PCMST) to reduce the height of the trie and expedite router-table operations. Experiments using real IPv4 routing databases demonstrate that the proposed data structures are efficient in terms of memory usage and it performs well in terms of the average times of the lookup, insert, and delete operations. We report the results of experiments conducted to compare the performance of the proposed data structure with that of other structures using the benchmark IPv4 prefix databases AS4637, AS6447, and AS65000 with 219,581, 296,552, and 226,847 prefixes, respectively.

A graph G = (V, E) is said to be conditional k-edge-fault pancyclic if, after removing k faulty edges from G and provided that each node is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to \V\ inclusive. In this paper, we sketch the common properties of a class of networks called Matching Composition Networks (MCNs), such that the conditional edge-fault pancyclicity of MCNs can be determined from the derived properties. We then apply our technical theorem to show that an m-dimensional hyper-Petersen network is conditional (2m 5)-edge-fault pancyclic.

Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosability of many well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a novel measure of diagnosability by adding an additional condition that any faulty set cannot contain all the neighbors of any node in a system. In this paper, we evaluate the conditional diagnosability for augmented cubes under the PMC model. We show that the conditional diagnosability of an n-dimensional augmented cube is 8n - 27 for n≥5.

Processor fault diagnosis plays an important role in measuring the reliability of multiprocessor systems and the diagnosis of many well-known interconnection networks. The conditional diagnosability, which is more general than the classical diagnosability, is to measure the diagnosability of a multiprocessor system under the assumption that all of the neighbors of any node in the system cannot fail at the same time. This study shows that the conditional diagnosability for k -ary n -cubes under the PMC model is 8 n − 7 for k ≥ 4 and n ≥ 4.

In this paper, we consider two embedding problems in Cartesian product networks: one is the pancycle problem, which involves embedding cycles of various lengths in the given product network; and the other is the panconnectivity problem, which involves embedding paths of various lengths between any pair of distinct nodes in the given product network. We then apply our technical lemmas and theorems to derive new topological properties of two multiprocessor systems, namely, generalized hypercubes and nearest neighbor mesh hypercubes.

The problem of fault diagnosis has been discussed widely, and the diagnosability of many well-known networks has been explored. Strong diagnosability, and conditional diagnosability are both novel measurements for evaluating reliability and fault tolerance of a system. In this paper, some useful sufficient conditions are proposed to determine strong diagnosability, and the conditional diagnosability of a system. We then apply them to show that an n-dimensional augmented cube AQnis strongly (2n -1)-diagnosable for n ≥ 5, and the conditional diagnosability of AQnis 6n - 17 for n ≥ 6. Our result demonstrates that the conditional diagnosability of AQnis about three times larger than the classical diagnosability.

(t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t, k)-diagnosability for a class of component composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m ≥ 4) is (Ω(h),κ(G))-diagnosable, where h= {2m-1× (m-3) × lg(m-1) (m-1)/(m-1)2if 2m-2≤ n(G)m-1× (m-3)/m-1 if n(G) ≥ m!. Based on this result, the (t, k)-diagnosability of several multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs, can be computed efficiently.

IP lookup affects the speed of an incoming packet and the time required to determine which output port the packet should be sent to; hence, it plays an important role in the design of router-tables. In this paper, we propose a new data structure, called a multiprefix trie, for use in designing dynamic router-tables. One key feature of our data structure is that each node can store more than one prefix, which reduces the number of memory accesses. When performing lookup, the structure can search more prefixes in one node and may find the longest matching prefix in an internal node rather than on a leaf. Moreover, when updating the router-table, it does not need to reconstruct the table. As a by-product, the proposed data structure minimizes the time required for dynamic router-table operations, including lookup, insertion, and deletion, and also reduces the number of memory accesses. We report the results of experiments conducted to compare the proposed data structure with other structures using the benchmark IPv4 prefix database AS4637 with 219,581 prefixes.

The planted (l, d)-motif search problem is a mathematical abstraction of the DNA functional site discovery task. In this paper, we propose a heuristic algorithm that can find planted (l, d)-signals in a given set of DNA sequences. Evaluations on simulated data sets demonstrate that the proposed algorithm outperforms current widely used motif finding algorithms. We also report the results of experiments on real biological data sets.

Let F_v be a set of faulty nodes in an n-dimensional hypercube, denoted by Q_n. Also, let F_e be a set of faulty edges in which at least one end-node of each edge is faulty. An edge in Q_n is said to be critical if it is either fault-free or in F_e. In this paper, we prove that, for up to 2n-4 faulty nodes and/or edges, an n-dimensional hypercube contains a fault-free cycle of every even length from 4 to 2^n-2oF_vo in which each node is incident to at least two critical edges. Our result improves on the previously best known results reported in the literature.

Diagnosability is an important metric for measuring the reliability of multiprocessor systems. In this paper, we study the diagnosability of a class of networks, called Two-Matching Composition Networks (2-MCNs), each of which is constructed by connecting two graphs via two perfect matchings. By applying our result to multiprocessor systems, we also compute the diagnosability of folded hypercubes and augmented cubes, both of which belong to two-matching composition networks.

The classic problem of determining the diagnosability of a given network has been studied extensively. Under the PMC model, this paper addresses the problem of determining the diagnosability of a class of networks called (1,2)-Matching Composition Networks, each of which is constructed by connecting two graphs via one or two perfect matchings. By applying our results to multiprocessor systems, we can determine the diagnosability of hypercubes, twisted cubes, locally twisted cubes, generalized twisted cubes, recursive circulants G(2^{n},4) for odd n, folded hypercubes, augmented cubes, crossed cubes, Möbius cubes, and hyper-Petersen networks, all of which belong to the class of (1,2)-matching composition networks.

A graph G is called k-fault Hamiltonian (resp. Hamiltonian-connected) if after deleting at most k vertices and/or edges from G, the resulting graph remains Hamiltonian (resp. Hamiltonian-connected). Let δ(G) be the minimum degree of G. Given a (δ(G) - 2)-fault Hamiltonian/ (δ(G) - 3)-fault Hamiltonian-connected graph G and a (δ(H) - 2)-fault Hamiltonian/(δ(H) - 3)-fault Hamiltonian-connected graph H, we show that the Cartesian product network G × H is (δ(G) + δ(H) - 2)-fault Hamiltonian and (δ(G)+δ(H) - 3)-fault Hamiltonian-connected. We then apply our result to determine the fault-tolerant hamiltonicity and Hamiltonian-connectivity of two multiprocessor systems, namely the generalized hypercube and the nearest neighbor mesh hypercube, both of which belong to Cartesian product networks. We also demonstrate that our results are worst-case optimal with respect to the number of faults tolerated.

A graph G is said to be conditional k-edge-fault pancyclic if after removing k faulty edges from G, under the assumption that each node is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to $|V(G)|$. In this paper, we consider the common properties of a wide class of interconnection networks, called restricted hypercube-like networks, from which their conditional edge-fault pancyclicity can be determined. We then apply our technical theorems to show that several multiprocessor systems, including n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, recursive circulants $G(2^{n},4)$ for odd n, n-dimensional crossed cubes, and n-dimensional twisted cubes for odd n, are all conditional $(2n-5)$-edge-fault pancyclic.

Abstract In this article, we study some topological properties of k‐ary n‐cubes Q . We show that each edge in Q lies on a cycle of every length from k to kn. We also show that Q is both bipanconnected and edge‐bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer. © 2009 Wiley Periodicals, Inc. NETWORKS 2009

Strong diagnosability is a more precise concept for measuring the reliability of multiprocessor systems than the traditional global measurement. In this paper, we study the strong diagnosability of multiprocessor systems under the PMC model. Our main objective is to determinate the strong diagnosability of two wide classes of networks, namely regular networks and product networks, subject to certain conditions. Based on our results, we demonstrate the strong diagnosability of several well-known networks, including variants of hypercubes and many others.

A graph G is called Hamiltonian if there is a Hamiltonian cycle in G. The conditional edge-fault Hamiltonicity of a Hamiltonian graph G is the largest k such that after removing k faulty edges from G, provided that each node is incident to at least two fault-free edges, the resulting graph contains a Hamiltonian cycle. In this paper, we sketch common properties of a class of networks, called matching composition networks (MCNs), such that the conditional edge-fault hamiltonicity of MCNs can be determined from the found properties. We then apply our technical theorems to determine conditional edge-fault hamiltonicities of several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, and n-dimensional hyper Petersen networks. Moreover, we also demonstrate that our technical theorems can be applied to network construction.

We consider fault-tolerant embedding, where an n-dimensional faulty hypercube, denoted byQn, acts as the host graph, and the longest fault-free cycle represents the guest graph. LetFvbe a set of faulty nodes inQn. Also, letFebe a set of faulty edges in which at least one end-node of each edge is faulty, and letFebe a set of faulty edges in which the end-nodes of each edge are both fault-free. An edge inQnis said to be critical if it is either fault-free or inFe. In this paper, we prove that there exists a fault-free cycle of length at least 2n-2|Fv| inQn(nges 3) with |Fe| les 2n-5, and |Fv|+|Fe| les 2n-4 , in which each node is incident to at least two critical edges. Our result improves on the previously best known results reported in the literature, where only faulty nodes or faulty edges are considered.

Abstract In this article, we analyze some edge‐fault‐tolerant properties of the folded hypercube, a variant of the regular hypercube that is obtained by adding an edge to every pair of nodes with complementary addresses. We show that ann‐dimensional folded hypercube is (n− 2)‐edge‐fault‐tolerant Hamiltonian‐connected whenn(≥ 2) is even, (n− 1)‐edge‐fault‐tolerant strongly Hamiltonian‐laceable whenn(≥ 1) is odd, and (n− 2)‐edge‐fault‐tolerant hyper Hamiltonian‐laceable whenn(≥ 3) is odd. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

The notion of diagnosability has long played an important role in measuring the reliability of multiprocessor systems. Such a system is t-diagnosable if all faulty nodes can be identified without replacement when the number of faults does not exceed t, where t is some positive integer. Furthermore, a system is strongly i-diagnosable if it can achieve (t + 1)-diagnosability, except for the case where a node's neighbors are all faulty. In this paper, we investigate the strong diagnosability of a class of product networks, under the comparison diagnosis model. Based on our results, we can determine the strong diagnosability of several widely used multiprocessor systems, such as hypercubes, mesh-connected k-ary n-cubes, torus-connected k-ary n-cubes, and hyper-Petersen networks.

A system is t-diagnosable if all faulty nodes can be identified without replacement when the number of faults does not exceed t, where t is some positive integer. Furthermore, a system is strongly t-diagnosable if it is t-diagnosable and can achieve (t+1)-diagnosable except for the case where a node's neighbors are all faulty. In this paper, we propose some conditions for verifying whether a class of interconnection networks, called matching composition networks (MCNs), are strongly diagnosable under the comparison diagnosis model.

The k-ary n-cube, denoted by Qnk, has been one of the most common interconnection networks. In this paper, we study some topological properties of Qnk. Given two arbitrary distinct nodes x and y in Qnk, we show that there exists an x–y path of every length from [k/2]n to kn− 1, where n ≥ 2 is an integer and k ≥ 3 is an odd integer. Based on this result, we further show that each edge in Qnklies on a cycle of every length from k to kn. In addition, we show that Qnkis both bipanconnected and edge-bipancyclic, where n ≥ 2 is an integer and k ≥ 2 is an even integer.

The star graph has been recognized as an attractive alternative to the hypercube. In this paper, we investigate the hamiltoncity of a n-dimensional star graph. We show that for any n-dimensional star graph (n ≥ 4) with at most 3n − 10 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves the previously best known result where the number of tolerable faulty edges is bounded by 2n − 7. We also demonstrate that our result is optimal with respect to the worst case scenario where every other node of a six-length cycle is incident to exactly n − 3 faulty non-cycle edges.

The locally twisted cube is a variation of hypercube, which possesses some properties superior to the hypercube. In this paper, we investigate the edge-fault-tolerant Hamiltoncity of an n-dimensional locally twisted cube, denoted by LTQn. We show that for any LTQn(n ges 3) with at most 2n - 5 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. We also demonstrate that our result is optimal with respect to the number of faulty edges tolerated.

For a complete graph G = (V, E) with length function l : E rarr R+and two vertex subsets R sub V and R' sube R, a selected-leaf-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R \ R' belong to the leaves of this Steiner tree. The selected-leaf-terminal Steiner tree problem is to find a selected-leaf-terminal Steiner tree T whose total lengths Sigma(u, v)epsiTl(u, v) is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem

A graph is pancyclic if it contains cycles of all lengths. A graph G is node-pancyclic if for every node u, G contains cycles C of all lengths such that u is in C. The twisted cube is an alternative to the popular hypercube network. In this paper, we prove that the twisted cube is node-pancyclic

Abstract This article introduces a new family of Cayley graphs, called k‐degree Cayley graphs, for building interconnection networks. The k‐degree Cayley graph possesses many valuable topological properties, such as regularity with degree k, logarithmic diameter, and maximal fault tolerance. We present an optimal shortest path routing algorithm for the k‐degree Cayley graph. Cycle‐embedding and clique‐embedding are also discussed. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 26–36 2006

A graph G=(V, E) is said to be pancyclic if it contains fault-free cycles of all lengths from 4 to |V| in G. Let F/sub v/ and F/sub e/ be the sets of faulty nodes and faulty edges of an n-dimensional Mobius cube MQ/sub n/, respectively, and let F=F/sub v//spl cup/F/sub e/. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to |V-F/sub v/|. In this paper, we show that MQ/sub n/-F contains a fault-free Hamiltonian path when |F|/spl les/n-1 and n/spl ges/1. We also show that MQ/sub n/-F is pancyclic when |F|/spl les/n-2 and n/spl ges/2. Since MQ/sub n/ is regular of degree n, both results are optimal in the worst case.

This work introduces a new family of Cayley graphs, named the k-valent graphs, for building interconnection networks. It includes the trivalent Cayley graphs (Vadapalli and Srimani, 1995) as a subclass. These new graphs are shown to be regular with the node-degree k, to have logarithmic diameter subject to the number of nodes, and to be k-connected as well as maximally fault tolerant. We also propose a shortest path routing algorithm and investigate some algebraic properties like cycles or cliques embedding.

In the literature, there are quite a few sequential and parallel algorithms to solve problems on distance-hereditary graphs. Two well-known classes of graphs, which contain trees and cographs, belong to distance-hereditary graphs. We consider the vertex-coloring problem on distance-hereditary graphs. Let T/sub d/(|V|, |E|) and P/sub d/d(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree representation of a distance-hereditary graph G=(V,E) on a PRAM model M/sub d/. Our algorithm runs in O(T/sub d/(|V|, |E|)+log|V|) time using O(P/sub d/(|V|, |E|)+|V|/log|V|) processors on M/sub d/. The best known result for constructing a decomposition tree needs O(log/sup 2/ |V|) time using O(|V|+|E|) processors on a CREW PRAM. If a decomposition tree is provided as input, we solve the problem in O(log |V|) time using O(|V|/log |V|) processors on an EREW PRAM. To the best of our knowledge, there is no parallel algorithm for this problem on distance-hereditary graphs.

In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let T d |V|,|E|) and P d (|V|,|E|) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M d . Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(|V|+|E|) time, and solved in parallel in O(T d (|V|,|E|)+log |V|) time using O(P d (|V|,|E|)+|V|log |V|)processors on M d . By constructing a decomposition tree under a CREW PRAM, we also show that T d (|V|,|E|)=O(log 2 |V|) and P d (|V|,|E|)=O(|V|+|E|).

In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log/sup 2/ n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM.

In this paper, we aim to embed longest fault-free paths in an n-dimensional star graph with edge faults. When n/spl ges/6 and there are n-3 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices, exclusive of two exceptions in which at most two vertices are excluded. Since the star graph is regular of degree n-1, n-3 (edge faults) is maximal in the worst case. When n/spl ges/6 and there are n-4 edge faults, a longest fault-free path can be embedded between two arbitrary distinct vertices. The situation of n<6 is also discussed.

Suppose that G is a bipartite graph with its partite sets of equal size. G is said to be strongly Hamiltonian-laceable if there is a Hamiltonian path between every two vertices that belong to different partite sets and there is a path of (maximal) length N - 2 between every two vertices that belong to the same partite set, where N is the order of G. In other words, a strongly Hamiltonian-laceable graph has a longest path between every two of its vertices. In this paper, we show that the star graphs with dimension four or larger are strongly Hamiltonian-laceable. © 2000 john Wiley & Sons, Inc.

The arrangement graph A/sub n,k/, which is a generalization of the star graph (n-k=1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously, the arrangement graph has proved Hamiltonian. In this paper, we further show that the arrangement graph remains Hamiltonian even if it is faulty. Let |F/sub e/| and |F/sub v/| denote the numbers of edge faults and vertex faults, respectively. We show that A/sub n,k/ is Hamiltonian when 1) (k=2 and n-k/spl ges/4, or k/spl ges/3 and n-k/spl ges/4+[k/2]), and |F/sub e/|/spl les/k(n-k)-2, or 2) k/spl ges/2, n-k/spl ges/2+[k/2], and |F/sub e/|/spl les/k(n-k-3)-1, or 3) k/spl ges/2, n-k/spl ges/3, and |F/sub e/|/spl les/k, or 4) n-k/spl ges/3 and |F/sub v/|/spl les/n-3, or 5) n-k/spl ges/3 and |F/sub v/|+|F/sub e/|/spl les/k. Besides, for A/sub n,k/ with n-k=2, we construct a cycle of length at least 1) [n!/(n-k!)]-2 if |F/sub e/|/spl les/k-1, or 2) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub v/|/spl les/k-1, or 3) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub e/|+|F/sub v/|/spl les/k-1, where [n!/(n-k)!] is the number of nodes in A/sub n,k/.

The star graph has been recognized as an attractive alternative to the hypercube. Let F/sub e/ and F/sub /spl nu// be the sets of vertex faults and edge faults, respectively. Previously, Tseng et al. showed that an n-dimensional star graph can embed a ring of length n! if |F/sub e/|/spl les/n-3 (|F/sub /spl nu//|=0), and a ring of length at least n!-4|F/sub /spl nu//| if |F/sub /spl nu//|/spl les/n-3 (|F/sub e/|=0). Since an n-dimensional star graph is regular of degree n-1 and is bipartite with two partite sets of equal size, our result achieves optimality in the worst case.

The arrangement graph A/sub n,k/, which is a generalization of the star graph (n-t=1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously the arrangement graph has proven hamiltonian. In this paper we further show that the arrangement graph remains hamiltonian even if it is faulty. Let |F/sub e/| and |F/sub v/| denote the numbers of edge faults and vertex faults, respectively. We show that A/sub n,k/ is hamiltonian when (1) (k=2 and n-k/spl ges/4, or k/spl ges/3 and n-k/spl ges/4+[k/2]), and |F/sub e/|/spl les/k(n-k-2)-1, or (2) k/spl ges/2, n-k/spl ges/2+[k/2], and |F/sub e/|/spl les/k(n-k-3)-1, or (3) k/spl ges/2, n-k/spl ges/3, and |F/sub 3/|/spl les/k.

We present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree for a distance-hereditary graph which take O(log n) time using O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance-hereditary graph in O(log/sup 2/ n) time using O(n+m) processors on a CREW PRAM.