NetGraph Optimizer: High-Performance MCF Solver for SDN/Telecom Networks

Оптимизатор распределения трафика в SDN-сети: для каждого потока (flow) с требованиями по полосе и максимальной задержке находим путь так, чтобы ни один линк не был перегружен, а максимальная утилизация канала (MLU) была минимальной.

Это задача Multi-Commodity Flow, решаемая комбинацией:

• K-shortest paths (алгоритм Йена + Дейкстра) — кандидаты путей; A* пока только рассматривается. Семантику Cost/Latency и отсечение по maxLatency нужно проверить;
• Beam Search — последовательная эвристика (top-N частичных решений по MLU);
• Parallel Branch & Bound — параллельный поиск с отсечением по текущему MLU и бюджетом узлов; оптимальность подтверждается только при завершении полного поиска;
• Граф в CSR-формате — плоские массивы, обход соседей через Span<int> без аллокаций;
• PathPool — переиспользование int[] в горячем цикле (минимум GC).

---

Архитектура

flowchart LR
    TG[TrafficGenerator] --> CB
    GG[GraphGenerator] --> G[NetworkGraph CSR]
    G --> F[KShortestPathsFinder]
    F --> CB[CandidateBuilder]
    CB --> SB[SequentialBeamSolver]
    CB --> PBB[ParallelBranchAndBoundSolver]
    PBB --> DE[DotExporter]

Loading

---

Ключевые инженерные решения

Решение	Что даёт
CSR-граф (_offsets + _edgeIndices)	Cache locality, обход соседей через ReadOnlySpan<int> без аллокаций
BinaryHeap на плоском массиве	Ручная мин-куча, ресайз как у std::vector, zero-alloc
Алгоритм Йена с Дейкстрой и переиспользуемыми буферами	K-кратчайших путей; фильтр maxLatency требует проверки семантики Cost/Latency
PathPool на ConcurrentBag<int[]>	Потокобезопасный пул массивов путей для повторного использования в Beam Search
Beam Search	Последовательная эвристика, beamWidth лучших состояний, сортировка по MLU
Parallel B&B	Parallel.For на первом уровне, отсечение по Volatile.Read(ref _best), бюджет узлов
Span<T> для утилизаций	Оценка MLU без аллокаций и копирований

---

Алгоритмическое ядро

Компонент	Реализация
Граф сети	CSR: Link[] + _offsets + _edgeIndices, обход через ReadOnlySpan<int>
Поиск путей	Алгоритм Йена с Дейкстрой; соответствие Cost и Latency и отсечение по maxLatency требуют проверки
K путей	Настраивается через CLI (k), отсечение по maxLatency
Beam Search	Последовательный обход спросов, beamWidth лучших состояний по MLU
Branch & Bound	Параллельный, отсечение по нижней границе, бюджет узлов, rollback вместо копирования
Целевая функция	Minimize MLU (Max Link Utilization)

---

Структура

src/NetGraph.Core              # граф (CSR), k-путей, солверы, экспорт в DOT
src/NetGraph.Cli               # демо: генерация сети + запуск солверов + graph.dot
tests/NetGraph.Tests           # xunit: корректность графа, путей, солверов
benchmarks/NetGraph.Benchmarks # BenchmarkDotNet: Sequential vs Parallel B&B
docs/                          # планы экспериментов и материалы проекта

---

Как запустить

# Демо-запуск
dotnet run --project src/NetGraph.Cli -c Release -- 50 120 60 5 8
# аргументы: [узлы] [доп. рёбра] [потоки] [k путей] [beam width]

# Тесты
dotnet test

# Бенчмарки
dotnet run --project benchmarks/NetGraph.Benchmarks -c Release

Визуализация результата:

dot -Tpng graph.dot -o network.png

---

Результаты бенчмарков

Заполняется по выводу BenchmarkDotNet (dotnet run --project benchmarks/NetGraph.Benchmarks -c Release):

Method	Mean	Error	StdDev	Median	Ratio	RatioSD	Gen0	Gen1	Allocated	Alloc Ratio
SequentialBeam	268.5 us	1.80 us	1.68 us	268.6 us	1.00	0.01	2.9297	0.4883	120.2 KB	1.00
ParallelBranchAndBound	484,531.2 us	43,468.84 us	128,168.87 us	399,222.5 us	1,804.97	475.35	—	—	14.35 KB	0.12

Что видно:

• Beam Search — ~269 мкс на инстансе 50 узлов / 60 потоков.
• В этом прогоне Parallel B&B занял ~485 мс; его результат не следует считать точным оптимумом, если достигнут бюджет узлов до полного обхода.
• Managed-аллокации B&B — 14.35 KB против 120.2 KB у Beam. Это метрика данного benchmark-прогона, не оценка unmanaged-памяти.

Отчёт BenchmarkDotNet создан на Windows 10, Ryzen 7 4800H, .NET 10.0.11. Значения характеризуют только этот прогон и могут отличаться от результатов на другом CPU/ОС.

Скриншоты профилировщика (dotMemory / PerfView) — в docs/.

Планы экспериментов

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

• Сравнение алгоритмов распределения потоков — Beam ширины 1, Layered Beam, Bounded Best-First и Branch & Bound.
• Сравнение поиска кратчайших путей — Дейкстра и A* внутри генерации кандидатов; перед этим требуется уточнить семантику Cost и Latency.
• Сравнение scratch-буферов Beam Search — PathPool, ArrayPool и arena. Этот эксперимент имеет смысл после выбора репрезентативного алгоритма/сценария, чтобы отделить эффект памяти от эффекта самого алгоритма.

Эти документы появились после оценки обновлённого PoC dotnet-arena-bench для этого проекта и обсуждения возможных алгоритмов. PoC включает синтетические измерения на двух разных стендах: его абсолютные значения не переносятся на этот проект, а повторение на другом стенде показывает, почему нужны измерения на целевой нагрузке. В частности, в модели E03 ArrayPool на 12–33% дешевле арены для scratch на узел, тогда как преимущество арены на пакетных операциях не доказывает её выгоду для Beam Search с состояниями, живущими между слоями.

Рекомендуемый порядок реализации и тестирования

1. Зафиксировать семантику задачи. Определить целевую функцию, когда решение считается допустимым, и что означает ограничение MLU <= 1. Для поиска путей отдельно определить назначение Cost, Latency и maxLatency. Без этого алгоритмы могут решать разные задачи.
2. Добавить тестовый оракул для малых экземпляров. Полным перебором проверить минимальный MLU там, где пространство вариантов невелико. Дополнить независимой проверкой назначения, ограничений ёмкости и пересчёта MLU через MluEvaluator.
3. Закрепить поведение существующих алгоритмов. Тестами проверить Layered Beam при beamWidth = 1 и обычной ширине, а также Branch & Bound с явными настройками. Сравнить с оракулом на малых случаях и зафиксировать поведение при нехватке кандидатов и исчерпании бюджета.
4. Снять baseline до новых алгоритмов. На одинаковых заранее построенных кандидатах измерить Beam ширины 1 и несколько фиксированных ширин, затем Branch & Bound. Записать качество, время, число раскрытых состояний, аллокации и параметры параллелизма.
5. Реализовать Bounded Best-First. Сначала определить приоритет, детерминированное разрешение равенств, политику переполнения фронта и завершение. Добавить тесты на малых графах, сравнить качество с оракулом, затем включить в те же бенчмарки.
6. Отдельно проверить shortest-path поиск. После фиксации весовой семантики сравнить Дейкстру и A* на корректности кратчайшего пути, top-k кандидатов и ограничений задержки; отдельно измерить подготовку эвристики и end-to-end построение кандидатов.
7. Только после выбора репрезентативного варианта измерять память. Сравнить PathPool, ArrayPool и arena на одинаковой реализации/нагрузке, сохраняя тесты корректности и проверяя жизненный цикл буферов.
8. Решение о production-внедрении принимать по результатам. Повторить устойчивые прогоны на нескольких заранее заданных сценариях; документировать ограничения и не менять production-поведение только на основании синтетического бенчмарка.

---

Требования

• .NET 10 SDK (или .NET 10 Runtime)
• Graphviz — для визуализации (dot -Tpng graph.dot -o network.png)
• BenchmarkDotNet — подтягивается через NuGet

---

Лицензия

Проект распространяется под лицензией MIT. См. LICENSE.

---

Автор

cherninkiy — github.com/cherninkiy