commit 88ff88110d8d014c3929d665f6d9318093e54cbb
parent 3e8657c9814daac43c2a2ebff175ca8f305d30f0
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Fri, 3 Nov 2017 10:38:12 +0300
Edit tree hierarchy traversal algorithm.
Diffstat:
2 files changed, 27 insertions(+), 23 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -3026,19 +3026,23 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
для разреженных сетей (в которых узлы занимают непоследовательные IP-адреса)
сбалансированность дерева не гарантируется.
-Алгоритм обхода древовидной иерархии определяет IP-адреса и порядок их опроса,
-который каждый узел кластера выполняет для поиска своего руководителя. Сначала
-базовый узел (узел, который ищет руководителя) вычисляет адрес своего
-потенциального руководителя и пытается установить соединение с ним. Если
-соединение не удается, базовый узел последовательно пытается соединиться с
-каждым узлом, находящимся на более высоком уровне иерархии, пока не достигнет
-вершины иерархии (корня дерева). Если ни одно из соединений не удается, базовый
-узел последовательно пытается соединиться с каждым узлом на своем уровне,
-имеющим более низкую позицию в диапазоне всех IP-адресов подсети. Если ни один
-из узлов не отвечает, базовый узел занимает вершину иерархии, а обход иерархии
-повторяется через заданный промежуток времени. Пример порядка обхода для
-кластера из 11 узлов и древовидной иерархии с ветвлением 2 показан на
-рис.\nbsp{}[[fig-tree-hierarchy-11]].
+Формулу для вычисления расстояния можно сделать сколь угодно сложной (чтобы
+учесть задержки и пропускную способность сети или географическое местоположение
+узла), однако, для ее простейшего вида более выгодно использовать алгоритм
+обхода узлов кластера. Этот алгоритм требует меньшего количества памяти,
+поскольку не нужно хранить ранжированный список всех узлов, вместо этого он
+перебирает все IP-адреса сети в порядке, определяемом значением ветвления.
+Алгоритм работает следующим образом. Сначала базовый узел (узел, который ищет
+руководителя) вычисляет адрес своего потенциального руководителя и пытается
+установить соединение с ним. Если соединение не удается, базовый узел
+последовательно пытается соединиться с каждым узлом, находящимся на более
+высоком уровне иерархии, пока не достигнет вершины иерархии (корня дерева). Если
+ни одно из соединений не удается, базовый узел последовательно пытается
+соединиться с каждым узлом на своем уровне, имеющим более низкую позицию в
+диапазоне всех IP-адресов подсети. Если ни один из узлов не отвечает, базовый
+узел занимает вершину иерархии, а обход иерархии повторяется через заданный
+промежуток времени. Пример порядка обхода для кластера из 11 узлов и древовидной
+иерархии с ветвлением 2 показан на рис.\nbsp{}[[fig-tree-hierarchy-11]].
#+name: fig-tree-hierarchy-11
#+begin_src dot :exports results :file build/tree-hierarchy-11-ru.pdf
@@ -3083,14 +3087,6 @@ digraph {
#+RESULTS: fig-tree-hierarchy-11
[[file:build/tree-hierarchy-11-ru.pdf]]
-Поскольку узлу для выбора руководителя нужно соединиться с узлом, адрес которого
-известен заранее, то алгоритм обнаружения масштабируется на большое количество
-узлов. Соединение с другими узлами из ранжированного списка происходит только в
-том случае, если текущим узел-руководитель выходит из строя. Таким образом, если
-адреса узлов кластера расположены плотно в диапазоне адресов подсети, каждый
-узел устанавливает соединение только со своим руководителем, и неэффективного
-сканирования всей сети каждым узлом не происходит.
-
**** Результаты тестирования.
Платформа, на которой осуществлялось тестирование, представляла собой несколько
многоядерных узлов, поверх которых с помощью пространств имен Linux
@@ -3165,6 +3161,14 @@ digraph {
[[file:build/tree-hierarchy-11-ru.pdf]]
**** Обсуждение.
+Поскольку узлу для выбора руководителя нужно соединиться с узлом, адрес которого
+известен заранее, то алгоритм обнаружения масштабируется на большое количество
+узлов. Соединение с другими узлами из ранжированного списка происходит только в
+том случае, если текущий узел-руководитель выходит из строя. Таким образом, если
+адреса узлов кластера расположены плотно в диапазоне адресов подсети, каждый
+узел устанавливает соединение только со своим руководителем, и неэффективного
+сканирования всей сети каждым узлом не происходит.
+
Следующие ключевые особенности отличают наш подход от некоторых предложенных
ранее
подходов\nbsp{}cite:brunekreef1996design,aguilera2001stable,romano2014design.
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -2851,8 +2851,8 @@ guaranteed.
Formula for computing distance can be made arbitrary complex (to account for
network latency and throughput or geographical location of the node), however,
-for its simplest form it is more efficient to use node traversal algorithm
-instead. The traversal requires less memory as it does not store ranked list of
+for its simplest form it is more efficient to use node traversal algorithm. The
+algorithm requires less memory as there is no need to store ranked list of all
nodes, but iterates over IP addresses of the network in the order defined by the
fan-out value. The algorithm is as follows. First, the /base/ node (a node which
searches for its principal) computes its potential principal address and tries
