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

Настройка локальной сети вручную в Ubuntu

Компьютер в сети, должен быть уникальным.

Уникальность ему предоставляет IP-адрес. IP-адрес — это последовательность единиц и нолей, равная 32 знакам (1100100111…) — страшно и непонятно :).

Для наглядности и удобства эту последовательность разбили на 4 равные части и перевели в десятичную систему исчисления.

Что получилось? 32 знака (единицы и ноли) = 8 знаков * 4 группы = 255.255.255.255 (8 знаков = 2 в 8-й степени — 1 = 256 — 1 = 255).

То есть максимально возможная группа цифр — это 255.255.255.255.

Маска подсети:

Что такое маска подсети? А это часть ip-адреса. IP-адрес поделили на две неравные части. Первые 24 знака (бита) — маска, а остальные 8 — адрес хоста в подсети.

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

Шлюз:

Как работает сеть? Если сказать просто, то так: компьютер отсылает пакет абы куда :), но в пакете есть информация в которой записано кому он предназначен — информация о получателе. Пакет может прийти хосту, для которого он не предназначен. Хост проверит по записанной ключевой информации принадлежность пакета, убедится, что пакет не для него, и выбросит его как ненужный. И так происходит пока пакет не придет к получателю.

Что за информация записана в пакете, по которой хосты определяют принадлежность пакета получателю?

При тривиальных условиях, то есть когда компьютеры в одной подсети, записывается MAC-адрес получателя и ip-адрес получателя, а когда пакет шлем через шлюз, то в пакете указывается MAC-адрес шлюза (его мы узнаем из ip-адреса шлюза с помощью ARP-запроса) и ip-адрес компьютера-получателя.

DNS:

DNS-сервер — это компьютер, который знают всё про всех :). Это глобальное определение.

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

Пример: Есть желание попасть на http://yandex.ru. Наш компьютер формирует запрос для сервера — это компьютер на котором размещена страничка http://www.yandex.ru :).

Для того, чтобы узнать адрес этого сервера, ему нужно, сначала, посмотреть файл hosts (в windows — C:/windows/system32/drivers/etc/hosts, в linux — /etc/hosts) и, если в нём нет записи с этим именем, то послать запрос DNS-серверу, в котором прописаны символы — «yandex.ru».

DNS-сервер посмотрит в таблицах соответствий имён ip-адресам, и найдет ip-адрес сервера. Этот 32-битный адрес он вернёт нам. Используя этот ip-адрес мы преспокойненько попадаем на нужную нам страничку.

Если же DNS-сервер не отвечает, то мы отправляем запрос второму DNS-серверу.

Если у вас не работает интернет, проверьте, может быть не прописаны или прописаны но неправильно DNS-серверы.

Проверить это можно «попинговав» сначала yandex.ru, а потом его ip-адрес: 77.88.21.11.

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

• 10.0.0.0 — 10.255.255.255 (одна сеть класса A)
• 172.16.0.0 — 172.31.255.255 (шестнадцать сетей класса B)
• 192.168.0.0 — 192.168.255.255 (256 сетей класса C)

Это «серые», «внутренние» адреса. Они используются в локальных компьютерных сетях, которые если и имеют выход в интернет, то только через шлюз, у которого есть внешний ip-адрес. Если у этого шлюза вторая сеть — интернет, и адрес внешний, то необходимо настроить на нем технологию транслирования сетевых адресов (network address translation, NAT).

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

При использовании NAT, шлюз меняет адрес отправителя на свой внешний адрес, а у себя записывает, что «ответные пакеты с этого сервера перенаправлять такому-то компьютеру…».

В этом случае используется SNAT (source network address translation).

Если же нам необходимо изменять адрес получателя (например, в нашей локальной сети есть сервер терминалов с серым адресом, а мы бы хотели иметь к нему доступ из интернета), то можно использовать на нашем шлюзе DNAT (destination network address translation) — «проброс портов».

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

Определение состояния сетевых устройств и средств

Если рассматривать самое простое соединение, т.е. компьютер в локальной сети и получает настройки автоматически, то необходимо выполнить команду:

Далее, для изменения настроек нам понадобятся права суперпользователя, по этому будем использовать программу sudo.

sudo dhclient eth0

(команду dhclient надо запускать с правами суперпользователя).

Команда ifconfig (без параметров), отображает информацию только об активных сетевых интерфейсах.

Просмотреть информацию по всем интерфейсам можно командой ifconfig -a, выбрать необходимый из них (eth0, или eth1, или eth0:1) и работать с ним.

ifconfig -a

В Ubuntu имена сетевых устройств имеют вид ethN, где N — число, означающее номер устройства связи в системе.

Нумерация устройств начинается с нуля. Если в компьютере две сетевых карты, то они будут с идентификаторами eth0 и eth1. Если в сетевую карту ethN вставлен сетевой провод, идущий в модем, роутер или свитч, будет написано «RUNNING», на первом рисунке это видно.

Интерфейс eth0 — карта Ethernet. Сетевой кабель подлючен, интерфейс активен, присвоен ip(192.168.1.254) и маска подсети(255.255.255.0):Интерфейс lo — интерфейс обратной петли и позволяет компьютеру обращатся к самому себе. Интерфейс имеет ip-адрес 127.0.0.

1 и необходим для нормальной работы системы:

Команда ifconfig -a удобна в тех случаях, когда надо быстро выяснить состояние интерфейсов, в частности, если необходимо узнать их ip-адреса.

Помимо сведений о конфигурации сетевых интерфейсов команда выдает еще много полезной информации, например, количество отправленных и полученных пакетов (параметры RX и TX).

Еще один интересный адрес, который можно увидеть у сетевой карты — параметр HWaddr (Hardware Address, аппаратный адрес). Это mac-адрес (Media Access Control, управление доступом к среде). Это 48-разрядный серийный номер сетевого адаптера, присваиваемый производителем. Так как lo создан программно, у него не может быть аппаратного адреса.

Настройка сетевого интерфейса при помощи ifconfig

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

Чтобы получить подробную информацию по команде, пишем в терминале:
man ifconfig

Если компьютер со статическим ip-адресом и не имеет доступа ни к другим сетям ни к интернету, то команда настройки сетевого интерфейса будет такой:

sudo ifconfig eth0 192.168.1.2 netmask 255.255.255.0 up

Поясняю:

eth0 — идентификатор сетевого оборудования (сетевая карта).

192.168.1.2 — присваеваемый ip-адрес.

netmask 255.255.255.0 — присваеваемая маска подсети.

up — поднять интерфейс (то есть применить изменения, начать работу сетевой карте).

down — остановить интерфейс.

Команда: sudo ifconfig eth0 down Т.е. остановить работу сетевой карты с eth0 идентификатором.

Бывает так, что провайдер интернет привязывает mac-адрес сетевой карты к учётке клиента. При замене сетевой карты или же компьютера, мы получим отсутствие интернета на нашей стороне. Как временное решение может подойти подмена реального mac-адреса, mac-адресом который был зарегистрирован у провайдера. Почему временное? Потому, что описанная ниже команда делает изменения которые удалятся, при перезагрузке компьютера.

Сначала выясняем наш старый mac-адрес, выполняем команду ifconfig без параметров.

Допустим он у нас такой: 00:00:00:00:00:01.

Производим следующие действия, то есть выполняем последовательность команд:

1) Отключаем интерфейс: ifconfig eth0 down

2) Изменяем MAC: ifconfig eth0 hw ether 00:00:00:00:00:01

3) Включаем интерфейс: ifconfig eth0 up

Все действия можно выполнить одной командой:

sudo ifconfig eth0 down && ifconfig eth0 hw ether 00:00:00:00:00:01 up

&& — означает, выполнить следующую команду при успешном выполнении предыдущей команды.

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

Редактируем файл /etc/network/interfaces

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

Набираем команду ifconfig -a Видим список всех (активных и неактивных) сетевых устройств, которые именуются как eth0, eth1, eth2 и т.д.

На скриншоте вы видите три устройства:

еth0 — первая сетевая карта.

lo — локальная петля.

Локальная сеть подключена к сетевой карте eth0.

Почти вся информация о настройках сети и методах ее активации, хранится в файле /etc/network/interfaces, именно с ним мы и будем работать, используя редактор.

Открываем файл:

sudo gedit /etc/network/interfaces

auto lo — говорит о том, что интерфейс lo поднимается автоматически при загрузке системы.

Добавьте в файл строки:

auto eth0 iface eth0 inet static address 192.168.1.254 netmask 255.255.255.0 gateway 192.168.1.1

auto eth0 — сетевая карта eth0 поднимается автоматически во время загрузки системы.

address 192.168.1.254 — статический ip адрес, тут пишем свой ip-адрес.

netmask — стандартная маска сети.

gateway — ip-адрес основного шлюза.

Редактирование закончено. Сохраняем и закрываем файл.

Запросите у вашего провайдера услуг Интернет (Internet Service Provider, ISP) адреса основного и вспомогательного серверов DNS и опишите их в файле /etc/resolv.conf. На примере я укажу адрес DNS-сервер своего провайдера, вы должны ввести свои данные.

Откройте файл для редактирования:

sudo gedit /etc/resolv.conf

Вставьте свои данные:

nameserver 192.168.1.1 nameserver 172.16.0.1

Сохраните и закройте файл.

Для настройки DHCP и получения сетевых параметров автоматически, нужно добавить две строчки (пусть у меня так поднимется карта eth1).

Откройте файл:

sudo gedit /etc/network/interfaces

Вставьте строчки следующего содержания:

auto eth1 iface eth1 inet dhcp

Ваш файл будет выглядеть так:

auto lo iface lo inet loopback auto eth0 iface eth0 inet static address 192.168.1.254 netmask 255.255.255.0 gateway 192.168.1.1 auto eth1 iface eth0 inet dhcp

Если по каким-либо причинам вы хотите чтобы при загрузке у сетевой карты eth0 был другой mac-адрес, для этого нужно дописать строчку hwaddress ether 00:00:00:00:00:01:

auto eth0 iface eth0 inet static address 192.168.1.254 netmask 255.255.255.0 gateway 192.168.1.1 hwaddress ether 00:00:00:00:00:01

Несколько IP-адресов на одной сетевой карте

На одной сетевой карте может быть несколько ip-адресов, это бывает необходимо, если в коммутатор идут два провода от разных сетей и один от компьютера.

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

Для этого необходимо идентифицировать так называемый алиас (alias) к определенному сетевому интерфейсу, и выглядеть это будет так: сетевой_интерфейс:1 или сетевой_интерфейс:2, т.е. eth0:1 или eth1:2. Идентифицировать его можно следующим образом:

ifconfig eth0:1 192.168.0.5 netmask 255.255.255.0 up

Интересно то, что можно настроить основной интерфейс через dhcp (автоматически) dhclient eth0, а алиас eth0:1 в статику, чего я в альтернативных операционных системах не нашел.

Все это хорошо, но после перезагрузки все настройки слетают. В Ubuntu есть файл /etc/network/interfaces. В него можно прописать опции сетевых карт, которые будут устанавливаться при загрузке системы (благодаря скрипту /etc/init.d/networking, запускающемуся автоматически).

Откройте файл для редактирования:

sudo gedit /etc/network/interfaces

Синтаксис простой:

Настройка локальной сети в Ubuntu

Из этой категории

Источник: https://tavportal.ru/archives/136

Избавляемся от широковещательного шторма с помощью STP

Широковещательный шторм – передача большого количества пакетов в сети, часто с последующим увеличением их количества. Причины широковещательного шторма:

• Петли коммутации
• Атаки на сеть
• Неисправная сетевая карта

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

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

STP (Spanning Tree Porotocol) – сетевой протокол, предназначенный для автоматического удаления циклов (петель коммутации) из топологии на канальном уровне в Ethernet сетях. Протокол работает на канальном уровне.

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

Для того, чтобы определить какие порты заблокировать, а какие будут передавать данные, STP выполняет следующее:

• Выбирается корневой мост (Root Bridge)
• Далее каждый коммутатор просчитывает ближайший путь к корневому. Соответствующий порт называется корневым портов (Root Port)
• После этого для каждого сегмента сети, к которому присоединен более чем один мост, просчитывается кратчайший путь к корневому мосту (порту). Мост, через который проходит этот путь, становится назначенным мостом (Designed Bridge), а соответствующий порт – назначенным портом (Designed Port)
• Далее во всех сегментах, с которыми соединены более одного порта, все мосты блокируют все порты, не являющиеся корневыми и назначенными

В итоге получается древовидная структура (математический граф) с вершиной в виде корневого коммутатора. Ранее было упомянуто, что коммутаторы обмениваются между собой пакетами BPDU. BPDU (Bridge Protocol Data Unit) – фрейм протокола управления сетевыми мостами.

Рассмотрим формат пакета:

• Protocol Identifier – идентификатор протокола
• Protocl Version – версия протокола
• BPDU Type – тип BPDU. Существует два типа – конфигурационный и уведомление о реконфигурации
• Flags – флаги. В поле Flag используется только два бита: бит 1 является флагом изменения топологии (Topology Change), бит 8 является флагом подтверждения смены топологии (Topology Change Acknowledgement)
• Root ID – идентификатор корневого моста
• Root Path Cost – стоимость пути до корневого моста
• Bridge ID – идентификатор моста. Состоит из поля приоритета (2б) и MAC-адреса (6б). Root Priority = N * 4094, где N – назначается администратором.
• Port ID – идентификатор порта
• Message Age – время жизни сообщения
• Max Message Age – максимальное время жизни сообщения. Если пакет превысил это значение, то он игнорируется коммутаторами
• Hello Time – интервал hello, через который посылаются пакеты BPDU
• Forward Delay – задержка смены состояний. Минимальное время перехода моста в активное состояние.

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

Построение дерева:

• В начале каждый коммутатор считает себя корневым (root)
• Каждый коммутатор посылает Hello BPDU через интервал 2 секунды
• Если мост получает BPDU с Bridge ID меньше, чем свой, он транслирует этот BPDU, а свой прекращает
• В конце остается только один мост, который продолжает генерировать и передавать свои BPDU. Этот мост и будет считаться корневым Root Bridge
• На основании меньшего Root Path Cost выбираются корневые порты у оставшихся коммутаторов. Если Root Path Cost совпадает, то порт выбирается на основе меньшего Bridge ID. Если и Bridge ID совпало, то выбираем на основе меньшего Port ID
• Коммутатор в сети имеющий наименьшее расстояние до корневого является назначенным. Сегменты, подключенные к этому коммутатору через назначенные порты.

Изменение топологии:

• При обнаружении изменения в сети коммутатор отравляет BPDU, у которого установлен Flag Topology Change = 1. BPDU рассылается каждый hello-интервал в направлению к корневому коммутатору.
• Следующий коммутатор (на пути к Root Bridge), получив BPDU с Topology Change = 1 отправляет обратно BPDU с подтверждением Topoly Change Acknowledgement = 1.
• Остальные коммутаторы, для которых для данного сегмента порт работает в режиме Designed port, повторяют первые два шага и отправляют в направлении к Root Bridge BPDU с Topology Change = 1.
• Как только корневой коммутатор получает уведомление об изменении топологии, он отправляет hello с флагом Topology Change Acknowledgement =1 всем коммутаторам. Коммутатор, получив сообщение hello, использует таймер Forward Delay Time для того, чтобы обновить записи в своей таблице коммутации.

Настройка STP на управляемом коммутаторе Dlink DES-3528 

В коммутационном шкафу была собрана схема для изучения протокола STP.

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

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

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

На коммутаторе SW5 командой show stp проверялся статус протокола STP – включен или выключен.

Выяснилось, что протокол STP на коммутаторах SW1 – SW5 был выключен. Командой enable stp включаем протокол STP на всех коммутаторах и проверяем загрузку ЦП компьютера.

Загрузка ЦП упала после включения протокола STP. Отсюда можно сделать вывод, что высокая нагрузка на процессор была связана с широковещательным штормом, а протокол STP устранил эту проблему.
При просмотре статуса STP show stp была выведена следующая информация:

• STP Status : Enabled – STP включен
• STP Version: RSTP – версия RSTP (Rapid spanning tree protocol)
• Maxe Age: 20 – время жизни пакета 20 с
• Hello time: 2 – время отклика 2 с
• Forward Delay: 15 – обновления записей в таблице коммутатора через 15 с
• Max Hops: 20 – максимальное количество хопов 20
• Tx Hould Count: 6 – максимальное количество шагов прохождения пакета
• Forwading BPDU: Disabled – посылка фрейма для устранения петель

С помощью команды show stp instance 0 выведем информацию о дереве протокола STP.

Команда выводит следующие поля:

• Instance Type: CIST – тип используемой конфигурации
• Instance Status: Enabled – статут конфигурации (включен)
• Instance Priority: 32768 – приоритет коммутатора
• Designed Root Bridge: 00-22-B0-B4-4A-E0 – назначенный корневой коммутатор (MAC-адрес назначенного коммутатора)
• External Root Cost: 200000 – сумма пути до корневого коммутатора
• Regional Root Bridge: 00-22-B0-B4-5D-D0 – региональный коммутатор
• Internal Root Cost: 0 – сумма пути до регионального коммутатора
• Designated Bridge: 00-22-B0-B4-4A-E0 – назначенный коммутатор
• Root Port: 4 – порт, по которому подключён корневой коммутатор
• Last Topology Change: 357 – время, в котором произошло последнее изменение топологии прохождения пакета
• Topology Change Count: 9 – общее количество раз, когда топология изменилась

С помощью команды show stp port 1-7 просмотрим информацию по всем портам коммутатора.

Информация о портах

• MSTI – код дерева
• Designated Bridge – назначенный коммутатор с идентификатором
• Internal PathCost – стоимость пути до корня
• Prio – приоритет
• Status – состояние порта
• Role – роль порта
• Port Index – индекс порта
• Hello Time – время приветствия

По полученным данным можно построить логическую топологию сети. Из рисунков выше видно, что порт 1 и 6 являются назначенным (Designed), порт 5 альтернативный (Alternative), порт 4 корневой (Root). Помимо ролей портов, можно также узнать их состояние.

Порты 1,4,6 находятся в состоянии пересылки (Forwarding) – то есть в данный момент они в работе. Порт 5 находится в состоянии блокировки (Discarding). Получается альтернативный порт в данный момент заблокирован и через него не будут передаваться кадры.

В итоге, получив аналогичную информацию со всех остальных коммутаторов SW1, SW2, SW3, SW4, мы можем воспроизвести текущую топологию сети и построить дерево STP.

Обрыв кабеля и перерасчет маршрутов в схеме

В собранной схеме в нескольких местах был произведен обрыв. Место обрыва определялось с помощью команды show stp port 1-7. В том случае если рабочий порт находился в состоянии Disabled (Выключено) делался вывод о том, что на этом месте произошел обрыв. Например, для коммутатора SW5 четвертый корневой порт находился в состоянии Disabled. Кроме того выяснилось, что
второй порт коммутатора SW2 также находился в состоянии Disabled.

В результате проверки, было локализовано место обрыва. Как видно из рисунка выше на SW5 порт 4, который ранее был корневым (Root), в данный момент выключен (Disabled). Также на SW1 корневой порт 2 также находится в состоянии disabled.

В результате обрыва произошло перенаправление маршрутов к Root Bridge (корневому коммутатору). Для перенаправления использовались Alternative Port (альтернативные порты). В итоге поменялось дерево сети.

Настройка приоритетов на коммутаторах Dlink DES-3528

Настроим приоритеты на коммутаторах таким образом, чтобы при отключении корневого коммутатора SW2 корневым стал SW4. После чего при отключении SW4 корневым стал SW3.

 При настройке приоритетов учитывалось два обстоятельства: во-первых чем ниже приоритет коммутатора, тем выше вероятность того, что он станет корневым; во-вторых приоритетность коммутатора должны быть кратна 4096.

 Исходя из поставленной задачи и учитывая тот факт, что на всех коммутаторах стоит приоритетность по умолчанию, равная 32768, было сделано следующее.

Настроим приоритет коммутатора командой  config stp priority. Для SW2 зададим самый низкий приоритет, для SW4 приоритет 8192, для SW3 оставим приоритет по-умолчанию 16384.

SW2 > config stp priority 4096

SW4 > config stp priority 8192

Выведем информацию о приоритете коммутаторов SW2, SW4.

В результате отключения коммутатора SW2 произошло перенаправление корневых портов в соответствии с приоритетами коммутаторов. Корневым коммутатором стал SW4. На SW5 корневым портом был назначен порт 6.

Протокол RSTP

RSTP (Rapid Spanning Tree Protocol) – быстрый протокол покрывающего дерева. Версия протокола STP с ускоренной реконфигурацией дерева, использующего для исключения петель в соединениях коммутаторов.

По сравнению с STP уменьшилось время построения топологии, а также время восстановления работоспособности сети. Что позволило уменьшить это время? В протоколе RSTP есть только три состояния порта (в отличие от STP – 4 состояния). Состояния “отключен”, “блокирован”, “прослушивание” портов STP были заменены в одно состояние “сбрасывание”.

Мы оказываем услуги по ремонту и настройке компьютеров, смартфонов, планшетов, wi-fi роутеров, модемов, IP-TV, принтеров. Качественно и недорого. Возникла проблема? Заполните форму ниже и мы Вам перезвоним.

Источник: https://netclo.ru/izbavlyaemsya-ot-shirokoveshhatelnogo-sh/

Реализуйте алгоритм для однонаправленного списка с петлёй, возвращающий начальный узел петли

Эта задача является разновидностью классической задачи, задаваемой на собеседованиях, – определить, содержит ли связный список петлю. Давайте используем подход «Сопоставление с образцом».

Часть 1. Определяем, есть ли в связном списке петля

Простейший способ выяснить есть ли в связном списке петля,— использовать метод бегунка (быстрый/медленный). FastRunner делает два шага за один такт, а SlowRunner — только один. Подобно двум гоночным автомобилям, мчащимся по одной трассе разными путями, они непременно должны встретиться.

Проницательный читатель может задать вопрос: может ли быстрый бегунок «перепрыгнуть» медленный без столкновения? Это невозможно. Допустим, что FastRunner перепрыгнул через SlowRunner и теперь находится в элементе i+1 (а медленный – в i). Это означает, что на предыдущем шаге SlowRunner был в точке i-1, а FastRunner — ((i+1)-2)=i-1. Следовательно, столкновение неизбежно.

Часть 2. Когда же они встретятся?

Давайте введем обозначение: k – длина связного списка в разомкнутом виде. Как узнать, когда FastRunner и SlowRunner встретятся, используя алгоритм из части 1?

Мы знаем, что FastRunner перемещается в два раза быстрее, чем SlowRunner. Поэтому когда SlowRunner через k шагов попадет в петлю, FastRunner пройдет 2k шагов. Поскольку k существенно больше, чем длина петли, введем обозначение K=mod(k, LOOP_SIZE).

В каждом последующем шаге FastRunner и SlowRunner становятся на шаг (или два шага) ближе к цели. Поскольку система замкнута, когда A перемещается на  q, оно становится на q шагов ближе к B.

Можно установить следующие факты:

1. SlowRunner: 0 шагов внутри петли.
2. FastRunner: k шагов.
3. SlowRunner: отстает от FastRunner на k шагов.
4. FastRunner: отстает от SlowRunner на LOOP_SIZE – K шагов.
5. FastRunner нагоняет SlowRunner со скоростью 1 шаг за единицу времени.

Когда же они встретятся? Если FastRunner на LOOP_SIZE – K  шагов отстает от SlowRunner, а FastRunner нагоняет его со скоростью 1 шаг за единицу времени, они встретятся через LOOP_SIZE- k шагов. В этой точке они будут отстоять на k шагов от начала петли. Давайте назовем эту точку CollisionSpot.

Часть3. Как найти начало петли?

Мы теперь знаем, что CollisonSpot – это k узел до начала петли. Поскольку K=mod(k, LOOP_SIZE) (или k=K+M*LOOP_SIZE для любого целого  M),  можно сказать, что до начала петли k узлов. Если узел N-2 узла в петле из 5 элементов, то элементы 7, 12 и даже 397 принадлежать петле.

Поэтому и CollisionSpot, и LinkedListHead находятся в k узлах от начала петли.

Если мы сохраним один указатель в CollisionSpot и переместим другой в LinkedListHead, то каждый из них будет отстоять на k узлов от LoopStart. Перемещение этих указателей заставит их столкнуться — на сей раз через k шагов – в точке LoopStart. Все, что нам нужно сделать, — возвратить этот узел.

Часть 4. Собираем все воедино

FastPointer двигается в два раза быстрее, чем SlowPointer. Через k узлов SlowPointer оказывается в петле, а FastPointer – на k-м узле связного списка. Это означает, что FastPointer и SlowPointer отделяют друг от друга LOOP_SIZE-k узлов.

Если FastPointer двигается на 2 узла за одиночный шаг SlowPointer, указатели будут сближаться на каждом цикле и встретятся через LOOP_SIZE-k циклов. В этой точке они окажутся на расстоянии k узлов от начала петли.

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

Давайте запишем алгоритм, воспользовавшись информацией из частей 1-3:

1. Создадим два указателя FastPointer и SlowPointer.
2. Будем перемещать FastPointer на 2 шага, а SlowPointer на один шаг.
3. Когда указатели встретятся, нужно передвинуть SlowPointer в LinkedListHead, а FastPointer оставить на том же месте.
4. SlowPointer и FastPointer продолжают двигаться со своими скоростями, точка их следующей встречи будет искомым результатом.

Следующий код реализует описанный алгоритм:

LinkedListNode FindBegining(LinkedListNode head) { LinkedListNode slow = head; LinkedListNode fast = head; /*Находим первую точку встречи LOOP_SIZE-k шагов по связному списку.*/ while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { //Коллизия break; } } /* Ошибка — нет точки встречи, следовательно, нет петли */ if (fast == null || fast.next == null) { return null; } /* Перемещаем медленный бегунок в начало списка (Head). Быстрый остается в точке встречи. *Каждые k шагов от Loop Start. Если указатели продолжат движение с той же скоростью, то * встретятся в точке Loop Start. */ slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } /* Возвращаем точку начала петли. */ return fast;}

Разбор по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»

Хинт для программистов: если зарегистрироваться на соревнования Huawei Honor Cup, бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании. Перейти к регистрации.

Источник: https://tproger.ru/problems/given-a-circular-linked-list-implement-an-algorithm-which-returns/

Защита от образования петель

25

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

25.1 Обзор функции защиты от образования петель

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

Рисунок 116 Защита от образования петель и STP

STP

Защита от образования петель

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

При подключении коммутатора (без петли) к коммутатору с петлей проблемы последнего отражаются на первом следующим образом:

•Он будет принимать широковещательные сообщения, рассылаемые коммутатором с петлей.

Руководство пользователя по серии ES-3124

Глава 25 Защита от образования петель

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

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

Рисунок 117 Коммутатор с петлей

A B

N

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

На приведенном ниже рисунке показан коммутатор A с активированной на порту N функцией защиты от образования петель, который отправляет пробный пакет P на коммутатор B. Так как на коммутаторе B имеется петля, пробный пакет P возвращается на порт N коммутатора A. Для защиты остальной части сети от коммутатора с петлей данный коммутатор отключает порт N.

Рисунок 118 Защита от образования петель – пробный пакет

A B

P

N P

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

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

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

Руководство пользователя по серии ES-3124

Глава 25 Защита от образования петель

Рисунок 119 Защита от образования петель – петля в сети

P

N

P

A

P

«После устранения проблемы с петлей в сети отключенный порт можно

командной строки).

25.2Настройка защиты от образования петель

Чтобыотобразитьпоказанныйнижеэкран, выберитевнавигационнойпанелиAdvanced Application > Loop Guard.

«Функция защиты от образования петель не может быть включена на портах, для которых включен протокол покрывающего дерева (RSTP, MRSTP или MSTP).

Рисунок 120 Экран Advanced Application > Loop Guard

Руководство пользователя по серии ES-3124

Глава 25 Защита от образования петель

Поля экрана описаны в следующей таблице.

Таблица 83 Экран Advanced Application > Loop Guard

ПОЛЕ	ОПИСАНИЕ
Active	Установите этот переключатель, чтобы включить защиту от образования
петель на коммутаторе.
При отключении порта в результате действия функции защиты от образования
петель коммутатор генерирует сообщения syslog, сообщения внутреннего
контрольного журнала, а также «ловушки» SNMP.
Port	В этом поле отображается номер порта.
*	С помощью этой строки можно настроить одновременно все порты. С помощью
этой строки можно назначить общие для всех портов настройки, а затем внести
необходимые изменения на уровне отдельного порта.

Примечание: Изменения в данной строке сразу же копируются
на все порты.
Active	Установите этот переключатель, чтобы включить защиту от образования
петель для данного порта. Данный коммутатор будет отправлять пробные
пакеты через этот порт для проверки, не подключен ли он к коммутатору с
петлей. В случае обнаружения подключения данного порта к коммутатору с
петлей данный коммутатор отключит этот порт.
Снимите выделение с переключателя, если необходимо отключить эту
функцию защиты от образования петель.
Apply	Нажмите Apply, чтобы сохранить изменения в оперативной памяти
коммутатора. Эти настройки будут утеряны в случае выключения коммутатора
или перебоя в подаче питания, поэтому по завершении настройки необходимо
нажать на ссылке Save в верхней навигационной панели для сохранения
изменений в энергонезависимой памяти.
Cancel	Нажмите Cancel, чтобы начать настройку на этом экране заново.

Руководство пользователя по серии ES-3124

Соседние файлы в предмете Сети ЭВМ и средства коммуникаций

Источник: https://StudFiles.net/preview/841891/page:59/

Рассмотрим, создадим и заюзаем аппаратную петлю на порте коммутатора — «Хакер»

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

INFO

• Rx и Tx — обозначения Receive и Transmit на схемах (приём и передача).
• Loop — англ. петля, контур, шлейф, виток, спираль.

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

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

Петли, штормы и порты — это не только морские термины. Петлей называют ситуацию, когда устройство получает тот же самый сигнал, который отправляет. Представь, что устройство «кричит» себе в порт: «Я здесь!» — слушает и получает в ответ: «Я здесь!». Оно по-детски наивно радуется: есть соседи! Потом оно кричит: «Привет! Лови пакет данных!» — «Поймал?» — «Поймал!» — «И ты лови пакет данных! Поймал?» — «Конечно, дружище!»

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

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

Меня удивил случай, когда установщик цифрового телевидения вот так подсоединил патч-корд (рис. 1). «Куда-то же он должен быть воткнут…» — беспомощно лепетал он.

Рис. 1. Синий свитч с петлей на бортуДругие статьи в выпуске:

• выпуска
• Подписка на «Хакер»

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

Настраиваем коммутаторы

Перед тем как начинать настройку, необходимо установить физическое соединение между коммутатором и рабочей станцией.

Существует два типа кабельных соединений для управления коммутатором: соединение через консольный порт (если он имеется у устройства) и через порт Ethernet (по протоколу Telnet или через web-интерфейс). Консольный порт используется для первоначального конфигурирования коммутатора и обычно не требует настройки. Для того чтобы получить доступ к коммутатору через порт Ethernet, устройству необходимо назначить IP-адрес.

Web-интерфейс является альтернативой командной строке и отображает в режиме реального времени подробную информацию о состоянии портов, модулей, их типе и т. д. Как правило, web-интерфейс живет на 80 HTTP-порте IP-коммутатора.

Настройка DLink DES-3200

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

1. Назначить коммутатору IP-адрес из диапазона адресов твоей сети с помощью следующей команды:DES-3200# config ipif System \ ipaddress xxx.xxx.xxx.xxx/yyy.yyy.yyy.yyy.

   Здесь xxx.xxx.xxx.xxx — IP-адрес, yyy.yyy.yyy.yyy. — маска подсети.

2. Проверить, правильно ли задан IP-адрес коммутатора, с помощью следующей команды:DES-3200# show ipif
3. Запустить на рабочей станции web-браузер и ввести в его командной строке IP- адрес коммутатора.

Управляемые коммутаторы D-Link имеют консольный порт, который с помощью кабеля RS-232, входящего в комплект поставки, подключается к последовательному порту компьютера. Подключение по консоли иногда называют подключением Out-of-Band. Его можно использовать для установки коммутатора и управления им, даже если нет подключения к сети.

После подключения к консольному порту следует запустить эмулятор терминала (например, программу HyperTerminal в Windows). В программе необходимо задать следующие параметры:

Baud rate: 9,600Data width: 8 bitsParity: noneStop bits: 1Flow Control: none

При соединении коммутатора с консолью появится окно командной строки. Если оно не появилось, нажми Ctrl+r , чтобы обновить окно.

Например, если надо узнать синтаксис команды config, введи в командной строке:

DES-3200#config + пробел

Далее можно ввести «?» или нажать кнопку Enter. На экране появится список всех возможных способов завершения команды. Лично я для вывода этого списка на экран пользуюсь клавишей TAB.

Loopback-тест

Базовая конфигурация коммутатора

При создании конфигурации коммутатора прежде всего необходимо обеспечить защиту от доступа к нему неавторизованных пользователей. Самый простой способ обеспечения безопасности — создание учетных записей для пользователей с соответствующими правами. Для учетной записи пользователя можно задать один из двух уровней привилегий: Admin или User. Учетная запись Admin имеет наивысший уровень привилегий. Создать учетную запись пользователя можно с помощью следующих команд CLI:

DES-3200# create account admin/user (знак «/» означает ввод одного из двух параметров)

После этого на экране появится приглашение для ввода пароля и его подтверждения: «Enter a case-sensitive new password». Максимальная длина имени пользователя и пароля составляет 15 символов. После успешного создания учетной записи на экране появится слово Success. Ниже приведен пример создания учетной записи с уровнем привилегий Admin:

Username «dlink»:DES-3200#create account admin dlinkCommand: create account admin dlinkEnter a case-sensitive new password:****Enter the new password again for confirmation:****Success.DES-3200#

Изменить пароль для существующей учетной записи пользователя можно с помощью следующей команды: DES-3200# config account Ниже приведен пример установки нового пароля для учетной записи dlink:

DES-3200#config account dlinkCommand: config account dlinkEnter a old password:****Enter a case-sensitive new password:****Enter the new password again for confirmation:****Success.

Проверка созданной учетной записи выполняется с помощью следующей команды: DES-3200# show account. Для удаления учетной записи используется команда delete account .

Шаг второй. Чтобы коммутатором можно было удаленно управлять через web-интерфейс или Telnet, коммутатору необходимо назначить IP-адрес из адресного пространства сети, в которой планируется использовать устройство. IP-адрес задается автоматически с помощью протоколов DHCP или BOOTP или статически с помощью следующих команд CLI:

DES-3200# config ipif System dhcp,DES-3200# config ipif System ipaddress \ xxx.xxx.xxx.xxx/yyy.yyy.yyy.yyy.

Здесь xxx.xxx.xxx.xxx — IP-адрес, yyy.yyy.yyy.yyy. — маска подсети, System — имя управляющего интерфейса коммутатора.

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

Для установки параметров портов на коммутаторе D-Link служит команда config ports. Ниже я привел пример, в котором показано, как установить скорость 10 Мбит/с, дуплексный режим работы и состояние для портов коммутатора 1–3 и перевести их в режим обучения.

DES-3200#config ports 1-3 speed 10_full learning enable state enableCommand: config ports 1-3 speed 10_full learning enable state enableSuccess

Команда show ports выводит на экран информацию о настройках портов коммутатора.

Шаг четвертый. Сохранение текущей конфигурации коммутатора в энергонезависимой памяти NVRAM. Для этого необходимо выполнить команду save:

DES-3200#saveCommand: saveSaving all settings to NV-RAM… 100%done.DES-3200#

Шаг пятый. Перезагрузка коммутатора с помощью команды reboot:

DES-3200#rebootCommand: reboot

Будь внимателен! Восстановление заводских настроек коммутатора выполняется с помощью команды reset.

DES-3200#reset config

А то я знал одного горе-админа, который перезагружал коммутаторы командой reset, тем самым стирая все настройки.

loop_detection для коммутаторов Alcatelinterface range ethernet e(1-24)loopback-detection enableexitloopback-detection enable loop_detection для коммутаторов Dlinkenable loopdetectconfig loopdetect recover_timer 1800config loopdetect interval 1config loopdetect mode port-basedconfig loopdetect trap noneconfig loopdetect ports 1-24 state enabledconfig loopdetect ports 25-26 state disabled

Но сегодня мы хотим применить loopback во благо. У такого включения есть замечательное свойство. Если на порте коммутатора имеется петля, устройство считает, что к нему что-то подключено, и переходит в UP-состояние, или, как еще говорят, «порт поднимается». Вот эта-то фишка нам с тобой и нужна.

Loopback

Loop — это аппаратный или программный метод, который позволяет направлять полученный сигнал или данные обратно отправителю. На этом методе основан тест, который называется loopback-тест. Для его выполнения необходимо соединить выход устройства с его же входом. Смотри фото «loopback-тест». Если устройство получает свой собственный сигнал обратно, это означает, что цепь функционирует, то есть приемник, передатчик и линия связи исправны.

Устраиваем аппаратную петлю

Устроить обратную связь очень просто: соединяется канал приема и передачи, вход с выходом (Rx и Tx).

Таблица 1. Распиновка RJ45

Обожми один конец кабеля стандартно, а при обжиме второго замкни жилы 2 и 6, а также 1 и 3. Если жилы имеют стандартную расцветку, надо замкнуть оранжевую с зеленой, а бело-оранжевую с бело-зеленой. Смотри рис. 3.

Нумерация контактов RJ-45

Теперь, если воткнешь такой «хвостик» в порт коммутатора или в свою же сетевую карту, загорится зелёненький сигнал link. Ура! Порт определил наше «устройство»!

Красная кнопка, или Hello world

Ну куда же без Hello world? Каждый должен хоть раз в жизни вывести эти слова на экран монитора! Сейчас мы с тобой напишем простейший обработчик событий, который будет срабатывать при замыкании красной кнопки. Для этого нам понадобятся только кнопка с двумя парами контактов, работающих на замыкание, витая пара и коннектор. На всякий случай приведу схему красной кнопки (рис. 4).

Схема красной кнопки

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

Все, теперь можно тестировать. Вставь обжатую часть в порт сетевой карты или в порт коммутатора. Ничего не произошло? Хорошо. Нажми кнопку. Линк поднялся? Замечательно!

Сама красная кнопка

Вот листинг простейшего обработчика Hello World на Cshell:

Скрипт на Cshell, генерящий Hello word#!/bin/csh# ver. 1.0# Проверяем, запущен ли процесс в памятиif ( 'ps | grep 'redbut' | grep -v 'grep' | wc -l'

Источник: https://xakep.ru/2012/10/21/switching-loop/