Что такое петля в информатике
Перейти к содержимому

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

  • автор:

Петля (граф)

Петля́ в графе — ребро, инци­дентное одной и той же вершине.

Строго говоря, у петли нет ориентации. Однако в ориентированном графе для отличия от смешанного графа петлям придают ориентацию.

См. также

Wikimedia Foundation . 2010 .

Смотреть что такое «Петля (граф)» в других словарях:

  • Петля (теория графов) — У этого термина существуют и другие значения, см. Петля. Граф, содержащий петлю при вершине 1 Петля в графе ребро, инци­дентное одной и той же вершин … Википедия
  • Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия
  • Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
  • Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Инцидентность — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Подграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

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

нарушение работоспособности локальной сети с помощью программного обеспечения 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.

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

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

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

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

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

Рис.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.

Структура заголовка пакета LLMNR

Рис. 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 Загруженность пропускной способности канала передачи

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

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

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

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

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

Петля в локальной сети. Как найти и устранить?

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

Заранее узнать появление петли очень трудно, а при её возникновении сеть просто «ложится». Одна локальную петлю можно «диагностировать» по ряду признаков, которые показывают зацикливание пакета информации

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

Маршрутная петля появляется, когда пакет отправителя не может попасть получателю и длительное время движется по одному маршруту – он «зацикливается» в одном участке сети

petlya v lokalnoj seti 1

Как мы видим отправитель отправляет пакет данных на «коммутатор А», пакет идёт далее, и не зная кому его передать передаёт его «коммутатору С», и так циклично. А получатель так и не получив своей пакет отклоняет его, сообщив отправителю что пакет не получен.

И мы в ответ получаем сообщение

petlya v lokalnoj seti 2

При этом сеть на данном участке оказывается перегруженной и «падает». Перегружают её пакеты которые не могут покинуть петлю – формируется широковещательный шторм.

Кроме того, наличие зацикленных пакетов приводит к существенному снижению пропускной способности канала свзяи. При этом проблема на одном из участков сети становятся причиной сбоев общих сетевых каналов связи. Однако ввиду того, что время жизни пакета (TTL) в протоколе IP весьма ограниченно, такое «зацикливание» пакета не происходит вечно.

Петля в локальной сети: Характерные признаки

Сетевая петля обладает совершенно четкими признаками, этими признаками является ряд параметров

Time to live (TTL) время жизни пакета

IP ID идентификатор IP пакета

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

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

Анализатор сетевого трафика (сниффер) поможет не только выявить наличие маршрутной петли, но и покажет сетевые устройства, которые ее создали. Конечно, можно подергать каждый патч-корд каждого сетевого устройства, однако такое решение нерационально для корпоративной сети.

1. Прежде всего, нужно локализовать проблемный участок. Определить какой из участков сети «падает».

2. Запустить сниффер с целью определения устройств, между которыми осуществляется столь «эмоциональное» общение.

3. Далее, понадобится определить пакеты, создающие широковещательный шторм и отфильтровать их. Как правило, эти IP-пакеты содержат одинаковый IP-идентификатор и их очень много.

4. Также, следует оценить время жизни таких пакетов. Проходя через роутер, пакет теряет единицу TTL, поэтому можно проследить каждую потерянную единицу вплоть до уничтожения самого пакета маршрутизатором.

5. Определив пакеты, имеющие явные признаки зацикливания в петле, можно отфильтровать (например, в Capsa) MAC-адреса физических устройств, которые принимают участие в общении по сетевой петле и посылают такие датаграммы.

6. Обладая сведениями о MAC-адресах, можно найти устройства, работа которых вызвала маршрутную петлю.

Понятное объяснение петель в графах: определение, примеры и свойства

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

Понятное объяснение петель в графах: определение, примеры и свойства обновлено: 11 ноября, 2023 автором: Научные Статьи.Ру

Помощь в написании работы

Введение

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

Нужна помощь в написании работы?

Мы — биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Определение понятия петля

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

Петля обозначается обычно как (v, v), где v – вершина, к которой она принадлежит.

Петли могут быть как в ориентированных, так и в неориентированных графах.

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

В неориентированном графе петля представляет собой ребро, которое соединяет вершину с самой собой, и не имеет направления.

Примеры петель в графах

Петли в графах могут быть различных видов и форм. Вот несколько примеров:

Пример 1:

Рассмотрим неориентированный граф с тремя вершинами A, B и C. Если добавить ребро, которое соединяет вершину A с самой собой, то получится петля. Таким образом, граф будет выглядеть следующим образом:

В данном примере петля представляет собой ребро, которое соединяет вершину A с самой собой.

Пример 2:

Рассмотрим ориентированный граф с четырьмя вершинами A, B, C и D. Если добавить дугу, которая начинается и заканчивается в вершине B, то получится петля. Таким образом, граф будет выглядеть следующим образом:

В данном примере петля представляет собой дугу, которая начинается и заканчивается в вершине B.

Пример 3:

Рассмотрим ориентированный граф с пятью вершинами A, B, C, D и E. Если добавить дугу, которая начинается и заканчивается в вершине C, то получится петля. Таким образом, граф будет выглядеть следующим образом:

В данном примере петля представляет собой дугу, которая начинается и заканчивается в вершине C.

Свойства и характеристики петель

Петля в графе – это дуга, которая начинается и заканчивается в одной и той же вершине. Она представляет собой цикл длины 1.

Вот некоторые свойства и характеристики петель:

Длина петли

Петля имеет длину 1, так как она состоит только из одной дуги.

Ориентация петли

Петля может быть ориентированной или неориентированной, в зависимости от типа графа.

В неориентированном графе петля представляет собой неупорядоченную пару вершин, и направление дуги не имеет значения.

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

Кратность петли

Петля всегда имеет кратность 1, так как она состоит только из одной дуги.

Влияние петли на связность графа

Петля не влияет на связность графа, так как она не добавляет новые связи между вершинами.

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

Таким образом, петли являются особыми элементами графа, которые могут быть полезными при изучении его свойств и характеристик.

Виды петель в различных типах графов

Петли могут встречаться в различных типах графов, и их характеристики могут отличаться в зависимости от типа графа.

Направленные графы

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

Направление петли определяется направлением дуги.

Например, в направленном графе может быть петля, которая начинается в вершине A и заканчивается в той же вершине A.

Ненаправленные графы

В ненаправленных графах петля представляет собой ребро, которое соединяет одну и ту же вершину.

Направление петли не имеет значения, так как ребро не имеет ориентации.

Например, в ненаправленном графе может быть петля, которая соединяет вершину A с той же вершиной A.

Мультиграфы

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

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

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

Псевдографы

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

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

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

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

Значение петель в теории графов и их применение

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

Отражение повторяющихся связей

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

Учет циклических процессов

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

Обозначение самопетель

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

Анализ структуры графа

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

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

Таблица по теме “Петли в графах”

Понятие Определение Пример
Петля Ребро, которое соединяет вершину с самой собой Пример петли
Самопетля Петля, где начальная и конечная вершины совпадают Пример самопетли
Несамопетля Петля, где начальная и конечная вершины различны Пример несамопетли

Заключение

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

Понятное объяснение петель в графах: определение, примеры и свойства обновлено: 11 ноября, 2023 автором: Научные Статьи.Ру

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *