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

Бородин  Андрей  Викторович

канд.  эконом.  наук,  профессор  кафедры  информатики  и  системного  программирования  Поволжского  государственного  технологического  университета,  РФ,  Республика  Марий  Эл,  г.  Йошкар-Ола

E -mail:  bor@mari-el.com

Зубьяк  Дарья  Романовна

студент  группы  ПС-31  факультета  информатики  и  вычислительной  техники  Поволжского  государственного  технологического  университета,  РФ,  Республика  Марий  Эл,  г.  Йошкар- Ола

E-mail:  

STOCHASTIC  SIMULATION  IN  TASKS  OF  SYNTHESIS  OF  OPTIMUM  TOPOLOGY  OF  NETWORKS  OF  DISTRIBUTION  OF  EXACT  TIME

Andrey   Borodin

сandidate  of  Science,  professor  of  Informatics  and  System  Programming   department

of  Volga  State  University  of  Technology,  Russia,  Republic  of  Mari  El,  Yoshkar-Ola

Darya   Zubyak

student  of  PS-31  Group  of  Faculty  of  Informatics  and  ADP  Equipment

of  Volga  State  University  of  Technology,  Russia,  Republic  of  Mari  El,  Yoshkar-Ola

АННОТАЦИЯ

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

ABSTRACT

The  paper  deals  with  the  task  of  synthesis  of  systems  of  distribution  of  exact  time,  optimum  by  criterion  of  total  cost  of  ownership.  It  is  shown  that  relevance  of  a  problem.  Much  attention  is  given  to  failure  patterns  of  single  components  of  system.  It  is  given  the  technique  of  integration  of  models  of  separate  components  of  system  in  model  of  all  system.  It  is  formulated  the  formal  problem  definition  of  a  choice  of  optimum  network  topology  of  distribution  of  exact  time  on  the  discrete  set  of  decisions.

Ключевые  слова:   точное  время;  NTP;  PTP;  GPS;  NMEA;  топология  сети;  имитационное  моделирование;  сеть  Петри;  случайная  величина;  совокупная  стоимость  владения;  риск;  мера  риска;  оптимизация.

Keywords:  exact  time;  NTP;  PTP;  GPS;  NMEA;  network  topology;  simulation;  Petri  net;  random  variable;  total  cost  of  ownership;  risk;  risk  measure;  optimization.

Аэропорты,  железнодорожные  и  автовокзалы,  биржи  и  кредитные  учреждения  —  перечень  социально  значимых  объектов,  для  которых  служба  точного  времени  является  инфраструктурно-значимой  подсистемой.  Для  операторов  связи  и  многих  научно-исследовательских  учреждений,  относящихся  к  отраслям  гидрометеорологии,  сейсмологии,  гелиофизики  и  т.  п.,  эта  служба  вообще  является  системообразующей.  Отказы  подсистемы  точного  времени  означают  для  названных  структур  либо  индивидуальные  потери,  либо  коллективные  потери,  включающие  последствия  природных  катастроф.  В  этих  условиях  риски,  связанные  с  функционированием  подсистемы  точного  времени,  формируют  отраслевые  и  социоприродные  риски.  Оптимизация  этих  рисков  (идентификация  угроз  и  минимизация  соответствующих  потерь,  представленных  в  той  или  иной  форме)  представляется  в  этой  связи  чрезвычайно  актуальной  проблемой.

Для  дистрибуции  точного  времени  в  современных  инфраструктурных  решениях  используются  протоколы  NTP  (Network  Time  Protocol)  [7]  и  Precision  Time  Protocol  (PTP)  [6].  Основная  масса  клиентского  оборудования,  использующего  синхронизацию  времени,  поддерживает  сегодня  лишь  протокол  NTP.  Использование  протокола  PTP,  обеспечивающего  более  высокую  точность  дистрибуции  точного  времени,  пока  ограничено  необходимостью  использования  специальных  аппаратных  решений  и  их  весьма  значительной  стоимостью.  Основными  игроками  на  рынке  разработки  и  производства  NTP-серверов  являются  американские  компании  Microsemi  (ранее  Symmetricom)  и  Spectracom,  а  также  отчасти  Trimble  и  Communication  Systems  Solutions,  немецкий  рынок  NTP-решений  представлен  компанией  Meinberg.  Безусловный  лидер  на  этом  рынке  —  Microsemi  Corp.  Несмотря  на  также  достаточно  высокую  стоимость  специализированных  серверов  времени  названных  копаний  их  использование  часто  целесообразно  [2].  Другим  подходом  к  синхронизации  времени  является  использование  достаточно  широко  распространенных  GPS-приемников,  поддерживающих  протокол  NMEA  [1],  сообщения  которого  по  определению  содержат  метки  точного  времени,  формируемые  на  основе  данных,  получаемых  со  спутникового  дивизиона.

Учитывая  перечисленные  выше  соображения,  была  поставлена  задача  разработки  методики  выбора  оптимальных  технических  решений  по  синхронизации  времени.  В  основу  синтезируемых  технических  решений  могут  быть  положены  как  решения  на  основе  протокола  NTP  в  вычислительных  сетях,  формирующих  инфраструктуру  тех  или  иных  организаций,  так  и  источники  точного  времени  в  виде  потока  NMEA-данных,  терминируемые  стандартными  хостами  сети  с  установленным  специализированным  программным  обеспечением  синхронизации  времени  (локальные  решения,  NTP-,  PPS-серверы).  Методика  должна  учитывать  возможность  использования  комбинированных  решений.

Для  решения  поставленной  задачи  были  разработаны  модели  отказов  различных  типов  источников  точного  времени  в  виде  конечных  вероятностных  пространств.  Для  построения  вероятностных  пространств,  моделирующих  источники  точного  времени,  используется  подход,  основанный  на  использовании  сетей  Петри  со  случайной  маркировкой  [3].  В  частности  для  специализированных  серверов  времени  с  раздельными  портами  управления  и  сервиса  носитель  вероятностного  пространства  содержит  4  элементарных  исхода  (см.  рис.  1):  нормальное  функционирование,  отказ  в  обслуживании  на  порту  управления,  отказ  в  обслуживании  для  сервисной  функции,  отказ  оборудования.  Для  специализированных  серверов  с  совмещенным  портом  носитель  содержит  3  исхода  (см.  рис.  2):  нормальное  функционирование,  отказ  в  обслуживании  и  отказ  оборудования.  Для  NMEA-устройств  —  два  (см.  рис.  3):  нормальное  функционирование  и  отказ  оборудования.

Рисунок  1.  Модель  отказов  сервера  времени  с  выделенным  портом  управления

Рисунок  2.  Модель  отказов  сервера  времени  с  одним  универсальным  портом

Рисунок  3.  Модель  отказов  NMEA -устройства

Переходы  сетей  Петри,  представленных  на  рисунках  1—3,  соответствующие  отказам  всех  видов,  дополнительно  охарактеризованы  средними  затратами  на  восстановление.  Если  восстановление  происходит  в  автоматическом  режиме,  то  соответствующая  характеристика  считается  равной  нулю.

Для  построения  вероятностного  пространства,  моделирующего  систему  дистрибуции  точного  времени  в  целом,  содержащую  множество  типовых  элементов,  используется  принцип  асинхронной  интерпретации  моделей  элементов.  В  модели  отдельно,  также  асинхронно,  выделяется  логика  учета  потерь,  связанных  с  потерей  синхронизации  времени  в  сети.  Например,  для  мультисервисной  сети  передачи  данных,  объединяющих  три  кампуса  и  содержащих  резервированные  сервера  времени  в  каждом  кампусе  (см.  рис.  4),  модель  системы  дистрибуции  точного  времени  представлена  на  рис.  5. 

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

На  рис.  4  один  кампус  содержит  два  сервера  времени  с  одним  универсальным  портом,  остальные  два  кампуса  содержат  по  два  сервера  времени  с  выделенными  портами  управления,  которые  из  соображений  безопасности  отделены  от  основной  сети  межсетевыми  экранами.  Любой  сервер  времени  стратума  2  в  сети  имеет  доступ  ко  всем  первичным  серверам  времени.  Сервера  времени  стратума  2  на  рис.  4  не  представлены,  первичные  сервера  времени  изображены  в  виде  часов.  Потеря  синхронизации  времени  для  всех  клиентов  сети  происходит  при  одновременном  отказе  всех  первичных  источников  времени.  Эта  логика  описана  на  рис.  5  фрагментом  сети,  состоящим  из  позиции  p*  и  перехода  t*,  соединенных  дугой  кратности  6.

Рисунок  6.  Модель  отказов  подсистемы  дистрибуции  точного  времени  мультисервисной  сети  передачи  данных

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

Модель  системы  дистрибуции  точного  времени,  представленная  на  рис.  6,  основывается  на  простейших  статистиках  отказов.  Эти  статистики  накапливаются,  как  правило,  на  ежедневной  основе.  Иначе  говоря,  модель,  представленная  на  рис.  6,  —  это  модель  одного  дня  жизненного  цикла  подсистемы.  Возникает  вопрос:  как  оценить  совокупную  стоимость  владения  за  произвольный  период?  Воспользуемся  предположением  о  независимости  событий,  происходящих  в  разные  дни.  В  этом  случае  модель  подсистемы  дистрибуции  времени  на  заданном  интервале  времени  можно  представить  в  виде  сети  Петри,  представленной  на  рис.  7.  На  этом  рисунке:  t₀  —  переход,  охарактеризованный  плановыми  затратами  на  техническое  обслуживание  подсистемы  (и,  возможно,  на  ее  развертывание);  N₁  —  модель  одного  дня  жизненного  цикла  подсистемы.  Прямое  вычисление  распределения  случайной  величины  совокупной  стоимости  владения  подсистемой  по  имитационной  модели,  приведенной  на  рис.  7,  затруднено  ввиду  значительного  количества  элементарных  вероятностных  пространств  [5].  Для  решения  этой  задачи  удобно  использовать  результаты,  полученные  для  портфелей  однородных  финансовых  инструментов  и  реализованные  в  виде  пакета  прикладных  программ  «МультиМир»  [4].

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

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

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

Теперь,  имея  в  арсенале  инструмент  расчета  распределения  случайной  величины  совокупной  стоимости  владения,  можно  сформулировать  основную  оптимизационную  задачу:

,

где:    —  оптимальное  техническое  решение; 

  —  множество  возможных  технических  решений; 

  —  модель  технического  решения  ; 

  —  случайная  величина  совокупной  стоимости  владения,  соответствующая  модели  ; 

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

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

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

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

Список  литературы:

1.Бородин  А.В.  О  задаче  синхронизации  времени  на  основе  GPS-приемников  коммерческой  точности  с  использованием  протокола  NMEA  [Текст]  /  А.В.  Бородин  //  Обозрение  прикладной  и  промышленной  математики.  —  2008.  —  Т.  15.  —  В.  6.  —  С.  1046—1047.

2.Бородин  А.В.  Стоимость  владения  как  критерий  архитектуры  первичного  NTP-сервера  на  основе  GPS-приемников  коммерческой  точности  [Текст]  /  А.В.  Бородин  //  Обозрение  прикладной  и  промышленной  математики.  —  2009.  —  Т.  16.  —  В.  3.  —  С.  507—508.

3.Бородин  А.В.  Теоретико-игровые  модели  процессов  риска  над  сетями  Петри  [Текст]  /  А.В.  Бородин  //  Моделирование  и  анализ  безопасности  и  риска  в  сложных  системах:  Труды  международной  научной  школы  МАБР-2006.  СПб.:  ГОУ  ВПО  «СПбГУАП»,  2006.  —  С.  305—307.

4.Уразаева  Т.А.  Алгебра  рисков  [Текст]  /  Т.А.  Уразаева.  Йошкар-Ола:  Поволжский  государственный  технологический  университет,  2013.  —  209  с.

5.Уразаева  Т.А.  Алгебраические  аспекты  имитационного  моделирования  портфелей  срочных  финансовых  инструментов  [Текст]  /  Т.А.  Уразаева,  А.В.  Бородин  //  Материалы  конференции  «Имитационное  моделирование.  Теория  и  практика».  ИММОД-2013.  Т.  1.  Казань:  Издательство  «Фэн»  Академии  наук  РТ,  2013.  —  С.  282—286.

6.IEEE  Std  1588^TM-2008.  IEEE  Standard  for  a  Precision  Clock  Synchronization  Protocol  for  Networked  Measurement  and  Control  Systems  [Электронный  ресурс].  —  Режим  доступа.  —  URL:  http://www.googlecode.com/files/IEEE-1588-2008.  pdf.  Дата  обращения:  24.10.2013.

7.RFC  5905.  Network  Time  Protocol  Version  4:  Protocol  and  Algorithms  Specification,  June  2010  [Электронный  ресурс].  —  Режим  доступа.  —  URL:  http://  www.rfc-editor.org/rfc/rfc5905.txt.  Дата  обращения:  24.10.2013.