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

Начнём с классического набора задач — маршрутизация и поиск кратчайшего пути. В сетевых протоколах применяются два базовых подхода: distance-vector (вектор расстояний, например RIP) и link-state (состояние каналов, например OSPF). Для link-state узел собирает информацию о топологии и затем использует алгоритм Dijkstra для вычисления кратчайших путей. Пример: граф из четырёх узлов A, B, C, D с весами ребер — пошагово Dijkstra выбирает ближайший непомеченный узел, обновляет расстояния соседей и повторяет. В сетях важно учитывать, что веса могут отражать не только задержку, но и пропускную способность или стоимость, поэтому алгоритм всегда применяется с метрикой, соответствующей задаче.

Другой важный алгоритм — Bellman–Ford, используемый в distance-vector подходе. Он работает итеративно и позволяет обнаруживать отрицательные циклы (что полезно в теоретическом плане). В практических сетях distance-vector проще по реализации, но менее устойчив к петлям; для их избежания применяются техники вроде split horizon или poison reverse. При проектировании протокола нужно выбирать между быстротой сходимости и объёмом передаваемой информации.

Ключевая роль в сетях отводится структурам данных для хранения маршрутных таблиц — триграммы (trie), radix-деревья, патрицианские trie (Patricia trie) и многобитовые trie. Для задачи Longest Prefix Match (LPM) используются оптимизированные trie-структуры: адрес IPv4/IPv6 разбивается на биты, и поиск идёт по дереву до самого длинного совпадающего префикса. На практике для ускорения поиска применяют многобитовые обходы и таблицы переходов; в аппаратных маршрутизаторах часто используют TCAM (Ternary Content Addressable Memory) для быстрого сопоставления масок, но TCAM дорог и ограничен по объёму, поэтому комбинация программных и аппаратных структур — обычная компромиссная стратегия.

Для фильтрации и быстрого теста принадлежности потоков используются компактные структуры, дающие экономию места за счёт допустимых ошибок, — Bloom-фильтры и их варианты. Bloom-фильтр хранит битовый массив и несколько хешей каждого элемента. Он гарантирует отсутствие ложных отрицаний, но может давать ложные срабатывания (false positives). Пример: массив из 1000 бит, 3 хеш-функции, вставлено 100 элементов — вероятность ложноположительного ответа можно оценить формулой (1 − e^{−kn/m})^k. Для подсчёта частот и потоков используются Count-Min Sketch, позволяющий оценить частоту элемента с ограниченной ошибкой при малой памяти; он полезен в задачах DDoS-детекции и учёта трафика в реальном времени.

Очереди и дисциплины обслуживания — ещё одна важная группа структур и алгоритмов. На уровне маршрутизаторов и коммутаторов пакеты буферизуются в очередях: простейшая модель — FIFO, более продвинутые — Priority Queuing, Weighted Fair Queueing (WFQ), Deficit Round Robin (DRR). Для борьбы с переполнением применяется RED (Random Early Detection): алгоритм отслеживает среднюю длину очереди и случайно дропает пакеты до момента переполнения, что сигнализирует отправителю о начале перегрузки. Механизмы управления перегрузкой тесно связаны с протоколами транспортного уровня: модель AIMD (additive increase, multiplicative decrease) реализована в TCP — совокупность фаз slow start, congestion avoidance, fast retransmit и fast recovery определяет поведение окна перегрузки cwnd. На примере: при slow start cwnd удваивается каждый RTT, пока не достигнет порога ssthresh, затем переходит в медианный режим, где cwnd растёт линейно.

В задачах высокой скорости обработки пакетов важны временные и пространственные характеристики алгоритмов. Время поиска маршрута в trie может быть O(L) по числу битов префикса, в хеш-таблице — амортизированное O(1), но память и коллизии важны. TCAM обеспечивает O(1) поиск на уровне аппаратуры, но имеет высокое энергопотребление и стоимость. При проектировании следует сравнивать: например, radix-tree для 1 млн префиксов может занимать значительную оперативную память, в то время как сжатые multi-bit trie уменьшат глубину, улучшив кэш-попадания.

Мультимедиа и группы рассылки требуют специальных алгоритмов: multicast использует деревья распределения. Есть два подхода: построение кратчайших путевых деревьев (по алгоритму Dijkstra с мультикастовой модификацией) или построение общих деревьев (Rendezvous point) — PIM-SM. Структура данных для multicast часто хранит состояния групп и интерфейсов (например, IGMP/MLD у хостов). При этом задача Steiner tree (минимальное дерево соединяющее группу) является NP-трудной, поэтому применяются приближённые алгоритмы и эвристики.

Безопасность и криптография в сетях также полагаются на алгоритмы и структуры данных. Для ускорения проверки целостности используют хеш-функции и MAC; таблицы ассоциаций ключей (Key-Value) и структуры для управления сессиями (session tables) позволяют быстро сопоставлять пакет с контекстом безопасности. При проектировании протоколов (например TLS) важно учитывать порядок операций и состояние: handshake, обмен ключами, установка шифрованной сессии — всё это реализуется через finite state machines и хэш-таблицы для сессий на стороне сервера.

Современные тенденции: SDN (Software-Defined Networking) и контроллеры управления используют распределённые алгоритмы согласования и консенсуса для глобального вида сети. Для быстрого прямого сопоставления потоков применяются OpenFlow-таблицы — набор правил match-action, которые реализуются аппаратно/программно. Ограничения TCAM в сочетании с необходимостью большого числа правил приводят к использованию техники агрегации правил, регулярных выражений и приоритетов. Распределённые алгоритмы обновления состояний (consistent update) используют версии и транзакционные подходы, чтобы избежать рассогласования данных и кратковременных петель при обновлении правил.

Наконец, практика проектирования сетевого ПО и аппаратуры диктует ряд правил и компромиссов. Выбор структуры данных — это компромисс между временем доступа, памятью и простотой аппаратной реализации. При обработке 100 Gbps потока каждое дополнительное чтение/запись дорого по времени, поэтому часто используются специализированные аппаратные блоки, конвейеры и параллелизм. Для прототипирования и исследований применяют симуляторы (ns-3) и контролируемые тесты, чтобы оценить поведение алгоритмов под нагрузкой.

Кратко подытожим практические рекомендации: используйте trie и его оптимизации для LPM и маршрутизации по префиксу; применяйте хеш-таблицы и скетчи для учёта потоков и частот; используйте Bloom-фильтры для быстрой проверки принадлежности с допустимыми ложноположительными ошибками; выбирайте дисциплины очередей исходя из целей QoS (WFQ для справедливого разделения, RED — для раннего контроля перегрузки); учитывайте апаратные ограничения (TCAM/ASIC) при проектировании. Понимание алгоритмических деталей, их сложности и поведения в реальных условиях — ключ к созданию надёжных и эффективных сетевых систем.

• Практический пример Dijkstra: пошаговое вычисление кратчайших расстояний в топологии (инициализация расстояний, выбор минимального узла, релаксация соседей, повторение до охвата всех узлов).
• Пример Bloom-фильтра: битовый массив и примеры хешей для трёх вставляемых IP-адресов, оценка вероятности ложноположительного ответа.
• Схема TCP: slow start — удвоение cwnd в RTT, достижение ssthresh — переход на AIMD, реакция на потерю (уменьшение окна).

Если вам нужно, я могу подробно разобрать один из перечисленных алгоритмов с конкретным числовым примером (пошаговый Dijkstra с таблицами, построение Patricia-trie для набора префиксов, расчёт параметров Bloom-фильтра или эмуляция поведения TCP при заданной задержке и потере). Также могу предложить сравнение по сложности и памяти для нескольких структур как таблицу (в текстовом виде), чтобы упростить выбор при проектировании реальной сети.