More Web Proxy on the site http://driver.im/

research-article

Real-Time Communication in Multihop Networks

Authors:

D. FerrariAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 5, Issue 10

Pages 1044 - 1056

https://doi.org/10.1109/71.313121

Published: 01 October 1994 Publication History

Abstract

Communication in real-time systems has to be predictable, because unpredictable delaysin the delivery of messages can adversely affect the execution of tasks dependent onthese messages. We develop a scheme for providing predictable interprocesscommunication in real-time systems with (partially connected) point-to-pointinterconnection networks, which provide guarantees on the maximum delivery time formessages. This scheme is based on the concept of a real-time channel, a unidirectionalconnection between source and destination. A real-time channel has parameters thatdescribe the performance requirements of the source-destination communication, e.g.,from a sensor station to a control site. Once such a channel is established, thecommunications subsystem guarantees that these performance requirements will be met.We concentrate on methods to compute guarantees for the delivery time of messagesbelonging to real-time channels. We also address problems associated with allocatingbuffers for these messages and develop a scheme that preserves delivery timeguarantees.

References

[1]

{1} W. Zhao and K. Ramamritham, "Virtual time CSMA protocols for hard real-time communication," IEEE Trans. Software Eng., vol. 13, pp. 938-952, Aug. 1987.

Digital Library

[2]

{2} J. F. Kurose, M. Schwartz, and Y. Yemini, "Controlling window protocols for time-constrained communication in multiple access networks," IEEE Trans. Commun., vol. 36, pp. 41-49, Jan. 1988.

[3]

{3} W. Zhao, J.A. Stankovic, and K. Ramamritham, "A multi-access window protocol for transmission of time constrained messages," in Proc. 8th Int. Conf. Distrib. Computing Syst., 1988, pp. 384-392.

[4]

{4} J. F. Kurose, M. Schwartz, and Y. Yemini, "Multiple-access protocols and time-constrained communication," ACM Computing Surv., vol. 16, pp. 43-70, Mar. 1984.

Digital Library

[5]

{5} J.K. Strosnider and T.E. Marchok, "Responsive, deterministic IEEE 802.5 token ring scheduling," J. Real-Time Syst., vol. 1, pp. 133-158, Sept. 1989.

Digital Library

[6]

{6} D. Ferrari, "Guaranteeing performance for real-time communication in wide-area networks," Tech. Rep. UCB/CSD 89/485. Comput. Sci. Div., Dept. of Elec. Eng. and Comput. Sci., Univ. of California, Berkeley, CA, USA, Jan. 1989.

[7]

{7} D. Ferrari and D. C. Verma, "A scheme for real-time channel establishment in wide-area networks," IEEE J. Selected Areas Commun., vol. 8, pp. 368-379, Apr. 1990.

Digital Library

[8]

{8} D. P. Anderson, "A software architecture for network communication," in Proc. 8th Int. Conf. Distrib. Computing Syst., 1988, pp. 376-383.

[9]

{9} D. P. Anderson and D. Ferrari, "The DASH project: An overview," Tech. Rep. 84/405, Comput. Sci. Div., Dept. of Elec. Eng. and Comput. Sci., Univ. of California, Berkeley, CA, USA, Feb. 1988.

[10]

{10} J. W. Dolter, P. Ramanathan, and K. G. Shin, "A microprogrammable VLSI routing controller for HARTS," in Proc. IEEE Int. Conf. Comput. Design: VLSI in Comput., 1989, pp. 160-163.

[11]

{11} P. Ramanathan, D. D. Kandlur, and K.G. Shin, "Hardware assisted software clock synchronization for homogeneous distributed systems," IEEE Trans. Comput., vol. 39, pp. 514-524, Apr. 1990.

Digital Library

[12]

{12} R. L. Cruz, "A calculus for network delay and a note on topologies of interconnection networks," Ph.D. dissertation, Tech. Rep. UILU-ENG-87-2246, Univ. of Illinois at Urbana-Champaign, USA, July 1987.

[13]

{13} D. P. Anderson, S. Y. Tzou, R. Wahbe, R. Govindan, and M. Andrews, "Support for continuous media in the DASH system," in Proc. 10th Int. Conf. Distrib. Computing Syst., 1990, pp. 54-61.

[14]

{14} D. P. Anderson, R. G. Herrtwich, and C. Schaefer, "SRP: A resource reservation protocol for guaranteed performance communication in the Internet," Tech. Rep. TR-90.006, Int. Comput. Sci. Inst., Berkeley, CA, USA, Feb. 1990.

Digital Library

[15]

{15} D. D. Kandlur and K. G. Shin, "Traffic routing for networks with virtual cut-through capability," in Proc. 10th Int. Conf. Distrib. Computing Syst., 1990, pp. 398-405.

[16]

{16} M. L. Dertouzos, "Control robotics: The procedural control of physical processes," in Proc. IFIP Congress, 1974, pp. 807-813.

[17]

{17} C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," J. ACM, vol. 20, pp. 46-61, Jan. 1973.

Digital Library

[18]

{18} J. Y.-T. Leung and J. Whitehead, "On the complexity of fixed-priority scheduling of periodic, real-time tasks," Performance Evaluation, vol. 2, pp. 237-250, Dec. 1982.

[19]

{19} D. E. Comer and R. Yavatkar, "FLOWS: Performance guarantees in best effort delivery systems," Tech. Rep. CSD-TR-791, Comput. Sci. Dept., Purdue Univ. West Lafayette, IN,-USA, July 1988.

[20]

{20} I. Cidon and I. S. Gopal, "PARIS: An approach to integrated high-speed private networks," Int. J. Digital Analog Cabled Syst., vol. 1, pp. 77-86, Apr. 1988.

[21]

{21} I. Cidon, I. Gopal, G. Grover, and M. Sidi, "Real-time packet switching: A performance analysis," IEEE J. Selected Areas Commun., vol. 6, pp. 1576-1586, Dec. 1988.

Digital Library

[22]

{22} S. J. Golestani, "Congestion-free transmission of real-time traftic in packet networks," in Proc. INFOCOM, 1990, pp. 527-536.

[23]

{23} S. J. Golestani, "A stop-and-go queueing framework for congestion management," in Proc. SIGCOMM, 1990, pp. 8-18.

Digital Library

[24]

{24} M.-S. Chen, K. G. Shin, and D. D. Kandlur, "Addressing, routing, and broadcasting in hexagonal mesh multiprocessors," IEEE Trans. Comput., vol. 39, pp. 10-18, Jan. 1990.

Digital Library

[25]

{25} J. Lehoczky, L. Sha, and Y. Ding, "The rate monotonic scheduling algorithm: Exact characterization and average case behavior," in Proc. Real-time Syst. Symp., 1989, pp. 166-171.

Cited By

Kashif HPatel HFischmeister S(2016)Path Selection for Real-Time Communication on Priority-Aware NoCsACM Transactions on Design Automation of Electronic Systems10.1145/286657221:3(1-25)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2866572
Zhang SZhang QXiao SZhu TGu YLin Y(2015)Cooperative Data Reduction in Wireless Sensor NetworkACM Transactions on Embedded Computing Systems10.1145/278675514:4(1-26)Online publication date: 8-Dec-2015
https://dl.acm.org/doi/10.1145/2786755
Kiasari AJantsch ALu Z(2013)Mathematical formalisms for performance evaluation of networks-on-chipACM Computing Surveys10.1145/2480741.248075545:3(1-41)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1145/2480741.2480755
Show More Cited By

Real-Time Communication in Multihop Networks

Recommendations

Real-time communication in FieldBus multiaccess networks
RTAS '95: Proceedings of the Real-Time Technology and Applications Symposium

There has been an increasing need of timely and predictable communication services for embedded real-time systems in automated factories and industrial process controls. Work has been done on real-time communication with deadline guarantees in point-to-...
Deferring Real-Time Traffic for Improved Non-Real-Time Communication in FDDI Networks

The fiber distributed data interface (FDDI) is suitable for real-time communication because of the high speed and the performance guarantees it provides. However, these guarantees are achieved at the expense of non-real-time traffic because the real-...
A note on dependable real-time communication in multihop networks

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) forward error recovery approach and (ii) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 5, Issue 10

October 1994

114 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © Copyright © 1994 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 October 1994

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kashif HPatel HFischmeister S(2016)Path Selection for Real-Time Communication on Priority-Aware NoCsACM Transactions on Design Automation of Electronic Systems10.1145/286657221:3(1-25)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2866572
Zhang SZhang QXiao SZhu TGu YLin Y(2015)Cooperative Data Reduction in Wireless Sensor NetworkACM Transactions on Embedded Computing Systems10.1145/278675514:4(1-26)Online publication date: 8-Dec-2015
https://dl.acm.org/doi/10.1145/2786755
Kiasari AJantsch ALu Z(2013)Mathematical formalisms for performance evaluation of networks-on-chipACM Computing Surveys10.1145/2480741.248075545:3(1-41)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1145/2480741.2480755
Rahmati DMurali SBenini LAngiolini FDe Micheli GSarbazi-Azad HRoychowdhury J(2009)A method for calculating hard QoS guarantees for Networks-on-ChipProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687507(579-586)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687507
Channakeshava KRavindran BJensen E(2006)Utility Accrual Channel Establishment in Multihop NetworksIEEE Transactions on Computers10.1109/TC.2006.6255:4(428-442)Online publication date: 1-Apr-2006
https://dl.acm.org/doi/10.1109/TC.2006.62
Mahapatra AAnand KAgrawal D(2006)QoS and energy aware routing for real-time traffic in wireless sensor networksComputer Communications10.1016/j.comcom.2004.12.02829:4(437-445)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1016/j.comcom.2004.12.028
Lee S(2003)Real-time wormhole channelsJournal of Parallel and Distributed Computing10.1016/S0743-7315(02)00055-263:3(299-311)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1016/S0743-7315%2802%2900055-2
Raghavan SManimaran GSiva Ram Murthy C(2002)A note on dependable real-time communication in multihop networksComputer Communications10.1016/S0140-3664(02)00089-025:17(1673-1683)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1016/S0140-3664%2802%2900089-0
Manimaran GMerugu SManikutty AMurthy C(2001)Integrated scheduling of tasks and messages in distributed real-time systemsEngineering of distributed control systems10.5555/770609.770616(99-112)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.5555/770609.770616
Kim JShin K(2001)Performance Evaluation of Dependable Real-Time Communication with Elastic QoSProceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS)10.5555/647882.738090(295-303)Online publication date: 1-Jul-2001
https://dl.acm.org/doi/10.5555/647882.738090
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents