LLTR Часть 0: Автоматическое определение топологии сети и неуправляемые коммутаторы. Миссия невыполнима?

КДПВ: LLTR Часть 0 - пневмотранспорт из Футурамы


Как построить топологию сети на канальном уровне, если в нужной подсети используются только неуправляемые свитчи? В статье я постараюсь ответить на этот вопрос.


Начну с причины возникновения LLTR (Link Layer Topology Reveal).


У меня был один “велосипед” - синхронизатор больших файлов “на полной скорости сети”, способный за 3 часа целиком залить 120 GiB файл по Fast Ethernet (100 Мбит/с; 100BASE‑TX; дуплекс) на 1, 10, 30, или > 200 ПК. Это был очень полезный “велосипед”, т.к. скорость синхронизации файла почти не зависела от количества ПК, на которые нужно залить файл. Все бы хорошо, но он требует знания топологии сети для своей работы.


Подробнее в статье про него:

Ладно, а зачем понадобилось “гонять” 120 GiB файл по сети на такое количество ПК?

Этим файлом был VHD с операционной системой, программами, и т.п. Файл создавался на мастер‑системе, а затем распространялся на все остальные ПК. VHD был не только способом доставки системы на конечные ПК, но и давал возможность восстановления исходного состояния системы при перезагрузке ПК. Подробнее в статье: “Заморозка системы: история перехода с EWF на dVHD”.



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


Существующие протоколы обнаружения топологии канального уровня (LLDP, LLTD, CDP, …) для своей работы требуют соответствующей поддержки их со стороны всех промежуточных узлов сети. То есть они требуют как минимум управляемых свитчей, которые бы поддерживали соответствующий протокол. На Хабре уже была статья, как используя эти протоколы, “определить топологию сети на уровнях 2/3 модели OSI”.


Но что же делать, если промежуточные узлы – простые неуправляемые свитчи?


Если интересно как это можно сделать, то добро пожаловать под кат. Обещаю наличие множества иллюстраций и примеров.


{ объем изображений: 924 KiB; текста: 69 KiB; смайликов: 9 шт. }


Немного UserCSS перед прочтением

Note: изначально этот спойлер размещался до ката.


Наверняка все, кто хотел настроить стили под себя, уже сделали это. Тем не менее, вот часть моего UserCSS. Основные изменения:


  • виден конец раскрытого спойлера (полезно, когда спойлер большой, и разницу в отступе между основным текстом и текстом в спойлере не сразу замечаешь), точнее вернул прежнюю рамку и фон спойлера;
  • блок цитаты вернул свой прежний вид (я показывал нескольким людям, не понимающим русского языка, и не читающим хабр, новые “желтые цитаты”, и они говорили, что это вставки контекстной рекламы…);
  • основной шрифт, его размер, и межстрочный интервал, также вернулись назад (IMHO, с ними длинный текст воспринимается легче);
  • убран рейтинг публикации и количество просмотров, но оставлено количество добавлений в закладки.


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


@charset "utf-8";

body { font-family: Verdana,sans-serif !important; }
.nav-links__item-link { font-family: Helvetica,Arial,sans-serif !important; }
.comment__message, .comment-form__preview { font-family:Arial !important; }

.post__text { font-size:13px !important; line-height:1.60 !important; }
.post__title-text, .post__title_link { font-family: Tahoma,sans-serif !important; line-height:118% !important; }
.post__title-text { font-size:30px !important; }
.post__title_link { font-size:26px !important; }

/*
.post__text-html p > br:first-child, .post__text p+br { display:none !important; }
.post__text p { margin-bottom: 0.9em; margin-top: 0.9em; }
/* for test: https://habr.com/post/315186  :( */
.post__text br { line-height:normal !important; } /* or 1 ; https://habr.com/company/pt/blog/337450 */

.post__text img { -o-object-fit:contain; object-fit:scale-down; } /* https://stackoverflow.com/questions/787839/resize-image-proportionally-with-css and don't use "height:auto; width:auto;" (example: <img src="img32x32_2x.png" width="16" height="16">)*/

.post__text h1, .post__text h2, .post__text h3 { font-family: Helvetica,Arial,sans-serif !important; }
.post__text h2 { font-size:1.5em !important; }
.post__text h3 { font-size:1.375em !important; }
.post__text h4, .post__text h5, .post__text h6 { font-family: Verdana,sans-serif !important; font-size:1.125em !important; font-weight:bold !important; }
.post__text h5 { color:#3D3D3D !important; }
.post__text h6 { color:#5C5C5C !important; }

.post__text ul li, .post__text ul ul li, .post__text ul ol li, .post__text ol li, .post__text ol ul li, .post__text ol ol li { line-height:inherit !important; padding:0 !important; }
.post__text ul, .post__text ul ul, .post__text ul ol, .post__text ol, .post__text ol ul, .post__text ol ol { margin-left:35px !important; }
.post__text ul ul, .post__text ul ol, .post__text ol ul, .post__text ol ol { margin-bottom:9px !important; }

.post__text .spoiler .spoiler_title { color:#6DA3BD !important; font-size:inherit !important; font-weight:400 !important; }
.post__text .spoiler::before { margin-top:2px !important; }
.post__text .spoiler .spoiler_text { color:#666 !important; background:#F9F9F9 !important; border:1px solid #EEE !important; }
.post__text .spoiler .spoiler_text hr:first-child,
.post__text .spoiler .spoiler_text hr:last-child { display:none !important; }

.post__text code { font-size:13px !important; /*background-color:#F8F8F8 !important;*/ border:1px solid #F2F2F2 !important; border-radius:3px !important; padding:0 0.25em !important; white-space:pre-wrap !important; }
.post__text strong > code { font-weight: normal !important; background-color: #F8F8F8 !important; }
.post__text pre code { line-height:1.5 !important; background-color:#F8F8F8 !important; border-color:#DDD !important; padding:0.5em 1em !important; white-space:pre !important; overflow-x:auto !important; }
.hljs-comment, .hljs-quote { color:#808080 !important; font-style:inherit !important; }
.hljs-doctag,.hljs-keyword,.hljs-formula,
.hljs-section,.hljs-name,.hljs-selector-tag,.hljs-deletion,.hljs-subst { color:#4d7386 !important; }
.hljs-literal{ color:#7296a3 !important; }
.hljs-string,.hljs-regexp,.hljs-addition,.hljs-meta-string{ color:#390 !important; }
.hljs-built_in,.hljs-class .hljs-title{ color:#968e5b !important; }
.hljs-attr,.hljs-attribute,.hljs-variable,.hljs-template-variable,.hljs-type,.hljs-selector-class,.hljs-selector-attr,.hljs-selector-pseudo,.hljs-number{ color:#2f98ff !important; }
.hljs-symbol,.hljs-bullet,.hljs-link,.hljs-meta,.hljs-selector-id,.hljs-title{ color:#968e5b !important; }

.post__text kbd { display:inline-block !important; padding:0.2em 0.5em 0.3em !important; vertical-align:middle !important; background-color:#FCFCFB !important; border:1px solid #D9D9D9 !important; border-radius:3px !important; border-bottom-color:#C6CBD1 !important; box-shadow:inset 0px -1px 0px #C6CBD1 !important; font:11px/10px Tahoma, sans-serif !important; color:#575757 !important; text-shadow:0px 1px 0px #FFF !important; }

.post__text blockquote,
.comment__message blockquote, .comment-form__preview blockquote { background:inherit !important; border-left:0.25em solid #DFE2E5 !important; color:#70767D !important; padding:0 1em !important; }

.post__text .user_link { display:inline-block !important; padding-left:14px !important; color:#666 !important; font:92.4%/1.5em Arial !important; background:url("https://hsto.org/storage/habrastock/i/bg-user2.gif") 0px 60% no-repeat !important; }
.post__text .user_link::before { content:'@' !important; color:transparent !important; position:absolute !important; left:0 !important; }/*for copy-paste (for Opera Presto)*/

.voting-wjt_post>.voting-wjt__counter,
.post-stats__item_views { display:none !important; }


UPDATE: UserJS – Anti-quotes-hell и <code> (см. подробнее в этом комментарии):


// ==UserScript==
// @version     1.0.0
// @namespace   https://habr.com/users/ZiroKyl/
// @homepageURL https://habr.com/post/414799/
// @name        Anti-quotes-hell for Habr
// @include     https://habr.com/post/*
// @include     https://habr.com/company/*/blog/*
// ==/UserScript==

// Enable opera:config#UserPrefs|UserJavaScriptonHTTPS


if(self == top){
    window.opera.addEventListener("BeforeEvent.DOMContentLoaded", function(){ "use strict";
        var code = document.querySelectorAll(".post__text :not(pre) > code");

        var unQuote = function(el){
            var aN = null, a = "",
                bN = null, b = "";

            if((aN = el.previousSibling) && (bN = el.nextSibling) &&
                aN.nodeType == 3         &&  bN.nodeType == 3     ){

                a = aN.data; a = a.charCodeAt(a.length-1);
                b = bN.data; b = b.charCodeAt(0);

                // a != " " && ( a+1 == b && (a == "“"  || a == "‘" )  ||  (a == "«" && b == "»")  ||  a == b && (a == "'" || a == "`" || a == '"') )
                if(a != 32  && ( a+1 == b && (a == 8220 || a == 8216)  ||  (a == 171 && b == 187)  ||  a == b && (a == 39  || a == 96  || a == 34 ) )){
                    aN.data = aN.data.slice(0,-1);
                    bN.data = bN.data.slice(1);

                    return true;
                }
            }

            return false;
        };


        var aN = null, bN = null, pElTagName = "";

        for(var i=code.length;i--;){
            // “<code>...</code>”  ->  <code>...</code>
            if(!unQuote(code[i])                                                                  &&
                ( code[i].previousElementSibling == null && code[i].nextElementSibling == null &&
                  (pElTagName = code[i].parentElement.tagName)                                 &&
                  (pElTagName == "A" || pElTagName == "STRONG")                                 ) &&
                ( (!(aN = code[i].previousSibling) || aN.data.trim().length == 0) &&
                  (!(bN = code[i].nextSibling)     || bN.data.trim().length == 0)  )              ){
                // “<a><code>...</code></a>”     ->  <a><code>...</code></a>
                // “<a> <code>...</code> </a>”   ->  <a> <code>...</code> </a>
                // “<a><code>...</code>...</a>”  -X
                unQuote(code[i].parentElement);
            }
        }
    }, false);
}


Основные стили взял из предыдущих версий Матрицы Хабра:


  • 2012-06 (UserCSS) – основной шрифт Verdana 13px, межстрочный интервал 160%
  • 2012-06 – первое появление спойлера + блок с кодом
  • 2012-04 – таблица + заголовки
  • 2012-05 – больше заголовков
  • 2012-05 – просто хорошая статья
  • 2011-05 — межстрочный интервал 1.54em (в узкой колонке, с пустым пространством слева и справа, текст читается хуже, чем при интервале 160%), блоки с кодом изменили цвет фона и потеряли обводку, (что еще: изменилась “шапка” хабы [одна статья может быть в многих хабах] стали блогами [одна статья может быть только в одном блоге])
  • 2011-01 – содержимое растягивается на всю ширину экрана (в таком формате текст с уменьшенным межстрочным интервалом выглядит оптимально, IMHO), IMHO: широкая правая колонка (при ширине экрана 1600px) создает ощущение уюта, а так же здесь лучше, чем в других версиях выглядят комментарий (подобраны удачные размеры отступов)
  • 2010-08, 2009-12, 2009-05, 2009-03 – изменения на примере одной и той же статьи
  • 2010-02, 2009-06 – статьи с более плотным текстом (более длинные абзацы)
  • 2010-03, 2010-02, 2009-06, 2008-12 – позитивные воспоминания про Opera
  • 2007-12 – Хабразачистка :)и облако тегов в правой колонке
  • 2007-04 – межстрочный интервал еще меньше


Про LLTR я собираюсь написать цикл статей с общей тематикой “как создать протокол”. Это статья – нулевая.


# Аналогия из физического мира – пневмотранспорт


Представим, что у нас есть 2 пневмо-трубы


Фото комнаты с терминалом пневматического трубопровода, и пустыми контейнерами


Одна труба для входящих посылок (красные контейнеры), и одна для исходящих (синие контейнеры).


У нас есть несколько знакомых, которые подключены к этой же системе пневмотранспорта. Мы можем посылать им контейнеры, и они нам могут присылать контейнеры. Адрес доставки контейнера наносится на сам контейнер (например, в RFID или bar‑code).


В какой‑то момент всем захотелось узнать маршрут, по которому каждый день проходят их посылки, и узнать к каким свитчам (коммутационным центрам) подключены их пневмо‑трубы, т.е. узнать топологию пневмо‑сети.


Путь от терминала до комуникационного центра


Все, что можем делать мы и наши друзья – это посылать и принимать контейнеры с неким содержимым.


Предлагаю подумать, как в таком случае можно построить топологию этой сети. Несколько вариантов находятся под спойлером:


спойлер

1. Если трубы прозрачные, как у пневмотранспорта в Футураме (КДПВ), то можно просто отправить видеокамеру, которая заснимет весь путь движения контейнера.


2. Можно расположить в контейнере датчики (гироскоп, компас, акселерометр, …), и построить карту перемещений по собранным ими данным.


3. Можно обойтись и без датчиков, отправляя специальным образом контейнеры, наполненные воздухом. Ниже рассматривается именно этот вариант, т.к. он применим к обычным проводным Ethernet‑сетям.



# LLTR Basic


Возвращаясь к проводным Ethernet‑сетям, напомню о проблеме, благодаря которой LLTR был создан. Проблема подробно описана в разделе “PC подключены к разным switch” статьи про RingSync – это проблема снижения скорости при неправильном построении цепочки пиров в сети с несколькими свитчами. Для правильного построения цепочки пиров нужна информация о топологии сети.


Небольшой пример (проблемы нет):


Диаграмма: RingSync проблемы нет. Примечание: компактно описать нарисованное на диаграмме довольно сложно, поэтому в alt изображений я буду указывать тип изображения и перевод имени файла изображения.


У нас есть 2 свитча (соединенных одним “проводом”), 4 хоста (пира), все соединения дуплексные, и скорость всех соединений одинаковая. Стрелками показан путь движения данных. В данном случае проблемы нет – данные передаются на максимальной скорости сети.


Другой пример (проблема есть):


Диаграмма: RingSync проблема есть


В этом примере цепочка пиров построилась менее удачно (т.к. нам не известна топология сети), что привело к образованию “бутылочного горлышка” (два однонаправленных потока данных в одном соединении) и падению общей скорости передачи данных.


В данном случае решение проблемы (определение топологии сети) кроется в причине необходимости ее решения – в образовании “бутылочного горлышка”. Целиком цепочка проблем выглядит следующим образом: нужно избавиться от “бутылочных горлышек” → нужно построить “правильную” цепочку → нужно определить топологию сети. К слову, мы не будем перебирать все возможные комбинаций цепочки, в поисках цепочки без “бутылочных горлышек” – это слишком долго, вместо этого поступим умнее/хитрее:


Диаграмма: LLTR Basic broadcast


Заполним сеть трафиком – выделим один из хостов под роль источника broadcast трафика. На всех остальных хостах запустим сбор статистики по принятому broadcast трафику. Далее выберем любые 2 не broadcast хоста, и начнем посылать с первого хоста unicast трафик на второй хост. По собираемой на хостах статистике broadcast трафика в этот момент, будет видно, что на некоторых хостах упала скорость получения broadcast трафика – эти хосты, в данном случае, были подключены к правому свитчу. А на всех хостах, подключенных к левому свитчу, скорость получения broadcast трафика не изменилась.


Связь между двумя свитчами стала “бутылочным горлышком”, и позволила выделить все хосты, подключенные к правому свитчу в отдельный кластер.


Note: В обычных случаях принято всеми силами бороться с broadcast, особенно с тем, который “утилизирует всю пропускную способность”, но мы имеем дело с сетью на неуправляемых свитчах, которая возможно не раз страдала от broadcast‑шторма/флуда, и хоть раз в жизни хочется, чтобы такой broadcast принес пользу. Кстати, вполне возможно заменить broadcast на unicast, только такое сканирование займет больше времени. Для пневмотранспорта тоже придется использовать unicast, пока не выпустят установку, клонирующую материю, и не установят ее в каждый коммутационный центр :).


Для построения корректной топологии сети, осталось повторить то же самое для всех возможных комбинации ориентированных пар не broadcast хостов. Что значит “ориентированных пар” – надо посылать вначале unicast трафик из первого хоста на второй, и собрать статистику, а потом поменять направление (трафик из второго в первый), и собрать отдельную статистику по этому варианту.


Количество комбинаций, которые нужно проверить, можно посчитать по формуле n×(n−1) {каждому (n) нужно “поздороваться” со всеми остальными (n−1), даже если с ним ранее они уже здоровались}, где n – количество всех хостов минус один (broadcast хост).


В итоге, вся собранная статистика подается на вход специальному алгоритму (о нем подробнее в одной из следующих статей), который и строит топологию сети (точнее он делает больше – сразу строит правильную цепочку пиров для RingSync).


Кстати, минимальная конфигурация сети, которую целесообразно сканировать состоит из двух свитчей, к каждому из которых подключено два хоста. Что касается скорости broadcast и unicast, то broadcast трафик можно держать в диапазоне 75% - 100% от “чистой скорости передачи данных” (net bitrate; поиск по “Ethernet 100Base-TX”), а unicast в диапазоне 80% - 100%.


А что будет, если убрать один из хостов?

Получится сеть, в которой один свитч, к которому подключены 3 хоста, и в разрез между одним из хостов и свитчем подключен еще один свитч. То есть, в сети находится всего лишь один свитч (вставленный в разрез превратился в “перемычку” – его не считаем), а это идеальный случай для RingSync “бутылочному горлышку” неоткуда взяться. Раз нет проблемы то и нечего устранять :)



# LLTR Advanced


Картинка из теста IQ

НЛОприлетелоиоставилоэтотпробелздесь? Напоминает одну из картинок теста IQ


Как выше было написано, при использовании LLTR Basic нужно n×(n−1) раз сканировать сеть, что приводит нас к O(n2). Для небольшого количества хостов – это не проблема:


  • 4 хоста, n=3 ⇒ 6 сканирований;
  • 30 хостов, n=29 ⇒ 812 сканирований.


Но если у нас 200 хостов, n=199 ⇒ 39 402 сканирования. Дальше еще хуже…


Посмотрим, как можно улучшить ситуацию. Грокнем два простых варианта топологии дерево:


  • звезда из свитчей;
  • последовательное соединение свитчей.

# Топология: “звезда из свитчей”


Диаграмма: LLTR Advanced звезда 0


Ниже пошагово поясняется изображенное на этой картинке действо.


У нас есть 5 свитчей и 12 хостов. Хосты обозначаются кругами [●] внутри свитча, к которому они подключены. Полностью черный свитч – это “корневой” свитч.


Один из хостов выделим под роль источника broadcast трафика (на схеме изображен окружностью [○]).


Если использовать LLTR Basic, то для 12 хостов, n=11 ⇒ нужно 110 сканирований (итераций).


Итерация 1. Выберем один из хостов (обозначен синим кружочком со стрелкой вверх) в качестве источника (src) unicast трафика, и один хост (обозначен синим ) в качестве получателя (dst) unicast трафика. Запустим, в определенный промежуток времени, сканирование и сбор статистики.


Собранная статистика показала падение скорости broadcast трафика на 9‑и хостах. Для наглядности, падение скорости на всех хостах, подключенных к свитчу, обозначается как прямоугольник со стрелкой вниз.


Исходя из выявленного падения скорости, можно распределить хосты по двум кластерам:


  • желтый (первоначальный) – хосты на которых скорость broadcast оставалась близкой к максимуму;
  • зеленый – хосты, на которых было зафиксировано значительное падение скорости broadcast.


Итерация 2. Выберем другие unicast src и dst хосты, и опять запустим сканирование и сбор статистики.


Падение скорости зафиксировано на 3‑х хостах. Сейчас они находятся в зеленом кластере, т.к. в предыдущей итерации на этих хостах тоже было зафиксировано падение скорости. Переместим эти 3 хоста из зеленого кластера в новый красный кластер.


Итерация 3. Опять выберем другие unicast src и dst хосты, и опять запустим сканирование и сбор статистики.


Падение скорости зафиксировано на других 3‑х хостах. Сейчас они находятся в зеленом кластере. Переместим эти 3 хоста из зеленого кластера в новый фиолетовый кластер.


Итог: уже после трех итераций из 110, все хосты были разбиты по кластерам, соответствующим их свитчам. В оставшихся 107 итерациях новых кластеров образовано не будет.


Это был идеальный случай – мы либо знали топологию сети, либо нам очень повезло.


# Интересно, какие могут быть варианты первой итерации?


Вариант 1: “unicast on broadcast sw”. Unicast src расположен на том же свитче, что и broadcast src (также, как и в примере выше на рисунке в итерации 1). Unicast dst располагается на любом другом (не broadcast src) свитче.


Анимация: LLTR unicast расположен на broadcast свитче


Во всех случаях реакция сети на сканирование одинаковая – падение скорости на всех “не broadcast src” свитчах. Это понятно — unicast src вливается в то же начало канала, что и broadcast src – отсюда падение скорости на всех остальных свитчах, и неважно на каком из них находится unicast dst.


Вариант 2: “unicast general”. Unicast src располагается на любом “не broadcast src” свитче. Unicast dst располагается на любом другом (“не broadcast src” и “не unicast src”) свитче.


Анимация: LLTR общий случай unicast


Во всех случаях падение скорости происходит на том из свитчей, на котором был расположен unicast dst. Это же поведение сети было на итерации 2 и 3 (см. рисунок) из примера в начале раздела.


Вариант 3: “unicast to broadcast sw”. Unicast src располагается на любом “не broadcast src” свитче (также как и в варианте 2). Unicast dst расположен на том же свитче, что и broadcast src.


Анимация: LLTR unicast в broadcast свитч


В этих случаях реакция сети на сканирование отсутствует. Если в предыдущих вариантах (1 и 2) создавался новый кластер, то в этом варианте новые кластеры не создаются. Отчасти это плохо – мы не получаем новой информации о топологии сети (на самом деле в некоторых случаях, и если эта итерация не первая, то можно получить немного информации – о местоположении unicast dst).


Вариант 4: “unicast in sw”. Unicast src и dst расположены на одном и том же свитче.


Анимация: unicast внутри свитча


Здесь также сеть никак не реагирует на сканирование, и соответственно нету новых кластеров.


Итог. Варианты 1 и 2 – хорошие, на них сеть реагирует, и дает нам новую информацию о своей топологии. А на основе этой информации создаются новые кластеры.


Варианты 3 и 4 могут сказать только то, что unicast dst находится либо на одном свитче с broadcast src, либо на одном свитче с unicast src. Причем, дать полную информацию за одну итерацию о точном местоположении unicast dst они сами не могут – всегда будет или рядом с broadcast src, или с unicast src. Точное местоположение можно получить, только объединив полученную информацию с информацией из других итераций.


# А был ли выбор unicast src и dst в примере случайным?


Может выбор был не случайным, и в нем есть скрытая закономерность?


Ok, мы только что посмотрели, как сеть реагирует на различные варианты сканирования. Помните пример из начала раздела, возможно, настало время посмотреть на него под “новым углом”, и ответить на вопрос: случайно ли я выбирал unicast src и dst, или схитрил?


Диаграмма: LLTR Advanced звезда 0 - вероятности


Эта картинка аналогична картинке из начала раздела, отличие в том, что к каждой итерации добавились альтернативные варианты выбора unicast src, и кое‑что справа…


Этим “кое‑что” является подсчет вероятности образования нового кластера (количество вариантов, при которых новый кластер создастся, деленное на количество вариантов при которых новый кластер создастся + количество вариантов, не приводящих к созданию нового кластера). Варианты подсчитывались относительно зафиксированного unicast src, и свободного unicast dst. Unicast dst “свободный” – это значит, что рассматривались все возможные варианты его местоположения.


То есть, в примере я специально выбирал те варианты, у которых была наибольшая вероятность образования нового кластера. К сожалению, в реальности такой оценкой (вероятностей) мы не сможем воспользоваться. Не зря в конце я написал:

Это был идеальный случай – мы либо знали топологию сети, либо нам очень повезло.

Однако способность оценивать вероятность образования нового кластера пригодится нам ниже.


# Сканировать внутри кластера, или использовать межкластерное сканирование – вот в чем вопрос…


На примере выше в последней (3‑й) итерации использовалось сканирование между кластерами. Так ли оно хорошо, ведь вначале использовали сканирование внутри кластера?


Note: Если unicast src и dst находятся в одном и том же кластере – это сканирование внутри кластера. Если unicast src находится в одном кластере, а unicast dst в другом – это межкластерное сканирование.


Если посмотреть на вероятности в 3‑й итерации, то у межкластерного сканирования будет 0.60 против 0.30 у сканирования внутри кластера. Вероятность словно говорит нам “используй межкластерное сканирование, бро.”, но стоит ли слепо следовать ее советам?


Note: Использование только одного типа сканирования (или внутри кластера, или межкластерное) – позволит значительно сократить количество итераций.


Если в примере выше, начиная с 4‑й итерации, начать сканировать только внутри кластера, то это займет 20 итераций (3×2 + 3×2 + 2×1 + 3×2), всего получится 23 итерации вместо 110 (как было рассчитано в начале раздела). Если с той же 4‑й итерации, начать использовать только межкластерное сканирование, то это займет 87 итераций (3×(3 + 2 + 3) + 3×(3 + 2 + 3) + 2×(3 + 3 + 3) + 3×(3 + 3 + 2) – 3), всего получится 90 итераций.


Межкластерное сканирование заметно проигрывает, к тому же его нельзя использовать на 1‑й итерации (в этот момент существует только 1 кластер). Если же обратить внимание на 2‑ю итерацию из примера выше, то можно увидеть, что у последнего альтернативного варианта сканирования вероятность образования нового кластера равна 0.00. Полагаю, что ответ на вопрос: “Какой же тип сканирования был у этого альтернативного варианта?”, уже ясен.


# Прелести параллельного сканирования


Если, используя сканирование внутри кластера, получится параллельно запустить сканирование сразу во всех кластерах, то дополнительные 20 итераций (3×2 + 3×2 + 2×1 + 3×2) сократятся до 6 итераций (3×2). При межкластерном сканировании тоже можно получить выигрыш от параллельного сканирования.


Вопрос состоит в том, не будет ли одно сканирование влиять на результаты другого сканирования, будучи запущенными параллельно.


Note: Реакция сети по завершении параллельного сканирования будет одна (единая для всех сканирований), а самих сканирований будет много – сможем ли мы для каждого сканирования однозначно узнать, как сеть отреагировала именно на это сканирование?


Диаграмма: LLTR Advanced звезда параллельное сканирование 0


На примере: слева – параллельное сканирование только внутри кластера; справа, начиная со 2‑й итерации — только межкластерное параллельное сканирование.


Со сканированием внутри кластера все в порядке – после 6‑и дополнительных итераций вся необходимая статистика будет собрана. А вот с межкластерным сканированием проблемы, какие бы мы комбинации unicast src и dst не перебирали, у нас так и останутся только 2 кластера. Одна из причин уже была найдена, когда мы рассматривали альтернативные варианты 2‑й итерации: “вероятность образования нового кластера равна 0.00”.


Межкластерное сканирование отправим “на полку пылится”, и посмотрим на еще один пример параллельного сканирования только внутри кластера. Возможно, в нем будет что‑то интересное…


Диаграмма: LLTR Advanced звезда параллельное сканирование 1


Наши опасения, по поводу влияния одного сканирования на результаты другого, подтвердились. Во 2‑й итерации правое сканирование (“unicast on broadcast sw”: unicast src расположен на том же свитче, что и broadcast src) повлияло на результаты левого сканирования (“unicast in sw”: unicast src и dst расположены на одном и том же свитче).


Сканирование “unicast on broadcast sw” вызвало падение скорости на свитче зеленого кластера, внутри него проходило свое сканирование “unicast in sw”, которое не должно было вызвать падение скорости на свитче. Это все привело к тому, что результаты сканирования “unicast in sw” говорят, что unicast src продолжает находиться в зеленом кластере (причем он там – единственный хост), а 2 остальных хоста зеленого кластера теперь переместились в фиолетовый кластер.


И немного слов про кластер из одного хоста. Если вспомнить из чего должна состоять минимальная конфигурация сети, которую целесообразно сканировать (состоит из двух свитчей, к каждому из которых подключено два хоста), то в ней кластер из одного хоста возможен. Этот кластер “располагается” на свитче, к которому подключен broadcast src. То есть, собранная статистика говорит нам, что broadcast src находится не в желтом кластере, а в зеленом! Этого попросту не может быть.


Note: Если считать, что в нормальной ситуации падение скорости на unicast src не может произойти, и не менять кластер, в котором он находится (даже если падение скорости произошло), то случится все вышеописанное.


Итог: параллельное сканирование в данном виде использовать нельзя.


Вспоминая картинку из IQ теста…


не имеет смысла

Показать бессмысленность обратного сканирования, если прямое сканирование привело к образованию кластера (это пригодится только при межкластерном сканировании…)



# Топология: “последовательное соединение свитчей”


Диаграмма: LLTR Advanced последовательное соединение 0


Правая часть картинки аналогична левой части.


В левой части показан путь unicast (синяя линия) и broadcast (черная линия) трафика, а также уменьшение скорости broadcast трафика (черная линия стала серой). На 5‑й итерации отчетливо видно, что одни линии трафика “соединяют” свитчи выше от их середины, а другие линии – ниже. Если линия нарисована выше середины, то трафик, по этим линиям, движется из правого свитча в левый (↼), иначе (линия ниже середины) – из левого свитча в правый (⇁), т.е. (⇋).


В правой части картинки отображено разбиение хостов на кластеры.


У нас есть 5 свитчей и 15 хостов. Если использовать LLTR Basic, то для 15 хостов, n=14 ⇒ нужно 182 итерации.


Первая и вторая итерация очень схожи. На 1‑й итерации отображено то, что произойдет, если unicast src расположен на том же свитче, что и broadcast src, а unicast dst располагается на любом свитче левее broadcast src свитча. Unicast трафик словно отбрасывает тень (затеняет) на весь broadcast трафик левее broadcast src свитча. Это очень хорошо видно в левой части картинки (черная линия стала серой). На 2‑й итерации отображено то же самое, для случая, когда unicast dst располагается правее broadcast src свитча.


Каждая итерация демонстрирует один из возможных вариантов сканирования. Посмотрим на оставшиеся итерации (варианты сканирования).


Итерация 3. Направление broadcast и unicast трафика не совпадают – реакция сети отсутствует.


Итерация 4. Направление broadcast и unicast трафика совпадают – сеть отреагировала.


Итерация 5. Unicast src и dst находятся по разные стороны от broadcast src свитча – вся та сторона, где находится unicast dst будет затенена (упадет скорость). Стрелка, указывающая на 2‑ю итерацию, как бы намекает на то, что “имеет смысл сканировать только внутри кластера”.


Посмотрим, что может случиться, если сканировать только внутри кластера (2 немного разных примера):


Диаграмма: LLTR Advanced последовательное соединение 1


Ничего плохого не случилось, все прошло хорошо. Советую обратить внимание на 4‑ю итерацию в примере слева (намек на то, где произошло падение скорости, и где образовался новый кластер), и на 1‑ю итерацию в примере справа.


В обоих примерах сбор всей статистики займет 30 итераций ((4) + (3×2 + 3×2 + 3×2 + 2×1 + 3×2)), против 182 итераций при использовании LLTR Basic.


А что у нас с параллельным сканированием?


Диаграмма: LLTR Advanced последовательное соединение параллельное сканирование 0


С левым примером все хорошо, а вот в правом примере что‑то пошло не так. В 3‑й итерации, unicast трафик внутри желтого кластера двигался между двумя свитчами в направлении (↼), совпадающим с направлением broadcast трафика, что привело к затенению всех свитчей левее unicast src свитча желтого кластера. Проблема в том, что левее unicast src свитча желтого кластера проходило еще одно сканирование (в красном кластере), которое было затенено, что и исказило его результаты. В итоге unicast src красного кластера остался в красном кластере, а все остальные хосты красного кластера переместились в оранжевый кластер. В общем, повторилась та же самая проблема, что была и в случае с параллельным сканированием топологии “звезда из свитчей”.


Кстати, про повторение истории, а можно ли в данной топологии провести полноценное сканирование, если к одному из свитчей подключен только один хост? В предыдущей топологии “звезда из свитчей” такое нельзя было сделать…


За основу возьмем удачный пример параллельного сканирования (пример слева), и попробуем изменить конфигурацию сети:


Диаграмма: LLTR Advanced последовательное соединение параллельное сканирование 0 0


На картинке изображена конфигурация сети (2 конфигурации), и построенные кластеры (по окончанию последней итерации).


Как ни странно, в левой конфигурации сети все прошло хорошо – фиолетовый кластер в точности описывает свой свитч, к которому подключен только 1 хост. А вот с правой конфигурацией сети проблема – ни одно из сканирований не смогло выделить крайний левый хост/свитч в отдельный оранжевый кластер.


Так почему же с правой конфигурацией, в которой есть свитч с 1 хостом, возникли проблемы (как и положено, в таком случае), а с левой конфигурацией, в которой также есть свитч с 1 хостом, вдруг все прошло хорошо? В чем отличия между этими конфигурациями?


Отличие простое: в правой конфигурации свитч подключен последним (находится с краю), а в левой конфигурации к свитчу подключается (левее) еще один свитч со своими хостами. Получается, что в конфигурации слева к свитчу подключен не один хост, а сразу 4 хоста (1 напрямую + 3 через другой свитч):


Диаграмма: LLTR Advanced последовательное соединение параллельное сканирование 0 1


Вся иерархия целиком выглядит следующим образом:


Диаграмма: LLTR Advanced последовательное соединение параллельное сканирование 0 2


Поэтому ответ на немного измененный первоначальный вопрос: “Можно ли в данной топологии провести полноценное сканирование, если к одному из свитчей напрямую подключен только один хост?” – да, если свитч не крайний.


На обратной стороне стикера явно что-то есть

НЛОприлетелоиоставилоэтотпробелздесь? Еще одна картинка. К чему бы она здесь… ;)


# TL;DR


Здесь я хотел написать кратко о вышеописанном, но не вышло…


Однако, я понял, что упустил несколько моментов:


  • если в одной сети запустить сразу 2 независимых сканирования/зондирования сети, то ничего хорошего из этого не выйдет – они будут искажать результаты друг друга;
  • во время сканирования/зондирования сети, нагрузка на нее значительно увеличится, поэтому не рекомендуется запускать ее часто (в часы‑пик тоже не стоит запускать).


И во избежание возникновения ассоциаций с одним из рассказов в картинках xkcd, и появления соответствующего комментария к данной блогозаписи, картинки из этого рассказа размещаются здесь(:


Butterfly-зонд

# В следующих частях / To be continued…


  1. Первые шаги в OMNeT++ и INET [tutorial]
  2. Алгоритм определения топологии сети по собранной статистике
  3. OMNeT++ продолжение
  4. Математика
  5. OMNeT++ продолжение 2
  6. Реализация
  7. Эксперимент (название‑спойлер: “в конце Джон умрет”)


Эта часть: в GitHub Pages;
DOI: 10.5281/zenodo.1406970


Про опечатки и другие улучшения…

Если в тексте нашлись ошибки, то можете написать о них в ПМ/ЛС.


Если можете помочь с уменьшением количества текста до ката, сохранив при этом всю вложенную в текст информацию и удобство чтения, то варианты принимаю в тот же ПМ/ЛС.


Если вы считаете что в тексте лучше использовать синоним одного из слов, то тоже можно писать в ПМ/ЛС.


P.S. Раздел про пневмотранспорт вставлен не случайно:


(из “Стражей Галактики” вставить сцены с “Ракетой” (~енотом~), когда он просит принести ногу‑протез для плана побега (и ему приносят ногу), и когда он просит дать глаз для плана атаки в конце фильма (он говорит: “очень важная часть плана”))



P.S. на картинках метки un 7-Zip me стоят неспроста (; обрати внимание на хеш в URI картинок )


P.P.S. в изображениях могут быть спрятаны пасхалки, придающие им глубокий смысл ;)


P.P.P.S. В свете этого скрыл ссылки на внешний ресурс, где я раньше постил статьи под спойлеры, во всех местах кроме одного – там где указывается на конкретный раздел статьи. Если такие ссылки (на статьи) разрешены, то напишите в ПМ/ЛС, уберу из под спойлера – станет удобнее читателям :)


P.P.P.P.S. Ответы на комментарии смогу написать только в небольшой промежуток времени, вечером по Всемирному координированному времени.

Поделиться публикацией
Комментарии 13
    +1
    Для восстановление сети из неуправляемых коммутаторов после грозы потребуется очень много времени и ресурсов! (с) forum.nag.ru
      0
      До середины прочитал и у меня чуть не взорвался мозг, особенно в выборе unicast src и dst или просто конец рабочего дня о себе дает знать.
      Программный сканер-то написали уже? Который бы рисовал гипотетическую топологию?
        0
        Программный сканер-то написали уже?

        Да, про него в следующих частях.
        Следующая часть («Часть 1») выйдет скоро. Надеюсь, что успею ее обработать (сверстать, ...) менее чем за 1 неделю.

        До середины прочитал и у меня чуть не взорвался мозг,… или просто конец рабочего дня о себе дает знать.

        Перед публикацией статьи я давал прочитать ее нескольким людям, и одному из них было трудно воспринять всю информацию за один раз. Тогда я ему посоветовал «забить» на текст и посмотреть на схемы (предварительно прочитав в тексте про обозначения). Это ему помогло.

        P.S. Я и сам представляю (в голове) все это графически (в виде схем, анимаций, ...).
        0

        Прочитал вашу тему про vhd хотел бы использовать ее у себя на работе можете актуализировать статью и или выложить что нового наработанно по данной теме

          0
          Ничего нового за это время не появилось (все и так работает). Несколько раз обновлял bat'ники. В статье все ссылки указывают на последнюю версию.

          P.S. важно понимать, что это только часть защиты, остальную часть я нигде не описывал (часть из нее в принципе не могу описать), но если это все реализовать, то вполне можно использовать такую систему для хакерских конкурсов (поиск по «hacker vs laptop»).
            0
            4 koot
            P.S. важно понимать, что это только часть защиты, остальную часть я нигде не описывал
            Но одно из основных правил очень простое:
            — все, что можно изменить — нельзя выполнить
            и наоборот:
            — все, что можно выполнить — нельзя изменить.

            Стандартными средствами первое решается с помощью ACL в NTFS и политик.
            Второе — с помощью dVHD и ACL в NTFS.

            Под «все, что можно изменить» подразумеваются файлы пользователя, хранящиеся на отдельном разделе (вне VHD).

            Если пользователю все-таки понадобится выполнить один из своих файлов, то для этого я создал symbolic link / junction point (на разделе в VHD), ведущей к директории с файлами пользователя. Важно, чтобы это была не корневая директория, иначе будет трудно корректно настроить наследование прав доступа (ACL в NTFS).
            0

            А также, если ранее не "замораживали системы" (не использовали immutable/non-persistent хранилища для виртуальных машин, или Aufs/UnionFS, или EWF, или Deep Freeze/Shadow Defender/Comodo Time Machine/…), то столкнетесь с одной проблемой, решение которой заключается в заморозке времени системы (восстановление даты после перезагрузки).


            Если не заморозить время (либо периодически не "размораживать" систему), то программы, имеющие встроенный "планировщик заданий" будут со временем все больше и больше тормозить систему.


            Поясню: в таких "планировщиках заданий" задания выглядят примерно так: если с момента предыдущего запуска задания прошло больше двух недель, то "запустить задание" (заданием может быть, например, оптимизация кеша {очистка, перестройка}). А т.к. запись о моменте предыдущего запуска хранится на VHD (перезагрузка системы приводит систему в исходное состояние), то спустя 2 недели после заморозки, задание начнет выполняться после каждой перезагрузки (планировщик обновляет дату последнего запуска задания, но после перезагрузки дата возвращается назад, и планировщик опять запускает задание ...).

            0
            Интересно!
            Но в основе идеи лежат «идеальные» свичи. В то время как реальные коммутаторы доступа имеют производительность того же порядка, что и скорость аплинка.
              0
              Во время создания LLTR (лето 2015) моя реальность выглядела много мрачнее:

              • в основном D-Link DES-1016 (A / B / D) – точной модели уже не помню
              • парочка D-Link DGS-1005D/RU
              • и это ZyXEL ES-116S ...


              Повествование я хотел строить в направлении от абстракций (Часть 0) к реальным условиям (Часть 7), тем самым полностью описав процесс создания LLTR (таким, каким этот процесс был в реальности).

              В этой «нулевой» части всего лишь было «немного» теории с "идеальными условиями":
              … все соединения дуплексные, и скорость всех соединений одинаковая.
              , и встроенным в текст «расширителем кошелка Миллера» (пригодится для следующих частей ;)
              В следующих частях я выложу «нюансы» (но конкретно эти условия сохранятся).

              И да, для описанной конфигурацией коммутаторов доступа (с портом, скорость которого превышает суммарную скорость основных портов):
              коммутаторы доступа имеют производительность того же порядка, что и скорость аплинка
              полную (физическую) топологию сети этим способом не получить (это будет выглядеть как один большой свитч, или несколько, если в сети будут «узкие места»), но оптимальная цепочка пиров все же будет построена, и «полная скорость сети» будет достигнута.
                0
                … но оптимальная цепочка пиров все же будет построена, и «полная скорость сети» будет достигнута.
                Более корректный ответ: в этих условиях можно не получить оптимальную цепочку — придется делать перебор вариантов. Однако предварительное «сканирование» (LLTR) сети позволит (в некоторых случаях) сократить количество перебираемых вариантов.

                Но я не зацикливался на подобных случаях (все равно количество перебираемых вариантов будет велико), оставаясь в пределах оговоренных ограничений:
                … все соединения дуплексные, и скорость всех соединений одинаковая.
                + точность результатов сканирования может уменьшить активность сторонних узлов сети в момент сканирования. Это придется учитывать и подстраиваться, что приведет к усложнению алгоритма работы (выбор параметров сканирования, последовательности сканирования, обработка полученных данных).

                Поэтому «не все сразу» — при создании модели (Часть 1) добавится еще одно ограничение — отсутствие посторонней активности в сети.
              0
              Нужна помощь: следующая часть будет посвящена разработке, но единственный хаб связанный с сетью в потоке разработка называется Mesh-сети (есть еще близкие хабы: Twisted, «Разработка систем связи» и «Системы обмена сообщениями»).
              Нужно выбрать наиболее подходящий хаб для статьи. Точнее наоборот — чтобы статья подходила для читателей этого хаба.

              Прототип (модель) протокола будет создаваться в OMNeT++, в котором также моделируют и Mesh-сети. Однако в моей статье не будет ни слова про Mesh-сети.
              Код в ней будет написан на C++, но эта статья не про язык/стандарт C++.
              В ней будет немного реверс-инжиниринга, но это не основная тема статьи.

              Варианты:

              • разместить в АдминистрированиеСетевые технологии (но статья не относится к администрированию)
              • разместить в РазработкаMesh-сети (и в начале статьи извиниться перед его [хаба] читателями)
              • попросить создать новый хаб, например, Разработка → Сетевые протоколы (но если бы каждый создавал хаб для своей статьи, то получился бы хаос)

              В общем, идеального варианта нет.

              P.S. было бы здорово, если хабы из Администрирования имели зеркальную копию в Разработке, ведь то, что администрируют изначально было кем-то разработано.
                0
                Неделя пролетела незаметноВышла новая часть!

                Она большая, очень большая. Если «Часть 0» (эта часть) занимала 20 страниц, то «Часть 1» занимает 138 страниц (вместе с содержимым спойлеров). Сейчас некоторые сайты показывают время чтения статьи (например: «6-12 мин.»), ну что же, если бы на Хабре было такое поле, то в нем было бы написано «4-6 дн.» … хорошо, что такого поля нет.
                И, т.к. это tutorial, а они обычно предполагают воспроизведение действий читателями, то в конце добавил опрос, чтобы узнать, сколько людей дошли до конца, и пора ли публиковать следующую часть.

                Заодно обновил UserCSS (только с ним я могу читать такие «объемные» тексты).
                Изменений несколько, и все они связаны с <code>.

                Первое изменение можно назвать "Anti quotes-hell".
                Допустим, есть фрагмент кода, который читатель может скопировать и использовать (вставить в командную строку, код программы, …) (эффект лучше заметен, если для основного текста и для inline-<code> используется один и тот же размер шрифта):

                • foo + bar + 19
                • -foo=bar
                • foo + bar & baz + zzz

                Где здесь код, и где текст? Точнее где здесь границы кода?

                Чтобы границы были лучше видны, я заключаю блоки кода в кавычки:

                • foo + bar +” 19
                • -foo=bar
                • foo + bar” & “baz + zzz

                Но как это будет выглядеть, если сам блок кода содержит кавычки в начале и конце (например, чтобы показать, что число надо задавать в виде строки):

                • "8"
                • "foo" + "bar"
                • "6" + "9" == "69"

                Слишком много кавычек. При большой концентрации кавычек в тексте они перестают помогать и начинают отвлекать. Получается рябь/мусор из кавычек.

                Поэтому я (как читатель) предпочитаю подсвечивать фон и границы блоков кода. У меня это настроено в стилях браузера (UserCSS).

                Поэтому я (как писатель) предпочитаю, вместо задания визуального представления (использования кавычек) в разметке — разделять разметку и оформление (подсвечивание фона и границ блоков кода). То есть писать так:

                • foo + bar + 19
                • -foo=bar
                • foo + bar & baz + zzz

                И как раз здесь возникает проблема, если начальные стили сайта (AuthorCSS) не задавали фон/границу для внутристрочных блоков кода, и заходит читатель, который в своем UserCSS не задает оформление внутристрочных блоков кода.

                Поэтому мне (как писателю) приходится добавлять кавычки (получая в итоге «quotes-hell»), и (как читателю) использовать UserJS, который убирает обрамляющие блоки кода кавычки.



                Второе изменение убирает фон у внутристрочных блоков кода.
                Если сравнить два представления одного и того же текста: одно — оригинальное (без UserCSS; без затенения фона у <code>), другое — измененное (с UserCSS), то в измененном варианте <code> начинают акцентировать на себя внимание. Но автор текста не хотел делать акцент на всех <code>! Для создания акцента он использует <strong><em>).

                Решение проблемы: убрать затемнение фона, но оставить чуть заметный border.
                Кстати, после этого изменения, кажется что <code> дополнительно подсвечены изнутри, т.е. кажется, что их фон ярче, чем фон обычного текста.

                И что самое приятное — теперь мы можем при помощи затемнения фона создавать акцент на выборочных <code> с использованием разметки: <strong><code>...</code></strong>!

                Похоже, в GitHub при создании help.github.com задумались об этом, и пришли к тому же выводу. И дополнительно добавили изменение цвета border для случая <a><code>...</code></a> — я попробовал добавить это в UserCSS, и оказалось, что при большой концентрации code-ссылок в абзаце — они начинают отвлекать.

                Еще один нюанс (если не устали читать этот поток мыслей)
                Иногда авторы используют внутристрочные блоки кода (<code>) для разметки многострочных фрагментов (либо для вывода не кода моноширинным шрифтом), вместо использования <source> или <pre>. При этом код начинает выглядеть как «многострочная колбаска»…

                В этом случае поможет «анти-колбасочный стиль»: с border-top-style: none; и border-bottom-style: none;. С ним и границы кода видны, и нет «колбасок». Но в своем UserCSS я не использую его — мне нравится полный вариант border.

                P.S. для разметки не кода подходит тег <samp>.
                P.P.S. мне вначале показалось, что на help.github.com тоже используется <samp> для вывода «терминала», но оказалось, что там просто использовали <pre class="command-line">.


                  0
                  Похоже, через Yandex многие ищут «OMNeT++ учебник на русском» (запрос подсказки для "OMNeT++"):
                  (
                      GET /suggest-opera?part=OMNeT%2B%2B&n=5 HTTP/1.1
                      Host: suggest.yandex.ru
                      Accept-Language: ru
                  )(
                      ["omnet++",["omnet++","omnet++ учебник на русском", ...]]
                  )

                  В Google тоже есть похожие запросы:
                  (
                      GET /complete/search?q=OMNeT%2B%2B&client=opera&hl=ru HTTP/1.1
                      Host: clients1.google.com
                      Accept-Language: ru
                  )(
                      ["OMNeT++",[4x...,"omnet++ на русском","omnet++ installation guide",...]]
                  )

                  Вполне подходящие название для «Часть 1»: это tutorial (учебник), он про OMNeT++, и он написан кириллицей :-)
                  Да будет так: "OMNeT++ учебник на русском".

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое