Показаны сообщения с ярлыком TDMA. Показать все сообщения
Показаны сообщения с ярлыком TDMA. Показать все сообщения

вторник, 14 октября 2014 г.

SDN: новые возможности управления потоками в mesh — сетях



Здравствуйте, уважаемые читатели. Стоит сразу оговориться, что данная статья не о том, что хорошо, а что плохо в SDN или каких-то других сетевых технологиях. Мы не яростные адепты программно-конфигурируемых сетей. Мы просто хотим рассказать вам о решениях, к которым мы пришли, разрабатывая промышленные mesh-сети в рамках создания промышленных беспроводных систем связи. Рассказать о возможностях, которые находятся на стыке технологий, позволяя опираться на хорошо проверенные решения и в то же время идти в ногу со временем.

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

Сказанное, в полной мере, относится и к mesh-сетям, где преобладают два подхода к маршрутизации – проактивный(например протокол OLSR) и реактивный (протокол AODV). Существуют и весьма производительные гибридные схемы.

OLSR (Optimized Link-State Routing) [1] основан на сборе и распространении служебной информации о состоянии сети. В результате обработки этой информации каждый узел может построить модель текущего состояния сети в виде формального описания графа, вершины которого ставятся в соответствие узлам сети, рёбра (или дуги) – линиям связи (линкам). Имея такой граф, любой узел может вычислить «длины» кратчайших путей до всех адресатов в сети и выбрать «оптимальный» маршрут, ведущий к любому конкретному узлу сети.

Данный алгоритм хорошо реагирует на множество непредвиденных событий, к которым, прежде всего, следует отнести:

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

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

Наряду с протоколом OLSR, который обеспечивает предварительный (проактивный) расчёт маршрутов между всеми парами абонентов в пределах подсети, в mesh-сетях реализуется другой – реактивный протокол AODV ( Ad hoc On-Demand Distance Vector) [2]. Данный протокол предусматривает поиск и организацию маршрутов по мере их необходимости, и разрушение найденных маршрутов после их использования.

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

Тем не менее, оба протокола (в совокупности), в какой-то степени, соответствуют основным требованиям, которым должен удовлетворять «идеальный алгоритм» [3]. Эти требования можно сформулировать и прокомментировать следующим образом:

Корректность. Оба алгоритма работоспособны и не содержат логических противоречий.
  • Вычислительная простота. Реализация алгоритма AODV требует минимальных процессорных ресурсов. И, наоборот, алгоритм OLSR достаточно сложен.
  • Устойчивость. Оба алгоритма стремятся к конкретному решению без резких осцилляций при незначительных изменениях состояний радиолучей.
  • Справедливость. На первый взгляд, оба алгоритма предоставляют равноценные услуги всем пользователям сети. Но, вследствие своего топологического расположения в сети, отдельные пользователи могут захватить относительно большую долю ресурсов, чем им необходимо.
  • Адаптивность к изменениям трафика и топологии. Оба алгоритма способны определить новое множество маршрутов при изменении топологии сети. Но и тот, и другой алгоритм статичен по отношению к внешнему трафику и распределению нагрузки.

Последний недостаток характерен для всех известных децентрализованных стратегий, за исключением стратегий кратчайшей очереди и смещения [3], при которых вес маршрута определяется как линейная функция от двух параметров: числа транзитных участков на пути к адресату и длинах очередей на направлениях выдачи, лежащих на маршруте (классический пример – Internet [3]). В протоколах mesh-сетей подобных стратегий нет, и, по-видимому, не будет, так как такая стратегия потребует сложных и трудоёмких вычислений на всех узлах и, вряд ли будет обладать свойством устойчивости – незначительные колебания нагрузки могут спровоцировать перерасчёт маршрутов.

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

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

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

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

Такой подход может быть реализован и в mesh-сетях, но он требует использования специализированных маршрутно-адресных таблиц, задающих соответствие направлений передачи пакетов не только адресам получателей, но и более специализированным признакам, например выделенным парам — «источник-получатель». В стандартных сетевых протоколах таких возможностей нет, но эта задача достаточно тривиально решается применением протокола OpenFlow.

Одна из малозаметных, но наиболее значительных особенностей данного протокола в том, что он позволяет понимать под «потоком» практически все что угодно, за счет создания собственного классификатора потоков, адаптированного к конкретной сетевой задаче. Например в первой версии протокола OpenFlow поток TCP может быть определен данными из 10 полей. OpenFlow позволяет найти компромисс между стандартными решениями и уникальными алгоритмами, которые могут сосуществовать в одной и той же среде, не «мешая» друг другу.
Суть такого компромисса заключается в следующем:

  • в стандартный стек протоколов встраиваются механизмы, позволяющие разделить обслуживаемый поток на части, причем одна из них может обслуживаться стандартными протоколами TCP/IP, остальные – с помощью оригинальных процедур;
  • для сортировки могут использоваться служебные поля принимаемых пакетов, такие как IP-адреса отправителя и получателя, соответствующие им MAC-адреса, номера портов и т.д.
  • для определения маршрутов «нестандартных» потоков могут использоваться таблицы потоков, задающие соответствие направлений передачи пакетов не только адресам получателей, но и на основании более сложной динамической логики — «источник-получатель», права доступа, загрузка серверов, приоритеты по обслуживанию и т. д.


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

В следующей части мы постараемся осветить вопросы реализации описанного гибридного подхода в промышленных беспроводных mesh-сетях.

среда, 28 августа 2013 г.

Алгоритм DESYNC. Достоинства и недостатки


Алгоритм DESYNC. Достоинства и недостатки.
Часть 2. 


3.      Позитивные свойства  алгоритма и его недостатки
3.1. С точки зрения пользователя, алгоритм DESYNC весьма удобен, поскольку он не требует подготовки каких либо настроечных данных, например таких, как размер сети, её топология или её исходное состояние.
Пользователю сети достаточно знать допустимое число абонентов в «клике», которое ограничено возможностями используемых технических средств и задано разработчиком изделия как некая константа.
Это объясняется тем, что, при использовании алгоритма DESYNC, узлы сети определяют моменты передачи собственных синхросигналов автономно,  опираясь лишь на  показания собственных «часов», ход которых корректируется в моменты приёма «синхросигналов» от соседей. При этом  данный алгоритм игнорирует такие атрибуты узлов, как идентификаторы (адреса) соседних узлов, их число, статус и т.п.  
3.2. Рассматриваемый алгоритм обладает свойством «самоадаптации» - добавление или удаление того или иного узла не приведёт к потере синхронизма. Возникающий при этом «дисбаланс» фаз вызовет лишь  их коррекцию в узлах сети, причём, по окончании соответствующего переходного процесса, сеть войдёт в стационарный режим. То же самое будет происходить при поражениях или спонтанных отказах узлов.  
3.3. Использование данного алгоритма обеспечивает «справедливое» деление временных интервалов между узлами -  в стационарном режиме (в независимости от числа узлов) интервалы времени между передачами очередных синхросигналов – T / n будут распределены равномерно.
Эта особенность может оказаться полезной при случайных сбоях и временных потерях радиослышимости – если число абонентов в сети невелико, то случайные сбои, которые могут спровоцировать резкие скачки фаз, далеко не всегда приведут к коллизиям. Такие события будут всегда приводить к увеличению длин интервалов T / n, что увеличивает шансы на успех  при возврате элементов сети к прежнему состоянию.  Вообще, любая подобная ситуация может рассматриваться как «штатная».
 3.4. Однако следует отметить, что использование рассматриваемого протокола эффективно только в том случае, если топология сети отвечает условию (9):




то есть сеть является «кликой».
Если же условие (9) соблюдаться не будет, то сеть может оказаться в состоянии «перманентного переходного процесса», который может быть проиллюстрирован следующим примером.
Допустим, что сеть состоит из трёх узлов и её топология соответствует графу, который изображён на рисунке 2:


Рисунок 2

Представим себе, что в сети работают только два узла – Xa и Xb, и моменты выдачи «синхросигналов» этими узлами, соответствуют временному циклу, представленному на рисунке 3:

Рисунок 3

Теперь представим себе, что, после очередной коррекции фазы в узле Xb, к сети подключился узел Xс,  и следующий цикл T будет соответствовать рисунку 4:

Рисунок 4

Такая ситуация приведёт к сдвигу фазы узла Xb, причём «новая» фаза этого узла будет стремиться к середине интервала времени между выдачей «синхросигналов» от узла Xa (воспринимаемого как узел Xb-1) и Xс (воспринимаемого как узел Xb+1).
Но, поскольку «новая» фаза узла Xb  обнаружится только в следующем цикле, резких скачков фаз в узлах Xa и Xс  не произойдёт. Произойдут лишь следующие события:
1)      узел Xc зафиксирует длину интервала Δс(t), воспринимая  Xb  как источник «синхросигнала» от  мнимого  узла Xc-1;
2)      узел Xa  зафиксирует либо длину интервала Δa(t), либо длину интервала Δa+1(t)  (в последнем случае процедуры коррекции фазы в узле Xa будут выполнены, но фаза этого узла практически не изменится).
Далее, последовательность событий может развиваться по следующему сценарию:
- получив  следующий «синхросигнал» от Xb, узел Xс сдвинет свою фазу так, что момент выдачи «синхросигнала» Xc  в следующем цикле будет смещён в сторону Xa, (см. рисунок 5):


Рисунок 5

- если узел Xa воспринимает «синхросигнал» от Xb как сигнал от источника Xa+1, то он также сдвинет свою фазу, но в противоположенную сторону – навстречу Xс (см. рисунок 6):


Рисунок 6

- возникает коллизия, в результате чего узел Xb перестанет воспринимать сигналы от своих соседей и будет менять свою фазу только за счёт погрешности собственных «часов»;
- однако «дрейф» фазы Xb не улучшит сложившуюся ситуацию, поскольку узлы Xa и Xc будут всегда стремиться занять один и тот же слот.
Возможны другие (может и более благополучные) сценарии, но приведённого примера вполне достаточно, чтобы убедиться в том, что использование алгоритмов DESYNC в сетях, не отвечающих условию (9), не имеет смысла.

вторник, 13 августа 2013 г.

Алгоритм DESYNC. Достоинства и недостатки



Алгоритм DESYNC. Достоинства и недостатки.
Часть1.


Вашему вниманию предлагается оригинальный алгоритм (DESYNC: ftp://ftp.deas.harvard.edu/techreports/tr-18-06.pdf), который может быть использован для распределения нагрузки между группами узлов, подключенных к одному и тому же групповому каналу.
Рассматриваемый алгоритм обеспечивает автоматическое составление и корректировку расписаний выхода в эфир для всех абонентов канала. При этом алгоритм DESYNC  исключает возможность возникновения коллизий.
Экспериментальные исследования [1] показали ощутимое снижение потери сообщений в условиях конкурентной среды с 58% до 1%, так же как и 25% увеличение пропускной способности.
1.      Основные принципы.
1.1. Представим себе полносвязную сеть («клику»), которая включает в себя n узлов. Будем считать, что любой узел такой «клики» - Xi, может рассматриваться как некий генератор синхросигналов, выдаваемых с частотой - ω, которая определяется соотношением (1):
ω = 1 / T
(1)
где T – длительность цикла, разделяющего синхросигналы, которые выдаются одним и тем же узлом.
Фаза, на которой находится каждый конкретный узел Xi, может быть определена величиной ϕ i(t), которая может принимать значения от 0 до 1, причём значения ϕi(t) определяются
отдельно для каждой вершины, то есть число индексов
i будет зависеть от числа вершин в «клике» и определяться неравенством (2):


  1.2. Вычисление величины ϕi(t) в каждом узле Xi, должно осуществляться автономно, с помощью собственных «внутренних часов», причём в момент времени, когда величина ϕi(t) достигнет единицы, узел Xi выдаёт в сеть синхросигнал, после чего приравнивает ϕi(t) нулю.
Значение величины ϕi(t) должно всегда соответствовать доле интервала времени T, которое прошло после установки ϕi(t) в ноль. Например, значение ϕi(t)=0.75 соответствует тому, что узел Xi отсчитал 75% времени T.
1.3. Все узлы «клики» способны слышать синхросигналы от своих «соседей» и использовать эту информацию для «подгона» или «осаживания» величин ϕi(t) таким образом,  чтобы  моменты выдачи синхросигналов разными узлами не совпадали по времени, но передавались поочерёдно – в порядке возрастания  значений индексов i.
Более того, процедуры коррекции фаз должны стремиться к тому, чтобы интервал времени Δi(t) между выдачей синхросигнала любым узлом Xi-1 и выдачей синхросигнала следующим за ним узлом Xi – интервал Δi(t), равнялся интервалу Δi*(t), который определяется соотношением (3):
Δi*(t) = T / n
(3)

Если условие (3) выполняется для всех вершин «клики», то процесс коррекции фаз ϕi(t) может считаться завершённым. В противном случае – сеть должна считаться полностью или частично рассинхронизированной.

1.      Механизмы коррекции фазы.
1.1.Суть механизма коррекции фаз в DESYNC заключается в следующем:
1)      поскольку каждый узел «клики» - Xi способен установить факт передачи синхросигнала от любого узла XjГ-1Xi, то он способен получать информацию от узлов Xi-1 и Xi+1, первый из которых выдал синхросигнал перед синхросигналом от Xi, второй – вслед за синхросигналом от Xi;

2)  наблюдая за эфиром, любой узел Xi может получить информацию о фактах передачи синхросигналов всеми узлами «клики»;

3) имея такую информацию узел Xi способен вычислить среднюю точку между выдачей синхросигнала узлом Xi-1 и выдачей синхросигнала узлом Xi+1; Для этого достаточно воспользоваться выражением  (4):


где Φi-1(t) и  Φi+1(t) – фазы приёма синхросигналов от узлов Xi-1 и Xi+1, по «местному времени» узла Xi;  

4)      после того, как значение Φmid(t) определено, узел Xi может скорректировать свою фазу, заменяя ϕi(t) на величину ϕi*(t), которая определяется с помощью формулы (5):


где α – параметр, который отвечает неравенству (6):


Этот параметр позволяет ограничить  колебания фазы при её коррекции - чем ниже  значение α - тем незначительней «коррекционный эффект»;


5)      коррекция фазы осуществляется сразу после получения синхросигнала от Xi+1.

2.2.       В принципе, для вычисления Φmid(t), достаточно воспользоваться выражением (4).. Но, возможно и более  рациональное решение. Величина Φmid(t) может быть определена с помощью выражения (7):

где
- Δi – текущее значение величины ϕi(t)  в момент получения последнего синхросигнала от всех соседей Xi (до момента времени, когда ϕi(t)=1);
- Δi+1 - значение величины ϕi(t) в момент получения первого синхросигнала от любого соседнего узла, принятого после момента выдачи синхросигнала узлом Xi.

 2.3. Такое решение может быть проиллюстрировано следующими примерами.
Предположим, что последовательность выдачи синхросигналов узлами Xi-1 , Xi  и Xi+1 соответствует временной диаграмме, которая представлена на рисунке 1:


Рисунок 1

Допустим, что синхросигнал от узла Xi-1 принят в тот момент времени, когда «часы» узла Xi показывают ϕi(t)=0.7. Эта величина фиксируется в памяти узла Xi.  Тогда, в момент времени, когда узел Xi будет выдавать «собственный» синхросигнал, он может установить, что Δi(t)=0.7.
Аналогичным образом, после получения синхросигнала от Xi+1, может быть установлена величина Δi+1. Предположим, что Δi+1=0.3. Тогда, имея  Δi(t)=0.7 и Δi+1=0.3 с помощью выражения (8) можно получить:


Φmid(t) = ϕi(t) + {[Δi+1 - Δi(t)] / 2} = 1 + (0.3 – 0.7) / 2 = 1 – 0.2 = 0.8


Предположим, что заданный параметр α=0.5. В таком случае, пользуясь формулой (5), можно получить: 
ϕi*(t) = (1- α) ϕi(t) + α Φmid(t) = 0.5x0.3 + 0.5x0.8 = 0.55

что соответствует  «подгону» фазы ϕi(t), - поскольку установка ϕi*(t) будет осуществлена при ϕi(t)=Δi+1=0.3, то  текущее значение ϕi(t) будет увеличено.      
Аналогичным образом, может быть осуществлено «осаживание» фазы ϕi(t).
Такое событие произойдёт в том случае, если после измерения величин Δi и Δi+1 выяснится, что эти величины  отвечают неравенству (8):  
Δi+1 > Δi
(8)
Например, при Δi(t)=0.3, Δi+1=0.7 и α=5, будем иметь:  
Φmid(t) = 1 + (0.7 – 0.3) / 2 = 1.2
Округлив эту величину по модулю 1, получим Φmid(t) = 0.2, и, при α=0.5, будем  иметь:

ϕi*(t) = (1- α) ϕi(t) + α Φmid(t) = 0.5x0.7 + 0.5 x 0.2 = 0.36
Таким образом, коррекция фазы будет осуществлена при ϕi(t)=Δi+1=0.7, следовательно, текущее значение ϕi(t) будет уменьшено.

Мы продолжим обсуждение темы в следующей части.

среда, 26 июня 2013 г.

Анализ существующих протоколов TDMA



Анализ существующих протоколов TDMA
Часть 5

Описание графа G** = (U, Г**) может быть оформлено в виде матрицы = ║Uij║ размером N×N, где N – число дуг в исходном графе = (E, Г). Столбцы и строки такой матрицы должны соответствовать дугам исходного графа, а элементы Uij содержать следующую информацию:



Пример такой матрицы, составленной для приведённого на рисунке 2.2 исходного графа, представлен на рисунке 21:

Рисунок 21

(для удобства чтения, дуги обозначены соответствующими им парами вершин исходного графа).

Данной матрице соответствует граф G** = (U, Г**), показанный на рисунке 22:

 
Рисунок 22


Сравнивая приведённые на рисунках 14 и 22 графы, отметим, что описание графа G** = (U, Г**) более громоздко, чем описание графа G* = (E, Г*). Это объясняется тем, что в исходном графе = (E, Г) число дуг превышает число вершин.
И, если функциональная избыточность сети достаточно высока – число вершин в графе G**=(U, Г**) будет очень велико, и число «красок» будет мало отличаться от числа дуг в исходном графе.  В предельном же случае, когда граф  = (E, Г) будет представлять собой «клику», то есть отвечать условию (7):    




каждая дуга такого графа потребует отдельной «краски» и, соответственно,  каждый радиолуч - отдельного слота.
Число таких слотов будет определяться выражением (8):





где n – число вершин в графе = (E, Г).
Если же отказаться от идеи распределения слотов по радиолучам, и распределять слоты по узлам, то число слотов будет равняться величине n. Так, если «клика» включает в себя 16 узлов, то при распределении слотов по радиолучам, необходимо предусмотреть организацию 240 слотов, а при распределении по узлам – всего 16.
Казалось бы, сама идея распределения слотов по радиолучам - нерациональна. Однако, если считать, что выделение временных слотов должно производиться для ограниченного числа пользователей, то их число может оказаться небольшим. Например, (см. рисунок 23), для организации дуплексного соединения между узлами X1 и X5, потребуются всего два временных слота.

Рисунок 23

По-видимому, этот вопрос требует более детального рассмотрения. И очевидно, что он тесно связан с алгоритмами решения задачи раскраски графов.


вторник, 18 июня 2013 г.

Анализ существующих протоколов TDMA


Анализ существующих протоколов TDMA
Часть 4

Следует отметить, что, в общем случае, граф коллизий G* = (E, Г*) может обладать семейством внутренне устойчивых подмножеств и не иметь таких подмножеств вообще – всё зависит от конфигурации исходного графа = (E, Г).

И, по-видимому, задача оптимальной раскраски вершин графа = (E, Г) должна включать в себя алгоритм поиска семейства таких подмножеств, с последующим выбором приемлемого варианта раскраски вершин.

Сказанное относится и к задаче «бесконфликтной» раскраске радиолучей. Только в данном случае должен быть построен граф коллизий иного вида – граф      G** = (U, Г**), причём множество вершин этого графа должно соответствовать дугам исходного графа - = (E, Г), а отображения Г** – указывать на «конфликтные» радиолучи.

«Конфликтность» радиолучей может быть определена следующими правилами:
1)      каждый узел не должен осуществлять передачу информации одновременно по двум и более радиолучам;
2)      любой узел не может одновременно принимать информацию от двух и более узлов;
3)      ни один из узлов не способен к одновременной передаче и приёму пакетов.

Более точно, эти правила будут выглядеть следующим образом:
1)      «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (Xi, Xj) должна считаться «конфликтной» для любой другой дуги G=(E, Г), если эти дуги исходят из одной и той же вершины Xi. Например, фрагменту исходного графа = (E, Г), который изображён на рисунке 15

Рисунок 15


будет соответствовать фрагмент графа G** = (U, Г**), который представлен на рисунке 16:

Рисунок 16

2)      аналогичным образом, «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (Xi, Xj) должна считаться «конфликтной» для любой другой дуги = (E, Г), если эти дуги заходят в одну и ту же вершину Xj. Например, (см. рисунки 17 и 18), дуги (X1, X2), (X3, X2) и (X4, X2) будут также являться «конфликтными», и все соответствующие им вершины в графеG** = (U, Г**) должны считаться смежными.



Рисунок 17


Рисунок 18



3)      наконец, любая пара дуг (Xi, Xk) и (Xk, Xj), первая из которых заходит в вершину Xkисходного графа = (E, Г), а вторая выходит из той же вершины того же графа, также должны считаться «конфликтными» - см. рисунки 19 и 20:

Рисунок 19

 

Рисунок 20


Мы продолжим обсуждение темы в следующей части.