Capítulo 14 Redes de filas de espera



Descargar 155.15 Kb.
Página6/6
Fecha de conversión10.01.2017
Tamaño155.15 Kb.
1   2   3   4   5   6

14.8 Otros algoritmos para redes de puesta en fila


El algoritmo MVA es también aplicable a redes de puesta en fila con más cadenas, pero no se describirá en el presente Manual. Durante el último decenio se han publicado diversos algoritmos. Un panorama general se puede encontrar en (Conway y Georganas, 1989 [16]). En general, los algoritmos exactos no son aplicables para redes amplias. Por tanto, se han elaborado muchos algoritmos aproximados para ser aplicados en redes de puesta en fila de dimensiones realistas.

14.9 Complejidad


Las redes de puesta en fila tienen la misma complejidad que las redes de circuito conmutados con encaminamiento directo (véase el § 11.5 y el cuadro 11.1). El espacio de estado de la red que figura en el cuadro 14.3 tiene el siguiente número de estados para cada nodo:

El caso más desfavorable se produce cuando cada cadena está constituido por un cliente. El número de estado entonces resulta 2S, donde S es el número de cliente.



Cuadro 14.3 – Parámetros de una red de puesta en fila con N cadenas,
K
nodos y i Si clientes. El parámetro jk indica la carga de
la cadena j en el nodo k (véase el cuadro 11.1)


Cadena

Nodo


Dimensión de la población









14.10 Atribución de la capacidad óptima


Se considera ahora un sistema de transmisión de datos con K nodos, que son sistemas independientes de puesta en fila de un solo servidor M/M/1 (sistema de demora de Erlang con un servidor). El proceso de llegada al nodo k es un proceso de Poisson con mensajes de intensidad k (clientes) por unidad de tiempo, y el tamaño del mensaje está distribuido exponencialmente con el valor medio 1/k [bits]. La capacidad del nodo k es k [bits por unidad de tiempo].

Se introduce en la capacidad total la restricción lineal siguiente:



Para cada atribución de capacidad que satisface la ecuación (14.21), se tiene el tiempo medio de permanencia (promedio de llamada) siguiente (véase el § 12.4.1, combinación en paralelo):



donde:


Definiendo:



se obtiene la ley de Kleinrock para atribución de capacidad óptima (Kleinrock, 1964 [65]).



Teorema 14.2 ley de las raíces cuadradas de Kleinrock: La atribución de capacidad óptima que reduce T al mínimo (y así el número total de mensajes en todos los nodos) es:

con la condición que:



Con esta atribución óptima resulta:



En esta expresión se indica que a todos los nodos se atribuye primero la capacidad mínima necesaria i/i. La capacidad restante:



se atribuye entre los nodos en forma proporcional a la raíz cuadrada del flujo medio k/k.

Esto se puede determinar introduciendo el multiplicador de Lagrange y considerar:

El valor mínimo de G se obtiene calculando k conforme a la ecuación (14.26). Si todos los mensajes tienen el mismo valor medio k=, (se puede considerar entonces diferentes costos en los nodos conforme a la restricción que se disponga de un monto fijo (Kleinrock, 1964 [65]).


BIBLIOGRAFÍA

[1] Abate, J. & Whitt, W. (1997): Limits and approximations for the M/G/1 LIFO waitingtime distribution. Operations Research Letters, Vol. 20 (1997): 5, 199206.

[2] Andersen, B. & Hansen, N.H. & og Iversen, V.B. (1971): Use of minicomputer for telephone traffic measurements. Teleteknik (Edición inglesa) Vol. 15 (1971): 2, 3346.

[3] Ash, G.R. (1998): Dynamic routing in telecommunications networks. McGraw-Hill 1998. 746 pp.

[4] Baskett, F. & Chandy, K.M. & Muntz, R.R. & Palacios, F.G. (1975): Open, Closed and Mixed Networks of Queues with Different Classes of Customers. Journ. of the ACM, abril 1975, pp. 248260. (BCMP queueing networks).

[5] Bear, D. (1988): Principles of telecommunication traffic engineering. Revised 3rd Edition. Peter Peregrinus Ltd, Stevenage 1988. 250 pp.

[6] Bech, N.I. (1954): Metode til Beregning af Spærring i Alternativ Trunking- og Grade-ringssystemer. Teleteknik, Vol. 5 (1954) : 4, pp. 435448.

[7] Bolotin, V.A. (1994): Telephone circuit holding time distributions. ITC 14, 14th International Teletraffic Congress. Antibes Juan-les-Pins, France, junio 6-10. 1994. Proceedings pp. 125134. Elsevier 1994.

[8] Boots, N.K. & Tijms, H. (1999): A multiserver queueing system with impatient customers. Management Science, Vol. 45 (1999) : 3, 444448.

[9] Bretschneider, G. (1956): Bie Berechnung von Leitungsgruppen für überfließenden Verkehr. Nachrichtentechnische Zeitschrift, NTZ, Vol. 9 (1956) : 11, 533540.

[10] Bretschneider, G. (1973): Extension of the equivalent random method to smooth traffics. ITC7, Seventh International Teletraffic Congress, Estocolmo, junio 1973. Paper 411. 9 pp.

[11] Brockmeyer, E. (1954): The simple overffow problem in the theory of telephone traffic. Teleteknik 1954, pp. 361-374. En Danés. Traducido al inglés por la Copenhagen Telephone Company, abril 1955. 15 pp.

[12] Brockmeyer, E. & Halstrøm, H.L. & Jensen, Arne (1948): The life and works of A.K. Erlang. Transactions of the Danish Academy of Technical Sciences, 1948, No. 2, 277 pp. Copenhague 1948.

[13] Burke, P.J. (1956): The Output of a Queueing System. Operations Research, Vol. 4 (1956), 699704.

[14] Christensen, P.V. (1914): The number of selectors in automatic telephone systems. The Post Office Electrical Engineers Journal, Vol. 7 (1914) 271-281.

[15] Cobham, A. (1954): Priority assignment in waiting line problems. Operations Research, Vol. 2 (1954), 7076.

[16] Conway, A.E. & Georganas, N.D. (1989): Queueing Networks - Exact Computational Algorithms: A Unified Theory Based on Decomposition and Aggregation. The MIT Press 1989. 234 pp.

[17] Cooper, R.B. (1972): Introduction to Queueing Theory. Nueva York 1972. 277 pp.

[18] Cox, D.R. (1955): A Use of Complex Probabilities in the Theory of Stochastic Processes. Proc. Camb. Phil. Soc., Vol. 51 (1955), pp. 313319.

[19] Cox, D.R. & Miller, H.D. (1965): The Theory of Stochastic Processes. Methuen & Co. Londres 1965. 398 pp.

[20] Cox, D.R.& Isham, V. (1980): Point Processes. Chapman and Hall. 1980. 188 pp.

[21] Crommelin, C.D. (1932): Delay Probability Formulae When the Holding Times are Constant. Post Office Electrical Engineers Journal, Vol. 25 (1932), pp. 4150.

[22] Crommelin, C.D. (1934): Delay Probability Formulae. Post Office Electrical Engineers Journal, Vol. 26 (1934), pp. 266274.

[23] Delbrouck, L.E.N. (1983): On the steadystate distribution in a service facility carrying mixtures of traffic with different peakedness factor and capacity requirements. IEEE Transactions on Communications, Vol. COM-31 (1983): 11, 12091211.

[24] Dickmeiss, A. & Larsen, M. (1993): Spærringsberegninger i telenet. Master's thesis. Institut for Telekommunikation, Danmarks Tekniske Højskole, 1993. 141 pp.

[25] Eilon, S. (1969): A simpler proof of L = λW. Operations Research, Vol. 17 (1969), pp. 915917.

[26] Elldin, A., and G. Lind (1964): Elementary Telephone Traffic Theory. Chapter 4. L.M. Ericsson AB, Estocolmo 1964. 46 pp.

[27] Engset, T.O. (1918): Die Wahrscheinlichkeitsrechnung zur Bestimmung der Wählerzahl in automatischen Fernsprechämtern. Elektrotechnische Zeitschrift, 1918, Heft 31. Traducido al inglés por Telektronikk (Noruega), junio 1991, 4pp.

[28] Eslamdoust, C. (1995): Design of large communication networks. Master's thesis. Department of Telecommunication, Technical University of Denmark, 1995. 108 + 133 pp.

[29] Feller, W. (1950): An introduction to probability theory and its applications. Vol. 1, Nueva York 1950. 461 pp.

[30] Fortet, R. & Grandjean, Ch. (1964): Congestion in a loss system when some calls want several devices simultaneously. Electrical Communications, Vol. 39 (1964) : 4, 513526. Documento presentado al ITC4, Cuarto Congreso Internacional de Teletráfico, Londres, Inglaterra 1521 julio 1964.

[31] Fredericks, A.A. (1980): Congestion in blocking systems  a simple approximation technique. The Bell System Technical Journal, Vol. 59 (1980): 6, 805827.

[32] Fry, T.C. (1928): Probability and its engineering uses. Nueva York 1928, 470 pp.

[33] Gordon, W.J, and & Newell, G.F. (1967): Closed queueing systems with exponential servers. Operations Research, Vol. 15 (1967), pp. 254265.

[34] Grillo, D. & Skoog, R.A. & Chia, S. & Leung, K.K. (1998): Teletraffic engineering for mobile personal communications in ITUT work: the need to match theory to practice. IEEE Personal Communications, Vol. 5 (1998): 6, 3858.

[35] Hayward, W.S. Jr. (1952): The reliability of telephone traffic load measurements by switch counts. The Bell System Technical Journal, Vol. 31 (1952): 2, 357377.

[36] ITU-T (UIT-T) (1993): Unidad de intensidad de tráfico. Recomendación UIT-T B.18. 1993. 1 p.

[37] Iversen, V.B. (1973): Analysis of real teletraffic processes based on computerized measurements. Ericsson Technics, No. 1, 1973, pp. 164. "Holbæk measurements".

[38] Iversen, V.B. (1976): On the accuracy in measurements of time intervals and traffic intensities with application to teletraffic and simulation. Ph.D.thesis. IMSOR, Technical University of Denmark 1976. 202 pp.

[39] Iversen, V.B. (1976): On General Point Processes in Teletraffic Theory with Applications to Measurements and Simulation. ITC-8, Eighth International Teletraffic Congress, paper 312/18. Melbourne 1976. Publicado en Teleteknik (Edición inglesa) 1977 : 2, pp. 5970.

[40] Iversen, V.B. (1980): The A-formula. Teleteknik (Edición inglesa), Vol. 23 (1980) : 2, 6479.

[41] Iversen, V.B. (1982): Exact Calculation of Waiting Time Distributions in Queueing Systems with Constant Holding Times. Fjerde Nordiske Teletrafik Seminar (NTS-4), Fourth Nordic Teletraffic Seminar, Helsinki 1982. 31 pp.

[42] Iversen, V.B. (1987): The exact evaluation of multiservice loss system with access control. Teleteknik, Edición inglesa, Vol 31 (1987) : 2, 56-61. NTS7, Seventh Nordic Teletraffic Seminar, Lund, Suecia, 2527 de agosto, 1987, 22 pp.

[43] Iversen, V.B. & Nielsen, B.F. (1985): Some properties of Coxian distributions with applications, pp. 6166 in Proceedings of the International Conference on Modelling Techniques and Tools for Performance Analysis. 5-7 de junio, 1985, Valbonne, Francia. NorthHolland Publ. Co. 1985. 365 pp. (Editor N. Abu El Ata).

[44] Iversen, V.B. & Stepanov, S.N. (1997): The usage of convolution algorithm with truncation for estimation of individual blocking probabilities in circuit-switched telecommunication networks. Proceedings of the 15th International Teletraffic Congress, ITC 15, Washington, DC, USA, 22-27 de junio 1997. 13271336.

[45] Iversen, V.B. & Sanders, B. (2001): Engset formulæ with continuous parameters  theory and applications. AEÜ, International Journal of Electronics and Communications, Vol. 55 (2001): 1, 3-9.

[46] Jackson, J.R. (1957): Networks of waiting lines. Operations Research, Vol. 5 (1957), pp. 518521.

[47] Jackson, J.R. (1963): Jobshop-like queueing systems. Management Science, Vol. 10 (1963), No. 1, pp. 131142.

[48] Jensen, Arne (1948): An Elucidation of A.K. Erlang's Statistical Works through the Theory of Stochastic Processes. Published in "The Erlangbook": E. Brockmeyer, H.L. Halstrøm and A. Jensen: The Life and Works of A.K. Erlang. København 1948, pp. 23100.

[49] Jensen, Arne (1948): Truncated multidimensional distributions. Pages 5870 in "The Life and Works of A.K. Erlang". Ref. Brockmeyer et al., 1948.

[50] Jensen, Arne (1950): Moe's Principle  An econometric investigation intended as an aid in dimensioning and managing telephone plant. Theory and Tables. Copenhague 1950. 165 pp.

[51] Jerkins, J.L. & Neidhardt, A.L. & Wang, J.L. & Erramilli A. (1999): Operations measurement for engineering support of high-speed networks with self-similar traffic. ITC 16, 16th International Teletraffic Congress, Edinburgo, 7-11 de junio, 1999. Proceedings pp. 895906. Elsevier 1999.

[52] Johannsen, Fr. (1908): "Busy". Copenhague 1908. 4 pp.

[53] Johansen, K. & Johansen, J. & Rasmussen, C. (1991): The broadband multiplexer, "transMux 1001". Teleteknik, Edición inglesa, Vol. 34 (1991) : 1, 5765.

[54] Joys, L.A.: Variations of the Erlang, Engset and Jacobæus Formulæ, Proceedings of the Fifth International Teletraffic Congress (ITC-5), Nueva York, USA, 1967, 107111. También publicado en: Teleteknik, (Edición inglesa), 11 (1967), No. 1, 4248.

[55] Joys, L.A. (1968): Engsets Formler for Sannsynlighetstetthet og dens Rekursionsformler. (Fórmulas de Engset para probabilidad y sus fórmulas recursivas, en noruego). Telektronikk 1968 No 12, pp. 5463.

[56] Joys, L.A. (1971): Comments on the Engset and Erlang formulae for telephone traffic losses. Thesis. Report TF No. 25,/71, Research Establishment, The Norwegian Telecommunications Administration. 1971. 127 pp.

[57] Karlsson, S.A. (1937): Tekniska anordninger fö samtalsdebitering enligt tid. Helsingfors Telefonförening, Tekniska Meddelanden 1937, No. 2, pp. 3248.

[58] Kaufman, J.S. (1981): Blocking in a shared resource environment. IEEE Transactions on Communications, Vol. COM 29 (1981) : 10, 14741481.

[59] Keilson, J. (1966): The ergodic queue length distribution for queueing systems with finite capacity. Journal of Royal Statistical Society, Series B, Vol. 28 (1966), 190201.

[60] Kelly, F.P. (1979): Reversibility and Stochastic Networks. John Wiley & Sons, 1979. 230 pp.

[61] Kendall, D.G. (1951): Some problems in the theory of queues. Journal of Royal Statistical Society, Series B, Vol. 13 (1951) : 2, 151173.

[62] Kendall, D.G. (1953): Stochastic processes occuring in the theory of queues and their analysis by the method of the imbedded Markov chain. Ann. Math. Stat., Vol. 24 (1953), 338354.

[63] Khintchine, A.Y. (1955): Mathematical Methods in the Theory of Queueing. Londres 1960. 124 pp. (Original en Ruso, 1955).

[64] Kingman, J.F.C. (1969): Markov population processes. J. Appl. Prob., Vol. 6 (1969), 118.

[65] Kleinrock, L. (1964): Communication Nets: Stochastic Message Flow and Delay. McGrawHill 1964. Reimpreso por Dover Publications 1972. 209 pp.

[66] Kleinrock, L. (1975): Queueing Systems. Vol. I: Theory. Nueva York 1975. 417 pp.

[67] Kleinrock, L. (1976): Queueing Systems. Vol. II: Computer Applications. Nueva York 1976. 549 pp.

[68] Kosten, L. (1937): Über Sperrungswahrscheinlichkeiten bei Staffelschaltungen. Elek. Nachr. Techn., Vol. 14 (1937) 512.

[69] Kraimeche, B. & Schwartz, M. (1983): Circuit Access Control Strategies in integrated digital networks. IEEE INFOCOM, 9-12 de abril, 1984, San Francisco, USA, Proceedings pp. 230235.

[70] Kruithof, J. (1937): Telefoonverkehrsrekening. De Ingenieur, Vol. 52 (1937) : E15E25.

[71] Kuczura, A. (1973): The interrupted Poisson process as anflover ow process. The Bell System Technical Journal, Vol. 52 (1973) : 3, pp. 437448.

[72] Kuczura, A. (1977): A method of moments for the analysis of a switched communication network's performance. IEEE Transactions on Communications, Vol. Com25 (1977): 2, 185193.

[73] Lavenberg, S.S. & Reiser, M. (1980): Meanvalue analysis of closed multichain queueing networks. Journal of the Association for Computing Machinery, Vol. 27 (1980): 2, 313322.

[74] Lind, G. (1976): Studies on the probability of a called subscriber being busy. ITC8, Melbourne, noviembre de 1976. Paper 631. 8 pp.

[75] ListovSaabye, H. & Iversen V.B. (1989): ATMOS, a PCbased tool for evaluating multiservice telephone systems. IMSOR, Technical University of Denmark 1989, 75 pp. (en danés).

[76] Little, J.D.C. (1961): A proof for the queueing formula L = λW. Operations Research, Vol. 9 (1961) : 383387.

[77] Maral, G. (1995): VSAT Networks. John Wiley & Sons, 1995. 282 pp.

[78] Marchal, W.G. (1976): An approximate formula for waiting time in single server queues. AIIE Transactions, diciembre de 1976, 473474.

[79] Nguyen, Than-Bang: Trafikplanlægningssystemet TES under Windows. Master's thesis. Department of Telecommunication, Technical University of Denmark 1995. 74 + 93 pp.

[80] Palm, C. (1941): Mättnoggrannhet vid bestämning af trafikmängd enligt genomsök-ningsförfarandet (Exactitud de las mediciones en la determinación de volúmenes de tráfico por el método de barrido). Tekn. Medd. K. Telegr. Styr., 1941, No. 79, pp. 97115.

[81] Palm, C. (1943): Intensitätsschwankungen im Fernsprechverkehr. Ericsson Technics, No. 44, 1943, 189 pp. Traducción al inglés por Chr. Jacobæus: Intensity Variations in Telephone Traffic. NorthHolland Publ. Co. 1987.

[82] Palm, C. (1947): The assignment of workers in servicing automatic machines. Journal of Industrial Engineering, Vol. 9 (1958) : 2842. Primera publicación en Suecia en 1947.

[83] Palm, C. (1947): Table of the Erlang Loss Formula. Telefonaktiebolaget L M Ericsson, Estocolmo 1947. 23 pp.

[84] Palm, C. (1957): Some propositions regarding flat and steep distribution functions, pp. 317 in TELE (Edición inglesa), No. 1, 1957.

[85] Pinsky, E. & Conway, A.E. (1992): Computational algorithms for blocking probabilities in circuitswitched networks. Annals of Operations Research, Vol. 35 (1992) 3141.

[86] PostigoBoix, M. & GarcíaHaro, J. & Aguilar-Igartua, M. (2001): IMA: technical foundations, application and performance analysis. Computer Networks, Vol. 35 (2001) 165183.

[87] Press, W.H. & Teukolsky, S.A. & Vetterling, W.T. & Flannery, B.P. (1995): Numerical recipes in C, the art of scientific computing. 2nd edition. Cambridge University Press, 1995. 994 pp.

[88] Rabe, F.W. (1949): Variations of telephone traffic. Electrical Communications, Vol. 26 (1949) 243248.

[89] Riordan, J. (1956): Derivation of moments of overflow traffic. Appendix 1 (pp. 507514) in (Wilkinson, 1956 [104]).

[90] Roberts, J.W. (1981): A service system with heterogeneous user requirements  applications to multiservice telecommunication systems. Pages 423431 in Performance of data communication systems and their applications. G. Pujolle (editor), NorthHolland Publ. Co. 1981.

[91] Roberts, J.W. (2001): Traffic theory and the Internet. IEEE Communications Magazine Vol. 39 (2001) : 1, 9499.

[92] Ross, K.W. & Tsang, D. (1990): Teletraffic engineering for productform circuitswitched networks. Adv. Appl. Prob., Vol. 22 (1990) 657675.

[93] Ross, K.W. & Tsang, D. (1990): Algorithms to determine exact blocking probabilities for multirate tree networks. IEEE Transactions on Communications. Vol. 38 (1990) : 8, 12661271.

[94] Rönnblom, N. (1958): Traffic loss of a circuit group consisting of bothway circuits which is accessible for the internal and external traffic of a subscriber group. TELE (Edición inglesa), 1959: 2, 7992.

[95] Sanders, B. & Haemers, W.H. & Wilcke, R. (1983): Simple approximate techniques for congestion functions for smooth and peaked traffic. ITC10, Tenth International Teletraffic Congress, Montreal, junio de 1983. Paper 4.4b1. 7 pp.

[96] Stepanov, S.S. (1989): Optimization of numerical estimation of characteristics of multiflow models with repeated calls. Problems of Information Transmission, Vol. 25 (1989): 2, 6778.

[97] Sutton, D.J. (1980): The application of reversible Markovp opulation processes to teletraffic. A.T.R. Vol. 13 (1980): 2, 38.

[98] Techguide (2001): Inverse Multiplexing  scalable bandwidth solutions for the WAN. Techguide (The Technologu Guide Series), 2001, 46 pp.

[99] Vaulot, É. & Chaveau, J. (1949): Extension de la formule d'Erlang au cas ou le traffic est fonction du nombre d'abonnés occupés. Annales de Télécommunications, Vol. 4 (1949) 319324.

[100] Veirø, B. (2002): Proposed Grade of Service chapter for handbook. Comisión de Estudio 2 del UIT-T, GT 3/2. Septiembre de 2001. 5 páginas.

[101] Villén, M. (2002): Overview of ITU Recommendations on traffic engineering. UITT Comisión de Estudio 2, COM 2-KS 48/2-E. Mayo de 2002. 21 pp.

[102] Wallström, B. (1964): A distribution model for telephone traffic with varying call intensity, including overflow traffic. Ericsson Technics, 1964, No. 2, pp. 183202.

[103] Wallström, B. (1966): Congestion studies in telephone systems with overflow facilities. Ericsson Technics, No. 3, 1966, pp. 187351.



[104] Wilkinson, R.I. (1956): Theories for toll traffic engineering in the U.S.A. The Bell System Technical Journal, Vol. 35 (1956) 421514.



(133000)
1   2   3   4   5   6


La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal