Математические модели и алгоритмы оптимального управления FIFO-очередями в общей памяти

Андрей Владимирович Соколов, Александр Михайлович Сазонов, Евсей Викторович Морозов, Руслана Сергеевна Некрасова, Ростислав Валерьевич Разумчик

Аннотация


В статье рассматриваются задачи оптимального распределения памяти для двух и произвольного числа очередей в общей памяти в дискретном времени. Приведены математические модели и алгоритмы оптимального распределения памяти между очередями, минимизирующие потери информации.

Ключевые слова


FIFO-очереди; теория массового обслуживания; дискретное время; оптимальное разделение памяти

Полный текст:

PDF

Литература


Кнут Д. Искусство программирования для ЭВМ. Т. 1. М.: Вильямс, 2001. 712 c.

Седжвик Р. Фундаментальные алгоритмы на С++. Киев: Диасофт, 2001. 687 c.

Боллапрагада В., Мэрфи К., Уайт Р. Структура операционной системы Cisco IOS. М.: Вильямс, 2002. 197 c.

Соколов А. В. О распределении памяти для двух стеков // Автоматизация эксперимента и обработки данных. 1980. С. 65–71.

Yao A. C. An Analysis of a Memory Allocation Scheme for Implementing Stacks // SIAM J. Comput. 1981. 10(2) P. 398–403. doi:10.1137/0210029

Louchard G. Some distributed algorithms revisited // Communications in Statistics. Stochastic Models. 1995. Vol. 11, iss. 4. doi:10.1080/15326349508807361

Louchard G., Schott R., Tolley M., Zimmermann P. Random walks, heat equation and distributed algorithms // Journal ofComputational and Applied Mathematics. 1994. Vol. 53, iss. 2, P. 243–274. doi: 10.1016/0377-0427(94)90048-5

Louchard G., Schott R. Probabilistic analysis of some distributed algorithms // Random, xxructures & Algorithms, 1991. Vol. 2, iss. 2. P. 151–186. doi: 10.1002/rsa.3240020203

Flajolet Ph. The evolution of two stacks in bounded space and random walks in a triangle // Mathematical Foundations of Computer Science,

Lecture Notes in Computer Science. 1986. Vol. 233. P. 325–340. doi: 10.1007/BFb0016257

Аксенова Е. А. Оптимальное управление FIFO-очередями на бесконечном времени //Стохастическая оптимизация в информатике. СПб.: С.-Петербургский университет, 2006. № 2 С. 71—76.

Аксенова Е.А., Драц А.В., Соколов А.В. Оптимальное управление n FIFO-очередями на бесконечном времени // Информационно-управляющие системы. 2009. № 6. С. 401—415.

Drac A. V., Sokolov A. V. The linked list representation of n LIFO-stacks and/or FIFOqueues in the single-level memory // Information Processing Letters. Elsevier Science PublishingCompany Inc. 2013. Vol. 13, no. 19–21. P. 832–835.

Соколов А. В., Драц А. В. Моделирование некоторых методов представления n FIFO очередей в памяти одного уровня // Эвристические алгоритмы и распределенные вычисления. 2014. Т. 1, № 1. С. 40—52.

Барковский Е. А., Соколов А. В. Оптимальное управление двумя параллельными FIFO-очередями на бесконечном времени // Информационно-управляющие системы. 2015. № 5. С. 65—71.

Irland M. I. Buffer management in packet switch // IEEE Transactions on Communications. Vol. COM-26. March 1978. P. 328–337. doi: 10.1109/TCOM.1978.1094076

Rich M., Schwartz M. Buffer sharing in computer-communication network nodes // IEEE trans. commun. Vol. COM-25. 1977. P. 958–970.

Yamashita H., Onvural R. O. Allocation of buffer capacities in queueing networks with arbitrary topologies // Annals of Operations Research. August 1994. Vol. 48, iss. 4. P. 313–332. doi: 10.1007/BF02024519

Perros H. G. Open queueing networks with blocking // Stochastic Analysis of Computer and Communications Systems / Ed. H. Takagi. NorthHolland, 1990.

Yum T. P., Dou C. Buffer allocation strategies with blocking requirements // Performance Evaluation. 1984. Vol. 4, iss. 4. P. 285–295. doi: 10.1016/0166-5316(84)90013-0

Kamoun E., Kleinrock L. Analysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Schemes // IEEE Transactions on Communications. July 1980. Vol. COM-28, no. 7. P. 992–1003.

Ozel O., Uysal-Biyikoglu E., Girici T. Optimal Buffer Partitioning on a Multiuser Wireless Link

// Proceedings of Information Theory and Applications Workshop, UCSD, San Diego, CA, Jan. 31 – Feb. 5, 2010. doi: 10.1109/ITA.2010.5454079

REFERENCES in ENGLISH

Knuth D. Iskusstvo programmirovaniya dlya EVM [The art of computer programming]. Vol. 1.

Moscow: Vilyams, 2001. 712 p.

Sedgewick R. Fundamentalnye algoritmy na С++ [Fundamental algorithms in C++]. Kiev:Diasoft, 2001. 687 p.

Bollapragada V., Murphi C., White R.

Struktura operacionnoj sistemy Cisco IOS [The

structure of Cisco IOS]. Moscow: Vilyams, 2002.

p.

Sokolov A. V. O raspredelenii pamyati dlya

dvuh stekov [On memory distribution for 2 stacks].

Avtomatizaciya eksperimenta i obrabotki dannyh

[Experiment automation and data processing].

P. 65–71.

Yao A. C. An Analysis of a Memory

Allocation Scheme for Implementing Stacks.

SIAM J. Comput. 10(2). 1981. P. 398–403. doi:

1137/0210029

Louchard G. Some distributed algorithms

revisited. Communications in Statistics.

Stochastic Models. 1995. Vol. 11, iss. 4. doi:

1080/15326349508807361

Louchard G., Schott R., Tolley M.,

Zimmermann P. Random walks, heat equation

and distributed algorithms. Journal of

Computational and Applied Mathematics. 1994.

Vol. 53, iss. 2. P. 243–274. doi: 10.1016/0377-

(94)90048-5

Louchard G., Schott R. Probabilistic

analysis of some distributed algorithms. Random

Structures & Algorithms. Summer 1991. Vol. 2,

iss. 2. P. 151–186. doi: 10.1002/rsa.3240020203

Flajolet Ph. The evolution of two stacks in

bounded space and random walks in a triangle. Mathematical Foundations of Computer Science,

Lecture Notes in Computer Science. 1986. Vol.

P. 325–340. doi: 10.1007/BFb0016257

Aksenova E. A. Optimalnoe upravlenie FIFOocheredyami

na beskonechnom vremeni [Optimal

control of the FIFO-queues for infinity time].

Stohasticheskaya optimizaciya v informatike [Stochastic

optimization in informatics]. St.-Petersburg:

S-Peterburgskii un., 2006. No. 2.

C. 71—76.

Aksenova Е. А., Drac A. V., Sokolov A. V.

Optimalnoe upravlenie n FIFO-ocheredyami na

beskonechnom vremeni [Optimal control of the n

FIFO-queues for infinity time]. Informacionnoupravlyayushchie

sistemy [Information and

control systems]. 2009. No. 6. C. 401—415.

Drac A. V., Sokolov A. V. The linked list

representation of n LIFO-stacks and/or FIFOqueues

in the single-level memory. Information

Processing Letters. Elsevier Science Publishing

Company Inc. 2013. Vol. 13, no. 19–21. P. 832–

Sokolov A. V., Drac A. V. Modelirovanie

nekotoryh metodov predstavleniya n FIFO

ocheredej v pamyati odnogo urovnya [Simulation

of some methods of representation of n FIFOques

in the single-level memory]. Evristicheskie

algoritmy i raspredelennye vychisleniya [Heuristic

algorithms and distributed computing]. 2014.

Vol. 1, no. 1. C. 40–52.

Barkovsky E. A., Sokolov A. V. Optimalnoe

upravlenie dvumya parallelnymi FIFOocheredyami

na beskonechnom vremeni [Optimal

control of two parallel FIFO-queues on an infinite

time]. Informacionno-upravlyayushchie sistemy

[Information and control systems]. 2015. No. 5

C. 65–71.

Irland M. I. Buffer management in packet

switch. IEEE Transactions on Communications.

Vol. COM-26. March 1978. P. 328–337. doi:

1109/TCOM.1978.1094076

Rich M., Schwartz M. Buffer sharing in

computer-communication network nodes. IEEE

trans. commun. Vol. COM-25. 1977. P. 958–970.

Yamashita H., Onvural R. O. Allocation

of buffer capacities in queueing networks with

arbitrary topologies. Annals of Operations

Research. August 1994. Vol. 48, iss. 4. P. 313–

doi: 10.1007/BF02024519

Perros H. G. Open queueing networks with

blocking, in: Stochastic Analysis of Computer and

Communications Systems, ed. H. Takagi. NorthHolland,

Yum T. P., Dou C. Buffer allocation strategies

with blocking requirements. Performance

Evaluation. 1984. Vol. 4, iss. 4. P. 285–295. doi:

1016/0166-5316(84)90013-0

Kamoun E., Kleinrock L. Analysis of Shared

Finite Storage in a Computer Network Node

Environment Under General Traffic Schemes.

IEEE Transactions on Communications. July

Vol. COM-28, no. 7. P. 992–1003.

Ozel O., Uysal-Biyikoglu E., Girici T.

Optimal Buffer Partitioning on a Multiuser

Wireless Link, In proceedings of Information

Theory and Applications Workshop, UCSD, San

Diego, CA, Jan. 31 – Feb. 5, 2010. doi:

1109/ITA.2010.5454079




DOI: http://dx.doi.org/10.17076/mat396

Ссылки

  • На текущий момент ссылки отсутствуют.


© Труды КарНЦ РАН, 2014-2016