Real-time communication in multihop networks
IEEE Transactions on Parallel and Distributed SystemsPublished 1 January 1994
D.D. Kandhlur, Kang G. Shin, D. Ferrari
Citations157
SJR quartileQ1
SJR score2.10
SNIP2.28
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A scheme for providing predictable interprocess communication in real-time systems with (partially connected) point-to-point interconnection networks, which provides guarantees on the maximum delivery time for messages.
Abstract
Communication in real-time systems has to be predictable, because unpredictable delays in the delivery of messages can adversely affect the execution of tasks dependent on these messages. We develop a scheme for providing predictable interprocess communication in real-time systems with (partially connected) point-to-point interconnection networks, which provide guarantees on the maximum delivery time for messages. This scheme is based on the concept of a real-time channel, a unidirectional connection between source and destination. A real-time channel has parameters that describe the performance requirements of the source-destination communication, e.g., from a sensor station to a control site. Once such a channel is established, the communications subsystem guarantees that these performance requirements will be met. We concentrate on methods to compute guarantees for the delivery time of messages belonging to real-time channels. We also address problems associated with allocating buffers for these messages and develop a scheme that preserves delivery time guarantees.>
Keywords
Computer Science
Journal of the ACMScheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
8,334 Citations1973C. L. Liu, J. W. Layland
The rate monotonic scheduling algorithm: exact characterization and average case behavior
1,461 Citations2003John P. Lehoczky, Lui Sha +1 more
An exact characterization of the ability of the rate monotonic scheduling algorithm to meet the deadlines of a periodic task set and a stochastic analysis which gives the probability distribution of the breakdown utilization of randomly generated task sets are represented.
Performance EvaluationOn the complexity of fixed-priority scheduling of periodic, real-time tasks
1,127 Citations1982Joseph Y.‐T. Leung, Jennifer Whitehead
It is shown that the problem is NP-hard in all but one special case and the complexity of optimal fixed-priority scheduling algorithm is discussed.
IEEE Journal on Selected Areas in CommunicationsA scheme for real-time channel establishment in wide-area networks
1,037 Citations1990D. Ferrari, D.C. Verma
The results are judged encouraging: the approach satisfies the guarantees even in worst case situations, uses the network's resources to a fair extent, and efficiently handles channels with a variety of offered load and burstiness characteristics.
IEEE Transactions on ComputersAddressing, routing, and broadcasting in hexagonal mesh multiprocessors
211 Citations1990Ming-Syan Chen⋆, Kang G. Shin +1 more
An elegant, distributed routing scheme is developed for wrapped H-meshes so that each node in an H-mesh can compute shortest paths from itself to any other node with a straightforward algorithm of O(1) using the addresses of the source-destination pair only, independent of the network's size.
A stop-and-go queueing framework for congestion management
200 Citations1990S. Jamaloddin Golestani
A framework for congestion management in integrated services packet networks based on a particular service discipline, called stop-and-go queueing, is proposed, providing the necessary flexibility in accommodating throughput and end-to-end delay requirements of different connections on an as-needed basis.
International Journal of Digital & Analog Cabled SystemsParis: An approach to integrated high‐speed private networks
197 Citations1988Israel Cidon, Inder S. Gopal
This paper describes a design of a high-speed packet switching system for integrated voice, video and data communications that makes use of a simplified network architecture in order to achieve the low packet delay and high nodal throughput necessary for the transport of voice and video.
ACM Computing SurveysMultiple-access protocols and time-constrained communication
175 Citations1984James F. Kurose, Mischa Schwartz +1 more
A taxonomy for multiple-access protocols is developed in order to characterize common approaches and to provide a framework within which these protocolscan be compared and contrasted.
Support for continuous media in the DASH system
152 Citations2002David P. Anderson, S.-Y. Tzou +3 more
The DASH resource model is defined as a basis for reserving and scheduling resources involved in end-to-end handling of continuous-media information flowing continuously over real time i.e. digital audio or digital video data.
Congestion-free transmission of real-time traffic in packet networks
100 Citations2002S. Jamaloddin Golestani
A strategy for congestion-free communication in packet networks is proposed, which provides guaranteed services per connection with no packet loss and an end-to-end delay which is a constant plus a small bounded jitter term and provides an attractive solution for the transmission of real-time traffic in packets networks.
IEEE Transactions on ComputersHardware-assisted software clock synchronization for homogeneous distributed systems
81 Citations1990Parameswaran Ramanathan, D.D. Kandlur +1 more
A clock synchronization scheme that strikes a balance between hardware and software solutions is proposed, and the guaranteed worst-cast skews can be made insensitive to the maximum variation of message transit delay in the system.
ACM SIGCOMM Computer Communication ReviewA stop-and-go queueing framework for congestion management
76 Citations1990S. Jamaloddin Golestani
IEEE Journal on Selected Areas in CommunicationsReal-time packet switching: a performance analysis
74 Citations1988Israel Cidon, I. Gopal +2 more
The authors model the internal structure of a packet-switching node in a real-time system and characterize the tradeoff between throughput, delay, and packet loss as a function of the buffer size, switching speed, etc.
Real-Time SystemsResponsive, deterministic IEEE 802.5 token ring scheduling
63 Citations1989J.K. Strosnider, T.E. Marchok
This paper presents an algorithmic-based scheduling approach that supports a priori schedulability determination for arbitrary synchronous message sets without the costly development, testing, and tuning of TDM schedules, which allows the IEEE 802.5 standard to support dynamic, adaptive, and reconfigurable run-time environments where the inflexibility ofTDM would be prohibitive.
IEEE Transactions on CommunicationsControlling window protocols for time-constrained communication in multiple access networks
37 Citations1988James F. Kurose, Moshe Schwartz +1 more
An alternate performance model based on a queuing system with impatient customers is developed and protocol performance under the optimal elements of the control policy shows significant improvements over cases in which the protocol is not controlled in this manner.
SRP: A Resource Reservation Protocol for Guaranteed-Performance
20 Citations1990David P. Anderson, Ralf G Herriwich +1 more
This report describes the Session Reservation Protocol (SRP), SRP is defined in the DARPA Internet family of protocols, it allows communicating peer entities to reserve the resources necessary to achieve given performance objectives (delay and throughput).
A microprogrammable VLSI routing controller for HARTS
18 Citations2003J. Dolter, Parameswaran Ramanathan +1 more
The design and implementation of a VLSI routing controller for use in the Hexagonal Architecture for Real-Time Systems (HARTS), which is currently being built, are presented.
A multi-access window protocol for transmission of time constrained messages
16 Citations2003Wei Zhao, John A. Stankovic +1 more
A novel window protocol for transmitting time-constrained messages in a multiaccess network is proposed that explicitly takes time constraints into account and closely approximates the optimal minimum-laxity-first policy.
FLOWS: performance guarantees in best effort delivery systems
14 Citations1989Douglas E. Comer, Raj Yavatkar
The authors describe the concept of flows in detail and present algorithms that implement flows in a high-speed packet-switched network under development at Purdue University.
The DASH Project: An Overview
14 Citations1988David P. Anderson, Domenico Ferrari
The DASH project at UC Berkeley is studying problems arising in the design of large, high-performance distributed systems, and is building an experimental system that combines vertically integrated mechanisms to achieve design goals, while an open system structure is maintained where possible.
A software architecture for network communication
13 Citations2003David P. Anderson
The role of RMS in the DASH communication architecture and techniques and algorithms for providing RMS at different system levels are described.
Guaranteeing Performance for Real-Time Communication in Wide-Area Networks
10 Citations1988Domenico Ferrari
This paper argues that the feasibility of providing performance guarantees in a wide-area network should be investigated, and describes a possible approach, and presents a model of the network to be studied, and discusses its generality.
Traffic routing for multi-computer networks with virtual cut-through capability
5 Citations2002D.D. Kandlur, Kang G. Shin
An approximate algorithm that tries to reduce the cost incrementally by rerouting traffic is developed and is evaluated for two popular network topologies: the hypercube and the C-wrapped hexagonal mesh.
GenesGuaranteeing Performance for Real-Time Communication in Wide-Area
3 Citations1988Domenico Ferrari
The results show miRNA mediated regulation of gene expression levels of nucleoside metabolic pathway genes can impact interindividual variation in expression levels which in turn may influence treatment outcomes.