Модели и методы спецификации и тестирования телекоммуникационных протоколов
На правах рукописи
Гойхман Вадим Юрьевич МОДЕЛИ И МЕТОДЫ СПЕЦИФИКАЦИИ И ТЕСТИРОВАНИЯ ТЕЛЕКОММУНИКАЦИОННЫХ ПРОТОКОЛОВ 05.12.13 – Системы, сети и устройства телекоммуникаций
Автореферат диссертации на соискание ученой степени кандидата технических наук
Санкт-Петербург 2011
Работа выполнена в Санкт-Петербургском Государственном университете телекоммуникаций (СПбГУТ) им. проф. М.А. Бонч-Бруевича на кафедре систем коммутации и распределения информации.
Научный руководитель доктор технических наук, профессор Б.С. Гольдштейн Научный консультант доктор технических наук, профессор Я.С. Дымарский
Официальные оппоненты: заслуженный деятель науки, доктор технических наук, профессор А.Н. Терехов кандидат технических наук, доцент Л.В. Юрасова Ведущая организация ООО «НТЦ Протей»
Защита состоится «_» 2011 г. в часов на заседании диссертационного совета Д 219.004.02 при Санкт-Петербургском Государственном Университете Телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191186, Санкт-Петербург, наб. р. Мойки, 61.
С диссертацией можно ознакомиться в библиотеке университета.
Автореферат разослан «_» 2011 г.
Ученый секретарь диссертационного совета, кандидат технических наук, доцент В.Х. Харитонов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность исследований. Телекоммуникационные протоколы, как и методы их специфицирования и тестирования в ССОП (сетях связи общего пользования), эволюционировали вместе с развитием телекоммуникационной техники. На современном этапе, характеризующемся конвергенцией сетей с разными технологиями передачи информации и коммутации, стали использоваться новые телекоммуникационные протоколы, базирующиеся на принципах коммутации каналов в сетях TDM (Time Division Multiplexing) и в сетях коммутации пакетов NGN (Next Generation Network) – в сетях следующего поколения.
Значительное усложнение логики и увеличение количества технологий, сетей и услуг требует соответствующего развития методов спецификации и тестирования телекоммуникационных протоколов, которое пока заметно отстает от развития самих этих протоколов, слабо используя современные идеологические и математические средства, такие как язык спецификаций и описания SDL (Specification and Description Language).
В силу сказанного представляются актуальными задачи анализа и формализации SDL спецификаций, минимизации числа значимых SDL-состояний, а также расчета вероятностно-временных характеристик (ВВХ) сертификационных испытаний этих протоколов и оптимизации на этой базе необходимого объема таких испытаний.
Состояние вопроса. Начало исследований в этом направлении совпало по времени с появлением языка SDL и поколения систем коммутации с программным управлением.
В рекомендациях Международного союза электросвязи (МСЭ) серии Z и в документах других стандартизующих организаций рассмотрены языки – методы спецификации и описания инфокоммуникационных протоколов, – но они ориентированы только на инженерное применение и не позволяют математически рассчитать ВВХ и статистическую достоверность результатов тестирования. Научные основания для такого расчта содержатся в довольно многочисленных работах по математической статистике, а также в исследованиях формальных спецификаций С.С. Бернштейна, Г.Л. Ионина, Б.
Лискова и Д. Гатэга, Ч. Хоара и др.
В ряде работ профессоров А.Н. Терехова, Б.С. Гольдштейна, Я.С. Дымарского, М.А.
Шнепса-Шнеппе и некоторых других авторов исследованы вопросы спецификаций программного обеспечения телекоммуникационных систем, но эти исследования не распространялись на минимизацию SDL-спецификаций и статистические оценки тестирования протоколов, и в них не рассматривались математические модели процесса сертификационных испытаний.
Цель и задачи исследования. Цель диссертации состоит в создании формализованной модели SDL-спецификаций телекоммуникационного протокола, допускающей выявление и минимизацию числа логически значимых состояний SDL спецификации, в разработке стратегии этой минимизации, а также в получении формул для расчета статистических характеристик тестирования таких минимизированных формализованных протокольных спецификаций и разработке алгоритма проведения испытаний на основе промежуточных статистически достоверных оценок, получаемых в процессе испытаний. Эта цель определила необходимость решения следующих научных задач:
сформулировать принципы и построить модель эффективной SDL-спецификации телекоммуникационного протокола;
разработать механизмы и алгоритмы нормализации SDL-спецификаций, т.е.
минимизации числа логически значимых состояний SDL-спецификации, исключив несущественные и тупиковые ветви;
построить математическую модель тестирования SDL-спецификаций;
рассчитать статистические оценки процесса тестирования SDL-спецификаций телекоммуникационного протокола;
применить полученные результаты к телекоммуникационным протоколам TDM- и NGN-сетей.
Методы исследования. Основным математическим аппаратом в работе являются математическая статистика и теория вероятностей, а также теория алгоритмов и математическая логика, в основном, при формировании и преобразовании SDL спецификаций инфокоммуникационных протоколов.
Научная новизна работы состоит в предмете исследования – в спецификациях протоколов сетей NGN и TDM, в разработке математической модели процесса тестирования SDL-спецификаций, в нахождении путей получения достоверных оценок результатов тестирования, в разработке алгоритма оптимизации самого процесса тестирования.
Личный вклад. Все важнейшие результаты, составляющие содержание диссертации, получены автором лично. В работах, изданных в соавторстве, автору принадлежат математические модели и теоретические результаты.
Практическая ценность результатов работы. Теоретические исследования, выполненные в работе, доведены до инженерных решений. Основные результаты работы использованы в контрактных работах по сертификации с целым рядом отечественных и зарубежных телекоммуникационных компаний, а также в НТЦ Протей при заводских испытаниях оборудования NGN и в Санкт-Петербургском Государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича при организации учебного процесса.
Апробация работы. Основные результаты диссертации докладывались, обсуждались и были одобрены на международных и общероссийских конференциях IEEE, на конференциях НТОРЭС им. А.С. Попова, на ежегодных научно-технических конференциях профессорско-преподавательского состава, научных сотрудников и аспирантов СПбГУТ с 2002 по 2011 годы.
Публикации. По материалам диссертации в научно-технических журналах и в трудах международных и всероссийских научных конференций опубликовано 24 печатные работы, включая четыре учебных пособия с грифом УМО.
Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения и списка литературы. Объем пояснительной записки 157 страниц, иллюстраций, список литературы насчитывает 58 наименований. В качестве приложений приведены громоздкие выкладки, которые доказывают справедливость ряда утверждений, составляющих основу последних двух глав диссертационной работы, а также акты о внедрении результатов диссертации.
Основные положения, выносимые на защиту:
формализованная модель SDL-спецификации протокола, позволяющая преобразовывать и минимизировать число ее состояний;
математическая модель процесса тестирования реализации протокольных спецификаций, учитывающая статистические оценки числа испытаний;
алгоритм процесса тестирования инфокоммуникационных протоколов.
СОДЕРЖАНИЕ ПОЯСНИТЕЛЬНОЙ ЗАПИСКИ Во введении обосновывается актуальность темы, рассматривается состояние исследуемой проблемы, формулируется цель работы, перечисляются основные научные результаты диссертации и кратко излагается е содержание. Приводятся основные положения, выносимые на защиту.
В первой главе характеризуются задачи спецификации интерфейсов телекоммуникационных сетей. Здесь рассматривается эволюция систем сигнализации ТфОП/ISDN в процессе перехода к сети нового поколения NGN.
Эволюцию телекоммуникационных протоколов можно изобразить в виде дерева, как это показано на рис. 1.
Характеристики каждого поколения сигнальных протоколов связаны с существовавшей на тот период архитектурой коммутационного оборудования, межстанционной инфраструктурой, функциональными возможностями терминалов, а также принципами построения сети. Исходная точка эволюции задана моментом появления автоматических телефонных станций (АТС).
Скорость, Мбит/с RADIUS SIP 1000 SIGTRAN H.248/MEGACO SIP-T BICC Diameter H. RADIUS SIP MGCP H. ОКС QSIG 2, DSS 2ВСК 2600 Гц 1,024 2ВСК универсальный 1ВСК(Норка) Батарейный способ 0, Индуктивный способ Время, гг 1950 1960 1970 1980 1990 2000 Рис. 1. Эволюция телекоммуникационных протоколов ЕСЭ РФ Декадно-шаговые АТС устанавливали соединение под непосредственным управлением абонента, а связывались друг с другом физическими соединительными линиями, и сигнальную информацию можно было передавать только по разговорному тракту (сперва постоянным током, а на следующем этапе эволюции – при разделении на АТС функций сигнализации и коммутации – тональными частотами).
С изобретением многочастотной сигнализации в телефонии мало что изменилось, однако произошло одно важное событие: разделение функций коммутации и функций управления ею между разными группами оборудования АТС. Спустя десять лет, в связи с бурным развитием вычислительной техники, с переходом на цифровую технику передачи и коммутации и с появлением систем общеканальной сигнализации (ОКС №7 и DSS-1), группу средств управления коммутацией составили распределенные микропроцессорные комплексы с программным управлением, выполняющие функции далеко не только передачи, приема и обработки информации о номерах абонентов, но и многое другое, в частности, участие в решении задач тестирования оборудования. Все это вело к созданию новых систем сигнализации и внесло в телефонию слово «протокол».
Во второй половине 90-х годов интенсивное развитие получили IP-сети, превратившиеся в экономичную среду передачи данных. Большое распространение получил стек протоколов TCP/IP, используемый как в сети Интернет, так и в локальных сетях. Это стало предпосылкой к созданию сети следующего поколения NGN, нацеленной на поддержание транспортировки информации всех типов и облегчающей внедрение новейших услуг. Появилась необходимость создания новых протоколов сигнализации, которые соответствовали бы принципам NGN: работе поверх протоколов TCP/IP (в, том числе, для речевой связи), простоте, надежности, совместимости с сигнализацией разных типов и поддержке мобильности абонентов.
Объединение сетей телефонной связи, передачи данных и телевизионных привело к увеличению объема и сложности общих технических средств этих сетей, что усложнило эксплуатационную поддержку, в частности, протоколов настолько, что сделало этот вопрос критическим. Область перехода на новый уровень технологий и скоростей указывает на рис. 1 пунктирная линия. Стало ясно, что нужны формализованные методы спецификации протоколов, облегчающие тестирование не только их реализаций разработчиком и покупателем, но и самих спецификаций.
В первой главе дается основательная постановка этих задач (подробно они решаются в следующих главах), критически рассматривается, каково состояние известных исследований в этих направлениях, и ставится цель диссертации.
Во второй главе развиваются положения главы 1, предлагается модель тестируемости SDL-спецификаций телекоммуникационных протоколов. Здесь излагаются принципы модели, основанные на представлении спецификации как ряда связанных друг с другом расширенных конечных автоматов EFSM, и исследован ряд примеров использования такого ее представления. Этими примерами явились: задачи определения эффективности спецификации, вопросы тестируемости SDL-спецификаций, алгоритм и процедура создания нормальной формы EFSM (NF-EFSM) на базе таких спецификаций, доказательство универсальности процедуры преобразования этой формы в развитый или частично развитый EFSM. Под эффективностью спецификации понимается некое соотношение между функциональными характеристиками протокола и затратами труда на тестирование программно-аппаратных средств реализации интерфейса, который поддерживает этот протокол.
С точки зрения тестирования конечный автомат представляет собой набор ветвей, а задача тестирования заключается в проверке каждой из ветвей. Любая ветвь состоит из последовательных переходов, каждый из которых предварительно определен. Как следствие этого, ветвь p определена условием ветви c(p): входящая последовательность переходов x обязана удовлетворять условию «x должен привести к p». Таким образом, создавая набор тестов для ветви p, необходимо найти входящие последовательности, удовлетворяющие условию c(p).
Если ветвь p является невыполнимой, для нее должно соблюдаться условие отсутствия любых входящих последовательностей переходов, удовлетворяющих условию c(p). Такая ситуация может возникнуть после нескольких переходов в случае, если предварительные условия этих переходов находятся в противоречии.
Таким образом, проблема тестирования SDL-спецификаций часто усложняется наличием в представляющих их EFSM невыполнимых ветвей. Во второй главе представлен метод преобразования спецификаций, позволяющий уменьшить количество невыполнимых ветвей. Метод состоит из двух частей: а) построение на базе спецификаций расширенного конечного автомата нормальной формы (NF-EFSM), и б) развитие этого NF EFSM до уровня, удовлетворяющего тестированию (PE-EFSM). Создание PE-EFSM начинается с выявления областей состояний, которые содержат, по крайней мере, два условных перехода и разделения этих областей с указанием предусловий. Разделение областей приводит к необходимости перестроения переходов, связанных с разделенными состояниями, и определения типов новых переходов;
если новому переходу невозможно задать тип, от этого перехода отказываются. В случае разбиения исходного состояния требуется определить, какое из полученных состояний теперь является исходным, а затем удалить все состояния, которые не могут быть достигнуты из исходного. Процесс развития завершается в случае выполнения одного из двух условий: «полное завершение» – нет никаких условных переходов;
«обусловленное завершение» – все оставшиеся условные переходы в представленном PE-EFSM являются условными переходами, обладающими хорошо структурированными петлями в исходном NF-EFSM. Если ни одно из условий не выполнено, необходимо провести новую итерацию расширения.
Предлагаемая новая методика базируется на построенной в третьей главе математической модели. С помощью этой модели рассчитываются оценки необходимого для завершения испытаний числа N тестов взаимодействия телекоммуникационных протоколов, формализованных по методам главы 2.
Третья глава диссертации посвящена разработке статистических моделей испытаний телекоммуникационных протоколов.
Успешная интеграция нового телекоммуникационного оборудования в существующую ЕСЭ РФ зависит от того, насколько верно испытательному центру удалось решить вопросы тестирования. Важно не только не допустить к использованию сетевые элементы, не совместимые с ЕСЭ РФ, но и не довести до неприемлемо высокой величины стоимость испытаний. Для абсолютно достоверного тестирования необходимо проверить порядка N х М пар SDL-автоматов с применением к каждому из них тестов взаимодействия. Очевидные ограничения – неоправданно большое число испытаний, необходимость всякий раз получать доступ к телекоммуникационному оборудованию каждого типа и др. – становятся причиной того, что возникает потребность искать решения, которые позволили бы ограничить число проводимых тестов, скажем, уровнем N + М. Именно поиску подходов к уменьшению числа необходимых тестов посвящена глава 2 диссертации.
На рис. 2 упрощенно представлен фрагмент сети NGN с выделением основных сетевых элементов, а также связывающие разные сетевые элементы NGN телекоммуникационные протоколы, составляющие в совокупности объект исследования диссертационной работы.
Именно для реализации этих протоколов в составе программного обеспечения представленных на рис. 2 сетевых элементов проведены основные исследования глав 2 и 3.
Рис. 2. Распределенный узел NGN в составе серверов приложений (Application Server), медиасерверов (Media Server), контроллера шлюзов (Media Gateway Controller), шлюза доступа (Access Gateway), сигнального (Signaling Gateway) и транспортного (Trunking Gateway) шлюзов Основная часть третьей главы посвящена математической модели испытаний.
Сначала исследуется проблематика статистических оценок при генерации тестовых последовательностей на базе теории главы 2, а в следующих разделах выставляются требования к параметрам модели, задаваемым оператором. Обычная практика испытаний элементов телекоммуникационной сети – это проведение тестов по «Типовым методикам сертификационных испытаний». Вопросы оценки качества испытуемого сетевого элемента определяются следующими правилами из этих методик: проверка считается успешной, если потери по каждому виду связи не превышают 0,001;
результаты проверки считаются положительными, если в течение непрерывного трехсуточного периода произведено не менее 1000000 контрольных вызовов (на 10000 номеров узла коммутации) с коэффициентом ошибок не более 0,1% при соединениях в пределах одной системы коммутации и не более 0,2% при соединениях, проходящих через две независимые системы.
При таких правилах методика обработки результатов тестирования весьма проста и не требует громоздкого математического аппарата. Недостатки такого подхода очевидны:
фиксированный и довольно значительный объем испытаний;
отсутствие какой бы то ни было обратной связи между процессом и объектом испытаний;
отсутствие прямой связи между наблюдаемой частотой возникновения потерь вызовов и достоверностью реализации;
использование для принятия решения незначительной части информации, содержащейся в результатах испытаний.
Задачей третьей главы является разработка математической модели и соответствующих методов совершенствования тестирования протоколов в процессе испытаний. Речь идет о получении точных доверительных оценок для вероятности потерь вызовов (сессий) P из-за нарушений сетевого взаимодействия (и происходящих из-за этих нарушений отказов в предоставлении телекоммуникационных услуг). Эта модель должна позволить без ущерба для качества испытаний и даже с увеличением достоверности значительно уменьшить время тестирования сетевых элементов и при этом получить не только достоверные, но и достаточно точные (с заданной близостью к истинному значению P) его оценки p.
Процесс оценивания состоит из двух этапов. На первом этапе происходит отбор объектов, удовлетворяющих нормативным требованиям. Испытания проводятся до тех пор, пока верхняя граница доверительного интервала pВ для неизвестного параметра потерь n не станет меньше максимально допустимой вероятности P0 (pВ P0 – условие 1), или пока количество испытаний N не достигнет максимального значения (N = Nmax – условие 2). Испытания ведутся сериями одинаковой длины N0 до тех пор, пока не будет получена первая «ненулевая» серия (n00). Затем проводится оценка pВ, если pВ P0, то испытания продолжаются, при этом количество потерь будет последовательно увеличиваться до n+K, где K=1,2,…, пока не выполнится одно из двух вышеуказанных условий. В случае, если первый этап завершился выполнением условия 2, необходимо выполнение следующего этапа на котором для отобранных объектов должна быть определена, с заданной точностью, вероятность потерь. Обобщенная схема проведения испытаний представлена на рис. 5.
Рис. 5. Блок-схема методики оценки качества элемента телекоммуникационной сети Оба этапа рассматриваются в четвертой главе, здесь же выставляются требования к варьируемым параметрам модели, а именно к методу приближения, коэффициенту доверия и точности оценки потерь. Рассмотрим более детально каждый из них.
Строгое решение задачи нахождения нижней и верхней доверительных границ для вероятности P биномиального распределения довольно сложно и решается, как правило, с использованием соответствующих таблиц, однако, в нашем случае, когда N лежит в диапазоне (1000–1000000), а коэффициент доверия (0,90–0,995) воспользоваться данными этих таблиц не представляется возможным.
В связи с этим в качестве интервальной оценки были использованы точные доверительные интервалы с заданным коэффициентом доверия (0,90, 0,95, 0,975, 0,99, 0.995), вычисляемые по методу Клоппера-Пирсона с помощью функции binofit пакета прикладных программ Matlab. Как известно, в случае если объем выборки N «достаточно велик» можно говорить об асимптотической близости нормального распределения к биномиальному (закон больших чисел). Речь идет о нескольких сотнях или тысячах генерируемых вызовов (сессий), что в практике проведения сертификационных испытаний систем обычно выполняется.
Для решения прикладных задач необходимо выбрать приближенный метод, основанный на аппроксимации биномиального распределения нормальным распределением. Сравнивались простой асимптотический метод Вальда, асимптотический метод с коррекцией непрерывности, метод Вильсона, метод подсчета, включающий коррекцию непрерывности. Вычисления проводились для четырех групп значений количества потерь: n=0–3, при N=500, 1000, 2000, 3000. Сравнение на рис. 5 показало, что минимальная относительная погрешность достигается методом Вильсона, при коэффициенте доверия =0,95 и n0:
(n 0,5b2 b 0, 25b2 n(1 n / N )) / N (1 b2 / N ), (1) p1, p где b Определив метод приближения и уровень доверия, необходимо задать точность оценки результатов испытаний. Упростим (1), исходя их того, что N значительно больше n и b, p1, p2 (n 0,5b2 b 0, 25b2 n ) / N (2) и проведем расчет относительного отклонения оценки p от верхней pВ p2 N и нижней границы pН p1 N доверительного интервала, а также от интервальной оценки для неизвестного параметра n:
rВ b( n 0, 25b2 0,5b) / n, rН b( n 0, 25b2 0,5b) / n, rИ b n 0, 25b2 / n. (3) Из (3) выведем соотношения для прогноза числа потерь n, необходимых для оценки P с точностью r, а затем найдем усредненные значения верхней, нижней и интервальной оценки n:
r2 r2 r b2 b2 b2 1 r 1r 1r dr. (4) nВ dr, nН dr, nИ r1 ) r 1 r 2 r1 ) r 1 r 2 r (r2 (r2 2(r2 r1 ) r Рис. 6. Зависимость погрешности аппроксимации биномиального распределения от уровня доверия, для четырех методов, при n=3, N= Зададим уровень доверия =0,975 (b=1,96), проведем при варьируемой точности r [0,01 (0,01) 0,1;
0,1 (0, 05) 0,5;
0,5 (0,1) 0,8] расчеты числа потерь n, по результатам расчета сузим диапазон r и проведем повторные расчеты. Расчет средних значений в более узком диапазоне подтвердил целесообразность выбора диапазона усреднения [0,2;
0,3] как по соображениям минимизации значения nИ, так и одновременному удержанию приемлемого значения точности r.
В третьей главе задан двухэтапный алгоритм проведения испытаний, в качестве метода приближения выбран метод Вильсона, определен коэффициент доверия =0,975 и точность оценки вероятности потери вызова r=(20–30)%.
Четвертая глава в известной степени продолжает третью, предлагая модели определения вероятностей потерь для отобранных объектов с заданной точностью и уровнем доверия. По заданному в третье главе алгоритму в два этапа статистическими методами осуществляется анализ процесса тестирования и затем проводится расчет прогнозных значений испытаний. Остановимся более подробно на первом этапе.
Первый подэтап. Расчет количества испытаний до первой ошибки Каждый тест представляет собой статистический эксперимент, в котором реализуется схема Бернулли. Предполагаем, что результаты экспериментов независимы друг от друга.
В таком случае случайная величина X, представляющая собой полное число потерь в N испытаниях подчиняется биномиальному распределению P( X ) PN0 (n0 ) CN00 pn0 (1 p)N0 n0, n0 0,1, 2,..., N0.
n (5) Из уравнения следует, что вероятность того, что в серии из N0 испытаний не будет потерь PN0 (0) q N0, а хотя бы одна потеря (успех) – P 1 q N. (6) При больших N0 выражение (6) можно представить так:
N0 p (7) P1e и трактовать как определение вероятности реализации результативной (ненулевой) серии.
Расчет математического ожидания количества испытаний до первой ошибки Случайная величина X, представляющая собой число серий до первой результативной серии, подчиняется геометрическому распределению, для которого математическое ожидание:
(8) MX q / p.
В таком случае математическое ожидание числа серий, включая первую результативную, будет:
(9) MX q / p 1 1/ p, а математическое ожидание суммарного числа испытаний NI1 в сериях до первой результативной (включительно):
N I 1 N 0 / p N 0 /(1 e N p ). (10) Расчет гарантированного количества испытаний до первой ошибки Проведем подобные расчеты для заданного уровня гарантии PГ реализации результативной серии. Обозначим как xГ количество экспериментов, которые необходимо для этого осуществить.
Опираясь на (10), получаем гарантированное суммарное количество испытаний NI1Г до первой ошибки:
ln(1 PГ ) / PГ p, если xГ / N0 1, N I 1Г (11) N0, если xГ / N0 1.
N I 1Г Зададим уровень гарантии реализации результативной серии PГ =0,85, используем значения вероятность потери p0, как p01 =10–4, p03 =3·10–4, p05 =5·10–4, p07 =7·10–4, p09 =9·10– и проведем расчеты для варьируемой длины серии испытаний N0 (500, 1000, 2000, 3000, 5000, 10000).
Рассмотрим полученные результаты расчетов с точки зрения организации процесса тестирования. При тестировании телекоммуникационного оборудования организация серий испытаний представляется более сложной задачей, чем проведение большого количества тестов в одной серии. В связи с этим целесообразно выбрать длину серии испытаний N0=5000 или N0=10000. Суммарное количество испытаний будет составлять N=mN0, где m – математическое ожидание количества серий.
Второй подэтап. Оценивание количества испытаний до K-й ошибки По результатам первого подэтапа получаем значения количества потерь n0 в NI испытаниях, где NI1=mN0, но в отличие от теоретических расчетов, m здесь имеет смысл не математического ожидания количества серий, а конкретного результата испытаний, что позволяет говорить об оценке максимального правдоподобия (частота ошибок):
(12) pI 1 n0 / N I 1.
Точечное оценивание числа испытаний до K-й ошибки Опираясь на (9), запишем математическое ожидание числа испытаний до K-ой ошибки включительно:
(13) MX K / p.
Воспользуемся (12) и найдем оценку математического ожидания количества испытаний, которые надо провести до K-й ошибки включительно:
(14) MX KNI 1 / n0.
Случайная величина X, представляющая собой число испытаний до K-й ошибки, подчиняется отрицательному биномиальному распределению, для которого математическое ожидание и дисперсия определяются как:
(15) MX Kq / p, DX Kq / p 2, (16) 0, N Г 0,1, 2,..., K 1, а функция распределения как F ( X (17) NГ ) F ( ), N Г K, 0,1, 2,..., где F ( ) с высокой точностью аппроксимируется нормальным законом с математическим N I ожиданием (15) и дисперсией (16), тогда N Г (18) K (b K K), n где K K (1 n0 / N I 1 ) Интервальное оценивание количества испытаний до K-й ошибки Воспользуемся (1) и построим доверительный интервал для ранее определенных границ pН=p1N;
pВ=p2N. В таком случае оценка математического ожидания числа испытаний до первой ошибки включительно, усредненная по всевозможным значениям (уровня доверия) параметра b:
2n0 1 (19) MX NI1 NI1, 2n0 2 2n0 n 2n0 а оценка P: (20) p.
N I 1 (2n0 1) Расчет количества потерь K на втором подэтапе Количество ошибок после n0 можно найти, решая неравенство pB n (21) N P0, K обозначим x n0 K, тогда p x/ N. (22) Воспользуемся приближением Вильсона (1):
b2 (0,5 P0 ) b 0, 25b2 (23) x(1 p) x( P0 / p 1).
Введем (24) a P0 / p, тем самым получаем параметр, представляющий собой отношение нормативной величины вероятности к оценке вероятности. Анализ величины а позволяет установить наличие или отсутствие решения для K, из (23) видно, что должно выполняться условие a1.
b Учитывая малость P0, найдем приближенное значение x: х a. (25) a b Тогда (26) K a n0.
a Таким образом, подставив в (24) точечную (12) и интервальную (20) оценки потерь и рассчитав (26), найдем точечную K и интервальную K оценки количества потерянных вызовов на втором подэтапе.
Учитывая, что на первом подэтапе уже провели NI1 испытаний, воспользовавшись (14) и (24), находим суммарное число испытаний, в процессе которых будет x n0 K ошибок:
(27) N I ax / P0.
Воспользовавшись (14), находим гарантированное суммарное количество испытаний N I до K-ой ошибки N I (28) N I1 K (b K K) Г n Численные расчеты значений второго подэтапа Для выявления характера влияния разных параметров на основные характеристики, в том числе на продолжительность испытаний, выполнены расчеты значений оценки математического ожидания и гарантированной оценки суммарного количества испытаний N I и N I Г для двух, рекомендованных по результатам исследования первого подэтапа, значений серий (5000 и 10000). Уровень доверия варьировался от 0,80 до 0,98.
Перебирались все возможные значения n0, но так, чтобы выполнялось условие a1.
Расчеты проводились как для точечной, так и для интервальной оценки ( N и N ). При расчете соблюдалась последовательность действий, предложенная ранее: – по данным количества испытаний и потерь давалась оценка P;
при заданной вероятности потери P0 =10 –3 рассчитывался коэффициент a;
для выбранного уровня доверия проводился расчет x, K, K’;
в случае получения K0 вычисления далее не проводились, и N I устанавливался равным N 0 (условие рВP0 оказывается выполненным уже на одном из испытаний первоначальной серии);
на основе полученных данных вычислялись значения N I, N I Г и N I, N I Г. Далее для каждой серии проведено усреднение по потерям, а затем по уровню доверия, в результате получены значения: K ср, N I, N I Г и Kср, NI, NI Г.
Для полученных средних значений точечной и интервальной оценки рассчитаны следующие коэффициенты предпочтения: k1 K / K, k2 NI / NI, k3 NI / NI В каждой группе введен коэффициент сравнения оценки математического ожидания и гарантированного значения: k4 NI / NI, k5 NI / NI, k6 (k4 k5 ) / 2.
В заключение проведен расчет А(10000)/А(5000), где А(Z) представляет собой значения K ср, N I, N I Г, и Kср, NI, NI Г и шести коэффициентов k. Все полученные данные сведены в табл. 1.
Таблица 1. Усредненные характеристики испытаний на первом этапе.
K ср K ср k1 k2 k3 k4 k5 k NI NI Г NI NI Г N=5000 17 7 2,6 27900 14000 2,0 35600 18600 1,9 1,27 1,33 1, N=10000 39 17 2,3 55700 30700 1,8 63800 36200 1,8 1,15 1,18 1, А(10000)/ А (5000) 2,3 2,6 0,9 2,0 2,2 0,9 1,8 1,9 0,9 0,90 0,88 0, Проведенные расчеты позволяют сделать следующие выводы.
1. Объем серии, используемой на первом подэтапе, должен составлять 5000 тестов.
Результаты еще раз подтверждают вывод о предпочтительности выбора объема первоначальной серии испытаний, равного N=5000. По сравнению с N=10000 при таком выборе в 1,8–2,2 раза сокращается средняя продолжительность испытаний (в 1,8 раза при точечной оценке гарантированного значения, в 2,2 раза при интервальной оценке математического ожидания). В 2–3 раза уменьшается количество циклов испытаний, что также немаловажно, поскольку упрощается организация испытаний. Кроме того, резко сокращается объем непроизводительных испытаний.
2. После первого подэтапа необходимо проанализировать коэффициент потерь a и в случае, если он попадает в диапазон (1;
1,1], увеличивать значение нормированной величины потерь на 0,1. Суммарный объем испытаний нелинейно зависит от наблюдавшегося количества потерь n0 на первом подэтапе. Это относится как к оценке математического ожидания, так и к гарантированным значениям. Фактически, это зависимость от вероятности потери вызова P, оценка которой такова, что чем ближе n0 / N к норме P0, т.е. чем меньше параметр a отклоняется от единицы, тем больший объем испытаний требуется провести. Зависимость носит катастрофический характер – при стремлении а к единице наблюдается неограниченный рост K и N I, так что при а (1;
1,1] значение P0 уже трудно достижимо.
В связи с этим для случая, когда a попадает в диапазон (1;
1,1], предлагается ввести вместо P0 величину P0 P0 P0 (положить, например, P0 0,1P0 ). Такой подход даст реализуемые значения объема испытаний N I и позволит оценить P за приемлемое время.
3. Если коэффициент потерь a1, то количество испытаний необходимо ограничить 120 000.В случае если a1, дальнейшие расчеты теряют смысл, однако количество испытаний на первом этапе необходимо ограничить. В качестве такого ограничителя предлагается выбрать гарантированное значение точечной оценки математического ожидания количества испытаний, имеющее место при соблюдении следующего условия:
E ( NP ), если NP 0, 0 n 1), если NP E ( NP 0, 0 где E(x) – целая, а {x} – дробная части числа x. Для заданных значений – P0=0,001 и N0=5000, получаем n0=4. Для заданных параметров при уровне доверия =0,975 находим Nmax =120 000.
4. При прогнозе объема испытаний предпочтительней использовать интервальные оценки, а в качестве ограничителей количества испытаний – точечные оценки.
Сопоставление коэффициентов k1 – k3 показывает, что и оценка математического ожидания, и гарантированные значения суммарного количества испытаний при переходе от точечной к интервальной оценке убывают в 1,9–2,0 раз, а количество потерь уменьшается еще более значительно – в 2,6 раза (коэффициент k1 ). Это говорит о том, что использование интервальных оценок предпочтительно при прогнозе объема испытаний.
Однако, при проведении испытаний, когда значения N I, N I Г и N I, N I Г используются как ограничители количества испытаний на первом этапе (Nmax), целесообразно, для гарантии, использовать немаркированные значения N I, N I Г.
5. При прогнозе испытаний предпочтительнее использование гарантированных оценок. Использование гарантированных оценок N I Г, N I Г значительно увеличивает ожидаемый объем испытаний. Как видно из данных таблицы (коэффициенты k4 – k6) объем испытаний увеличивается на (27–33)% для N=5000 и на (15–18)% для N=10000. Поскольку в дальнейшем признано целесообразным установить N=5000, можно считать, что в среднем гарантированные значения на 30% превосходят математические ожидания. Таким образом, использование оценок с заданным уровнем гарантии предпочтительнее при прогнозе объема испытаний. Как видно из рис. 5, второй этап состоит из прогноза числа потерь и необходимого количества испытаний для получения окончательных выводов.
Прогноз числа потерь nII Воспользуемся (4) и для определенного в третьей главе диапазона точности – 20–30% проведем усреднение по уровню гарантии, используя композитное правило Симпсона. В результате расчета мы получаем прогнозное значение n И 51, учитывая полученные на первом этапе прогнозные средние значения потерь n0 2, K 17 по формуле (29) nII n И n0 K находим среднее значение необходимого числа потерь на втором этапе испытаний nII 32.
Отметим, что все полученные прогнозные значения используются только при исследовании характеристик предлагаемой методики. На практике в формулу (34) подставляются фактические значения, полученные на первом этапе испытаний.
Прогноз необходимого количества испытаний на втором этапе.
Исходными данными для прогноза количества испытаний на втором этапе являются определенные на первом этапе значения потерь и количество испытаний. На основании этих данных мы получаем оценку максимального правдоподобия:
(30) pI nI / N I.
Воспользовавшись (13), получим оценку математического ожидания количества испытаний, которые надо провести на втором этапе: MX II nII / pI. (31) Учитывая (28) оценку гарантированного значения суммарного количества испытаний второго этапа, можно записать:
nII ), (32) N II nII (b nII Г pI где nII nII (1 pI ).
На основе полученных в третьей и четвертой главах математических выкладок проведем оценку общего предполагаемого объема испытаний, для чего зададим следующие исходные данные:
- достоверность односторонней оценки =0,975;
- предельно допустимую вероятность потери вызова – P0 = 0,001;
- необходимую точность r оценки p вероятности потери вызова P – r=(20–30)%;
- гарантийную вероятность необходимого числа испытаний – Рг=0,975;
- сетку возможных значений оценки вероятности потери вызова – 10–4 (1 10–4) 9 10–4.
Важнейшим параметром схемы является значение N0 – длина серии испытаний в подэтапе 1.1. Ранее было показано, что для целей практического использования целесообразно рекомендовать значение N0=5000, поскольку при этом (по сравнению с N0 = 10000) в среднем в 1,8–2,2 раза улучшаются ожидаемые объемные характеристики процесса испытаний. Однако при сравнительном анализе преимуществ или недостатков предлагаемой методики это соображение не может являться решающим. Напротив, необходимо стремиться выбрать не вполне благоприятные условия и варианты для определения характеристик методики, чтобы придать большую убедительность выводам о ее преимуществах, если таковые есть, или обеспечить возможность коррекции результатов, если они будут не в пользу методики. Исходя из этого, было выбрано N0 = 10000. Результаты вычислений представлены в табл. 2.
Следует отметить следующее:
- объем испытаний на первом этапе в значительной части рассмотренного диапазона значений p [10–4, 6 10–4] почти не изменяется и составляет десятки тысяч. Однако начиная с p = 7·10–4, наблюдается быстрый рост и в пограничной с P0 области составляет сотни тысяч испытаний. Среднее количество испытаний составляет примерно NI Г = 43000;
- обратная картина наблюдается на втором этапе. В области малых значений p N II Г очень велико (более 700000), затем оно быстро убывает и, в конце концов, сходит на нет, поскольку в пограничной с P0 области второй этап вообще оказывается не нужным.
Средний объем испытаний составляет примерно NII Г = 430000;
- соответственно этому суммарный объем испытаний в области малых значений p практически совпадает с N II Г, а в области больших значений – с N I Г. Средний суммарный объем испытаний составляет N Г = 470000;
- сравнение, представленное на рис. 7, предлагаемой методики с известной, по общему объему испытаний показывает, что ее применение обеспечивает снижение количества испытаний в 0,5 – 11,6 раза, а в среднем сокращает его в 5 раз. Для проведения сравнения введен k7 – коэффициент преимущества предлагаемой методики: k7 106 / N Г Таблица 2. Прогнозируемые характеристики испытаний.
Параметр, Возможные оценки вероятности потери вызова характеристика 10–4 2 10–4 3 10–4 4 10–4 5 10–4 6 10–4 7 10–4 8 10–4 9 10– 10000 10000 10000 10000 15392 24886 40265 74606 NI Г 2199408 734756 351702 186225 152880 122821 78794 11549 N II Г 2209408 744756 361702 196225 168272 147707 119058 86154 N Г 0,5 1,3 2,8 5,1 5,9 6,8 8,4 11,6 5, k Рис. 7. Прогнозируемые характеристики процесса испытаний В четвертой главе рассмотрены оценки и реализация предлагаемого метода проведения испытаний, которые позволяют:
а) автоматизировать процесс проведения испытаний, б) сократить время проведения испытаний, в) возложить на программный комплекс весь процесс обработки результатов, г) создать единую систему показателей качества, д) сформировать базу для сравнительного системного анализа однотипных сетевых элементов разных фирм-изготовителей.
ЗАКЛЮЧЕНИЕ Разработаны математические модели сертификационных испытаний 1.
инфокоммуникационных протоколов, рассчитаны статистические оценки числа тестов в разных условиях. Разработан алгоритм оптимизации процесса тестирования SDL спецификаций (рис. 5).
2. Определены ключевые вероятностно-временные характеристики процессов тестирования инфокоммуникационных протоколов и выведены аналитические выражения для их расчета.
3. Построена математическая модель SDL-спецификаций телекоммуникационных протоколов, позволяющая оптимизировать число состояний и тем самым уменьшать сроки и трудоемкость сертификационных испытаний.
4. Обнаружено, что для некоторого диапазона параметров тестирования весьма ограниченное число тестов может обеспечивать вполне достоверные оценки. Исследованы зависимости прогнозируемого числа оставшихся испытаний от статистических оценок результатов уже проведенных испытаний и выработаны соответствующие рекомендации.
5. Отдельные результаты диссертационной работы и, в первую очередь, математические модели процесса тестирования были применены при организации сертификационных испытаний в ИЛ СПбГУТ и ЛО ЦНИИС в процессе выполнении целого ряда контрактов на сертификационные испытания с разными фирмами-производителями коммутационного оборудования сетей TDM и NGN, в Научно-техническом центре Протей при заводских испытаниях оборудования NGN/IMS, в Научно-техническом центре СевенТест при разработке протокол-тестеров семейства SNT и платформы сетевого мониторинга СПАЙДЕР, в учебном процессе в СПбГУТ им. проф. М.А. Бонч-Бруевича при создании учебно-исследовательской платформы СОТСБИ-У, что подтверждено соответствующими актами и справками о внедрении.
6. Подготовлено развернутое пособие для разработки автоматизированной системы тестирования, отвечающей всем требованиям, которые предъявляют к такой системе существующие нормативные документы, с учетом Рекомендаций ITU-Т серий Е.800, Q.500, Y.1540 в составе основных показателей качества, дополнительно к вероятности потери вызова/сессии.
СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ
Гойхман В., Митрошкин К. Организация мультисервисных сетей на основе программных 1.
коммутаторов. // «Мир Lucent». - 2001.- №9. - C. 12-17.
Гойхман В.Ю., Гольдштейн Б.С., Кисленко Л.С. Телекоммуникационный контент в 2.
Инфобанке СОТСБИ. // Вестник связи. - 2002. - №9. - C.116-120. (в списке ВАК) Гойхман В.Ю., Гольдштейн Б.С., Дымарский Я.С., Сибирякова Н.Г. Сертификационные 3.
испытания коммутационного оборудования средств связи. // Вестник Международной академии «Информация, связь, управление в технике, природе, обществе». - 2002. - №4. - C.3-28.
Гойхман В.Ю., Гольдштейн Б.С., Дымарский Я.С., Сибирякова Н.Г. Модели и методы 4.
оценки эффективности протокол-тестеров. // Вестник Международной академии «Информация, связь, управление в технике, природе, обществе». - 2002. - №4. - C.29-60.
Гойхман В.Ю., Апостолова Н.А., Гольдштейн Б.С. Учрежденческие IP-PBX - прообраз 5.
эволюции технологий в СТС. // Вестник связи. - 2003. - №7. - C.37-40 (в списке ВАК).
Гойхман В.Ю. Учрежденческие АТС сегодняшнего и следующего поколения. // 6.
Технологии и средства связи. - 2003, - №4. - C. 14-20.
Гойхман В.Ю., Гольдштейн А.Б. Мультисервисные абонентские концентраторы. // 7.
Технологии и средства связи. 2004. №1. - C.22-28.
Гойхман В.Ю., Васильев А.С. Диверсификация городских АТС. // Технологии и средства 8.
связи. Спец. вып. "АТС 2004: коммутационное оборудование". 2004. - C. 10-12.
Гойхман В.Ю. Учрежденческие АТС: классификация, емкость, интерфейсы. // 9.
Технологии и средства связи. Спец. вып. "АТС 2004: коммутационное оборудование". 2004. C.34-38.
10. Гойхман В.Ю. Учрежденческие АТС - эволюция технологий. // Connect! Мир связи.
2005. №4. - C. 22-25.
11. Гойхман В.Ю. Распределенные коммутационные системы. Принципы построения. // Технологии и средства связи. 2005. №2. - C.52-59.
12. Гойхман В.Ю. Функциональные объекты IP-УАТС. // Connect! Мир связи. 2005. №4. C. 230-234.
13. Гойхман В.Ю. Новая модель сертификации коммутационного оборудования. // Технологии и средства связи. Спец. вып. 2006. - C. 12-13.
14. Гойхман В.Ю. Бизнес-коммуникации предприятия среднего бизнеса. // Connect! Мир связи. 2006. №9. - C. 114-118.
15. Гойхман В.Ю. Телефония для самых больших. Обзор решений крупных УПАТС для корпораций и ведомств. // Connect! Мир связи. 2006. №11. - C. 98-104.
16. Гойхман В.Ю. Модель тестируемости SDL-спецификаций телекоммуникационных протоколов. // 60-я научно-техническая конференция профессорско–преподавательского состава, научных сотрудников и аспирантов СПбГУТ им. проф. М.А. Бонч-Бруевича: Материалы.– СПб.:
2008.
17. Гойхман В.Ю. Процедура подтверждения соответствия оборудования корпоративных сетей. //«CIO». - 2008.- №8.
18. Гойхман В.Ю. Современные возможности корпоративной телефонии. // «CIO». - 2008. №9.
19. Гойхман В.Ю., Гольдштейн Б.С., Фицов В.В. Протокол сигнализации R1.5: учебное пособие (направление 210400 «Телекоммуникации» — специальности 210406 «Сети связи и системы коммутации», 210402 «Средства связи с подвижными объектами», 210407 «Эксплуатация средств связи»). СПбГУТ. СПб, 2009 (гриф УМО).
20. Гойхман В.Ю., Гольдштейн Б.С., Онучина Д.Н. Протокол SIP: учебное пособие (направление 210400 «Телекоммуникации» и направление 230100 «Информатика и вычислительная техника»). СПбГУТ. СПб, 2009 (гриф УМО).
21. Гойхман В.Ю. Исследование SDL-спецификаций протоколов сетей TDM и NGN. 61-я научно-техническая конференция профессорско–преподавательского состава, научных сотрудников и аспирантов СПбГУТ им. проф. М.А. Бонч-Бруевича: Материалы.– СПб.: 2009.
22. Гойхман В.Ю., Гольдштейн Б.С., Политова Ю.В. Протокол ISUP стека ОКС7: учебное пособие (направление 210400 «Телекоммуникации» и направление 230100 «Информатика и вычислительная техника»). СПбГУТ. СПб, 2009. (гриф УМО).
23. Гойхман В.Ю. Статистические модели тестирования телекоммуникационных протоколов.
62-я научно-техническая конференция профессорско–преподавательского состава, научных сотрудников и аспирантов СПбГУТ им. проф. М.А. Бонч-Бруевича: Материалы.– СПб.: 2010.
24. Гойхман В.Ю., Гольдштейн Б.С., Онучина Д.Н. Сеть NGN. Оборудование IMS: учебное пособие (направление 210400 «Телекоммуникации» и направление 230100 «Информатика и вычислительная техника»). СПбГУТ. СПб, 2010 (гриф УМО).
Подписано к печати 16. 06. 2011.
Тираж 80 экз. Объем 1 печ. л.