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

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

Комментариев нет:

Отправить комментарий