Oblivious Routing

Oblivious routing은 네트워크 상태와 상관없이 패킷을 라우팅하는 방식으로, 구현과 분석이 간단하다. 네트워크 상태 정보를 추가하면 라우팅 성능을 개선할 수 있지만, 복잡도가 크게 증가하고 신중하지 않으면 오히려 성능이 저하될 수 있다.

Oblivious routing의 주요 트레이드오프는 locality와 load balance 사이의 균형이다. 각 패킷을 먼저 임의의 노드로 보내고 그 후 목적지로 전송하는 Valiant의 randomized routing algorithm(9.1절 참조)은 어떤 트래픽 패턴에서도 정확히 부하를 균등하게 분산시킨다. 하지만, 이 과정은 트래픽의 지역성(locality)을 완전히 파괴한다. 예를 들어, 가장 인접한 이웃 간의 통신조차 최악의 경우와 같은 성능을 보인다.

반면 minimal oblivious routing(9.2절 참조)은 지역성을 유지하며, 대부분의 트래픽 패턴에 대해 평균적인 네트워크 처리량을 향상시킨다. 하지만, torus 네트워크에서는 어떤 minimal 알고리즘도 Valiant 알고리즘의 최악 경우 처리량의 절반을 넘기 어렵다. 이에 따라 minimal 알고리즘과 Valiant 방식 사이의 절충안으로 load-balanced oblivious algorithm이 제안된다.

Oblivious routing 알고리즘은 채널 부하 함수가 선형이기 때문에 분석이 매우 용이하다. 이 선형성 덕분에 주어진 트래픽 패턴에서 채널 부하 γ를 계산하고, 이상적인 처리량을 산출하기 쉽다. 또한 9.4절에서 볼 수 있듯, 이 선형성은 해당 라우팅 알고리즘에 대한 최악의 트래픽 패턴을 계산하는 데에도 유리하다.

---

9.1 Valiant의 Randomized Routing Algorithm

거의 모든 토폴로지에서 어떤 트래픽 패턴이든 부하를 균등하게 분산시키기 위해 Valiant 알고리즘을 사용할 수 있다. 이 알고리즘에서는, s에서 d로 보내야 하는 패킷을 먼저 임의로 선택된 중간 노드 x로 전송한 후, x에서 d로 전송한다. 이 두 단계 각각에 어떤 라우팅 알고리즘이든 사용할 수 있으나, 일반적으로 균일 트래픽에 대해 부하를 잘 분산시키는 라우팅 알고리즘이 가장 적합하다. 예를 들어, torus나 mesh 네트워크에는 dimension-order routing, butterfly에는 destination-tag routing이 적합하다.

이렇게 하면 원래의 트래픽 패턴과 무관하게 각 단계가 균일한 랜덤 트래픽처럼 보이게 되므로, Valiant 알고리즘은 어떤 트래픽이든 간에 부하를 랜덤 트래픽의 두 배, 즉 네트워크 용량의 절반 수준으로 감소시킬 수 있다.

---

9.1.1 Torus 토폴로지에서의 Valiant 알고리즘

Valiant 알고리즘은 k-ary n-cube 네트워크에서 locality를 희생하는 대신 최악의 성능을 높인다. 두 단계 각각에서 각 패킷은 평균적으로 n개의 차원마다 k/4 거리만큼 이동하므로 총 hop 수는 nk/2이다. 이 경우, 각 링크는 평균적으로 γ = k/4의 부하를 가지며, 처리량은 4b/k이다.

이 처리량은 tornado 트래픽 패턴을 기준으로 거의 최적이다. tornado 트래픽에서는 각 패킷이 H = n(k/2−1) hop을 이동해야 하며, 어떤 라우팅 알고리즘이든 최소 채널 부하는 다음과 같다:

  γ ≥ HminN / C = n(k/2 − 1)N / 2nN = k/4 − 1/2

k가 증가함에 따라 이 이상적인 채널 부하는 Valiant 알고리즘이 유도하는 채널 부하에 가까워지므로, 결과적으로 Valiant 알고리즘은 점근적으로 최적이다.

반면 minimal 알고리즘은 tornado 트래픽에 대해 한 방향 채널(clockwise)에 k/2−1의 부하를, 반대 방향에는 0의 부하를 주므로, load balance가 나빠 처리량은 b/(k/2−1) ≤ 2b/k 수준에 불과하다. 따라서 minimal 라우팅은 최악의 경우 Valiant 알고리즘의 절반 수준밖에 도달하지 못한다.

이처럼 Valiant 알고리즘은 tornado 같은 최악의 트래픽 패턴에 대해 좋은 성능을 제공하지만, 지역성(locality)을 파괴하고 2단계 라우팅으로 인한 오버헤드를 수반한다. 예를 들어, 원래는 hop 1로 충분한 인접 노드 간의 트래픽도 두 단계 랜덤 라우팅으로 인해 hop 수가 nk/2까지 증가하며, 처리량이 저하된다.

---

9.1.2 Indirect Network에서의 Valiant 알고리즘

Valiant 알고리즘을 k-ary n-fly와 같은 indirect network에 적용하면, 특정 트래픽 패턴으로 인해 발생하는 병목 현상을 제거할 수 있다. 실제로 이 알고리즘의 두 단계 라우팅은 butterfly 네트워크를 논리적으로 두 번 겹쳐 구성한 Beneš 네트워크와 동일하다.

이 경우 Valiant 알고리즘은 Beneš 또는 Clos(k ≠ 2일 때) 네트워크에 대해, 각 패킷이 사용할 중간 스위치를 랜덤하게 선택하는 방식으로 작동한다. 이는 평균 부하를 잘 분산시키지만, 중간 노드 선택의 편차로 인해 순간적인 부하 불균형이 생길 수 있다. 이러한 부하의 순간적 변화는 충분히 깊은 버퍼를 통해 평균화되어야 하며, 그렇지 않으면 adaptive routing을 사용하여 통계적 부하 변화를 피하는 것이 좋다.

Oblivious routing을 indirect network에 적용할 경우, 네트워크를 folded 구조로 만들면 Valiant의 두 단계가 butterfly 네트워크의 노드를 서로 반대 방향으로 통과하게 되어 효율적이다. 이는 각 단계의 중간에서 소스와 목적지를 연결할 필요가 없어지고, 첫 번째 단계가 최종 목적지를 도달할 수 있는 지점에서 바로 종료할 수 있기 때문에 minimal oblivious routing 구현이 가능해진다.

 

9.2 Minimal Oblivious Routing

다음 그림 9.2는 **folded Clos network (fat tree)**에서 minimal oblivious routing의 예를 보여준다. 소스 노드 s = 1에서 목적지 노드 d = 6으로 가는 패킷은 s와 d의 가장 가까운 공통 조상 중 임의로 선택된 스위치 노드 (0XXX-A 또는 0XXX-B)를 거쳐 전달된다. 네트워크가 folded 되어 있기 때문에 모든 채널은 양방향이다.

s = 1에서 d = 6으로 가기 위해 0XXX-A 또는 0XXX-B 스위치 노드 중 하나를 선택할 수 있으며, 두 경로 모두 6개의 hop으로 minimal route가 된다.

이 경로는 점진적으로도 구성할 수 있다. 초기에는 패킷이 오른쪽으로 진행하며, 각 스위치에서 우상단 포트와 우하단 포트 사이에서 임의 선택을 하며 라우팅된다. d의 주소와 일치하는 스위치 노드에 도달하면 (예: d = 0110에 대해 처음 일치하는 0XXX 노드), 패킷은 방향을 반대로 바꿔 왼쪽으로 이동한다. 이때는 목적지 주소 중 X로 표시된 비트들만 사용하여 partial destination-tag routing으로 유일한 경로를 결정한다. 여기서는 d의 하위 3비트인 110이 사용되며, 이는 0XXX-A 또는 B에서 terminal d = 6까지 아래, 아래, 위의 경로를 의미한다.

공통 조상 노드를 임의로 선택하면, source/destination 쌍의 트래픽이 공통 조상과 그 경로 상의 스위치들 사이에 정확히 균등하게 분산된다. 이 minimal한 서브네트워크(오른쪽은 공통 조상 노드들로 경계)에 속하지 않는 라우팅은 불필요하게 bandwidth만 소비하며 load balance에 도움이 되지 않는다.

Thinking Machines CM-5(10.6절 참조)는 여기서 설명한 알고리즘과 거의 동일한 것을 사용하지만, 차이점은 첫 번째 라우팅 단계가 oblivious가 아니라 adaptive 라는 것이다.

---

9.2.2 Torus에서의 Minimal Oblivious Routing

Valiant 알고리즘의 minimal 버전은 k-ary n-cube 토폴로지에서 중간 노드 x를 s와 d 사이의 minimal quadrant에만 제한함으로써 구현할 수 있다. 이 minimal quadrant는 s와 d를 모서리 노드로 포함하는 가장 작은 n차원 서브네트워크다.

그림 9.3은 s = 00에서 d = 21로의 minimal oblivious routing 예시를 보여준다 (그림 9.1과 동일한 s, d, 6-ary 2-cube). 먼저 8.4.2절과 같이 상대 주소 Δ = (2, 1)을 계산한다. Δ의 크기는 minimal quadrant의 크기이며, 이 경우 x축으로 2 hop, y축으로 1 hop이다. 선호 방향 벡터 D = (+1, +1)이므로, minimal quadrant는 s = 00의 오른쪽 위에 위치한다.

이제 quadrant 내에서 중간 노드 x를 무작위로 선택하고, e-cube routing을 사용하여 s → x → d 순으로 라우팅한다. 이 예에서는 6개의 가능한 x가 있고, 각각 그림 9.3(b)의 회색 음영 노드로 표시된다. x까지의 경로는 굵은 실선, x 이후는 회색 실선으로 표시된다. 경우에 따라 source나 destination 자체가 x로 선택될 수도 있다.

가능한 중간 노드는 6개지만, 실질적인 경로는 3개뿐이다. 이는 y 방향 hop이 발생하는 위치에 따라 결정되며, 예를 들어 노드 02에서 y hop이 발생하는 경로는 4번 사용되고, 00에서 y hop이 발생하는 경로는 1번만 사용된다. 이로 인해 부하가 고르지 않게 분포되며, 차원을 이동하는 순서를 무작위로 선택함으로써 이 불균형을 어느 정도 개선할 수 있다.

그림 9.3(b)의 회색 점선은 y-우선 라우팅을 사용했을 때의 경로를 보여준다. x-우선과 y-우선을 무작위로 선택하면 minimal quadrant의 양끝 y 채널은 각각 12개 경로 중 5회 사용되고, 중간 채널은 2회만 사용되어 더 나은 분산이 된다.

Torus에서의 minimal oblivious routing은 지역성을 매우 잘 유지한다. 이웃 간 트래픽은 그대로 local로 유지되며, 랜덤 트래픽도 처리량이 절반으로 줄지 않는다. 하지만 이런 지역성은 최악의 성능과 트레이드오프 관계에 있다. 예를 들어 tornado 패턴은 심각한 load imbalance를 일으킨다.

---

9.3 Load-Balanced Oblivious Routing

Valiant 알고리즘(완전한 랜덤화)과 torus에서의 minimal oblivious routing 사이에서 타협하는 방법으로, 라우팅에 사용할 quadrant를 무작위로 선택하는 방식이 있다. 8.1절과 같이 거리 기반 가중치를 사용하면 tornado 트래픽에 대해 부하를 정확히 균등 분산할 수 있다.

각 차원 i에 대해 다음과 같이 방향을 선택한다:

• 짧은 방향 D′_i = D_i : 확률은 (k − |Δ_i|) / k
• 긴 방향 D′_i = −D_i : 확률은 |Δ_i| / k

이 방향 벡터 D′가 선택되면, minimal oblivious routing과 같이 해당 quadrant 내에서 중간 노드를 무작위로 선택하고, s → x → d로 라우팅한다. 각 단계의 dimension order도 무작위로 선택되며, 두 단계 모두 D′ 방향으로 진행된다.

이러한 load-balanced oblivious routing은 지역성과 최악 성능 간의 절충안이다. 지역 트래픽에는 Valiant보다 성능이 좋으며, 짧은 경로를 더 자주 사용한다. 하지만 minimal routing보다는 성능이 떨어지며, 일부 패킷은 비최소 quadrant를 통해 우회된다. tornado 트래픽에는 성능이 우수하지만, 최악 처리량은 Valiant 알고리즘보다 훨씬 낮다.

---

9.4 Oblivious Routing의 분석

Oblivious routing 알고리즘은 네트워크 상태와 관계없이 경로를 결정하기 때문에, 어떤 노드 쌍 s → d에 대해 단위 부하 λ_sd = 1이 주어졌을 때 **채널 c에 유도되는 부하 γ_c(sd)**는 다른 노드 쌍과 무관하게 고정된다.

이 특성 덕분에, 주어진 라우팅 알고리즘과 트래픽 패턴에 대해 각 채널 c의 부하 γ_c는 아래와 같이 쉽게 계산할 수 있다:

  γ_c = ∑_{i,j} λ_ij × γ_c(ij)  (식 9.1)

 

예를 들어, 그림 9.3에서 s₁ = 00에서 d₁ = 21로 x-우선 라우팅을 두 단계 모두 사용하면, 채널 (10, 20)은 6개의 가능한 경로 중 2개에서 사용되므로 γ(10,20)(00,21) = 1/3이 된다. 또 다른 예로, s₂ = 10에서 d₂ = 31로 라우팅할 경우 채널 (10, 20)은 6개의 경로 중 4개에서 사용되므로 γ(10,20)(10,31) = 2/3이다.

이제 두 개의 비영(非零) 항만을 갖는 트래픽 행렬을 생각해보자. λ(00,21) = λ(10,31) = 1인 경우, 다음과 같이 γ(10,20)을 계산할 수 있다:

  γ(10,20) = γ(10,20)(00,21) + γ(10,20)(10,31) = 1/3 + 2/3 = 1

Oblivious routing에서는 채널 부하가 선형이다. 특정 트래픽 패턴에 대한 채널 부하는 트래픽 행렬의 각 항에 따른 부하의 중첩(superposition)으로 계산된다. 이 선형성 덕분에 가장 큰 채널 부하를 유도하는 트래픽 행렬을 찾음으로써 **최악의 트래픽 패턴(worst-case traffic pattern)**을 계산할 수 있다.

라우팅 알고리즘이 주어진 트래픽 패턴에서 달성하는 throughput을 계산하기 위해, 트래픽 행렬을 정규화하여 각 행과 열의 합이 1이 되도록 한 후, 스케일 팩터 α를 구한다. α를 곱한 트래픽 행렬 αΛ는 critical channel을 정확히 포화(saturate) 시킨다. 원래의 트래픽 행렬 Λ는 최대 채널 부하 γ_max(Λ)를 유도하는데, 이 값이 채널의 bandwidth b보다 클 수 있다. 따라서 throughput 및 스케일 팩터는 다음과 같이 주어진다:

  α = b / γ_max(Λ)

선형성에 의해 이 α는 다음을 만족시킨다:

  γ_max(αΛ) = α × γ_max(Λ) = b

최악 트래픽 패턴을 찾기 위해, 모든 최악의 트래픽은 permutation 형태를 가진다는 사실을 사용할 수 있다. 이는 모든 정규화된 트래픽 행렬은 permutation의 가중합으로 표현될 수 있기 때문이다:

  Λ = ∑ₖ wₖ Πₖ  단, ∑ₖ wₖ = 1  (식 9.2)

이 중 하나의 permutation, say Π_max는 다음 조건을 만족한다:

  ∀k, γ_max(Π_max) ≥ γ_max(Πₖ)

따라서

  γ_max(Λ) = ∑ₖ wₖ γ_max(Πₖ) ≤ γ_max(Π_max)  (식 9.3)

즉, permutation 중 하나가 최악의 트래픽 패턴이 될 수 있다.

특정 채널 c에서 최대 부하를 유도하는 permutation을 찾기 위해, 그림 9.4와 같이 bipartite graph를 구성한다. 왼쪽에는 모든 source 노드에 대해 정점이, 오른쪽에는 모든 destination 노드에 대해 정점이 존재한다. source s에서 destination d로의 각 간선은 γ_c(s,d)로 라벨링된다. permutation Π는 matching에 해당하며, 이 matching의 가중치 합이 채널 c에 대한 부하 γ_c(Π)가 된다. 따라서 이 그래프에서 최대 가중치 matching을 찾으면 해당 채널에서 최대 부하를 유도하는 permutation을 얻을 수 있다. 이 절차를 모든 채널에 반복하여 전체 네트워크에서 최악의 permutation을 구한다.

이 방법을 통해 얻은 최악 트래픽 패턴은, 3.2절에서 설명한 일반적인 트래픽 패턴보다 훨씬 낮은 throughput을 보이는 경우가 많다. 표 9.1은 8-ary 2-cube에서 네 가지 라우팅 알고리즘이 여섯 가지 트래픽 패턴에 대해 보여주는 throughput (capacity 대비 비율)을 보여준다. 각 알고리즘마다 worst-case 패턴이 다르며, minimal과 load-balanced oblivious routing은 특히 표준 패턴보다 낮은 worst-case throughput을 보인다.

---

표 9.1: 8-ary 2-cube에서 6가지 트래픽 패턴에 대한 네 가지 라우팅 알고리즘의 throughput (capacity 기준)

트래픽 패턴e-cubeValiantMinimalLoad-Balanced

Nearest neighbor	4.00	0.50	4.00	2.33
Uniform	1.00	0.50	1.00	0.76
Bit complement	0.50	0.50	0.40	0.42
Transpose	0.25	0.50	0.54	0.57
Tornado	0.33	0.50	0.33	0.53
Worst-case	0.25	0.50	0.21	0.31

 

이전에는 특정한 의심 트래픽 패턴만 시뮬레이션하여 worst-case를 판단했는데, 이는 매우 오해를 불러일으킬 수 있다. 하지만 adaptive routing 알고리즘은 채널 부하 함수가 선형이 아니므로 위 방법을 사용할 수 없다. 따라서 adaptive routing은 특정 트래픽 패턴에 대해 직접 시뮬레이션하여 평가하는 수밖에 없다.

---

9.5 Avici Terabit Switch Router (TSR)에서의 Oblivious Routing 사례 연구

**Avici Terabit Switch Router (TSR)**는 input line card와 output line card를 연결하는 3차원 torus interconnection network를 switch fabric으로 사용하는 확장형 인터넷 라우터이다. 각 cabinet에는 2 × 4 × 5 folded torus 네트워크로 구성된 40개의 5-Gbit/s line card가 들어있다. 최대 8개의 cabinet을 결합하여 8 × 8 × 5 토폴로지로 구성할 수 있고, 총 320개의 노드를 가지며 최대 1.6 Tbit/s의 aggregate bandwidth를 제공한다.

각 line card는 5 Gbit/s (full duplex)의 인터페이스 bandwidth를 제공하며, 주로 OC-48 또는 OC-192 POS 링크에 연결된다.

그림 9.6에 보이는 OC-48 POS 인터페이스용 line card 하단에는 heatsink가 부착된 6개의 칩이 있으며, 이것이 bit-sliced torus router를 구성한다. 이 router는 총 24-bit 폭으로 구성되며, 각 칩은 4-bit를 담당한다. 네트워크 링크는 총 28-bit (24 data + 3 control + 1 clock)이며, 400 MHz에서 동작하여 9.6 Gbit/s (1.2 GByte/s)의 속도를 제공한다. 각 router는 6방향 각각에 대해 input/output 1개씩, 총 12개의 링크와 연결된다.

Avici TSR은 여러 측면에서 주목할 만하다. 15.7절에서는 **output 별로 virtual network를 할당하여 서비스 품질 보장(QoS)**을 제공하는 방법을 설명할 것이다. 이 절에서는 TSR이 내부 네트워크 링크의 부하를 균형 있게 분산시키기 위해 사용하는 oblivious routing algorithm에 초점을 맞춘다.

TSR 네트워크는 부분적으로 구성된 라우터이거나 line card가 실패하거나 제거된 경우처럼 irregular topology에서도 non-stop routing을 제공해야 한다. 이를 위해 TSR은 source routing(11.1.1절)을 사용한다. 송신 노드는 목적지까지의 정확한 경로를 라우팅 방향 문자열로 구성한다. 예: +x, −y, +x, +z, −y, −x 와 같은 문자열에서 각 방향은 한 hop을 의미한다. 소프트웨어 프로세스가 모든 s → d 경로를 사전 계산하고 테이블에 저장하며, 패킷은 출발지에서 이 테이블을 조회하여 라우팅 문자열을 패킷 헤더에 추가한다. 이 문자열은 각 hop마다 다음 이동 방향을 결정하는 데 사용된다.

TSR에는 input SONET 링크에 backpressure가 없기 때문에, 내부 fabric을 과부하 없이 모든 트래픽 패턴에 대해 처리할 수 있는 라우팅 방식이 필요하다.

 

![그림 9.6 설명]
단일 OC-48 (2.488 Gbit/s) SONET line card는 두 부분으로 나뉜다. 위쪽 서브카드는 인터페이스에 특화되어 있으며, 아래쪽 메인카드는 인터페이스에 독립적이다. 보드 하단에 heatsink가 부착된 6개의 칩이 있으며, 각각 4-bit씩 나누어 구성된 24-bit 폭의 torus router를 구성한다.

TSR은 적대적인 트래픽(adversarial traffic)이 존재하는 경우에도 내부 채널이 과부하되지 않도록 oblivious routing을 사용하여 네트워크 채널의 부하를 균등하게 분산시킨다. 소스 line card s에서 목적지 line card d로 패킷이 전송될 때, d에 대한 라우팅 테이블에 저장된 24개의 경로 중 하나를 무작위로 선택한다. 동일한 flow에 속한 패킷들은 동일한 경로를 선택하도록 flow identifier를 기반으로 무작위 선택이 이루어지므로 순서가 유지된다.

d에 대한 라우팅 테이블에는 s에서 d로 향하는 minimal quadrant 내의 3가지 초기 방향 각각에 대해 8개씩, 총 24개의 경로가 포함된다. 예를 들어, s = (0,0,0)이고 d = (3,2,4)인 경우, 8 × 8 × 5 시스템에서 minimal 방향은 +x, +y, −z이다. 따라서 각각의 방향에 대해 8개의 경로가 테이블에 존재한다.

라우팅 과정을 그림 9.7이 보여준다. 패킷이 line card s로 들어오면 route lookup 및 분류 단계에 입력된다. 이 단계에서 패킷의 목적지 d를 결정하고 flow identifier f를 계산한다. 동일한 flow에 속한 모든 패킷은 동일한 flow ID를 가진다. flow ID는 해시되어 r = hash(f) ∈ [0, 23]의 route selector를 생성한다. 그런 다음, 라우팅 테이블은 인덱스 24d + r로 조회되어 s에서 d로 가는 24개 경로 중 하나를 선택한다. 이 경로는 패킷 헤더에 추가되어 경로 선택에 사용된다.

참고: IP에서는 flow란 source address, source port, destination address, destination port가 동일한 패킷들의 집합이다.

---

그림 9.7 설명

각 source 노드 s에 있는 TSR 라우팅 테이블은 각 목적지 d에 대해 24개의 경로를 저장한다. 이는 3개의 초기 방향 각각에 대해 8개의 경로로 구성된다. 동일한 flow 내에서 패킷의 순서를 유지하기 위해, 각 패킷은 해당 flow의 identifier를 해시하여 사용할 경로를 선택한다.

---

TSR에서 table-driven oblivious routing으로 부하를 균등하게 분산시키기 위해서는 좋은 테이블을 구성하는 것이 핵심이다. 각 (s, d) 쌍에 대해 저장된 경로 수 NR이 적다면, 경로를 신중히 선택해야 한다.

하나의 접근 방식은 경로를 하나씩 생성하며 라우팅 테이블을 점진적으로 구성하는 것이다. 경로가 생성될 때마다 해당 경로가 사용하는 채널 각각에 1단위 부하가 추가된다. 다음 경로를 생성할 때는 사용 가능한 minimal 경로들 중 현재 채널 부하의 총합이 가장 낮은 경로를 선택한다. 이러한 경로 생성을 9.3, 9.4번 연습문제에서 다룬다.

---

9.6 참고문헌 노트 (Bibliographic Notes)

• Randomized routing은 Valiant [187]가 처음 제안하였다.
• 9.2.2절에서 설명한 minimal oblivious routing은 Nesson과 Johnsson [135]의 연구에 기반한다.
• 9.3절의 load-balanced oblivious routing은 Singh 외 [168]에 의해 제안되었다.
• Towles와 Dally는 oblivious routing의 최악 경우 분석 기법을 기술하였다 [185].

---

9.7 연습문제 (Exercises)

9.1 Uniform traffic에서의 load-balanced routing:
k-ary n-cube에서 uniform traffic 하의 load-balanced routing 알고리즘(9.3절 참고)에 의해 유도되는 채널 부하의 일반식을 구하라.

9.2 Dimension-order routing의 최악 성능 최적성:
2차원 torus에서 minimal routing 알고리즘으로서 dimension-order routing이 **최악 경우 throughput에 대해 최적(상수 항 이내)**임을 설명하라. 이 주장은 n > 2의 경우에도 성립하는가?

9.3 Avici TSR에서의 경로 생성:
任意의 토폴로지 네트워크에 대해 Avici TSR과 유사한 source routing table을 작성하는 프로그램을 작성하라. 9.5절 마지막에서 설명한 방법을 사용하여 NR = 8인 경우 각 (s, d) 쌍에 대해 테이블을 생성하라. 여러 개의 무작위 permutation을 생성하여 각 permutation에서 가장 큰 링크 부하를 측정해보라. NR 값을 변화시켜 (s, d) 쌍당 경로 수에 따른 부하 불균형 변화를 분석하라.

9.4 Avici TSR에서의 반복 경로 생성:
9.3번 문제와 동일한 분석을 하되, 이번에는 반복적인 경로 생성 방식을 적용하라. 초기 경로 세트를 구한 후, 그 경로들이 유도하는 채널 부하를 기반으로 두 번째 경로 세트를 생성한다. 이 과정을 NI회 반복한다. 이 반복 알고리즘의 성능이 단일 패스 알고리즘보다 어떤지 비교하라.

9.5 Fat tree에서의 순간 부하 불균형:
1,024-node folded 4-ary 5-fly (fat tree)에서 Valiant 알고리즘을 batch mode로 사용한다고 가정하자. 각 배치마다 source terminal은 중간 목적지 terminal을 무작위로 선택한다. 중간 목적지 x를 선택한 source terminal 수를 f(x)라 할 때, 모든 x에 대해 max(f(x))의 기대값은 얼마인가?