Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism

Abstract

This paper considers the support of real-time applications in an Integrated Services Packet Network (ISPN). We first review the characteristics of real-time applications. We observe that, contrary to the popular view that real-time applications necessarily require a fixed delay bound, some real-time applications are more flexible and can adapt to current network conditions. We then propose an ISPN architecture that supports two distinct kinds of real-time service: guaranteed service, which is the traditional form of real-time service discussed in most of the literature and involves pre-computed worst-case delay bounds, and predicted service which uses the measure performance of the network in computing delay bounds. We then propose a packet scheduling mechanism that can support both of these real-time services as well as accommodate datagram traffic. We also discuss two other aspects of an overall ISPN architecture: the service interface and the admission control criteria.

References

1. 1 R. Chipalkatti, J. Kurose, and D. Towsley. Schedulin9 Policies/or Real-Time and Non-Real. Time Traffic in a Statistical Multiplewer, In Proceedings of GlobeCom '89, pp 774-783, 1989.
2. 2 S. Casner private communication, 1992.
3. 3 R. Cocchi, D. Estrin, S. Shenker, and L. Zhang. A Study of Priority Pricing in Multiple Service Class Networks, In Proceedings of SIGCOMM '91, pp 123-130, 1991.
4. 4 A. Demers, S. Keshav, and S. Shenker. Analysis and Simulation o/a Fair Queueing Algorithm, In Journal of Internetworking: Research and Experience, 1, pp. 3-26, 1990. Also in Proc. ACM SIGCOMM '89, pp 3-12.
5. 5 J. DeTreville and D. Sincoskie. A Distributed Experimental Communications System, In IEEE $SAC, Vol. 1, No. 6, pp 1070-1075, December 1983.
6. 6 D. Ferrari. Distributed Delay Jitter Control in Packet- Switching Internetworks, preprint, 1991.
7. 7 D. Ferrari and D. Verma. A Scheme for Real-Time Channel Establishment in Wide-Area Networks, In IEEE JSAC, Vol. 8, No. 4, pp 368-379, April 1990.
8. 8 S. J. Golestani. A Stop and Go Queueing Framework /or Congestion Management, In Proceedings of SIG- COMM '90, pp 8-18, 1990.
9. 9 S. J. Golestani. Duration-Limited Statistical Multiplexing o/Delay Sensitive Traffic in Packet Networks, In Proceedings of INFOCOM '91, 1991.
10. 10 R. Gu~rin and L. Grin. A Unified Approach to Bandwidth Allocation and Access Control in Fast Packet- Switched Networks, To appear in Proceedings of IN- FOCOM '92.
11. 11 R. Gu~rin, H. Ahmadi, and M. Naghshineh. Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks, In iEEE JSAC, Vol. 9, No. 9, pp 968-981, September 1991.
12. 12 J. Hyman and A. Lazar. MARS: The Magnet Ii Real- Time Scheduling Algorithm, In Proceedings of SIG- COMM '91, pp 285-293, 1991.
13. 13 J. Hyman, A. Lazar, and G. Pacifici. Real-Time Scheduling with Quality of Service Constraints, In IEEE JSAC, Vol. 9, No. 9, pp 1052-1063, September 1991.
14. 14 V. Jacobson and S. Floyd private communication, 1991.
15. 15 V. Jacobson private communication, 1991.
16. 16 C. Kalmanek, H. Kanakia, and S. Keshav. Rate Controlled Servers for Very High-Speed Networks, In Proceedings of GlobeCom '90, pp 300.3.1-300.3.9, 1990.
17. 17 C. Liu and J. Layland. Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment, In Journal of ACM, 20, pp. 46-61, 1973.
18. 18 S. Lu and P. R. Kumar. Distributed Scheduling Based on Due Dates and Buffer Priorities, In IEEE Transactions on Automatic Control, 36, pp 1406-1416, 1991.
19. 19 A. Parekh and R. Gallager. A Generalized Processor Sharing Approach to Flow Control- The Single Node Case, In Technical Report LIDS-TR-2040, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1991.
20. 20 A. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks, In Technical Report LIDS-TR-2089, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1992.
21. 21 H. Schulzrinne, J. Kurose, and D. Towsley. Congestion Control .for Real-Time Traffic, In Proceedings of INFOCOM '90.
22. 22 D. Verma, H. Zhang, and D. Ferrari. Delay Jitter Control /or Real-Time Communication in a Packet Switching Network, In Proceedings of TriCom '91, pp 35-43, 1991.
23. 23 C. Weinstein and J. Forgie. Experience with Speech Communication in Packet Networks, In IEEE JSAC, Vol. 1, No. 6, pp 963-980, December 1983.
24. 24 H. Zhang and S. Keshav. Comparison o.{ Rate-Based Service Disciplines, In Proceedings of SIGCOMM '91, pp 113-121, 1991.
25. 25 L. Zhang. A New Architecture/or Packet Switching Network Protocols, In Technical Report LCS-TR-455, Laboratory for Computer Science, Massachusetts Institute of Technology, 1989.
26. 26 L. Zhang. VirtualClock: A New Traffic Control Algorithm for Packet Switching Networks, In ACM Transactions on Computer Systems, Vol. 9, No. 2, pp 101- 124, May 1991. Also in Proc. ACM SIGCOMM '90, pp 19-29.
27. 27 L. Zhang. A Comparison of Traffic Control Algorithms for High-Speed Networks, In 2rid Annual Workshop on Very High Speed Networks, 1991.

Index Terms

• Networks

  • Network services

    • In-network processing

  • Network types

    • Packet-switching networks

    • Wired access networks

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making