Online packet scheduling under adversarial errors.

*(English)*Zbl 1431.68163Summary: We consider the problem of scheduling packets of different sizes via a directed communication link prone to errors, where dynamic packet arrivals and errors are modeled by an adversary. Packets arrive over time to be transmitted over a channel in which instantaneous errors occur at times not known to the algorithm in advance. We focus on estimating the competitive throughput of online scheduling algorithms defined as the ratio between the total size of packets successfully transmitted by an online algorithm and the largest total size of packets which can be transmitted for the same arrival and error patterns. First, we design two online algorithms with optimal competitive throughput in various scenarios. One algorithm works for any \(f \geq 1\) channels and attains the competitive throughput 1/2 provided that sizes of packets satisfy the divisibility property (i.e., any larger size is divisible by any smaller). The other algorithm achieves the optimal competitive throughput in \((1 / 3, 1 / 2]\) for arbitrary sizes of packets on one communication channel, where the exact value of the competitive throughput depends on the sizes of packets. Second, we focus on algorithms working with speedup \(s \geq 1\). In this setting, online algorithms transmit packets \(s\) times faster than the offline optimum solution they are compared against. We design an algorithm which attains the competitive throughput 1 if it works with speedup 2 in the case that sizes of packets satisfy the divisibility property and with speedup \(s \in [4, 6)\) for arbitrary sizes of packets. This demonstrates that throughput of the best online fault-tolerant scheduling algorithms scales well with resource augmentation.

##### MSC:

68W27 | Online algorithms; streaming algorithms |

90B35 | Deterministic scheduling theory in operations research |

##### Keywords:

packet scheduling; dynamic packet arrivals; adversarial errors; online algorithms; competitive throughput; resource augmentation
PDF
BibTeX
XML
Cite

\textit{P. Garncarek} et al., Theor. Comput. Sci. 795, 492--509 (2019; Zbl 1431.68163)

Full Text:
DOI

##### References:

[1] | Ajtai, M.; Aspnes, J.; Dwork, C.; Waarts, O., A theory of competitive analysis for distributed algorithms, (Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), (1994), IEEE), 401-411 |

[2] | Anantharamu, L.; Chlebus, B. S.; Kowalski, D. R.; Rokicki, M. A., Deterministic broadcast on multiple access channels, (Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM), (2010), IEEE), 146-150 |

[3] | Andrews, M.; Zhang, L., Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data, J. ACM, 52, 5, 809-834, (Sept. 2005) |

[4] | Awerbuch, B.; Kutten, S.; Peleg, D., Competitive distributed job scheduling, (Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (STOC), (1992), ACM), 571-580 |

[5] | Böhm, M.; Jez, L.; Sgall, J.; Veselý, P., On packet scheduling with adversarial jamming and speedup, (2017), CoRR |

[6] | Fernández Anta, A.; Georgiou, C.; Kowalski, D. R.; Widmer, J.; Zavou, E., Measuring the impact of adversarial errors on packet scheduling strategies, J. Sched., 19, 2, 135-152, (2016) · Zbl 1341.90045 |

[7] | Fernández Anta, A.; Georgiou, C.; Kowalski, D. R.; Zavou, E., Online parallel scheduling of non-uniform tasks: trading failures for energy, Theor. Comput. Sci., 590, 129-146, (2015) · Zbl 1327.68337 |

[8] | Fernández Anta, A.; Georgiou, C.; Kowalski, D. R.; Zavou, E., Competitive analysis of fundamental scheduling algorithms on a fault-prone machine and the impact of resource augmentation, Future Gener. Comput. Syst., 78, 245-256, (2018) |

[9] | Garncarek, P.; Jurdzinski, T.; Lorys, K., Fault-tolerant online packet scheduling on parallel channels, (2017 IEEE International Parallel and Distributed Processing Symposium. 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017, Orlando, FL, USA, May 29 - June 2, 2017, (2017)), 347-356 |

[10] | Jurdzinski, T.; Kowalski, D. R.; Lorys, K., Online packet scheduling under adversarial jamming, (Approximation and Online Algorithms - 12th International Workshop. Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12. Approximation and Online Algorithms - 12th International Workshop. Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, Revised Selected Papers, vol. 2014, (2014)), 193-206 · Zbl 06512666 |

[11] | Meiners, C.; Torng, E., Mixed criteria packet scheduling, (Algorithmic Aspects in Information and Management, (2007)), 120-133 · Zbl 1137.90507 |

[12] | Pinedo, M. L., Scheduling: Theory, Algorithms, and Systems, (2012), Springer · Zbl 1239.90002 |

[13] | Pruhs, K.; Sgall, J.; Torng, E., Online Scheduling, 115-124, (2003), CRC Press |

[14] | Richa, A.; Scheideler, C.; Schmid, S.; Zhang, J., Competitive throughput in multi-hop wireless networks despite adaptive jamming, Distrib. Comput., 1-13, (2012) |

[15] | Sleator, D. D.; Tarjan, R. E., Amortized efficiency of list update and paging rules, Commun. ACM, 28, 2, 202-208, (1985) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.