• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • College of Computing Technical Reports
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • College of Computing Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    On Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithms

    Thumbnail
    View/Open
    GIT-CC-02-21.pdf (300.1Kb)
    Date
    2002
    Author
    Xu, Jun
    Lipton, Richard J.
    Metadata
    Show full item record
    Abstract
    In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling that guarantees O (1) GPS-relative delay bounds is Ω (log₂n) (Widely believed as a "folklore theorem" but never proved). We also discover that surprisingly the complexity lower bound remains the same even if the delay bound is relaxed to (nª) for 0 <a <1. This implies that the delay complexity tradeoff curve is "flat" in the "interval" (O (1), O (n)). We later extend both complexity results (for O (1) or O (na) delay) to a much stronger computational model. Finally, we show that the same complexity lower bounds are applicable to guaranteeing tight end-to-end delay bounds. This is done by untangling the subtle relationship between the GPS-relative delay bound and the end-to-end delay bound.
    URI
    http://hdl.handle.net/1853/6534
    Collections
    • College of Computing Technical Reports [506]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology