Directed Acyclic Graphs (DAGs), rooted at popular/default destinations, have emerged as a preferred mechanism to provide IPv6 routing functionality in large scale low power and lossy networks, that include wireless sensor networks and those based on power line communication. A DAG maintains its acyclic nature by requiring that each DAG node must have a higher 'rank' than any of its DAG parents. While a node may decrease its DAG rank safely, increasing its DAG rank to add a new parent may result in a routing loop if the new parent is also a descendant in the DAG. In this paper, we first study via simulations the time required by the network to converge to a stable, loop-free state following a rank increase operation and the number of routing messages generated (the network 'churn') during this time. Then, we describe the precautionary measures that can be used to avoid routing loops and evaluate via simulations how these measures affect the time and churn involved in reaching a stable state following a rank increase operation.

OSPF is a popular interior gateway routing protocol. Commercial OSPF routers limit their processing load by using a hold time between successive routing table calculations as new link state advertisements (LSAs) arrive following a topology change. A large hold time value limits the frequency of routing table calculations but also causes large delays in convergence to the topology change. Hence, commercial routers now use an exponential back off scheme, where the hold time is initially set to a small value that is expected to rapidly increase, and hence limit the frequency of routing table calculations, in face of continuous LSA arrivals. In this paper, we analyze the ability of different hold time schemes to limit the frequency of routing table calculations under continuous LSA arrivals starting with a small value for the hold time. This analysis is performed using Markov regenerative process based stochastic models as well as simulations using an extensively modified OSPFD simulator.

IEEE 802.15.4, a MAC/PHY protocol for low power and low data rate wireless networks, is emerging as the popular choice for various monitoring and control applications. Depending on the application, the traffic load on an IEEE 802.15.4 network may vary over a wide range. Hence, proper configuration is important for successful operation of the protocol under given traffic load conditions. In this paper, we examine the impact of different configuration parameters: namely, macMinBE, macMaxBE and macMaxCSMABackoffs, on the performance of beaconless IEEE 802.15.4 networks. The performance is measured in terms of the packet loss probability and the packet latency as the traffic load on the network increases. Based on this analysis, we suggest IEEE 802.15.4 configuration that results in a good tradeoff between the packet loss probability and the packet latency for a given traffic load range. This analysis is based on ns2 simulations.

IEEE 802.15.4, a MAC/PHY protocol for low power and low data rate wireless networks, is emerging as the popular choice for various monitoring and control applications. Depending on the application, the traffic load on an IEEE 802.15.4 network may vary over a wide range. The performance of the protocol, measured in terms of the packet loss probability and the packet latency, depends upon the prevailing traffic load as well as the configuration of IEEE 802.15.4 MAC parameters. Static configuration of IEEE 802.15.4 MAC parameters, good for a particular traffic load range, may result in bad performance when the traffic load changes beyond that range. In this paper, we present a scheme that can be used by an IEEE 802.15.4 node to dynamically adjust its MAC configuration based on the observed loss rate and latency suffered by recent packets generated by the node. The performance benefits of the proposed scheme are illustrated via NS2 simulations.

This paper deals with the enhancement of the heuristic for the grade of service Steiner minimum tree problem that could be applied to the design of communication networks offering graduated services. This problem, which is known as one of the NP-hard problems, attempts to find a network with the minimum construction cost meeting the G-condition. In prior research, we proposed a heuristic based on the local Steiner point locating policy in conjunction with the distance preferring minimum spanning tree building policy. Herein, we suggest methods of selecting the G-node and disconnections for the distance local GOSST heuristic for the problem in this paper. The ameliorated heuristic provides a 17% improvement in the network construction cost saving ratio to G-MST.

Fast convergence to topology changes is now a key requirement in routing infrastructures while reducing the routing protocol’s processing overhead continues to be as important as before. In this paper, we examine the problem of scheduling routing table updates in link state routing protocols. Commercial routers typically use a hold time based scheme to limit the number of routing table updates as new LSAs arrive at the router. The hold time schemes limit the number of routing table updates at the expense of increased delay in convergence to the new topology, which is clearly not acceptable any more. We analyze the performance of different hold time schemes and propose a new approach to schedule routing table updates, called LSA Correlation. Rather than using individual LSAs as triggers for routing table updates, LSA Correlation scheme correlates the information in the LSAs to identify the topology change that led to their generation. A routing table update is performed when a topology change has been identified. The analysis and simulation results presented in this paper suggest that the LSA Correlation scheme performs much better than the hold time based schemes for both isolated and large scale topology change scenarios.

In this paper, we analyze OSPF's interface state machine and propose modifications in order to reduce the time/processing requirements of the leader election process in a broadcast LAN environment. The proposed modifications are based on dynamic adjustment of wait time duration rather than using a static value.

Load distribution improves performance of a computer network by transferring tasks from heavily loaded computers, where service is poor, to lightly loaded computers, where the tasks can take advantage of an available computing capacity that would otherwise go unused. In This work, a traveling token concept for dynamic load balancing protocol is proposed. Instead of each computer probing other computers often resulting in unsuccessful probing, we take a different approach that makes the identity of the heavily loaded and lightly loaded computers better known to other computers. The results of our simulation show that the proposed protocol outperforms other existing protocols implemented in our simulator almost in all cases we tested.

We present a receiver-initiated fuzzy logic control method to improve computer network performance by balancing loads among computers. We study and present the performance of this protocol by comparing it with the performance of: (i) a well-known protocol called the BID algorithm; (ii) a non-fuzzy (threshold based) receiver-initiated algorithm; (iii) a fuzzy logic sender-initiated algorithm.

Various studies have shown that both hardware and software are subject to failures. However, the majority of the existing works have dealt with the problem by considering that either software is fault-free but hardware is subject to failure, or hardware is fault-free but software is subject to failure. Thus, techniques for dealing with both software and hardware faults must be developed. In this work, we propose an efficient integrated fault-tolerant approach for ultrareliable execution of tasks where both hardware and software failures, and on-line fault diagnosis are considered. The proposed approach is called the Integrated Fault-Tolerant (IFT) approach. We also propose a scheduling algorithm called the Integrated Fault-Tolerant Scheduling (IFTS) algorithm based on the IFT technique.

The authors study the effect of the traditional sequential recovery block (SRB) and the distributed recovery block (DRB) schemes on system performance (system average throughput, system mean response time, and percentage of tasks of a certain type completed) for two new software fault tolerant scheduling algorithms-sequential recovery block round-robin (SRBRR) scheduling algorithm and distributed recovery block round-robin (DRBRR) scheduling algorithm.

For critical computer applications, N-version Programming (NVP) is used for software fault tolerance. However, software redundancy which is employed in NVP results in system performance degradation. We propose software fault-tolerant scheduling policies based on both fully N-version programming and semi N-version programming models of computation. Further we study the performance of the system under the proposed scheduling policies.

In general, a load balancing algorithm improves a system performance. Obviously, larger the difference between the task arrival rates at various processors, more the system is imbalanced and more improvement in the system performance is achieved using a load balancing algorithm. The existing works which have used an experimental technique to show the improvement in the system performance under a load balancing algorithm have used an ad hoc procedure to select the task arrival rates for various processors. Thus, their experimental results necessarily may not provide a complete picture of the improvement in the system performance under their load balancing algorithms. The authors present a systematic scheme for the selection of the task arrival rates at various processors such that experimental results reflect a complete picture of the improvement in the system performance under a load balancing algorithm. The idea has been motivated by the well-known Taguchi technique used in quality control.>

Multiple processor systems allow both highly reliable and highly fast service. Distributed self-test algorithms that attempt to improve both the reliability and the performance of these systems are proposed. In these algorithms, reliability is improved by considering the distributed mode of control and assigning processors to test each other periodically for the diagnosis and isolation of the faulty processors and interprocessor links. Meanwhile, performance is improved by considering a dynamic testing strategy and minimizing testing overhead by reducing the number of tests performed on each processor. Simulation results show the effectiveness of the algorithms.>

A distributed processor level fault diagnosis algorithm is proposed where every processor will come up with its own conclusion about the status of other processors and also the links connecting it to its neighboring processors. Performance is improved by considering a dynamic testing strategy where each processor is assigned a small number of processors to test it, ideally two. Then, when some processors or links fail, a new testing assignment is made among the processors. Simulation results are presented to show that the proposed algorithm is effective in reducing the testing overhead.>

A study is made of the design of fault-tolerant array processors. It is shown how hardware redundancy can be used in the existing structures in order to make them capable of withstanding the failure of some of the array links and processors. Distributed fault-tolerance schemes are introduced for the diagnosis of the faulty elements, reconfiguration, and recovery of the array. Fault tolerance is maintained by the cooperation of processors in a decentralized form of control without the participation of any type of hardcore or fault-free central controller such as a host computer. Time redundancy is utilized by assigning the functions of the failed processors to fault-free processors.>

The problem of achieving fault diagnosis in a network of interconnected processing elements (called nodes) is considered. It is assumes that there is no central facility to control, coordinate or mediate among the processing elements. Every node can eventually determine the status of nodes and communication paths between them. A diagnostic algorithm for homogeneous systems (systems with only testing nodes) is given. The self-fault-diagnosis of inhomogeneous systems (systems with nodes of varying degrees of testing capability) is studied and diagnostic algorithms are proposed.>

Tree structures, as the interconnection structure in networks of many processing elements, have interesting features such as regularity ease of expansion, simple routing, simple addressing, suitability for VLSI/WSI implementation, etc. Distributed fault tolerance of these networks is considered. It is assumed that in these structures, there does not exist any central failure-free entity for providing services such as diagnosis of faulty components, system reconfiguration after failure, control, or coordination among the processing elements. Every processing element is able to diagnose the condition of every other node or internode communication paths via a truly distributed scheme.

The problem of designing distributed fault-tolerant computing systems is considered. A model in which the network nodes are assumed to possess the ability to "test" certain other network facilities for the presence of failures is employed. Using this model, a distributed algorithm is presented which allows all the network nodes to correctly reach independent diagnoses of the condition (faulty or fault-free) of all the network nodes and internode communication facilities, provided the total number of failures oes not exceed a given bound. The proposed algorithm allows for the reentry of repaired or replaced faulty facilities back into the network, and it also has provisions for adding new nodes to the system. Sufficient conditions are obtained for designing a distributed fault-tolerant system by employing the given algorithm. The algorithm has the interesting property that it lets as many as all of the nodes and internode communication facilities fail, but upon repair or replacement of faulty facilities, the system can converge to normal operation if no more than a certain number of facilities remain faulty.