Теория телетрафика

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

Предмет теории телетрафика

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

Теория телетрафика, как математическая теория, оперирует не с самими системами распределения информации, а с их математическими моделями. Математическая модель системы распределения информации включает следующие три основных элемента:

• входящий поток вызовов (требований на обслуживание),
• систему распределения и обработки информации и
• дисциплину обслуживания потока вызовов.

Входящие потоки вызовов

Входящие процессы, такие, как телефонные вызовы, поступающие в АТС, или интернет-потоки, математически описываются стохастическими точечными процессами — потоками однородных событий. Одним из самых важных, и в то же время удобным для математических выкладок, является пуассоновский процесс. Он достаточно точно моделирует ситуации с поступлением запросов на обслуживание от большого количества независимых источников, однако даёт неточные результаты при моделировании запросов на обслуживание (напр., потока пакетов), поступающих от одного источника, или малого количества источников[1].

В таких случаях более подходит пуассоновский процесс, управляемый марковской цепью (англ. Markov Modulated Poisson Process (MMPP))[1].

Среди других моделей можно назвать авторегрессивный гауссовский процесс, экспоненциальный авторегрессивный процесс и пакетный процесс Пуассона-Парето (англ. Poisson Pareto Burst Process (PPBP))[1]. Процесс PPBP, сравнительно со своими предшественниками даёт наилучшие результаты для интернет-трафика[1]. Дальнейшее изучение пакетных систем (и вообще, систем со «всплесками») привело к понятию самоподобных (фрактальных) процессов[2] [3].

Системы распределения и обработки информации

• Сеть связи, то есть, совокупность коммутационных приборов, например, аналоговых, электронных или цифровых АТС, коммутаторов пакетов и т. п.;
• Коммутационный узел или одна или несколько его частей.

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

Дисциплина обслуживания

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

• способ обслуживания вызовов (с потерями, с ожиданием, комбинированное обслуживание);
• порядок обслуживания вызовов (в порядке очередности, в случайном порядке, обслуживание пакетами и др.);
• режимы искания выходов схемы (свободное, групповое, индивидуальное);
• законы распределения длительности обслуживания вызовов (показательный закон, постоянная или произвольная длительность обслуживания);
• наличие преимуществ (приоритетов) в обслуживании некоторых категорий вызовов;
• наличием ограничений при обслуживании всех или некоторых категорий вызовов (то есть, ограничения по длительности ожидания, числу ожидающих вызовов, длительности обслуживания);
• законы распределения вероятностей выхода из строя элементов схемы.

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

Цель теории телетрафика

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

Задачи теории телетрафика

Включают задачи анализа, синтеза и оптимизации.

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

• Развитие координатной, квазиэлектронной и электронной (цифровой) коммутационной техники поставило перед теорией телетрафика сложные вероятностно-комбинаторные задачи синтеза, в которых требуется определить структурные параметры коммутационных систем при заданных потоках, дисциплине и качестве обслуживания.

• Близкими к задачам анализа и синтеза являются задачи оптимизации. Эти задачи при проектировании систем распределения информации формулируются следующим образом: определить такие значения структурных параметров коммутационной системы (алгоритмы функционирования), для которых:
  • при заданных потоках, качестве и дисциплине обслуживания стоимость или объем оборудования системы распределения информации минимальны и
  • при заданных потоках, дисциплине обслуживания и стоимости качественные показатели функционирования системы распределения информации оптимальны.

Методы решения задач теории телетрафика

Основной математический аппарат составляют:

• теория вероятностей,
• математическая статистика и
• комбинаторика.

История развития теории телетрафика

Основы были заложены в работах А. К. Эрланга по исследованию пропускной способности полнодоступного пучка линий, обслуживающего простейший поток вызовов с потерями и с ожиданием. Труды А. К. Эрланга послужили толчком для других работ, которые были связаны с подтверждением, развитием или опровержением его результатов.

В 1918 году Т. Энгсет обобщил результаты А. К. Эрланга на случай обслуживания полнодоступным пучком потока вызовов от конечного числа источников нагрузки, а в 1927 году Г. О’Делл опубликовал результаты исследований по неполнодоступным ступенчатым включениям. Э. Молина работал по теории группообразования.

В 1928 году Т. Фрай написал первую книгу по теории вероятностей, в которой одна из глав была посвящена теории телетрафика.

В 1933 году советский математик А. Н. Колмогоров выполнил свою классическую работу по аксиоматическому обоснованию теории вероятностей, в которой идея А. К. Эрланга о статистическом равновесии была отождествлена со стационарной мерой марковского процесса. В этот период появились первые работы А. Я. Хинчина по исследованию систем с ожиданием.

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

Первое большое исследование в этом направлении было выполнено в 1950 году К. Якобеусом, которое основывалось на априорных распределениях вероятностей состояний системы. Другой метод расчета потерь в таких системах, а именно — метод вероятностных графов, был предложен К. Ли в 1955 году.

Обобщение и развитие методов теории телетрафика и, в первую очередь, работ А. К. Эрланга и К. Пальма были выполнены А. Я. Хинчиным в 1955 году. Его работа, в виде отдельной книги, издана в 1963 году[4].

Автоматизация междугородной телефонной связи поставила перед теорией телетрафика задачу расчета пропускной способности сетей с обходными направлениями. Первые работы по этому вопросу были опубликованы в 1956 году Р. Вилкинсоном и, независимо от него, Г. Бретшнайдером.

Исследование параметров избыточной нагрузки на таких сетях выполнено Д. Риорданом[5].

С автоматизацией междугородной связи тесно связана проблема повторных вызовов. Эту проблему изучали ученые разных стран: А. Эллдин (Швеция), Л. Костен и Ж. Коэн (Нидерланды), П. Ле-Галль (Франция), М. А. Шнепс-Шнеппе, Г. Л. Ионин, Ю. Н. Корнышев (СССР).

Развитие квазиэлектронной техники поставило перед теорией телетрафика проблему синтеза многозвеньевых коммутационных систем. В 1953 году Ч. Клоз опубликовал первую работу[6] по многозвеньевым неблокирующим коммутационным схемам, а в начале 60-х годов серию работ по анализу и синтезу многозвеньевых схем выполнил В. Бенеш[7].

В 1970-х и 1980-х годах авторами У. Ечиали, П. Науром, М. Цукерманом и И. Рубиным изучались, с использованием Z-преобразований, процессы MMPP[8] [9] [10] [11]. Для анализа очередей в контексте MMPP М. Ф. Нейтс разработал матричные методы [12].

Литература

• М.А. Шнепс-Шнеппе. Численные методы теории телетрафика. — М.: Связь, 1974. — 232 с.

• Лившиц Б.С. и др. Теория телетрафика. — М.: Связь, 1979. — С. 224, ил.

• ITU–D, Study Group 2, Question 16/2. TELETRAFFIC ENGINEERING Handbook. — Geneva, January 2005.
• Башарин Г. П. Лекции по математической теории телетрафика. Изд. 3-е, перераб. и доп. — М.: РУДН, 2009.

• Степанов С. Н. Теория телетрафика: концепции, модели, приложения. — М.: Горячая линия - Телеком, 2015. — 868 с. — ISBN 978-5-9912-0543-6.

Примечания

1. Moshe Zukerman. Introduction to Queueing Theory and Stochastic Teletraffic Models. — Copyright M. Zukerman (c) 2000-2014. — С. 238. Архивировано 11 августа 2016 года.
2. Walter Willinger and Vern Paxson. Where Mathematics Meets the Internet // NOTICES OF THE AMS. — September 1998. — Т. 45, № 8. — С. 961—970.
3. Б.Цыбаков и Н. Георганас, 1998 [1] Архивная копия от 13 сентября 2013 на Wayback Machine
4. Хинчин А. Я. Работы по математической теории массового обслуживания. — М.: Физматгиз, 1963.
5. Риордан Дж. Вероятностные системы обслуживания. — М.: Связь, 1966.
6. Clos, Charles. A study of non-blocking switching networks (англ.) // Bell Labs Technical Journal^[англ.] : journal. — 1953. — March (vol. 32, no. 2). — P. 406—424. — ISSN 00058580. Архивировано 14 марта 2012 года.
7. Бенеш В. Э. Математические основы теории телефонных сообщений. — М.: Связь, 1968.
8. U. Yechiali and P. Naor. Queuing Problems with Heterogeneous Arrivals and Service // Operations Research. — 1971. — Т. 19. — С. 722—734.
9. M. Zukerman and I. Rubin. Performance of flow-controlled communications systems under bursty traffic // Proceedings of IEEE GLOBECOM ’86. — Houston, December 1986. — Т. 3. — С. 1266—1271.
10. M. Zukerman and I. Rubin. Queueing performance of demand-assigned multi access communication systems under bursty traffic conditions // Proceedings of IEEE ICC ’86. — Toronto, Canada, June 1986. — Т. 3, № 57.2. — С. 1827—1832.
11. M. Zukerman and I. Rubin. On multi channel queueing systems with fluctuating parameters // Proceedings of IEEE INFOCOM ’86. — Miami, Florida, April 1986. — С. 600—608.
12. M. F. Neuts. Matrix-geometric solutions in stochastic models - algorithmic approach. — Baltimore: Johns Hopkins University Press, 1981.