среда, 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) будет уменьшено.

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