PART II — 구조
수십억 개의 컴퓨터가 어떻게 서로 말을 걸까요? 그 답은 결국 네트워크 토폴로지의 수학에 있습니다. 이 챕터에서는 그래프를 도구 삼아 데이터 센터, 멀티프로세서, 인터넷의 뼈대를 모델링하고, 어떤 토폴로지가 빠르고 싸고 막히지 않는지 따져 봅니다. 그래프 이론이 추상적 놀이가 아니라 진짜 엔지니어링 도구라는 사실을 보여 주는 챕터예요.
네트워크라고 하면 거창해 보이지만, 본질은 단순합니다. 입력이라 부르는 점들 \(I_1, I_2, \dots, I_N\)이 있고, 출력이라 부르는 점들 \(O_1, O_2, \dots, O_N\)이 있습니다. 그리고 각 입력은 어딘가의 출력으로 메시지를 보내고 싶어 합니다. 데이터 센터에서는 입력이 서버, 출력도 서버. 멀티코어 칩에서는 입력이 코어, 출력은 메모리 뱅크. 본질은 같습니다.
문제는 입력과 출력 사이를 직선으로 잇는 것이 비현실적이라는 점이에요. \(N\)개 입력과 \(N\)개 출력을 모두 직접 연결하면 선이 \(N^2\)개 필요합니다. \(N=10^6\)이면 선이 \(10^{12}\)개. 이걸 진짜로 깔 사람은 없겠죠. 그래서 가운데에 스위치(switch)들을 두고, 메시지가 스위치를 거쳐 가도록 만듭니다. 결국 우리가 다루는 건 정점이 입력·스위치·출력이고 간선이 통신선인 그래프예요.
정의 11.1.1 (통신 네트워크)
입력 집합 \(\mathcal{I} = \{I_1, \dots, I_N\}\)과 출력 집합 \(\mathcal{O} = \{O_1, \dots, O_N\}\), 그리고 스위치 집합 \(S\)로 이루어진 그래프 \(G\)를 통신 네트워크라 부릅니다. 보통 모든 \(I_i\)는 차수 1, 모든 \(O_j\)도 차수 1로 두고, 가운데 스위치들이 라우팅을 담당합니다.
이 위에서 진짜 풀어야 할 문제는 무엇일까요? 어떤 입력이 어떤 출력으로 가고 싶다는 요청이 한꺼번에 들어옵니다. 이 요청을 깔끔하게 모델링한 것이 순열 라우팅(permutation routing)입니다.
정의 11.1.2 (라우팅 문제)
\(\{1, \dots, N\}\) 위의 순열 \(\pi\)가 주어지면, 모든 \(i\)에 대해 입력 \(I_i\)에서 출력 \(O_{\pi(i)}\)로 가는 경로 \(P_i\)를 찾는 것이 라우팅 문제입니다. 경로들의 모음 \(\{P_1, \dots, P_N\}\)을 그 순열에 대한 라우팅이라 부릅니다.
예제 11.1.3
입력 4개, 출력 4개, 가운데 스위치 한 개만 있는 가장 단순한 네트워크를 상상해 봅시다. 모든 입력이 그 스위치로 들어가고, 스위치가 적절히 출력으로 보내 줍니다. 어떤 순열이 와도 라우팅은 가능해요. 다만 모든 메시지가 스위치 하나를 통과해야 하니, 한 정점에 부하가 몰립니다. "되긴 되는데 막히는" 전형적인 예입니다.
여기서 우리는 라우팅이 가능한가만 묻는 게 아니라, 얼마나 좋게 가능한가를 묻고 싶어집니다. 경로가 너무 길면 지연(latency)이 커지고, 한 간선에 너무 많이 몰리면 병목이 되니까요. 그래서 다음 절에서는 네트워크의 품질을 재는 자(尺)들을 정의합니다.
네트워크를 평가하는 자는 크게 네 가지입니다. 지름, 혼잡도, 비용(스위치 수), 그리고 대역폭. 하나만 가지고는 좋은 네트워크를 못 만들고, 항상 트레이드오프가 있다는 점을 미리 강조해 둡니다.
정의 11.2.1 (지름)
네트워크 \(G\)의 지름(diameter)은 \[ \mathrm{diam}(G) = \max_{u, v} \, d(u, v) \] 입니다. 여기서 \(d(u,v)\)는 \(u\)와 \(v\) 사이의 최단 경로 길이고, 보통 입력에서 출력까지의 거리를 따집니다. 지름은 라우팅의 최악 지연을 직관적으로 잡아 주는 양이에요.
정의 11.2.2 (혼잡도)
순열 \(\pi\)에 대한 라우팅 \(\{P_1, \dots, P_N\}\)이 주어졌을 때, 그 라우팅의 혼잡도(congestion)는 한 간선을 지나는 경로의 최대 수입니다. \[ \mathrm{cong}(\{P_i\}) = \max_{e \in E(G)} \,\bigl| \{ i : e \in P_i \} \bigr|. \] 그리고 네트워크 자체의 혼잡도는 모든 순열에 대해 라우팅을 가장 잘 골랐을 때의 최댓값으로 정의합니다. 즉 \[ \mathrm{cong}(G) = \max_{\pi} \, \min_{\{P_i\}} \mathrm{cong}(\{P_i\}). \] 어떤 순열이 와도 이 값 이하로 막힘을 줄일 수 있다는 뜻이에요.
혼잡도 정의가 살짝 어지러울 수 있어요. "최악의 순열을 가져와 보세요. 그래도 우리는 라우팅을 잘 골라서 한 간선당 통과 메시지 수를 이 정도로 막을 수 있어요." 이 약속의 보증치가 \(\mathrm{cong}(G)\)입니다.
정의 11.2.3 (비용과 대역폭)
비용은 보통 스위치의 수, 또는 간선의 수, 또는 각 스위치의 차수로 잽니다. 칩으로 만들 때 핀 수와 면적이 곧 돈이라 매우 실용적인 척도예요. 대역폭(bandwidth)은 단위 시간당 통과시킬 수 있는 메시지 수로, 이상적인 모델에서는 혼잡도의 역수에 비례한다고 봐도 좋습니다.
노트
지름은 짧을수록 좋고, 혼잡도도 작을수록 좋고, 비용도 적을수록 좋습니다. 그런데 셋이 동시에 작아지지 않습니다. 어디를 죄면 어딘가가 늘어나요. 다음 절은 본질적으로 이 트레이드오프 카탈로그입니다.
예제 11.2.4
예제 11.1.3의 단일 스위치 네트워크는 지름이 2(입력→스위치→출력)로 매우 짧습니다. 비용도 스위치 1개로 최소. 그런데 모든 메시지가 같은 두 간선을 공유하니 혼잡도가 \(N\)에 가깝죠. 짧고 싸지만 막혀 죽는 구조입니다.
이제 자(尺)는 다 만들었으니, 실제 네트워크 디자인들을 그 자에 대 봅시다.
네트워크 토폴로지의 동물원에는 별별 친구들이 다 있지만, 교과서에 빠지지 않는 네 가지를 살펴봅니다. 완전 이분 그래프, 2D 메시, 버터플라이, 그리고 베네스 네트워크.
모든 입력을 모든 출력에 직접 연결한 구조입니다. 입력과 출력 사이 간선이 \(N^2\)개. 지름은 1, 혼잡도는 1(각 입력은 자기 출력으로 가는 한 줄만 쓰면 끝). 완벽해 보이죠? 그런데 비용이 \(\Theta(N^2)\)이라 \(N\)이 커지면 미친 짓이 됩니다.
정리 11.3.1 (완전 이분 그래프의 측정치)
\(K_{N,N}\)의 지름은 1, 모든 순열 라우팅의 혼잡도는 1, 간선 수는 \(N^2\), 각 정점의 차수는 \(N\)입니다.
\(N = n^2\)개의 입력과 출력을 \(n \times n\) 격자에 늘어놓은 구조입니다. 각 격자칸이 작은 스위치이고, 옆 칸끼리만 직접 연결됩니다. 만들기 쉽고(인접 연결만 있으니까) 비용도 \(\Theta(N)\)으로 매우 쌉니다. 대신 한 끝에서 다른 끝까지 가려면 격자를 가로질러야 해서 지름이 \(\Theta(\sqrt{N})\)에 달해요.
예제 11.3.2
\(n=4\)인 \(4 \times 4\) 메시. 입력 \(I_{(0,0)}\)에서 출력 \(O_{(3,3)}\)으로 가려면 가로 3 + 세로 3 = 6 칸을 거쳐야 합니다. 지름은 약 \(2(n-1)\)이에요. 한편 모든 메시지가 격자 한가운데 가로선을 가로지르는 최악 순열에서는 그 가로선의 \(n\)개 간선에 \(\Theta(n^2) = \Theta(N)\)개 경로가 몰려 혼잡도가 \(\Theta(\sqrt{N})\) 정도 됩니다.
\(N = 2^n\)일 때, 입력 측 \(N\)개·출력 측 \(N\)개와 가운데 \(n+1\)개 층을 두고, 각 층마다 비트 하나씩을 "고를지 말지" 결정하는 스위치를 배치하는 구조입니다. 입력에서 출력까지 정확히 \(n+1\) 단계를 거치고, 각 단계에서 한 비트를 결정하면 모든 출력에 도달할 수 있어요.
정리 11.3.3 (버터플라이의 측정치)
\(N = 2^n\)인 버터플라이 네트워크의 지름은 \(n+1 = \log_2 N + 1\), 스위치 수는 \(\Theta(N \log N)\), 각 스위치의 차수는 상수(보통 4). 그러나 최악 순열의 혼잡도는 \(\Theta(\sqrt{N})\)에 이릅니다.
지름이 \(\log N\)으로 정말 작아진다는 점에 주목하세요. 메시 대비 지수적으로 짧습니다. 대신 어떤 못된 순열을 가져오면 한 간선에 \(\sqrt{N}\) 개의 경로가 몰리는 일이 벌어집니다. "빠르긴 한데 운 나쁜 패턴에서는 막힌다"가 버터플라이의 성격이에요.
버터플라이의 혼잡도 문제를 해결하는 영리한 트릭은, 버터플라이를 두 개 등을 맞대고 붙여 거의 거울처럼 이어붙이는 것입니다. 이렇게 만든 것이 베네스 네트워크예요. 지름은 \(2\log_2 N\) 정도로 살짝 늘지만, 어떤 순열이 와도 혼잡도 1로 라우팅이 가능하다는 굉장한 성질을 얻습니다.
정리 11.3.4 (베네스의 라우팅)
\(N = 2^n\)인 베네스 네트워크에서는 임의의 순열 \(\pi\)에 대해 모든 경로가 서로 간선을 공유하지 않는 라우팅이 존재합니다. 즉 \(\mathrm{cong}(G) = 1\). 지름은 \(2n+1 = \Theta(\log N)\), 스위치 수는 \(\Theta(N \log N)\)입니다.
증명 스케치
핵심 아이디어는 재귀입니다. 베네스 네트워크는 첫 층과 마지막 층을 빼고 나면 두 개의 작은 베네스 네트워크가 위·아래로 들어 있는 구조예요. 각 입력은 첫 층에서 위쪽 부분망으로 갈지 아래쪽으로 갈지 둘 중 하나를 골라야 하고, 같은 짝이 되는 출력의 마지막 층 짝은 그 반대로 가야 충돌이 안 납니다. 이 조건을 그래프 색칠 문제로 옮기면 이분 그래프의 2-색칠 가능성으로 환원되고, 홀수 길이 사이클이 없음을 보이면 됩니다. 작은 부분망에서도 같은 논리를 재귀적으로 적용하면 전체 라우팅이 만들어져요.
∎
네 가지 디자인을 같은 자(尺)로 정렬하면 다음과 같습니다.
| 네트워크 | 지름 | 혼잡도 | 스위치 수 | 스위치 차수 |
|---|---|---|---|---|
| 완전 이분 \(K_{N,N}\) | \(1\) | \(1\) | \(\Theta(N)\) | \(\Theta(N)\) |
| 2D 메시 | \(\Theta(\sqrt{N})\) | \(\Theta(\sqrt{N})\) | \(\Theta(N)\) | \(O(1)\) |
| 버터플라이 | \(\Theta(\log N)\) | \(\Theta(\sqrt{N})\) | \(\Theta(N \log N)\) | \(O(1)\) |
| 베네스 | \(\Theta(\log N)\) | \(1\) | \(\Theta(N \log N)\) | \(O(1)\) |
노트
표를 가만히 보면 베네스가 거의 만능처럼 보입니다. 지름은 \(\log N\), 혼잡도는 1, 스위치 수는 \(N\log N\), 차수는 상수. 그런데 빠진 비용이 하나 있어요. 베네스는 라우팅 자체를 계산하는 비용이 듭니다. 임의의 순열을 받았을 때 충돌 없는 경로를 정해 주는 알고리즘이 \(O(N \log N)\) 정도 시간을 먹어요. 메시지가 자주 바뀌는 환경이면 이 부담이 작지 않습니다. 그래서 실제 데이터 센터는 종종 메시 + 그 위에 트리(fat-tree, Clos 네트워크 같은) 같은 하이브리드를 씁니다.
마지막으로 이 챕터의 메시지를 한 줄로 정리해 두면. 통신 네트워크 설계는 지름·혼잡도·비용이라는 삼각형 안에서 어디에 무게를 둘지 고르는 게임입니다. 그래프라는 한 가지 언어로 셋을 모두 정량화할 수 있다는 사실이, 이산수학이 시스템 설계에 끼친 가장 우아한 기여 중 하나예요. 다음 챕터에서는 이 그래프 위에서 걷기가 갖는 또 다른 면 — 연결성, 트리, 색칠 — 을 살펴봅니다.