Soft Real-Time Switched Ethernet: Best-Effort Packet Scheduling Algorithm, Implementation, and Feasibility Analysis

Simple item page
dc.contributor.authorWang, Jinggangen
dc.contributor.committeechairRavindran, Binoyen
dc.contributor.committeememberMidkiff, Scott F.en
dc.contributor.committeememberAthanas, Peter M.en
dc.contributor.departmentElectrical and Computer Engineeringen
dc.date.accessioned2014-03-14T20:46:18Zen
dc.date.adate2002-10-10en
dc.date.available2014-03-14T20:46:18Zen
dc.date.issued2002-09-24en
dc.date.rdate2003-10-10en
dc.date.sdate2002-10-03en
dc.description.abstractIn 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.en
dc.description.degreeMaster of Scienceen
dc.identifier.otheretd-10032002-152839en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-10032002-152839/en
dc.identifier.urihttp://hdl.handle.net/10919/35277en
dc.publisherVirginia Techen
dc.relation.haspartthesis-final.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectasynchronous real-time distributed systemsen
dc.subjectbest-effort schedulingen
dc.subjectsoft timelinessen
dc.subjectpacket schedulingen
dc.subjectreal-time Etherneten
dc.subjectreal-time Etherneten
dc.subjectbest-effort schedulingen
dc.subjectbenefit functionsen
dc.subjectfeasibility conditionsen
dc.subjectpacket schedulingen
dc.titleSoft Real-Time Switched Ethernet: Best-Effort Packet Scheduling Algorithm, Implementation, and Feasibility Analysisen
dc.typeThesisen
thesis.degree.disciplineElectrical and Computer Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis-final.pdf
Size:
1.02 MB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses