Modern vehicles rely on ECUs connected over an Intra-Vehicular CAN-bus network to facilitate data exchange. However, in recent times, the quantity of potential attack surfaces for malicious cyberattacks, such as DOS, Fuzzy, etc., has notably surged owing to their amplified connectivity. Unfortunately, the CAN bus solitarily cannot ensure its protection due to its deficiency in security components, leading to grave safety and security issues like disabling the brakes, etc., and hence requires a reliable mechanism for detecting anomalies in the system. To address these challenges, this paper proposes HAVEN, a Hybrid Anomaly Detection System for Intra-Vehicular CAN-bus Communication using combinations of Rule-based with Machine Learning techniques and Neural Networks (Binary and Multiclass Classification forms). The experimental results show that our proposed hybrid models achieve high detection accuracy on different datasets incurring significantly low execution time and high F1-score. This is attributable to the parallel execution and multi-threading nature of the Machine Learning and Neural Networks employed in conjunction with the Rule-based techniques. Upon comparing the results of both models, our evaluation demonstrates that the second model incorporating neural networks yields superior results, establishing its potential as a highly efficient and promising solution and opening future avenues for further research work.

The growing integration of the Internet of Things (IoT), cloud computing, and artificial intelligence (AI) in modern agriculture machinery has revolutionized the food and agriculture sector by significantly improving the efficiency and precision of farming equipment. Global agriculture machinery manufacturers have started adopting and implementing advanced cloud-based platforms and technologies for monitoring machinery and equipment performance and enabling remote diagnostics and updates. However, these platforms largely focus on functional analytics and fleet management, often overlooking critical cybersecurity considerations. As agriculture machinery increasingly relies on interconnected systems, including in-vehicle networks such as Controller Area Networks (CAN), edge computing, and cloud services, the attack surface continues to expand, making cybersecurity an essential component of situational awareness. This paper proposes a real-time 2-tier cybersecurity situational awareness framework for agriculture machinery-based IoT networks (Ag-CSA). The proposed Ag-CSA framework combines an edge-based machine learning anomaly detection system (MLADS) with a cloud-based alert correlation to identify, aggregate, and analyze cyber threats. The framework is validated within an experimental testbed environment using CAN-specific datasets, achieving low prediction latency (<10 ms), high alert confidence (≈84%), and low end-to-end system latency (<400 ms).

The rapid expansion of electric vehicle (EV) technologies and their seamless integration into smart grids herald a significant transition toward sustainable energy practices, highlighting the need to bolster Electric Vehicle Charging Stations (EVCS). These stations, connected through protocols like ISO 15118 and OCPP, ensure secure interactions between EVs, EVCS, and management systems. However, the rise of Internet of Things (IoT) connectivity exposes EVCS to cyber threats, including Distributed Denial of Service (DDoS), Man-in-the-Middle (MitM), and Injection attacks, which threaten the stability of thousands of EVCS and the overall charging infrastructure. In response to these challenges, this paper presents a Federated Learning-based Anomaly Detection System (FL-EVCS), an approach that significantly enhances the cybersecurity framework within EVCS networks. By adopting a federated learning model, FL-EVCS prioritizes data privacy by exchanging model parameters instead of raw data across the network. This method offers a powerful collective defense strategy, considerably enhancing the capabilities of traditional ADS that utilize machine learning algorithms such as KNN, RF, and SVM. In our evaluations, FL-EVCS demonstrated good performance by achieving an accuracy of around 97% and superior F1-scores, compared to traditional ML-based ADS using the CICEVSE2024 dataset. By enhancing EVCS security against cyber threats and supporting EV market growth with a secure user-friendly infrastructure, FL-EVCS markedly increases detection accuracy and efficiency. This approach offers a well-balanced solution for anomaly detection, meeting stringent data privacy requirements and promoting the resilience and expansion of the EVCS ecosystem.

With the evolving characteristics and dynamics of the grid, Solid-State Transformer (SST)-based Power Substations (SSPS) are being proposed as a new solution to effectively incorporate distributed generation and energy storage systems. However, these power converter-based solutions are vulnerable to cyber and physical threats due to their mixed signal characteristics (analog and digital data processing) and communication requirements, leading to severe consequences if the attacks remain undetected and unmitigated. To identify potential threats, this paper proposes a real-time supervised machine learning-based anomaly detection system (ML-ADS) for detecting Electromagnetic Side-channel Noise Injection (EM-SNI) attacks on SSTs. The proposed system can detect anomalies with fine granularity, meeting real-time latency requirements for effective mitigations. The model was deployed and optimized for evaluation into a realistic hardware-in-the-loop (HIL) SST testbed environment. Our experimental evaluation demonstrates a promising performance with high accuracy (more than 99%) and low false-negative rates (less than 1%), with feasible latency (≈200ms).

This work-in-progress paper evaluates Federated Intrusion Response Network for Grids (FIRNet-G), an implementation of the Autonomous Intelligent Cyberdefense Agent (AICA) architecture, using graph machine learning for anomaly detection in power distribution grids. The study focuses on identifying cyber attacks in DNP3 traffic within a simulated multi-substation power utility environment. It integrates DNP3 traffic parsing into FIRNet-G’s knowledge graph and augments the Iowa State University PowerCyberSec SCADA testbed for DNP3 traffic monitoring. A federated neural network model classifies DNP3 attacks, with each FIRNet-G agent observing its local environment and generating node embeddings using GraphSAGE. The paper describes the AICA architecture, its implementation, and introduces a novel node embedding approach using a custom Separating Hashing Vectorizer of Variable Length (SHVVL) algorithm. Future work includes incorporating the Flower.ai federated learning framework, implementing differential privacy, and comparing FIRNet-G’s performance to traditional intrusion detection systems. The research also explores link prediction, anomaly detection based on embedding distances, and integrating vulnerability information to enhance attack detection and prediction. This study advances the development of autonomous cyberdefense systems for critical infrastructure, addressing the challenges of securing power distribution grids against evolving cyber threats.

IEC 61850-based Substation Automation Systems (SAS) are essential to the modern grid as they ensure secure and efficient operation and maintain overall system safety. However, there has been an increase in cybersecurity concerns about IEC 61850 SAS due to its lack of security features. A deeper understanding of the system-wide impacts on the grid due to cyber attacks is crucial to develop necessary risk assessments and cybersecurity countermeasures. This paper presents a systematic methodology for the impact characterization of cyber attacks on IEC 61850-enabled substation buses and analyzes the corresponding impact on the grid through the grid voltage performance. To identify relevant attack vectors, NESCOR vulnerability classes are utilized. Two data integrity attacks (single and pulsating trip) in different scenarios (isolated and coordinated) are executed on three types of substation buses (generation, transmission, and load). A comprehensive assessment of the impacts is conducted within a cyber-physical system (CPS) hardware-in-the-loop (HIL) testbed environment utilizing a modified Kundur’s four-machine, two-area power system. The transient voltage stability of the sensitive bus voltages is examined using the voltage profile index (VPI) as an impact characterization metric. The experimental results for our model reveal that data integrity attacks on generation and load buses exhibit a higher severity than on transmission buses. The severity also varies with the type and location of the attack.

There have been several public demonstrations of attacks on connected vehicles showing the ability of an attacker to take control of a targeted vehicle by injecting messages into their Controller Area Network (CAN) bus. In this article, using injected speed reading and Revolutions Per Minute (RPM) reading messages in in-motion vehicle, we examine the ability of the Pearson correlation and the unsupervised learning methods k-means clustering and Hidden Markov Model (HMM) to differentiate ’no-attack’ and ’under-attack’ states of the given vehicle. We found that the Pearson correlation distinguishes the two states, the k-means clustering method has an acceptable accuracy but high false positive rate and HMM detects attacks with acceptable detection rate but has a high false positive in detecting attacks from speed readings when there is no attack. The accuracy of these unsupervised learning methods are comparable to the ones of the supervised learning methods used by CAN bus Intrusion Detection System (IDS) suppliers. In addition, the article shows that studying CAN anomaly detection techniques using off-vehicle test facilities may not properly evaluate the performance of the detection techniques. The results suggest using other features besides the data content of the CAN messages and integrate knowledge about how the Electronic Control Units (ECUs) collaborate in building effective techniques for the detection of injection of fabricated message attacks.

There are two fundamental expectations from cloud-IoT applications using sensitive and personal data: 1) utility and 2) privacy. Due to the complex nature of cloud-IoT ecosystems, there is a growing concern about data utility at the cost of privacy. While the current state-of-the-art encryption schemes protect users' privacy, they preclude meaningful computations on encrypted data. Thus, the question remains “how can IoT device users benefit from cloud computing without worrying about privacy and security?” Cloud service providers (CSPs) can leverage fully homomorphic encryption (FHE) schemes to build privacy-preserving services. However, there are challenges in adopting them for cloud-IoT devices. Thus, to foster real-world adoption of FHE-based solutions, we propose a framework called proxy reciphering as a service. We leverage schemes, such as distributed servers, secret sharing, FHE, and chameleon hash functions to tailor a solution that enables long-term privacy-preserving computations for encrypted IoT-device data and is secure even after a device-key compromise. We evaluate the framework by developing a testbed and measuring the latencies with real-world ECG records from TELE ECG database. We also analyze the security properties against major cyber threats. We observe that: 1) the computation and communication latencies are acceptable, and the security gains outweigh the latencies introduced; 2) the throughput of the reciphering proxy servers can be increased with preprocessing; and 3) a key-refresh scheme can limit the postcompromise attack exposure window. We infer that proxy reciphering as a service is a practical, secure, scalable and an easy-to-adopt framework for long-term privacy-preserving cloud computations for cloud-IoT applications.

The Internet of Things (IoT) and the cloud are expanding technologies with many security vulnerabilities. With at least one major data leak every year since 2004, the public's concern for data privacy has given rise to legislation known as the General Data Protection Regulation (GDPR) in the European Union. Assured deletion, the process by which deleted data on the cloud is made permanently unrecoverable, is a strong defense against data leaks. The existing assured deletion techniques fall into two categories: cryptographic protection and secure overwriting. Cryptographic protection blocks malicious preservation of data but leaves the data subject to cryptanalysis. Secure overwriting prevents cryptanalysis attacks but leaves the data subject to malicious preservation of data. Furthermore, both cryptographic protection and secure overwriting are too expensive for direct application to IoT technology. To address these problems, we proposed a hybrid assured deletion technique which combines cryptographic protection with secure overwriting on a semi- trusted cloud host. By moving the computation operations of assured deletion from the IoT device to a semi-trusted cloud host, we reduce the latency of the operations while relieving the IoT device of the processing overhead. By combining cryptographic protection with secure overwriting, the outsourced data is safeguarded from both vulnerabilities. We evaluated the proposed technique for latency performance and attack exposure. The results show that the latency performance of the hybrid technique was comparable to that of the cryptographic protection, and its overall attack surface is better than both the cryptographic protection and secure overwrite solutions.

Cybersecurity and resiliency of wide-area monitoring, protection, and control (WAMPAC) applications is critically important to ensure secure, reliable, and economical operation of the bulk power system. WAMPAC relies heavily on the security of measurements and control commands transmitted over wide-area communication networks for real-time operational, protection, and control functions. The current “N-1” security criterion for grid operation is inadequate to address malicious cyber events; therefore, it is important to fundamentally redesign WAMPAC and to enhance energy management system applications to make them attack resilient. In this paper, we present three key contributions to enhance the cybersecurity and resiliency of WAMPAC. First, we describe an end-to-end attack-resilient cyber-physical security framework for WAMPAC applications encompassing the entire security life cycle including risk assessment, attack prevention, attack detection, attack mitigation, and attack resilience. Second, we describe a defense-in-depth architecture that incorporates attack resilience at both the infrastructure layer and the application layer by leveraging domain-specific security approaches at the WAMPAC application layer in addition to traditional cybersecurity measures at the information technology infrastructure layer. Third, we discuss several attack-resilient algorithms for WAMPAC that leverage measurement design and cyber-physical system model-based anomaly detection and mitigation along with illustrative case studies. We believe that the research issues and solutions identified in this paper will open up several avenues for research in this area. In particular, the proposed framework, architectural concepts, and attack-resilient algorithms would serve as essential building blocks to transform the “fault-resilient” grid of today into an “attack-resilient” grid of the future.

The papers in this special issue focus on deeply embedded systems and the challenges of cyper-physical security systems. Deeply-embedded systems (deployed in human body, with computer programs sending and receiving sensitive data and performing data mining for the decisions) are increasingly popular, but the security and privacy issues are not fully understood and studied. For example, issues relating to the confidentiality/integrity/availability/privacy of implantable and wearable medical devices, secure and private big data analytics, acquisition, and storage, privacy-preserving data mining, secure machine learning, cyber physical systems security, and security of hardware and software systems used for databases (with diverse societal contexts) are critical, and can be challenging to address due to their unique constraints and usage model. Existing systems for such computations would need to be transparently integrated into sensitive environments-the consequent size and energy constraints imposed on any security solutions are demanding. Thus, unique challenges arise due to the sensitivity of computation processing, need for security in implementations, and assurance “gaps.” This special issue is dedicated to the identification of techniques designed for embedded systems and cyber-physical systems, such as emerging cryptographic solutions applicable to extremely-constrained, sensitive infrastructures.

The massive adoption of The Internet of Things (IoT) and the creation of a smart-world around us leads to several privacy and security concerns. There has been significant work in the past to address the privacy and confidentiality of IoT data such as: providing secure end-to-end channels for the transmission of IoT data, encrypting IoT data using optimized cryptographic schemes such as order-preserving and homomorphic encryption that impose a reasonable energy overhead while improving security. However, for data intense IoT applications, decrypting large data sets using cryptographic schemes is significantly expensive in terms of latency as seen by the end user of the application. In this paper, we propose an Adaptive Latency-Aware Query Processing over encrypted IoT data that aims to: (i) minimize query latency for data intense applications as seen by the end user and, (ii) at the same time maintain minimum energy consumption overhead, comparable to the current schemes as much as possible. We present two main contributions: (i) a novel Adaptive latency-aware algorithm which chops down a single large query into several iterations of small sized queries by adaptively computing the optimal query size (t) for each iteration, and (ii) a novel IoT architecture with server cache suitable for addressing the latency issue through parallel execution, while leaving the Cloud database unmodified. Both contributions together allow minimizing query latency while maintaining minimum energy overhead. We evaluated the effectiveness of the proposed adaptive algorithm for latency and energy performance. The results show that the proposed adaptive solution delivers significantly a better latency performance while being comparable to the existing solutions in terms of energy efficiency.

We build on the framework of joint scheduling and network coding optimization. The formulation is extended to include rate, energy, and delay in network coding and routing paradigms. We then study energy-rate and delay-rate relationships to see how minimum energy and delay change as functions of multicast rate demand. The main observation is that as the rate demand approaches maximum achievable rate, the solution tends to increasingly use more diverse, longer paths. This translates into non-linearly higher energy and delay for higher input rates. In the case of energy, we are also able to show that network coding provides more benefits (when compared to routing) at higher rates. Another observation is related to the scheduling over maximal independent sets (MISs). We present results on comparing the performance of scheduling over all, exponentially growing MISs and small randomly selected subsets of MISs. Our results point to the effectiveness of the latter in achieving near-optimal rate and energy while reducing the complexity of the problem.

A Transmission Algorithm using Opportunistic Network Coding (TAONC) searches coding opportunities that minimize the amount of radio communication energy between a sender and multiple receivers in wireless networks. It calculates the energy gain of network coding at both a sender and receivers when a TAONC reduces communication energy by encoding multiple transmission packets into one. It considers the energy overheads, which are consumed by the TAONC and a Reception Algorithm using Opportunistic Network Coding (RAONC). We show that opportunistic network coding can effectively decrease the wireless communication energy even with consideration of the overheads. We study an appropriate algorithm complexity that optimizes the benefit of network coding with its overhead.

Emerging applications of wireless sensor networks mandate extensive in-network information processing and communication while requiring energy efficiency. Dense deployments of wireless nodes and shared wireless channel pose severe interference constraints. Several scheduling schemes in literature propose interference-aware message scheduling with the objective of energy minimization, but the problem of joint scheduling of tasks and messages for energy minimization in interference-aware manner has not been studied. We formulate a Mixed Integer Linear Program (MILP) for the joint scheduling of computation tasks and communication messages in data collection tree based networks. We propose a three phase heuristic which first performs joint scheduling of tasks and messages and then reduces the energy consumption of the network by using the energy saving techniques like Dynamic Voltage Scaling (DVS) for tasks and Dynamic Modulation Scaling (DMS) for messages. These techniques tradeoff energy with latency. However, in dense deployments of WSN with small transmitter receiver distances, DMS does not monotonically reduce the energy consumption. We use this knowledge to efficiently perform slack allocation. We present a Mixed Integer Linear Programming (MILP) formulation to obtain the optimal solution. We evaluate the performance of the proposed algorithm for a variety of scenarios and our results show that the energy savings obtained by the proposed algorithm competes closely with that of the MILP solution.

The development of a trustworthy smart grid requires a deeper understanding of potential impacts resulting from successful cyber attacks. Estimating feasible attack impact requires an evaluation of the grid's dependency on its cyber infrastructure and its ability to tolerate potential failures. A further exploration of the cyber-physical relationships within the smart grid and a specific review of possible attack vectors is necessary to determine the adequacy of cybersecurity efforts. This paper highlights the significance of cyber infrastructure security in conjunction with power application security to prevent, mitigate, and tolerate cyber attacks. A layered approach is introduced to evaluating risk based on the security of both the physical power applications and the supporting cyber infrastructure. A classification is presented to highlight dependencies between the cyber-physical controls required to support the smart grid and the communication and computations that must be protected from cyber attack. The paper then presents current research efforts aimed at enhancing the smart grid's application and infrastructure security. Finally, current challenges are identified to facilitate future research efforts.

One of the important objectives in Wireless Sensor Networks (WSNs) is to minimize energy consumption while satisfying delay constraints. Although, several energy-aware MAC layer protocols exist, the absence of channel adaptation and load adaptation results in energy wastage due to retransmissions and low success rate. In this paper, we propose an Adaptive- CSMA/CA protocol which accounts for varying channel and load conditions at a node by influencing the selection of either low energy or low delay transmission option. We devise an energy-delay metric that helps a node select the best message and modulation to obtain joint reduction in energy and delay at the time of transmission. Our simulation results show that our proposed Adaptive-CSMA/CA scheme results in upto 87% improvement in energy consumption under varying channel conditions and upto 150% higher success ratio under varying load as compared to the CSMA/CA specified in IEEE 802.15.4.

Disruption of electric power operations can be catastrophic on national security and the economy. Due to the complexity of widely dispersed assets and the interdependences among computer, communication, and power infrastructures, the requirement to meet security and quality compliance on operations is a challenging issue. In recent years, the North American Electric Reliability Corporation (NERC) established a cybersecurity standard that requires utilities' compliance on cybersecurity of control systems. This standard identifies several cyber-related vulnerabilities that exist in control systems and recommends several remedial actions (e.g., best practices). In this paper, a comprehensive survey on cybersecurity of critical infrastructures is reported. A supervisory control and data acquisition security framework with the following four major components is proposed: (1)real-time monitoring; (2)anomaly detection; (3)impact analysis; and (4)mitigation strategies. In addition, an attack-tree-based methodology for impact analysis is developed. The attack-tree formulation based on power system control networks is used to evaluatesystem-,scenario-, andleaf-level vulnerabilities by identifying the system's adversary objectives. The leaf vulnerability is fundamental to the methodology that involves port auditing or password strength evaluation. The measure of vulnerabilities in the power system control framework is determined based on existing cybersecurity conditions, and then, the vulnerability indices are evaluated.

Botnet-based distributed denial of service (DDoS) attacks represent an emerging and sophisticated threat for today's Internet. Attackers are now able to mimic the behavior of legitimate users to a great extent, making the issue of countering these attacks very challenging. In this paper, we propose a simple yet effective scheme that enables an ISP's edge routers to pass a great percentage of legitimate traffic, that is destined to a Web server under DDoS attack within that ISP, while filtering all other traffic. The proposed scheme, called JUST-Google, is based on the fact that Web search engines (especially Googletrade) represent the entrance for today's Web, thus making it in a strategic position to defend against these attacks. The main idea is that Googletrade can assist in identifying human users from bot programs by directing users who want to access a Web site under attack to a group of nodes that will perform authentication in which users are required to solve a reverse Turing test to obtain access to the Web server. Performance analysis shows that the proposed scheme would enable legitimate clients to access a Web site that is under attack with high probability.

Accurate fault detection and location is essential to the efficient and economical operation of ISP networks. In addition, it affects the performance of Internet applications such as VoIP and online gaming. Fault detection algorithms typically depend on spatial correlation to produce a set of fault hypotheses, the size of which increases by the existence of lost and spurious symptoms, and the overlap among network paths. The network administrator is left with the task of accurately locating and verifying these fault scenarios, which is a tedious and time-consuming task. In this paper, we formulate the problem of designing infrastructure overlay networks for verifying the location of IP links faults taking into account the cost of the debugging paths and the stress on the underlying IP links. We map the problem into a integer generalized flow problem, and prove its NP-hardness. We relax the link stress constraint and formulate the resulting problem as a minimum cost circulation that can be solved in polynomial time. We evaluate the fault verification and IP links coverage capabilities of various overlay network sizes and topologies using real-life Internet topologies. Finally, we identify some interesting research problems in this context.

Distributed Denial-of-Service (DDoS) attacks have emerged as a popular means of causing mass targeted service disruptions, often for extended periods of time. The relative ease and low costs of launching such attacks, supplemented by the current woeful state of any viable defense mechanism, have made them one of the top threats to the Internet community today. While distributed packet logging and/or packet marking have been explored in the past for DDoS attack traceback/mitigation, we propose to advance the state of the art by using a novel distributed divide-and-conquer approach in designing a new data dissemination architecture that efficiently tracks attack sources. The main focus of our work is to tackle the three disjoint aspects of the problem, namely attack tree construction, attack path frequency detection, and packet to path association, independently and to use succinct recurrence relations to express their individual implementations. We also evaluate the network traffic and storage overhead induced by our proposed deployment on real-life Internet topologies, supporting hundreds of victims each subject to thousands of high-bandwidth flows simultaneously, and conclude that we can truly achieve single packet traceback guarantees with minimal overhead and high efficiency.

There has not been an organized way to efficiently correlate anomaly behaviors in critical infrastructures as information about malicious activities are not gathered from geographically dispersed cyber systems. This paper establishes a systematic approach to identify properties that can be extracted to detect malicious activities in the cyber-based control systems. The malicious detection can be implemented through an on-line anomaly inference system in order to improve situational awareness. In this preliminary investigation, a methodology to infer anomaly is proposed for power systems, representing the anomalous cyber- or power-related events among substation networks.

Performing end-to-end energy management for the data aggregation application poses certain unique challenges particularly when the computational demands on the individual nodes are significant. In this paper, we address the problem of minimizing the total energy consumption of data aggregation with an end-to-end latency constraint while taking into account both the computational and communication workloads in the network. We consider a model where individual nodes support both dynamic voltage scaling (DVS) and dynamic modulation scaling (DMS) power management techniques and explore the energy-time tradeoffs these techniques offer. Specifically, we make the following contributions in this paper. First, we present an analytical problem formulation for the ideal case where each node can scale its frequency and modulation continuously. Second, we prove that the problem is NP-hard for practical scenarios where such continuity cannot be supported. We then present a mixed integer linear programming (MILP) formulation to obtain the optimal solution for the practical problem. Further, we present polynomial time heuristic algorithms which employ the energy-gain metric. We evaluated the performance of the proposed algorithms for a variety of scenarios and our results show that the energy savings obtained by the proposed algorithms are comparable to that of MILP.

In this paper, we address the problem of scheduling a set of periodic real-time messages in a wireless network with the objective of minimizing the total energy consumption while meeting deadline and reliability constraints. We formally prove that this problem is NP-hard and solve it in two stages. First, we consider a simple model that assumes that the wireless channel is completely reliable and the network is fully provisioned. Using the technique of employing multiple hop-by-hop transmissions instead of a single direct hop transmission as the basis, we prove that the strategy of choosing the hop distances such that they are equidistant is optimal in terms of energy consumption under the deadline constraint. Based on the intuition provided by the optimal strategy, we present heuristic scheduling algorithms for a more realistic wireless channel model and network condition. Our simulation results show that the proposed scheduling algorithms provide significant energy savings over the baseline algorithms

Recent technological advances have opened up several distributed real-time applications involving battery-driven embedded devices with local processing and wireless com- munication capabilities. Energy management is the key is- sue in the design and operation of such systems. In this pa- per, we consider a single-hop networked real-time embed- ded system where each node supports both dynamic volt- age scaling (DVS) and dynamic modulation scaling (DMS) power management techniques to tradeoff time for energy savings. In this model, we address the problem of schedul- ing periodic complex tasks where each task consists of several precedence constrained message passing sub-tasks. Our contributions towards this problem are two fold. First, we analyze the system level energy-time tradeoffs consider- ing both the computation and communication workloads by defining a novel energy gain metric. We then present static (centralized) and dynamic (distributed) energy gain based slack allocation algorithms which reduce the total energy consumption, while guaranteeing the ready time, deadline and precedence constraints. We compare the performance of the proposed algorithms with several baseline algorithms through simulation studies. Our results show that the pro- posed algorithms perform significantly better than the base- line algorithms for the simulated conditions. Finally, we identify several interesting energy-aware research problems in the area of networked real-time embedded systems.

Disruption of electric power operations can be catastrophic on the national security and economy. Due to the complexity of widely dispersed assets and the interdependency between computer, communication, and power systems, the requirement to meet security and quality compliance on the operations is a challenging issue. In recent years, NERC’s cybersecurity standard was initiated to require utilities compliance on cybersecurity in control systems - NERC CIP 1200. This standard identifies several cyber-related vulnerabilities that exist in control systems and recommends several remedial actions (e.g., best practices). This paper is an overview of the cybersecurity issues for electric power control and automation systems, the control architectures, and the possible methodologies for vulnerability assessment of existing systems.

This paper presents a novel scheme to mitigate the effect of SYN flooding attacks. The scheme, called intentional dropping based filtering, is based on the observation of client's persistence (i.e., client's reaction to packet loss by subsequent retransmissions) which is very widespread as it is built in TCP's connection setup. The main idea is to intentionally drop the first SYN packet of each connection request. Subsequent SYN packet from a request is passed only if it adheres to the TCP's timeout mechanism. Our analysis shows that the proposed scheme reduces attacker's effective attack rate significantly with an acceptable increase in connection establishment latency.

Tracing DoS attacks that employ source address spoofing is an important and challenging problem. Traditional traceback schemes provide spoofed packets traceback capability either by augmenting the packets with partial path information (i.e., packet marking) or by storing packet digests or signatures at intermediate routers (i.e., packet logging). Such approaches require either a large number of attack packets to be collected by the victim to infer the paths (packet marking) or a significant amount of resources to be reserved at intermediate routers (packet logging). We adopt a hybrid traceback approach in which packet marking and packet logging are integrated in a novel manner, so as to achieve the best of both worlds, that is, to achieve a small number of attack packets to conduct the traceback process and a small amount of resources to be allocated at intermediate routers for packet logging purposes. Based on this notion, two novel traceback schemes are presented. The first scheme, called distributed link-list traceback (DLLT), is based on the idea of preserving the marking information at intermediate routers in such a way that it can be collected using a link list-based approach. The second scheme, called probabilistic pipelined packet marking (PPPM), employs the concept of a "pipeline" for propagating marking information from one marking router to another so that it eventually reaches the destination. We evaluate the effectiveness of the proposed schemes against various performance metrics through a combination of analytical and simulation studies. Our studies show that the proposed schemes offer a drastic reduction in the number of packets required to conduct the traceback process and a reasonable saving in the storage requirement.

Several IP traceback schemes employing packet marking have been proposed to trace attacks that use source address spoofing, such as DoS/DDoS attacks. A major challenge with these schemes is the limited number of bits available for marking in the IP headers. Marking this information elsewhere could lead to packet fragmentation and/or attack amplification when a clever attack is launched. We present a novel scheme, called the space-time encoding (STE) scheme, that requires very few bits to be marked on an IP packet, by every router along the attack path deterministically. At every router, this scheme makes use of the local router connectivity information to encode (mark) the incoming physical interface across multiple packets. Our analysis of the simulation results, obtained by trial runs on large data sets available that represent Internet maps, show that we need to mark only 25 bits on every packet and in the ideal case would require only 7 packets for successful traceback. Additionally, we also propose techniques that enhance the scheme to make it scalable and easily deployable.

Multicasting in Diffserv networks is a challenging problem due to the architectural conflicts between them, namely, stateful vs. stateless core. In this paper, we assume an edge-based multicast (EBM) model wherein the multicast tree is constructed such that the branching occurs only at the edge routers. We propose an algorithm to solve the problem of dynamic member join/leave in heterogeneous QoS multicasting under EBM model. We formally state the problem and propose an algorithm for it, which is optimal when the constraint on the member join/leave requires that there can be no service disruption for on-tree nodes. We then evaluate the performance of our algorithm with respect to a static multicast tree construction heuristic and a source-based shortest path algorithm using "tree QoS cost" as a primary metric. Our studies show that the proposed algorithm achieves good performance in terms of tree QoS cost, time taken for member join/leave, and number of service disruptions with acceptable storage overhead.

This paper presents a novel scheme to mitigate the effect of SYN flooding attacks. The scheme, called intentional dropping based filtering, is based on the observation of client's persistence (i.e., client's reaction to packet loss by subsequent retransmissions) which is very widespread as it is built in TCP's connection setup. The main idea is to intentionally drop the first SYN packet of each connection request. Subsequent SYN packet from a request is passed only if it adheres to the TCP's timeout mechanism. Our analysis shows that the proposed scheme reduces attacker's effective attack rate significantly with an acceptable increase in connection establishment latency.

The issue of handling network failures is becoming increasingly important. In this paper, we address the problem of constrained routing by treating reliability as one of the QoS requirements. The problem is to create a feasible path from a given node to the destination such that the bandwidth and reliability requirements of the path are satisfied and the cost of the path is minimized (Reliability Constrained Least Cost Routing Problem). To solve the problem, we propose an approach which employs a novel concept, called partial protection, wherein backup paths are created for a selected set of domains in the network so as to meet the reliability constraints. The Partial Protection Approach (PPA) has two steps: Primary Path Creation and Backup Path Creation if necessary. To implement PPA, we propose three scalable two-pass resource reservation schemes, viz., Conservative, Optimistic, and Hybrid schemes. These schemes differ depending on whether the backup paths are created during the forward pass, reverse pass, or both. We evaluate the performance of the proposed schemes for dynamic multicast groups with different bandwidth and reliability requirements using average call acceptance rate and average tree cost as performance metrics. Our studies show that group dynamics and reliability requirements have significant impact on the performance of the schemes.

The use of feedback control techniques has been gaining importance in the context of scheduling in real-time systems as a means to provide predictable performance in the face of uncertain workload. We propose a novel feedback-based scheduling approach for task scheduling in real-time systems. We focus on a system with a mobile node, where the mobility characteristics affect task parameters. The objective is to achieve low miss ratio and high CPU utilization. This objective is achieved by feeding back system performances and adapting the node' mobility parameters. We study the new approach in a selective herbicide spraying problem in the agricultural production wherein the speed of an autonomous vehicle (and hence task parameters) is adapted based on weed distribution in the given farm field. Simulations and analysis show that our approach can achieve low miss ratio and high CPU utilization.

The Internet infrastructure security has been gaining importance in recent years due to growing concerns for cyberwarfare. Among different network threats, the routing table poisoning attack is the most devastating and least researched topic, which needs immediate research attention. In this paper, we develop a scalable algorithm for detecting and recovering from router attacks in distance vector routing protocols. The algorithm is able to detect and recover from malicious updates under certain well-defined conditions. We carry out extensive simulation studies to evaluate the proposed pivot based algorithm for inconsistency recovery (PAIR) for three performance metrics, viz. detection probability, recovery probability and malicious distance under different network and attack scenarios. Our studies show that the PAIR is extremely scalable and offers high detection and recovery capability.

The routing table poisoning attack is one of the most devastating and least researched topic among Internet attacks, which needs immediate research attention. In this paper, we develop a scalable method for detecting router attacks and locating the malicious routers (within a small bounded set of nodes) in link state routing protocols. We carry out analytical and simulation studies to evaluate the proposed secure link state protocol (SLIP) for two performance metrics, viz. attack detection probability and fault detection time, under different network and attack scenarios. Our studies show that the SLIP offers a very high attack detection capability with a little degradation in fault detection time compared to the link state protocol.

The phenomenal growth of QoS-aware applications over the Internet has accelerated the development of key technologies such as differentiated services (DiffServ). Although QoS is provided through class-based service differentiation, the aspect of fault tolerance is not addressed in the DiffServ architecture. For traditional IP networks, the underlying link state protocol provides fault detection and recovery. However for QoS sensitive flows, the recovery times of such protocols may not be adequate. Although such a problem may be solved through fine grain HELLO timers, the underlying core routers may not be able to tolerate the additional CPU and bandwidth burden. The edge-based intelligence of the DiffServ domain represents a unique opportunity to improve the fault detection capability of the link state protocol. We propose a hybrid scheme whereby heartbeat packets are used to detect possible faults coupled with a temporary fine grain HELLO interval for fault location and possible recovery. We analyze our scheme through extensive simulation studies and we examine the tradeoffs and benefits of our scheme.

The significant growths of group communications and QoS-aware applications over the Internet have accelerated the development of two key technologies, namely, multicasting and Differentiated Services (DiffServ). Although both are complementary technologies, their integration is a non-trivial task due to several architectural conflicts between them. The inherent heterogeneous nature of QoS multicasting further complicates this problem with the sender-driven nature of DiffServ. Thus, in this paper, we propose a method for providing heterogeneous QoS to multicast groups via dynamic DSCPs without per-group state information in the DiffServ core. We detail our approach as well as examine implications for an adaptive method for both multicast and unicast connections. Finally, we present simulation studies regarding the performance benefits of dynamic DSCPs in multicasting.

The emergence of new multimedia group-based applications drives the need for efficient network support for quality of service (QoS) multicasting. In the core based tree (CBT) multicast distribution model, when a new receiver joins the group, it always attempts to establish a path to the core node of the multicast tree, making the core the hot spot node in the network. The situation becomes even worse when many groups have the same node as their core. Hence, the network resources around the core become the bottleneck for future join requests. Thus, the CBT-based protocols suffer from the problem of "hot spot traffic concentration" around the core. We propose a single-probe multi-destination (SPMD) protocol for QoS multicasting, which aims at alleviating the traffic concentration around the core. In our protocol, a receiver joining an existing multicast session establishes a path by performing a single path search towards multiple members of the multicast tree, rather than to the core node alone as in the case of CBT. We demonstrate the effectiveness of the proposed SPMD routing protocol through extensive simulation studies by evaluating its performance in terms of average call acceptance rate (ACAR) and average call setup time (ACST). Our studies show that the proposed protocol performs better than the single-destination multicast routing protocols (in terms of ACAR), especially when the groups are resource-intensive, such as high bandwidth groups.

The proliferation of QoS-aware group applications coupled with the limited availability of network resources demands efficient mechanisms to support QoS multicasting. During a life-cycle of a multicast session, three important events can occur: membership dynamics, network dynamics, and traffic dynamics. The first two are concerned with maintaining a good quality (cost) multicast tree taking into account dynamic join/leave of members, and changes in network topology due to link/node failures/additions, respectively. The third aspect is concerned with flow, congestion, and error control. There have been many solutions proposed for dealing with each of these issues. However, the issue of tree migration has not been addressed as part of these solutions. In this paper, we highlight the importance of tree migration as a mechanism for handling membership and network dynamics in core-based I multicasting, prove that it is NP-complete, and propose four heuristic algorithms for it. The proposed algorithms are evaluated under two performance metrics: service disruption and resource wastage. Our simulation studies show that two of the algorithms offer comparable performance to that of the other two, in addition to being highly scalable and easily implementable.

The phenomenal growths of group communications and QoS-aware applications over the Internet have respectively accelerated the development of two key technologies, namely, multicasting and differentiated services (DiffServ). Although both are complementary technologies, the integration of the two technologies is a non-trivial task due to architectural conflicts between multicasting and DiffServ. We propose an approach for providing multicast support across a DiffServ domain that is scalable in terms of group size, network size, and number of groups. We analyze our approach in a detailed manner for feasibility, adaptiveness, and deployment considerations.

Though the areas of secure multicast group architecture, key distribution and sender authentication are under scrutiny, one topic that has not been explored is how to integrate these with multilevel security. Multilevel security is the ability to distinguish subjects according to classification levels, which determines to what degree they can access confidential objects. In the case of groups, this means that some members can exchange messages at a higher sensitivity level than others. The Bell-La Padula model outlines the rules of these multilevel accesses (see Bell, D. and La Padula, L., MITRE Report, M74-244, MTR 2547 v2, 1973). In multicast groups that employ multilevel security, some of these rules are not desirable, so a modified set of rules is developed and is termed differential security. Also, this paper proposes three methods to set up a differentially secure multicast group: (1) naive approach, (2) multiple tree differential security (DiffSec) approach, and (3) single DiffSec tree approach. Our simulation studies show that both single and multiple DiffSec tree approaches offer similar performance in terms of bandwidth consumption, which is significantly better than that of the naive approach. We also discuss the suitability of the schemes, taking into account scalability and implementation issues.

In real-time systems, tasks have deadlines to be met despite the presence of faults. Primary-Backup (PB) scheme is one of the most common schemes that has been employed for fault-tolerant scheduling of real-time tasks, wherein each task has two versions and the versions are scheduled on two different processors with time exclusion. There have been techniques proposed for improving schedulability of the PB-based scheduling. One of the more popular ones include Backup-Backup (BB) overloading, wherein two or more backups can share/overlap in time on a processor. In this paper we propose a new schedulability enhancing technique, called primary-backup (PB) overloading, in which the primary of a task can share/overlap in time with the backup of another task an a processor. The intuition is that, for both primary and backup of a task, the PB-overloading can assign an earlier start time than that of the BB-overloading, thereby increasing the schedulability. We conduct schedulability and reliability analysis of PB- and BB-overloading techniques through simulation and analytical studies. Our studies show that PB-overloading offers better schedulability (25% increase in the guarantee ratio) than that of BB-overloading, and offers reliability comparable to that of BB-overloading. The proposed PB-overloading is a general technique that can be employed in any static or dynamic fault-tolerant scheduling algorithm.

The issue of providing efficient media retrieval services has been an important problem in recent years. Among them, video-on-demand (VoD) is one of the most popular and challenging ones. An efficient solution to the VoD service problem should address the twin issues of scalability and client heterogeneity. In this paper, we propose a VoD server model, that is based on the parallel video server architecture and layered coding, to satisfy these twin issues. The proposed model dynamically adapts to the server load in order to maximize the number of clients (connections) admitted while maintaining a high quality for the already admitted connections. We study the adaptiveness our model by proposing promotion/demotion policies for quality adaptation. We also propose a performance metric, called marginal quality, that normalizes the quality (received) across heterogeneous connections. Finally, we evaluate the effectiveness of our model, in terms of connection acceptance rate, connection quality, and fairness in connection quality, through extensive simulation studies.

The phenomenal growths of group communications and QoS-aware applications over the Internet have accelerated the development of two key technologies, namely, multicasting and Differentiated Services (DiffServ). Although both are complementary technologies, the integration of the two technologies is a non-trivial task due to architectural conflicts between multicasting and DiffServ. We propose a protocol for member join/leave in a DiffServ network that is scalable in terms of group size, network size, and number of groups. We detail our join/leave protocol for both intra-domain and inter-domain routing as well as the various different types of multicast trees (single source tree, shortest path tree, shared tree, many-to-many tree). Finally, we present simulation studies regarding the performance of our join/leave protocol.

Wavelength-division multiplexed (WDM) optical networks using wavelength routing are considered to be a potential candidate for next-generation wide-area backbone networks. The key component in such networks is the light-path network (LPN) manager. The functions of the LPN manager include setting up the logical topology, sustaining the network by monitoring traffic and network parameters, and handling node and/or link failures. Failure handling in WDM networks is of prime importance due to the nature and volume of traffic these network carry. Failure detection is usually achieved by exchanging control messages among nodes with timeout mechanisms. Failure restoration can be done either by re-routing only the failed light paths (LPs) or by reconfiguring all the existing LPs in the network. The reconfiguration approach involves finding new LPs in the faulty network (LP design) and realizing these new LPs by selectivity removing the old LPs (LP realization) with the objective of minimizing the service disruption to the ongoing calls. Existing work on the reconfiguration approach considers only LP design and ignores LP realization. In this paper, we first propose an architecture for the LPN manager highlighting the importance of LP realization in reconfiguration-based failure restoration, then we propose performance measures and heuristic algorithms for LP realization. We evaluate the effectiveness of the LP realization algorithms through simulation studies.

The issue of providing fault-tolerance in real-time communication has been a problem of growing importance. There are two basic approaches for satisfying fault-tolerant requirements in real-time communication: (i) the forward error recovery approach, and (ii) the detect and recovery approach. The first approach is well-suited for hard real-time communication, whereas the second approach is well-suited for soft real-time communication. Neither of these basic approaches is well-suited for applications which involve both hard and soft real-time communication. In this paper, we propose an integrated scheme that combines the benefits of both the basic approaches. The proposed scheme not only caters to such mixed communication requirements, but also improves the call acceptance rate significantly due to its efficient resource allocation mechanisms such as traffic dispersion and backup multiplexing. The effectiveness of the proposed scheme has been evaluated through extensive simulation studies.

With the proliferation of multimedia group applications, the construction of multicast trees satisfying quality of service (QoS) requirements is becoming a problem of prime importance. Many of the multicast applications (such as video broadcasts and teleconferencing) require the network to support dynamic multicast sessions wherein the membership of the multicast group changes with time. We propose and evaluate an algorithm for on-line update of multicast trees to adjust to changes in group membership. The algorithm is based on a concept called quality factor (QF) that represents the usefulness of a portion of the multicast tree to the overall multicast session. When the usefulness of a particular region of the tree drops below a threshold, a rearrangement technique is used to suitably modify the tree. This algorithm aims to satisfy the delay-constraints of all current group members, at the same time minimizing the cost of the constructed tree. We compare the performance of our algorithm, by simulation, with that of an off-fine Steiner heuristic; with ARIES, a previously published algorithm for on-line update of unconstrained trees; and with the algorithm proposed by Hong, Lee and Park (see Proc. of IEEE INFOCOM, pp. 1433-40, 1998) for on-line update of delay-constrained trees. The simulation results indicate that our algorithm provides excellent cost-competitiveness that is better than that provided by the algorithm described by Hong et al., minimizes changes in the multicast tree after each update, and performs favorably even when compared with the unconstrained ARIES heuristic.

We propose a new distributed route selection approach, called parallel probing, for real-time channel establishment in a point-to-point network. The existing distributed routing algorithms fall into two major categories: preferred neighbor based or flooding based. The preferred neighbor approach offers a better call acceptance rate, whereas the flooding approach is better in terms of call setup time and routing distance. The proposed approach attempts to combine the benefits of both preferred neighbor and flooding approaches in a way to improve all the three performance metrics simultaneously. This is achieved by probing k different paths in parallel, for a channel, by employing different heuristics on each path. Also, the proposed approach uses a notion called intermediate destinations (IDs), which are subset of nodes along the least-cost path between source and destination of a call, in order to reduce the excessive resource reservations while probing for a channel by releasing unused resources between IDs and initiating parallel probes at every ID. Further, it has the flexibility of adapting to different load conditions by its nature of using different heuristics in parallel, and hence, a path found for a channel would have different segments (a segment is a path between two successive IDs), and each of these segments would very well be selected by different heuristics. The effectiveness of the proposed approach has been studied through simulation for well-known network topologies for a wide range of quality-of-service and traffic parameters. The simulation results reveal that the average call acceptance rate offered by the proposed route-selection approach is better than that of both the flooding and preferred neighbor approaches, and the average call setup time and routing distance offered by it are very close to that of the flooding approach.

With the proliferation of multimedia group applications, the construction of multicast trees satisfying quality of service (QoS) requirements is becoming a problem of prime importance. Many of the multicast applications (such as video broadcasts and teleconferencing) require the network to support dynamic multicast sessions wherein the membership of the multicast group changes with time. In this paper, we propose and evaluate an algorithm called CRCDM (controlled rearrangement for constrained dynamic multicasting) for on-line update of multicast trees to adjust to changes in group membership. The CRCDM algorithm is based on a concept called quality factor (QF) that represents the usefulness of a portion of the multicast tree to the overall multicast session. When the usefulness of a particular region of the tree drops below a threshold, a rearrangement technique is used to suitably modify the tree. Our algorithm aims to satisfy the delay constraints of all current group members, at the same time minimizing the cost of the constructed tree. We compare the performance of our algorithm, by simulation, with that of an off-line Steiner heuristic; with ARIES, a previously published algorithm for on-line update of unconstrained trees; and with the algorithm proposed by Hong, Lee and Park (see Proc. IEEE INFOCOM, p.1433-40, 1998) for on-line update of delay-constrained trees. The simulation results indicate that our algorithm provides excellent cost-competitiveness that is better than that provided by the algorithm described by Hong et al., minimizes changes in the multicast tree after each update, and performs favorably even when compared with the unconstrained ARIES heuristic.

The problem of real-time communication over a multiple access network has been well studied in the past. But, there has been no prior work addressing real-time communication over a switched local area network (SLAN), where several LAN segments are connected through a switch. In this paper we propose real-time protocols for the SLAN. The proposed protocols are based on CSMA/CD with deterministic collision resolution and belong to the dynamic planning based category, where an admission test is performed for guaranteeing message transmission. This test is based on the worst case channel access time that can elapse before a particular node can transmit its message. We also compute the worst case buffer requirement at the switch. We study the effectiveness of the proposed protocoIs through extensive simulation studies.

Many time-critical applications require dynamic scheduling with predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. In this paper, we propose an algorithm to dynamically schedule arriving real-time tasks with resource and fault-tolerant requirements on to multiprocessor systems. The tasks are assumed to be nonpreemptable and each task has two copies (versions) which are mutually excluded in space, as well as in time in the schedule, to handle permanent processor failures and to obtain better performance, respectively. Our algorithm can tolerate more than one fault at a time, and employs performance improving techniques such as 1) distance concept which decides the relative position of the two copies of a task in the task queue, 2) flexible backup overloading, which introduces a trade-off between degree of fault tolerance and performance, and 3) resource reclaiming, which reclaims resources both from deallocated backups and early completing tasks. We quantify, through simulation studies, the effectiveness of each of these techniques in improving the guarantee ratio, which is defined as the percentage of total tasks, arrived in the system, whose deadlines are met. Also, we compare through simulation studies the performance our algorithm with a best known algorithm for the problem, and show analytically the importance of distance parameter in fault-tolerant dynamic scheduling in multiprocessor real-time systems.

Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. In this paper, we propose an efficient algorithm for nonpreemptive scheduling of dynamically arriving real-time tasks (aperiodic tasks) in multiprocessor systems. A real-time task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of parallelization of the task. We use this parallelism in tasks to meet their deadlines and, thus, obtain better schedulability compared to nonparallelizable task scheduling algorithms. To study the effectiveness of the proposed scheduling algorithm, we have conducted extensive simulation studies and compared its performance with the myopic scheduling algorithm. The simulation studies show that the schedulability of the proposed algorithm is always higher than that of the myopic algorithm for a wide variety of task parameters.

Many time critical applications require predictable performance and tasks in these applications have deadlines to be met despite the presence of faults. We propose a new dynamic non preemptive scheduling algorithm for a relatively new task model called parallelizable task model where real time tasks can be executed concurrently on multiple processors. We use this parallelism in tasks to meet their deadlines and thus obtain better processor utilization compared to nonparallelizable task scheduling algorithms. We assume that tasks are aperiodic. Further, each task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of task parallelization. To study the effectiveness of our algorithm, we have conducted extensive simulation studies and compared its performance with the myopic scheduling algorithm (K. Ramamritham et al., 1990). We found that the success ratio offered by our algorithm is always higher than the myopic algorithm for a wide variety of task parameters. Also, we propose a resource reclaiming algorithm to reclaim resources from parallelizable real time tasks when their actual computation times are less than their worst case computation times. Our parallelizable task scheduling together with its associated reclaiming offers the best guarantee ratio compared to the other algorithmic combinations.

Many time-critical applications require predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. Failures can happen either due to processor faults or due to task errors. To tolerate both processor and task failures, the copies of every task have to be mutually excluded in space and also in time in the schedule. We assume, each task has two versions, namely, primary copy and backup copy. We believe that the position of the backup copy in the task queue with respect to the position of the primary copy (distance) is a crucial parameter which affects the performance of any fault-tolerant dynamic scheduling algorithm. To study the effect of distance parameter, we make fault-tolerant extensions to the well-known myopic scheduling algorithm which is a dynamic scheduling algorithm capable of handling resource constraints among tasks. We have conducted an extensive simulation to study the effect of distance parameter on the schedulability of fault tolerant myopic scheduling algorithm.

A number of existing multiprocessors are based on the hypercube interconnection network. The popularity of the hypercube is due to its small communication diameter, which grows logarithmically with the cube size, its fault-tolerant properties, and its modularity which makes it possible to build a larger cube from smaller subcubes. The star graph has been studied as a network topology for fault-tolerant parallel com puting. Unfortunately, the size of the network grows too sharply with n to be affordable for values of n larger than 7 or 8. We introduce a novel intercon nection network known as the incomplete star graph, which overcomes the above problem while retaining the most of the advantages of the star graph. We present the architecture of the incomplete star graph and compare its performance with the full star as well as competing architectures such as the incomplete hypercube and arrangement graphs. We provide routing algorithms for both non-faulty and faulty incompletestar graphs, and study their performance.