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

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

Вашему вниманию предлагается оригинальный алгоритм (DESYNC: ftp://ftp.deas.harvard.edu/techreports/tr-18-06.pdf), который может быть использован для распределения нагрузки между группами узлов, подключенных к одному и тому же групповому каналу.

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

Экспериментальные исследования [1] показали ощутимое снижение потери сообщений в условиях конкурентной среды с 58% до 1%, так же как и 25% увеличение пропускной способности.

1.      Основные принципы.

1.1. Представим себе полносвязную сеть («клику»), которая включает в себя n узлов. Будем считать, что любой узел такой «клики» - X_i, может рассматриваться как некий генератор синхросигналов, выдаваемых с частотой - ω, которая определяется соотношением (1):

ω = 1 / T

(1)

где T – длительность цикла, разделяющего синхросигналы, которые выдаются одним и тем же узлом.

Фаза, на которой находится каждый конкретный узел X_i, может быть определена величиной ϕ _i(t), которая может принимать значения от 0 до 1, причём значения ϕ_i(t) определяются
отдельно для каждой вершины, то есть число индексов i будет зависеть от числа вершин в «клике» и определяться неравенством (2):

  1.2. Вычисление величины ϕ_i(t) в каждом узле X_i, должно осуществляться автономно, с помощью собственных «внутренних часов», причём в момент времени, когда величина ϕ_i(t) достигнет единицы, узел X_i выдаёт в сеть синхросигнал, после чего приравнивает ϕ_i(t) нулю.

Значение величины ϕ_i(t) должно всегда соответствовать доле интервала времени T, которое прошло после установки ϕ_i(t) в ноль. Например, значение ϕ_i(t)=0.75 соответствует тому, что узел X_i отсчитал 75% времени T.

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

Более того, процедуры коррекции фаз должны стремиться к тому, чтобы интервал времени Δ_i(t) между выдачей синхросигнала любым узлом X_i-1 и выдачей синхросигнала следующим за ним узлом X_i – интервал Δ_i(t), равнялся интервалу Δ_i*(t), который определяется соотношением (3):

Δi*(t) = T / n

(3)

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

1.      Механизмы коррекции фазы.

1.1.Суть механизма коррекции фаз в DESYNC заключается в следующем:

1)      поскольку каждый узел «клики» - X_i способен установить факт передачи синхросигнала от любого узла X_jГ^-1X_i, то он способен получать информацию от узлов X_i-1 и X_i+1, первый из которых выдал синхросигнал перед синхросигналом от X_i, второй – вслед за синхросигналом от X_i;

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

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

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

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

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

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

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

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

где

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

- Δ_i+1 - значение величины ϕ_i(t) в момент получения первого синхросигнала от любого соседнего узла, принятого после момента выдачи синхросигнала узлом X_i.

 2.3. Такое решение может быть проиллюстрировано следующими примерами.

Предположим, что последовательность выдачи синхросигналов узлами X_i-1 , X_i  и X_i+1 соответствует временной диаграмме, которая представлена на рисунке 1:

Рисунок 1

Допустим, что синхросигнал от узла X_i-1 принят в тот момент времени, когда «часы» узла X_i показывают ϕ_i(t)=0.7. Эта величина фиксируется в памяти узла X_i.  Тогда, в момент времени, когда узел X_i будет выдавать «собственный» синхросигнал, он может установить, что Δ_i(t)=0.7.

Аналогичным образом, после получения синхросигнала от X_i+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) будет уменьшено.

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