Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Considering suppressed packets improves buffer management in quality of service switches

Tools
- Tools
+ Tools

Englert, Matthias and Westermann, Matthias (2012) Considering suppressed packets improves buffer management in quality of service switches. SIAM Journal on Computing, Volume 41 (Number 5). pp. 1166-1192. doi:10.1137/110856745

Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1137/110856745

Request Changes to record.

Abstract

The following buffer management problem arises in network switches providing different levels of services: At the beginning of each time step, one packet can be sent, and afterward an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet has a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. Additionally, each packet has a value which reflects its importance. A buffer management strategy determines the packet to be sent in each time step. The goal of a buffer management strategy is to maximize the sum of the values of sent packets. We introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. We show that this strategy achieves a competitive ratio of $2 \sqrt{2} - 1 \approx 1.828$, which is the best known competitive ratio in the deterministic case. In addition, we present a memoryless version of this strategy that achieves a competitive ratio of $\approx 1.893$. This is the first memoryless strategy that achieves a competitive ratio less than 2. Altogether, this demonstrates the potential of the concept of suppressed packets.

Item Type: Journal Article
Divisions: Faculty of Science > Computer Science
Journal or Publication Title: SIAM Journal on Computing
Publisher: SIAM
ISSN: 0097-5397
Official Date: 11 September 2012
Dates:
DateEvent
11 September 2012Available
24 July 2012Accepted
28 November 2011Submitted
Volume: Volume 41
Number: Number 5
Number of Pages: 27
Page Range: pp. 1166-1192
DOI: 10.1137/110856745
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Adapted As:

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us