Условие
В одной придуманной нами компании N сетевой архитектор получил задачу: развернуть изолированный контур из 17 серверов. Для обеспечения отказоустойчивости он решил соединить их напрямую патч-кордами так, чтобы от каждого сервера отходило ровно три кабеля к соседним машинам. Архитектор набросал схему и со спокойной душой ушел домой.
На следующее утро на смену заступил дежурный инженер. Взглянув на ТЗ и схему коллеги, он лишь покачал головой, налил кофе и заявил: «Сеть построить не получится, архитектор где-то просчитался».
Может, дежурный просто вредничает или не хочет обжимать лишние провода? 17 серверов — не так много, а три порта на каждом — стандартное требование для резервирования каналов. Или все-таки инженер прав, и законы математики выше в приоритете, чем фантазия архитектора?
Задача
Вы — старший системный архитектор. Помогите коллегам разобраться, кто прав: архитектор или дежурный инженер? Напишите небольшую программу на Python или другом языке, которая проверяет принципиальную возможность существования подобных сетей для любого количества серверов и соединений.
Решение
Сначала переведем задачу с языка сетевых инженеров на язык математики. Наш тестовый контур — это обычный граф. Серверы выступают в роли вершин, а сетевые кабели — это ребра, которые их соединяют. Количество связей, выходящих из одного сервера, в теории графов называется степенью вершины. Теперь по пунктам:
- По условию задачи, у нас есть 17 вершин, и степень каждой из них должна быть равна строго 3. Такой граф (где степени всех вершин равны) называется регулярным.
- Попробуем смоделировать ситуацию и посчитать общее количество портов, которые должны быть задействованы в нашей сети: 17 х 3 = 51.
- Каждый сетевой кабель имеет два конца. Он втыкается в порт одного сервера и в порт другого. Если мы сложим степени всех вершин графа, мы получим удвоенное количество ребер (кабелей).
- Фундаментальная теорема теории графов, также известная как лемма о рукопожатиях, утверждает: сумма степеней всех вершин любого графа всегда должна быть четной, так как она равна 2E, где E — количество ребер.
- В нашем случае сумма степеней равна 51. Но 51 — число нечетное. Если мы попытаемся соединить серверы, у нас физически останется один свободный кабель, который просто некуда будет подключить вторым концом.
Получается, дежурный инженер абсолютно прав: архитектор допустил оплошность, и построить такую сеть физически невозможно.
Решение на Python
Чтобы автоматизировать подобные проверки для будущих проектов дата-центра (например, если серверов станет 100, а связей — 5), напишем лаконичный скрипт на Python.
def check_network_topology(servers_count, links_per_server):
total_ports = servers_count * links_per_server
if total_ports % 2 != 0:
return False, "Сумма портов нечетная, один кабель останется без пары!"
if links_per_server >= servers_count:
return False, (
"У сервера не может быть соседей столько же или больше, "
"чем серверов в сети."
)
return True, f"Топология возможна. Потребуется ровно {total_ports // 2} кабелей."
servers = 17
links = 3
is_valid, message = check_network_topology(servers, links)
print(f"Результат проверки: {is_valid} ({message})")
Или максимально упростим код.
def check_network_topology(servers_count, links_per_server):
total_ports = servers_count * links_per_server
if total_ports % 2 != 0:
return False, "Сумма портов нечетная, один кабель останется без пары!"
if links_per_server >= servers_count:
return False, (
"У сервера не может быть соседей столько же или больше, "
"чем серверов в сети."
)
return True, f"Топология возможна. Потребуется ровно {total_ports // 2} кабелей."
servers = 17
links = 3
is_valid, message = check_network_topology(servers, links)
print(f"Результат проверки: {is_valid} ({message})")
Работая со сложностью O(1), программа мгновенно выдает вердикт. Уровень сложности подходит, потому что нам не нужно перебирать варианты — достаточно знать свойства четности.
Заключение
Архитектор признал свою ошибку, извинился перед дежурным и перерисовал схему, добавив в контур 18-й резервный сервер (для четного количества вершин лемма о рукопожатиях отлично работает). Сеть была успешно поднята, а в качестве примирения инженеры заказали пиццу.
Чтобы больше не путаться в базовых алгоритмах и проектировать инфраструктуру без математических ляпов, архитектор сразу же подписался на рассылку Академии Selectel. В ней регулярно выходят полезные разборы задач, статьи про архитектуру сетей и актуальные тренды из мира IT, которые пригодятся специалисту любого уровня.
