12. 통신 네트워크 (Communication Networks)

그래프 이론을 통해 통신 네트워크를 분석하는 법을 알아보자. 입력 터미널과 출력 터미널이 각각 $N$개인 네트워크를 $N\times N$ 네트워크라 한다.

	Diameter	Switch Size	Number of Swith	Max Congestion
Complete Binary Tree	$2(1+\log_2 N)$	$3\times 3$	$2N - 1$	$N$
2D array	$2N$	$2\times 2$	$N^2$	$2$
Butterfly	$2+\log_2 N$	$2\times 2$	$N(1+\log_2 N)$	$\sqrt{N}$ or $\sqrt{N/2}$
Benes Network	$1+2\log_2 N$	$2\times 2$	$2N \log_2 N$	$1$

• 지연^Latency은 입력에서 출력으로 패킷이 이동하는데 필요한 시간이다.
• 지름^Diameter은 네트워크에서 서로 가장 먼 거리의 입력과 출력 사이의 최단 경로의 길이이다.
• 퍼뮤테이션^Permutation은 $\pi\{0, 1, \cdots , N-1\} \rightarrow \{0, 1, \cdots, N-1 \}$꼴로 나타내어지는 함수로, 입력값에 대해 각각 다른 출력값을 매핑한다. $\pi(i) = \pi(j) \iff i=j$
• 입력 $i$에서 출력 $\pi(i)$로 이어지는 경로는 $P_{i, \pi(i)}$로 나타낸다.
• 경로 $P_{0,\pi(0)}, \cdots, P_{N-1, \pi(N-1)}$의 Congestion은 어떤 스위치를 지나가는 경로들의 수이다.

완전 이진 트리 네트워크

다음 그래프는 지름이 6, 스위치 크기가 $3\times 3$, 스위치가 7개이고 Max Congestion 4인 완전 이진 트리 네트워크이다.

In 1이 Out4, In2가 Out3, In3가 Out2, In4가 Out 1으로 이어지는 경로를 가질 때, 트리의 루트 노드에 해당하는 스위치의 Congestion은 4이다.

2D 배열 네트워크

2D 배열 네트워크는 다음과 같이 생긴 네트워크이다. 각 경로는 우측으로 이동하다가, 아래로 내려가는 경로이므로 최대 Congestion은 2가 된다. 퍼뮤테이션과 관계없이, 좌측 하단의 Congestion은 항상 2가 된다.

Butterfly 네트워크

버터플라이 네트워크는 레벨 0 스위치에서 레벨이 올라갈 때마다 세분화되는 경로를 갖는다.

각 행은 0부터 시작하는 2비트 값을 갖는데, 예를들어 위 그림에서 맨 위의 행은 000, 맨 아래 행은 111 주소를 갖는다.
각 스위치는 (레벨, 행)으로 나타내어질 수 있다. (0, 000)스위치는 (1, 000) 또는 (1, 100) 스위치로 패킷을 전송할 수 있다.

Benes 네트워크

Benes 네트워크는 마치 버터플라이 네트워크 2개를 이어놓은 듯이 생겼다. $N=2^a, a\geq 1$개의 입력을 갖는 Benes 네트워크의 Congestion은 1이다.
귀납적으로 증명해보자.

$N=2$인 Benes 네트워크를 생각해보자. 3개의 스위치 레벨이 있을 것이고, 직관적으로 Congestion은 1임을 알 수 있다.

그런데 $N>2$인 Benes 네트워크는 $N=2$인 Benes 네트워크의 확장이다. 위 그림에서, 레벨 0의 스위치들에 주목해보자. (0, 000)스위치는 입력 0에서 들어오는 신호를 다음 레벨의 상부(위에서부터 네개의 스위치)로 보낼지 하부로 보낼지를 결정한다. 즉, $N=2$인 네트워크와 같다.

그 다음 레벨에서도 다시 다음 레벨의 부네트워크 중 상부로 보낼지 하부로 보낼지를 결정하고... 이를 반복하는 형식으로 Benes 네트워크가 구성되어 있다. 그렇기 때문에, Permutation과 관계없이 Benes 네트워크의 Congestion은 항상 1이다.

제약 그래프^{Constraint Graph}

만약 두 개의 패킷이 각각 다른 부네트워크를 통과한다면, 서브네트워크 사이에는 간선이 존재하게 된다.
out0($\pi(6)=0$)을 향하는 패킷과 out4($\pi(2)=4$)를 향하는 패킷은 같은 네트워크를 통과할 수 없다.

제약 그래프의 간선들은 두 개의 집합(입력 간선 집합, 출력 간선 집합)으로 묶을 수 있다. 각 노드는 각 집합에서 하나의 간선을 인접간선으로 갖게 된다. 이때, 그래프는 2개의 색으로 칠할 수 있다.

증명) 모든 순환은 짝수 길이를 갖는다.
노드들은 출력 하나, 입력 하나로 총 2개의 간선을 가지기 때문에, 노드가 몇 개가 있던 짝수 길이를 갖게 된다.