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.>

The results are reported of an experimental study of software metrics for a fairly large software system used in a real-time application. A number of issues are examined, including the mutual relationship between various software metrics and, more importantly, the relationship between metrics and the development effort. Some interesting connections are reported between metrics and the software development effort.>

The rising costs of software development and maintenance have naturally aroused intere5t in tools and measures to quantify and analyze software complexity. Many software metrics have been studied widely because of the potential usefulness in predicting the complexity and quality of software. Most of the work reported in this area has been related to nonreal-time software. In this paper we report and discuss the results of an experimental investigation of some important metrics and their relationship for a class of 202 Pascal programs used in a real-time distributed processing environment. While some of our observations confirm independent studies, we have noted significant differences. For instance the correlations between McCabe's control complexity measure and Halstead's metrics are low in comparison to a previous study. Studies of the type reported here are important for understanding the relationship between software metrics.

In this note we report the results of an experimental investigation on the performance of the very simple level scheduling algorithm for unit time task systems. Although the problem of the construction of optimal k-processor schedules for unit time tasks is NP-complete, the experimental study suggests that this efficient linear time algorithm can produce optimal schedules most of the time in the sense that the probability of producing an optimal schedule using this efficient linear time algorithm is at least 0.9 for over 700 cases randomly constructed in our experiment.

Most minimization algorithms produce an irredundant sum of products by first generating all prime implicants of a switching function. In this note we show that such an approach can be a wasteful one for an already complex problem. Specifically we show that there are functions for which the useful prime implicants form an extremely small fraction of all prime implicants, where we define a prime implicant to be useful if there is at least one irredundant sum of products which includes it.

A formal framework for studying the scheduling problem for task systems with multiple outcome operations and independent control structure is presented Models of sequential programs and their parallel representa tlons (schedules) are developed.Schedules are seen to be restrictions of the parallel program schema of Karp and Mdler The restrictions are that the operations are synchronous and of fixed duration Interpretations of schedules are provided, and it as shown that the schedules are determinate and preserve the results of sequential computations in various senses Various equivalence properties of schedules and their relationships are studied.A number of decldablhty questions are answered by using the notion of "parallel derivatives" introduced by Mlllen Optamallty of schedules IS defined m terms of minimal tame executions, and parallel derivatives are used to generate optimal schedules.Finally, the finite representation of optimal schedules as considered

The parallel scheduling of a partially ordered set of tasks has received great attention. The partially ordered tasks can be viewed as components of a straight-line program. In this note, we discuss some aspects of the nonpreemptive parallel scheduling of a program with more general control structures. We examine the existence of optimal k-processor schedules, and in line with recent interest in the complexity of computer computations and algorithms, we study the complexity of constructing optimal k-processor schedules. In particular we show that, for every k > 1, any algorithm that would yield an optimal k-processor schedule of a loop-free program, when such a schedule exists, will be of exponential-time complexity.

The purpose of this paper is to present the basis of an automata-theoretic model which treats the concept of “schedule” for programs which admit a (predefined) degree of parallelism.

A finite-state machine (FSM) is said to have finite input-memory, μi(finite output-memory μo) if μi(μo) is the least integer such that yk= f(Xk, Xk-1,..., Xk-μi), (yk= f(Xk, yk-1,..., yk-μo)). If no such integer μi(μo) exists then by convention μi= ∞ (μ0= ∞). It is well known that for a nondegenerate binary-input binary-output FSM M, μi≥ [log2 n] (μo ≥ [log2 n]), where n is the number of non-equivalent states in M. In this note we show that the above bound cannot be improved upon by giving a procedure to construct, for any n > 0, a binary-input binary-output FSM with n nonequivalent states and minimal input-memory μi= [log2n] (minimal output-memory μo= [ log2 n]). In the process of proving the tightness of the lower bound on μi(μo), we enumerate the number of distinct minimal binary r-stage feed-forward (output feedback) shift registers.

The definitions of input-memory and output-memory of a sequential machine are examined and an attempt is made to clarify some, confusion in the literature regarding the concepts of input-memort and output-memory.

A finite state machine (FSM) is said to have finite memory μ if μ is the least integer such that yk= f(Xk, Xk-1,... Xk-μ, Yk-1, ... μk-μ) where ykand Xkrepresent the output and input at time k. If no such μ exists, then by convention the memory is said to be infinite. It has been observed [1] that if the memory of a p-nary input, q-nary output n-state minimal nondegenerate FSM is finite, then the memory μ is bounded as follows: Recently, considerable attention has been devoted to the study of the upper bound on μ [2]-[5]. In this paper we examine the lower bound on μ. We show that the lower bound is tight for all positive integers n and certain values of p and q. We also show that when n = 4k, k a positive integer, there exist binary input, binary output minimal FSMs with minimal memory. It will be seen that this is equivalent to showing that for all positive integers μ there exist binary input, binary output minimal FSMs with the maximum number of states n=22μ. Finally, we enumerate the equivalence classes of these finite memory machines with memory μ and n = 22μstates.