Accession Number:

ADA374575

Title:

Packet Fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2000-02-01

Pagination or Media Count:

41.0

Abstract:

While Packet Fair Queueing PFQ algorithms provide both bounded delay and fairness in wired networks they cannot be applied directly to wireless networks. The key difficulty is that in wireless networks sessions can experience location-dependent channel errors. This may lead to situations in which a session receives significantly less service than it is supposed to, while another receives more. This results in large discrepancies between the sessions virtual times, making it difficult to provide both delay-guarantees and fairness simultaneously. Our contribution is twofold. First, we identify a set of properties, called Channel-condition Independent Fair CIF, that a Packet Fair Queueing algorithm should have in a wireless environment 1 delay and throughput guarantees for error-free sessions, 2 long term fairness for error sessions, 3 short term fairness for error-free sessions, and 4 graceful degradation for sessions that have received excess service. Second, we present a methodology for adapting PFQ algorithms for wireless networks and we apply this methodology to derive a novel algorithm based on Start-time Fair Queueing called Channel-condition Independent packet Fair Queueing CIF-Q, that achieves all the above properties. To evaluate the algorithm we provide both theoretical analysis and simulation results.

Subject Categories:

  • Computer Systems
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE