Центры обработки данных (ЦОД) — это сердце всемирной паутины, где происходит обмен и обработка огромных объёмов данных. Пакеты данных передаются по кратчайшим путям, что позволяет оптимально использовать сетевые ресурсы. В отличие от традиционных иерархических сетей, инфраструктуры дата-центров являются многоранговой плоской архитектурой. Они имеют тысячи взаимосвязанных узлов, что предъявляет высокие требования к выполнению алгоритмов поиска кратчайшего пути, от точки входящего запроса к нужному узлу (серверу). Эти сети могут состоять из десятков или сотен тысяч узлов и, естественно, страдают от частых сбоев программного (либо аппаратного) обеспечения, а также перегрузки каналов. Пакеты передаваемых данных маршрутизируются по кратчайшим путям с использованием достаточных ресурсов, чтобы обеспечить эффективное использование сети и минимизировать задержки.

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

Обладая превосходной производительностью и низким уровнем сложности алгоритмы прокладывания кратчайшего пути стали доминировать во всех типах сетей связи. Используя такие алгоритмы для маршрутизации пакетов, эти топологии максимизируют пропускную способность и минимизируют задержки. По этой причине, в протоколах маршрутизации Интернета, на протяжении десятилетий использовались такие алгоритмы, как протокол открытого кратчайшего пути (open shortest path first), протокол промежуточных систем (IS — intermediate system) и протокол пограничного шлюза (border gateway). Все они также работают в сочетании с балансировкой нагрузки. Самым популярным примером протоколов маршрутизации, используемых в центрах обработки данных, является стратегия многопутевого доступа с равной ценностью (ECMP — equal cost multipath protocol). Однако в сетях, с огромным количеством выделенных и виртуальных серверов, даже расчёт кратчайших путей представляет собой проблему из-за чрезвычайно большого количества узлов. В предыдущее время эта проблема решалась с помощью более простых алгоритмов, с меньшей производительностью. Но с ростом распространения Интернета стали использоваться новые подходы и технологические возможности для ускорения расчёта кратчайшего пути в сетях крупных дата-центров.

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