Performance of Scheduling Policies in Adversarial Networks with Non-synchronized Clocks

Fernández Anta, Antonio; López Presa, Jose Luis; Lorenzo Prieto, Maria Araceli; Manzano García, Pilar; Martinez Romo, Juan; Mozo Velasco, Alberto y Thraves, Christopher (2011). Performance of Scheduling Policies in Adversarial Networks with Non-synchronized Clocks. "Theory of Computing Systems", v. 48 (n. 1); pp. 1-22. ISSN 1432-4350. https://doi.org/10.1007/s00224-009-9223-5.

Descripción

Título: Performance of Scheduling Policies in Adversarial Networks with Non-synchronized Clocks
Autor/es:
  • Fernández Anta, Antonio
  • López Presa, Jose Luis
  • Lorenzo Prieto, Maria Araceli
  • Manzano García, Pilar
  • Martinez Romo, Juan
  • Mozo Velasco, Alberto
  • Thraves, Christopher
Tipo de Documento: Artículo
Título de Revista/Publicación: Theory of Computing Systems
Fecha: Junio 2011
Volumen: 48
Materias:
Palabras Clave Informales: Scheduling, Continuous adversarial queuing theory, Adversarial models, Clock skew, Clock drift, Clock synchronization
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Arquitectura y Tecnología de Computadores [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

In this paper we generalize the Continuous Adversarial Queuing Theory (CAQT) model (Blesa et al. in MFCS, Lecture Notes in Computer Science, vol. 3618, pp. 144–155, 2005) by considering the possibility that the router clocks in the network are not synchronized. We name the new model Non Synchronized CAQT (NSCAQT). Clearly, this new extension to the model only affects those scheduling policies that use some form of timing. In a first approach we consider the case in which although not synchronized, all clocks run at the same speed, maintaining constant differences. In this case we show that all universally stable policies in CAQT that use the injection time and the remaining path to schedule packets remain universally stable. These policies include, for instance, Shortest in System (SIS) and Longest in System (LIS). Then, we study the case in which clock differences can vary over time, but the maximum difference is bounded. In this model we show the universal stability of two families of policies related to SIS and LIS respectively (the priority of a packet in these policies depends on the arrival time and a function of the path traversed). The bounds we obtain in this case depend on the maximum difference between clocks. This is a necessary requirement, since we also show that LIS is not universally stable in systems without bounded clock difference. We then present a new policy that we call Longest in Queues (LIQ), which gives priority to the packet that has been waiting the longest in edge queues. This policy is universally stable and, if clocks maintain constant differences, the bounds we prove do not depend on them. To finish, we provide with simulation results that compare the behavior of some of these policies in a network with stochastic injection of packets.

Más información

ID de Registro: 11650
Identificador DC: http://oa.upm.es/11650/
Identificador OAI: oai:oa.upm.es:11650
Identificador DOI: 10.1007/s00224-009-9223-5
URL Oficial: http://link.springer.com/article/10.1007%2Fs00224-009-9223-5
Depositado por: Memoria Investigacion
Depositado el: 29 Nov 2012 10:38
Ultima Modificación: 20 Abr 2016 19:40
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • InvestigaM
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM