Measuring the impact of adversarial errors on packet scheduling strategies

详细信息    查看全文

• 作者：Antonio Fernández Anta ; Chryssis Georgiou ; Dariusz R. Kowalski…
• 关键词：Packet scheduling ; Adversarial errors ; Unreliable link ; Asymptotic throughput ; Competitive analysis ; Error feedback mechanisms
• 刊名：Journal of Scheduling
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：19
• 期：2
• 页码：135-152
• 全文大小：1,091 KB
• 参考文献：Aiello, W. A., Mansour, Y., Rajagopolan, S., & Rosén, A. (2000). Competitive queue policies for differentiated services. In INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE (vol. 2, pp. 431–440). IEEE.
  Ajtai, M., Aspnes, J., Dwork, C., & Waarts, O. (1994). A theory of competitive analysis for distributed algorithms. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on, (pp. 401–411). IEEE.
  Anantharamu, L., Chlebus, B. S., Kowalski, D. R., & Rokicki, M. A. (2011). Medium access control for adversarial channels with jamming. In A. Kosowski & M. Yamashita (Eds.), Structural Information and Communication Complexity (pp. 89–100). Berlin: Springer.
  Andrews, M., & Zhang, L. (2005). Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data. Journal of the ACM, 52(5), 809–834. doi:10.​1145/​1089023.​1089028 . ISSN 0004-5411.CrossRef
  Awerbuch, B., Kutten, S., & Peleg, D. (1992). Competitive distributed job scheduling. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing (pp. 571–580). ACM.
  Becchi, M. (2008). From poisson processes to self-similarity: a survey of network traffic models. Technical report, Citeseer.
  Borodin, A., & El-Yaniv, R. (1998). Online computation and competitive analysis. Cambridge: Cambridge University Press.
  Epstein, L., & van Stee, R. (2007). Online bin packing with resource augmentation. Discrete Optimization, 4(34), 322–333. doi:10.​1016/​j.​disopt.​2007.​09.​004 . (ISSN 1572-5286).CrossRef
  Goldwasser, M. H. (2010). A survey of buffer management policies for packet switches. ACM SIGACT News, 41(1), 100–128.CrossRef
  Jamieson, K., & Balakrishnan, H. (2007). PPR: Partial packet recovery for wireless networks. In Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, SIGCOMM ’07 (pp. 409–420), New York, NY, USA, ACM. ISBN 978-1-59593-713-1. doi:10.​1145/​1282380.​1282426 .
  Jurdzinski, T., Kowalski, D. R., & Lorys, K. (2014). Online packet scheduling under adversarial jamming. Approximation and online algorithms (pp. 193–206). Berlin: Springer.
  Kesselheim, T. (2012). Dynamic packet scheduling in wireless networks. In PODC, (pp. 281–290)
  Kesselman, A., Lotker, Z., Mansour, Y., Patt-Shamir,B., Schieber, B., & Sviridenko, M. (2004). Buffer overflow management in qos switches. SIAM Journal on Computing, 33(3), 563–583.
  Kogan, K., Lpez-Ortiz, A., Nikolenko, S. I., Sirotkin, A. V., & Tugaryov, D. (2012). Fifo queueing policies for packets with heterogeneous processing. In G. Even & D. Rawitz (Eds.), Design and analysis of algorithms (Vol. 7659, pp. 248–260). Lecture Notes in Computer Science Berlin Heidelberg: Springer. doi:10.​1007/​978-3-642-34862-4 . (ISBN 978-3-642-34861-7).
  Kogan, K., Lopez-Ortiz, A., Nikolenko, S. I., & Sirotkin, A. V. (2013). Multi-queued network processors for packets with heterogeneous processing requirements. In Communication Systems and Networks (COMSNETS), 2013 Fifth International Conference on, pp. 1–10. doi:10.​1109/​COMSNETS.​2013.​6465538 .
  Li, F. (2011). A near-optimal memoryless online algorithm for fifo buffering two packet classes. In W. Wang, X. Zhu & D.-Z. Du (Eds.), Combinatorial Optimization and Applications (pp. 222–233). Berlin: Springer.
  Li, F., & Zhang, Z. (2009). Scheduling weighted packets with deadlines over a fading channel. In Information Sciences and Systems, 2009. CISS 2009. 43rd Annual Conference on, (pp. 707–712). IEEE.
  Lin, S., & Costello, D. J. (2004). Error control coding (Vol. 123). Englewood Cliffs, NJ: Prentice-hall.
  Mansour, Y., Patt-Shamir, B., & Lapid, O. (2000). Optimal smoothing schedules for real-time streams. In Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing (pp. 21–29). ACM.
  Meiners, C., & Torng, E. (2007). Mixed criteria packet scheduling., Algorithmic aspects in information and management Berlin Heidelberg: Springer.CrossRef
  Mitzenmacher, M., & Upfal, E. (2005). Probability and computing. Cambridge: Cambridge University Press.CrossRef
  Pinedo, M. L. (2012). Scheduling: Theory, algorithms, and systems. Berlin: Springer.CrossRef
  Pruhs, K., Sgall, J., & Torng, E. (2004). Online scheduling. In J. Leung (Ed.), Handbook of scheduling: Algorithms, Models and Performance analysis (pp. 15-1–15-41). Boca Raton, FL: CRC Press.
  Raghavan, A., Ramchandran, K., & Kozintsev, I. (2001). Continuous error detection (CED) for reliable communication. IEEE Transactions on Communications, 49(9), 1540–1549.CrossRef
  Richa, A., Scheideler, C., Schmid, S., & Zhang, J. (2012). Competitive throughput in multi-hop wireless networks despite adaptive jamming. Distributed Computing, 26, (159–171).
  Sleator, D. D., & Tarjan, R. E. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2), 202–208.CrossRef
  Van Stee, R. (2002). On-line scheduling and bin packing, IPA dissertation series. https://​books.​google.​com.​cy/​books?​id=​1UzMGAAACAAJ .
  Yao, A. C.-C. (1977). Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS ’77, (pp. 222–227), Washington, DC, USA. IEEE Computer Society. doi:10.​1109/​SFCS.​1977.​24 .
  
• 作者单位：Antonio Fernández Anta (1)
  Chryssis Georgiou (2)
  Dariusz R. Kowalski (3)
  Joerg Widmer (1)
  Elli Zavou (4)
  
  1. IMDEA Networks Institute, Avda. del Mar Mediterraneo 22, 28918, Leganés, Madrid, Spain
  2. Department of Computer Science, University of Cyprus, 75 Kallipoleos Str., P.O. Box 20537, 1678, Nicosia, Cyprus
  3. Department of Computer Science, University of Liverpool, Ashton Building, Ashton Street, Liverpool, L69 3BX, United Kingdom
  4. Universidad Carlos III de Madrid and IMDEA Networks Institute, Avda. del Mar Mediterraneo 22, 28918, Leganés, Madrid, Spain
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Calculus of Variations and Optimal Control
  Optimization
  Artificial Intelligence and Robotics
  Production and Logistics
  
• 出版者：Springer Netherlands
• ISSN：1099-1425

文摘

In this paper, we explore the problem of achieving efficient packet transmission over unreliable links with worst-case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric to measure the efficiency of scheduling strategies in such a setting. To this end, we propose an asymptotic throughput metric which corresponds to the long-term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous with deferred error feedback, which requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The asymptotic throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the metric and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.