Abstract | ||
---|---|---|
Online scheduling of unit-length packets with hard deadlines by a single server in slotted time is considered. First, the throughput optimal scheduling policies are characterized. Then multiclass packets are considered in which each packet has an M-bit class identifier, and a new optimality property called lex-optimality (short for lexicographic optimality) is defined for online scheduling policies. Lex-optimality is a hierarchical sequence of M throughput optimality properties. The lex-optimal policies that do not drop packets early are characterized. Both characterizations involve identification of a "no-regret subset" of the set of packets available for scheduling in a given slot. A lex-optimal scheduling algorithm is presented with complexity per packet O(MB), where M is the log of the number of priority classes and B is the maximum buffer size. The algorithm requires no more packets to be buffered than any online, throughput optimal scheduling policy. Simulation results are presented that illustrate that lex-optimality combines elements of pure priority and nested priority scheduling. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1287/moor.1040.0144 | Mathematics of Operations Research |
Keywords | DocType | Volume |
throughput optimal scheduling policy,Online scheduling,lex-optimal scheduling algorithm,nested priority scheduling,online scheduling policy,M throughput optimality property,lexicographic optimality,new optimality property,priority class,pure priority,Hard Deadlines,Lex-Optimal Online | Journal | 30 |
Issue | ISSN | Citations |
3 | 0364-765X | 2 |
PageRank | References | Authors |
0.37 | 6 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bruce Hajek | 1 | 154 | 17.84 |
Pierre Seri | 2 | 2 | 0.37 |