Zeah Engineering Factory

라우팅 메커니즘은 deterministic, oblivious, adaptive 라우팅 알고리즘을 실제로 구현하는 방식을 뜻한다. 많은 라우터는 라우팅 알고리즘을 구현하기 위해 source 또는 각 홉(hop)에서 routing table을 사용한다. 목적지마다 단일 항목만 있는 테이블은 deterministic routing에만 사용할 수 있지만, 목적지마다 복수 항목을 제공하면 oblivious와 adaptive routing도 구현할 수 있다. table 기반이 아닌 대안으로는 algorithmic routing이 있으며, 이는 특수한 하드웨어가 런타임에 패킷의 경로나 다음 홉을 계산하는 방식이다. 그러나 algorithmic routing은 일반적으로 단순한 라우팅 알고리즘과 정규 토폴로지에만 제한된다.

11.1 테이블 기반 라우팅

8.3절의 Relation 8.1~8.3을 다시 떠올려 보자. 이는 모든 라우팅 알고리즘을 다음과 같이 정의한다.

이 세 가지 형태의 라우팅 관계는 모두 테이블을 통해 구현할 수 있다. 각 입력 쌍에 대한 관계 값이 테이블에 저장되며, 입력으로 테이블을 인덱싱한다. 예를 들어 첫 번째 형태에서는 각 노드 쌍마다 가능한 path 집합을 테이블에 저장하고, source와 destination 노드로 인덱싱한다. 각 노드에는 해당 노드가 source 또는 현재 노드일 때 필요한 테이블 일부만 저장하면 된다. 예를 들어 노드 x에서는 source 노드(또는 현재 노드) x에 해당하는 테이블 부분만 저장하면 된다.

테이블 기반 라우팅의 주요 장점은 일반성이다. 용량 제약만 없다면, 라우팅 테이블은 어떤 토폴로지에서든 어떤 라우팅 관계든 지원할 수 있다. 테이블 기반 라우팅을 사용하는 라우팅 칩은 테이블의 내용을 재프로그래밍하는 것만으로 다양한 토폴로지에서 사용할 수 있다.

이 절의 나머지에서는 테이블 기반 라우팅의 양 극단을 살펴본다. source-table routing에서는 전체 라우팅 경로를 source에서 한 번에 찾아 구현하고, node-table routing에서는 경로를 hop 단위로 점진적으로 찾아간다. 이 둘 사이에는 다양한 중간 형태가 존재하며, 각 테이블 조회는 경로의 일부분을 반환한다.

11.1.1 소스 라우팅 (Source Routing)

source routing은 패킷에 대한 모든 라우팅 결정을 source 터미널에서 미리 계산된 경로를 테이블 조회를 통해 완전히 수행하는 방식이다. 각 source 노드는 목적지당 하나 이상의 경로를 갖는 라우팅 테이블을 가진다. 패킷을 라우팅할 때, 목적지 정보를 이용해 해당 경로나 경로 집합을 테이블에서 조회한다. 만약 복수의 경로가 반환된다면, 추가적인 상태 정보를 통해 oblivious 또는 adaptive 방식으로 하나의 경로를 선택한다. 선택된 경로는 패킷에 붙어서 네트워크를 따라 전달되며, 중간에서의 추가 계산 없이 빠르게 패킷을 전달할 수 있다.

이 방식은 속도, 단순성, 확장성 측면에서 매우 유리하므로 deterministic 및 oblivious routing에서 널리 사용된다. 하지만 source table routing은 중간 홉의 네트워크 상태 정보를 활용할 수 없기 때문에 adaptive routing 구현에는 잘 사용되지 않는다.

다음 표는 Figure 11.1의 4 × 2 torus 네트워크에서 노드 00의 source routing table을 보여준다. 이 테이블은 네트워크 내 모든 목적지에 대해 두 개의 경로를 제공한다. 각 경로는 source 노드에서 목적지 노드까지의 경로를 포트 선택자의 문자열로 나타낸다. 이 포트 선택자는 NEWSX의 다섯 개 기호로 이루어진 알파벳에서 3비트 이진수로 인코딩되어 있다.

표 11.1: Figure 11.1의 4 × 2 torus 네트워크에서 노드 00의 source routing table

패킷이 node 00에서 node 21로 라우팅되는 예를 보자. Figure 11.1의 네트워크에서, source node는 Table 11.1을 목적지 21로 인덱싱해 미리 계산된 두 경로 NEEX와 WWNX를 찾는다. 이 중 임의로 첫 번째 경로 NEEX를 선택한다. 이 라우팅 문자열은 네트워크를 따라 패킷을 전달하기 위해 한 글자씩 해석된다. 첫 번째 문자 N은 node 00의 north 포트를 선택하고 제거되며, 나머지 문자열 EEX는 node 01로 전달된다. node 01에서는 east 포트를 선택하고 EX를 node 11로 보낸다. 다시 east 포트를 선택하고 마지막 문자 X는 node 21로 간다. X는 router의 exit 포트를 지정하며, 패킷을 node 21의 input queue로 보낸다.

source routing은 이 장의 다른 방법들에 비해 여러 가지 장점이 있다. 가장 큰 장점은 속도이다. source에서 처음 테이블을 조회하고 경로를 선택한 이후에는 라우팅에 소요되는 시간이 없다. 각 패킷이 라우터에 도착할 때 즉시 출력 포트를 선택할 수 있고, 계산이나 메모리 접근이 필요 없다. hop당 지연 중 라우팅 지연은 0이다. 또한 router 설계가 단순해진다. 각 router에 라우팅 로직이나 테이블이 필요 없다.

source routing은 토폴로지에 독립적이다. router 포트 수, source 테이블 크기, 경로의 최대 길이만 만족한다면 임의의 strongly connected 토폴지에서 라우팅이 가능하다. 예를 들어 Figure 11.1의 네트워크처럼 포트가 4개인 router들을 이용해 degree-4 네트워크를 구성하면 source routing을 통해 패킷을 전달할 수 있다.

source routing을 사용하는 router는 네트워크 크기에 구애받지 않고 사용 가능하다. 네트워크 크기, 테이블 크기, 경로 길이에 대한 제약은 source에만 있기 때문에, 큰 네트워크를 지원하는 데 드는 비용은 terminal에만 국한되며, 작은 네트워크에 그 비용이 전가되지 않는다.

임의 길이의 경로를 처리하려면 router는 임의 길이의 경로를 지원해야 한다. 경로는 exit 포트 선택자 X로 끝나는 임의 길이 문자열이지만, 이를 고정 길이의 routing phit과 flit에 적절히 인코딩해야 한다.

Figure 11.2는 임의 길이 source route를 인코딩하는 방법을 보여준다. 이 예에서는 router가 16-bit phit, 32-bit flit, 최대 13개의 포트를 지원한다고 가정한다. 각 16-bit phit에는 4개의 4-bit 포트 선택자가 들어 있고, 각 flit에는 8개의 선택자가 들어간다.

packing을 용이하게 하기 위해 P와 F라는 두 개의 새로운 포트 선택 기호를 도입한다. P는 phit 연속, F는 flit 연속을 나타낸다.

Figure 11.2(a)는 13-hop 경로 NENNWNNENNWNN이 두 개의 flit에 인코딩된 예이다. 각 phit에서는 포트 선택자를 오른쪽에서 왼쪽 순서로 해석한다. 처음에는 연속 기호가 없지만, 이후 hop이 진행되면서 순차적으로 P와 F가 삽입된다. Figure 11.2(b)에서는 첫 hop 이후 phit의 가장 왼쪽에 P가 삽입된다. Figure 11.2(c)에서는 네 번째 hop 후에 P가 오른쪽 끝에 나타나고, 이는 라우터에 해당 phit을 제거하고 flit 끝에 F를 붙이라는 명령이 된다. Figure 11.2(e)에서는 flit 연속 기호 F를 만나 flit을 제거하고 다음 flit을 처리하게 한다. 이와 같은 방식으로 exit 포트 선택자 X를 만날 때까지 처리된다. 이러한 방식으로 여러 phit과 flit에 걸쳐 임의 길이의 경로를 인코딩할 수 있다.

이 연속 선택자 덕분에 router는 단일 phit만 처리하면 되며, 각 단계의 leading phit 입력만으로 출력을 결정할 수 있으므로 다음 phit이 도착하기 전에 출력을 생성하고 전송할 수 있다.

source terminal의 라우팅 테이블은 임의 길이의 문자열을 효율적으로 저장할 수 있도록 설계되어야 한다. Figure 11.3처럼 단일 간접화(indirection) 레벨을 사용해 이를 구현할 수 있다. 테이블을 목적지로 인덱싱하면 하나 이상의 포인터가 반환되며, 각 포인터는 가변 길이의 경로 문자열을 가리킨다. 모든 경로는 X로 끝나며, 한 경로가 다른 경로의 접미사인 경우, 첫 경로의 문자열 내부를 가리키는 포인터로 나타낼 수 있어 저장 공간이 절약된다. 이러한 방식은 경로를 조회할 때 추가 메모리 접근이 필요하지만, 가장 짧은 경로를 제외한 경우에는 경로를 고정 길이로 만드는 데 드는 낭비를 줄이므로 전체적으로 더 효율적이다. 절충안으로는 경로의 처음 몇 hop을 테이블에 직접 저장하고 나머지 경로에 대한 포인터를 포함하는 방식이 있다.

source routing 테이블은 각 목적지에 대해 여러 개의 경로를 저장할 수 있다. Table 11.1에서도 각 목적지에 두 개의 경로를 저장하고 있다. 이처럼 한 쌍의 source-destination 사이에 복수 경로를 제공하는 것은 여러 이점을 갖는다.

• Fault tolerance: 일부 경로가 edge-disjoint라면, 노드 간 연결 채널이 하나 이상 고장 나더라도 경로가 유지된다.
• Load balance: 여러 경로를 통해 트래픽이 분산되므로 다양한 트래픽 패턴에서도 네트워크의 부하가 고르게 유지된다.
• Distribution: 테이블 인덱싱에 사용되는 목적지가 특정 서버가 아닌 서비스 같은 논리적 목적지인 경우, 여러 경로는 여러 서버로 연결될 수 있다. 이 경우 라우팅 테이블은 특정 서비스를 제공하는 서버 간에 트래픽을 분산하는 역할을 한다.

여러 개의 경로가 있을 때는 각 패킷이 어떤 경로를 따라야 할지 결정해야 한다. 패킷 순서를 보장할 필요가 없다면, 의사 난수 생성기를 사용해 트래픽을 무작위로 분산시키는 방식이 효과적이다. 경로와 테이블 항목 수가 동일하고 난수가 균등하게 분포한다면, 모든 경로는 동일한 확률로 선택된다. 일반적으로는 경로 수가 목적지마다 다르고, 테이블에 고정 개수의 항목만 존재하므로 1:1 매핑은 어렵다. 대신 테이블 항목 수를 충분히 늘리면 부하 균형을 근사할 수 있다. 예를 들어 M개의 경로에 대해 N개의 테이블 항목이 있다면, 각 경로는 k 또는 k+1개의 항목에 저장되며, 두 경로 간의 부하 차이는 1/N으로 제한된다.

또 다른 방법은 각 경로에 확률값을 이진 필드로 저장하는 것이다. 로직 회로는 이 확률과 난수를 결합해 경로를 선택할 수 있다. 이 방식은 임의의 확률 분포를 표현할 수 있고, 테이블 항목을 중복 저장하는 것보다 훨씬 더 저장 공간 효율적이다.

경우에 따라 네트워크를 통해 전송되는 특정 패킷들의 순서를 보장해야 할 수도 있다. 프로토콜이 재정렬 기능이 없거나, 예를 들어 cache coherence protocol처럼 메시지 순서가 정확성에 영향을 미치는 경우, 순서를 유지해야 한다. 이러한 패킷 집합은 flow라고 하며, 각 패킷은 flow 식별자(flow identifier)로 라벨링된다. 이는 프로토콜과 패킷 종류를 식별하는 header 필드 조합일 수 있다. flow 식별자를 해싱해서 경로 선택자 생성에 사용하면, 해당 flow의 모든 패킷이 동일한 경로를 따라가므로 (FIFO queueing을 가정할 때) 순서가 유지된다. 그러나 flow 분포가 고르지 않으면 경로 선택 확률이 왜곡될 수 있다. Avici TSR의 randomized table-based routing에서 flow 순서를 유지하는 방식은 9.5절에 설명되어 있다.

11.1.2 Node-Table Routing

table-based routing은 라우팅 테이블을 terminal이 아닌 라우팅 노드에 저장하는 방식으로도 구현할 수 있다. node-table routing은 각 단계에서 사용할 수 있는 여러 다음 홉 중 하나를 네트워크 상태에 따라 선택할 수 있으므로 adaptive routing에 더 적합하다. node table을 사용하면 각 노드는 목적지까지 전체 경로가 아니라 다음 홉 정보만 저장하면 되므로 라우팅 테이블 전체 저장 공간을 크게 줄일 수 있다. 하지만 저장 공간이 줄어드는 대신, 성능 저하와 라우팅 제한이라는 단점이 있다. 이 구조에서는 패킷이 라우터에 도착할 때마다 테이블 조회를 수행해야 출력 포트를 결정할 수 있다.

패킷이 라우터에 도착했을 때 목적지 외에도 도착한 input 포트를 기준으로 테이블 항목을 선택하는 방식도 가능하다. source routing과 달리 경로의 각 단계마다 테이블을 조회해야 하므로, 라우터를 통과하는 패킷의 지연 시간이 상당히 증가한다. 또한, 모든 노드가 가장 큰 네트워크에서 모든 목적지에 대한 다음 홉 정보를 저장할 수 있어야 하므로 확장성도 희생된다. 더불어, 이 방식에서는 서로 다른 source 노드 x와 y에서 같은 목적지 z로 향하는 패킷이 동일한 중간 노드 w의 같은 채널로 들어온 경우, w → z 구간에서 서로 다른 경로를 주는 것이 불가능하다. source routing에서는 이게 쉽게 가능하다.

Table 11.2는 Figure 11.1 네트워크에 대한 node routing table의 예시를 보여준다. 각 노드에 대한 테이블이 노드 번호 아래 두 개의 열로 나타나 있으며, 각 목적지마다 한 행이 있다. 각 노드와 목적지 쌍에 대해 두 개의 가능한 다음 홉이 주어져 있어, 일정 수준의 adaptive routing이 가능하다. 예를 들어, node 01에서 node 13으로 향하는 패킷은 N 또는 E 방향 중 하나를 선택할 수 있다. 일부 다음 홉은 실제로는 목적지로부터 멀어지는 방향이며, 이러한 misroute는 굵게 표시되어 있다.

node-table routing에서는 livelock 문제가 발생할 수 있다. 테이블 항목이 패킷을 무한 루프로 보내는 방향으로 설정될 수 있기 때문이다. 예를 들어, node 00에서 node 11로 가는 항목이 N 방향이고, node 10에서 node 11로 가는 항목이 S 방향이라면, 패킷은 00 ↔ 10 사이를 무한히 순환하게 된다. 반면, source routing은 고정된 길이의 경로를 가지므로 반드시 도착지에 도달하게 되며 이런 문제가 없다. node-table routing에서도 테이블을 신중하게 구성하면 이러한 문제를 피할 수 있다.

node-table routing은 로컬에서 경로를 조정할 수 있다는 장점이 있다. 특정 output 링크가 혼잡하거나 고장났을 때, 다른 노드와 협의 없이도 노드 스스로 경로를 변경할 수 있다. Table 11.2처럼 각 목적지에 대해 여러 엔트리가 있으면, 혼잡도나 사용 가능성을 기준으로 출력 포트 선택에 bias를 줄 수 있다. 예를 들어, Table 11.2에서 node 00의 N 포트가 혼잡하면, 목적지 10인 패킷은 다음 홉으로 N이 아닌 S를 선택할 수 있다.

매우 큰 네트워크에서는 저장 공간을 줄이기 위해 node-table을 계층적(hierarchical)으로 구성할 수 있다. 예를 들어, 가까운 노드는 개별적으로 다음 홉을 저장하고, 멀리 있는 노드는 그룹으로 묶어서 저장하는 식이다. 이런 방식의 한 예로는 CAM(Content Addressable Memory)을 라우팅 테이블로 사용하는 것이다. Table 11.3은 8-ary 3-cube 네트워크에서 node 4448의 CAM 기반 라우팅 테이블 예시이다. 각 행은 목적지 그룹과 해당 그룹에 대한 다음 홉으로 구성되며, 9비트 주소(x, y, z 각 3비트)로 표현된 목적지 그룹은 일부 비트에 “X”(don’t care)를 포함할 수 있다. “X”를 허용하는 CAM은 ternary CAM(TCAM)이라 부른다.

X의 수에 따라 이 주소는 단일 노드, 1D, 2D, 3D로 연속된 노드 그룹을 인코딩할 수 있다. 예를 들어 첫 번째 행은 node 444 자체를 나타내며, 다음 행은 서쪽에 있는 1D 노드 배열(440443)을 나타낸다. 마지막 항목은 2D 노드 배열(500577)을 나타내며, 나머지 항목은 3D 노드 그룹을 표현한다.

CAM 기반 라우팅 테이블은 마치 출력 포트를 선택하는 논리함수를 계산하는 프로그램 가능 로직 배열(PLA)처럼 작동한다. 특정 포트를 선택하는 각 항목은 논리식에서 해당 포트를 위한 항(term) 하나로 작용한다. 예를 들어, W 포트를 선택하는 논리식은 두 번째와 여덟 번째 행에 대응하는 두 항(term)으로 구성된다. 이런 방식으로 하나의 포트에 대한 모든 항목을 최소한의 합-곱식으로 압축하면 node routing table을 줄일 수 있다.

node-table routing은 대부분의 광역 패킷 라우터에서 사용하는 방식이다. 이는 네트워크 연결성과 라우팅을 분산 알고리즘으로 계산하는 데 적합하기 때문이다. 하지만 interconnection network처럼 노드가 가까이 위치한 시스템에서는, delay가 증가하므로 adaptivity가 필요한 경우가 아니면 source routing이 보통 더 우수하다.

source routing과 node-table routing은 table-based routing의 두 극단을 나타낸다. node-table routing은 다음 홉만 저장하고, source routing은 전체 경로를 저장한다. 물론 이 두 극단 사이에는 다양한 중간 지점이 있을 수 있으며, 테이블에 다음 M개 (M > 1)의 홉을 저장하는 방식도 있다. 이 방식은 지역적인 adaptivity와 중간 수준의 hop latency를 제공하지만, 실제로는 거의 사용되지 않는다. hybrid 방식에서는 노드마다 다른 동작을 해야 하므로 대칭성이 없기 때문이다.

11.2 알고리즘 기반 라우팅 (Algorithmic Routing)

라우팅 관계를 테이블에 저장하는 대신, 알고리즘을 이용해 계산할 수 있다. 속도를 위해 이 알고리즘은 보통 조합 논리 회로로 구현된다. 이런 알고리즘 기반 라우팅은 테이블 기반 라우팅의 일반성은 희생하지만, 특정 토폴로지와 그에 맞는 라우팅 전략에 최적화될 수 있다. 대신, 면적과 속도 측면에서 더 효율적일 수 있다.

가장 단순한 예는 목적지 주소의 특정 자릿수를 추출하는 digit selector이며, 이는 destination-tag routing에서 사용된다. 예를 들어 Section 2.5의 간단한 라우터에서는 이러한 회로가 사용된다.

2D torus 라우팅용 알고리즘 회로는 Figure 11.4에 나와 있다. 이 회로는 sx, sy라는 각 차원에 대한 부호 비트와 목적지까지 몇 hop 남았는지를 나타내는 상대 좌표 x, y를 입력으로 받는다. 상대 주소는 zero checker에 전달되어 xdone, ydone 신호를 생성한다. 이 신호들은 각 차원에서 라우팅이 완료되었는지를 나타낸다. 부호 비트와 done 신호는 다섯 개의 AND 게이트에 입력되며, 목적지로 가까워지는 생산적인 방향(productive direction)을 결정한다. 예를 들어, xdone=0이고 sx=0이면 +x 방향으로 진행 중이며, 이는 생산적인 방향이 된다.

이처럼 생성된 5비트 생산적 방향 벡터는 route selection 블록에 전달되어 하나의 방향을 선택하고, 그 선택된 방향 벡터가 출력된다.

route selection 블록은 이 회로가 수행하는 라우팅 방식의 종류를 결정한다. productive direction 벡터에서 하나를 무작위로 선택하면 minimal oblivious router가 되며, 출력 큐의 길이를 기준으로 선택하면 minimal adaptive router가 된다. 모든 생산적인 방향의 큐 길이가 특정 임계값을 초과하면 비생산적인 방향도 선택할 수 있게 하면 fully adaptive router가 된다.

Figure 11.5는 512-프로세서 IBM SP2 시스템을 보여준다. 각 캐비닛(또는 frame)은 16개의 RS6000 워크스테이션과 하나의 32포트 스위치 보드를 포함하고 있다.

tag 라인은 유효한 flit을 식별하며, token 라인은 반대 방향으로 동작하여 송신 노드에 credit을 반환한다(흐름 제어를 위함). 스위치를 통과하는 지연 시간은 20ns 사이클 5개다.

Figure 11.6에 보이듯, 8개의 switch 칩이 2단계 양방향 네트워크로 구성된 32포트 스위치 모듈에 배열된다. 이 모듈은 양쪽 측면에서 각각 16개의 양방향 채널을 제공한다. 스위치 모듈 밖으로 나가는 모든 채널은 differential ECL 신호로 전달된다. SP 시스템의 가장 하위 단계에서는 16개의 프로세서 모듈이 하나의 스위치 모듈의 한 쪽 16포트에 연결된다. 이 17개의 모듈은 하나의 캐비닛(frame)에 통합되어 구성된다.

16개 이상의 프로세서를 가진 SP 시스템은 여러 frame과 switch module로 구성된다. 최대 80프로세서(5 frame)까지는 Figure 11.7처럼 frame들을 직접 연결하여 구성할 수 있다. 더 큰 시스템은 frame을 folded Clos 네트워크의 첫 두 단계로 사용하고, 16×16 중간단계와 32포트 최종단계를 제공하기 위해 switch module을 사용한다. 예를 들어, Figure 11.8은 32개의 frame과 16개의 추가 switch module로 512프로세서 시스템을 구성하는 방식을 보여준다. 8K 프로세서 시스템까지는 두 단계의 switch module을 이용해 구축할 수 있다.

※ 각 switch module은 fault tolerance를 위해 동일한 32포트 switching 구조를 2세트 보유한다(총 16개의 switch chip). 한 세트는 실제 switching을 수행하고, 다른 하나는 이를 shadow하여 오류를 감지한다.

각 노드는 Section 11.1.1에서 설명한 source routing table을 포함한다. 이 테이블은 각 목적지마다 4개의 경로를 저장하고 있다. Figure 11.9에서 보듯, 패킷이 라우팅을 위해 도착하면, 목적지와 함께 2비트 packet counter 값을 이용해 테이블을 인덱싱한다. packet counter는 매번 패킷이 생성될 때 증가한다. 8바이트의 route descriptor가 테이블에서 읽혀지는데, 그 중 첫 바이트는 이 descriptor에서 유효한 라우팅 flit의 개수 N(0~7)을 나타낸다.

이후 N개의 바이트는 각각 1~2 hop을 인코딩하는 routing flit이며, 최대 길이의 route descriptor는 최대 14 hop을 인코딩하는 7개의 flit을 포함할 수 있다. 이 routing flit들은 라우팅 시 사용되기 위해 패킷 앞에 붙는다.

Figure 11.10은 SP 패킷 형식을 보여준다. 패킷은 초기의 length flit 다음에 하나 이상의 routing flit과 payload data flit을 포함한다. 각 라우터는 첫 routing flit을 검사한다. selector bit인 S가 0이면, upper hop 필드(bits 4–6)를 사용해 출력 포트를 선택하고, S를 1로 설정한다. S가 1이면, lower hop 필드(bits 0–2)를 사용하고 해당 flit은 폐기되며 length는 감소한다. 기본적으로 S는 0으로 시작하지만, 경로가 홀수 개의 hop으로 구성된 경우, 마지막 routing flit의 S bit는 1로 초기 설정되어야 한다. SP 패킷은 source에서 정해진 경로를 따라 이동하며, 2 hop마다 하나의 routing flit을 소비한다. 목적지에 도달하면 routing flit은 모두 소모되어 length flit과 data flit만 남는다. 각 routing flit이 소모될 때마다 length flit이 감소하므로, 어느 시점에서든 패킷의 현재 길이를 나타낸다.

라우팅 테이블은 네트워크 링크 간의 부하를 균형 있게 분산하고, edge-disjoint 경로를 제공하도록 구성된다. 각 노드에 대해 첫 번째 목적지 경로는 네트워크에 대해 최소 신장 트리를 구성함으로써 결정된다. 초기에는 각 edge에 단위 가중치를 부여하고, 경로에 사용될 때마다 edge 가중치에 작은 값 ε를 더하여 가중치를 증가시킨다. 이후 업데이트된 edge 가중치를 기준으로 새로운 최소 신장 트리를 생성하고, 이를 기반으로 두 번째 경로를 생성한다. 이 과정을 반복하여 세 번째 및 네 번째 경로를 생성한다.

IBM SP 네트워크는 CM-5(Section 10.6) 및 Avici TSR(Section 9.5)의 네트워크와 비교해볼 만하다. SP 네트워크는 large configuration에서 CM-5와 거의 동일한 토폴로지를 갖고 있으며, 둘 다 8×8 포트 switch를 이용한 folded Clos 구조를 사용한다. 주요 차이는 SP 네트워크에는 concentration이 없고, CM-5는 4배 concentration이 존재한다는 점이다. 하지만 동일한 토폴로지를 사용하더라도 라우팅 방식은 매우 다르다. CM-5는 상향 링크에서 adaptive routing을 사용해 동적으로 부하를 분산시키는 반면, SP 네트워크는 oblivious하게 라우팅한다.

CM-5와 SP는 동일한 토폴로지를 갖고 라우팅 방식에서 차이를 보이는 반면, TSR과 SP는 매우 유사한 라우팅 방식을 갖지만 적용되는 토폴로지는 매우 다르다. TSR과 SP 모두 각 목적지에 대해 여러 개의 대체 경로를 source 테이블에 저장하는 oblivious source routing 방식을 사용한다. SP는 각 목적지마다 4개의 경로를, TSR은 24개의 경로를 유지한다. SP는 packet counter를 이용해 라우트를 선택하고, TSR은 flow identifier를 해싱하여 라우트를 선택한다. 이 방식은 관련된 패킷이 동일한 경로를 따라가도록 하여 순서를 유지하게 한다. 두 시스템 모두 라우팅 테이블의 대체 경로들을 네트워크 채널에 부하를 statically 분산되도록 구성한다. 이처럼 oblivious source routing 기법은 불규칙한 3D torus부터 folded Clos 네트워크까지 매우 다른 토폴로지에 적용 가능하며, 이는 source routing의 토폴로지 독립성이라는 큰 장점을 보여준다.

11.4 참고 문헌 노트

table-based routing은 유연성과 단순성 덕분에 실제 구현에서 인기가 많다. Section 11.3에서 언급했듯이 IBM SP1과 SP2 네트워크는 source routing table을 사용하며, Avici TSR도 마찬가지다. 그러나 네트워크 규모가 커질수록 source table의 크기는 부담이 된다. 그래서 SGI Spider, InfiniBand, 인터넷 같은 많은 네트워크는 node-table 방식을 채택한다. 많은 node-table 구현에서는 McQuillan이 도입하고 Kleinrock과 Kamoun이 자세히 분석한 hierarchical routing을 사용하여 테이블 크기를 줄인다. SGI Spider에서 사용된 hierarchical routing 메커니즘은 Exercise 11.4에서 다루어진다. 테이블 크기를 줄이는 또 다른 접근은 interval routing이다(Exercise 11.5 참고). 이는 Santoaro와 Khatib이 개발하고 van Leeuwen과 Tan이 확장하였으며 INMOS Transputer에서 구현되었다. CAM은 routing table 구현에서 일반적으로 사용되며, Pei와 Zukowski, McAuley와 Francis의 연구에서 설명되어 있다. Fredkin이 도입한 trie 구조도 특히 IP 라우터에서 routing table로 많이 사용된다. Pei와 Zukowski는 hardware에서의 trie 설계를, Doeringer 등은 IP lookup에 적합하도록 trie를 확장한 내용을 설명하였다.

11.5 연습문제

11.1 Source route 압축
본 장에서 제시된 source route에서는 각 포트 선택자 기호(N, S, E, W, X)를 3비트로 인코딩했다. source route 표현 시 평균 비트 수를 줄이기 위한 대체 인코딩 방법을 제안하라. torus에서 흔히 나타날 수 있는 "일반적인" 경로를 고려하여 인코딩 방식을 정당화하라. 또한 다음 경로들에 대해 기존 3비트 인코딩과 제안한 인코딩을 비교하라.
(a) NNNNNEEEX
(b) WNEENWWWWWNX
(c) SSEESSX

11.2 CAM 기반 routing table
8-ary 2-cube 토폴로지에서 node 34의 node-table을 고려하라. 이를 RAM에 저장할 경우 몇 개의 테이블 항목이 필요한가? CAM을 사용할 경우 얼마나 줄일 수 있는가? CAM에 필요한 항목들을 나열하라.

11.3 Minimal adaptive 경로 선택 논리
Figure 11.4에 제시된 route selection block에 대해 minimal adaptive routing을 구현하기 위한 논리를 설계하라. downstream 큐 길이가 가장 짧은 productive 경로를 선택하는 논리를 구상하라.

11.4 SGI Spider에서의 hierarchical routing
SGI Spider는 meta-table과 local table이라는 두 레벨의 hierarchical node-table을 사용한다. 네트워크 내 각 노드의 ID는 meta address(상위 비트)와 local address(하위 비트)로 나뉜다. 패킷이 next hop을 계산할 때, 먼저 meta address가 현재 노드와 일치하는지를 확인한다. 다르면 목적지의 meta address를 사용해 meta-table에서 next hop을 찾고, 같으면 local address를 사용해 local table에서 next hop을 찾는다. 개념적으로 meta address는 패킷을 해당 "영역(region)"으로 이동시키며, local address는 정확한 목적지까지 보낸다. 이 방식에서 node ID 중 2비트를 meta address로 사용할 경우, 2D torus 네트워크의 routing table 크기는 얼마나 작아질 수 있을까?

11.5 mesh 네트워크에서의 linear interval routing
interval routing은 각 노드의 outgoing edge에 중복되지 않는 구간(interval)을 할당함으로써 routing table 크기를 줄이는 방식이다. Figure 11.11은 linear interval labeling의 예시를 보여준다. 각 채널은 [x, y] 구간을 갖고, 목적지 d가 x ≤ d ≤ y를 만족하면 해당 채널을 통해 전송된다. 예를 들어, node 3에서 node 1로 가는 경우, node 3의 west 채널이 해당 구간을 포함하므로 west로 보낸다. 이어서 node 1에서 목적지인 node 0으로 이동한다. 4×4 mesh 네트워크에 대해 linear interval labeling을 구성하라. (목적지 노드 번호는 0~15로 부여)

11.6 IBM SP2를 위한 경로 생성
512-node IBM SP2 네트워크에서 spanning tree를 계산하는 프로그램을 작성하라. 이 트리를 이용해 각 목적지당 4개의 경로를 포함한 routing table을 생성하라.

11.7 Spanning tree 경로의 부하 균형
Exercise 11.6에서 생성한 routing table을 사용해 무작위 permutation을 여러 번 수행한 후, 채널 부하를 계산하라. 부하가 얼마나 균형적으로 분산되는가?

11.8 IBM SP 네트워크에서의 adaptive routing
SP 네트워크의 후속 버전은 상향 링크에서는 CM-5와 같은 adaptive source routing을 사용하고, 하향 링크에서는 source routing을 사용하였다. 이 방식이 어떻게 작동할 수 있을지 설명하라. SP 네트워크 구조 내에서 이 방식이 동작할 수 있도록 경로 인코딩 방식을 개발하라.

11.9 시뮬레이션
CM-5 스타일의 adaptive routing과 IBM SP 스타일의 oblivious routing을 512-node SP 네트워크에서 비교 시뮬레이션하라.

adaptive routing 알고리즘은 일반적으로 queue 점유율과 같은 네트워크 상태 정보를 이용하여, 패킷을 전달할 때 여러 가능한 경로 중 하나를 선택한다. 네트워크 상태에 따라 라우팅이 결정되므로, adaptive routing 알고리즘은 flow control 메커니즘과 밀접하게 연결된다. 이는 routing 알고리즘과 flow control이 대부분 독립적인 deterministic 및 oblivious routing과는 대조적이다.

이론적으로 좋은 adaptive routing 알고리즘은, 네트워크 상태 정보를 활용하지 못하는 oblivious routing보다 더 나은 성능을 보여야 한다. 그러나 실제로 많은 adaptive routing 알고리즘은 최악의 경우 성능이 나쁜 경우가 많다. 이는 대부분의 실용적인 adaptive routing 알고리즘이 local 정보를 사용하기 때문이다. 이러한 알고리즘은 local queue length와 같은 지역적인 네트워크 상태만을 참고하여 라우팅 결정을 내리기 때문에, 지역적인 부하 균형은 맞춰도 전체적으로는 부하가 불균형하게 되는 경우가 생긴다.

adaptive routing의 지역성은 트래픽 패턴 변화에 늦게 반응하는 문제도 일으킨다. 혼잡 지점보다 앞선 라우팅 지점의 queue가 가득 차야만 혼잡을 감지할 수 있기 때문이다. 따라서 adaptive routing에는 backpressure가 강하게 전달되는 flow control 방식(예: shallow queue 사용)이 바람직하다. 그래야 멀리 있는 혼잡에도 더 빨리 적응할 수 있다.

10.1 Adaptive Routing 기본

adaptive routing에 관련된 다양한 이슈는 간단한 8-node ring을 통해 설명할 수 있다. Figure 10.1에서는 노드 5가 노드 6으로 패킷을 지속적으로 전송하며, (5,6) 채널의 모든 대역폭을 사용 중이다.

동시에 노드 3은 노드 7로 패킷을 보내고자 한다. 이때 노드 3은 그림의 실선 화살표로 표시된 시계방향 경로와 점선 화살표로 표시된 반시계 방향 경로 중 선택할 수 있다.

전체 네트워크 상태를 실시간으로 알고 있는 독자는, 노드 3이 (5,6) 채널의 혼잡을 피하기 위해 반시계 방향을 선택해야 한다는 것을 쉽게 알 수 있다. 하지만 노드 3의 라우터는 (5,6) 채널에서 발생하는 혼잡을 알 수 없다. 이 혼잡은 노드 5의 queue에는 영향을 주지만, 다른 트래픽이 없다면 노드 3의 queue에는 영향을 주지 않는다.

adaptive routing 알고리즘이 네트워크 상태를 어떻게 감지하는지가 핵심이다. 이 질문은 공간과 시간이라는 관점으로 나눠볼 수 있다: 알고리즘이 local 정보를 사용하는가, global 정보를 사용하는가? 현재 정보를 사용하는가, 과거 정보를 사용하는가? 이 질문들은 이진적인 답이 있는 것이 아니라, local과 global 정보, 현재성과 과거성 사이에는 연속적인 스펙트럼이 존재한다.

거의 모든 adaptive router는 flit 기반 혹은 packet 기반 flow control을 사용하며(Chapter 12 참고), 현재 노드의 flit 혹은 packet queue 상태를 통해 local link의 혼잡을 추정한다. 다른 위치의 link 상태에 대한 직접적인 정보는 없다. 따라서 Figure 10.1의 상황처럼 노드 3이 단독 패킷을 노드 7로 보낼 경우, 해당 queue는 (5,6) 채널의 혼잡을 반영하지 않으며, 결국 노드 3은 어느 경로를 선택하든 무작위로 결정할 수밖에 없다.

라우터는 backpressure를 통해 네트워크 다른 위치의 혼잡을 간접적으로 감지할 수 있다. 한 노드의 queue가 가득 차면, 이전 노드로부터의 전송이 중단되며, 이로 인해 그 이전 노드의 queue도 차게 된다. 이 backpressure는 트래픽의 흐름과 반대 방향으로 네트워크를 따라 전파된다. 하지만 backpressure는 혼잡 지점으로 들어오는 트래픽이 있어야만 전파된다. 트래픽이 없다면 backpressure도 없고, 따라서 원거리 혼잡에 대한 정보도 없다.

예를 들어 Figure 10.1의 경우, 노드 4와 5의 입력 queue가 완전히 가득 차야만 노드 3이 (5,6) 채널의 혼잡을 감지할 수 있다.

Figure 10.2는 채널 위의 점들이 해당 채널 목적지 노드의 입력 버퍼에 있는 패킷 수를 나타내는 그림이다.

이 예는 adaptive routing이 stiff flow control과 함께 사용할 때 성능이 더 나은 이유를 보여준다. 예를 들어 각 입력 queue가 F = 4개의 패킷만 저장할 수 있다면, 노드 3은 8개의 패킷만 보낸 뒤 혼잡을 감지하고 반대 방향으로 라우팅을 전환한다. 네트워크는 비교적 빠르게 부하가 균형을 이루게 되며, 첫 8개의 패킷만 높은 지연을 겪게 된다. 반면 입력 queue가 F = 64개의 패킷을 저장할 수 있다면, 노드 3이 혼잡을 감지하는 데 16배 더 오래 걸리고, 16배 더 많은 패킷이 혼잡 경로로 인해 높은 지연을 겪는다.

부하 불균형이 경미할 경우, 혼잡 정보가 출발 노드까지 도달하는 데 더 오랜 시간이 걸린다. 예를 들어 어떤 채널이 10%만 초과 부하되었다면, 입력 버퍼 앞에 있는 버퍼가 한 칸 밀리기 위해서는 혼잡 경로로 10개의 패킷이 먼저 지나가야 한다. 이 경우, 출발 노드가 혼잡을 감지하는 데 매우 오랜 시간이 걸리며, 수많은 패킷이 비효율적으로 라우팅될 수 있다.

Figure 10.1의 예는 adaptive routing에서 정보의 현재성(currency) 문제도 보여준다. 예를 들어 노드 3이 (5,6) 채널의 혼잡을 감지하는 시점에, 노드 5→6의 트래픽이 종료되고 대신 노드 1→0의 트래픽이 시작되면, 노드 3은 실시간이 아닌 과거 정보를 바탕으로 (1,0) 채널로 잘못 라우팅할 수 있다. 이 경우 혼잡 채널의 소스 노드까지의 hop 수가 H = 2이고, 입력 버퍼 크기가 F일 때, 노드 3이 (5,6) 채널의 상태를 감지한 시점은 HF 패킷 이전의 상태인 것이다.

ring보다 복잡한 topology에서는 각 단계에서 adaptive routing 결정을 내리게 된다. 그러나 혼잡 정보의 지역성 때문에 여전히 비효율적인 전역 라우팅 경로가 발생할 수 있다.

Figure 10.3은 지역적으로는 좋은 선택이 전체적으로는 나쁜 경로가 되는 사례를 보여준다. 이 경우 패킷은 s = 00에서 d = 23으로 가며, 회색으로 표시된 경로를 따라 이동한다. 초기 hop은 노드 01로 북쪽 방향이고, 여기서 북쪽 link는 약간 혼잡해 보이므로 패킷은 동쪽으로 이동하여 노드 11로 간다. 이후 북쪽의 모든 경로가 매우 혼잡하여 결국 두 개의 매우 혼잡한 link를 지나가야 한다.

노드 01에서 (01,11) 채널을 선택하고 약간 혼잡한 (01,02) 채널을 피하려는 결정은, 이후 경로에서 더 심한 혼잡을 야기할 수 있다.

다른 모든 minimal routing 알고리즘과 마찬가지로, minimal adaptive routing 알고리즘은 source-destination 쌍이 minimal path 다양성(|R_sd| = 1)을 갖지 않는 경우, 혼잡을 피할 수 없다.

이 상황은 Figure 10.4에서 20에서 23으로 가는 경로에 나타난다. 각 hop에서 단 하나의 productive 방향(+y)만 존재하므로, 패킷은 혼잡한 (21,22) 채널을 피할 수 없다. 아래에서는 non-minimal adaptive routing이 이러한 병목을 어떻게 피하는지 설명한다.

이번 섹션에서 예시로 든 모든 네트워크는 torus였지만, minimal adaptive routing은 어떤 topology에도 적용될 수 있다. 예를 들어, Figure 9.2에 있는 folded Clos에서는 s와 d의 공통 조상 노드까지는 오른쪽으로 adaptive하게 라우팅하고, 그 이후에는 d까지 왼쪽으로 deterministic하게 라우팅하면 된다. 이 경우, 오른쪽으로 가는 구간에서는 모든 출력이 productive하지만, 왼쪽으로 가는 구간에서는 하나의 출력만 productive하다. 이는 실제로 Thinking Machines CM-5의 data network에서 사용된 방식이다 (10.6절 참고).

10.3 Fully Adaptive Routing

non-minimal 또는 fully adaptive routing에서는 패킷이 목적지까지의 최단 경로를 따라가야 한다는 제약이 사라진다. 패킷은 혼잡하거나 고장난 채널을 피하기 위해 일시적으로 목적지로부터 멀어지는 경로로도 전달될 수 있다.

예를 들어, Figure 10.5는 앞의 Figure 10.4에서 20에서 23으로 가는 경로에서 (21,22) 채널의 혼잡을 피하기 위해, 노드 21에서 패킷을 노드 31로 우회시키는 예를 보여준다. 이처럼 목적지로부터 멀어지는 방향의 채널을 따라가는 것을 misrouting이라 한다.

일반적인 fully adaptive routing 알고리즘은 productive output에 우선순위를 둔다. 즉, 혼잡이 없으면 목적지 쪽으로 보내지만, 경로 다양성을 높이기 위해 unproductive output도 허용한다. 한 가지 가능한 알고리즘은 다음과 같다:

• 주어진 패킷에 대해, queue 길이가 임계치보다 짧은 productive output이 있으면, 그중 가장 queue가 짧은 채널로 보낸다.
• 그렇지 않으면, productive 여부와 무관하게 가장 queue가 짧은 채널로 보낸다.

일부 알고리즘은 패킷이 방금 지나온 노드로 되돌아가는 채널을 선택하지 않도록(U-turn 방지) 제한을 두기도 한다. 채널을 오갔다가 되돌아가는 것은 비효율적이라는 가정 때문이다.

fully adaptive routing은 혼잡 회피를 위한 경로 다양성을 제공하지만, livelock이 발생할 수 있다 (14.5절 참고). livelock은 패킷이 네트워크 내에서 무한히 돌아다니다가 목적지에 도달하지 못하는 현상이다. 패킷이 절반 이상을 unproductive 경로로 misrouting하면 livelock이 발생할 수 있다.

Figure 10.6은 이러한 livelock 예시를 보여준다. 노드 00에서 03으로 가는 패킷이 노드 02에서 혼잡을 만나 12로 misrouting되며, 그 후 11로 또 misrouting된다. 이로 인해 11 → 02 → 11을 반복하는 순환이 시작된다.

livelock을 피하기 위해서는, fully adaptive routing 알고리즘이 시간 내에 진전이 보장되도록 어떤 메커니즘을 포함해야 한다. 예를 들어,

• misrouting을 M번까지만 허용한 후 minimal adaptive routing으로 되돌아가도록 하면, 목적지까지 H hops 떨어져 있는 패킷은 최대 H + 2M hops 내에 도달할 수 있다.
• 다른 방식은, H'개의 productive hop마다 한 번의 misrouting을 허용하는 것이다. 이 방식은 H' − 1 거리 단축을 위해 H' + 1 hops를 사용하므로, 전체적으로 패킷은 최대 H × (H'+1)/(H'−1) hops 안에 도달한다.
• chaotic routing(Exercise 10.3)은 전달 hop 수에 상한을 두지 않고, 확률적으로 결국 도달할 것이라는 전제를 사용한다.

fully adaptive routing은 livelock 외에도 deadlock 가능성도 높인다. 이에 대한 논의는 14장에서 다룬다.

10.4 Load-Balanced Adaptive Routing

adaptive routing 알고리즘은 일반적으로 local 정보만 기반으로 라우팅 결정을 내리기 때문에, 네트워크 전체의 부하 균형을 맞추기 어렵다. 이를 해결하기 위한 한 가지 접근은 hybrid routing 알고리즘을 사용하는 것이다.

이 방식은 다음과 같이 구성된다:

1. 먼저 9.3절에서 설명한 방법으로, oblivious하게 라우팅할 사분면(quadrant)을 선택한다.
2. 이후에는 backtracking 없이 해당 quadrant 내에서 adaptive routing을 사용하여 패킷을 목적지까지 보낸다.

oblivious하게 quadrant를 선택하는 단계는 global load balancing을 수행하고, adaptive routing 단계는 local load balancing을 수행한다.

이 hybrid 방식은 전체 부하 균형이 뛰어나고, 결과적으로 worst-case 성능이 매우 좋다. 다만, local 트래픽 패턴에서는 pure adaptive routing(minimal 또는 fully adaptive)에 비해 성능이 낮을 수 있다. 그 이유는 이 방식도 oblivious routing처럼 일부 패킷을 네트워크를 돌아가게 만들기 때문이다.

비록 이 알고리즘은 minimal하지 않고, 일부 패킷은 멀리 돌아가지만, 패킷은 항상 목적지를 향해 전진하며 livelock은 발생하지 않는다. 일단 라우팅 quadrant가 결정되면, 목적지까지 필요한 hop 수 H가 결정되고, 정확히 H hops 만에 도달하게 된다.

10.5 Search-Based Routing

지금까지 살펴본 라우팅 전략은 모두 greedy하고 conservative한 방식이었다.

• greedy: 한 번 채널을 선택하면 뒤로 물러나지 않는다 (backtrack 없음).
• conservative: 패킷을 하나의 경로로만 보낸다 (여러 경로에 동시에 전송하지 않음).

greedy하지 않은 라우팅 방식의 한 예로, 라우팅 문제를 검색(search) 문제로 보는 방식이 있다. 이 방식은 패킷이 최적 경로를 탐색하게 만든다. 이 때,

• 경로가 막히거나 혼잡하면 backtracking하거나,
• 혹은 여러 경로에 header를 broadcast하고, 그 중 최적의 경로로 data를 전송한다.

이러한 search-based 라우팅 알고리즘은 느리고 리소스를 많이 소모하므로 실제 라우팅에는 거의 사용되지 않는다. 하지만 오프라인에서 라우팅 테이블 생성을 위해 경로를 찾을 때는 유용하다.

10.6 사례 연구: Thinking Machines CM-5의 Adaptive Routing

Figure 10.7은 Thinking Machines의 Connection Machine CM-5 사진을 보여준다. CM-5는 Thinking Machines가 제작한 마지막 connection machine이며, 유일한 MIMD(Multiple Instruction, Multiple Data) 구조의 제품이었다. 초기 CM-1과 CM-2는 bit-serial, SIMD(Single Instruction, Multiple Data) 구조의 병렬 컴퓨터였다.

CM-5는 최대 16K개의 processing node로 구성되어 있으며, 각 노드는 32MHz SPARC 프로세서와 4-way vector unit을 포함한다. 이 시스템은 다음의 세 가지 별도 interconnection network를 포함하고 있었다:

1. Data network
2. Control network
3. Diagnostic network

CM-5는 다양한 관점에서 흥미로운 시스템이며, 영화 『쥬라기 공원』에도 잠깐 등장했다. 그러나 여기서는 data network에 초점을 맞춘다.

Figure 10.8에 나타나듯이, CM-5의 data network는 folded Clos topology를 사용하며, processor와는 duplex connection을 갖는다. switch의 첫 두 단계에는 2:1 concentration이 적용된다. 그림의 각 채널은 양방향에서 20MB/s(40MHz에서 4비트 폭)를 지원한다.

Figure 10.7: CM-5는 최대 16K개의 processing node를 포함하며, 각 노드는 32MHz SPARC 프로세서와 벡터 부동소수점 연산 유닛을 포함한다. 이 노드들은 folded Clos(fat tree) 네트워크로 연결되어 있다.

각 방향에 대해 differential signaling을 사용하며, 각 switch는 1μm CMOS standard-cell 기술로 구현된 단일 칩의 8×8 byte-wide router이다.
Figure 10.8에서 첫 번째 및 두 번째 네트워크 레벨 간의 채널은 backplane을 통해 구현되고, 상위 레벨 채널은 9피트 또는 26피트 길이의 케이블로 구성된다.

각 processing node는 두 개의 독립된 switch에 하나씩 연결되어 있어, 노드당 총 인터페이스 대역폭은 40MB/s이다. 이 duplex 연결 덕분에 네트워크는 단일 고장 지점(single-point fault)에 대해 내성이 있다. 즉, 노드에 연결된 router 하나가 고장나더라도 다른 채널을 통해 계속 메시지를 송수신할 수 있다. 각 프로세서는 memory-mapped interface를 통해 네트워크에 메시지를 주입하며, 메시지는 최대 5개의 32비트 word 데이터를 포함할 수 있다. (후속 버전에서는 최대 18 word까지 허용)

4개의 processing element로 이루어진 그룹에 연결된 두 개의 level-1 switch는 논리적으로 하나의 노드처럼 동작하며, 각각 4개의 다른 level-2 switch에 연결된다. 이와 유사하게, 도식의 4개의 level-2 switch는 각각 8개의 다른 level-3 switch에 연결된다(그중 2개만 그림에 나타남). 이 topology는 level i에 있는 switch가 오직 downstream(왼쪽)으로 메시지를 전송함으로써 4^i 개의 노드에 접근할 수 있도록 구성되어 있다.

CM-5의 메시지 라우팅은 9.2.1절에서 설명한 방식과 유사하되, upstream 라우팅이 oblivious가 아니라 adaptive하다는 점이 다르다. 노드 s에서 노드 d로 가는 메시지는 두 단계로 라우팅된다:

1. 메시지는 upstream 방향(오른쪽)으로 공통 조상 switch까지 라우팅되며, 이 단계는 idle한 upstream 링크 중 무작위로 선택되어 adaptive하게 수행된다.
2. 공통 조상에 도달하면, 메시지는 목적지 d까지의 고유 경로를 따라 downstream(왼쪽)으로 deterministic하게 라우팅된다. 이때 destination-tag routing을 사용한다.

Figure 10.9는 CM-5 메시지의 형식을 보여준다. 메시지는 4비트 단위의 flit으로 구성되며, 송신 노드가 credit을 가진 동안에는 매 cycle마다 하나의 flit이 4-bit 데이터 채널을 통해 전송된다. 메시지의 첫 번째 flit은 height flit으로, 해당 메시지가 공통 조상에 도달하기 위해 얼마나 upstream(오른쪽)으로 이동해야 하는지를 나타내는 height h 값을 포함한다.

이후에 오는 ⌈h/2⌉ 개의 route flit은 downstream 경로를 구성하며, 각각의 route flit은 두 개의 2-bit route field를 포함한다. 각 field는 downstream 라우팅의 한 단계를 나타낸다. 그 외의 flit은 payload와 관련된 데이터이며 라우팅과는 무관하다.

upstream 라우팅 단계는 메시지 헤더의 height 필드 h로 제어된다. 메시지가 각 router에 들어올 때, h는 해당 router의 레벨 l과 비교된다.

• l < h인 경우, upstream 라우팅은 계속되며, idle한 upstream 링크 중 무작위로 선택된다.
• 모든 링크가 busy이면, 메시지는 block 상태로 남아 idle 링크가 생길 때까지 대기한다.
• l = h인 router에 도달하면, s와 d의 공통 조상에 도달한 것이며 downstream 라우팅 단계가 시작된다.

downstream 단계에서는 각 hop마다 route flit의 route field 하나가 사용되며, 동시에 height h가 감소한다. 이를 통해 다음의 두 가지 효과가 있다:

1. head flit 다음에는 항상 ⌈h/2⌉ 개의 route flit이 유지된다.
2. h의 최하위 비트(LSB)를 통해 어떤 route field를 사용할지 결정한다.
   • h가 짝수일 경우, r의 왼쪽 field를 사용해 downstream 포트를 선택하고, h는 1 감소한다.
   • h가 홀수일 경우, r의 오른쪽 field를 사용하고, h를 감소시키며, 이 route flit은 discard된다.
   • 다음 hop에서는 h가 다시 짝수이며, 새로운 route flit의 왼쪽 field가 사용된다.

h가 0이 되면 목적지에 도달한 것이고, 모든 라우팅 관련 flit은 소진된 상태가 된다.

CM-5의 upstream 라우팅의 adaptive 특성은 flit-level blocking flow control(13.2절 참고)에 의해 조절된다. channel의 흐름을 제어하기 위해, CM-5는 on/off flow control의 변형을 사용한다 (13.3절 참고). 작동 방식은 다음과 같다:

• 입력 포트 버퍼에 공간이 있으면, 수신 라우터는 송신 라우터에 token을 보낸다.
• 송신자는 이 token을 즉시 사용하여 flit을 보낼 수 있지만, token을 저장(credit처럼 bank)할 수는 없다. flit이 없으면 token은 무효화된다.
• 버퍼가 가득 차면 token이 보내지지 않고, 트래픽이 차단된다.
• CM-5의 각 출력 포트에는 하나의 5-word 메시지를 저장할 수 있는 버퍼가 있다 (후속 버전에서는 18-word).

upstream 라우팅 단계에서, 패킷은 idle 상태의 upstream 포트에 무작위로 할당된다.

• 출력 버퍼가 비어 있으면 포트는 idle로 간주되며, 새로운 메시지를 할당받을 수 있다.
• idle 포트가 없다면, 패킷은 현 위치에서 block되며 입력 버퍼를 점유하게 되고, 결과적으로 하위 노드의 패킷들도 차단될 수 있다.

router는 출력 버퍼가 전체 메시지를 수용할 수 있을 때만 메시지를 해당 포트에 할당하므로, 메시지가 router의 crossbar를 지나는 도중에는 block되지 않는다.

10.7 참고 문헌

adaptive routing의 발전은 deadlock과 livelock을 방지하기 위한 flow control 메커니즘과 밀접하게 연관되어 있다. 초기 adaptive routing 알고리즘에는 Linder와 Harden [118], Chien [36], Aoki와 Dally [48], 그리고 Allen 외 [8]의 연구가 포함된다. Duato의 프로토콜 [61]은 Cray T3E [162]에서 사용된 알고리즘을 포함하는 adaptive routing 알고리즘 계열을 가능하게 했다. Chaos routing (Exercise 10.3)은 Konstantinidou와 Snyder [104]에 의해 소개되었고, Bolding [26]에 의해 확장되었다. CM-5에서 사용된 fat tree에서의 minimal adaptive routing은 Leiserson [114]에 의해 설명되었다. Boppana와 Chalasani [27]는 여러 라우팅 방법을 비교하고, 실제 adaptive 알고리즘이 특정 측면에서는 deterministic 알고리즘보다 못할 수 있음을 보여주었다.

10.8 연습문제

10.1 4×4 mesh에서 minimal adaptive routing의 이점: minimal adaptive routing (10.2절)이 minimal oblivious routing (9.2절)보다 우수한 permutation traffic pattern을 찾고, steady state에서 두 알고리즘의 γ_max를 계산하라. (backpressure 정보가 네트워크 전체에 전파될 만큼 충분한 시간이 경과했다고 가정)

10.2 minimal과 load-balanced adaptive routing 비교: load-balanced adaptive routing (10.4절)이 minimal adaptive routing보다 나은 permutation traffic pattern 하나, 반대로 minimal이 더 나은 pattern 하나를 찾아라.

10.3 chaotic routing의 livelock 없음 증명: chaotic routing은 deflection routing 방식이다. 여러 패킷이 동일한 채널을 두고 경합할 경우, router는 임의로 하나의 패킷에 해당 채널을 할당하고, 나머지는 사용 가능한 다른 출력 포트(비생산적일 수도 있음)로 misrouting된다. 모든 입력 포트를 어떤 출력 포트에든 할당할 수 있으므로, 항상 전송은 가능하다. T cycle 동안 목적지에 도달하지 못할 확률이 T가 커질수록 0에 가까워짐을 보임으로써, livelock이 확률적으로 발생하지 않음을 설명하라.

10.4 fat tree에서 adaptive와 oblivious routing 비교: 8×8 crossbar switch로 구성된 256-node folded Clos (fat tree) 네트워크에서 dropping flow control을 사용할 때, 어떤 알고리즘이 dropping 확률이 더 낮은가? 트래픽 패턴이 바뀔 때, 두 dropping 확률은 어떻게 변하는가?

10.5 CM-5에서의 최악의 트래픽 패턴: CM-5 네트워크에 대해, randomized oblivious routing (9.2.1절)의 최악의 트래픽 패턴을 찾고, 이 패턴에 대해 adaptive와 oblivious routing의 throughput을 비교하라.

10.6 시뮬레이션: 8-ary 2-cube 네트워크에서 adaptive routing의 buffer 깊이와 응답 시간의 tradeoff를 분석하라. 두 traffic permutation을 T cycle마다 번갈아가며 적용하고, 시간에 따른 평균 패킷 지연을 그래프로 나타내라. 노드당 버퍼 크기가 이 그래프의 모양에 어떤 영향을 주는지 분석하라.

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 기준)

이전에는 특정한 의심 트래픽 패턴만 시뮬레이션하여 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))의 기대값은 얼마인가?

라우팅은 주어진 topology 내에서 source node에서 destination node로 가는 경로를 선택하는 과정이다. 네트워크의 topology, 즉 지도와 같은 구조가 정해지면, 그다음은 그 지도에서 목적지까지 가는 길을 고르는 것이 라우팅이다. Topology가 네트워크의 이상적인 성능을 결정한다면, 라우팅은 이 성능 중 얼마나 실제로 구현되는지를 결정하는 두 가지 핵심 요소 중 하나이다. 나머지 하나는 12장과 13장에서 다룰 flow control이다.

라우팅 알고리즘은 여러 이유에서 중요하다. 좋은 라우팅 알고리즘은 permutation traffic과 같은 비균일 트래픽 패턴이 있어도 네트워크의 채널들 간 부하를 고르게 분산시킨다. 채널 부하가 균형을 이룰수록 네트워크의 throughput은 이상적인 값에 가까워진다. 하지만 의외로, 현재 사용 중인 많은 router들이 부하를 고르게 분산하는 데 실패하고 있다. 대부분의 경우, 각 노드 쌍 사이의 트래픽은 단일하고 미리 정해진 경로를 따른다. 이런 라우팅 알고리즘은 비균일 트래픽 상황에서 큰 부하 불균형을 유발할 수 있으며, 이로 인해 throughput이 떨어진다. 그럼에도 불구하고 이런 라우팅 방식이 사용되는 이유는 또 다른 중요한 라우팅 알고리즘의 특성인 짧은 경로 길이를 최적화하기 위함이다.

잘 설계된 라우팅 알고리즘은 경로 길이를 가능한 짧게 유지하여 hop 수를 줄이고, 메시지의 전체 latency를 낮춘다. 하지만 때로는 minimal routing(항상 최단 경로를 선택하는 방식)이 부하 균형과 throughput 향상과 충돌할 수 있다. 특히 oblivious routing 알고리즘에서는 모든 트래픽 패턴에 대해 부하 균형을 맞추려면 전체 메시지의 평균 경로 길이를 늘릴 수밖에 없다. 반대로 평균 경로 길이를 줄이면 부하 균형이 무너진다. Oblivious 알고리즘은 현재 트래픽 패턴을 고려하지 않기 때문에 이런 tradeoff가 생긴다. 이 알고리즘들은 9장에서 자세히 다룬다.

• 1. Greedy Routing
  • 방법: 목적지까지의 최단 거리 방향으로 항상 라우팅함.
    • 예: 노드 0에서 노드 3은 시계방향, 노드 0에서 노드 5는 반시계방향.
    • 거리가 같을 경우 무작위로 선택.
  • 특징: 경로는 짧지만, 부하 분산이 되지 않아 특정 방향에 트래픽이 몰릴 수 있음.
  • Tornado traffic에서 throughput: 0.33

  ---

  2. Uniform Random Routing
  • 방법: 패킷마다 양방향 중 무작위로 한 방향을 동일 확률(50%)로 선택.
  • 특징: 균등 확률로 방향을 선택하므로, 부하 분산이 일부 이루어짐.
  • Tornado traffic에서 throughput: 0.40

  ---

  3. Weighted Random Routing
  • 방법: 짧은 방향을 높은 확률(1−d/8), 긴 방향을 낮은 확률(d/8)로 선택.
    • 여기서 d는 source와 destination 간의 최소 거리.
  • 특징: 트래픽을 짧은 경로에 집중하되, 일부는 긴 경로로 분산시켜 부하 분산 효과 향상.
  • Tornado traffic에서 throughput: 0.53

  ---

  4. Adaptive Routing
  • 방법: 현재 로컬 채널 부하를 고려하여 트래픽이 덜 혼잡한 방향으로 선택.
    • 큐 길이나 과거의 패킷 수로 채널 부하를 추정.
    • backtracking은 허용되지 않음 → source에서 한 번만 결정.
  • 특징: 실시간 네트워크 상태를 반영하여 경로 결정.
  • Tornado traffic에서 throughput: 0.53 (weighted random과 동일 수준)

최악의 경우 throughput을 가장 잘 보장하는 알고리즘은 무엇일까? 대부분의 사람들은 greedy 알고리즘을 선택한다. 실제로 2002년 박사 자격 시험에서 이 문제가 출제되었고, 응시자의 90% 이상이 greedy 알고리즘을 선택했다. 하지만 이 알고리즘은 최악의 경우에 최선의 throughput을 제공하지 않는다.

예를 들어, 각 노드 i가 i+3 mod 8로 패킷을 보내는 tornado traffic pattern을 보자. 이때 greedy routing을 사용하면 모든 트래픽이 ring을 시계방향으로만 이동하고, 반시계 방향 채널은 사용되지 않아 부하 불균형이 심해진다. 이로 인해 각 terminal의 throughput은 b/3으로 떨어진다. 반면, random routing에서는 반시계방향 링크에 5/2의 부하가 걸려 throughput은 2b/5가 된다. Weighted random은 전체 트래픽 중 5/8이 3 링크를, 3/8이 5 링크를 지나므로 부하는 각 방향에 대해 15/8이 되고, throughput은 8b/15가 된다. Adaptive routing도 잘 구현된다면 이와 같은 부하 균형을 달성하여 동일한 throughput을 낼 수 있다.

이 예시는 라우팅 선택이 부하 균형에 얼마나 큰 영향을 미치는지를 보여준다. 물론 throughput은 최적화할 수 있는 여러 지표 중 하나일 뿐이고, 어떤 지표를 중시하느냐에 따라 적절한 알고리즘 선택은 달라질 수 있다.

8.2 라우팅 알고리즘의 분류

라우팅 알고리즘은 source node x에서 destination node y까지 가능한 경로 집합 Rxy 중에서 어떻게 선택하는지를 기준으로 분류할 수 있다.

• Deterministic routing: 항상 동일한 경로를 선택한다 (Rxy의 크기가 1 이상이라도 항상 같은 경로 선택). topology의 경로 다양성을 무시하므로 부하 분산에는 매우 취약하다. 그럼에도 구현이 쉽고 deadlock-free로 만들기 쉬워서 널리 사용된다.
• Oblivious routing: deterministic 알고리즘을 포함하는 개념으로, 현재 네트워크의 상태를 전혀 고려하지 않고 경로를 선택한다. 예를 들어, 가능한 모든 경로에 대해 트래픽을 균등 분산하는 random 알고리즘이 이에 해당한다.
• Adaptive routing: 네트워크의 상태에 따라 동적으로 경로를 선택한다. 상태 정보는 노드나 링크의 사용 여부, 큐 길이, 채널 부하 이력 등을 포함할 수 있다.

앞서 소개한 tornado 예제는 이 세 가지 유형의 예시를 모두 포함한다. Ring에서 greedy는 deterministic routing, random과 weighted random은 oblivious routing, adaptive는 초기 hop의 채널 부하를 고려하므로 adaptive routing이다.

이때 언급된 알고리즘들은 Rxy, 즉 최소 경로 집합을 기준으로 한 것이며, 이를 minimal routing이라고 한다. 반면, minimal이 아닌 경로도 포함하는 경우 R′xy에서 선택하며 이를 non-minimal routing이라고 한다. Ring 예제에서 greedy는 minimal, random과 adaptive는 non-minimal로 분류된다.

8.3 라우팅 관계 (Routing Relation)

라우팅 알고리즘을 라우팅 관계 R과 선택 함수 ρ로 나누어 표현하면 유용하다. R은 경로(또는 incremental routing에서는 채널)들의 집합을 반환하고, ρ는 그 중 하나를 선택하는 역할을 한다.

라우팅 알고리즘이 incremental인지, node 기반인지 channel 기반인지에 따라 R은 세 가지 방식으로 정의된다.

• R: N × N → P(P)
  두 노드 간 가능한 전체 경로의 집합을 반환한다. 이를 all-at-once routing이라 부른다.
• R: N × N → P(C)
  현재 노드와 목적지를 입력으로 받아 가능한 채널들의 집합을 반환한다.
• R: C × N → P(C)
  현재 채널과 목적지를 입력으로 받아 가능한 채널들의 집합을 반환한다.

첫 번째 방식은 라우팅 결정을 source에서 한 번에 수행하고 패킷과 함께 경로 정보를 저장한다. 계산은 단순하지만, 패킷마다 경로 정보를 함께 보내야 하므로 오버헤드가 있다.

두 번째, 세 번째 방식은 incremental routing으로, hop마다 라우팅 결정을 반복 수행한다. 패킷마다 경로 정보를 들고 다닐 필요는 없지만, hop마다 R을 계산해야 하므로 latency가 증가할 수 있다. 또한, 일부 라우팅 전략은 incremental 방식으로는 구현할 수 없다.

특히 Relation 8.2 방식은 수직에서 수평, 혹은 그 반대 방향으로 들어오는지를 구분하지 못하므로 2-D mesh에서 특정 노드에서만 방향 전환을 제한하는 전략은 구현 불가하다. Relation 8.3은 이를 어느 정도 해결할 수 있다. 이전 채널 정보를 활용해 deadlock 방지에도 효과적이다.

라우팅이 deterministic이 아니라면, R은 여러 경로/채널을 반환하므로, 선택 함수 ρ가 최종 선택을 담당한다. ρ가 네트워크 상태를 고려하지 않으면 oblivious, 고려하면 adaptive가 된다.

8.4 Deterministic Routing

가장 단순한 형태인 deterministic routing은 모든 source-destination 쌍에 대해 항상 같은 경로를 선택한다. 예: R: N × N → P. 이는 경로 다양성이 없기 때문에 부하 불균형을 유발한다. 어떤 트래픽 패턴에서는 모든 deterministic routing이 심한 부하 불균형을 일으킨다.

그럼에도 불구하고, 구현이 간단하고 비용이 낮아 과거 네트워크에서 널리 사용되었고, 지금도 irregular topology에서는 자주 쓰인다. 이는 randomized나 adaptive 라우팅을 설계하기 어렵기 때문이다.

대부분의 topology에서는 minimal deterministic routing function을 선택하는 것이 합리적이다. 최소한 경로 길이는 짧게 유지된다. 일부 topology에서는 간단한 deterministic 접근 방식이 adaptive를 포함한 다른 어떤 minimal routing algorithm보다도 부하 분산이 잘 되는 경우도 있다 (Exercise 9.2 참고). 또한 특정 source-destination 쌍 사이에서 메시지 순서를 유지해야 하는 경우, deterministic routing이 이를 단순하게 보장하는 방법이 될 수 있다. 이는 예를 들어 특정 cache coherence protocol에서 중요하다.

이 절에서는 가장 널리 쓰이는 deterministic routing algorithm 두 가지, 즉 butterfly에서의 destination-tag routing과 torus/mesh에서의 dimension-order routing을 설명한다.

8.4.1 Butterfly Network에서의 Destination-Tag Routing

k-ary n-fly network에서 (4.1절 참고) 목적지 주소는 radix-k 숫자 n자리로 해석되며, 이것이 경로 선택에 직접 사용된다. 주소의 각 자릿수는 네트워크 각 단계에서 출력 포트를 선택하는 데 사용된다. 이는 마치 source-routing table에서 미리 정해진 routing header처럼 동작한다. 2장에서 설명한 단순 router에서 사용된 방식이다.

Figure 8.3(a)는 source 3에서 destination 5까지 가는 경로를 예시로 보여준다. 5의 이진수는 101이고, 각 비트는 네트워크의 각 단계에서 출력 포트를 결정한다. 첫 번째 비트 1은 아래쪽 출력 포트를, 두 번째 비트 0은 위쪽 포트를, 세 번째 비트 1은 다시 아래쪽 포트를 선택한다.

이 예에서 출발 노드 3의 주소는 실제로 사용되지 않았다. 다시 말해, 어떤 노드에서 출발하더라도 101 패턴을 따라가면 목적지 5에 도달한다. 이는 모든 목적지 주소에 대해 동일하게 적용된다. 즉, destination-tag routing은 목적지 주소에만 의존하며 source와는 무관하다.

Figure 8.3(b)는 4-ary 2-fly network에서 7번 노드에서 11번 노드로 가는 경로를 보여준다. 여기서 목적지 주소 11은 234(4진수)로 해석되며, 첫 번째 router에서 포트 2(위에서 세 번째), 두 번째 router에서 포트 3(맨 아래)을 선택한다. 이 역시 출발 노드에 상관없이 목적지를 정확히 선택할 수 있다.

8.4.2 Cube Network에서의 Dimension-Order Routing

dimension-order 또는 e-cube routing은 torus 및 mesh와 같은 direct k-ary n-cube network에서 destination-tag routing과 유사한 방식이다. 목적지 주소를 radix-k 숫자로 해석하고, 각 자릿수를 하나씩 사용하여 경로를 결정한다. 하지만 butterfly network와 달리 cube network에서는 한 자릿수를 해결하기 위해 여러 hop이 필요할 수 있다.

예를 들어 Figure 8.4의 6-ary 2-cube에서 node 03에서 node 22로 이동하는 패킷을 보자. torus에서는 각 차원을 시계방향 또는 반시계방향으로 이동할 수 있으므로, 먼저 각 차원에서의 최단 방향을 계산해야 한다.

source s = (0, 3), destination d = (2, 2)일 때:

• m = (2 − 0, 2 − 3) mod 6 = (2, 5)
• Δ = (2, 5) − (0, 6) = (2, -1)
• D = (+1, -1) → x 차원은 +1 방향(시계방향), y 차원은 -1 방향(반시계방향)

이 정보를 기반으로 패킷은 먼저 x 차원에서 이동하고, 목적지 좌표에 도달하면 y 차원으로 전환한다. Figure 8.4에서 node 03에서 시작하여 x 차원으로 한 hop(03 → 02), y 차원으로 두 hop(02 → 12 → 22) 이동한다.

목적지를 32로 변경하면 Δ = (3 − 0, 2 − 3) = (3, 5) → D = (0, -1). y 방향의 preferred direction이 0이 된다. 이는 양방향 모두 3 hop이 필요하다는 뜻이며, 이 경우 부하를 균형 있게 분산하기 위해 deterministic routing 대신 무작위로 양방향으로 패킷을 나누는 것이 효과적이다. Equation 8.4를 보면, preferred direction이 0이 되는 경우는 k가 짝수일 때만 발생한다.

mesh에서는 wraparound channel이 없으므로 방향 선택이 단순해진다:

• DM,i = +1 if di > si, -1 otherwise

Dimension-order routing은 부하 분산 성능은 좋지 않지만, 다음 두 가지 이유로 널리 사용된다:

1. 구현이 매우 간단하다. 특히 각 차원별로 router를 분할하여 dimension-slicing이 가능하다.
2. 각 차원 간의 채널 dependency에 cycle이 생기지 않도록 하여 deadlock 방지를 단순화한다. 다만, 차원 내에서는 여전히 deadlock이 발생할 수 있다 (14장 참고).

8.5 사례 연구: Cray T3D에서의 Dimension-Order Routing

Figure 8.5는 최대 2,048개의 DEC Alpha processing element를 3-D torus로 연결한 Cray T3D를 보여준다. T3D는 shared-memory multiprocessor이며, 각 PE는 로컬 메모리를 가지며 다른 PE의 메모리에도 접근 가능하다. 각 PE 쌍은 하나의 router를 공유하고, 이 router는 네트워크 인터페이스를 통해 연결된다.

T3D는 dimension-order routing을 사용하며, Figure 8.6에 보이듯 각 차원(x, y, z)을 위한 동일한 ECL gate array로 구현된 dimension-sliced router를 사용한다. 이는 J-Machine router(5.5절)와 유사한 구조이다. 이러한 분할은 dimension-order routing 덕분에 가능하다.

패킷이 network interface로부터 들어오면, x router가 이를 받아 x 좌표가 목적지인지 판단한다. 목적지에 도달하지 않았다면 +x 또는 −x 방향으로 전달하고, x 좌표가 일치하면 다음 y router로 넘긴다.

패킷은 +x 방향(xpOut 채널)을 따라 전달된다. 이후 각 x router에서는 현재 위치가 목적지의 x 좌표와 일치하는지 확인한다. 일치하면 y router로 전달하고, 그렇지 않으면 계속 +x 방향으로 이동한다.

Cray T3D의 각 router 채널은 300 MBytes/s의 대역폭을 가지며, 모듈 간 wire mat을 통해 연결된다. 각 채널은 16비트 data와 8비트 control 신호로 구성되어 있으며, 150 MHz에서 동작한다. 이는 원래 Alpha 21064 프로세서와 동일한 클럭이다. Wire mat은 torus topology를 구성하기 위해 보드 엣지 커넥터에 수작업으로 연결된 여러 개의 wire들을 엮은 구조로, 불규칙하게 짜인 직물처럼 보여서 'mat'이라고 불린다. 각 data/control 신호는 wire mat 내에서 differential ECL 신호로 twisted pair를 통해 전달된다.

그림 8.6은 T3D router가 x, y, z 세 개의 차원에 대해 동일한 ECL gate array 칩 세 개로 분할되어 구성됨을 보여준다.

Cray T3D에는 I/O 노드가 포함되어 있으며, 이들은 x 및 z 차원으로만 네트워크에 연결된다. 이로 인해 torus topology는 다소 불규칙해진다. 일반적으로 메시지는 x에서 시작해서 z에서 끝나므로 문제가 없어 보이지만, 메시지를 보내는 노드가 I/O 노드와 y 차원만 다를 경우 문제가 발생할 수 있다. 이를 해결하기 위해 해당 노드에는 두 개의 주소가 부여된다. 이 문제는 Exercise 8.8에서 더 자세히 다룬다.

8.6 참고 문헌

Tornado traffic 문제와 weighted random 해법은 Singh 외 [168]에서 설명되었다. 라우팅 관계의 여러 형태와 이들이 deadlock 분석에서 가지는 중요성은 Dally [57]와 Duato [60, 61, 62]에 의해 다루어졌다. Butterfly network에서의 destination-tag routing은 Lawrie [110]가 처음 설명했으며, torus network에서의 e-cube routing은 Sullivan과 Bashkow [179]가 제안했다. Degree δ를 가진 네트워크에 대해 Borodin과 Hopcroft [28], Kaklamanis 외 [91]는 특정 트래픽 패턴이 deterministic routing 알고리즘에서 최소 √(N/δ) 이상의 채널 부하를 유도할 수 있음을 보여주었다.

8.7 연습문제

8.1 Section 8.1의 라우팅 알고리즘과 네트워크를 다시 고려하라. 다음 조건에서 최적의 알고리즘은 무엇인가?

(a) 최소 메시지 지연
(b) 균일 트래픽에서 최고의 throughput
(c) 다양한 permutation 트래픽 패턴에서 평균 throughput 최대화

각 조건당 하나의 알고리즘만 선택하고 그 이유를 설명하라.

8.2 Incremental routing의 한계
관계식 8.1(path-based relation)으로는 표현할 수 있지만, 관계식 8.2 및 8.3(incremental form)으로는 표현할 수 없는 라우팅 알고리즘을 설명하라.

8.3 Incremental 및 all-at-once routing의 header bit
Destination-tag routing을 incremental 또는 all-at-once 방식으로 구현할 수 있다. 각 방식에 대해 패킷에 저장되어야 할 비트 수를 계산하라. 어느 방식이 비트 수가 적은가? 이 관계는 일반 topology의 minimal routing에서도 성립하는가? Topology의 path diversity와 어떤 관련이 있는가?

8.4 Ring에서 backtracking 허용
Section 8.1에서 다룬 라우팅 예에서 backtracking을 허용한다면, weighted random 알고리즘보다 더 나은 최악의 경우 throughput을 제공하는 알고리즘을 개발할 수 있는가? 있다면 제시하고, 없다면 그 이유를 설명하라.

8.5 Stage가 추가된 butterfly에서의 라우팅
k-ary n-fly에서 하나 이상의 stage가 추가된 구조를 위한 deterministic 방식의 destination-tag routing 확장 방법을 설명하라. 부하 분산을 개선하기 위한 간단한 randomization 방법도 제안하라.

8.6 Cray T3D에서의 방향-우선 라우팅
Figure 8.6의 Cray T3D router 채널 레이블을 재배열하여 첫 번째 router는 +x와 +y, 두 번째는 +z와 −x, 세 번째는 −y와 −z를 처리하게 만든다고 하자. 이 분할 방식에서도 동작 가능한 라우팅 알고리즘을 설명하라. 한 번 router에 도달한 패킷은 이전 router로 돌아갈 수 없음을 명심하라.

8.7 방향-우선 라우팅의 장점
Exercise 8.6에서 유도한 라우팅 알고리즘이 dimension-order routing보다 가지는 장점은 무엇인가?

8.8 T3D에서 I/O 노드 라우팅
T3D 네트워크에서 I/O 노드는 x 및 z 차원에만 추가된다. 예를 들어, (0,0,0)부터 (3,3,3)까지 주소를 갖는 64-node 4-ary 3-cube가 있다고 하자. 이때 (4,0,0) 또는 (0,0,4)와 같은 주소로 I/O 노드를 추가할 수 있다. 모든 내부 노드에서 I/O 노드로, 그리고 그 반대로 dimension-order routing으로 라우팅이 가능하도록 하기 위해 I/O 노드에 두 개의 주소를 어떻게 부여할 수 있는지 설명하라.

8.9 Torus에서 “정확히 반대 방향” 트래픽 부하 균형
Dimension-order routing에서는 torus에서 노드가 정확히 반대 방향에 있을 때 부하 균형 문제가 발생할 수 있다. 이때 항상 positive 방향만 선택한다면 균일 트래픽에서의 throughput은 어떻게 되는가? 최악의 경우 throughput은 얼마인가? capacity의 분수로 표현하라. deterministic 알고리즘을 유지하면서도 이러한 반대 방향 부하 균형 문제를 개선할 수 있는 방법을 제안하고, 균일 및 최악의 throughput을 다시 계산하라.

8.10 CCC에서의 minimal routing
Exercise 5.8에서 설명한 일반 CCC topology에 대해 near minimal routing 알고리즘을 설계하라. 항상 정확한 최소 경로를 찾기보다 단순함을 우선하되, 생성되는 경로가 [128]에서 보여준 최대 직경 Hmax = 2n + ⌈n/2⌉ − 2를 초과하지 않도록 하라. 균일 트래픽에서의 부하 분산 특성도 논의하라.