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
Binoy Ravindran	Committee Chair
Peter M. Athanas	Committee Member
Scott F. Midkiff	Committee Member

Keywords

packet scheduling
soft timeliness
real-time Ethernet
real-time Ethernet
best-effort scheduling
benefit functions
feasibility conditions
packet scheduling
best-effort scheduling
asynchronous real-time distributed systems

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)
Filename		Size	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