Вычисление минимального дерева для передачи файлов

Question

Я создаю систему обмена файлами, которая должна передавать один файл нескольким узлам.Один единственный корневой узел имеет весь файл и должен передать его всем другим узлам.Как лучше всего построить дерево передачи файлов, чтобы общее время ожидания было минимальным?

Например:

В этом дереве нам нужно подождать4 раза до окончания передачи.

Эти два варианта лучше, поскольку нам нужно только три раза дождаться завершения передачи.

Answer 1

Я полагаю, что оптимальный алгоритм (в условиях ограничения одновременной отправки и получения, как указал Стив) должен начинаться с помещения log2(n) узлов под корень.Тогда для каждого узла у него должно быть количество дочерних элементов, которое имеет его родительский минус слева направо, среди своих ближайших братьев и сестер (т.е. не смотря на дочерних элементов родителя).

Answer 2

Ответ легче получить, если представить, что 2-й и последующие дочерние элементы данного узла на самом деле являются цепочкой потомков первого дочернего узла, так что, например,

     O
    /|\
   / | \
  /  |  \
 O   O   O

фактически представляется как

     O
    /
   /
  /
 O===O===O

(я представляю ребра "sibling-of" как ===.) В этом новом представлении каждый узел, кроме корня, может иметь не более 2 дочерних элементов: один является его фактическим первым дочерним элементом,и другой, являющийся его первым родным братом направо.(Корень не может иметь братьев и сестер, поэтому он будет иметь не более одного дочернего элемента.) Например, второе дерево в записи OP,

         O
        / \
       /   \
      /     \
     O       O
    / \
   /   \
  /     \
 O       O

, может быть представлено в представлении "sibling-edge" как

         O
        /
       /
      /
     O=======O
    /
   /
  /
 O=======O

Хитрость в том, что передачи обоим дочерним узлам будут происходить одновременно.Это позволяет нам визуально упорядочить дерево так, чтобы все узлы, которые передаются в одно и то же время, находились в одной вертикальной позиции.Теперь мы получаем:

0            O
            /
           /
          /
1        O
        / \\
       /   \\
      /     \\
2    O       O
      \\
       \\
        \\
3        O

Чтобы выяснить максимальное количество узлов, которые могут быть перенесены к времени t, нам нужно дерево в приведенном выше макете, нижний элемент которого (t й) строка не содержит пробелов.Давайте назовем это максимальное количество узлов m(t).Для t> 1 мы можем построить такое дерево, взяв дерево максимального размера для t-1 и создав 2 дочерних элемента (= 1 дочерний элемент и 1 дочерний элемент в исходном дереве) для каждого крайнего правого узла.Табулирование нескольких значений m(t) дает нам:

t      Total        Rightmost
       nodes        nodes

0      1            1
1      1+1*1=2      1 (only multiply by 1 because the root can't have siblings)
2      2+1*2=4      2
3      4+2*2=8      4
4      8+4*2=16     8

Ясно, m(t) = 2^(t-1), что имеет смысл, потому что это оптимальное дерево - просто полное двоичное дерево с небольшим «стволом» наверху длякорневой узел.

Из этого следует, что если число узлов n является степенью 2, оптимальное дерево для n = 2^t узлов требует t+1 времени, а если нет, оно будетпотребуется на 1 единицу времени больше, чем следующая меньшая степень 2. Таким образом, количество времени, необходимое для отправки на n узлы, составляет roundup(log2(n)) + 1.

Чтобы реализовать фактическое дерево связи, теперь вы можете преобразоватьребра "sibling-of" возвращаются в ребра между родительским узлом левого узла и правым узлом.Это показывает, что для количества узлов степени 2 число ребер, выходящих из корня, будет таким же, как и общее необходимое время (roundup(log2(n)) + 1).Число ребер, выходящих из 1-го дочернего элемента любого узла, всегда на единицу меньше, чем у его родителя, а количество ребер, выходящих из каждого 2-го и последующего дочернего элемента, всегда на единицу меньше, чем его левый брат.

Answer 3

Представьте себе кролика, который порождает другого кролика.Эти двое порождают еще двух кроликов, и эти четверо порождают еще четырех кроликов ... Теперь дерево кроликов с ребром, представляющим отношения родитель-потомство, имеет несколько своеобразную форму.Корневой узел имеет степень D = log2 (n).Потомки корня (D из них) имеют градусы от 0 до D-1.Фактически, каждый узел со степенью X имеет X подузлов со степенями от 0 до X.

Можно сказать, что это "фрактальное дерево", совершенное в своей "несбалансированности".предполагая, что скорость загрузки каждого узла равна скорости загрузки каждого узла.В реальном мире это не так, поэтому вам действительно нужно пересмотреть (снова) вашу первоначальную проблему: -)

Answer 4

По поводу комментария Стива Джессопса;почему бы просто не использовать BitTorrent или тому подобное?(т.е. хорошо протестированная, хорошо развернутая инфраструктура, построенная на известной хорошей платформе и которая практически не требует от вас работы?)

Клиент BT можно легко изменить, чтобы он принимал некоторую форму аутентификации, если это то, чтотребуется.

Редактировать: ответ пользователя хороший;log2(n) вероятно оптимальное количество клиентов; при условии, что у каждого клиента одинаковая полоса загрузки .

Однако на практике;вероятно, самая быстрая отправка всего, что вы можете, каждому клиенту напрямую, пока ваша трубка позволяет, и затем стремиться к log2(n) как к максимальному количеству клиентов, получающих в любой момент времени.Если ваш канал в n раза больше максимальной скорости загрузки любого отдельного клиента, это самый быстрый способ.( Редактировать: Предполагая, конечно, что вы можете отправлять нескольким клиентам одновременно. Но это само собой разумеющееся, верно?;)