Title page for ETD etd-10032002-152839


Type of Document Master's Thesis
Author Wang, Jinggang
Author's Email Address jiwang5@vt.edu
URN etd-10032002-152839
Title Soft Real-Time Switched Ethernet: Best-Effort Packet Scheduling Algorithm, Implementation, and Feasibility Analysis
Degree Master of Science
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
Ravindran, Binoy Committee Chair
Athanas, Peter M. Committee Member
Midkiff, Scott F. Committee Member
Keywords
  • asynchronous real-time distributed systems
  • best-effort scheduling
  • soft timeliness
  • packet scheduling
  • real-time Ethernet
  • real-time Ethernet
  • best-effort scheduling
  • benefit functions
  • feasibility conditions
  • packet scheduling
Date of Defense 2002-09-24
Availability unrestricted
Abstract
In this thesis, we present a MAC-layer packet scheduling algorithm, called Best-effort Packet Scheduling Algorithm(BPA), for real-time switched Ethernet networks. BPA considers a message model where application messages have trans-node timeliness requirements that are specified using Jensen's benefit functions. The algorithm seeks to maximize aggregate message benefit by allowing message packets to inherit benefit functions of their parent messages and scheduling packets to maximize aggregate packet-level benefit. Since the packet scheduling problem is NP-hard, BPA heuristically computes schedules with a worst-case cost of O(n^2), faster than the O(n^3) cost of the best known Chen and Muhlethaler's Algorithm(CMA) for the same problem. Our simulation studies show that BPA performs the same or significantly better than CMA.

We also construct a real-time switched Ethernet by prototyping an Ethernet switch using a Personal Computer(PC) and implementing BPA in the network protocol stack of the Linux kernel for packet scheduling. Our actual performance measurements of BPA using the network implementation reveal the effectiveness of the algorithm.

Finally, we derive timeliness feasibility conditions of real-time switched Ethernet systems that use the BPA algorithm. The feasibility conditions allow real-time distributed systems to be constructed using BPA, with guaranteed soft timeliness.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  thesis-final.pdf 1.07 Mb 00:04:56 00:02:32 00:02:13 00:01:06 00:00:05

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.