Перегрузка сети

Снижение качества обслуживания из-за высокого сетевого трафика

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

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

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

Пропускная способность сети

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

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

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

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

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

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

Теория управления перегрузкой

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

Пусть будет скоростью потока , будет емкостью канала связи и будет 1, если поток использует канал связи и 0 в противном случае. Пусть , и будут соответствующими векторами и матрицей. Пусть будет возрастающей, строго вогнутой функцией , называемой полезностью , которая измеряет, какую выгоду получает пользователь, передавая данные со скоростью . Тогда оптимальное распределение скорости удовлетворяет ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle c_{l}}$ ${\displaystyle l}$ ${\displaystyle r_{li}}$ ${\displaystyle i}$ ${\displaystyle l}$ ${\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}$

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

Среди способов классификации алгоритмов управления перегрузкой можно выделить:

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

Смягчение

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

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

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

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

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

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

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

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

Предотвращение перегрузки TCP/IP

Алгоритм предотвращения перегрузки TCP является основной основой для контроля перегрузки в Интернете. ^{[10] [11] [12] [13] [14]}

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

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

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

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

Одним из решений является использование случайного раннего обнаружения (RED) в выходной очереди сетевого оборудования. ^{[15] [16]} На портах сетевого оборудования с более чем одной выходной очередью можно использовать взвешенное случайное раннее обнаружение (WRED).

RED косвенно сигнализирует отправителю и получателю TCP, отбрасывая некоторые пакеты, например, когда средняя длина очереди превышает пороговое значение (например, 50%), и удаляет линейно или кубически больше пакетов ^[17] , например, до 100%, по мере дальнейшего заполнения очереди.

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

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

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

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

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

Другой подход заключается в использовании явного уведомления о перегрузке (ECN). ^[20] ECN используется только тогда, когда два хоста сигнализируют, что хотят его использовать. При этом методе бит протокола используется для сигнализации о явной перегрузке. Это лучше, чем косвенное уведомление о перегрузке, сигнализируемое потерей пакетов алгоритмами RED/WRED, но оно требует поддержки обоих хостов. ^{[21] [15]}

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

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

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

Обратная ECN

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

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

Радиосвязь

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

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

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

Контроль доступа

Управление доступом — это любая система, которая требует, чтобы устройства получили разрешение перед установлением новых сетевых подключений. Если новое подключение рискует создать перегрузку, разрешение может быть отклонено. Примерами служат возможности передачи без конкуренции (CFTXOP) в стандарте ITU-T G.hn для домашних сетей по устаревшим кабелям, протокол резервирования ресурсов для IP-сетей и протокол резервирования потоков для Ethernet .

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

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

Ссылки

1. (Аль-Бахадили, 2012, стр. 282) Аль-Бахадили, Х. (2012). Моделирование в проектировании и моделировании компьютерных сетей: использование и анализ. Hershey, PA: 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, KR; Stevens, WR (2011). TCP/IP Illustrated, Том 1: Протоколы (2-е изд.). Pearson Education. стр. 739. ISBN 9780132808187.
5. Ван Якобсон; Майкл Дж. Карелс (ноябрь 1988 г.), Избежание и контроль перегрузки (PDF) , В октябре 1986 г. в Интернете произошел первый из серии «коллапсов перегрузки». В этот период пропускная способность от LBL до Калифорнийского университета в Беркли (сайты, разделенные 400 ярдами и двумя переходами IMP) упала с 32 Кбит/с до 40 бит/с. Мы были очарованы этим внезапным падением пропускной способности в тысячу раз и приступили к расследованию того, почему все стало так плохо. В частности, мы задавались вопросом, ведет ли себя неправильно 4.3BSD (Berkeley UNIX) TCP или его можно настроить для лучшей работы в ужасных сетевых условиях. Ответ на оба этих вопроса был «да».
6. Хафнер, Кэти (4 сентября 2019 г.). «Салли Флойд, которая помогла наладить работу в Интернете, умерла в возрасте 69 лет». New York Times . Получено 5 сентября 2019 г.
7. Нанда, Приядарси (2000-11-01). "Подход теории управления к контролю перегрузки в интрасети". Тома трудов IFAC . 16-й семинар IFAC по распределенным системам управления компьютерами (DCCS 2000), Сидней, Австралия, 29 ноября - 1 декабря 2000 г. 33 (30): 91–94. doi :10.1016/S1474-6670(17)36735-6. ISSN  1474-6670.
8. Винтон Г. Серф; Роберт Э. Кан (май 1974 г.). «Протокол для пакетной сетевой интеркоммуникации» (PDF) . IEEE Transactions on Communications . 22 (5): 637–648. doi :10.1109/tcom.1974.1092259. Архивировано из оригинала (PDF) 4 марта 2016 г.
9. Ли, Б. П.; Балан, Р. К.; Якоб, Л.; Сиа, В. К. Г.; Ананда, А. Л. (2000), «TCP-туннели: предотвращение коллапса перегрузки», Труды 25-й ежегодной конференции IEEE по локальным компьютерным сетям. LCN 2000 , стр. 408–417, doi :10.1109/LCN.2000.891077, ISBN 0-7695-0912-6, S2CID  34447400
10. Ван Якобсон , Майкл Дж. Карелс . Избежание и контроль перегрузки (1988). Труды симпозиума Sigcomm '88 , т. 18(4): стр. 314–329. Стэнфорд, Калифорния. Август 1988. Эта статья положила начало многим алгоритмам избежания перегрузки, используемым в TCP/IP.
11. RFC 2001 — алгоритмы медленного старта TCP, предотвращения перегрузки, быстрой повторной передачи и быстрого восстановления
12. RFC 2581 — Управление перегрузкой TCP
13. RFC 3390 - TCP Увеличение начального окна TCP
14. Объяснение предотвращения перегрузки TCP с помощью диаграммы последовательности
15. Салли Флойд: RED (Случайное раннее обнаружение) Управление очередями
16. Салли Флойд, Ван Якобсон. Шлюзы случайного раннего обнаружения для предотвращения перегрузки (1993). Труды IEEE/ACM по сетям , т. 1(4): стр. 397–413. Изобретены шлюзы случайного раннего обнаружения (RED).
17. Аналитическая RED-функция, гарантирующая стабильное поведение системы , CiteSeerX 10.1.1.105.5995 , ...Преимущество этой функции заключается не только в избежании сильных колебаний, но и в избежании недоиспользования канала при низких нагрузках. Применимость полученной функции не зависит от диапазона нагрузки, никакие параметры не нужно настраивать. По сравнению с исходной линейной функцией сброса применимость значительно расширена...Наш пример с реалистичными параметрами системы дает аппроксимирующую функцию кубической части размера очереди... 
18. Чжан, Чанван; Инь, Цзяньпин; Цай, Чжипин; Чэнь, Вэйфэн (2010). «RRED: Надежный алгоритм RED для противодействия низкоскоростным атакам типа «отказ в обслуживании»» (PDF) . IEEE Communications Letters . 14 (5). IEEE : 489–491. doi : 10.1109/LCOMM.2010.05.091407. S2CID  1121461.
19. "Обзор предотвращения перегрузки". Cisco Systems . Получено 2020-08-07 .
20. RFC 3168 — Добавление явного уведомления о перегрузке (ECN) к IP
21. Сравнительное исследование RED, ECN и TCP Rate Control (1999)
22. Обобщенное объявление окна для TCP CongestionControl (PDF) , получено 2020-11-13
23. Pop, O.; Moldován, I.; Simon, Cs.; Bíró, J.; Koike, A.; Ishii, H. (2000), «Рекламируемое управление потоком TCP на основе окна в маршрутизаторах», Telecommunication Network Intelligence , стр. 197–218, doi : 10.1007/978-0-387-35522-1_12 , ISBN 978-1-4757-6693-6
24. Предложение по обратному ECN для интернет-протокола

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

Внешние ссылки

• Флойд, С. и К. Фолл, Продвижение использования сквозного контроля перегрузки в Интернете (IEEE/ACM Transactions on Networking, август 1999 г.)
• Салли Флойд, Об эволюции сквозного контроля перегрузки в Интернете: уникальный взгляд (Семинар IMA по явлениям масштабирования в сетях связи, октябрь 1999 г.) ( формат pdf )
• Ссылочный термин: Очередь Архивировано 2003-03-08 в Wayback Machine
• Пьер-Франсуа Ке, Шрирам Челлаппан, Аржан Дурреси, Мукундан Шридхаран, Хитай Озбай, Радж Джейн, «Руководство по оптимизации многоуровневой ECN с использованием модели TCP на основе потока жидкости»
• Салли Флойд, Ратул Махаджан, Дэвид Уэзеролл: RED-PD: RED с преимущественным отбрасыванием Архивировано 2003-04-02 в Wayback Machine
• Простой универсальный симулятор RED для образовательных целей от Мехмета Сюзена
• Подходы к контролю перегрузки в пакетных сетях
• Статьи по контролю за перегрузками
• Домашняя страница случайного раннего обнаружения
• Домашняя страница явного уведомления о перегрузке
• Домашняя страница TFRC
• Домашняя страница AIMD-FC
• Последние публикации по низкоуровневым атакам типа «отказ в обслуживании» (DoS)