Emek, Yuval ; Halldorsson, Magnus M. ; Mansour, Yishay ; Patt-Shamir, Boaz ; Radhakrishnan, Jaikumar ; Rawitz, Dror (2010) Online set packing and competitive scheduling of multi-part tasks PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing . No pp. given.
![[img]](https://repository.ias.ac.in/style/images/fileicons/application_pdf.png)
|
PDF
- Author Version
219kB |
Official URL: http://dl.acm.org/citation.cfm?id=1835698.1835800
Related URL: http://dx.doi.org/10.1145/1835698.1835800
Abstract
We consider a scenario where large data frames are broken into a few packets and transmitted over the network. Our focus is on a bottleneck router: the model assumes that in each time step, a set of packets (a burst) arrives, from which only one packet can be served, and all other packets are lost. A data frame is considered useful only if none of its constituent packets is lost, and otherwise it is worthless. We abstract the problem as a new type of online set packing, present a randomized distributed algorithm and a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximal burst size and the maximal number of packets per frame. We also present refined bounds that depend on the uniformity of these parameters.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Association for Computing Machinery. |
| Keywords: | Online Set Packing; Competitive Analysis; Packet Fragmentation; Multi-packet Frames |
| ID Code: | 89495 |
| Deposited On: | 27 Apr 2012 13:41 |
| Last Modified: | 19 May 2016 04:02 |
Repository Staff Only: item control page
