Further improvements in competitive guarantees for QoS buffering

N. Bansal, L.K. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber, M. Sviridenko

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    39 Citations (Scopus)

    Abstract

    We study the behavior of algorithms for buffering packets weighted by different levels of Quality of Service (QoS) guarantees in a single queue. Buffer space is limited, and packet loss occurs when the buffer overflows. We describe a modification of the previously proposed ``preemptive greedy{''} algorithm of for buffer management and give an analysis to show that this algorithm achieves a competitive ratio of at most 1.75. This improves upon recent work showing a 1.98 competitive ratio, and a previous result that shows a simple greedy algorithm has a competitive ratio of 2.
    Original languageEnglish
    Title of host publicationAutomata, Languages and Programming (31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings)
    EditorsJ. Diaz, J. Karhumäki, A. Lepistö, D. Sannella
    Place of PublicationBerlin
    PublisherSpringer
    Pages196-207
    ISBN (Print)3-540-22849-7
    DOIs
    Publication statusPublished - 2004

    Publication series

    NameLecture Notes in Computer Science
    Volume3142
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'Further improvements in competitive guarantees for QoS buffering'. Together they form a unique fingerprint.

    Cite this