| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Time-Utility Function-Driven Switched Ethernet: Packet Scheduling Algorithm, Implementation, and Feasibility Analysis
February 2004 (vol. 15 no. 2)
pp. 119-133
Abstract—We present a MAC-layer, soft real-time packet scheduling algorithm called UPA. UPA considers a message model where message packets have end-to-end timeliness requirements that are specified using Jensen's Time-Utility Functions (TUFs). The algorithm seeks to maximize system-wide, aggregate packet utility. Since this scheduling problem is NP-hard, UPA heuristically computes schedules with a quadratic worst-case cost, faster than the previously best CMA algorithm. Our simulation studies show that UPA performs the same as or significantly better than CMA for a broad set of TUFs. Furthermore, we implement UPA and prototype a TUF-driven switched Ethernet system. The performance measurements of UPA from the implementation reveal its strong effectiveness. Finally, we derive timeliness feasibility conditions of TUF-driven switched Ethernet systems that use the UPA algorithm.
[1] 119 H. Kopetz, A. Damm, C. Koza, M. Mulazzani, W. Schwabi, C. Senft, and R. Zainlinger, "Distributed Fault-Tolerant Real-Time Systems: The MARS Approach," IEEE Micro, pp. 25-58, Feb. 1989.[2] C. Venkatramani and T. Chiueh, Supporting Real-Time Traffic on Ethernet Proc. Real-Time Systems Symp., pp. 282-286, Dec. 1994.[3] D.W. Pritty, J.R. Malone, S.K. Banerjee, and N.L. Lawrie, A Real-Time Upgrade for Ethernet Based Factory Networking Proc. Conf. IEEE Industrial Electronics Soc. (IECON), pp. 1631-1637, 1995.[4] W. Kim and J. Srivastava, New Virtual Time CSMA/CD Protocols for Real-Time Communication Proc. IEEE Conf. Comm. for Distributed Applications and Systems, pp. 11-22, 1991.[5] W. Zhao and K. Ramamritham, A Virtual Time CSMA/CD Protocol for Hard Real-Time Communication Proc. IEEE Real-Time Systems Symp., pp. 120-127, Dec. 1986.[6] M.N. El-Derini and M.R. El-Sakka, A CSMA Protocol under a Priority Time Constraint for Real-Time Communication Proc. IEEE Workshop Future Trends of Distributed Computing Systems, pp. 128-134, 1990.[7] W. Zhao, J.A. Stankovic, and K. Ramamritham, A Window Protocol for Transmission of Time-Constrained Messages IEEE Trans. Computers, vol. 39, no. 9, pp. 1186-1203, Sept. 1990.[8] S.K. Kweon and K.G. Shin, Achieving Real-Time Communication over Ethernet with Adaptive Traffic Smoothing Proc. IEEE Real-Time Technology and Applications Symp., pp. 90-100, 2000.[9] J.-F. Hermant and G. LeLann, A Protocol and Correctness Proofs for Real-Time High-Performance Broadcast Networks Proc. IEEE Conf. Distributed Computing Systems, pp. 360-369, 1998.[10] D. Kim, Y. Doh, and Y. Lee, Table Driven Proportional Access Based Real-Time Ethernet for Safety-Critical Real-Time Systems Proc. IEEE Pacific Rim Symp. Dependable Computing, pp. 356-363, 2001.[11] S. Varadarajan and T.-C. Chiueh, Ethereal: A Host-Transparent Real-Time Fast Ethernet Switch Proc. IEEE Conf. Network Protocols, pp. 12-21, Oct. 1998.[12] SIXNET, The Sixnet Industrial Ethernet Switch http:/www.sixnetio.com, 2002.[13] H. Hoang, M. Jonsson, U. Hagström, and A. Kallerdahl, Switched Real-Time Ethernet and Earliest Deadline First Scheduling-Protocols and Traffic Handling Proc. IEEE Workshop Parallel and Distributed Real-Time Systems, pp. 94-99, Apr. 2002.[14] C. Baek-Young, S. Sejun, N. Birch, and J. Huang, Probabilistic Approach to Switched Ethernet for Real-Time Control Applications Proc. IEEE Conf. Real-Time Computing Systems and Applications, pp. 384-388, 2000.[15] H. Zhang, “Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks,” Proc. IEEE, vol. 83, pp. 1374-1396, Oct. 1995.[16] C.L. Liu and J.W. Layland, Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment J. ACM, vol. 20, no. 1, pp. 46-61, 1973.[17] E.D. Jensen, Asynchronous Decentralized Real-Time Computer Systems Real-Time Computing, W.A. Halang and A.D. Stoyenko, eds., NATO Advanced Study Inst., Oct. 1992.[18] K. Chen and P. Muhlethaler, A Scheduling Algorithm for Tasks Described by Time Value Function J. Real-Time Systems, vol. 10, no. 3, pp. 293-312, May 1996.[19] E.D. Jensen, A. Kanevsky, J. Maurer, T. Wheeler, Y. Zhang, D. Wells, T. Lawrence, and P. Hurley, An Adaptive, Distributed Airborne Tracking System Proc. IEEE Workshop Parallel and Distributed Real-Time Systems, Apr. 1999.[20] D.P. Maynard, S.E. Shipman, R.K. Clark, J.D. Northcutt, R.B. Kegley, B.A. Zimmerman, and P.J. Keleher, An Example Real-Time Command, Control, and Battle Management Application for Alpha technical report, Computer Science Dept., Carnegie Mellon Univ., Dec. 1988, Archons Project Technical Report 88121.[21] D.L. Mills, Improved Algorithms for Synchronizing Computer Network Clocks IEEE/ACM Trans. Networking, vol. 3, pp. 245-254, June 1995.[22] J.W.S. Liu, Real-Time Systems. Prentice Hall, 2000.[23] ZNYX Networks, Zx340q Series http://www.znyx.com/ products/netblaster zx340q.htm, 2002.[24] D. Mills, xntpd http://www.eecis.udel.edu/ntp/database/html_xntp3-5.90 xntpd.html, 2002.[25] U. Böhme and L. Buytenhenk, Linux bridge-stp-howto http://www.tldp.org/HOWTOBRIDGE-STP-HOWTO , 2002.[26] J. Wang, Soft Real-Time Switched Ethernet: Best-Effort Packet Scheduling Algorithm, Implementation, and Feasibility Analysis master's thesis, Virginia Tech., Sept. 2002.[27] G. LeLann, Proof-Based System Engineering and Embedded Systems Lecture Notes in Computer Science, G. Rozenberg and F. Vaandrager, eds., vol. 1494, pp. 208-248, Oct. 1998.
Index Terms:
Local-area networks, Ethernet, process control systems, real-time and embedded systems.
Citation:
Jinggang Wang, Binoy Ravindran, "Time-Utility Function-Driven Switched Ethernet: Packet Scheduling Algorithm, Implementation, and Feasibility Analysis," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 2, pp. 119-133, Feb. 2004, doi:10.1109/TPDS.2004.1264796
