Содержание к диссертации
Введение
1. Анализ мультисервисных сетей связи как социально-технических систем 10
1.1. Особенности мультисервисных сетей связи 10
1.1.1. Услуги, оказываемые мультисервисными сетями связи 10
1.1.2. Структура мультисервисных сетей связи 11
1.1.3. Основные параметры качества инфокоммуникационных услуг 13
1.1.4. Дисциплина обслуживания в мультисервисных сетях связи 16
1.1.5. Классификация пользователей мультисервисных сетей связи 19
1.1.6. Проблемы анализа сетей связи 21
1.2. Методы математического моделирования сетей связи 22
1.3. Концептуальная постановка задачи моделирования и оптимизации мультисервисных сетей связи 29
1.4. Цель работы и задачи исследования 39
2. Формализованное описание задачи моделирования и оптимизации мультисервисной сети связи 41
2.1. Оптимизационная модель магистрального уровня сети 41
2.1.1. Выбор критериев оптимизации ядра сети 41
2.1.2. Потоковая модель сети связи 46
2.2. Оптимизационная модель распределительного уровня сети 48
2.2.1. Модель распределительной сети как системы массового обслуживания 48
2.2.2. Обобщенный критерий оптимальности распределительного уровня мультисервисной сети связи 53
Выводы 63
3. Численная реализация модели магистрального уровня сети 64
3.1. Линеаризация модели оптимизации ядра сети 65
3.1.1. Модифицированный симплекс-метод 70
3.1.2. Алгоритм Дейкстры поиска кратчайшего пути 74
3.1.3. Алгоритм нахождения начального базисного допустимого решения 76
3.2.Эвристический алгоритм неполного перебора 78
3.3.Описание программного комплекса для моделирования и анализа магистрального уровня МСС 80
3.3.1. Выбор платформы для моделирования 81
3.3.2. Взаимодействие с внешними источниками информации... 82
3.3.3. Выбор структуры программного комплекса 82
3.3.4. Графический интерфейс 84
3.3.5. Запуск процедуры решения задачи и вывод результатов... 88
3.3.6. Команды главного меню 89
3.4. Идентификация модели оптимизации магистрального уровня мультисервисной сети связи 90
Выводы 95
4. Численная реализация и проверка адекватности модели распределительного уровня сети 97
4.1. Пример построения обобщенного критерия оптимальности распределительного уровня сети 97
4.2. Описание программного комплекса для моделирования и анализа распределительного уровня МСС 103
4.2.1. Выбор платформы для моделирования 104
4.2.2. Выбор структуры программного комплекса 105
4.2.3. Графический интерфейс 107
4.2.4. Команды главного меню 109
4.3. Тестирование имитационного алгоритма и программного комплекса 110
4.4. Решение демонстрационных примеров и анализ результатов 112
Выводы 123
Заключение 125
Список литературы 127
- Основные параметры качества инфокоммуникационных услуг
- Концептуальная постановка задачи моделирования и оптимизации мультисервисных сетей связи
- Обобщенный критерий оптимальности распределительного уровня мультисервисной сети связи
- Идентификация модели оптимизации магистрального уровня мультисервисной сети связи
Введение к работе
Актуальность темы. Современная сеть передачи данных является сложной системой, требования к которой предъявляются со стороны различных групп потребителей и операторов услуг. Любая, даже самая мощная, сеть передачи данных обладает ограниченными ресурсами для удовлетворения запросов пользователей. Увеличение количества доступных ресурсов возможно, но это требует дополнительных затрат от оператора сети. Пользователи сети, с одной стороны, заинтересованы в том, чтобы получать максимальное количество услуг с наивысшим качеством, с другой стороны - в снижении своих затрат на использование сети. Сообщество потребителей услуг неоднородно, разные группы потребителей хотят получать разные услуги и с разным качеством, что, в свою очередь, приводит к предъявлению противоречивых требований ко всей системе. Для качественного проектирования сетей передачи данных необходим учет всех требований, предъявляемых к сети. В последнее время все большее распространение получают мультисервисные сети связи (МСС), основное отличие которых от традиционных сетей заключается в том, что вместо одной услуги, предоставляемой традиционной сетью МСС предоставляют широкий спектр услуг. В условиях быстрого развития сетей передачи данных невозможно качественное проектирование на основе одного лишь опыта и интуитивных решений. Многие операторы сетей связи вынуждены собственными силами решать задачи развития, модернизации и анализа сетей. Для сведения к минимуму последствия ошибок приходится неоправданно завышать требования к оборудованию, что, в свою очередь, ведет к необоснованному увеличению стоимости строительства и эксплуатации всей сети связи. Проблема проектирования МСС достаточно сложна и её качественное решение не возможно без привлечения специального математического аппарата.
Основные параметры качества инфокоммуникационных услуг
Мультисервисная сеть связи может использоваться для оказания различных типов услуг, различающихся по требуемой емкости канала связи и требованиям к качеству передачи данных. В современных сетях связи обычно выделяют следующие параметры, влияющие на качество передачи данных[15]:
Latency (задержка) - время прохождения данных по сети. При передаче голосовых и видео данных предъявляются особенно жесткие требования к максимально допустимой задержке. Односторонняя задержка не должна превышать 100 мс (задержка на передачу данных и задержка на их декодирование оборудованием абонента). Для уменьшения задержки, вносимой сетью, используют QoS (Quality of Service) - предпочтение одних передаваемых данных перед другими [16,17]. Например, голосовые данные в сетях IP-телефонии передаются с большим приоритетом, чем остальные данные.
Jitter (дрожание) — пакеты в сетях передачи данных могут быть получены клиентом не в том порядке, в каком были ему отправлены, так как для доставки пакетов могли использоваться разные маршруты с разными характеристиками скорости и удаленности. Для решения проблем подобного рода используется сглаживающий буфер - jitter buffers. Задачей этих буферов является предварительное накопление пакетов перед их дальнейшей передачей декодеру.
Packet Loss (потеря пакетов). Влияние потери пакетов, передаваемых в сетях передачи данных, на качество видео и речи определяется размером пакета и используемым способом кодирования данных. Для нормальной работы систем IP-телефонии допускается потеря 1% пакетов, иначе заметно ухудшение качества речи [18].
На качество оказания инфокоммуникационных услуг влияет структура сети и пропускная способность каналов связи. Кроме того, существенное влияние на качество оказания инфокоммуникационных услуг, особенно при большой загрузке сети, оказывает дисциплина обслуживания.
В мультисервисных сетях связи, когда пропускной способности канала недостаточно для обработки запросов всех пользователей, неизбежно возникновение очередей. При этом задержка при ожидании в очереди является основной составляющей суммарной задержки пакета. Что касается потерь пакетов, то, если отбросить искажения при передаче, переполнение очередей из-за перегрузок является единственным существенным источником потерь. Задержка и потеря пакетов являются важными показателями качества инфокоммуникационных услуг. Помимо увеличения ресурсов сети основным способом снижения задержки и потери пакетов в очередях является выбор дисциплины обслуживания.
Как уже говорилось выше, мультисервисные сети связи в качестве транспортной инфраструктуры используют сети передачи данных с коммутацией пакетов, функционирующие под управлением различных протоколов. Протокол IP (а также базирующиеся на нем транспортные протоколы TCP и UDP) обслуживают пакеты в очереди по принципу FIFO (первый пришел - первый ушел). При этом протоколом не гарантируется ни минимальная задержка для каждого пакета, ни одинаковая задержка для пакетов из одного потока. В случае большой загрузки сети возникает опасность потери пакетов из-за переполнения очередей маршрутизаторов [19,20].
Необходимо отметить два принципиально различных подхода к потере пакетов при их передаче по сети. При передаче данных, как правило, необходимо, чтобы все пакеты достигли адресата, только в этом случае получатель данных сможет их обработать. Например, при передаче архива искажение одного байта может привести к невозможности извлечь необходимые данные. Простейший способ минимизации потерь пакетов из очереди - увеличение ее размера. В то же время при передаче мультимедийной информации требуется снизить задержки пакетов (пусть даже путем отбрасывания некоторых из них), что может быть достигнуто уменьшением размера очереди. Различные протоколы используемые в сетях передачи данных по-разному учитывают эти особенности. Для передачи данных на транспортном уровне используется протокол TCP, ориентированный на предварительное установление соединения и повторную передачу пакетов при отсутствии подтверждения о получении. В случае потери пакетов протокол TCP снижает объем передаваемых данных, что приводит к минимизации потери пакетов в сетях, функционирующих исключительно под управлением протокола TCP. В противоположность протоколу TCP, протокол UDP не поддерживает гарантированную доставку пакетов и не проводит анализ потерь пакетов при передаче. Поэтому протокол UDP не снижает объем передаваемых данных даже в случае большого количества потерянных пакетов [21].
Предположим, что в очередь поступают пакеты одного TCP и одного UDP источника, при этом интенсивность поступления UDP-пакетов изменяется от нуля до уровня пропускной способности исходящего канала. Пока обслуживаются только пакеты данных, нагрузка, создаваемая TCP, определяется емкостью канала связи. По мере роста интенсивности UDP- трафика свободное место в очереди будет заниматься UDP-пакетами, и результатом конкуренции потоков станут потери пакетов. При этом потеря пакетов заставит TCP снижать нагрузку, в то время как UDP продолжит и далее отправлять большое количество пакетов. Если характеристики нагрузки не изменятся, пропускная способность TCP-соединения снизится до нуля.
Для предотвращения таких ситуаций используются различные механизмы, определяющие дисциплину обслуживания сети. Например, механизм RED [22] (Random Early Detection - случайное раннее обнаружение) регулирует размер очереди путем исключения из нее пакетов случайным образом, что позволяет избегать перегрузок и обрабатывать пульсирующий трафик. Алгоритм состоит из двух процедур - оценки среднего размера очереди и принятия решения о сбросе пакета. RED анализирует два параметра: минимальный и максимальный размер порога. Если размер очереди меньше, чем минимальный размер порога, то поступающие пакеты отбрасываться не будут. Если размер очереди превышает максимальный размер порога, то пакеты удаляются до постановки в очередь. В случае, если длина очереди окажется в пределах от минимального до максимального порога, пакеты будут отбрасываться с вероятностью, линейно изменяющейся от нуля до единицы, с увеличением длины очереди. Несмотря на простоту, RED позволяет эффективно бороться с перегрузками. Алгоритм был реализован во многих сетевых ОС и в аппаратных маршрутизаторах. Позднее предлагались и другие алгоритмы борьбы с перегрузками, например, алгоритм FRED (Flow RED) принимает решение об удалении пакетов на основании статистики обслуживания каждого потока.
Алгоритмы активного управления очередью позволяют эффективно бороться с перегрузками, но не решают проблем неадекватного распределения ресурсов между потоками. Этого можно добиться единственным способом - их изоляцией, т. е. организацией отдельной очереди для потоков на основании передаваемой информации. Такие дисциплины обслуживания очереди называются планирующими (scheduling).
Таким образом, дисциплина обслуживания требований в передаче данных в мультисервисных сетях связи служит для уменьшения задержек и потерь пакетов в очередях и обеспечения гарантированного качества обслуживания. Алгоритм обслуживания требований может быть достаточно сложным и учитывать историю обслуживания пакетов для каждого отдельного потока.
Концептуальная постановка задачи моделирования и оптимизации мультисервисных сетей связи
На уровне ядра сети. При известной структуре сети (месторасположении узлов), потребностях в передаче данных и ограничениях (возможно равных нулю или бесконечности) на емкость ребер ядра сети, заданных надежностных и стоимостных характеристиках стандартных каналов связи найти такие оптимальные емкости каналов передачи данных между узлами, чтобы: 1. выполнить требования в связи между узлами; 2. не превысить ограничение на емкость каналов связи между каждой парой узлов; 3. обеспечить минимальную стоимость ядра МСС; 4. обеспечить оптимальные (максимальные) значения показателей эффективности сети. При этом необходимо учитывать неоднородность требований к бесперебойности связи различных пар узлов. В некоторых узлах могут располагаться экстренные службы, пункты правительственной связи и другие объекты, к надежности связи которых обществом предъявляются повышенные требования. - На распределительном уровне сети. При известной структуре сети, потребностях в передаче данных и ограничениях на емкость ребер ядра сети найти такие оптимальные емкости ребер, приоритеты типов передаваемой информации, ограничения на количество одновременно транслируемых каналов, чтобы: 1. задержки при передаче информации в сети как можно меньше превышали допустимые значения. Необходимо учесть, что различные группы потребителей и операторов услуг, связанные с использованием МСС, предъявляют противоречивые требования к качеству передачи информации каждого типа; 2. количество отказов в обслуживании из-за превышения максимального количества эфирных каналов было минимально; 3. стоимость сети передачи данных была минимальной. Требование минимизации стоимости МСС, главным образом, предъявляется оператором сети. Косвенно стоимость сети важна и для всех остальных заинтересованных групп, так как она влияет на стоимость оказываемых сетью услуг.
Таким образом, приведенная концептуальная постановка задачи оптимизации МСС позволяет свести задачу оптимизации мультисервисной сети связи к последовательному решению двух задач. В случае модернизации существующей сети на первом этапе решается задача оптимизации распределительного уровня сети для каждой распределительной подсети задачи. Агрегированные потребности в связи для распределительных сетей служат исходными данными для решения задачи оптимизации магистрального уровня сети. В случае проектирования новой мультисервисной сети связи на основании усредненных потребностей в связи между распределительными сетями (микрорайонами, крупными бизнесцентрами, узлами приема телевизионного сигнала) решается задача оптимизации магистрального уровня сети. По мере развертывания распределительных сетей связи и присоединения их к ядру решаются задачи оптимизации распределительного уровня сети для каждой распределительной подсети.
Перейдем к математическому моделированию задачи оптимизации мультисервисной сети связи с учетом проведенной декомпозиции, а так же сделанных и обоснованных в данной главе допущений.
Быстрые изменения современных технологий связи приводят к необходимости разработки математических моделей, позволяющих быстро и качественно проводить анализ и оптимизацию имеющихся проектных решений, а также проектировать новые сети.
Обзор возможных методов математического моделирования сетей связи свидетельствует о том, что в настоящее время не существует универсальных методов решения задач моделирования и оптимизации сетей связи. Принятие решения о выборе конкретной модели сети возможно только с учетом всех особенностей конкретной прикладной задачи. В связи с этим целью диссертационной работы является построение математической модели мультисервисной сети связи, учитывающей различные критерии оптимальности сети и особенности проектирования сетей российскими операторами связи, а также нечетко формализованные требования потребителей услуг и операторов связи, предъявляемые к качеству функционирования сети. Модель должна быть реализована в виде программного комплекса, позволяющего управлять сетями связи, проверять их работоспособность при возможных неисправностях, оптимально настраивать конфигурацию существующих сетей. Исходя из цели, определены следующие задачи исследования: 1. Проведение и обоснование декомпозиции сети на структурные уровни, описание связи между уровнями мультисервисной сети связи. 2. Разработка и математическое описание критериев функционирования мультисервисной сети связи, учитывающих требования пользователей и оператора сети. 3. Построение математической модели магистрального уровня мультисервисной сети связи, учитывающей ее качественные и стоимостные характеристики, а также разработка численного алгоритма оптимизации мультисервисной сети связи с учетом построенных критериев и ограничений, заданных в нечеткой форме. 4. Построение модели распределительного уровня сети, учитывающей различные критерии оптимальности сети, относящиеся как к пользователям, так и к оператору сети связи. 5. Разработка алгоритма оптимизации распределительного уровня сети с учетом нечетких предпочтений различных социальных групп потребителей и оператора сети. 6. Разработка комплекса программ - инструмента оператора сети, позволяющего поддерживать управленческие решения, направленные на повышение эффективности мультисервисных сетей связи.
Обобщенный критерий оптимальности распределительного уровня мультисервисной сети связи
Проведенное в данной главе исследование позволяет сделать выводы о том, что: 1. Задача оптимизации распределительного уровня сети может быть решена при помощи предложенной методики, учитывающей интересы оператора и пользователей сети. 2. Анализ результатов имитационного моделирования показал, что модель распределительного уровня сети позволят предсказывать возможные сбои в работе распределительного уровня сети передачи данных при различных сочетаниях потребностей пользователей и параметров сети. Получаемые результаты согласуются с теоретическими расчетами, редактор распределительных сетей позволяет предсказывать известные эффекты, возникающие в системах массового обслуживания. опоздлвших. 3. Построенную модель можно использовать как для прогнозирования показателей качества функционирования сети связи при изменении параметров услуг, подключении новых пользователей к сети, изменениях тарифной политики, влияющих на количество и порядок потребления услуг пользователями сети, так и для поиска оптимальной конфигурации вновь создаваемой сети связи. В результате проведенных исследований можно сделать следующие выводы: 1. Построена многоуровневая структурная схема МСС. Обосновано, что современная МСС представляет собой социально- техническую систему. Описаны конфликтные интересы различных групп пользователей сети. Показано, что эти интересы имеют ярко выраженную нечеткую природу. 2. Разработаны и математически корректно описаны технические критерии функционирования сети передачи данных для каждого из уровней сети. На уровне ядра сети определяющее значение играет способность сети выполнять свои функции при выходе из строя её элементов, а на распределительном уровне - качество передачи данных с учетом нечетких предпочтений потребителей услуг. 3. На основе теории графов построена математическая модель магистрального уровня сети передачи данных, учитывающая ее качественные и стоимостные характеристики, а также разработан численный алгоритм оптимизации сети передачи данных с учетом построенных критериев и ограничений, заданных в нечеткой форме. Произведена проверка адекватности модели путем решения ряда тестовых примеров. 4. На основе имитационного подхода построена математическая модель распределительного уровня сети в виде системы массового обслуживания, учитывающая различные требования к сети передачи данных со стороны потребителей и операторов услуг, а так же оператора сети. Модель была реализована в виде программного комплекса. Достоверность разработанной модели проверена путем сравнения численных результатов имитационного моделирования с аналитическими результатами для случая одного канала. 5. Предложена оригинальная методика учета конфликтных нечетко формализованных интересов различных групп пользователей сети. Показано, что все пользователи сети по интересам могут быть разбиты на группы. Для учета требований к качеству функционирования сети со стороны каждой группы пользователей построены нечеткие критерии. Учет интересов всех социальных групп производился с помощью обобщенного критерия в виде нечеткого множества с нечетким носителем. Сравнение вариантов построения сети с учетом нечетких предпочтений различных социальных групп осуществлялось с использованием специально разработанных индексов ранжирования 6. Анализ результатов имитационного моделирования показал, что модель позволяет предсказывать возможные сбои в работе распределительного уровня сети передачи данных при различных сочетаниях потребностей пользователей и параметров сети. Таким образом, модель можно использовать как для прогнозирования изменения показателей качества функционирования сети связи при изменении параметров услуг, подключении новых пользователей к сети, изменениях тарифной политики, влияющих на количество и порядок потребления услуг пользователями сети, так и для поиска оптимальной конфигурации вновь создаваемой сети связи. 7. Создан комплекс программ - инструмент оператора сети, позволяющий поддерживать управленческие решения, направленные на повышение эффективности сети передачи данных. Разработанный программный комплекс был внедрен в СИЦ Пермского филиала ОАО «Уралсвязьинформ» и получил положительный отзыв о возможности дальнейшего применения (см. Приложение 1).
Идентификация модели оптимизации магистрального уровня мультисервисной сети связи
Следовательно, при сделанных допущениях вариант У2лучше варианта Уъ, который, в свою очередь, лучше варианта У1 . Поэтому оператору сети выгодно выбирать вариант . С учетом весов критериев оптимальности, вариант №2 имеет наибольшую среднюю степень удовлетворенности пользователей качеством функционирования сети (0,56 для домашних пользователей и 0,44 для корпоративных). Поэтому, при нулевом уровне некомпенсируемости критериев оптимальным оказался вариант №2. В то же время в приведенном примере трудно предположить нулевой уровень некомпенсируемости критериев. Например, плохое качество услуг Интернет предоставляемых сетыо не может компенсироваться отличным качеством телефонии и, наоборот, плохое качество телефонии не может компенсироваться отличным доступом в Интернет. При полной некомпенсируемости критериев (а=1) лучшим окажется вариант №1. График зависимости значений обобщенного критерия оптимальности от уровня некомпенсируемости критериев изображен на рис. 23. Из рисунка 23 видно, что при а 0.336 вариант построения сети №1 становится предпочтительнее второго варианта. Это связанно с тем, что в первом варианте разброс значений критериев оптимальности существенно меньше, чем в других вариантах (см. таблицу 9). При выборе варианта №2 практически игнорируется качество услуги подключения к Интернет, что при высоком уровне некомпенсируемости критериев недопустимо.
Для моделирования распределительной сети был разработан программный комплекс (редактор распределительных сетей), позволяющий проводить прямые вычислительные эксперименты, анализировать параметры и оптимизировать сети передачи данных.
Процедура моделирования распределительного уровня сети включает следующие этапы: 1. Задание структуры сети связи, указание заданных характеристик узлов и ребер сети. 2. Задание информации об услугах, предоставляемых сетыо, и их характеристиках. 3. Задание информации о пользователях, подключенных к узлам сети, и их характеристиках. 4. Построение обобщенного критерия функционирования сети путем задания нечеткой свертки критериев пользователей и оператора сети. 5. Выполнение процедуры поиска оптимальных параметров распределительного уровня сети путем перебора вариантов построения сети и определения параметров качества её функционирования методом имитационного моделирования. 6. Вывод результатов решения задачи. Наиболее требовательным к ресурсам является пятый этап процедуры моделирования распределительного уровня сети. На остальных этапах необходимо обеспечить удобный пользовательский интерфейс. Для разработки программного комплекса моделирования распределительного уровня МСС была выбрана платформа Borland Delphi 7. Этот программный продукт был наиболее современным на момент начала разработки программного комплекса из линейки продуктов Borland Delphi, кроме того, использование этой среды разработки позволило применить наработки, полученные при создании программного комплекса моделирования магистрального уровня сети. Выбранная платформа обладает всеми теми преимуществами и недостатками, что и Borland Delphi 4. В соответствии с ранее приведенными этапами моделирования распределительного уровня сети необходимо выделить следующие элементы программного комплекса: 1. Пользовательский интерфейс для задания структуры сети. 2. Пользовательский интерфейс для задания параметров услуг оказываемых сетью и параметров пользователей МСС. 3. Пользовательский интерфейс для задания параметров нечеткого обобщенного иерархического критерия. 4. Программная реализация имитационного алгоритма. 5. Программная реализация алгоритма выбора лучшего решения. Все элементы программной системы были реализованы в виде двух программных модулей. Первый модуль предназначен для имитационного моделирования сетей связи и составления набора возможных решений. Второй модуль предназначен для выбора лучшего варианта из нескольких возможных по нечеткому иерархическому критерию и не содержит специфики, связанной с сетями связи. Этот программный модуль может использоваться для выбора лучшего варианта в любом пространстве параметров, для различных социально-технических систем сложной структуры[112,113]. На основе требуемых программных функций и выбранной структуры программной системы был реализован программный продукт «Комплекс для моделирования и анализа распределительного уровня МСС», структурная схема которого приведена на рис. 24. Разработанный програмный комплекс решает задачу оптимального проектирования распределительного уровня мультисервисной сети связи. Имитационная модель и методика построения нечеткого обобщенного иерархического критерия оптимальности приведены в главе 3. Программный комплекс имеет графический пользовательский интерфейс, позволяет решать задачу оптимального проектирования распределительного уровня МСС, предоставляет возможность сохранения исходных данных и результатов решения в формате XML. Модуль выбора лучшего варианта Модуль экспорта- импорта данных Модель нечеткого иерархического критерия Модель вариантов пешения Программа предназначена для использования на IBM — совместимых ЭВМ с операционной системой Windows 95 и более поздних версий. Объем используемой памяти зависит от размера решаемой задачи и используемого метода оптимизации. При запуске программного комплекса имитационного моделирования МСС открывается графическое окно, предназначенное для вывода информации о сети связи в графическом виде. Изображение этого окна приведено на рисунке рис. 25. Предусмотрена возможность изменения масштаба и перемещения изображения. Узлы сети изображаются в виде окружностей, в подписи к узлам указывается их наименование. Ребра сети изображаются в виде прямых линий, связывающих узлы. Главное окно имеет два режима. В режиме «сеть» выводится информация о сети и параметры текущего узла или ребра сети. В этом режиме можно указать тип и количество пользователей, подключенных к узлу сети. В режиме «вывод информации» отображается информация о параметрах информационной сети и ходе процесса моделирования. В этом режиме также предусмотрена возможность сохранения результатов имитационного моделирования для дальнейшего анализа.
