Calculating Bounds for Delay in Communication Networks Under Real Time Constraints
Resumo
Estudamos redes de comunicação submetidas a condição estrita de tempo real. Esta condição implica que cada cliente deve deixar sua estação de entrada antes de uma certa data limite (dead-line). O estudo de limites para a carga permite deduzir limites para o atraso dos clientes e discutir a “factibilidade” do sistema de tempo real. Primeiro nós analisamos as propriedades básicas de uma estação isolada com uma prioridade de dois níveis. Pois analisamos uma rede feed-forward de estações sem loops. Enfim, o caso de uma rede em anel está apresentado. Para cada uma dessas topologias, calculamos limites sobre a carga das estações. O cálculo está baseado em equações de evolução. Discutimos tambem de periodicidade e de condições de factibilidade quando o processo de chegada é uma superposição de processos periódicos.
Referências
C.S. Chang, Stability, Queue Length and Delay, Part 2: Stochastic queuing networks, IBM Research Report 17709, IBM Research Division, 1992. In Proc. IEEE Conf. on Decision and Control, vol. 1,1992.
C. Chaouiya, Outils pour la validation de contraintes de synchronisation dans des systèmes distribués, PhD Thesis, University of Nice-Sophia Antipolis, October 1992.
C. Chaouiya, $. Lefebvre-Barbaroux and A. Jean-Marie, Real-Time Scheduling of Periodic Tasks, To appear in Scheduling Theory and its Applications, P. Chretienne, E. G. Coffman, J. K. Lenstra, Z. Liu, (Eds.) J. Wiley, 1993.
R.L. Cruz, A Calculus for Network Delay, Part I: Network Elements in Isolation, IEEE Trans. Information Theory, 37, No 1, pp. 114-131, January 1991.
R.L. Cruz, A Calculus for Network Delay, Part II: Network Analysis IEEE Trans. Information Theory, 37, No 1, pp. 132-141, January 1991.
J. Kurose, On computing per-session performance bounds in high-speed multihop computer networks, In Performance Evaluation Review, vol.20, Newport, 1992. ACM SIGMETRICS and Performance'92.
S. Lefebvre-Barbaroux, Files d'attente avec arrivées atypiques: environnement aléatoire et superposition de flux périodiques, PhD Thesis, University of ParisXI, Orsay, February 1992.
S. Lefebvre-Barbaroux, A. Jean-Marie and C. Chaouiya, Problèmes d'ordonnancement d'une superposition de flux périodiques sous contrainte temps-réel, INRIA Research Report 1576, March 1992.
C.L. Liu and J.W. Layland, Scheduling Algorithms for Multiprogramming in Hard-Real-Time Environment, Journal of the Association for Computing Machinery, 20, No 1, January 1973, pp. 46-61.
O. Serlin, Scheduling of Time Critical Processes, AFIPS Conference Proceedings SJCC,40, Atlantic City, 1972.
