Online scheduling for buffering problems

In a scheduling problem, tasks have to be assigned to resources in such a way that some specified objective is accomplished. Often times, tasks either can or have to be stored in a buffer before they are assigned to a resource. In these cases, a buffer management strategy has to constantly facilitate decisions as to which tasks to store in the buffer, which tasks to execute, and which tasks to delete from the buffer. If the tasks arrive over time, these decisions have to be made online, that is, without knowledge of the future. The predominant method to investigate online algorithms is the competitive analysis. An online algorithm is c-competitive if, for every input, the solution returned by the algorithm is at most by a factor of c worse than a solution given by an optimal offline algorithm. We study four different online scheduling problems, in which buffers are a crucial component, in a competitive analysis. First, we introduce and study reordering buffers, which are used to reorder a stream of tasks, requests, or jobs in such a way that they can be served more efficiently. This concept can be applied to various scheduling problems in order to improve performance. To demonstrate the power of reordering buffers and to show how they can be efficiently used, we apply reordering buffers to two exemplary scheduling problems. In the first problem, the reordering buffer is used to minimize the sum of the distances between consecutive elements in a sequence of points from a metric space. We design the first algorithm achieving a polylogarithmic competitive ratio for general metric spaces. In the second problem, the reordering buffer is used to obtain improved competitive ratios for the well-known online minimum makespan scheduling problem. For the identical machine model, we present matching upper and lower bounds on the competitive ratio which are significantly lower than the bounds for the classic online minimum makespan scheduling problem without reordering buffers. This is somewhat surprising considering that, for more than four machines, no tight bounds are known for the problem without reordering, despite the great effort that was spent on this problem. Buffers cannot only be an optional tool for improving performance for various scheduling problems, they can also be a problem-specific necessity. We investigate two different scheduling problems that are motivated by the problem of packet forwarding in network switches that have so-called Quality-of-Service (QoS) capabilities, i.e., switches which are able to treat different kind of packets with different priority. Since a network switch may not be able to instantly forward every arriving data packet, network switches are equipped with buffers to temporarily store not yet forwarded data packets. The different packet priorities in the QoS scenario are abstracted by assigning each packet a certain value which reflects its priority. A scheduling strategy is used to decide which packets from the buffers are to be sent at any given time. First, we study a scenario in which the buffers in the network switch have limited capacity and packets have to be sent in the order they arrive. Since the capacity of the outgoing link is also limited, buffer overflow events may occur. In case of a buffer overflow, packets have to be dropped and cannot be forwarded anymore. In order to avoid dropping very valuable packets, it can make sense to preemptively drop packets of lower value at a point in time where it would otherwise not be necessary to drop packets at all. The challenge is to design algorithms that drop the right packets at the right time to achieve the best possible performance. In the second scenario we study, the capacity of buffers is unbounded and packets can be sent in arbitrary order. However, each packet has a deadline by which it has to be either sent or dropped. In this model, there is a trade-off between sending packets which are to expire shortly and sending packets with large values. We completely solve both problems for the case that only two different packet values appear in the input sequence and improve the previous bounds for the general case. For the first problem variant, we study the so-called preemptive greedy strategy, which is currently the only algorithm achieving a competitive ratio below 2. We analyze this algorithm more carefully and show improved upper and lower bounds on the competitive ratio of preemptive greedy. For the second problem variant, we introduce the novel concept of suppressed packets and demonstrate the potential of this approach by, among other things, presenting an algorithm achieving the currently best known competitive ratio.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2008

Author dc:creator

• Englert, Matthias

Contributors dc:contributor

• Westermann, Matthias

• info:eu-repo/classification/ddc/004
• Online-Algorithmus
• Competitive analysis
• Informatik
• online algorithms
• buffer management

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112728%22

OAI record oai:identifier

https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A50173