Zeah Engineering Factory

이제까지 네트워크 설계와 시뮬레이션 도구에 대해 살펴보았으므로, 본 장에서는 여러 시뮬레이션 예제를 제시한다. 이 예제들은 특정 네트워크나 라우터 설계의 세부 연구를 위한 것이 아니다. 대신, 일반적인 interconnection network에서 수행할 수 있는 유용한 실험들을 소개하고, 흥미롭고 때로는 직관에 반하는 결과들을 강조하기 위한 것이다.

본 장의 모든 시뮬레이션은 Appendix C에 기술된 상세한 flit-level simulator를 사용해 수행되었다. 별도로 명시하지 않는 한, 라우터는 input-queued이며 input speedup은 2이고, virtual-channel flow control을 사용한다. 각 입력 포트마다 8개의 virtual channel이 존재하며, 각 virtual channel에는 8개의 flit buffer가 있어, 입력 포트당 총 64개의 flit이 버퍼링된다. 모든 packet의 길이는 20 flit이다. virtual-channel 할당과 switch 할당은 모두 iSLIP 알고리즘을 사용해 수행된다. 현실적인 파이프라인 구조가 가정되며, 라우터의 hop당 지연(latency)은 3 cycle이다.

25.1 라우팅

이전 장들에서 보았듯이, 라우팅은 낮은 offered traffic에서는 짧은 latency를, 트래픽이 증가함에 따라 높은 saturation throughput을 유지하려는 섬세한 균형을 요한다. 먼저 라우팅 알고리즘이 latency에 미치는 영향을 살펴보고, zero-load latency 및 ideal throughput이라는 간단한 지표와 실제 네트워크 성능 사이의 관계를 분석한다. 흥미롭게도, 라우팅 알고리즘마다 그 이상적 성능에 얼마나 근접하는지가 다르다. 일반적인 평균 latency 지표뿐 아니라, 라우팅 알고리즘에 따라 발생하는 message latency의 분포도 함께 살펴본다. 이어지는 두 번째 실험 세트에서는 라우팅 알고리즘의 throughput에만 초점을 맞추고, 무작위로 생성된 traffic pattern에서 두 알고리즘의 성능을 비교한다.

25.1.1 Latency

이번 실험에서는 8-ary 2-mesh 구조에서 라우팅이 latency에 미치는 영향을 살펴본다. 먼저 interconnection network 연구에서 가장 흔히 사용되는 그래프인, uniform traffic 하에서 offered traffic 대비 latency 그래프부터 시작한다. 그림 25.1은 네 가지 라우팅 알고리즘의 성능을 비교한다: dimension-order routing (DOR), Section 9.2.2와 [135]에서 설명한 randomized minimal 알고리즘 (ROMM), Valiant의 randomized 알고리즘 (VAL), 그리고 minimal-adaptive routing 알고리즘 (MAD). MAD는 Duato의 알고리즘을 기반으로 하며, deadlock-free 하위 기능으로 DOR을 사용해 구현되었다.

낮은 트래픽 상황에서는 zero-load latency가 시뮬레이션 latency를 정확히 예측한다. flit이 채널을 통과하는 데 걸리는 시간을 cycle 단위로 정의하면, 라우터의 지연은 tr=3tr = 3tr=3 cycle이고, packet 길이가 20 flit이므로 serialization latency는 20 cycle이다. 예를 들어, minimal 알고리즘의 zero-load latency는 다음과 같이 계산된다:

T0=tr⋅Havg+Ts=3(163)+20=36 cyclesT_0 = tr \cdot H_{avg} + T_s = 3 \left( \frac{16}{3} \right) + 20 = 36\ \text{cycles}T0​=tr⋅Havg​+Ts​=3(316​)+20=36 cycles

이는 그림에 표시된 값과 같다. 마찬가지로, VAL의 zero-load latency는 52 cycle로 계산된다. 물론 트래픽이 증가하면 contention latency가 지연의 주요 요소가 되고, 각 latency 곡선의 수직 점근선은 각 라우팅 알고리즘의 saturation throughput에 의해 결정된다.

flow control을 정확히 모델링하고 있으므로, 라우팅 알고리즘들은 이상적인 throughput보다 낮은 수준에서 saturation이 발생한다. minimal 알고리즘(DOR, ROMM, MAD)의 경우 이상적으로는 네트워크 용량의 100%까지 수용할 수 있지만, Valiant의 경우 이상적으로는 그보다 낮다.

DOR은 전체 용량의 약 90%에 근접하고, ROMM과 MAD는 약 75%에 도달한다. 이러한 차이는 ROMM과 MAD 알고리즘에서 deadlock을 방지하기 위해 virtual channel을 분할했기 때문이다. DOR은 mesh 구조에서 본래 deadlock-free이기 때문에, 모든 경로가 자유롭게 virtual channel을 사용할 수 있다. 대부분의 분할 구조에서 그러하듯이, 이는 부하 불균형(load imbalance)을 유발할 수 있으며, 그로 인해 ROMM과 MAD 알고리즘의 실제 throughput이 낮아지는 결과를 초래한다. VAL도 역시 deadlock 방지를 위해 자원을 분할해야 하지만, 자연스러운 부하 분산(load balancing) 특성 덕분에 이상적인 값의 약 85%까지 도달할 수 있다.

그림 25.2는 동일한 토폴로지와 네 가지 라우팅 알고리즘에 대해 transpose traffic pattern 하에서 latency 대 offered traffic 곡선을 보여준다. 이 비대칭적인 트래픽 패턴은 부하를 분산하기 어려워 DOR의 성능이 낮으며, 약 35% 용량에서 saturation이 발생한다. ROMM은 약 62%까지 throughput을 끌어올리며 다소 개선된 성능을 보인다. 그러나 MAD는 모든 알고리즘을 능가하며 DOR보다 두 배 이상 높은 throughput을 달성하고 75% 이상의 용량에서 saturation이 발생한다. VAL도 DOR보다는 나은 성능을 보이며 약 43%의 용량까지 도달한다. 이처럼 transpose와 같은 어려운 트래픽 패턴에서의 성능도 중요하지만, neighbor traffic과 같이 쉬운, 지역적인 트래픽 패턴에서의 성능도 중요하다. 그림 25.3은 neighbor traffic 하에서의 결과를 보여준다. 이 경우 minimal 알고리즘들은 모두 동일한 이상적인 throughput을 가지지만, DOR은 그 단순함과 본래의 deadlock-free 특성 덕분에 ROMM과 MAD보다 유리하다. 예상대로 VAL은 앞의 두 트래픽 패턴과 같은 성능을 보인다.

앞의 세 실험에서는 평균 latency를 사용했지만, 개별 packet latency를 살펴보면 특정 시뮬레이션에서 관찰되는 latency 범위와 분포에 대한 통찰을 얻을 수 있다. 예를 들어, 그림 25.4는 uniform traffic 하에서 dimension-order routing을 사용하고 네트워크 용량의 20% offered traffic 하에서 (0,0)에서 (0,3)까지, 그리고 (0,0)에서 (4,4)까지 전송된 packet의 latency 분포를 보여준다. 낮은 부하에서는 거의 contention이 발생하지 않으며, 대부분의 packet은 최소한의 cycle만에 전달되며, 이는 그래프의 왼쪽 끝에 나타나는 큰 스파이크로 표현된다.

(0,0)에서 (4,4)까지의 packet은 hop 수가 많아 latency가 증가한다.

같은 조건에서 Valiant의 라우팅 알고리즘을 사용해 시뮬레이션을 수행하면 보다 흥미로운 분포를 보인다(그림 25.5). 각 packet은 무작위 중간 노드를 경유하기 때문에 path 길이에 다양성이 생긴다. 특정 경로 길이마다 dimension-order routing과 유사한 분포가 생성되며, Valiant 알고리즘의 전체 latency 분포는 이 여러 분포의 가중 합(superposition)으로 형성된다. 예를 들어, (0,0)에서 (0,3)으로의 라우팅에서는 대부분의 packet이 비최소 경로를 따라가므로 종 모양(bell shape)의 분포가 나타난다. (0,0)에서 (4,4)까지의 packet은 source와 destination 간 거리가 더 멀기 때문에 중간 노드가 최소 사분면(minimal quadrant)에 속할 확률이 높아지고, 이 경우 전체 경로가 최소 경로가 되어 분포가 왼쪽으로 이동하는 현상이 발생한다.

25.1.2 Throughput 분포

이제부터는 라우팅 알고리즘의 throughput 성능에만 초점을 맞춘다. interconnection network를 평가할 때 일반적으로 사용하는 표준 트래픽 패턴은 네트워크의 극단적인 상황에서의 성능은 잘 보여주지만, 평균적인 동작 특성을 평가하기에는 적절하지 않을 수 있다. 이러한 제한을 보완하기 위해, 다양한 무작위 permutation traffic pattern에 대해 throughput을 평가할 수 있다.

이 실험에서는 8-ary 2-cube 네트워크에서 dimension-order와 minimal adaptive routing의 throughput을 500개의 무작위 permutation 샘플에 대해 측정하였다. 그 결과는 그림 25.6에 나와 있다. dimension-order routing은 약 27%와 31% 지점에서 두 개의 뚜렷한 피크를 가지며, 전체 평균 throughput은 약 29.4%이다. 반면, minimal adaptive routing은 보다 고르게 분포되며 33% 근처에서 하나의 넓은 피크를 가지며, 평균 throughput은 약 33.3%이다. 이는 dimension-order routing보다 약 13.3% 높은 성능을 나타내며, adaptive routing이 제공하는 잠재적 이점을 보여준다.

virtual channel router를 설계할 때 일반적으로 고정된 양의 하드웨어 리소스를 virtual-channel buffer 구현에 할당한다. 설계자는 이러한 리소스를 어떻게 분할해야 네트워크 성능을 극대화할지를 결정해야 한다. 예를 들어, 깊은 buffer를 가진 적은 수의 virtual channel이 얕은 buffer를 가진 많은 virtual channel보다 더 나은 성능을 제공할 수 있을까?

그림 25.7은 8-ary 2-mesh 네트워크에서 다양한 virtual-channel 분할 방식에 대한 성능을 보여준다. 각 구성에서 virtual channel 수와 각 virtual channel의 깊이를 곱한 전체 buffer 용량은 일정하게 유지된다. 이 실험에서는 몇 가지 경향을 관찰할 수 있다. 첫째, virtual channel 수가 증가함에 따라 throughput이 증가하는 경향이 있다. 그래프에는 나타나지 않았지만, 8개의 virtual channel 구성은 4개 구성보다 약간 더 높은 saturation throughput을 가진다. 둘째, virtual channel 수가 증가하면 saturation 이하에서는 latency가 증가한다. 이는 virtual channel이 많을수록 packet의 interleaving이 심해져서, 네트워크 전체에서 packet이 "늘어나는" 현상이 발생하기 때문이다. 이와 같은 interleaving 효과는 switch allocator가 block되지 않았고 이전 라운드에서 할당을 받은 packet에 우선순위를 부여함으로써 줄일 수 있다. 다만, 패킷 길이가 가변적인 경우 starvation이나 fairness 문제를 피해야 하므로 설계자가 주의해야 한다.

throughput 경향의 예외는 16개의 virtual channel을 사용하는 경우이다. 이 구성의 zero-load latency가 다르다는 점이 근본적인 문제를 나타낸다. router 모델이 pipelining 지연을 포함하고 있기 때문에, buffer의 credit loop latency는 한 cycle보다 크다. 게다가 virtual-channel buffer의 깊이가 이 지연을 감당하지 못할 만큼 작아지면, virtual channel은 100% utilization을 유지하지 못하고 credit을 기다리며 stall 상태에 빠진다. 이는 16.3절에서 설명한 것과 동일한 현상이며, zero-load latency와 saturation throughput 모두에 영향을 준다.

virtual channel의 하드웨어 비용을 전체 buffer 용량으로 근사하는 것이 타당할 수는 있지만, virtual channel 수를 늘린다고 해서 latency 측면에서 항상 무료로 이득을 보는 것은 아니다. 일반적으로 virtual channel 수가 증가하면 virtual-channel 할당 시간이 길어지며, 이는 router의 파이프라인 처리에 영향을 준다. 이로 인해 zero-load latency가 증가하고, virtual channel 재할당에 더 많은 시간이 소요되어 saturation throughput이 약간 감소할 수 있다. 앞서 언급한 credit loop를 고려할 만큼 충분한 깊이가 없는 shallow buffer와 많은 virtual channel 조합은 종종 성능의 한계를 만든다. 그럼에도 불구하고 non-interference와 같은 다른 중요한 고려 사항 덕분에 이러한 극단적인 분할 방식도 여전히 설계에서 매력적인 선택이 될 수 있다.

25.2.2 네트워크 크기 (Network Size)

네트워크 크기는 이상적인 throughput 대비 실제 달성 가능한 throughput 비율에 큰 영향을 줄 수 있다. 그림 25.8은 uniform traffic 조건에서 네 가지 mesh 네트워크의 latency 대 offered traffic 곡선을 보여준다. 각 네트워크는 동일한 채널 크기와 동일한 라우터를 사용하므로, 네트워크의 전체 용량은 radix에 의해 결정된다. 예를 들어, 4-ary 3-mesh와 4-ary 4-mesh의 용량은 4b/k = b이고, 8-ary 2-mesh는 4b/k = b/2로, radix-4 네트워크의 절반 수준이다.

겉보기에는 동일한 라우터로 구성된 다양한 네트워크가 비슷한 수준의 capacity fraction을 달성할 것처럼 보이지만, 실험 결과는 그렇지 않다. 실제로는 capacity fraction이 일정하지 않고, 네트워크의 radix에 따라 결정되는 경향이 있다. radix-4 네트워크는 약 65%에서 saturation이 발생하고, radix-8은 약 80%, radix-16은 약 83%에서 saturation이 발생한다. 추가 실험을 통해, 실제 달성 throughput은 radix에 의해 결정된다는 경향이 확인된다.

이러한 결과는 네트워크 크기와 flow control 간의 상호작용으로 설명할 수 있다. capacity의 비율로 표현하면 네트워크 간 성능 비교가 쉬워지지만, 각 노드에서 실제로 주입되는 절대 throughput은 감춰진다. 앞서 언급한 바와 같이, radix-4 네트워크의 노드는 8-ary 2-mesh보다 2배, 16-ary 2-mesh보다는 4배 더 많은 트래픽을 주입할 수 있다. 시뮬레이션에서 각 노드의 injection process는 동일하지만, 전체 네트워크의 트래픽은 크게 다르다. radix-4 네트워크에서는 적은 수의 노드가 많은 트래픽을 생성하고, 큰 radix 네트워크에서는 더 많은 노드가 적은 양의 트래픽을 생성한다. 이러한 트래픽 특성 차이는 flow control에 큰 영향을 미친다. 소수의 강한 source는 순간적인 load(즉 burstiness)를 많이 발생시키며, 많은 수의 약한 source는 burstiness가 작다. 이 burstiness를 완화하는 것이 flow control의 역할이며, 이 성능은 노드당 buffering 양에 따라 달라진다. 동일한 라우터를 사용하는 상황에서는, 작은 radix 네트워크는 burst 완화 능력이 떨어져 전체 capacity의 더 낮은 비율만 달성할 수 있게 된다.

25.2.3 Injection Process

앞의 실험에서처럼 네트워크 크기가 성능에 영향을 줄 수 있으며, 이때 traffic의 burstiness가 중요하게 작용한다. 본 절에서는 injection process의 burstiness를 직접 조절함으로써 flow control 성능에 미치는 영향을 더 자세히 살펴본다.

burstiness의 가장 단순한 원천은 packet의 크기이다. 평균 주입률이 매우 낮은 경우라도, 주입 단위는 항상 packet이며, 이 packet은 다수의 flit으로 구성될 수 있다. 이는 특정 노드로 향하는 flit의 burst라고 볼 수 있다. 그림 25.9는 packet size가 네트워크 성능에 미치는 영향을 보여준다.

데이터에서 관찰되는 주요 경향은 packet size가 커질수록 latency는 증가하고 throughput은 감소한다는 것이다. 큰 packet은 serialization overhead가 크기 때문에 본질적으로 latency 측면에서 불리하며, 이는 zero-load latency에서도 확인된다. 또한, flow control은 완벽하지 않기 때문에, packet이 커질수록 자원 활용이 어려워진다. 예를 들어, packet size가 40 flit인 경우, 각 라우터의 buffer 깊이가 8 flit이므로 최소 5개의 라우터에 걸쳐 분산된다. 이 packet이 일시적으로 block되면 5개 라우터의 자원이 모두 block되며, 이로 인해 saturation throughput이 감소하게 된다.

이러한 전반적인 경향에서 벗어나는 예외는 packet size가 1인 경우이다 (PS = 1). 본 시뮬레이션의 router 모델은 Section 16.4의 그림 16.7(a)에 제시된 보수적인 virtual channel 재할당 방식을 채택하므로, virtual channel을 재사용하기까지 여러 cycle이 필요하다. packet이 작을수록 이 재할당 시간의 비중이 커지며, 결국 router에서 실질적으로 사용 가능한 virtual channel 수가 감소한다. 추가 시뮬레이션에서는 이 현상이 재할당 시간을 줄이거나 virtual channel 수를 늘렸을 때 사라지는 것이 확인되었다.

또 다른 injection process의 영향은 Section 24.2.2에서 설명한 2-state MMP(Markov Modulated Process)를 사용한 mesh network로부터 탐색할 수 있다. 이 실험에서도 packet 크기는 20 flit로 고정되며, 그림 25.10은 여러 MMP 파라미터 값에 따른 성능을 보여준다. 각 MMP는 두 개의 파라미터 α와 β를 가지며, burst의 간격과 지속 시간을 조절한다. 1/α는 burst 사이의 평균 간격을 의미하며, 각각의 곡선은 1, 200, 400 cycle의 평균 간격을 가진다. β는 평균 burst 지속 시간의 역수로 해석할 수 있으므로, 첫 번째 곡선은 무한 burst 지속 시간, 두 번째와 세 번째 곡선은 각각 100, 50 cycle의 평균 지속 시간을 가진다.

첫 번째 MMP는 무한 burst 지속 시간을 가지므로 항상 on 상태에 있으며, 결국 Bernoulli injection process와 동일하다. 따라서 이 MMP의 α 파라미터는 steady state에 영향을 미치지 않는다. Section 24.2.2의 분석에 따르면, burst 기간 중의 injection rate는 평균 injection rate의 1 + β/α 배이다. β/α 비율이 클수록 burst의 강도가 높아진다.

Figure 25.10은 여러 MMP 조건에서 8-ary 2-mesh 네트워크의 latency 대 offered traffic 곡선을 보여준다. 세 번째 MMP에서는 β/α = 0.02 / 0.0025 = 8이므로 burst 기간 동안의 주입률은 평균보다 9배 높다. 예를 들어, 전체 offered load가 40%일 경우, burst 구간에서는 주입률이 120%까지 치솟고, 평상시에는 packet이 주입되지 않는다. 이러한 bursty한 행동은 평균 latency를 증가시키고 saturation throughput을 감소시키는 결과를 낳는다.

25.2.4 Prioritization

대부분의 네트워크 latency 평가는 message의 평균 latency에 초점을 맞추지만, flow control 방식에 따라 개별 message의 latency 분포는 크게 달라질 수 있다. 이런 분포를 제어하는 것은 최악 지연(worst-case delay)과 지터(jitter)에 민감한 애플리케이션, 공정성(fairness), 또는 메시지 우선순위가 존재하는 네트워크에서 매우 중요하다.

예를 들어, 하나의 네트워크에 두 개의 메시지 클래스가 있다고 하자. 하나는 낮은 지연과 지터가 요구되는 실시간 영상 트래픽이고, 다른 하나는 지연 허용이 가능한 데이터 전송일 수 있다. 이 경우 실시간 트래픽의 요구 조건을 만족시키기 위해 높은 우선순위를 부여한다.

Figure 25.11은 2-ary 6-fly 네트워크에서 두 개의 우선순위 클래스를 적용한 실험 결과다. 여기서 전체 트래픽의 10%는 high-priority, 나머지 90%는 low-priority이며, 네트워크는 saturation 부근에서 동작한다. 라우터 모델에는 Section 19.3의 separable allocator가 사용되며, prioritized arbiter는 가장 높은 우선순위를 가진 요청자를 선택하고, 동률일 경우 round-robin으로 결정한다.

결과적으로 high-priority 메시지의 약 71%가 네트워크의 최소 지연인 37 cycle에 전달되며, 99%는 70 cycle 이내에 전달된다. 반면 low-priority 트래픽은 평균 latency가 높고, 98%는 300 cycle 이내에 도착하지만, tail은 700 cycle 이상까지 이어진다.

이러한 차별화 수준은 high-priority 트래픽이 전체 트래픽의 소수(10% 미만)인 경우에만 가능하다. high-priority 트래픽이 증가하면 그 효과는 줄어들며, 전체 트래픽이 대부분 high-priority로 채워지면 우선순위 부여의 이점은 거의 사라진다.

또 하나의 중요한 방식은 Section 15.4.1에서 설명한 age-based fairness이다. 이 방식에서도 prioritized allocator를 사용하는데, 이번에는 요청자 중 가장 오래된 packet에게 우선권을 부여한다. packet의 age는 네트워크에 주입된 이후 경과한 cycle 수로 측정된다.

Figure 25.12는 age-based arbitration을 사용한 경우와 사용하지 않은 경우의 latency 분포를 비교한 것이다. age-based arbitration이 없을 경우 일부 packet은 600 cycle 이상 걸리며 tail이 길어지지만, 있을 경우 tail이 짧아지고 대부분 packet이 400 cycle 이내에 도착한다. 다만, 평균 latency는 약간 증가할 수 있다.

25.2.5 Stability

네트워크가 saturation 부근 또는 그 이상에서 동작하게 되면, 설계자는 latency보다는 flow control의 **공정성(fairness)**에 더 관심을 갖게 된다. saturation 상태에서 channel이 공정하게 분배되지 않으면, 일부 flow는 starvation에 빠지고 throughput이 급감하면서 네트워크가 **불안정(unstable)**해질 수 있다.

Figure 25.13은 불안정한 네트워크와, 공정성을 확보한 두 가지 flow control 방식의 throughput을 보여준다. greedy한 flow가 starved flow를 가리는 것을 방지하기 위해, minimum throughput을 기준으로 측정하였다.

세 가지 방식 모두 saturation 이전까지는 유사한 성능을 보이며, 대략 네트워크 capacity의 43%에서 saturation이 발생한다. 그러나 그 이후에는 결과가 크게 달라진다. 아무런 fairness 메커니즘이 없을 경우 throughput은 급격히 떨어져 5% 미만으로 감소한다. 이는 Section 15.4.1의 parking lot 예제와 유사한 상황으로, 적은 hop 수로 경로를 통과하는 packet이 리소스를 더 많이 점유하게 된다.

반면 age-based arbitration을 도입하면 saturation 이후에도 매우 안정적인 throughput을 유지한다. 또한, 목적지마다 별도의 virtual channel을 사용하는 non-interfering 네트워크도 안정적이지만, saturation 이전에 throughput이 소폭 감소하며 약 35%에서 안정화된다.

25.3 Fault Tolerance

많은 interconnection network에서는 고장(fault)이 발생했을 때도 네트워크가 계속 동작할 수 있어야 하며, 이러한 고장이 발생하더라도 성능이 완만하게 감소하는 graceful degradation 특성이 중요하다. Figure 25.14는 graceful degradation의 예시이다.

이 실험에서는 8-ary 2-mesh 네트워크에서 다양한 수의 링크 고장이 발생하는 경우를 시뮬레이션하며, Section 14.8의 fault-tolerant planar-adaptive routing을 사용한다. 각 고장 수에 대해, uniform traffic 조건 하에서의 saturation throughput을 측정하였다.

고장 링크의 배치 방식에 따라 결과가 달라질 수 있기 때문에, throughput은 각 고장 수마다 30개의 고장 조합 평균으로 구해졌으며, 표준편차도 함께 그래프에 표시되었다. 실험 단순화를 위해 고장 영역이 convex가 되도록 링크를 배치했으며, 이 조건 하에서는 모든 노드가 planar-adaptive routing을 통해 연결된 상태로 유지된다.

Figure 25.14는 uniform traffic 하에서 fault-tolerant planar-adaptive routing을 사용하는 8-ary 2-mesh 네트워크에서, 실패한 링크 수에 따른 saturation throughput을 보여준다. 각 점은 임의로 고른 링크 고장 샘플 30개에 대한 평균 throughput을 나타내며, 수직 에러 바는 표준편차를 나타낸다. 에러 바의 상단과 하단은 각각 평균값에 표준편차를 더한 값과 뺀 값을 의미한다.

링크 고장이 없는 정상적인 네트워크의 throughput은 capacity의 약 60%를 약간 상회하며, 소수의 고장이 발생했을 때 throughput이 소폭 감소하는 것으로 보아 네트워크는 여전히 견고함(grace)을 유지한다. 고장 수가 12개로 증가해도 throughput 감소율은 크게 증가하지 않아, 네트워크가 비교적 높은 탄력성(resilience)을 유지함을 알 수 있다. 동시에 표준편차는 고장 수가 많아질수록 점차 증가하는데, 이는 단일 고장보다 고장들이 모여 있을 때 잠재적으로 더 큰 영향을 미칠 수 있음을 나타낸다.

예를 들어, 네트워크의 특정 소영역에 많은 고장이 집중되면 해당 영역에 접근할 수 있는 채널 수가 줄어들어, 남은 채널에 과도한 부하가 집중될 수 있다. 고장 수가 많아질수록 이런 고장 클러스터가 어떤 노드를 거의 고립시키는 경우가 발생할 확률도 증가하며, 극단적인 경우 특정 노드 쌍 사이에 경로가 아예 존재하지 않는 partitioned 상태에 이를 수도 있다.

23장에서 다룬 queueing theory와 probabilistic analysis 기법은 네트워크의 여러 측면을 모델링할 수 있다. 그러나 어떤 상황은 이러한 모델로 표현하기에는 너무 복잡하다. 이런 경우 simulation은 매우 유용한 도구가 된다. 하지만 simulation은 양날의 검으로, 복잡한 네트워크 설계를 훌륭하게 모델링할 수 있지만, 시뮬레이터 자체와 simulation 역시 복잡하다. 따라서 simulation 결과의 품질은 이러한 결과를 생성하고 측정하는 데 사용된 방법론의 품질에 달려 있다.

이 장에서는 simulation의 입력, 측정 및 설계의 기본 개념을 다룬다. 모든 네트워크 시뮬레이터가 router microarchitecture의 세부 사항까지 모델링할 필요는 없으며, 우선 네트워크 설계자가 선택할 수 있는 다양한 simulation 세부 수준에 대해 논의한다. 적절한 모델링 정확도를 선택하는 것만큼 중요한 것이 simulation에 사용할 workload를 선택하는 일이다. workload를 생성하기 위한 application-driven 방식과 synthetic 방식 모두를 다룬다. simulation의 입력과 모델이 정의된 후에는 네트워크의 성능을 측정해야 한다. 네트워크를 측정하고 그 측정값의 정확도를 평가하기 위한 여러 통계적 접근법을 소개한다. 마지막으로 시뮬레이터 설계의 기본을 소개하고, 네트워크 시뮬레이터에 특화된 몇 가지 이슈를 설명한다.

24.1 세부 수준(Levels of Detail)

네트워크 simulation을 시작하기 전에 설계자는 simulation에 적합한 세부 수준을 선택해야 한다. 매우 정확한 시뮬레이터를 사용하는 것이 항상 안전하긴 하다. 모델링 오류를 피할 수 있기 때문이다. 하지만 이는 시뮬레이터를 작성하고 실행하는 데 시간이 많이 걸린다는 단점이 있다. 보다 합리적이고 효율적인 접근은 설계자가 중요하다고 생각하는 네트워크 동작은 포함하고 불필요한 세부 사항은 제외하는 simulation 수준을 선택하는 것이다.

Figure 24.1은 네트워크 simulation의 전형적인 세부 수준 범위를 보여준다. 가장 단순한 interface level은 네트워크 인터페이스의 기능과 단순한 패킷 전달만 제공한다. 이 수준은 behavioral simulation이라고도 불린다. behavioral simulation은 설계 초기 단계에서 가장 유용하며, coherence protocol과 같이 네트워크를 사용하는 설계 요소를 테스트할 때 사용된다. 최종 네트워크 구현의 세부 사항이 정해지지 않았더라도 interface level은 여전히 네트워크의 일반적인 동작을 제공할 수 있다.

capacity level은 behavioral simulation과 매우 정밀한 네트워크 모델 사이의 중간 수준이다. 이 수준에서는 채널 bandwidth, 버퍼 크기, injection/ejection rate 등 네트워크의 기본 제약을 설정한다. 이러한 제약을 설정한 상태에서 초기 성능을 평가할 수 있으며, 시뮬레이터는 여전히 간단하여 초기 결과에 따라 빠르게 수정할 수 있다.

마지막으로 microarchitectural detail은 flit level에서 반영된다. 이 수준에서는 개별 flit을 모델링하며, 이를 위해 buffering, switching, arbitration을 위한 구조를 도입해야 한다. 이러한 구조가 정확히 모델링된다는 가정 하에, 이 수준에서의 성능 정보는 매우 정확할 수 있으며 일반적으로 flit time 또는 router cycle 단위로 표현된다. hardware level로 이동하면, flit time 대신 물리적 설계의 timing 정보가 사용되며, router microarchitecture의 implementation cost/area 정보도 제공된다.

24.2 네트워크 Workload

network workload란 시간에 따라 네트워크 터미널에 가해지는 traffic 패턴(예: packet)을 의미한다. workload를 이해하고 모델링함으로써 topology 및 routing function을 설계하고 평가할 수 있다. 가장 현실적인 traffic 패턴은 네트워크를 실제로 사용하는 클라이언트가 생성한 application-driven workload이다. 예를 들어, shared-memory interconnect에서는 다양한 처리 노드 간에 주고받는 coherence message가 네트워크 traffic을 구성한다. 네트워크뿐만 아니라 그 위에서 실행되는 application도 모델링하면, 해당 application에서 요구하는 정확한 workload를 얻을 수 있다. application-driven workload는 네트워크를 가장 정확히 모델링할 수 있지만, 이를 통해 기대되는 traffic의 전체 범위를 포괄하기는 어렵다. shared-memory 예제에서 보듯, workload는 application에 직접 연결되어 있어 workload를 확장하려면 새로운 application을 생성해야 하며, 이는 일반적으로 매우 비용이 많이 든다. 반면, 잘 설계된 synthetic workload는 interconnection network가 요구하는 특성을 포착하면서도 훨씬 유연하다.

24.2.1 Application-Driven Workloads

이상적으로는 interconnection network의 성능은 application-driven workload 하에서 측정되어야 한다. 즉, 네트워크에 적용되는 message의 순서가 네트워크의 예상 사용 application에서 직접 생성되는 것이다. 이러한 workload를 생성하는 한 가지 방법은 네트워크뿐 아니라 그 클라이언트도 함께 시뮬레이션하는 것이다. 예를 들어, processor-memory interconnect를 시뮬레이션할 경우 processor와 memory module에 대한 모델이 모두 필요하다. 그런 다음, 해당 처리 요소에서 application을 실행해 interconnection network의 성능을 평가한다. application이 생성하는 memory 및 processor 간의 message가 네트워크 traffic이 된다. 이러한 방식은 “full-system” simulation 또는 execution-driven workload라고 불린다. execution-driven workload는 확실히 정확하지만 한 가지 단점은 네트워크로부터의 피드백이 workload에 영향을 준다는 점이다. 이로 인해 설계자가 interconnection network 내 병목을 분리해서 분석하기가 어려워질 수 있다. 네트워크 설계 변경은 네트워크뿐만 아니라 workload에도 영향을 줄 수 있기 때문이다.

네트워크와 클라이언트를 동시에 모델링하는 대신, 네트워크 application에서 생성된 message의 시퀀스를 수집하고 이후 이 시퀀스를 "재생"하는 방식도 있다. 이를 trace-driven workload라고 하며, 실제 시스템이나 위에서 언급한 execution-driven simulation으로부터 수집될 수 있다. 예를 들어, IP router application에서는 일정 시간 동안 packet arrival의 시퀀스(또는 trace)를 기록할 수 있다. 각 도착에 대해 시간, 길이, 목적지를 저장한 후, 이 시퀀스를 네트워크 시뮬레이션에서 그대로 재현한다. execution-driven simulation으로부터 수집한 trace는 낮은 수준의 detail만을 제공하는 빠른 simulation에서 얻을 수도 있다. 이 trace는 이후 네트워크만을 자세히 시뮬레이션하는 데 재사용될 수 있다. trace가 사전에 수집되었기 때문에 네트워크로부터의 피드백은 workload에 영향을 주지 않는다. 이는 정확도를 떨어뜨릴 수 있지만, 어떤 application에서는 그 영향이 크지 않을 수도 있다. 예를 들어, IP router의 경우 피드백은 오랜 시간에 걸쳐 workload에 영향을 주므로 큰 문제가 되지 않는다.

24.2.2 Synthetic Workloads

Bernoulli injection process

Bernoulli process는 simulation에서 가장 흔히 사용되는 injection process 중 하나다. 이 process에서는 각 cycle마다 일정 확률 r로 packet을 inject한다. 즉, 매 cycle마다 동전 던지기를 해서 확률 r로 1이 나오면 packet을 inject하는 방식이다. Figure 24.2(b)에서처럼 packet injection은 기하급수적으로 분포된 간격을 가진다.

Bernoulli process는 injection에 randomness를 포함하지만, 내부에 상태(state)가 없기 때문에 시간에 따라 변하거나 상관관계를 가지는 traffic을 모델링할 수 없다. 실제로 많은 traffic source는 시간에 따라 변한다. 예를 들어 인터넷 traffic은 주간에는 사용량이 많고 야간에는 적은 diurnal 특성을 보인다. Bernoulli process는 느리게 변하는 short-term traffic을 모델링하기에는 적절하지만, 작고 빠른 시간 단위로 급격히 변하는 traffic을 충분히 표현하지는 못한다.

이렇게 급격히 변하는 injection process는 보통 bursty하다고 표현된다. voice connection, video stream, HTTP traffic과 같은 다양한 source의 burstiness를 포착하기 위해 여러 모델이 제안되었다. 그중 하나는 Markov modulated process (MMP)다. MMP에서는 Bernoulli injection rate이 Markov chain의 현재 상태에 따라 조절된다.

Figure 24.3은 2-state MMP를 보여준다. "on"과 "off" 상태가 있으며, 각각의 injection rate는 r₁과 0이다. 매 cycle마다 off에서 on으로 전이될 확률은 α이고, on에서 off로 전이될 확률은 β이다. 이 모델은 burst 구간 동안에는 rate r₁로 injection이 발생하고, burst 외에는 조용한 injection을 표현한다. burst의 평균 길이는 1/β이고, burst 사이의 평균 시간은 1/α이다.

이 시스템의 injection rate는 다음과 같이 steady-state 확률로 구한다. x₀는 off 상태의 확률, x₁은 on 상태의 확률일 때:

 αx₀ = βx₁
 x₀ + x₁ = 1

따라서 steady-state에서 on 상태일 확률은:

 x₁ = α / (α + β)

결과적으로 전체 injection rate는 다음과 같다:

 r = r₁ × x₁ = αr₁ / (α + β)

복잡한 MMP 모델은 Exercise 24.1에서 다룬다.

패킷 길이 (Packet Lengths)

traffic pattern에 대한 기본 내용은 3.2절에서 다루었고, 이제는 packet 길이를 정하는 문제가 남았다. 한 가지 간단한 방법은 application-driven workload에서 수집한 packet length 분포를 사용하는 것이다. Figure 24.4는 IP router에서 수집한 예시를 보여준다. 각 packet은 이 분포의 확률에 따라 길이가 결정된다.

24.3 Simulation Measurements

네트워크 성능을 추정할 때 주요 오차는 두 가지가 있다: systematic error와 sampling error. systematic error는 측정 자체 또는 simulation 과정에서의 bias로 인해 발생하며, 일반적으로 시뮬레이터의 초기화 과정에서 발생한다. Section 24.3.1에서 설명하듯이 simulation의 warm-up 기간을 적절히 설정하면 systematic error의 영향을 줄일 수 있다.

simulation이 warm-up을 마치면 네트워크는 steady state에 도달한 것으로 간주된다. 즉, 네트워크의 통계적 특성이 시간에 따라 더 이상 변하지 않는다. 이 시점부터는 네트워크를 샘플링하여 성능 파라미터를 정확히 추정하는 것이 중요하다. Section 24.3.2에서는 대표적인 샘플링 기법인 batch means와 replication 방법을 다룬다. 이를 confidence interval (24.3.3절)과 함께 사용하면 네트워크 파라미터를 측정하고 그 정확도를 통계적으로 검증할 수 있다.

24.3.1 Simulator Warm-Up

대부분의 시뮬레이터는 초기 상태에서 buffer는 비어 있고, 리소스는 idle 상태로 시작된다. 이러한 초기화는 구현이 간단하지만, simulation 측정에 systematic error를 유발한다. 예를 들어, simulation 초기의 packet은 거의 빈 네트워크를 지나므로 contention이 적고 latency도 낮다. 하지만 시간이 지나 buffer가 채워지면 이후에 inject되는 packet은 더 많은 contention을 겪게 되며, latency가 증가한다. 시간이 지나면 이러한 초기화의 영향은 점점 작아지고, 이 시점이 warm-up 완료 시점이다. warm-up 이전의 event를 무시하면 systematic error의 영향을 줄일 수 있다.

warm-up 기간을 정확히 판단할 수 있는 일반적인 방법은 존재하지 않지만, 대부분은 다음 절차를 따른다:

1. 휴리스틱 기반으로 초기 warm-up 기간 Twu 설정
2. 추정된 warm-up 기간 동안의 샘플은 무시하고 통계 수집
3. 남은 샘플이 stationary한지 검증. 그렇다면 Twu를 warm-up 기간으로 확정. 아니라면 Twu를 증가시키고 2~3 반복

위 절차의 세부 방식에 대한 여러 복잡한 기법이 있지만, 여기서는 실제로 잘 동작하는 간단한 방법을 설명한다. 먼저, 초기 warm-up 기간은 빠르게 simulation 가능한 100~1000 event 수준으로 설정한다. 이는 steady state에 빨리 도달하는 simulation의 경우 추정 오버헤드를 줄여준다.

simulation을 실행하면서 warm-up 기간 이후의 통계만 수집한다. 여기서는 평균 packet latency를 추정하는 예로, event를 batch 단위로 나눠 평균을 계산한다. 각 sample point는 다수의 packet latency 평균으로 구성된다. batch size는 통계적으로 의미 있는 수치인 30~50 이상이 적절하며, 여기서는 batch size를 100으로 한다. 즉, 첫 sample은 최초 100개의 packet, 두 번째 sample은 그 다음 100개, 이런 식이다.

warm-up 이후의 샘플에 대해 선형 회귀(linear fit)를 수행한다. 회귀선이 일정 precision 내에서 flat하다면 steady state로 간주하고, 아니라면 warm-up 기간을 늘려 절차를 반복한다.

Figure 24.5는 mesh 네트워크에서 packet latency가 시간에 따라 어떻게 변화하는지를 보여준다. batch size가 100임에도 단일 simulation에서는 약 6000개의 packet이 도착할 때까지 steady하게 보이지 않는다. 이는 샘플링 자체가 random process이기 때문으로, 자연스럽게 sampling error가 발생한다. 이 error는 여러 독립적인 simulation 결과를 평균내는 ensemble average 방식으로 크게 줄일 수 있다. Figure 24.5에서는 10개의 독립 simulation run의 ensemble average가 사용되었으며, 약 4000 sample 이후부터 안정화된 모습이다.

warm-up 기간은 단일 run으로도 추정 가능하지만, 여러 run을 평균 내면 underestimation 위험을 줄일 수 있다. 단, simulation 시간이 더 오래 걸린다는 단점이 있다. 일반적으로 20~30개 이상의 독립 run을 사용하는 것은 큰 의미가 없다.

24.3.2 Steady-State Sampling

적절한 warm-up 기간 이후 simulation이 steady state에 도달하면, 다음 단계는 이 상태에서 네트워크를 측정하는 것이다. 여기에서는 대표적인 두 가지 측정 방식인 batch means method와 replication method를 소개한다. 두 방식 모두 네트워크 시뮬레이터에서 널리 쓰이는 기법이다.

Batch Means Method

batch means method에서는 긴 simulation run 하나로부터 측정값을 수집한다. warm-up 기간을 정할 때처럼 샘플들을 여러 batch로 나눈 뒤, 각 batch에 대한 통계를 누적하여 계산한다. 단, warm-up 때와 달리 batch size는 전체 simulation 길이에 따라 정해지며 보통 총 20~30개의 batch가 되도록 한다. 관측값 집합 {X₀, X₁, ..., Xₙ₋₁}이 주어지면, k개의 batch로 나누기 위해 batch size s를 설정하여 n = s × k가 되도록 한다. 각 batch의 평균은 다음과 같이 계산한다:

 B̄ᵢ = (1/s) × ∑(j=0 to s−1) Xₛᵢ₊ⱼ, 0 ≤ i < k

전체 sample 평균은 각 batch 평균의 평균이다:

 B̄ = (1/k) × ∑(i=0 to k−1) B̄ᵢ

이때 전체 평균 B̄는 원래 샘플들의 평균과 동일하므로, batching 자체의 유용성이 의문일 수 있다. 하지만 다음 절에서 보듯이, 측정된 평균의 신뢰도를 평가하는 데 필요한 표준편차 추정에는 의미가 있다. batch 평균 간의 분산은 다음과 같이 계산된다:

 σ²_S = (1/(k−1)) × ∑(i=0 to k−1) (B̄ − B̄ᵢ)²

각 batch 평균은 여러 샘플의 평균이므로, 원래 샘플 간의 분산보다 훨씬 작고 이에 따라 표준편차도 작아져 평균에 대한 신뢰도가 높아진다.

다만, 이 방식의 주요 단점은 통계적 독립성 부족이다. 각 batch가 서로 독립적이어야 측정값 B̄이 바이어스 없이 정확하지만, 실제로는 이전 batch의 packet들이 네트워크 내에 남아 있기 때문에 batch 간 상관관계가 존재한다. 이를 줄이기 위해 batch는 최대한 크게 잡으며, 이 때문에 총 batch 수를 20~30개 정도로 제한한다.

Replication Method

replication method는 batch 간 상관관계 문제를 해결하기 위해 여러 개의 독립적인 simulation run에서 데이터를 수집한다. 긴 run 하나 대신 여러 개의 짧은 run을 사용하며, 일반적으로 30개 이상 run을 수행해도 정확도 향상에는 큰 효과가 없다. 오히려 각 run의 길이를 충분히 길게 설정하는 것이 더 중요하다. 각 run은 최소 수백 개의 샘플을 포함해야 정규 분포를 따르는 통계적 안정성을 확보할 수 있다.

k번째 run의 관측값 {X₀^(k), ..., Xₙ₋₁^(k)}에서 평균을 구하면:

 R̄ₖ = (1/n) × ∑(i=0 to n−1) Xᵢ^(k)

여러 run의 평균값은 다음과 같다:

 R̄ = (1/r) × ∑(k=0 to r−1) R̄ₖ

이 평균값들의 표준편차는 다음과 같이 계산된다:

 σ²_S = (1/(r−1)) × ∑(k=0 to r−1) (R̄ − R̄ₖ)²

replication method는 sample 간 상관관계를 제거해 주지만, 초기화에 따른 systematic error에 더 민감하다. run이 여러 번 수행되므로 각 run마다 initialization이 반복되고, 이로 인해 초기화 영향이 누적될 수 있다. 따라서 warm-up 기간 동안 버린 샘플 수의 5~10배 정도의 샘플을 각 run에서 수집하는 것이 바람직하다.

24.3.3 Confidence Intervals

simulation 데이터를 수집한 후에는 이 데이터가 얼마나 정확히 실제 process를 대표하는지를 판단해야 한다. confidence interval은 이 질문에 정량적으로 답할 수 있게 해 주는 통계적 도구다. 특정 샘플 집합에 대해, confidence interval은 일정한 확률로 진짜 평균이 포함되는 값의 범위를 제공한다.

confidence interval을 계산하려면 측정하려는 대상이 stationary하고 정규 분포를 따른다고 가정한다. 앞서 warm-up 절차에서 stationary 조건은 만족시켰고, 정규 분포에 대해서는 중심극한정리에 따라 충분한 샘플 수(수백~수천)가 있으면 대체로 만족한다고 간주한다.

샘플 집합 {X₀, ..., Xₙ₋₁}에 대한 평균은 다음과 같다:

 X̄ = (1/n) × ∑(i=0 to n−1) Xᵢ

confidence level이 100(1 − δ)%일 때, 실제 평균 X̃은 다음 범위에 포함될 확률이 100(1 − δ)%이다:

 X̄ − (σ_S × tₙ₋₁,δ⁄₂ / √n) ≤ X̃ ≤ X̄ + (σ_S × tₙ₋₁,δ⁄₂ / √n)

여기서 오차 항은 √n에 반비례하고, 샘플의 표준편차 σ_S 및 t-분포 값 tₙ₋₁,δ⁄₂에 비례한다. σ_S는 다음과 같이 계산된다:

 σ²_S = (1/(n−1)) × ∑(i=0 to n−1) (X̄ − Xᵢ)²

또는 앞서 24.3.2절에서 제시한 batch 또는 replication 방법을 통해 계산할 수 있다.

오차 항에 포함된 tₙ₋₁,δ⁄₂는 Student’s t-distribution에서 구하며, 샘플 수 n에 따라 달라진다. 이는 자유도(degrees of freedom)가 n−1이고 신뢰수준이 δ/2일 때의 값을 의미한다. Table 24.1은 95% 및 99% 신뢰구간에 대한 대표적인 t 값들을 보여준다.

Figure 24.6 설명

Figure 24.6은 batch means method를 이용해 얻은 평균 latency에 대한 95% confidence interval을 packet arrival 수에 따라 나타낸 것이다. 각 confidence interval은 해당 시점까지의 데이터를 30개의 batch로 나눈 결과이며, 시뮬레이션은 5000개의 packet warm-up 이후부터 시작된다. n⁻¹⁄² 형태의 수렴 패턴을 보이며, 네트워크가 포화 상태에 가까워 느린 수렴 속도를 나타낸다. 약 30만개의 arrival 이후에는 평균 latency의 약 5% 범위로 confidence interval이 좁혀지고, 백만개의 arrival 이후에는 2.5% 이내로 좁혀진다. 초반의 confidence interval은 최종 평균 latency를 포함하지 않는 경우도 있는데, 이는 batch 간 상관관계가 오차에 영향을 미쳤음을 보여준다.

24.4 Simulator Design

이 책의 범위를 넘는 일반적인 discrete-event simulator 설계에 대한 논의를 제외하더라도, 네트워크 시뮬레이터 설계자나 사용자라면 반드시 이해해야 할 기본 영역들이 있다. 다음 절에서는 두 가지 기본 접근 방식을 간단히 소개한다.

시뮬레이터 설계와 관련된 일반적인 개념은 이 책의 범위를 넘어서지만, 네트워크 시뮬레이터를 설계하거나 사용할 사람이라면 반드시 이해해야 할 몇 가지 기본 영역이 있다. 우선, 시뮬레이터 설계에서 가장 기본적인 두 가지 방식인 cycle-based simulation과 event-driven simulation을 간단히 설명한다. 그다음, 네트워크 시뮬레이션에서 중요한 한 가지 이슈인 injection process와 네트워크 간의 decouple을 위한 무한 source queue 모델링을 다룬다. 이어서, injection process를 모델링하기 위해 필수적인 난수(random number) 생성의 핵심 이슈들을 설명하고, 마지막으로 시뮬레이터에서 예상치 못한 동작이 발생했을 때 설계자가 고려해야 할 실질적인 조언을 제공한다.

24.4.1 Simulation Approaches

네트워크 시뮬레이터를 설계하는 데 있어 두 가지 대표적인 접근 방식이 있다: cycle-based simulation과 event-driven simulation. 이 두 방식의 차이를 설명하기 위해, 간단한 output-queued router 노드를 예로 들어 설명한다. 이 노드는 packet이 도착하면 즉시 해당 output port에 해당하는 output queue로 전달된다. output queue는 모든 input port로부터 동시에 packet을 수신할 수 있을 만큼의 write bandwidth를 가진다. 간단하게 하기 위해, 이 노드의 전체 지연 시간은 simulator cycle 하나로 가정하고, 버퍼는 무한대로 설정한다.

cycle-based simulation에서는 시간의 흐름이 두 개의 단계(phase)로 나뉜다. 일반적으로 첫 번째 phase는 global state를 읽는 작업, 두 번째 phase는 해당 상태를 쓰는 작업과 관련된다. 시뮬레이션을 이러한 read/write 단계로 나누면, global state를 읽는 함수들이 쓰기 전에 항상 먼저 실행될 수 있다.

예를 들어 Figure 24.7의 shared-memory switch를 cycle-based simulation으로 모델링한 경우, 각 simulation cycle의 시작에서 packet이 각 노드에 도착하고 첫 번째 phase가 실행된다. 이 phase에서는 ReadInputs 같은 global state를 읽는 함수들이 실행된다. ReadInputs 함수는 각 input port로 도착한 packet을 적절한 queue에 저장하는 역할을 한다.

두 번째 phase에서는 global state를 쓰는 함수들이 실행된다. 여기서는 WriteOutputs 함수가 해당 역할을 하며, 각 output에 대해 적절한 packet을 선택하고, 다음 노드의 input으로 전달한다. 이 과정은 다음 cycle의 ReadInputs에서 읽힐 수 있도록 처리된다. 이러한 두 단계의 절차는 시뮬레이션이 끝날 때까지 반복된다. 각 phase 내의 모든 함수들은 실행 순서에 관계없이 동일한 결과를 내야 한다는 것이 중요하며, 이는 Exercise 24.6에서 더 자세히 다룬다.

event-driven simulation은 cycle-based simulation과는 달리 global clock에 묶이지 않기 때문에 모델링에서 훨씬 더 유연하다. 특히 비동기 시스템을 시뮬레이션할 때 유리하다. event-driven 시뮬레이션은 매우 단순한 구조로 구성되며, 각각의 event는 세 가지 필드(시점, 동작, 데이터)를 가진다. 시뮬레이션은 이들 event를 실행 시간 기준으로 정렬한 event queue로부터 event를 꺼내어 처리하는 방식으로 진행된다.

Figure 24.8은 cycle-based simulation에서 사용했던 것과 같은 output-queued switch 설계를 event-driven simulation으로 작성한 코드 예시이다. 시뮬레이션은 특정 노드에서 packet이 도착하는 Arrival event로 시작된다. 도착한 packet은 해당 output port에 맞는 queue에 저장되며, 동시에 output scheduling을 위한 event가 필요하다. 이를 위해 queue에 처음 도착한 packet이 ScheduleOutput event를 생성하도록 구현되어 있으며, 이는 중복 event 생성을 방지하고 항상 non-empty queue에 대해 scheduling이 보장되도록 한다.

AddEvent 함수는 새로운 event를 event queue에 추가한다. 첫 번째 인자는 현재 시간으로부터 얼마나 뒤에 event를 실행할지 나타내며, 이 예시에서는 1 cycle 뒤로 설정되어 있다. ScheduleOutput 동작은 output queue에서 packet을 선택하고 이를 다음 노드로 전달하는 Arrival event를 생성하는 역할을 한다. 또한, output queue에 packet이 더 남아 있으면 2 cycle 뒤에 또 하나의 ScheduleOutput event를 예약한다. 이렇게 함으로써, arrival과 output scheduling을 교대로 수행하며, 이는 cycle-based 방식에서의 두 phase 접근법과 유사하다. 같은 시간에 실행될 event는 실행 순서와 관계없이 동일한 결과를 보장해야 한다.

event-driven simulation은 cycle-based 시뮬레이션의 단순한 두 단계 루프와 달리, 어떤 event를 실행할지 결정하기 위해 정렬된 event list를 유지해야 한다. 이 list에 효율적으로 삽입하고 삭제하려면 적절한 자료구조가 필요하다. 일반적으로 binary heap을 사용하면 O(log n)의 복잡도로 event 삽입과 삭제가 가능하다. 하지만 event-driven 시뮬레이터에 특화된 자료구조를 사용하면 더 나은 성능을 얻을 수 있다. 예를 들어, calendar queue는 O(1)의 복잡도로 event 삽입과 삭제가 가능하다.

24.4.2 Modeling Source Queues

23.1절에서 설명했듯이, interconnection network의 open-loop 측정 방식에서는 각 injection process를 네트워크와 분리하기 위해 무한 queue를 사용한다. 이 queue를 통해 injection process를 독립적으로 제어할 수 있지만, 포화 상태 이상에서 시뮬레이션을 수행할 경우에는 몇 가지 실질적인 문제가 생긴다. 이 경우 source queue의 크기는 제한 없이 증가하고, simulation 길이에 비례하여 packet이 저장된다. 시뮬레이터가 이 queue에 있는 모든 packet에 대해 메모리를 할당한다면, 시뮬레이션의 메모리 사용량도 제한 없이 증가하게 된다. 더 나아가 input queue를 compact하게 표현하려고 해도, 일부 flow control 방식에서는 queue 내 각 packet의 정확한 age 정보를 추적해야 하기 때문에 어려움이 있다.

가장 단순한 구현에서는 injection process가 네트워크와 동기화된 방식으로 수행된다. 매 simulation cycle마다 injection process는 해당 source queue에 새 packet을 추가할 수 있다. 하지만 실제로는 각 source queue의 맨 앞 packet만 네트워크에 영향을 주며, 나머지 packet은 당장은 시뮬레이션에 영향을 미치지 않는다. 이 점을 활용하면, source queue 전체를 명시적으로 저장하지 않고도 효율적으로 모델링할 수 있다. 즉, 각 injection process는 네트워크보다 시간상 뒤처진 상태에서 작동하도록 두고, 해당 source queue가 비게 될 때에만 injection process의 시간을 앞으로 진전시키는 방식이다.

Figure 24.9 설명

Figure 24.9는 source injection queue의 동작 예를 보여준다. injection process의 이력 일부는 tape 조각처럼 표현되며, 각 칸은 simulation cycle 하나에 해당한다. 칸이 비어 있으면(회색) 해당 cycle 동안 packet이 inject되지 않은 것이고, 채워져 있으면 해당 cycle에 inject될 packet을 의미한다. source queue는 비어 있을 때 회색으로 표시되며, packet이 있을 경우 그 이름으로 표시된다. injection process가 network 시간보다 느리게 동작하기 때문에, source queue는 오직 하나의 packet만 저장하면 된다.

예시는 cycle 0에서 network 시간과 injection process 시간이 모두 0으로 시작하고 source queue가 비어 있는 상태에서 시작된다. network 시간이 진행되면 source queue의 상태를 확인한다. 비어 있으면 injection process 시간도 같이 진행되며, packet이 생성되거나 network 시간과 맞을 때까지 증가한다. 이로 인해 packet A가 생성되고, injection process 시간은 한 cycle 증가한다 (b). cycle 2와 3에서도 같은 절차가 반복되지만, source queue가 아직 packet A로 가득 차 있으므로 network 시간은 2 cycle 동안 증가하고 injection process 시간은 cycle 1에서 멈춘다 (c). cycle 3에서 packet A가 네트워크로 나가고 source queue가 비게 되면, injection process 시간은 cycle 2로 진행되고, packet이 없으므로 다시 cycle 3으로 진행되어 packet B가 생성된다 (d).

24.4.3 난수 생성(Random Number Generation)

많은 네트워크 트래픽 프로세스는 stochastic 특성을 가지므로, network simulator는 이러한 source를 구현하기 위해 난수 생성을 필요로 한다. 예를 들어, 다음은 rate r을 갖는 Bernoulli injection process를 모델링한 C 스타일의 pseudo-code이다:

random() 함수는 0과 1 사이에서 균일하게 분포된 실수 값을 생성한다. 이 코드는 간단해 보이지만, 실제로 난수를 생성하는 과정은 상당히 까다롭다.

먼저, 실제로 난수를 생성하는 방법은 보통 자연적인 noise source를 샘플링하는 것이다. 예를 들어, 저항에서의 열잡음(Johnson noise)이나 reverse-bias 다이오드에서의 noise를 사용하는 방법 등이 있다. 하지만 실용적인 이유로 대부분의 소프트웨어는 pseudo-random number generator(PRNG)를 사용한다.

대부분의 PRNG는 다음과 같은 구조를 가진다. PRNG의 상태는 seed 값으로 저장되고, 난수가 요청되면 PRNG 알고리즘이 현재 상태로부터 "난수"와 다음 상태를 계산한다. 이 값은 사용자에게 반환되고 seed는 다음 상태로 갱신된다. 이 과정은 실제로는 완전한 무작위성과는 거리가 있지만, 적절한 알고리즘을 사용한다면 다양한 통계적 테스트를 만족할 수 있다.

불행히도 C 라이브러리에 기본 포함된 rand와 drand48 같은 난수 생성기는 품질이 낮은 편이다. 예를 들어 rand의 하위 비트는 주기가 짧고 무작위성이 떨어진다. drand48은 약간 개선되었지만 여전히 큰 문제가 있다. 따라서 이론적으로 검증되었고 경험적으로도 신뢰할 수 있는 PRNG를 사용하는 것이 바람직하다. 좋은 예로는 Knuth, Matsumoto & Kurita, Park & Miller가 제안한 PRNG들이 있다.

PRNG의 또 다른 실용적인 장점은 결정론적이라는 점이다. 초기 seed 값만 고정되면 생성되는 난수 시퀀스, 나아가 전체 시뮬레이션 동작이 동일하게 재현될 수 있다. 이로 인해 시드 값을 바꿔 다양한 실험을 수행할 수도 있고, 특정 결과를 재현하거나 디버깅을 할 때도 유용하다.

24.4.4 문제 해결(Troubleshooting)

다른 시뮬레이터와 마찬가지로, network simulator를 사용할 때도 먼저 기대 결과에 대한 직관이나 근사 계산을 수행한 후 시뮬레이터로 이를 검증하는 방식이 가장 좋다. 이 과정을 따르면 대부분 시뮬레이션 결과는 기대치와 유사하다. 그러나 예상과 다른 결과가 나올 경우 다음과 같은 일반적인 문제 해결 기법을 사용할 수 있다:

• 네트워크를 충분한 수준의 세부 정보로 시뮬레이션하고 있는지 확인한다.
• 자원 간의 불균형이나 불공정성을 확인한다. 이 문제는 매우 흔하지만 단순 모델에서는 간과되기 쉽다.
• 병목 자원을 찾아 문제 범위를 좁힌다. 예를 들어, virtual channel 수나 buffer 크기를 늘려도 throughput이 개선되지 않으면, flow control이 원인이 아닐 수 있다. 그다음은 routing function을 확인한다.
• 통계를 수집한다. 모든 트래픽이 예상된 목적지로 잘 가고 있는가? 일부 packet만 지나치게 오래 네트워크에 머무르고 있는가? 이상 통계는 좋은 실마리를 제공한다.
• 시뮬레이터를 단순한 case로 구성하여 분석 가능한 결과와 비교해 본다. 예를 들어 uniform traffic, Bernoulli arrival, 낮은 offered load, 큰 buffer를 사용해 실험한다.
• 시뮬레이터에도 bug가 있을 수 있다. 다른 시뮬레이터와 비교하거나 현재 시뮬레이터의 코드를 직접 분석해 본다.

24.5 참고 문헌(Bibliographic Notes)

simulation의 기본(설계, 입력, 측정, PRNG)에 대해서는 [29], [109]가 훌륭한 참고 자료이다.

application-driven workload는 여러 곳에서 제공된다. 예를 들어 병렬 컴퓨팅용 benchmark인 SPLASH나 database benchmark는 processor interconnection network를 위한 workload로 사용할 수 있다. 인터넷 packet trace는 다양한 온라인 소스에서 널리 구할 수 있다.

MMP를 활용해 voice와 data traffic을 모델링한 연구는 Heffes와 Lucantoni의 연구에 소개되어 있다. Jain과 Routhier는 burstiness를 모델링하기 위한 packet trains 기법을 제안했다. 그러나 이러한 모델조차도 실제 traffic 흐름의 통계에 비하면 단순하다. 예를 들어 Leland 등의 연구에 따르면 Ethernet traffic은 자기 유사성(self-similarity)을 가지며, 이는 단순 모델로는 표현이 불가능하다. packet size가 network 성능에 미치는 영향은 Kim과 Chien의 연구에서 다루어지며, 긴 message와 짧은 message 간 상호작용이 성능에 상당한 영향을 줄 수 있음을 보여준다.

Knuth는 PRNG의 엄밀한 분석 분야의 선구자였으며, Park과 Miller는 잘 검증된 최소 표준 PRNG를 제안했다. 이후 PRNG 발전은 [111]에서 정리되어 있다. 진정한 난수 발생기의 실제 구현도 있으며, 예를 들어 [149]에서는 on-chip resistor를 noise source로 사용한다.

24.6 연습문제(Exercises)

24.1 Four-state MMP
Figure 24.10의 four-state MMP에 대해 평균 injection rate r을 계산하라. 이 process가 Figure 24.3의 간단한 on-off process와 어떻게 관련되는지 설명하라.

24.2 (σ, ρ) regulator의 성능
Figure 24.3의 on-off MMP를 Section 15.2.1의 (σ, ρ) regulator에 적용했을 때, 비조절 source로 간주하라. σ = 1, ρ = 1/2이며, token은 두 slot마다 하나씩 생성된다. 이 시스템이 안정적(즉, regulator 내 packet queue의 기대 크기가 유한함)이 되기 위한 injection rate r₁에 대한 조건을 구하라. α = 1/4, β = 1/8일 때 Markov chain 모델을 작성하여 평균 queue 크기를 계산하고, 여러 r₁에 대해 시뮬레이션을 수행한 후 평균 queue 크기를 기록하라. 또한 Little’s law(식 23.6)를 사용하여 regulator의 기대 delay를 구하라.

24.3 상관된 workload
이 장에서는 network workload의 세 가지 측면이 독립적인 것으로 설명되었지만, 실제 application에서는 여러 측면 간에 강한 상관관계가 있을 수 있다. 예를 들어, 특정 노드 간 통신에서는 짧은 packet이 더 자주 발생하고, 긴 packet은 더 드물게 발생할 수 있다.

24.6 연습문제

24.3 Correlated workloads
이 장에서는 네트워크 workload의 세 가지 요소를 서로 독립적인 것으로 설명했지만, 실제 네트워크 애플리케이션에서는 이들 요소 간에 강한 상관관계가 존재할 수 있다. 예를 들어, 특정 source-destination pair 간의 통신에서는 긴 packet이 짧은 packet보다 더 드물게 나타날 수 있다. 이러한 상황이 발생할 수 있는 애플리케이션 예시를 설명하고, 이 상관관계를 injection process에 통합할 수 있는 방법을 제안하라.

24.4 Fairness of a coin
동전 하나를 받고, 이 동전이 공정한지 판단하라는 요청을 받았다. 즉, 앞면이 나올 확률이 50%이고 뒷면도 50%인지 확인하는 것이다. 처음 11회의 동전 던지기 결과는 다음과 같다:

{H, T, T, T, H, T, H, H, T, H, T}

이 결과는 5번의 앞면(H)과 6번의 뒷면(T)을 포함한다.

(a) 95%의 신뢰수준으로 이 동전이 거의 공정(앞면 확률이 49%~51%)하다고 말할 수 있는가? 아니라면, 이 동전에 대해 같은 신뢰수준으로 말할 수 있는 다른 특성이 있는가? 자유도는 11−1 = 10이며, Table 24.1의 Student's t-distribution이 유용할 것이다. 또한 앞면은 1, 뒷면은 0으로 할당해 분석해보라.

(b) 동전을 추가로 90번 던져서 총 101개의 샘플을 얻었고, 이 중 36번이 앞면(총 41번)이라면, 이 동전의 공정성에 대해 더 강한 결론을 낼 수 있는가?

24.5 Fairness of a die
Exercise 24.4와 유사한 실험을 수행하되, 동전 대신 정육면체 주사위를 사용하라. 평균값이 (1+2+3+4+5+6)/6 = 3.5로부터 ±0.05 이내에 있을 확률이 95% 이상이 될 때까지 주사위를 굴려라. 몇 번의 굴림이 필요했는가? (이 실험은 PRNG를 사용해 시뮬레이션하는 것이 더 빠를 수 있다.) 이때 confidence interval 계산에는 무한 자유도에 대한 Student’s t-distribution 값을 사용하라. 또한, 주사위가 공정한지(모든 면이 동일 확률로 나오는지)도 확인해보라. 아니라면, 이를 확인하기 위한 방법을 제안하라.

24.6 A single-phase simulation
Figure 24.7의 output queued switch 예제를 "단일 phase" simulation 방식으로 구성해 보자. 즉, ReadInputs와 WriteOutputs 함수를 하나로 통합하는 것이다. 이때 노드를 어떤 순서로 평가할 것인지 결정하는 데 문제가 발생할 수 있는 이유를 설명하라. 이 단일 phase 접근이 동작 가능한 상황이 있는가? 힌트: 시뮬레이션 대상 네트워크의 topology를 고려하라.

24.7 A lagging injection process
Section 24.4.2에서 설명한 lagging injection process를 네트워크 사이클마다 한 번 호출하는 pseudo-code로 작성하라. 네트워크 상태를 접근하기 위한 함수는 다음과 같다:

• sourceq_empty() : source queue가 비어 있으면 true 반환, 아니면 false
• get_net_time() : 현재 네트워크 시간 반환
• inject_packet() : injection process를 한 사이클 수행하고 packet이 생성되면 true, 아니면 false 반환

lagging source queue의 시간은 변수 q_time에 저장되어 있다고 가정한다.

24.8 Quality of a PRNG
다음 코드는 multiplicative linear congruential generator라고 알려진 흔한 PRNG 유형을 구현한 것이다.
이 구현은 [141]에서 언급된 FORTAN 라이브러리에서 사용된 것이다.

이때 0x8000000은 2³¹을 의미한다.
이 코드는 네트워크 시뮬레이터에서 다음처럼 목적지 노드를 선택하는 데 사용될 수 있다:

이 random number generator와 목적지 노드 생성을 구현하라. 생성된 목적지의 “randomness”에 대해 평가하라.
힌트: 이 PRNG는 좋은 난수 생성기가 아니다.