Publications

MIND Lab // Publications // Research // Information // Photo Gallery // Home



TR 3491 Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications   Sheng-Tzong Cheng, and Ashok K. Agrawala

We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it, the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communcation cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a brahcn-and-bound method to find an optimal solution as well as an approximation approach for suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has the complexity of O(n 2 M) , while that approximation solution has O(n M ) , where n is the number of processors in the system and M is the number of tasks in the graph.

TR 3495 A Generic Architecture for Programmable Traffic Shaper for High Speed Networks   Krishnan K. Kailas, Ashok K. Agrawala and S.V. Raghavan July 1995

Traffic shapers by preventing congestion and smoothing the traffic, play an important role in realizing the traffic control schemes employed in high speed networks to ensure the Quality of Sevice (QoS) requirements of the application. In this report, we present a generic architecture for progammable traffic shaper for high speed networks. The programmablility of the proposed architecture is illustrated by implementing some of the existing traffic shaping schemes. The architectural design issues of the proposed scheme are described and discussed.

TR 3246 A Workload Model for Multi-Window Environments   Ashok K. Agrawala, Leyuan Shi and Paola Rossaro March 1994

In this paper we propose a workload model which describes the behavior of a user in multi-window environments. In such environments a user may undertake several concurrent activities and change the degree of concurrency by opening or closing windows. The model proposed here captures the starting and terminating of a concurrent activity using an age dependent branching process. Both analytical solution and numerical examples are presented.

TR 3402 Allocation and Scheduling of Real-Time Periodic Tasks with Relative Timing Constraints   Sheng-Tzong Cheng and Ashok K. Agrawala Janaury 1995

Allocation problem has always been one of the fundamental issues of building the applications in distributed computing systems (DCS). For real-time applications on DCS, the allocation problem should directly address the issues of task and communication scheduling. In this context, the allocation of tasks has to fully utilize the available processors and the scheduling of tasks has to meet the specified timing constraints. Clearly, the execution of tasks under the allocation and schedule has to satisfy the precedence, resources, and other synchronization constraints among them. Recently, the timing requirements of the real-time systems emerge that the relative timng constraints are imposed on the consecutive executions of each task and the inter-task temporal relationships are specified across task periods. In this paper we consider the allocation and scheduling problem of the periodic tasks with such timing requirements. Given a set of periodic tasks, we consider the least common multiple (LCM) of the task periods. Each task is extended to several instances within the LCM. The scheduling window for each task instance is derived to satisfy the timing constraints. We develop a simulated annealing algorithm as the overall control algorithm. An example problem of the sanitized version of the Boeing 777 Aircraft Information Management Systems is solved by the algorithm. Experimental results show that the algorithm solves the problem in a reasonable time complexity. 22 pgs.

TR 2365.1 An Empirical Study of the Effect of Granularity on Parallel Algorithms on the Connection Machine   Sam H. Noh, Dipak Ghosal, and Ashok K. Agrawala December 1991

Technological trends suggest that soon communication networks will consist of a high speed wired backbone with numerous wireless Local Area Networks. Mobile computing and wireless subnetworks are increasingly in demand. Mobile routing solutions provide wireless LANs with seamless connectivity to backbone wired systems. However, these solutions do not provide acceptable performance. Wireless networks have distinct transmissioncharacteristics which present challenges to achieving efficient performance.Performance over wireless links is limited by high error rates, mobility, and low bandwidth. We have studied the performance of TCP and NFS over 15 pgs

TR 3128 An End-to-End Send Time Based Flow Control Scheme   Ashok K. Agrawala, Dheeraj Sanghi, and Leyuan Shi

We recently introduced a new transport protocol, called DTP, which uses send time control as its flow control scheme. In this scheme, the time at which a packet is sent by a source is computed from estimates of round-trip time, traffic in the network, and bottleneck service time. In this paper, we propose an estimation technique for send-time control scheme. The estimation scheme proposed here reflects the characteristics of network dynamics which have been observed on the Internet. The results show that DTP performs much better than TCP in all the scenarios considered.

TR 3181 Design and Implementation of Maruti-II   Manas Saksena, James da Silva and Ashok K. Agrawala December 1993

The design and development of integrated systems that support dependable operation of mission critical applications with real-time requirements poses challenging problems for systems designer and developers. The Maruti system is being designed to address integrated solutions for such applications, from the development of the application to the operating system support for their execution. Maruti has been designed as a time-driven system to provide temporal determinacy. In this paper, we present the design philosophy of the Maruti system, as well as discuss the design and implementaiton of Maruti-II. 23 pgs.

TR 3492 Design & Performance Study of a Flexible Traffic Shaper for High Speed Network  s S. Radhakrishnan, S.V. Raghavan and Ashok K. Agrawala June 1995

In networks supporting distributed multimedia, maximizing bandwidth utilization and providing performance guarantees are two incompatible goals. Heterogeneity of the multimedia sources calls for effective congestion control schemes to satisfy the diverse Quality of Service (QoS) requirements of each application. These include admission control at connection set up, traffic control at the source ends and efficient scheduling schemes at the switches. The emphasis in this paper is on traffic control at the source ends. Traffic control schemes have two functional roles. One is traffic enforcement as a supplement to the admission control policy. The other is shaping the input traffic so that it becomes amenable to the scheduling mechanism at the switches for providing the required QoS guarantees. Studies on bursty sources have shown that burstiness promotes statistical multiplexing at the cost of possible congestion. Smoothing the traffic helps in providing guarantees at the cost o f bandwidth utilization. The need for a flexible scheme which can provide a reasonable compromise between the utilization and guarantees is imminent. We present the design and performance study of a flexible traffic shaper which can adjust the burstiness of input traffic to obtain reasonable utilization while maintaining statistical service guarantees. The performance of the traffic shaper for bursty sources is studied using simulation.

TR 2737 Deterministic Modeling and Transient Analysis of a Network Processor with Cross Traffic   Bijendra N. Jain, and Ashok K. Agrawala August 1991

In this paper, we consider a single network processor which simultaneously processes packets over a given virtual circuit as well as those relating to cross traffic. A sequence of such network processors may be used to model the flow of packets between a given source-destination pair of hosts in a network. An approximate model of the processor is proposed which is shown to be exact provided cross traffic is reasonably distributed over any given time interval. The approximate model has been analyzed from several different viewpoints to show that it results in good estimates of the departure time of packets as they are relayed through it. The model has also been used to propose optimum packet submission times which result in minimum transit delay and/or inter-packet departure times. Such a model is useful in analyzing flow control schemes over a virtual circuit when the latter is viewed as a tandem of network processor in a communication network. 18 pgs.

TR 2842 Development and Deployment of Resilient Real-Time, Mission-Critical Applications   Daniel Mosse, and Ashok K. Agrawala March 1995

In real-time systems, fault tolerance has always been difficult to achieve, due to the timing and resource requirements. We introduce here a model for developing resilient applications, where the fault tolerance aspects are inherent in the model. We present in this paper a fault tolerance scheme that is divided into three levels, namely at the unit level, the application level, and the system level. At the unit level, we use monitors that carry out detection, reporting, and handling. At the application level, we use different types of replication to implement fault masking. Finally, at the system level, we use the concept of scenarios which define the different modes of operations that the system can be executing. 18 pgs.

TR 2767 DTP: An Efficient Transport Protocol   Dheeraj Sanghi, and Ashok K. Agrawala October 1991

We recently introduced a new flow control scheme [AgSa91], called send time control , which was designed based on a deterministic model of virtual circuits in a computer network. In this scheme, the time at which a packet is sent by a source is computed from estimates of round-trip time, traffic in the network and bottleneck service time. In this paper, we describe a new transport protocol, called DTP, which uses send time control as its flow control scheme. Preliminary measurements of coast-to-coast connections over the Internet show significant performance improvement over TCP which is the most commonly used transport protocol in the Internet today. 10 pgs.

TR 3504 Designing Temporal Controls   Ashok K. Agrawala, Seonho Choi & Leyuan Shi July 1995

Traditional control systems have been designed to exercise control at regularly spaced time instants. When a discrete version of the system dynamics is used, a constant sampling interval is assumed and a new control value is calculated and exercised at each time instant. In this paper we formulate a new control scheme, temporal control, in which we not only calculate the control value but also decide the time instants when the new values are to be used. Taking a discrete, linear, time-invariant system, and a cost function which reflects a cost for computation of the control values, as an example, we show the feasibility of using this scheme. We formulate the temporal control scheme as a feedback scheme and,through a numerical example, demonstrate the significant reduction in cost through the use of temporal control.

TR 2688 Exmon: A Tool for Resource Monitoring of Programs   Partho P. Mishra, Olafur Gudmundsson, and Ashok K. Agrawala June 1991

It is often necessary to know the usage of system resources, such as cpu time, number of disk accesses and so on, by a program. Knowledge of a program's resource usage profile over time is specially useful. Standard tools available under UNIX offer limited facilities to obtain this kind of information and usually provide the desired information only after a program completes execution. In this report we describe a tool, called Exmon, designed to operate under BSD UNIX, which provides the resource profile of a process as it executes. Exmon allows users to interactively control the execution of a user program and to selectively profile specific portions of the code. We present the results of profiling some application programs and discuss the limitations of Exmon due to the current method of resurce accounting on UNIX systems. 15 pgs.

TR 2909 Experimental Assessment of End-to End Behavior on Internet   Dheeraj Sanghi, Ashok Agrawala, Olafur Gudmundsson, and Bijendra Jain June 1992

Over the last decade Internet has grown by orders of magnitude from about a thousand hosts to over a million hosts. Many of the protocols that were designed many years ago continue to be used, even though the network currently supports faster links over a much larger geographical area. It is not clear if the assumptions made in the design of control schemes still hold, particularly when we consider end-to-end behavior of paths in the network, today. This paper describes a simple experiment designed to capture end-to-end behavior of the Internet. The measurements indicate that the IP level service provided in the network yields high losses, duplicates and reorderings of packets. In addition, the roundtrip transit delay varies significantly. These measurements indicate that the network may have several problems which sitll need to be analysed in order to improve the efficiency of protocols and control mechanisms that it uses. 9 pgs.

TR 2845 MARUTI An Approach to Real-Time System Design   Daniel Mosse, Manas C. Saksena, and Ashok K. Agrawala March 1992

No abstract available 17 pgs

TR 3256 Mission-Oriented Replication of Periodic Tasks in Real-Time Distributed Systems   Sheng-Tzong Cheng, Shyh-In Hwang and Ashok K. Agrawala April 1994

We consider the mission-oriented replication problem of a set of periodic real-time tasks where each task can be decomposed into several modules and intermodule communications. The objective is to find an allocation in which there exists a feasible schedule for the given task set. In this paper, we adopt a communication model where the replication of modules is not for the sake of fault tolerance but for increasing the degree of schedulability. To solve the problem, we develop a replication technique and embed the technique in a simulated annealing algorithm. Experimental results show that such replication may lead to a higher degree of schedulability and obtain a feasible solution. 24 pgs.

TR 2929 Modeling of Cross Traffic in Conjunction with Deterministic Analysis of Virtual Circuits   Sheng-Tzong Cheng, and Ashok Agrawala August 1994

The design and performance studies of computer networks have traditionally used stochastic models even though it is well recognized that there are strong deterministic dependences in the behavior of components of a network which are not reflected in such a model. Recently deterministic models have been formulated for a single virtual circuit and used for the design of flow control schemes. In this paper we extend the deterministic model to take into account the network topology and all the virtual circuits using the network. The basic model of a single server with several virtual circuits through it is introduced first. Next, the model for virtual circuits is formulated focusing primarily on the departure time of packets from various servers. Performance measures such as transit time and throughput can be assessed on packet by packet basis, giving a complete, dynamic characterization of the network. 24 pgs.

TR 2695 Modeling of Cross Traffic in Conjunction with Deterministic Analysis of Queues   Ashok K. Agrawala and Dheeraj Sanghi June 1991

There has been a growing interest in modeling virtual circuits as deterministic servers in tandem. The basic approach used in deterministic models assumes that there is no cross traffic or that it can be modeled as a known increase in the service time. In this paper, we extend the deterministic models to reflect the effect of cross traffic. A new flow control scheme based on our model is presented. This scheme takes into account the presence of cross traffic, and adapts as the cross traffic changes. Simulation results are presented and performance is compared with other flow control schemes. The results show that our scheme performs better than the window-based flow control scheme in TCP. 11 pgs.

TR 3411 Notes on Symbol Dynamics   Ashok K. Agrawala and Christopher Landauer February 1995

This paper introduces a new formulation of dynamic systems that subsumes both the classical discrete and differential equation models as well as current trends in hybrid models. The key idea is to express the system dynamics using symbols to which the notion of time is explicitly attached. The state of the system is described using symbols which are active for a defined period of time. The system dynamics is then represented as relations between the symbolic representations. We describe the notation and give several examples of its use. 11 pgs.

TR 2582 On Resource Management in Hard Real-Time Distributed Operating Systems   Olafur Gudmundsson, Keng-Tai Ko, Yiheng Shi, and Ashok K. Agrawala January 1992

This paper presents a comprehensive model of operating systems from the view point of resource management. The concept of resources is extended to include software components as logical resources. With this extension, the functions of operating systems can be coherently considered as that of resource management. We investigate the characteristics of resources and the requests that affect resource management principles. Also presented are the design philosophy and structure of MARUTI , a hard real-time operating system that is designed based on this model. This view is extremely important to hard real-time operating systems in which the satisfaction of time constraints for services is critical. This model provides a framework under which service timing could be explicitly controlled. 14 pgs.

TR 3020 Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications   Sheng-Tzong Cheng, and Ashok K. Agrawala March 1994

We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it, the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communcation cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a brahcn-and-bound method to find an optimal solution as well as an approximation approach for suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has the complexity of O(n 2 M) , while that approximation solution has O(n M ) , where n is the number of processors in the system and M is the number of tasks in the graph. 2n 42 Formulas should read O(n 2 M) and O(n M ) 28 pgs.

TR 3020.1 Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications Revised Version   Sheng-Tzong Cheng and Ashok K. Agrawala October 1994

We consider the replication problem of series-parallel(SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor commmunication. We call it, the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communicaiton model where the prupose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communication cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a branch-and-bound method to find an optimal solution as well as an approximation approach for suboptimal solution. The numerical results show that such replication may lead to a lower cost than the otpimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has the complexity of O(n2 2n M), while the approximation solution has O(n4 M2), where n is the number of processor s in the system and M is the number of tasks in the graph.

TR 3216 Optimization in Non-Preemptive Scheduling for Aperiodic Tasks   Shyh-In Hwang, Sheng-Tzong Cheng and Ashok K. Agrawala January 1994

Real-time computer systems have become more and more important in many applications, such as robot control, flight control, and other mission-critical jobs. The correctness of the system depends on the temporal correctness as well as the functional correctness of the tasks. We propose a scheduling algorithm based on an analytic model. Our goal is to derive the optimal schedule for a given set of aperiodic tasks such that the number of rejected tasks is minimized, and then the finish time of the schedule is also minimized. The scheduling problem with a nonpreemptive discipline in a uniprocessor system is considered. We first show that if a total ordering is given, this can be done in O(n2) time by dynamic programming technique, were n is the size to the task set. When the restriction of the total ordering is released, it is known to be NP-complete [3]. We discuss the super sequence [18] which has been shown to be useful in reducing the search space for testing the feasibility of a task set. By extendng the idea and introducing the concept of conformation, the scheduling process can be divided into two phases: computing the pruned search space and computing the optimal schedule for each sequence in the search space. While the complexity of the algorithm in the worst case remains exponential, our simulation results show that the cost is reasonable for the average case. 44 pgs.

TR 2772 Performance Prediction of Message Passing SIMD Multiprocessor Systems   Sam H. Noh, and Ashok K. Agrawala October 1991

The focus of this paper is twofold. First, the prediction of the execution signature prior to execution/implementation based on a more informative characterization of the workload, and second, the definition of a more general form of speedup, efficiency, and efficacy stemming from previous works, which may be used as parameters in the allocation of processors for multiprogramming of multiprocessor systems. The approach we take is to identify in the parallel algorithm the properties inherent to the algorithm and those that are system dependent. By characterizing the algorithm as an Augmented Task Graph (ATG) one is able to identify these features. Based on this characterization, one can obtain an estimate of the execution signature of the parallel algorithm on a multiprocessor system prior to execution and coding. Our method is aimed at multiprocessor systems based on the SIMD paradigm. We also define relative parameters such as relative speedup, relative efficiency, and relative efficacy to make a fair comparison between the use of different number of processors. Our prediction method and relative parameters defined allow us to 1) reduce the extensive experiments needed to obtain a single parameter characterization, 2) eliminate the need for the execution time of the algorithm on a single processor, and 3) make an objective performance comparison of different algorithms on the same multiprocessor system. 16 pgs.

TR 3168 Perturbation Analysis and Variance Properties   Leyuan Shi and Ashok K. Agrawala October 1993

Sample path derivatives can be used as derivative estimates of performance measures in stochastic discrete event systems such as computer networks and communication systems. These derivative estimates can be easily calculated based on a single sample path using the technique of Infinitesimal Perturbation Analysis (IPA). Usually, there exists more than one way to represent a parametric family of random variables or stochastic processes with given marginal probability distributions. Different representations often give rise to different sample path derivatives which have different variances. Previous results showed that inversion is a representation that usually gives a small variance. In this note we illustrate that variance reduction can be further expected if we use -function in sample path derivatives. 11 pgs.

TR 2697 Real-Time Heterogeneous Communication Support in MARUTI   Andrew P. Balinsky, Ashok K. Agrawala, and Olafur Gudmundsson June 1991

Heterogeneous support is essential for complex real-time systems. This paper describes how heterogeneous communication support was added to MARUTI, a distributed, real-time operating system. The design takes short cuts where feasible, which is essential for real-time system operation. XDR provides the low-level data translation mechanism. This work is an wxtension of existing work which does not take real-time explicitly into account. 12 pgs.

TR 2857 Real-Time UNITY: A New Method for Specification and Verification of Real-Time Systems   Ashok K. Agrawala, and Bojan Groselj March 1992

Specification and verification of real-time systems is a complex and expensive task. The existing methods are either ad hoc, or too formal to be used in practice. We propose a new method that employs a program-like specification of a real-time system. Using this specification, one can formally prove safety and liveness properties of the system. More importantly, the specification can be easily transformed into a simulation program. A simulation enables verification of timing properties (e.g., verification of deadlines), as well as different scheduling and allocation policies. Our approach is based on UNITY, a system for specification, verification, and design of parallel programs. We modify UNITY by adding time as a parameter and by enforcing a deterministic execution of the system specification. Real-Time UNITY enables specification of timeouts, buffers, communication channels, resources, deadlines, signals, interrupts, messages, as well as different scheduling algorithms (e.g., preemption). 15 pgs.

TR 3377 Scheduling an Overloaded Real-Time System   Shyh-In Hwang, Chia-Mei Chen and Ashok K. Agrawala November 1994

The real-time systems differ from the conventional systems in that every task in the real-time system has a timing constraint. Failure to execute the tasks under the timing constraints may result in fatal errors. Sometimes, it may be impossible to execute all the tasks in the task set under their timing constraints. Considering a system with limited resources, one solution to handle the overload problem is to reject some of the tasks in order to generate a feasible schedule for the rest. In this paper, we consider the problem of scheduling a set of tasks without preemption in which each task is assigned criticality and weight. The goal is to generate an optimal schedule such that all of the critical tasks are scheduled and then the non-critical tasks are included so that the weight of rejected non-critical tasks is minimized. We consider the problem of finding the optimal schedule in two steps. First, we select a permutation sequence of the task set. Secondly, a pseudo-polynomial algorithm is proposed to generate an optimal schedule for the permutation sequence. If the global optimal is desired, all permutation sequences have to be considered. Instead, we propose to incorporate the simulated annealing technique to deal with the large search space. Our experimental results show that our algorithm is able to generate near optimal schedules for the task sets in most cases while considering only a limited number of permutations. 29 pgs.

TR 3392 Scheduling of Periodic Tasks with Relative Timing Constraints   Sheng-Tzong Cheng and Ashok K. Agrawala January 1995

The problem of non-preemptive scheduling of a set of periodic tasks on a single processor has been traditionally considering the ready time and deadline on each task. As a consequence, a feasible schedule finds that in each period one instance of each task starts the execution after the ready time and completes the execution before the deadline. Recently, the timing requirements of the real-time systems emerge that the relative timing constraints are imposed on the consecutive executions of each task. In this paper, we consider the scheduling problem of the periodic tasks with the relative timing constraints imposed on two consecutive executions of a task. We analyze the timing constraints and derive the scheduling window for each task instance. Based on the scheduling window, we present the time-based approach of scheduling a task instance. The task instances are scheduled one by one based on their priorities assigned by the proposed algorithms in this paper. We conduct the experiments to compare the schedulability of the algorithms. 21 pgs.

TR 2698 Temporal Analysis and its Application in Non-Preemptive Scheduling   Manas C. Saksena and Ashok K. Agrawala June 1991

In the problem of non-preemptive scheduling of a set of tasks on a single processor, each task has a ready time, a deadline and a computation time. A feasible schedule for this set requires that a start time be assigned to each task. The approaches taken for scheduling often use search techniques and may reduce the search by using heuristics. In this paper we present a technique for analyzing the temporal relations among the tasks to establish pairwise relationships among them. These relationships can then be used effectively to reduce the complexity of scheduling these tasks. We present simulation results to confirm the usefulness of temporal analysis as a phase prior to scheduling. 13 pgs.

TR 2694 The MARUTI System and its Implementation   Daniel Mosse, Olafur Gudmundsson, and Ashok K. Agrawala June 1991

Design and development of integrated systems which support real time, fault tolerant, heterogeneous, and secure operation pose new and interesting challenges for system designers and developers. The MARUTI system efforts are aimed at adddressing the needs of such systems. In this paper, basic principles, structure, and design of the MARUTI system are presented. We also present the system prototype, which has been implemented on a UNIX platform. The approach used in mapping the MARUTI system objects into UNIX processes is presented along with a brief discussion of our implementation experiences. 14 pgs.

TR 2891 The RPT Parallel Gaussian Elimination Algorithm   Sam H. Noh, Soo-Mook Moon, and Ashok K. Agrawala April 1992

We present an algorithm for the Gaussian elimination problem that reduces the length of the critical path compared to the algorithm of Lord et at. This is done by redefining a notion of task. For all practical purposes, the issues of communication overhead and pivoting cannot be overlooked. We consider these issues for the new algorithm as well. Timing results of this algorithm as executed on the CM-2 model of the Connection Machine are pressented. Another contribution of this paper is the use of logical pivoting for stable computation of the Gaussian elimination algorithm. Pivoting is essential in producing stable results. When pivoting occurs, an interchange of two rows is required. A physical interchange of the values can be avoided by providing a permutation vector in globally accessible location. We show experimental results that substantiate the use of logical pivoting. 11 pgs.

TR 2918 Virtual Circuits with Cross Traffic: Model, Analysis and Parameter Estimation   Bijendra N. Jain, Ashok K. Agrawala, and Dheeraj Sanghi June 1992

In this paper, we model the flow of packets between a given pair of source-destination hosts as a virtual circuit which passes through a tandem of network processors. Each network processor is assumed to concurrently process packets relating to other source-destination pairs of hosts (also termed cross traffic). As such, the model of the virtual circuit takes into account the net effect of all cross traffic that passes through the network processors. The model of a virtual circuit proposed in this paper has been analyzed to obtain inter-packet departure time as a function of inter-packet send time. This function is used to propose a rate-based flow control scheme that results in minimum transit delay and/or maximum throughput. A scheme to estimate critical parameters of the function from on-line measurements has been proposed. This scheme may also be used in conjunction with the proposed rate-based flow control shcnme. 24 pgs.

MIND Lab // Publications // Research // Information // Photo Gallery // Home