Область пропускной способности коммутационных сетей массового обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

ГЛАВА I. ВВЕДЕНИЕ.

1.1. Предварительные замечания

1.2. Сети с коммутацией сообщений

1.3. Сети с коммутацией каналов.

ГЛ/иВА П. ОБЛАСТЬ ПРОПУСКНОЙ СПОСОБНОСТИ СЕТЕЙ СВЯЗИ С КОММУТАЦИЕЙ СООБЩЕНИЙ

2.1. Формальное описание пространства состояний и инфи-нитезимальных вероятностей процесса

2.2. Уравнения статистического равновесия и нахождение необходимых условий для эргодичности процесса

2.3. Построение одного вспомогательного процесса

2.4. Об одном классе процессов"с отказами"; нахождение необходимых и достаточных условий эргодичности в одном частном случае

2.5. Сети с приоритетами

2.6. Системы с монотонными маршрутами.

ГЛАВА Ш. ОБЛАСТЬ ПРОПУСКНОЙ СПОСОБНОСТИ ДЛЯ НЕКОТОРЫХ СЕТЕЙ С КОММУТАЦИЕЙ КАНАЛОВ.

3.1. Введение

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

3.3. Формальное описание марковских процессов, моделирующих сети связи с коммутацией каналов

3.4. Оценка области пропускной способности снизу для некоторых дисциплин обслуживания

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

I.I. Предварительные замечания

В последние годы создаются и развиваются сложные системы связи такие, как ARPANET, ALOHA и т.д., состоящие из большого числа узлов коммутации и допускающие существование многих очередей, состоящих из сообщений, возникающих в различных узлах коммутации. При исследовании поведения таких сетей возникает большое число различных математических задач (см.»например, монографию Клейнрока [19] ), которые решаются на различном уровне строгости, поскольку запросы практики существенно опережают возможности математического анализа таких сетей.

В диссертации рассматриваются марковские процессы с непрерывным временем и счетным числом состояний, моделирующие сети связи. Среди параметров, определяющих работу сетей связи, есть конечное семейство непрерывных параметров, являющихся интенсив-нос тями прихода в сеть сообщений различных типов и средними временами обслуживания сообщений различных типов в различных обслуживающих приборах (узлах коммутации). Кроме того, каждая сеть связи имеет "дискретную" топологическую характеристику, описывающую маршруты сообщений различных типов и режим коммутации. В работе также предполагается, что в сети могут накапливаться очереди с неограниченным числом мест для ожидания в различных узлах коммутации. В диссертации рассматривается следующий вопрос, -какова область значений непрерывных параметров -интенсивноетей прихода и средних времен обслуживания сообщений, цри заданной топологии сети и заданном режиме коммутации, внутри которой имеется стационарный режим работы сети, при этом рассматриваются лишь те математические модели работы сетей, которые укладываются в рамки марковских процессов с непрерывным временем и счетным числом состояний. Тогда описание области пропускной способности сетей можно переформулировать следующим образом: пусть имеется семейство марковских процессов, зависящее от конечного числа непрерывных параметров, моделирующее д сеть; . Необходимо найти ту область значений параметров, внутри которой данные марковские процессы будут эргодичными. Интерес к этому вопросу объясняется с одной стороны большим многообразием и сложностью марковских процессов, возникающих при рассмотрении сетей связи, с другой стороны, важностью для .приложений, поскольку лишь для значений параметров, лежащих в области пропускной способности, сеть имеет стационарный режим работы и имеет стационарные характеристики такие, как стационарное распределение длин очередей, стационарное распределение времени прохождений сообщений через сеть и т.д.

Отметим также, что все рассматриваемые в диссертации марковские процессы со счетным числом состояний, моделирующие рабоо и ту сетей связи, содержат лишь один неприводимым класс существенных состояний. Поэтому единственность стационарного распределения для таких процессов следует из его существования (см. »например, Ofdi.il §12). В работе рассмотрено два типа сетей связи - сети с коммутацией сообщений и сети с коммутацией каналов.

1. Боровков A.A. Вероятностные процессы в теории массового обслуживания. -М.: Наука, 1972, 367 с.

2. Боровков A.A. Асимптотические методы в теории массового обслуживания. -М.: Наука, 1980, 381 с.

3. Bunimovich L.A., Sinai.Ya.G., Markov partitions for dispersed -Communication in Math. Phisica 18, p.247-280.

4. Barbour A.D. Networks of Quenes and the Method of Stages -Adv. Appl. Pro., 1976, v.8, p.584-591.

5. Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. -М.Наука, 1965.

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

7. Башарин Г.П., Харкевич А.Д., Шнепс М.А. Массовое обслуживание в телефонии. -М.: Наука, 1968, 246 с.

8. Дэвис Д., Барбер Д., Сети связи для вычислительных машин.-М.: Мир, 1976, 680 с.

9. Добрушин Р.Л., Прелов В.В. Асимптотический подход к исследованию линейных сетей коммутации сообщений с большим числом узлов.- Проблемы передачи информации, 1979, т. 15 $ I, с. 6173.

10. Добрушин Р.Л., Сухов Ю.М. Асимптотическое исследование звездообразных сетей коммутации сообщении с большим числом радиальных лучей.-Проблемы передачи информации, 1976, т. 12, & I, с. 70-94.

11. Гихман И.И., Скороход A.B. Теория случайных процессов, т.1.-М.:Наука, 1971, 666 с.

12. Дуб Дж. Вероятностные цроцессы-М.: ИЛ, 1956, 605 с.

13. Ивченко Г.И., Каштанов В.А., Коваленко И.Н., Теория массового обслуживания,-М.: Высшая школы, 1982, 256 с.

14. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф.»Приоритетные системы обслуживания -М.:Изд-во МГУ, 1973, 382 с.

15. Jackson J.R. Jobshop-Like Queneing Systems.-Managern. Science, 1963, v.10, N 1, p. 131-142.

16. Jackson J.R. Networks of Waiting Lines.- Oper. Res. 1957, H 5, P. 518-521.

17. Калашников B.B. Качественный анализ поведения сложных систем методом дробных функций.-М.:Наука, 1978 , 247 с.

18. Клейнрок Л. Коммутационные сети. Стохастические потоки и задержки сообщений. М.:Наука, 1970 , 255 с.

19. Клейнрок Л. Вычислительные системы с очередями.-М.:Мир, 1979, 600 с.

20. Климов Г.П. Стохастические системы обслуживания.-М.: Наука, 1966.

21. Кельберт М.Я., Сухов Ю.М. Некоторые новые результаты о звездообразных сетях связи. -Тезисы докладов У Международного симпозиума по теории информации, т.1, Москва,Тбилиси: Наука, 1979, с. 176-178.

22. Кельберт М.Я., Сухов Ю.М. Об одном классе звездообразных сетей с пакетной коммутацией. Проблемы передачи информации, 1979, т. 15, Ш 4, с. 53-72.

23. Kiefer J., Wolfowitz J. On the theory of queues with many servers.- Trans. Amer. Math. Soc. 1955, 78, p.1-18.

24. Kiefer J. Wolfowitz J. On the characteristics of general queueing process with application to random walks.- Ann. Math.Statist. 1956. 27, p. 147-161.

25. Kelly P.P. Networks of Queues.- Adv. Appl. Prob., 1976, v.2, N 8, p. 416-432.

26. Kelly P.P. Reversibility and Stochastik Networks.-New York: J.Wiley, 1980, 230p.

27. Kramly A., Szasz D. Random Walks with Internal Degrees of Preec dom. Lokal Limit Theorems.- Preprint of Math. Budapest.1981, N 51.

28. Карлин С. Основы теории случайных процессов. .-М.:Мир,1971, 563 с.-14831. Козлов Б.А.: Васильев В.А., 0 влиянии закона распределения на надежность дублированной системы.-Теория надеж/ ности и массового обслуживания -М.:Наука, 1969.

29. Loynes R.M. On the Waiting-Time Distribution for Quenes in Series. -J.Roy.Statist. Soc., 1965, v. 27, N 3, p. 4.91-496.

30. Miller R.G. Stationary Equations in Continuons Time Markov Chains.- Trans.Amer. Math. Soc., 1963, t. 109, N 1.

31. Малышев B.A., Меньшиков M.B. Эргодичность, непрерывность и аналитичность счетных цепей Маркова-.Труды Московского Математического Общества, 1979, т.39, с. 3-48.

32. Mihaylov V.A.,Rybko А.Ы. The sufficient conditions for existence of stationary mode in channel swithing networks with quenes. Abstracts of International Coll. on Informational Theory.-Budapest, 1981, p.58.

33. Matthes K., Kerstan J., Mecke J. Infinitely Divisible Point Processes.-New York: J.Wiley and Sons, 1979, 532 p.

34. Рыбко А.Н. Стационарное распределение однородных во времени марковских процессов, моделирующих сети связи с коммутацией сообщений.-Проблемы передачи информации, 1981, т. 17, № I, с. 71-89.

35. Sinai Ya.G.Proceedings of the Kyoto Konferece.-Kyoto. 1981.

36. Феллер В. Введение в теорию вероятностей и ее приложения. -М: Мир, 1964, 498 с.

37. Чжун Кай-Лай. Однородные цепи Маркова. -М.:Мир, 1964, 425с.

38. Ширяев А.Н. Вероятноеть.-М.:Наука, 1980, 575 с.

39. Штоян Д. Качественные свойства и оценки стохастических моделей.-М.:Мир, 1979, 268 с.

40. Хасьминский Р.З. Устойчивость систем дифференциальных уравнений при случайном возмущении их параметров.-М. : Наука, 1969.

41. Хинчин А.Я. Работы по математической теории массового об-служивания.-М.:Физматгиз, 1963, 235 с.