Динамическое управление маршрутизацией в сетях массового обслуживания тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Юдаева, Наталия Валерьевна

• Юдаева, Наталия Валерьевна
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Юдаева, Наталия Валерьевна

Введение

Глава 1. Обзор основных результатов по сетям массового обслуживания с управлением маршрутизацией

1.1. Теория и анализ сетей массового обслуживания с управлением маршрутизацией.

1.2. Синтез сетей массового обслуживания с управлением маршрутизацией

1.3. Методы управления маршрутизацией в сетях массового обслуживания

Глава 2. Метод динамического управления маршрутизацией в сетях массового обслуживания

2.1. Постановка задачи и основные определения.

2.2. Маршрутные матрицы сетей массового обслуживания с управлением маршрутизацией.

2.3. Управление эволюцией сетей обслуживания

Глава 3. Анализ сетей обслуживания с динамическим управлением маршрутизацией

3.1. Распределение вероятностей состояний сети с управлением маршрутизацией.

3.2. Оптимальные длительности тактов

Глава 4. Оптимизация параметров управления маршрутизацией 50 4.1. Аддитивные характеристики сетей массового обслуживания

4.2. Формирование оптимального состава множества доминантных состояний.

Глава 5. Исследование сетей массового обслуживания с динамической маршрутизацией

5.1. Формирование вспомогательных маршрутных матриц

5.2. Оценка эффективности управления маршрутизацией

5.3. Определение множества доминантных состояний.

Введение диссертации (часть автореферата) на тему «Динамическое управление маршрутизацией в сетях массового обслуживания»

Эффективность использования сетей массового обслуживания (СеМО) в качестве математических моделей больших сложных систем с сетевой структурой и стохастическим характером функционирования (БСС) обусловила интенсивное развитие в течение последних трех десятилетий теории сетей массового обслуживания и методов анализа и синтеза СеМО [1-33]. Примерами систем указанного класса могут служить информационно-вычислительные сети, сети передачи данных, гибкие производственные системы. Структурная и функциональная специфика систем этого класса и использование в этих системах развитых подсистем управления со сложными алгоритмами управления существенно затрудняют решение задач анализа, синтеза и оптимизации систем этого класса, возникающих при их проектировании и эксплуатации. В связи с этим в значительной степени возрастают требования к используемым при решении этих задач математическим моделям и методам. Существенный вклад в развитие теории сетей массового обслуживания, разработку и развитие методов их анализа, синтеза и оптимизации внесли отечественные ученые: А.А.Боровков, Г.П.Башарин, В.В.Рыков, В.М.Вишневский, П.П.Бочаров, В.А.Ивницкий, Ю.В.Солодянников, В.А.Жожикашвили. Среди зарубежных специалистов необходимо отметить значительный вклад в развитие этого научного направления таких ученых как Дж.Джексон, Л.Клейнрок, Ф.Кеяли, Д.Тауслей, К.Чэнди, М.Райзер.

Отображение в модельных СеМО средств и методов управления БСС приводит к построению сетей обслуживания с управлением, которые фактически являются подклассом сетей массового обслуживания. СеМО с управлением обеспечивают не только принципиальную возможность решения целого класса задач анализа и синтеза БСС, но и возможность решения ряда задач, связанных с повышением эффективности управленшз БСС.

В основу диссертации положены результаты научных исследований, выполненных при участии автора в Саратовском государственном университете по темам, включенным в план НИР СГУ: "Управление сетями массового обслуживания" (шифр "Контур", гос.рег. № 01930007386), "Теория и методы управления сетями массового обслуживания" (шифр "Звено", гос.рег. Xе 01960007744), "Синтез сетей массового обслуживания с управлением" (шифр "Такт", гос.рег. ЗУ« 01200001098).

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

Основными задачами, решаемыми в диссертации, являются следующие.

1. Разработка принципов и методов динамического управления маршрутизацией в сетях массового обслуживания.

2. Анализ сетей обслуживания с динамическим управлением маршрутизацией.

3. Оптимизация параметров управления в сетях обслуживания с динамическим управлением маршрутизацией.

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

Основными результатами диссертации являются следующие.

1. Разработаны принципы и методы динамического управления маршрутизацией в сетях массового обслуживания.

2. Получены основные характеристики сетей обслуживания с динамическим управлением маршрутизацией.

3. Разработаны методы определения оптимальных значений параметров управления маршрутизацией.

Постановка задач, методы решения и полученные результаты являются новыми.

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

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

Результаты диссертации опубликованы в работах [34-39]. Результаты докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета и на Первом Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2000).

Результаты диссертационной работы получены автором самостоятельно. Научный руководитель - доктор технических наук, профессор Ю.И.Митрофанов, соавтор совместных публикаций, принимал участие в постановке задач, решаемых в диссертационной работе, в разработке концепций динамического управления маршрутизацией в СеМО, в формировании идей доказательств некоторых утверждений.

Диссертация состоит из введения, пяти глав и заключения. Объем диссертации -81 страница. Диссертация содержит 7 таблиц. Список

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Юдаева, Наталия Валерьевна

Заключение

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

1. Разработаны принципы и интервальный метод динамического управления маршрутизацией в однородных замкнутых экспоненциальных сетях массового обслуживания.

2. Разработан метод формирования матриц передач, определяющих маршруты требований, завершивших обслуживание в одной из систем.

3. Разработан метод формирования вспомогательных маршрутных матриц, используемых в течение вспомогательных тактов цикла функционирования сети с интервальным методом управления маршрутизацией.

4. Определены распределения вероятностей состояний в моменты окончания тактов и предельные распределения сети с интервальным методом управления маршрутизацией.

5. Определены оптимальные значения временных параметров метода динамического управления маршрутизацией - длительностей основного и вспомогательных тактов цикла функционирования сети.

6. Установлена связь между стационарными характеристиками и состояниями сети обслуживания.

7. Разработан метод определения оптимального значения структурного параметра управления - множества доминантных состояний.

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

В заключение, выражаю глубокую благодарность научному руководителю профессору Ю.И.Митрофанову за участие в постановке задач, руководство ходом исследований и консультации, а также искренне благодарю коллектив кафедры системного анализа и автоматического управления Саратовского государственного университета им. Н.Г.Чернышевского за ценные замечания, сделанные при обсуждении результатов на научных семинарах кафедры, и помощь, оказанную при оформлении диссертации.

Список литературы диссертационного исследования кандидат физико-математических наук Юдаева, Наталия Валерьевна, 2000 год

1. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989. 336 с.

2. Беляков В.Г., Митрофанов Ю.И. К исследованию замкнутых сетей массового обслуживания большой размерности // Автоматика и телемеханика. 1981. N 7. С. 61-67.

3. Гнеденко В.И., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966. 432 с.

4. Горцев A.M., Назаров A.A., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания. Томск: Изд-во Томского ун-та, 1978. 208 с.

5. Горцев A.M., Шмырин И.С. Оптимальная оценка состояний дважды стохастического потока событий при наличии ошибок в изменениях моментов времени // Автоматика и телемеханика. 1999. N 1. С. 52-66.

6. Гурьянов А.И., Митрофанов Ю.И. Определение параметров замкнутых линейный сетей систем массового обслуживания // Системное моделирование. Новосибирск: Вычислительный центр СО АН СССР, 1970. N 1. С. 39-49.

7. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. 192 с.

8. Илюшин В.В., Солодянников Ю.В. Оценка распределения суммарной длительности обслуживания в одноканальной системе обслуживания общего вида // Техническая кибернетика. Известия АН СССР. 1981. N 6. С. 73-81.

9. Илюшин В,Б., Солодянников Ю.В. К анализу потоков восстановления // Автоматика и телемеханика. 1983. N 6. С. 66-73.

10. Кениг Д., Штойян Д. Методы теории массового обслуживания / Пер. с нем. М: Радио и связь, 1981. 128 с.

11. Клейнрок JI. Теория массового обслуживания /Пер. с англ. М.: Машиностроение, 1979. 432 с.

12. Клейнрок JI. Вычислительные системы с очередями /Пер. с англ. М.: Мир, 1979. 600 с.

13. Климов Г.П. Теория вероятностей и математическая статистика. М.: Изд-во МГУ, 1983. 328 с.

14. Клячко A.A., Солодянников Ю.В. Вычисление распределения свертки винеровского процесса // Проблемы передачи информации. 1985. Т. 21. N 4. С. 41-48.

15. Клячко A.A., Солодянников Ю.В. Вычисление характеристических функций некоторых квадратичных функционалов от винеровского процесса // Теория вероятностей и ее применения. 1986. Т. 31. N 3. С. 569-573.

16. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения /Пер. с фр. М.: Мир, 1965. 303 с.

17. Митрофанов Ю.И. Исследование замкнутых сетей систем массового обслуживания // III Всесоюз. конф. по проблемам теоретической кибернетики: Тез. докл. Новосибирск: Институт математики СО АН СССР, 1974. С. 44-46.

18. Митрофанов Ю.И., Беляков В.Г., Курбангулов В.Х. Методы и программные средства аналитического моделирования сетевых систем. Препринт научного совета АН СССР по комплексной проблеме "Кибернетика", 1982. 68с.

19. Митрофанов Ю.И. Основы теории сетей массового обслуживания. Саратов: Изд-во Сарат. ун-та, 1993. 116 с.

20. Митрофанов Ю.И. Синтез сетей массового обслуживания. Саратов: Изд-во Сарат. ун-та, 1995. 164 с.

21. Анализ и оптимизация сетей массового обслуживания: Программное обеспечение /Митрофанов Ю.И., Брагина И.Г., Тананко И.Е., Юдаева Н.В.; Под ред. Митрофанова Ю.И.- Саратов: Изд-во ГосУНЦ "Колледж", 1995. 144 с.

22. Назаров A.A., Южаков А А. Мультипликативность стационарного распределения состояний многолинейной немарковской системы обслуживания при неоднородном входящем потоке // Автоматика и телемеханика. 1997. N 4. С. 113-120.

23. Солодянников Ю.В. О статистике систем и сетей массового обслуживания // Проблемы устойчивости стохастических моделей. Труды X Всесоюз. семинара. Куйбышевский государственный университет, 1987. С. 101-116.

24. Солодянников Ю.В. Робастное непараметрическое оценивание характеристик систем массового обслуживания // Автоматика и телемеханика. 1988. N 4. С. 63-77.

25. Солодянников Ю.В. О прямых и обратных задачах непараметрической статистики систем массового обслуживания // Известия ВУЗов. Математика. 1989. N 10.

26. Уолрэнд Дж. Введение в теорию сетей массового обслуживания /Пер. с англ. М.: Мир, 1993. 336 с.

27. Baskett F., Chandy K.M., Müntz R.R., Palacios F.G. Open, closed, and mixed networks of queues with different classes of customers //J.

28. ACM. 1975. Vol. 22. N 2. P. 248-260.

29. Chandy K.M., Herzog U., Woo L. Parametric analysis of queuing networks // IBM J. Res. Dev. 1975. Vol. 19. N 1. P. 36-42.

30. Chandy K.M., Herzog U., Woo L. Approximate analysis of general queuing networks // IBM J. Res. Dev. 1975. Vol. 19. N 1. P. 43-49.

31. Chandy K.M., Howard J.H.Jr., Towsley D.F. Product form and local balance in queueing networks //J. ACM. 1977. Vol. 24. N 2. P. 250-263.

32. Gordon W.J., Newell G.F. Closed queuing systems with exponential servers // Oper. Res. 1967. Vol. 15. N 2. P. 254-265.

33. Jackson J.R. Networks of waiting lines //Oper. Res. 1957. Vol. 5. N 4. P. 518-521.

34. Митрофанов Ю.И., Юдаева H.B. Адаптивная маршрутизация в сетях массового обслуживания. Саратов, 1997.- Деп. в ВИНИТИ 13.06.97, N 1947-В97.

35. Митрофанов Ю.И., Юдаева Н.В. Анализ сетей массового обслуживания с адаптивной маршрутизацией. Саратов, 1997- Деп. в ВИНИТИ 27.07.97, N 2507-В97.

36. Митрофанов Ю.И., Юдаева Н.В. Управление маршрутизацией в сетях массового обслуживания //Автоматика и телемеханика. 1999. N 11. С. 46-57.

37. Митрофанов Ю.И., Юдаева Н.В. Об оптимизации параметров сетей массового обслуживания с управлением маршрутизацией. Саратов, 2000.- Деп. в ВИНИТИ 31.01.2000, N 213-В00.

38. Митрофанов Ю.И., Юдаева Н.В. Модели и анализ сетей массового обслуживания с управлением маршрутизацией //Автоматика и телемеханика. 2000. N 6. С. 104-113.

39. Митрофанов Ю.И., Юдаева Н.В. Временные параметры динамического управления маршрутизацией в сетях массового обслуживания // Обозрение прикладной и промышленной математики. 2000. Т. 7. N 1. С. 194-195.

40. Towsley D. Queueing network models with state-dependent routing //J. ACM. 1980. Vol. 27. N 2. P. 323-337.

41. Krzesinski A.E. Multiclass queueing networks with state-dependent routing // Performance Evaluations. 1987. Vol. 7. N 2. P. 125-143.

42. Малинковский Ю.В. Инвариантность стационарного распределения состояний модифицированных сетей Джексона и Гордона-Ньюэлла // Автоматика и телемеханика. 1998. N 9. С. 29-36.

43. Крыленко А.В. Сети массового обслуживания с несколькими типами заявок, немедленным обслуживанием и обходами узлов заявками // Проблемы передачи информации. 1997. Т. 33. N 3. С. 91-101.

44. Ивницкий В.А. Об инвариантности стационарных вероятностей состояний замкнутой звездообразной сети массового обслуживания при зависимости вероятностей перехода от ее состояния // Теория вероятностей и ее применения. 1997. Т. 42. N 1. С. 179-184.

45. Ивницкий В.А. О стационарных вероятностях состояний замкнутой звездообразной сети массового обслуживания при зависимости вероятностей перехода от ее состояния // Автоматика и вычислительная техника. 1994. N 6. С. 29-37.

46. Serfozo R.F. Markovian network processes: congestion-dependent routing and processing // Queueing Systems. 1989. Vol. 5. P. 5-36.

47. Chao X., Pinedo M. On generalized networks of queues with positive and negative arrivals // Probability in the Engineering and Informational Sciences. 1993. Vol. 7. P. 301-334.

48. Chao X., Pinedo M. On queueing networks with signals and history-dependent routing // Probab. Eng. and Inf. Sci. 1995. Vol. 9. N 3.1. P. 341-354.

49. Henderson W., Northcote B.S., Taylor P.G. State-dependent signalling in queueing networks // Adv. Appl. Prob. 1994. Vol. 26. P. 436-455.

50. Boucherie R.J., Dijk N.M. Product forms for queueing networks with state-dependent multiple job transitions // Adv. Appl. Prob. 1991. Vol. 23. P. 152-187.

51. Miyazawa M. Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing // Queueing Systems. 1997. Vol. 25. P. 45-75.

52. Boucherie R.J. Norton's equivalent for queueing networks comprised of quasireversible components linked by state-dependent routing // Performance Evaluation. 1998. Vol. 32. N 2. P. 83-99.

53. Печинкин А.В., Рыков В.В. О декомпозиции замкнутых сетей с зависимым обслуживанием // Автоматика и телемеханика. 1999. N11. с. 58-68.

54. Крыленко А.В., Малинковский Ю.В. Сети массового обслуживания с мгновенно обслуживаемыми заявками II. Модели с несколькими типами заявок // Автоматика и телемеханика. 1998. N 2. с. 62-71.

55. Малинковский Ю.В., Якубович О.В. Сети массового обслуживания с мгновенно обслуживаемыми заявками I. Модели с одним типом заявок // Автоматика и телемеханика. 1998. N 1. с. 92-106.

56. Economou A., Fakinos D. Product form stationary distributions for queueing networks with blocking and rerouting // Queueing Systems. 1998. Vol. 30. P. 251-260.

57. Bertsimas D., Paschalidis I.Ch., Tsitsiklis J.N. Optimization of multiclass queueing netwokks: polyhedral and nonlinear characterizations of achievable performance // Ann. Appl. Prob. 1994. Vol. 4. P. 43-75.

58. Tassiulas L., Ephremides A. Throughput properties of queueing network with distributed dynamic routing and flow control // Adv. Appl. Prob. 1996. Vol. 28. P. 285-307.

59. Menich R., Serfozo R.F. Optimality of routing and servicing inde-dendent parallel processing systems // Queueing Systems. 1991. Vol. 9. P. 403-418.

60. Kelly F.P. Routing in circuit-switched networks: Optimization, shadow prieces and decentralization // Adv. Appl. Prob. 1988. Vol. 20. P. 112-144.

61. Kelly F.P. Dynamic routing in stochastic networks //In Stochastic Networks (Editors F.P.Kelly and R.J.Williams) The IMA Volumes in Mathematics and its Applications, 71. Springer- Verlag, New York. 1995. P. 169-186.

62. Kelly F.P. Network routing // Philosophical Transactions of the Royal Society 1991. A 377. P. 343-367.

63. Бурлаков M В, Ситуационное управление процессами обслуживания с синхронизированными управлениями // Автоматика и телемеханика. 1993. N 8. С. 63-73.

64. Boel R.K., Schuppen J.H. Distributed routing for load balancing // Discrete Event Dynamic Systems Analyzing complexity and performance in modern world Y.C.Ho ed. 1992. P. 237-248.

65. Alanyali M., Hajek B. Analysis of simple algorithms for dynamic load balancing // Math. Oper. Res. 1997. Vol. 22. N 4. P. 840-871.

66. Hajek В., Ogier R.G. Optimal dynamic routing in communication networks with continuous traffic // Networks. 1984. Vol. 14. P. 457-487.

67. Calvert В., Solomon W., Ziedins I. Braess's paradox in a queueing network with state-dependent routing //J. Appl. Prob. 1997. Vol. 34. P. 134-154.

68. Kelly F.P., Laws C.N. Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling // Queueing Systems. 1993. Vol. 13. P. 47-86.

69. Bertsimas D., Chryssikou T. Bounds and policies for dynamic routing in loss networks // Oper. Res. 1999. Vol. 47. N 3. P. 379-394.

70. Korilis Y.A., Lazar A.A., Orda A. Achieving network optima using stackelberg routing stategies // IEEE Transactions on Networking. 1997. Vol. 5. N 1. P. 161-173.

71. Stidham S.Jr., Weber R. A survey of Markov decision models for control of networks of queues // Queueing Systems. 1993. Vol. 13. P. 291-314.

72. Poznyak A.S., Najim K. Adaptive control of constrained finite Markov chains // Automatica. 1999. Vol. 35. P. 777-789.

73. Ибрагимов А.А. Об управляемых марковских процессах с поглощением // Автоматика и телемеханика. 1999. N 12. С. 80-89.

74. Mitra D., Mitrani I., Ramakrishnan K.G., Seery J.В., Weiss A. A unified set of proposals for control and design of high speed data networks // Queueing Systems. 1991. Vol. 9. P. 215-234.

75. Kelly F.P., Maullo о A.K., Tan D.K.H. Rate control for communication networks: shadow prices, proportional fairness and stability // Journal of the Operational Research Society. 1998. Vol. 49. P. 237-252.

76. Gibbens R., Kelly F., Turner S. Dynamic routing in multiparented networks // IEEE/ACM Transactions on Networking. 1993. Vol. 1. P. 261-270.

77. Hsu L.-F., Tapiero C.S., Lin C. Network of queues modeling in flexible manufacturing systems: a survey // Recherche operationelle (Operations Research). 1993. Vol. 27. N 2. P. 201-248.

78. Buzacott J.A., Yao D.D. On queueing network models of flexiblemanufacturing systems // Queueing Systems. 1986. Vol. 1. N 1. P. 5-27.

79. Малинковский Ю.В. Выходные потоки в модифицированных сетях Джексона // Автоматика и телемеханика. 1992. N 9. С. 134138.

80. Mandelbaum A., Pats G. State-dependent stochastic networks, Part I: Appoximations and applications with continuous diffusion limits // Annals of Applied Probability. 1998. Vol. 8. N 2. P. 569-646.

81. Баруча-Рид А.Т. Элементы теории марковских процессов и их приложения /Пер. с англ. М.: Наука, 1969. 512 с.

82. Карлин С. Основы теории случайных процессов /Пер. с англ. М.: Мир, 1971. 536 с.

83. Феллер В. Введение в теорию вероятностей и ее приложения /Пер. с англ. М.: Мир, 1967. Т.1. 499 с.

84. Кемени Д.Д., Снелл Д.Л. Конечные цепи Маркова: /Пер. с англ. М.: Наука, 1970. 272 с.

85. Чжун Кай-лай. Однородные цепи Маркова /Пер. с англ. М.: Мир, 1964. 428 с.