Document Open Access Logo

A Linux Real-Time Packet Scheduler for Reliable Static SDN Routing

Authors Tao Qian, Frank Mueller, Yufeng Xin

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2017.25.pdf
  • Filesize: 0.83 MB
  • 22 pages

Document Identifiers

Author Details

Tao Qian
Frank Mueller
Yufeng Xin

Cite As Get BibTex

Tao Qian, Frank Mueller, and Yufeng Xin. A Linux Real-Time Packet Scheduler for Reliable Static SDN Routing. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.25

Abstract

In a distributed computing environment, guaranteeing the hard deadline for real-time messages is essential to ensure schedulability of real-time tasks. Since capabilities of the shared resources for transmission are limited, e.g., the buffer size is limited on network devices, it becomes a challenge to design an effective and feasible resource sharing policy based on both the demand of real-time packet transmissions and the limitation of resource capabilities. We address this challenge in two cooperative mechanisms. First, we design a static routing algorithm to find forwarding paths for packets to guarantee their hard deadlines. The routing algorithm employs a validation-based backtracking procedure capable of deriving the demand of a set of real-time packets on each shared network device, and it checks whether this demand can be met on the device. Second, we design a packet scheduler that runs on network devices to transmit messages according to our routing requirements. We implement these mechanisms on virtual software-defined network (SDN) switches and evaluate them on real hardware in a local cluster to demonstrate the feasibility and effectiveness of our routing algorithm and packet scheduler.

Subject Classification

Keywords
  • Real-time Networks
  • Packet Scheduling
  • Deadline Guarantee

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Benny Akesson, Kees Goossens, and Markus Ringhofer. Predator: a predictable SDRAM memory controller. In Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis, pages 251-256. ACM, 2007. Google Scholar
  2. Karsten Albers and Frank Slomka. An event stream driven approximation for the analysis of real-time systems. In Real-Time Systems, 2004. ECRTS 2004. Proceedings. 16th Euromicro Conference on, pages 187-195. IEEE, 2004. Google Scholar
  3. Anne Bouillard, Bruno Gaujal, Sébastien Lagrange, and Éric Thierry. Optimal routing for end-to-end guarantees using network calculus. Performance Evaluation, 65(11):883-906, 2008. Google Scholar
  4. Gonzalo Carvajal, Luis Araneda, Alejandro Wolf, Miguel Figueroa, and Sebastian Fischmeister. Integrating dynamic-tdma communication channels into cots ethernet networks. IEEE Transactions on Industrial Informatics, 12(5):1806-1816, 2016. Google Scholar
  5. Martin Casado, Teemu Koponen, Daekyeong Moon, and Scott Shenker. Rethinking packet forwarding hardware. In HotNets, pages 1-6. Citeseer, 2008. Google Scholar
  6. Catalyst Switch Architecture. URL: http://www.cisco.com/networkers/nw03/presos/docs/RST-2011.pdf.
  7. Domenico Ferrari and Dinesh C. Verma. A scheme for real-time channel establishment in wide-area networks. Selected Areas in Communications, IEEE Journal on, 8(3):368-379, 1990. Google Scholar
  8. Leonidas Georgiadis, Roch Guérin, Vinod Peris, and Kumar N. Sivarajan. Efficient network qos provisioning based on per node traffic shaping. IEEE/ACM Transactions on Networking (TON), 4(4):482-501, 1996. Google Scholar
  9. Hoai Hoang, Magnus Jonsson, Anders Kallerdahl, and Ulrik Hagström. Switched real-time ethernet with earliest deadline first scheduling-protocols and traffic handling. Parallel and Distributed Computing Practices, 5(1):105-115, 2002. Google Scholar
  10. Torsten Hoefler, Timo Schneider, and Andrew Lumsdaine. Multistage switches are not crossbars: Effects of static routing in high-performance networks. In Cluster Computing, 2008 IEEE International Conference on, pages 116-125. IEEE, 2008. Google Scholar
  11. Bert Hubert, Thomas Graf, Greg Maxwell, Remco van Mook, Martijn van Oosterhout, P. Schroeder, Jasper Spaans, and Pedro Larroy. Linux advanced routing &traffic control. In Ottawa Linux Symposium, page 213, 2002. Google Scholar
  12. Sushant Jain, Kevin Fall, and Rabin Patra. Routing in a delay tolerant network. In SIGCOMM'04, pages 145-158. ACM, 2004. Google Scholar
  13. Kevin Jeffay, Donald F Stanat, and Charles U. Martel. On non-preemptive scheduling of period and sporadic tasks. In Real-Time Systems Symposium, 1991. Proceedings., Twelfth, pages 129-139. IEEE, 1991. Google Scholar
  14. D. D. Kandhlur, Kang G. Shin, and Domenico Ferrari. Real-time communication in multihop networks. Parallel and Distributed Systems, IEEE Transactions on, 5(10):1044-1056, 1994. Google Scholar
  15. Hermann Kopetz and Günter Grünsteidl. TTP-A time-triggered protocol for fault-tolerant real-time systems. In Fault-Tolerant Computing, 1993. FTCS-23. Digest of Papers, The Twenty-Third International Symposium on, pages 524-533. IEEE, 1993. Google Scholar
  16. Fernando Kuipers, Piet Van Mieghem, Turgay Korkmaz, and Marwan Krunz. An overview of constraint-based path selection algorithms for QoS routing. IEEE Communications Magazine, 40 (12), 2002. Google Scholar
  17. Jork Loeser and Hermann Haertig. Low-latency hard real-time communication over switched ethernet. In Real-Time Systems, 2004. ECRTS 2004. Proceedings. 16th Euromicro Conference on, pages 13-22. IEEE, 2004. Google Scholar
  18. David L. Mills. Internet time synchronization: the network time protocol. Communications, IEEE Transactions on, 39(10):1482-1493, 1991. Google Scholar
  19. Seyedbehzad Nabavi, Jianhua Zhang, and Aranya Chakrabortty. Distributed optimization algorithms for wide-area oscillation monitoring in power systems using interregional pmu-pdc architectures. Smart Grid, IEEE Transactions on, 6(5):2529-2538, 2015. Google Scholar
  20. Ben Pfaff, Justin Pettit, Keith Amidon, Martin Casado, Teemu Koponen, and Scott Shenker. Extending networking into the virtualization layer. In Hotnets, 2009. Google Scholar
  21. T. Qian, F. Mueller, and Y. Xin. A real-time distributed hash table. In Embedded and Real-Time Computing Systems and Applications (RTCSA), 2014 IEEE 20th International Conference on, pages 1-10. IEEE, 2014. Google Scholar
  22. Tao Qian, Aranya Chakrabortty, Frank Mueller, and Yufeng Xin. A real-time distributed storage system for multi-resolution virtual synchrophasor. In Power &Energy Society General Meeting. IEEE, 2014. Google Scholar
  23. Tao Qian, Frank Mueller, and Yufeng Xin. Hybrid EDF Packet Scheduling for Real-Time Distributed Systems. In Real-Time Systems (ECRTS), 2015 27th Euromicro Conference on, pages 37-46, July 2015. Google Scholar
  24. Nageswara SV Rao and Stephen G Batsell. QoS routing via multiple paths using bandwidth reservation. In INFOCOM'98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 1, pages 11-18. IEEE, 1998. Google Scholar
  25. Jakob Rosen, Alexandru Andrei, Petru Eles, and Zebo Peng. Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip. In Real-Time Systems Symposium, 2007. RTSS 2007. 28th IEEE International, pages 49-60. IEEE, 2007. Google Scholar
  26. Rui Santos, Moris Behnam, Thomas Nolte, Paulo Pedreiras, and Luís Almeida. Multi-level hierarchical scheduling in ethernet switches. In Proceedings of the ninth ACM international conference on Embedded software, pages 185-194. ACM, 2011. Google Scholar
  27. John W. Suurballe and Robert Endre Tarjan. A quick method for finding shortest pairs of disjoint paths. Networks, 14(2):325-336, 1984. Google Scholar
  28. Balajee Vamanan, Jahangir Hasan, and T. N. Vijaykumar. Deadline-aware datacenter tcp (d2tcp). ACM SIGCOMM Computer Communication Review, 42(4):115-126, 2012. Google Scholar
  29. Christo Wilson, Hitesh Ballani, Thomas Karagiannis, and Ant Rowtron. Better never than late: Meeting deadlines in datacenter networks. ACM SIGCOMM Computer Communication Review, 41(4):50-61, 2011. Google Scholar
  30. Dahai Xu, Yang Chen, Yizhi Xiong, Chunming Qiao, and Xin He. On finding disjoint paths in single and dual link cost networks. In INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, volume 1. IEEE, 2004. Google Scholar
  31. Heechul Yun, Gang Yao, Rodolfo Pellizzoni, Marco Caccamo, and Lui Sha. Memory access control in multiprocessor for real-time systems with mixed criticality. In Real-Time Systems (ECRTS), 2012 24th Euromicro Conference on, pages 299-308. IEEE, 2012. Google Scholar
  32. Heechul Yun, Gang Yao, Rodolfo Pellizzoni, Marco Caccamo, and Lui Sha. Memguard: Memory bandwidth reservation system for efficient performance isolation in multi-core platforms. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013 IEEE 19th, pages 55-64. IEEE, 2013. Google Scholar
  33. Hui Zhang and Domenico Ferrari. Rate-controlled service disciplines. J. High Speed Networks, 3(4):389-412, 1994. Google Scholar
  34. Kai Zhu, Yan Zhuang, and Yannis Viniotis. Achieving end-to-end delay bounds by edf scheduling without traffic shaping. In INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3, pages 1493-1501. IEEE, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact