Что такое петля в информатике

Как найти петлю в локальной сети и как ее оперативно устранить

Сетевая петля — на самом деле , опасная штука. Очень часто ее появление связано с неправильным подсоединением линков маршрутизаторов или коммутаторов. Реже она случается из-за неверных настроек маршрутного адреса.

Как найти такую петлю, мы разберем чуть ниже. Но в целом предугадывать возникновение таких петель не получается. Ее наличие становится видимым , уже когда проявляются признаки зацикливания или когда уже полностью «ложится» вся наша сеть.

Как образуется сетевая петля

Если посмотреть на принцип «сетевой петли», то для большего понимания скажем, что это когда пакет каких-либо данных долго блуждает по одному и тому же маршрутному кругу от коммутатора к коммутатору и никак не может достичь своего конечного получателя. От этого с лучается перегрузка сети и она «ложится» , т ак как становится просто перегруженной IP-пакетами, которые не перестают множит ь ся из-за коммуникации между сетевыми устройствами. Но пакеты не покидают маршрутную сеть, а блуждают внутри сетевой петли, так и образуется сетевой шторм.

Плюс, так как внутри локальной сети присутствует большое количество зацикли в шихся пакетов, то достаточно сильно снижается пропускающая способность всего канала связи. Но это тоже еще не все. Если у вас довольно большая сеть, то могут случиться проблемы и на других участках. Одна немного приятная новость, что возникшее зацикливание не вечно, жизнь самих сетевых пакетов ограничена по времени.

Как определить сетевую петлю по ее признакам

1. TTL — это временное ограничение жизни сетевого пакета;
2. IP ID — это и так понятно.

Как найти сетевую петлю в локальной сети

1. Первое , что нужно сделать , — это определить локальный участок, где происходит зацикливание. Определить н ет рудно — там возникают проблемы с И нтернетом.
2. Подберите любой сниффер и можете его запускать для определения зацикленных устройств.
3. Определите сетевые пакеты, создающие шторм , и отфильтруйте их. Найти их будет н ес ложно — их огромное количество и у многих схожий ID IP.

Мы будем очень благодарны

если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.

Петля в локальной сети: что такое и как найти

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

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

Пример петли в локальной сети

С петлей мне пришлось столкнуться в одной средней размеров конторе по долгу службы. Офис там располагался в видавшем виде здании, по-моему, даже частично или полностью деревянном. Сетевое оборудование было соответствующее, поэтому, когда в один не слишком добрый понедельник мне заявили о медленном Интернете, я, поначалу, не придал этому особого значения. Затем отвалились и Интернет, и 1С.

Поняв, что проблема, скорее всего, в неисправности коммутатора или кольце, я отправился в коммутационную. Там меня ждали три неуправляемых D-Link’а (это не оскорбление, а вполне себе термин для коммутатора).

Поначалу я всё же думал на неисправность коммутатора (тем более, что есть у меня субъективное недоверие к D-link). Количество портов трех 24-портовых коммутаторов для небольшого офиса на 10-15 машин было излишним, и оставалось еще от старых-добрых времен, когда компов в сетке было больше. Для вычисления виновника я по очереди выключал коммутаторы, и смотрел как на это отреагирует сеть. После нахождения нужного мне свича, все пользователи были переведены на оставшиеся два коммутатора, а я стал думать как вычислить нужный мне порт, ведь неисправен мог быть не весь коммутатор. Тогда ко мне и закралась мысль о кольце.

Первым делом я стал проверять, не может ли быть так, что один и тот же патч-корд воткнут обоими концами в один свич. Мне повезло, и такой кабель действительно был. Это вполне могло быть «подарком» предыдущего админа, чем-то не сошедшегося с руководством. Во всяком случае, вряд ли бы кто-то полез к свичам случайно.

Если бы кольцо не было таким явным, мне пришлось бы помучиться. Дело в том, что я выключил коммутатор, и повторного появления кольца нужно было бы подождать. Потом пришлось бы доставать из портов патч-корды и смотреть на реакцию сети. В целом, всё равно всё свелось бы к схеме, нарисованной выше, с её сетевыми розетками и патч-панелями.

Итак, несколько советов как вычислить петлю в локальной сети:

1. Локализуйте проблему. Падает вся сеть или отдельный участок? Если у одного отдела сеть есть, а у другого нет, то проверяйте коммутатор, раздающий сеть на тот отдел.
2. Какой тип коммутатора(-ов) используется? Это может быть управляемый коммутатор или неуправляемый. В проблемном участке может быть и смесь из обоих вариантов. В случае с неуправляемым коммутатором придется вычислять проблемный порт методом научного тыка. В управляемом коммутаторе порты можно закрыть через веб-интерфейс.
3. Проверьте кабели. Скорее всего, дело всё-таки в физическом закольцевании сети. Но может «сдуреть» отдельно взятый порт в коммутаторе или сетевой плате компьютера. Редко, но может встретиться ситуация с дублированием функций DHCP-сервера, когда устройство (роутер, коммутатор или компьютер), которое этого делать не должно, раздаёт остальным некорректные настройки сети. В таком случае выключите DHCP-сервер и попробуйте получить адрес с какого-либо компьютера в проблемном участке сети. Если опасения подтвердились — проверяйте устройства на предмет включения функции DHCP-сервера. В первую очередь, конечно, роутеры и коммутаторы.

На этом, пожалуй, всё, что нужно знать о тактике борьбы с петлями в локальных сетях. Напоследок еще можно дать совет — пользуйтесь управляемым оборудованием. Это существенно облегчает труд системного администратора и позволяет решать ряд проблем, вообще не вставая из-за стола.

Образование петли и нарушение работоспособности локальной сети с помощью программного обеспечения GNS3

Дисклеймер : Мы не несем ответственность за Ваши действия и не призываем Вас к каким-либо действиям! Все материалы взяты с открытых источников, опубликованы для образовательных целей.

Оглавление

1. Широковещательный шторм в состоянии петли
2. Методы предотвращения
3. Создание широковещательного шторма (петли)
4. LLMNR
5. Анализ последствий

1. Широковещательный шторм в состоянии петли

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

Рис.1 Пример петли в локальной сети

Рис. 2 Пример топологии сети

Пример топологии, рассматриваемой сети, изображен на рисунке 2.

Компьютер ПК-1 отправляет кадр (frame) по сети через коммутатор компьютеру ПК-N. Коммутатор получает кадр и в таблицу коммутации заносит адрес компьютера ПК-1 с портом. Коммутатор не знает где расположен порт получателя кадра, кроме порта, из которого этот кадр был получен. Соответственно, кадр получает ПК-N и получает виртуальный коммутатор GNS3 (далее будет подробно показано, как реализовать виртуальную сеть с помощью GNS3). Виртуальный коммутатор GNS3, который расположен в ПК-N, производит аналогичные действия. Компьютеры расположенные в локальной сети получают несколько кадров — один от коммутатора локальной сети, другой от виртуального коммутатора. Одновременно с этим, копию кадра от коммутатора локальной сети получает виртуальный коммутатор GNS3. Так как для виртуального коммутатора копия является “новым” кадром, то он производит стандартный процесс коммутации кадра. Тем самым происходит бесконечное циркулирование кадра между сегментами сети.

2. Методы предотвращения

Единственной возможностью прекратить циркулирование фрейма между сегментами сети является выключение одного из каналов связи между ними. Данную функцию реализует протокол STP, который оставляет между сегментами только один возможный канал связи между сегментами сети.

3. Создание широковещательного шторма (петли)

Рассмотрим проблему создания петли в сетевом программном эмуляторе GNS3 . GNS3 позволяет комбинировать виртуальные и реальные устройства, используемые для моделирования сложных сетей. Он использует программное обеспечение эмуляции Dynamips для имитации Cisco IOS . Для создания петли воспользуемся одним из способов подключения GNS3 к реальной физической сети. Этот способ возможен, если компьютер подключен к коммутатору (к локальной сети). Схема изображена на рисунке 3.

Рис. 3 Схема соединения 2 хостов и 1 коммутатора

У хостов в качестве интерфейса указываем “ nio_gen_eth:Ethernet N ”.

Перед этим проведем анализ трафика в сети с помощью ПО Wireshark (рис. 3).

Рис.4 Анализ трафика в сети с помощью Wireshark

В среднем в сети проходит 5-10 пакетов в секунду. Основной пакет — это LLMNR , который в последствии будет являться причиной нарушения работоспособности коммутатора. Сначала стоит разобрать сам протокол LLMNR .

4. LLMNR

LLMNR , англ. Link-Local Multicast Name Resolution — протокол стека TCP/IP , основанный на формате пакета данных DNS , который позволяет компьютерам выполнять разрешение имен хостов в локальной сети. Для LLMNR выделены порты 5355/UDP и 5355/TCP, в IPv4 выделен широковещательный адрес 224.0.0.252 и MAC-адрес 01-00-5E-00-00-FC, в IPv6 — FF02:0:0:0:0:0:1:3 (сокращённая запись — FF02::1:3) и MAC-адрес 33-33-00-01-00-03.

Рис. 5 Структура заголовка пакета LLMNR

Служба LLMNR ( Link-Local Multicast Name Resolution ) позволяет организовать одноранговое разрешение имен в пределах одной подсети для IPv4 , IPv6 или обоих видов адресов сразу без обращения к серверам, на что не способны ни DNS , ни WINS . WINS предоставляет как клиент-серверную, так и одноранговую службу разрешения имен, но не поддерживает адреса IPv6 . DNS , с другой стороны, поддерживает оба тина адресов, но требует наличия серверов. Разрешение имен LLMNR , работает для адресов IPv6 и IPv4 в тех случаях, когда другие службы разрешения имен недоступны, например, в домашних сетях, в небольших предприятиях, во временных сетях или корпоративных сетях, где по каким-то причинам недоступны DNS -службы. Поскольку трафик LLMNR не проходит через маршрутизаторы, вы не рискуете случайно заполнить им сеть.Как и WINS , LLMNR позволяет преобразовать имя хоста в IP -адрес. По умолчанию LLMNR включен на всех компьютерах под управлением Windows . Эти компьютеры прибегают к LLMNR , если попытки узнать имя хоста через DNS окончились неудачей. В результате, разрешение имен в Windows работает следующим образом:

1. Хост посылает запрос на первичный DNS -сервер. Если он не получает ответа или получает сообщение об ошибке, он по очереди посылает запросы на все вторичные DNS — серверы. Если и это не помогло, разрешение имени передается LLMNR .
2. Хост посылает многоадресный UDP -запрос, запрашивая IP -адрес для нужного имени компьютера. Этот запрос идет только по локальной подсети.
3. Каждый компьютер локальной подсети, поддерживающий LLMNR и сконфигурированный для ответа на поступающие запросы, сравнивает имя со своим хост-именем. Если они не совпадают, компьютер отбрасывает запрос. Если имена совпадают, компьютер пересылает исходному хосту одноадресное сообщение с ІР -адресом.

5. Анализ последствий

Компьютеры с LLMNR должны проверять уникальность своих имен в подсети. В большинстве случаев это происходит при запуске, восстановлении из спящего режима или при смене параметров сетевого интерфейса. Если компьютер еще не проверил уникальность своего имени, он должен указывать это в ответе на запрос. После создания петли в GNS3 (рис. 3), увидим некоторые особенности в Wireshark (рис. 6).

Рис. 6 Количество пакетов в сети

Рис. 7 Загруженность пропускной способности канала передачи

Рис. 8 Отключение сетевых дисков №1 и №2

Рис. 9 Анализ трафика с помощью Wireshark после создания петли

После создании петли сразу же в сети наблюдается рост количества пакетов к экспоненциальному росту их числа и парализует работу сети. Это состояние в сети называется широковещательный шторм. Широковещательный шторм — лавина широковещательных пакетов (на втором уровне модели OSI — кадров). Считается нормальным, если широковещательные пакеты составляют не более 10 % от общего числа пакетов в сети.Довольно часто к широковещательному шторму приводят петли в сети при неправильной настройке канального протокола Spanning Tree . Spanning Tree Protocol (STP) — канальный протокол. Основной задачей STP является устранение петель в топологии произвольной сети Ethernet, в которой есть один или более сетевых мостов, связанных избыточными соединениями. STP решает эту задачу, автоматически блокируя соединения, которые в данный момент для полной связности коммутаторов являются избыточными.

Учитель информатики

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

Графы

Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)

§17. Графы.

Что такое граф?

Ключевые слова:

Давайте подумаем, как можно наглядно представить такую информацию:

От пос. Васюки три дороги идут в Солнцево, Грибное и Ягодное. Между Солнцевом и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное.
Нарисуйте в тетради схему дорог по этому описанию.

Можно, например, нарисовать такую схему (рис. 3.17, а).

Рис. 3.17

В информатике для исследования таких схем используют графы.

Граф — это набор вершин (узлов) и связей между ними — рёбер.

Граф, соответствующий нашей схеме дорог, показан на рис. 3.17, б, для краткости населённые пункты обозначены латинскими буквами.

Матрица смежности графа

Для хранения информации об узлах и связях показанного выше графа можно использовать таблицу такого вида (рис. 3.18).

Рис. 3.18

Единица на пересечении строки А и столбца В означает, что между вершинами А и В есть связь. Ноль указывает на то, что связи нет. Такая таблица называется матрицей смежности. Она симметрична относительно главной диагонали (см. закрашенные клетки в таблице).

Исследуйте матрицу смежности и сравните её с графом на рис. 3.17, б. Что означает единица на пересечении столбца С и строки С?

В этом графе есть петля — ребро, которое начинается и заканчивается в одной и той же вершине.

Степенью вершины называют количество рёбер, с которыми связана вершина. При этом петля считается дважды (с вершиной связаны оба конца ребра!).

Подсчитайте по матрице смежности, сколько ребёр в графе. Определите степени всех вершин. Как вы рассуждали?

Строго говоря, граф — это математический объект, а не рисунок. Конечно, его можно нарисовать на плоскости (например, как на рис. 3.17, б), но матрица смежности не даёт никакой информации о том, как именно располагать вершины друг относительно друга. Для таблицы, приведённой выше, возможны, например, такие варианты (рис. 3.19).

Рис. 3.19

Нарисуйте по матрице смежности (рис. 3.20) два разных изображения графа.

Рис. 3.20

Граф имеет 4 вершины, причём каждая вершина связана рёбрами со всеми остальными. Нарисуйте этот граф. Сколько всего рёбер в этом графе?

Граф имеет N вершин, причём каждая вершина связана рёбрами со всеми остальными. Сколько всего рёбер в этом графе?

Граф имеет 4 ребра. Чему равна сумма степеней вершин в этом графе? Зависит ли она от количества вершин?

Граф имеет N рёбер. Чему равна сумма степеней вершин в этом графе?

Попробуйте нарисовать граф с пятью вершинами, где все вершины имеют степень 3. Получилось ли у вас? Почему?

Связный граф

В графе на рис. 3.17, б все вершины связаны: между любой парой вершин существует путь — последовательность вершин, в которой каждая следующая связана ребром с предыдущей. Такой граф называется связным.

Связный граф — это граф, между любыми вершинами которого существует путь.

Теперь представьте себе, что дороги Васюки-Солнцево, Васю- ки-Грибное и Грибное-Ягодное завалило снегом (или размыло дождём) так, что по ним ни пройти, ни проехать (рис. 3.21).

Рис. 3.21

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

Постройте матрицу смежности графа, изображённого на рис. 3.21.

Граф имеет 4 вершины и две компоненты связности. Какое наибольшее количество рёбер может быть в этом графе, если в нём нет петель? Нарисуйте этот граф.

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

Найдите все циклы в графе на рис. 3.17.

Дерево — это связный граф, в котором нет циклов.

Взвешенный граф

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

Рис. 3.22

Взвешенный граф — это граф, с каждым ребром которого связано некоторое число — вес ребра.

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

Как хранить информацию о таком графе? Ответ напрашивается сам собой — нужно в таблицу записывать не 1 или 0, а вес ребра. Если связи между двумя узлами нет, на бумаге можно оставить ячейку таблицы пустой, а при хранении в памяти компьютера записывать в неё условный код, например, число -1 или очень большое число. Такая таблица называется весовой матрицей, потому что содержит веса рёбер. В данном случае она выглядит так (рис. 3.23).

Рис. 3.23

Так же как и матрица смежности, весовая матрица симметрична относительно диагонали.

Что означают пустые ячейки в весовой матрице?

Как по весовой матрице сразу определить, сколько рёбер в графе?

Определите по весовой матрице (рис. 3.24) длины путей ADBEC, ABDCE, DEBAC. Как вы рассуждали?

Рис. 3.24

Оптимальный путь в графе

Для того чтобы определить оптимальный (наилучший) путь между двумя вершинами графа, нужно ввести какой-то числовой показатель, по которому можно сравнивать пути — определять, какой из них лучше. Обычно для оценки пути используют сумму весов ребёр, входящих в этот путь. Например, при поиске кратчайшего пути чем меньше это значение, тем лучше.

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

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

Рис. 3.25

Найдём наилучший путь из А в В — такой, при котором общая стоимость поездки минимальная.

Для решения задачи будем строить дерево перебора вариантов. Видим, что из пункта А напрямую

Рис. 3.26

Числа около рёбер обозначают стоимость поездки по этому участку, а индексы у названий узлов показывают общую стоимость проезда в данный узел из узла А. Теперь разберём варианты дальнейшего движения из узла С I tM lt;pb р (рис. 3.27).

Рис. 3.27

Почему, на ваш взгляд, на схеме не показана возможность движения из С в А?

Видим, что из С сразу можно попасть в В, стоимость проезда в этом случае равна 7.

Почему нельзя на этом остановиться, ведь путь из А в В найден?

Проверяя пути через узел В, выясняем, что можно сократить стоимость до 6 (рис. 3.28)

Рис. 3.28

Нужно ли исследовать дальше путь, содержащий цепочку ACED? Сравните стоимость этого пути и стоимость уже найденного пути из А в В.

Аналогично строим вторую часть схемы (рис. 3.29).

Рис. 3.29

Таким образом, оптимальный (наилучший) путь — ADEB, его стоимость — 3.

Нужно ли проверять пути ACED и ADEC, не дошедшие до узла В? Могут ли они улучшить результат?

Конечно, для более сложных графов метод перебора работает очень долго, поэтому используются более совершенные (но значительно более сложные) методы.

Ориентированный граф

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

Ориентированный граф (орграф) — это граф, в котором каждое ребро имеет направление.

Орграф может служить, например, моделью системы дорог с односторонним движением. Матрица смежности и весовая матрица для орграфа уже не обязательно будут симметричными.

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

Рис. 3.30

Рёбра в орграфе называют дугами. Дуга, в отличие от ребра, имеет начало и конец.

Нарисуйте граф по весовой матрице, показанной на рис. 3.31. С помощью дерева перебора найдите все возможные пути из вершины А в вершину Е, не проходящие дважды через одну и ту же вершину, и стоимости проезда по каждому из этих путей. Определите оптимальный путь из вершины А в вершину Е.

Рис. 3.31

Количество путей

Определим количество возможных путей из вершины А в вершину К для ориентированного графа, показанного на рис. 3.32.

Рис. 3.32

Так как граф ориентированный, переходить в другую вершину можно только по стрелкам.

В графе на рис. 3.32 есть одна начальная вершина А, из которой дуги только выходят. Такая вершина называется истоком. Вершина, в которую дуги только входят (и ни одна не выходит), называется конечной вершиной или стоком. В нашем графе сток — это вершина К.

По весовой матрице на рис. 3.31 найдите исток и сток в графе. Как вы рассуждали?

Будем двигаться по стрелкам от начальной вершины А. Около каждой вершины запишем количество возможных путей из вершины А в эту вершину. В вершину А существует единственный путь — пустой (никуда не ехать). Найдём все вершины, в которые можно приехать только из А: это вершины Б и Г, записываем около них количество путей 1 (рис. 3.33).

Рис. 3.33

Теперь ищем вершины, в которые можно попасть только из уже отмеченных вершин. Например, в вершину В есть один путь из А напрямую, а также по одному пути через Б и Г (так как эти вершины отмечены числом 1). Общее количество путей из А в Б равно сумме отметок предыдущих вершин: для вершины В получаем 3 пути. В вершину Ж можно попасть только из Г, поэтому число путей в Г и Ж совпадает (рис. 3.34).

Рис. 3.34

В вершину Д идёт один путь через Б и три пути через В, поэтому общее число путей — 4. Аналогично получаем 4 пути в вершину Е: 3 пути через В и один через Ж (рис. 3.35).

Рис. 3.35

Далее находим один путь из А в И (только через Ж) и 4 пути из А в 3 (все через Д). В конечную вершину К можно приехать через вершины Д (4 пути), 3 (4 пути), Е (4 пути) и И (1 путь), таким образом, общее количество различных путей равно 13 (рис. 3.36).

Рис. 3.36

Выводы

• Граф — это набор вершин (узлов) и связей между ними — рёбер.
• Матрица смежности — это таблица, в которой единица на пересечении строки и столбца обозначает ребро между соответствующими вершинами, а ноль — отсутствие ребра.
• Связный граф — это граф, между любыми вершинами которого существует путь.
• Цикл — это замкнутый путь в графе.
• Дерево — это связный граф, в котором нет циклов.
• Взвешенный граф — это граф, с каждым ребром которого связано некоторое число — вес ребра. Взвешенный граф описывается весовой матрицей.
• Ориентированный граф (орграф) — это граф, в котором каждое ребро имеет направление. Рёбра орграфа называют дугами. Матрица смежности и весовая матрица орграфа могут быть несимметричными.

Нарисуйте в тетради интеллект-карту этого параграфа.

Вопросы и задания

1. Можно ли сказать, что лес (множество деревьев) — это граф? Почему?
2. Как по матрице смежности определить, есть ли петли в графе?
3. Как по весовой матрице определить длину пути в графе?
4. Когда для представления данных используются орграфы? Приведите примеры.
5. Выполните по указанию учителя задания в рабочей тетради.

Подготовьте сообщение

а) «Задача о Кёнигсбергских мостах»
б) «Решение логических задач с помощью графов»