Перегрузка сети - Network congestion

Перегрузка сети в сеть передачи данных и теория массового обслуживания сокращенный качество обслуживания это происходит, когда сетевой узел или канал передает больше данных, чем может обработать. Типичные эффекты включают: задержка в очереди, потеря пакета или блокировка новых подключений. Следствием перегрузки является постепенное увеличение предлагаемая нагрузка приводит либо только к небольшому увеличению, либо даже к уменьшению сети пропускная способность.^[1]

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

Сети используют контроль перегрузки и предотвращение перегрузки методы, чтобы попытаться избежать коллапса. К ним относятся: экспоненциальный откат в таких протоколах, как CSMA / CA в 802.11 и подобные CSMA / CD в оригинале Ethernet, окно снижение в TCP, и честная очередь в таких устройствах, как маршрутизаторы и сетевые коммутаторы. Другие методы, которые решают проблему перегрузки, включают схемы приоритета, которые передают одни пакеты с более высоким приоритетом перед другими, а также явное выделение сетевых ресурсов конкретным потокам с использованием входной контроль.

Емкость сети

Сетевые ресурсы ограничены, в том числе маршрутизатор время обработки и ссылка пропускная способность. Спор за ресурсы может возникать в сетях при ряде общих обстоятельств. А Беспроводная сеть легко заполняется одним персональным компьютером.^[2] Даже в быстрых компьютерных сетях позвоночник может быть легко переполнен несколькими серверами и клиентскими ПК. Атаки отказа в обслуживании к ботнеты способны заполнить даже самые большие Магистраль Интернета сетевые ссылки, создавая крупномасштабную перегрузку сети. В телефонных сетях массовое мероприятие может перегружать цифровые телефонные цепи.

Застойный коллапс

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

К 1984 году застойный коллапс был идентифицирован как возможная проблема.^[3] Впервые это было замечено в раннем Интернете в октябре 1986 года.^[4] когда NSFnet Магистраль фазы I упала на три порядка с ее пропускной способности 32 кбит / с до 40 бит / с,^{[нужна цитата ]} который продолжался до тех пор, пока конечные узлы не начали реализовывать Ван Якобсон и Салли Флойд с контроль перегрузки между 1987 и 1988 гг.^[5] Когда больше пакеты были отправлены, чем могли бы быть обработаны промежуточными маршрутизаторами, промежуточные маршрутизаторы отбрасывали множество пакетов, ожидая, что конечные точки сети повторно передадут информацию. Однако ранние реализации TCP имели плохое поведение при повторной передаче. Когда эта потеря пакета произошла, конечные точки отправили дополнительные пакеты, которые повторяли потерянную информацию, удваивая входящую скорость.

Контроль перегрузки

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

Теория контроля перегрузки

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

Позволять ${\displaystyle x_{i}}$ быть скоростью потока ${\displaystyle i}$, ${\displaystyle c_{l}}$ быть емкостью ссылки ${\displaystyle l}$, и ${\displaystyle r_{li}}$ быть 1, если поток ${\displaystyle i}$ использует ссылку ${\displaystyle l}$ и 0 в противном случае. Позволять ${\displaystyle x}$, ${\displaystyle c}$ и ${\displaystyle R}$ - соответствующие векторы и матрица. Позволять ${\displaystyle U(x)}$ быть увеличивающимся, строго вогнутая функция, называется полезность, который измеряет, сколько пользы получает пользователь, передавая со скоростью ${\displaystyle x}$. Тогда оптимальное распределение ставок удовлетворяет

${\displaystyle \max \limits _{x}\sum _{i}U(x_{i})}$

такой, что ${\displaystyle Rx\leq c}$

В Дуал Лагранжа этой проблемы разделяется, так что каждый поток устанавливает свою собственную скорость, основанную только на цена сигнализируется сетью. Пропускная способность каждого канала накладывает ограничение, которое приводит к Множитель Лагранжа, ${\displaystyle p_{l}}$. Сумма этих множителей, ${\displaystyle y_{i}=\sum _{l}p_{l}r_{li},}$ цена, на которую реагирует поток.

Тогда контроль перегрузки становится распределенным алгоритмом оптимизации. Многие современные алгоритмы управления перегрузкой могут быть смоделированы в этой структуре с ${\displaystyle p_{l}}$ вероятность потери или задержка в очереди на ссылке ${\displaystyle l}$. Основным недостатком является то, что он назначает одинаковую цену для всех потоков, в то время как управление потоком скользящего окна вызывает вспыльчивость что заставляет разные потоки наблюдать разные потери или задержки на данном канале.

Классификация алгоритмов управления перегрузками

Смотрите также: Контроль перегрузки TCP

К способам классификации алгоритмов управления перегрузками относятся:

• По типу и количеству отзывов, полученных от сети: Убыток; задерживать; однобитовые или многобитовые явные сигналы
• За счет инкрементального развертывания: модификация требует только отправителя; отправитель и получатель нуждаются в модификации; доработка требует только роутер; отправитель, получатель и маршрутизаторы нуждаются в модификации.
• По характеристикам: продуктовые сети с высокой пропускной способностью и задержкой; ссылки с потерями; справедливость; преимущество перед короткими потоками; ссылки с переменной ставкой
• По критерию справедливости: Макс-мин честность; пропорционально справедливо; контролируемая задержка

Смягчение

Были изобретены механизмы для предотвращения перегрузки сети или борьбы с ее коллапсом:

• Сетевой планировщик  – активное управление очередью который переупорядочивает или выборочно отбрасывает сетевые пакеты при наличии перегрузки
• Явное уведомление о перегрузке - расширение протоколов связи IP и TCP, которое добавляет механизм управления потоком
• Контроль перегрузки TCP - различные реализации усилий по борьбе с перегрузкой сети

Правильное поведение конечной точки обычно состоит в том, чтобы повторять потерянную информацию, но постепенно снижать частоту повторения. Если все конечные точки делают это, перегрузка снимается, и сеть возобновляет нормальное поведение.^{[нужна цитата ]} Другие стратегии, такие как медленный старт убедитесь, что новые соединения не перегружают маршрутизатор до того, как начнется обнаружение перегрузки.

Общие механизмы предотвращения перегрузки маршрутизатора включают: честная очередь и другие алгоритмы планирования, и случайное раннее обнаружение (КРАСНЫЙ), когда пакеты случайно отбрасываются при обнаружении перегрузки. Это превентивно запускает конечные точки для замедления передачи до того, как произойдет коллапс перегрузки.

Некоторые сквозные протоколы разработаны и хорошо работают в условиях перегрузки; TCP это хорошо известный пример. Первые реализации TCP для обработки перегрузки были описаны в 1984 г.^[6] но Ван Якобсон включение решения с открытым исходным кодом в стандартный дистрибутив Berkeley UNIX ("BSD ") в 1988 году впервые показал хорошее поведение.

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

Практическое предотвращение перегрузки сети

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

Избежание перегрузки TCP / IP

В Алгоритм предотвращения перегрузки TCP это основная основа для контроль перегрузки в Интернете.^{[8][9][10][11][12]}

Проблемы возникают, когда возникают параллельные потоки TCP хвосты, особенно когда буфер настоящее. Эта отложенная потеря пакетов препятствует автоматическому предотвращению перегрузки TCP. Все потоки, которые испытывают эту потерю пакета, начинают повторное обучение TCP в один и тот же момент - это называется Глобальная синхронизация TCP.

Активное управление очередью

Активное управление очередью (AQM) - это переупорядочивание или отбрасывание сетевых пакетов внутри буфера передачи, связанного с контроллер сетевого интерфейса (NIC). Эту задачу выполняет сетевой планировщик.

Случайное раннее обнаружение

Одно из решений - использовать случайное раннее обнаружение (КРАСНЫЙ) в выходной очереди сетевого оборудования.^[13][14] На сетевое оборудование порты с более чем одной исходящей очередью, взвешенное случайное раннее обнаружение (WRED) можно использовать.

КРАСНЫЙ цвет косвенно сигнализирует TCP-отправителю и получателю, отбрасывая некоторые пакеты, например когда средняя длина очереди превышает пороговое значение (например, 50%) и удаляет линейно или же кубически больше пакетов,^[15] до например 100%, так как очередь заполняется дальше.

Надежное раннее случайное обнаружение

В надежное случайное раннее обнаружение (RRED) алгоритм был предложен для улучшения пропускной способности TCP по сравнению с отказ в обслуживании (DoS) атаки, особенно низкоскоростные атаки типа «отказ в обслуживании» (LDoS). Эксперименты подтвердили, что алгоритмы, подобные RED, были уязвимы для LDoS-атак из-за колеблющегося размера очереди TCP, вызванного атаками.^[16]

WRED на основе потока

Некоторое сетевое оборудование оснащено портами, которые могут отслеживать и измерять каждый поток и, таким образом, могут сигнализировать о потоке слишком большой полосы пропускания в соответствии с некоторой политикой качества обслуживания. Затем политика может разделить полосу пропускания между всеми потоками по некоторым критериям.^[17]

Явное уведомление о перегрузке

Другой подход - использовать Явное уведомление о перегрузке (ECN).^[18] ECN используется только тогда, когда два хоста сигнализируют о своем желании его использовать. В этом методе бит протокола используется для сигнализации явной перегрузки. Это лучше, чем косвенное уведомление о перегрузке, о котором сигнализирует потеря пакета алгоритмами RED / WRED, но оно требует поддержки обоих хостов.^[19][13]

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

Формирование окна TCP

Смотрите также: Параметр масштаба окна TCP

Избежать перегрузок можно эффективно за счет сокращения трафика. Когда приложение запрашивает большой файл, графику или веб-страницу, оно обычно рекламирует окно от 32К до 64К. Это приводит к тому, что сервер отправляет полное окно данных (при условии, что файл больше окна). Когда несколько приложений одновременно запрашивают загрузки, эти данные могут создать точку перегрузки у вышестоящего провайдера. За счет уменьшения количества оконных объявлений удаленные серверы отправляют меньше данных, что снижает перегрузку.^[20][21]

Обратный ECN

Обратный ECN (BECN) - еще один предлагаемый механизм перегрузки. Оно использует Блокировка источника ICMP сообщения в качестве механизма сигнализации IP для реализации базового механизма ECN для IP-сетей, сохраняя уведомления о перегрузке на уровне IP и не требуя согласования между конечными точками сети. Эффективные уведомления о перегрузке могут быть переданы протоколам транспортного уровня, таким как TCP и UDP, для соответствующих корректировок.^[22]

Побочные эффекты предотвращения застойного коллапса

Радио ссылки

Протоколы, которые предотвращают застойный коллапс, часто основаны на идее, что потеря данных вызвана перегрузкой. Это верно почти во всех случаях; ошибки при передаче редки. Однако это вызывает Вай фай, 3G или другие сети с радиоуровнем, чтобы в некоторых случаях иметь низкую пропускную способность, поскольку беспроводные сети подвержены потере данных из-за помех. TCP-соединения, работающие по радио на основе физический слой видят потерю данных и склонны ошибочно полагать, что происходит перегрузка.

Кратковременные связи

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

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

Входной контроль

Входной контроль требует, чтобы устройства получали разрешение перед установкой новых сетевых подключений. Если новое соединение рискует создать перегрузку, в разрешении может быть отказано. Одним из примеров этого является использование возможностей бесконфликтной передачи (CFTXOP) в ITU-T G.hn стандарт, обеспечивающий высокую скорость (до 1 Гбит / с) локальная сеть по различным проводам (линии электропередач, телефонные линии и коаксиальные кабели).

Смотрите также

• Управление пропускной способностью - Процесс измерения и управления коммуникациями в сетевом канале, чтобы избежать переполнения канала или переполнения канала
• Bufferbloat - Перегрузка, вызванная чрезмерной буферизацией пакетов
• Каскадный отказ - Система взаимосвязанных частей, в которой отказ одной или нескольких частей может вызвать отказ других
• Замена дросселя
• Эрланг (единица)
• Макс-мин честность
• Синдром ученика чародея - Ошибка сетевого протокола в исходных версиях TFTP.
• Контроль перегрузки TCP - Методы повышения производительности сети по протоколу управления передачей
• Инженерия телетрафика
• Взбучка - Компьютер постоянно обменивается данными между памятью и хранилищем, оставляя мало возможностей для производительной обработки
• Формирование трафика - Техника управления пропускной способностью
• Надежность (компьютерные сети)

Рекомендации

1. (Аль-Бахадили, 2012, с. 282) Аль-Бахадили, Х. (2012). Имитационное моделирование при проектировании и моделировании компьютерных сетей: использование и анализ. Херши, Пенсильвания: IGI Global.
2. den Hartog, F., Raschella, A., Bouhafs, F., Kempker, P., Boltjes, B., & Seyedebrahimi, M. (2017, ноябрь). Путь к разрешению Wi-Fi Tragedy of the Commons в многоквартирных домах. В 2017 году 27-я Международная конференция по телекоммуникационным сетям и приложениям (ITNAC) (стр. 1-6). IEEE.
3. RFC  896
4. Fall, K.R .; Стивенс, W.R. (2011). Иллюстрированный TCP / IP, Том 1: Протоколы (2-е изд.). Pearson Education. п. 739. ISBN  9780132808187.
5. Хафнер, Кэти. «Салли Флойд, которая помогала вещам работать гладко в Интернете, умерла в 69 лет». Нью-Йорк Таймс. Нью-Йорк Таймс. Получено 5 сентября 2019.
6. Винтон Дж. Серф; Роберт Э. Кан (май 1974 г.). «Протокол для взаимодействия в пакетной сети» (PDF). Транзакции IEEE по коммуникациям. 22 (5): 637–648. Дои:10.1109 / tcom.1974.1092259. Архивировано из оригинал (PDF) 4 марта 2016 г.
7. Lee, B.P .; Balan, R.K .; Jacob, L .; Seah, W.K.G .; Ананда, А.Л. (2000), "Туннели TCP: предотвращение коллапса перегрузки", Материалы 25-й ежегодной конференции IEEE по локальным компьютерным сетям. LCN 2000, стр. 408–417, Дои:10.1109 / LCN.2000.891077, ISBN  0-7695-0912-6, S2CID  34447400
8. Ван Якобсон, Майкл Дж. Карелс. Предотвращение перегрузки и контроль (1988). Материалы симпозиума Sigcomm '88, vol.18 (4): pp.314–329. Стэнфорд, Калифорния. Август 1988 г. В этой статье были разработаны многие алгоритмы предотвращения перегрузки, используемые в TCP / IP.
9. RFC 2001 - Медленный запуск TCP, предотвращение перегрузки, быстрая повторная передача и алгоритмы быстрого восстановления
10. RFC 2581 - Контроль перегрузки TCP
11. RFC 3390 - TCP увеличивает начальное окно TCP
12. Предотвращение перегрузки TCP, объясненное с помощью диаграммы последовательности
13. Салли Флойд: RED (случайное раннее обнаружение) Управление очередью
14. Салли Флойд, Ван Джейкобсон. Шлюзы случайного раннего обнаружения для предотвращения перегрузки (1993). Транзакции IEEE / ACM в сети, vol.1 (4): pp.397–413. Изобретены шлюзы случайного раннего обнаружения (RED).
15. Аналитическая конструкция функции RED, гарантирующая стабильное поведение системы, CiteSeerX  10.1.1.105.5995, ... Преимущество этой функции заключается не только в предотвращении сильных колебаний, но и в недопущении недостаточного использования звена при низких нагрузках. Применимость производной функции не зависит от диапазона нагрузки, никакие параметры настраивать не нужно. По сравнению с исходной линейной функцией капель применимость значительно расширилась ... Наш пример с реалистичными параметрами системы дает аппроксимирующую функцию кубического размера очереди ...
16. Чжан, Чангван; Инь, Цзяньпин; Цай, Чжипин; Чен, Вэйфэн (2010). «RRED: надежный алгоритм RED для противодействия низкоскоростным атакам типа« отказ в обслуживании »» (PDF). Письма по коммуникациям IEEE. IEEE. 14 (5): 489–491. Дои:10.1109 / LCOMM.2010.05.091407. S2CID  1121461.
17. «Обзор предотвращения перегрузки». Cisco Systems. Получено 2020-08-07.
18. RFC 3168 - Добавление явного уведомления о перегрузке (ECN) в IP
19. Сравнительное исследование RED, ECN и TCP Rate Control (1999)
20. Обобщенная оконная реклама для контроля перегрузки TCP (PDF), получено 2020-11-13
21. Объявленное оконное управление потоком TCP в маршрутизаторах, Дои:10.1007/978-0-387-35522-1_12
22. Предложение по Backward ECN для Интернет-протокола

• «Развертывание IP и MPLS QoS для мультисервисных сетей: теория и практика» Джона Эванса, Кларенса Филсфилса (Морган Кауфманн, 2007, ISBN  0-12-370549-5)
• RFC 2914 - Принципы контроля перегрузки, Салли Флойд, сентябрь 2000 г.
• RFC 896 - «Контроль перегрузки в IP / TCP», Джон Нэгл, 6 января 1984 г.
• Введение в Предотвращение перегрузки и контроль, Ван Джейкобсон и Майкл Дж. Карелс, ноябрь 1988 г.

Библиография

• Джон Эванс; Кларенс Филсфилс (2007). Развертывание IP и MPLS QoS для мультисервисных сетей: теория и практика. Морган Кауфманн. ISBN  978-0-12-370549-5.

внешняя ссылка

• Нэгл, Дж. RFC 896: Контроль перегрузки в сетях IP / TCP (1984)
• Флойд, С. RFC 2914: Принципы контроля перегрузки (2000)
• Флойд, С. и К. Фолл, Содействие использованию сквозного контроля перегрузки в Интернете (IEEE / ACM Transactions on Networking, август 1999 г.)
• Салли Флойд, Об эволюции сквозного контроля перегрузки в Интернете: индивидуальный взгляд (Семинар IMA по явлениям масштабирования в сетях связи, октябрь 1999 г.) (pdf формат)
• Ссылочный термин: очередность
• Пьер-Франсуа Кет, Шрирам Челлаппан, Арджан Дуррези, Мукундан Шридхаран, Хитай Озбай, Радж Джайн, «Рекомендации по оптимизации многоуровневой ECN с использованием модели TCP на основе потока жидкости»
• Салли Флойд, Ратул Махаджан, Дэвид Уэтералл: КРАСНЫЙ-ПП: КРАСНЫЙ с преимущественным сбросом
• Универсальный простой симулятор RED для образовательных целей от Мехмета Сузена
• Подходы к контролю перегрузки в пакетных сетях
• Документы в управлении перегрузкой
• Домашняя страница случайного раннего обнаружения
• Домашняя страница явных уведомлений о перегрузке
• Домашняя страница TFRC
• Домашняя страница AIMD-FC
• ^[постоянная мертвая ссылка ] Моделирование контроля перегрузки TCP: быстрое восстановление
• Последние публикации о низкоскоростных атаках типа «отказ в обслуживании» (DoS)