Zeah Engineering Factory

앞서 우리는 bandwidth 증가나 latency 감소처럼 자원 할당 효율을 높이는 데 집중했다. 그러나 routing이나 flow control이 완벽하더라도, 특정 자원에 대한 요청이 그 용량을 초과하는 상황은 여전히 발생한다. 이럴 때는 자원을 얼마나 효율적으로 배분할 것인가보다는, 어떤 service policy에 따라 자원을 공정하게 배분할 것인가에 주의를 기울여야 한다. 이 장에서는 network client가 요청하는 일반적인 서비스들과, 해당 서비스를 제공하는 메커니즘에 대해 설명한다. 이러한 주제 전반을 우리는 QoS(Quality of Service)를 제공하는 것으로 통칭한다.

15.1 Service Classes and Service Contracts

일부 interconnection network에서는 트래픽을 여러 클래스로 나누어 자원 할당을 좀 더 효율적으로 관리한다. 클래스마다 요구사항이 다르다. 어떤 클래스는 latency에 민감하고, 어떤 클래스는 latency에는 둔감하지만 jitter는 허용하지 않는다. 어떤 클래스는 packet loss를 허용할 수 있고, 어떤 클래스는 전혀 허용하지 않는다. 또한 중요도도 다르기 때문에, 생명 유지 시스템에 필요한 packet은 오락 시스템의 오디오 packet보다 우선순위가 높다.

클래스에 따른 자원 할당은 더 중요한 서비스에 더 많은 자원을 할당하거나, 클래스의 특성에 맞게 할당 방식을 조정하는 데 도움이 된다. 예를 들어, 상위 클래스 packet에는 buffer나 channel을 우선 할당하거나, 전체 자원 중 큰 비율을 제공할 수 있다. latency가 낮아야 하는 packet은 앞서 보내고, jitter를 줄여야 하는 packet은 예측 가능한 delay를 갖게 스케줄링하며, 손실을 허용하는 클래스는 손실 불가한 클래스보다 먼저 버려진다. 이런 방식은 모든 packet이 동일한 서비스를 받는 것보다 훨씬 효율적인 자원 할당이 가능하다.

트래픽 클래스는 크게 guaranteed service class와 best effort class로 나뉜다. guaranteed service는 특정 조건을 만족하는 한 일정 수준의 성능을 보장한다. 이는 network와 client 사이의 service contract를 의미하며, 일반적으로 client는 일정 수준 이하의 traffic만을 inject해야 하며, network는 그에 대한 loss rate, latency, jitter 등을 보장한다. 예를 들어, class A의 packet은 100ns 동안 1Kbit 이하를 inject할 경우, 99.999% 이상이 1μs 이내에 손실 없이 전달된다.

반면 best effort class는 어떤 보장도 하지 않는다. 이러한 packet은 delay가 길어지거나 drop될 수도 있다. network는 단지 최선의 노력을 할 뿐이다. 이는 마치 Federal Express(guaranteed)와 USPS mail(best effort)의 차이처럼 비유된다. best effort class 내에서도 여러 등급이 있을 수 있다.

하나의 클래스 내부, 특히 best effort class 내에서는 fairness가 중요하다. flow는 같은 클래스를 구성하는 가장 작은 단위이며, source, 목적지, 애플리케이션 등 기준은 다양하다. 동일한 클래스의 두 flow가 서로 매우 다른 서비스를 받는다면 network는 공정하지 않다고 볼 수 있다. 이 fairness는 아래에서 더 정확히 정의된다.

15.2 Burstiness and Network Delays

service 보장에는 단순한 속도 외에 delay와 jitter도 포함된다. 이를 위해서는 flow의 burstiness를 고려해야 한다. bursty하지 않은 flow는 일정한 패턴으로 데이터를 전송하며, bursty한 flow는 특정 순간에 많은 데이터를 몰아서 보낸다.

예를 들어, 하나는 2/3 packet/cycle의 비율로 꾸준히 전송하고, 다른 하나는 1/3 packet/cycle 비율이지만 한꺼번에 몰아보낸다. 이 두 flow가 1 packet/cycle의 channel을 공유하면, non-bursty flow의 jitter는 1에서 2 cycle로 증가하고, bursty flow는 최대 4 cycle의 delay를 겪는다. 이는 bursty한 flow가 다른 flow의 delay나 jitter에 큰 영향을 미칠 수 있음을 보여준다.

15.2.1 (σ, ρ) Regulated Flows

QoS를 위한 흐름 모델링 방식 중 하나는 (σ, ρ)로 나타내는 것이다. 여기서 ρ는 평균 전송 속도이며, σ는 burstiness를 나타낸다. 시간 T 동안 전송 가능한 최대 bit 수는 σ + ρT이다. 이는 평균보다 얼마나 bursty할 수 있는지를 정의한다.

예를 들어 100ns 동안 1Kbit 이하를 inject한다는 것은, ρ가 10Gbps이고, σ는 1Kbit임을 의미한다.

(σ, ρ) flow는 regulator를 통해 제어할 수 있다. regulator는 input queue와 token queue로 구성되며, token은 ρ rate로 주기적으로 생성된다. token queue의 크기 σ가 burstiness를 제어한다. 이 구조는 bursty한 flow가 network에 미치는 영향을 줄일 수 있다.

※ 실제 구현에서는 token queue 대신 credit counter를 사용할 수 있다. 이 counter는 ρ 속도로 증가하고 σ에서 포화되며, credit이 있을 때만 packet을 전송할 수 있다.

15.2.2 Calculating Delays

(σ, ρ)로 표현된 flow를 기반으로 deterministic한 delay 상한을 계산할 수 있다. 예를 들어, 두 개의 입력 flow가 하나의 multiplexer를 통해 합쳐지는 경우를 생각해보자. 각각의 flow는 (σ₁, ρ₁), (σ₂, ρ₂)로 규제되며, 입력과 출력 모두 bandwidth는 b로 동일하다고 가정한다.

이러한 구조는 queueing delay 분석에 사용된다. 이후 그림 15.3에서 이 구조를 기반으로 지연 시간 분석이 이어진다.

그림 15.3은 multiplexer의 queue 크기를 시간에 따라 나타낸 것으로, queue가 비어 있지 않은 최대 구간을 만들기 위한 adversarial input에 대한 전략을 보여준다. 기울기가 증가하는 구간은 한쪽 또는 양쪽 입력이 injection channel bandwidth가 허용하는 최대 속도로 전송하는 구간을 나타낸다. 양쪽의 burst가 끝나면 queue는 서서히 비워진다.

packet이 output으로 선택되는 방식에 대한 유일한 가정은 multiplexer가 work-conserving이라는 것이다. 즉, queue에 packet이 있으면 output channel은 idle 상태가 아니다.

시스템이 안정적이고 최대 지연이 정의되기 위해서는 ρ₁ + ρ₂ < b 조건을 만족하면 충분하다. 이 조건은 multiplexer queue가 비게 되는 순간이 존재함을 보장하고, 이는 곧 packet delay의 최대값이 queue가 비어 있지 않은 시간 구간으로 제한된다는 것을 의미한다. 따라서 최대 packet delay를 구하려면 queue가 가장 오랫동안 비어 있지 않게 만드는 adversarial input을 찾으면 된다.

adversarial 전략은 세 단계로 요약된다. 첫 번째 단계에서는 t = 0부터 양쪽 입력이 동시에 rate b로 전송을 시작한다. 입력은 총 2b 속도로 queue에 들어오지만, multiplexer는 b 속도로만 drain할 수 있기 때문에 queue는 rate b로 증가한다. 이는 그림 15.3의 첫 번째 직선 구간의 기울기로 나타난다. 이 단계는 어떤 입력 하나가 자신의 (σ, ρ) 조건을 위반하지 않기 위해 더 이상 b rate를 유지할 수 없는 시점까지 계속된다. 첫 번째 flow가 먼저 이 지점에 도달한다고 가정하면, 이때의 시간 t₁은 다음과 같다:

  t₁ = σ₁ / (b - ρ₁)

두 번째 단계에서는 첫 번째 flow가 rate ρ₁로만 전송할 수 있으며, 두 번째 flow는 여전히 b rate로 전송한다. 이로 인해 총 injection rate는 ρ₁ + b이고 drain rate는 b이므로 queue는 계속 증가하지만 증가 속도는 ρ₁이다. 이 단계는 두 번째 flow가 b rate를 유지할 수 없는 시점인 t₂까지 지속되며, 이때

  t₂ = σ₂ / (b - ρ₂)

세 번째 단계에서는 두 flow 모두 burst를 소진한 상태로, 각각 ρ₁, ρ₂ rate로 steady-state 전송을 한다. 이때 queue는 b - ρ₁ - ρ₂ 속도로 줄어들며, queue가 비워지는 데 걸리는 시간은 다음과 같다:

  t_drain = q_max / (b - ρ₁ - ρ₂)

여기서 q_max는 앞의 두 단계에서 누적된 queue 크기이다.

  q_max = b·t₁ + ρ₁(t₂ - t₁) = σ₁ + ρ₁σ₂ / (b - ρ₂)

따라서 최대 delay는 queue가 비어 있지 않은 구간의 총 시간으로 다음과 같이 계산된다:

  D_max = t₂ + t_drain = (σ₁ + σ₂) / (b - ρ₁ - ρ₂)

이 input 전략이 실제로 D_max를 최대화한다는 것은 [42]에서 증명되었으며, 양쪽 flow의 burst를 완전히 사용하고 queue를 최대로 만드는 전략이 최대 delay를 유도한다는 점에서 직관적이다. 이 방식은 다양한 네트워크 요소의 delay 계산에도 적용 가능하다.

✅ 왜 최대 지연 계산이 중요한가?

1. 서비스 보장(QoS)을 위해 필요함
   어떤 클래스의 트래픽에 대해 일정 수준 이하의 latency나 jitter를 보장하려면, 그 트래픽이 최악의 경우에도 얼마나 지연될지를 알아야 함. 예: "1μs 이하의 latency를 보장합니다" 같은 서비스 약속.
2. 네트워크 설계 시 자원 할당 근거로 사용됨
   router나 multiplexer 같은 구성 요소에 얼마나 많은 buffer나 bandwidth가 필요할지를 예측하기 위해, 이론적인 최대 지연값을 알아야 함.
3. 공정성 판단에도 활용 가능
   하나의 flow가 너무 많이 지연되는 경우, 자원이 공정하게 배분되지 않았을 수 있으므로, 지연 분석은 공정성(fairness) 평가에도 유용함.

15.3 Implementation of Guaranteed Services

guaranteed service를 구현하는 방법에는 여러 가지가 있다. 가장 간단한 방법은 aggregate resource allocation이며, 이는 특정 flow에 자원을 고정으로 할당하지 않고 전체 클래스의 자원 사용량에 기반하여 네트워크가 요청을 수락하는 방식이다. 이는 하드웨어 비용이 적고 구현이 간단하지만, delay bound가 느슨하다.

더 낮은 delay를 얻기 위해서는 space, 또는 space와 time을 함께 고려한 자원 예약이 필요하다. 이 경우 자원 예약 정보를 저장하기 위한 하드웨어가 추가로 필요하다.

15.3.1 Aggregate Resource Allocation

가장 간단한 guaranteed service 구현 방식은 트래픽 클래스 C의 총 요청량 ΣC가 일정 한도 이하일 것을 요구하는 것이다. 이 조건만 만족하면 네트워크 과부하를 피할 수 있고, packet loss 없이 특정 delay 특성을 보장할 수 있다. 이는 가장 단순한 guaranteed service 방식이며, 각 flow에 자원을 별도로 할당하지 않기 때문에 추가 하드웨어가 거의 필요 없다.

그러나 클래스 C에 속한 여러 input flow가 섞이면서, 결과적으로 output flow는 더욱 bursty해진다. 이로 인해 delay bound는 느슨해지고 jitter 보장이 어려워진다.

aggregate allocation에서는 client가 명시적으로 요청할 수도 있고, implicit하게 네트워크가 판단할 수도 있다. 예를 들어, packet switching 네트워크에서는 입력 또는 출력 포트가 과부하되지 않는 한 어떤 자원 요청이든 수락 가능하다. 포트가 처리 가능한 bandwidth를 초과하여 traffic을 수용하거나 전달해야 하는 경우, 해당 포트는 oversubscribed 상태이다.

그림 15.4의 예를 보자. 2-ary 2-fly 네트워크에 stage를 하나 더 추가하고, 트래픽을 중간 단계에서 random switch를 통해 목적지로 보낸다. 여기에는 bursty한 flow (노드 0 → 1)와 non-bursty한 flow (노드 2 → 0)가 있다. 자원을 flow별로 고정할 수 없는 aggregate 방식에서는 두 flow 사이에 coupling이 생기며, 이로 인해 non-bursty flow의 jitter가 증가한다. 또한 randomized routing은 시간뿐 아니라 공간에서도 burstiness를 유발한다. 평균적으로는 균형이 맞지만, 순간적으로는 불균형이 생기기 때문이다.

이러한 효과를 고려하고 15.2.2절의 delay 결과를 적용하면 다음과 같은 delay bound를 얻을 수 있다. 두 flow 모두 (σ, ρ)로 규제되며, bursty flow는 ρ₁ = 0.75Gbps, σ₁ = 1,024 bits이고, non-bursty flow는 ρ₂ = 0.75Gbps, σ₂ = 64 bits이다. channel bandwidth b = 1Gbps이고, 최대 packet 길이는 L = 128 bits이다.

randomized routing으로 인해 flow는 두 개의 sub-flow로 나뉘며, 각 sub-flow의 rate는 ρ/2이다. burstiness는 packet 단위 granularity로 인해 단순히 반으로 줄어들지 않고 상한은 (σ + L)/2가 된다.

즉,

  σ′₁ ≤ (1024 + 128)/2 = 576 bits
  σ′₂ ≤ (64 + 128)/2 = 96 bits

second stage에서 두 sub-flow가 multiplexer에 의해 병합되며, 15.2.2절의 결과를 적용하면 delay는 다음과 같다:

  D_max = (σ₁ + σ₂ + L) / (2b − ρ₁ − ρ₂)
     = (576 + 96) / (0.25Gbps) = 2.688μs

지연이 전혀 없는 경우도 가능하므로 jitter는 D_max와 동일할 수 있다. 마지막 단계에서 destination으로 가기 전 또 한 번의 multiplexing이 발생하며, 유사한 방식으로 delay를 계산할 수 있다.

15.3.2 Resource Reservation

더 강력한 delay와 jitter 보장이 필요한 경우에는 aggregate allocation보다 자원을 명시적으로 예약하는 방식이 필요하다. 이 경우 예약 정보를 네트워크 내에 저장해야 하므로 더 많은 하드웨어 자원이 필요하다. 여기서는 두 가지 예약 방식—virtual circuit과 time-division multiplexing(TDM)—을 소개한다.

Virtual circuit 방식은 각 flow에 대해 네트워크 내 고정된 경로를 할당하여 공간상 자원을 예약하는 방식이다. 예를 들어 ATM(Asynchronous Transfer Mode)에서 사용된다. 이 방식은 delay와 jitter의 주요 원인을 제거할 수 있다. 첫째, 자원이 공간적으로 예약되므로 randomized routing 등으로 인한 변동성이 사라진다. 둘째, 서로 영향을 미치는 flow 간 coupling을 피하기 위해 경로를 분리할 수 있다. 예를 들어, 앞서 본 2-ary 2-fly 구조에서 non-bursty flow는 bursty flow와 경로를 다르게 설정하여 jitter를 줄일 수 있다.

보다 엄격한 보장이 필요할 때는 TDM(Time-Division Multiplexing)을 사용한다. TDM은 시간과 공간 모두에서 특정 flow가 사용하는 자원을 완전히 독점하도록 구성한다. 이로 인해 다른 flow가 해당 자원을 공유하지 않게 되어, 예측 가능한 성능을 제공할 수 있다.

TDM 방식에서는 시간을 일정한 크기의 slot으로 나누고, 각 slot은 flit 하나를 전송할 수 있는 시간에 대응한다. 예를 들어 시간 단위를 32개의 slot으로 나누고, 각 slot이 1 flit 전송 시간이라면, bandwidth가 1 GByte/s인 채널에서 최소 32 MByte/s 단위로 bandwidth를 할당할 수 있다. 어떤 flow가 256 MByte/s를 요구한다면, 필요한 자원마다 8개의 slot을 요청하면 된다.

그림 15.6에서는 4-slot 기반 TDM 네트워크에서의 할당 예시를 보여준다. 일부 채널은 두 flow가 공유하지만, 각 slot은 특정 flow에 고유하게 할당되어 있어 서로 영향을 주지 않는다. 이런 방식으로 bursty한 flow와 자원을 공유하더라도 다른 flow의 burstiness가 증가하지 않는다.

slot 할당은 연결이 미리 정해진 경우 offline으로 계산할 수도 있고, 동적으로 연결이 추가되거나 제거되는 경우 online으로도 처리할 수 있다. 하지만 최적 할당을 찾는 문제는 일반적으로 NP-hard이며, 실무에서는 heuristic 방식을 사용한다. 하나의 heuristic 예시는 Exercise 15.5에서 다룬다.

각 자원에는 timewheel을 연결하여 시간별 자원 예약 상태를 저장할 수 있다. 현재 시간 slot을 가리키는 포인터가 존재하며, 해당 slot에서 자원을 사용할 수 있는 flow를 나타낸다. 사용되지 않는 slot은 "BE"로 표시되어 best-effort traffic이 사용할 수 있음을 의미한다. 시간이 흐르면 포인터는 다음 entry로 증가하며, 끝에 도달하면 다시 처음으로 돌아간다.

15.4 Implementation of Best-Effort Services

Best-effort 서비스 구현에서 QoS 측면의 핵심은 여러 best-effort flow 간의 공정성(fairness)을 제공하는 것이다. 마찬가지로, guaranteed service 내에서도 자원이 완전히 예약되지 않았을 경우에는 유사한 공정성 문제가 발생할 수 있다. 여기서는 두 가지 공정성 정의—latency fairness와 throughput fairness—를 소개하고, 각각의 구현 이슈를 설명한다.

15.4.1 Latency Fairness

latency fairness의 목적은 동일한 자원을 경쟁하는 여러 flow에 대해 동일한 지연을 제공하는 것이다. 이 개념을 설명하기 위해, 그림 15.7처럼 복잡한 주차장에서 차들이 출구로 나가는 상황을 예로 들어보자. 각 열에는 차들이 줄지어 서 있으며, 출구는 하나의 공유 경로다.

일반적인 운전 예절에서는 병합 지점에서 번갈아 차를 보내는 것이 공정하다. 이를 locally fair arbitration이라 부른다. 이 방식에서는 각 병합 지점에서 차들이 번갈아 나가므로 겉보기에 공정해 보인다. 하지만 D1은 가장 먼저 도착했음에도 불구하고, A열 차들보다 훨씬 늦게 출구에 도달한다. 24열까지 확장하면 마지막 열의 첫 번째 차량은 1년 이상 기다려야 나갈 수 있을 것이다.

이러한 문제를 해결하려면, 자원 요청자 중 가장 오래된 요청이 우선권을 가지는 latency fair arbitration을 도입해야 한다. 이 방식은 각 merge point에서 두 요청 중 더 오래된 요청을 먼저 처리하며, 결과적으로 각 열에서 한 대씩 돌아가며 나가는 구조가 된다. 네트워크에서는 이를 age-based arbitration이라고 하며, 패킷이 network에 inject된 시간 기준으로 가장 오래된 packet이 우선 접근권을 가진다.

이 방식은 latency fairness를 크게 향상시키지만, 전체 네트워크에서 완전한 latency fairness를 달성하는 것은 어렵다. 이유는 priority inversion 문제가 발생할 수 있기 때문이다. 즉, 우선순위가 높은(오래된) 패킷이 우선순위가 낮은(최근) 패킷 뒤에 막히는 현상이다. 이러한 문제는 다음에 소개할 throughput fairness에서도 동일하게 발생하며, Section 15.5에서 소개할 non-interfering network 설계를 통해 해결할 수 있다.

15.4.2 Throughput Fairness

latency 중심의 fairness와 달리, throughput fairness는 동일한 자원을 경쟁하는 flow들에 대해 동일한 bandwidth를 제공하는 것을 목표로 한다. 그림 15.8(a)는 세 개의 flow가 하나의 공유 채널을 사용하는 상황이다. 각 flow는 0.5 packet/cycle을 요청하지만 채널은 총 0.75 packet/cycle만 처리 가능하다. 따라서 각각의 flow는 0.25 packet/cycle씩 할당받는 것이 throughput 공정한 할당이다.

하지만 각 flow의 요청률이 달라지면 상황은 더 복잡해진다. 그림 15.8(b)에서는 각각 0.15, 0.5, 0.5 packet/cycle을 요청한다. 이 경우에는 여러 정의가 있을 수 있으나, 일반적으로 사용되는 정의는 max-min fairness이다. max-min fairness란, 어떤 flow의 할당량을 늘리면 그것보다 같거나 적은 할당을 가진 다른 flow의 할당량을 줄이지 않고는 늘릴 수 없는 상태를 말한다. 이 조건을 만족하는 할당이 바로 그림 15.8(b)에서 보여진 상태다.

max-min fairness는 다음과 같은 알고리즘으로 달성할 수 있다. N개의 flow가 있을 때, 각 flow i는 요청 bandwidth bᵢ를 갖고 있고, 모든 bᵢ를 오름차순으로 정렬한다고 하자. 그 후에는 가장 작은 요청을 가진 flow부터 bandwidth를 할당하면서, 나머지 자원이 고갈될 때까지 진행한다.

bandwidth는 다음과 같은 점화식으로 할당할 수 있다:

  R₀ = b
  aᵢ = min [bᵢ, Rᵢ / (N - i)]
  Rᵢ₊₁ = Rᵢ - aᵢ

여기서 b는 전체 bandwidth, Rᵢ는 i번째 요청까지 처리한 후 남은 bandwidth, aᵢ는 i번째 요청에 할당된 bandwidth이다. 이 알고리즘은 가장 작은 요청부터 먼저 할당하며, 남는 자원은 더 큰 요청들 사이에 균등하게 나누어진다.

max-min fairness는 하드웨어적으로는 각 flow의 요청을 별도의 queue로 분리하고, queue를 round-robin 방식으로 서비스함으로써 구현할 수 있다. 빈 queue는 건너뛴다. 이 구현 방식은 흔히 fair queueing이라 불린다. 개념적으로는 간단하지만, 현실에서는 몇 가지 문제점이 있다. 예를 들어, packet 길이가 다를 경우 추가적인 처리 로직이 필요하고, weighted fair queueing은 특정 flow에 더 높은 우선순위를 부여할 수 있는 기능도 제공한다. latency fairness에서와 마찬가지로, 진정한 throughput fairness도 네트워크 내 각 자원에서 per-flow 구조를 유지해야만 가능하다.

15.5 Separation of Resources

서비스 보장과 공정성 보장을 달성하려면 traffic class 간 격리(isolation)가 필요하다. 때로는 하나의 클래스 내부에서도 flow 간 구분이 필요할 수 있다. 이 절에서는 class와 flow를 통칭하여 class라 표현한다.

TDM 같은 예약 기반 기법에서는 자원 예약 정보를 저장하는 table이 필요하며, 그에 따른 비용이 든다. 반면, 자원이 동적으로 할당되는 경우에는 상황이 훨씬 복잡해진다. 이상적으로는 global하게 자원을 스케줄링하여 서로 영향을 주지 않도록 해야 하지만, interconnection network는 분산 시스템이기 때문에 global approach는 현실적이지 않다. 대신 fair queueing, age-based arbitration 같은 local 알고리즘을 사용하여 자원을 분배하고, 하드웨어 수준에서의 class 간 자원 분리가 필요하다.

본격적으로 non-interfering network를 소개하기 전에, 자원 분리 실패로 인한 대표적 병목 현상인 tree-saturation에 대해 설명한다.

15.5.1 Tree Saturation

어떤 자원이 평균보다 훨씬 많은 traffic을 수신하면, 네트워크 내 특정 지점이 hot-spot이 되어 문제가 생긴다. 예를 들어, shared memory 시스템에서는 여러 processor가 동시에 하나의 memory 주소에 lock을 얻기 위해 polling할 경우, 해당 노드가 과부하되고 hot-spot이 된다. IP router에서도 특정 output port로의 traffic이 집중되거나 routing table 설정 오류로 인해 hot-spot이 발생할 수 있다.

이러한 hot-spot은 단순히 해당 자원만이 아니라, 전혀 관련 없는 traffic에도 영향을 줄 수 있다. tree-saturation이란, hot-spot 자원을 향하는 packet들로 인해 인접 채널이 막히고, 그 인접 채널들로 향하는 경로도 차례로 막히면서 나무 형태의 정체 패턴이 형성되는 현상을 말한다.

그림 15.9는 이 개념을 보여준다. 예를 들어 destination 4가 과부하되어 해당 방향 채널들이 막히면, 그 채널로 이어지는 다른 채널들도 전파적으로 막히게 된다. 이때 어떤 packet이 destination 7로 가고자 하더라도, 해당 경로가 saturation tree에 포함되어 있다면 직접적으로 연관되지 않은 hot-spot 때문에 간접적 정체가 발생할 수 있다. 이 문제는 단지 목적지 노드에 국한되지 않고, 네트워크 채널 자체의 과부하로도 발생할 수 있다.

15.5.2 Non-interfering Networks

두 클래스 A와 B가 서로 non-interfering하려면, A가 사용하는 자원을 무기한 점유하여 B가 접근하지 못하게 하는 일이 없어야 한다. 이 조건을 만족하는 네트워크를 non-interfering network라 부른다.

예를 들어 virtual-channel flow control을 사용할 경우, 각 클래스별로 별도의 virtual channel을 구성하면 non-interfering 구조가 된다. 반면, physical channel은 매 사이클마다 재할당되므로, 한 클래스가 무한정 점유할 수 없기 때문에 반드시 복제할 필요는 없다. 입력 buffer 또한 클래스별로 분리되어야 하며, 각 client는 클래스마다 별도의 injection buffer를 가져야 한다.

non-interfering network는 서비스 보장과 공정성을 만족시키기 위해 필요한 자원 격리를 제공하지만, 하드웨어 복잡도가 매우 높아질 수 있다. 예를 들어, Internet router에서 output 간 간섭을 막기 위해 각 output마다 하나의 traffic class를 지정하고, virtual channel 및 injection buffer를 완전히 분리하려면 수백 개의 class를 지원해야 하며, 이는 라우터 설계를 크게 복잡하게 만든다.

따라서 진정한 격리가 필요한 클래스 수는 최소화하는 것이 설계상 바람직하다. 많은 경우 클래스 간 병합이 가능하며, 하드웨어 복잡도 감소와 서비스 품질 간 균형을 맞추는 것이 중요하다.

15.6 Case Study: ATM Service Classes

ATM(Asynchronous Transfer Mode)은 음성, 영상 등 멀티미디어 트래픽을 지원하면서, 동시에 best-effort traffic까지 수용 가능한 유연성을 갖춘 네트워크 기술이다. ATM은 주로 기업용 통합 네트워크, 캠퍼스 백본, 인터넷 백본 등에 사용된다.

ATM은 connection-based 방식이므로, 데이터 전송 전에 source와 destination 간의 virtual circuit이 먼저 설정되어야 한다. 연결은 회선 기반이지만, 데이터 전송 및 switching은 packet 기반이다. ATM의 독특한 특징 중 하나는 packet 크기가 고정(53 bytes)이라는 점이며, 이는 packetization latency를 줄이고 router 설계를 단순하게 만든다.

ATM은 다음과 같은 5가지 기본 서비스 클래스를 정의한다:

• CBR(Constant Bit Rate): 예) 실시간 uncompressed 음성
• VBR-rt(Variable Bit Rate, real-time): 예) 화상회의용 압축 영상
• VBR(Variable Bit Rate): VBR-rt와 유사하나 delay/jitter 요구는 덜함
• ABR(Available Bit Rate): 대역폭 수요는 알려져 있고 동적으로 조절 가능
• UBR(Unspecified Bit Rate): best-effort traffic

UBR을 제외한 서비스 클래스들은 class type 외에도 추가적인 service parameter를 요구한다. 예를 들어 VBR-rt는 (σ, ρ) regulated flow로, SCR(Sustained Cell Rate)과 BT(Burst Tolerance)를 명시해야 한다. 또한 MCR(Minimum Cell Rate), PCR(Peak Cell Rate), CLR(Cell Loss Ratio) 등 다양한 파라미터를 통해 flow 특성을 상세히 정의할 수 있다.

ATM은 CBR 트래픽에 대해서는 TDM 기반 전달 방식도 사용 가능하지만, 나머지 클래스들은 대부분 동적 자원 할당을 필요로 한다. 대부분의 switch는 throughput fairness를 보장하며, virtual circuit 간 자원 분리를 통해 간섭을 방지한다.

15.7 Case Study: Virtual Networks in the Avici TSR

앞서 Section 9.5에서 소개한 Avici TSR 네트워크는 oblivious source routing을 사용해 load를 균형 있게 분산시킨다. 이번 절에서는 이 시스템이 어떻게 virtual channel을 활용하여 non-interfering network를 구현했는지를 살펴본다.

Avici TSR은 각 목적지 노드 쌍마다 별도의 virtual channel을 할당하여, 네트워크 내 트래픽이 완전히 독립되도록 구성되어 있다. 즉, A로 가는 트래픽은 B로 가는 트래픽과 어떤 buffer도 공유하지 않으며, 따라서 B가 과부하되어 buffer를 가득 채우더라도 A로 가는 트래픽은 영향을 받지 않는다. 단, physical channel은 공유하지만, 전체 네트워크의 fabric channel에서 load balancing이 이루어지므로 steady state에서는 B가 자신의 output bandwidth 이상을 초과할 수 없다.

이 문제는 그림 15.10에서 잘 나타난다. B가 과부하되면 해당 방향의 모든 링크가 정체되며, 이는 tree saturation 현상으로 나타난다.

그림 15.10은 2D mesh 네트워크의 일부 구간을 보여주며, 목적지 노드 B로의 과부하로 인해 발생한 tree-saturation 현상을 나타낸다. 회색 경로 a, b, c, d를 따라 노드 A로 가는 패킷은 링크 d를 제외한 모든 지점에서 B로 향하는 트래픽과 자원을 공유하면 지연될 수 있다. 링크 d에서는 방향이 반대이므로 다른 virtual channel과 flit buffer를 사용하게 되어 지연이 발생하지 않는다.

B로 향하는 트래픽이 소비하는 bandwidth 자체는 문제가 아니다. B가 소비할 수 있는 bandwidth는 최대 1이고, 그 load가 모든 경로에 고르게 분산되어 있다고 가정하면, 링크 c에서는 B로 향하는 트래픽이 전체의 1/12, 링크 a에서는 1/20 정도만 사용하게 된다. 이는 A로 가는 패킷을 처리하기에 충분한 bandwidth를 남겨둔다. 하지만 문제는 B로 향하는 트래픽이 virtual channel과 flit buffer를 모두 점유하고, backup 상태이기 때문에 이 자원들을 매우 천천히 해제한다는 점이다. 이는 마치 축구장(노드 B) 근처에 위치한 식료품점(노드 A)으로 가려 할 때, 경기장으로 가는 차들로 인해 도로가 막혀 목적지에 도달하지 못하는 상황과 유사하다.

해결책은 각 목적지에 대해 별도의 virtual network를 제공하는 것이다. Avici TSR은 이를 실현하며, 두 개의 traffic class에 대한 differentiated service까지 제공한다. TSR은 각 physical channel당 512개의 virtual channel을 제공하며, 목적지 d마다 해당 방향의 모든 링크에 대해 두 개의 virtual channel을 예약한다. 하나는 일반 트래픽용, 다른 하나는 premium 트래픽용이다. 또한 source queue도 목적지와 서비스 class별로 분리되어 있어, source queue에서도 간섭이 발생하지 않는다. 이 구조에서는 A로 가는 트래픽이 B로 가는 트래픽과 virtual channel이나 buffer를 공유하지 않기 때문에 간섭이 발생하지 않는다. bandwidth만 공유할 뿐이며, 그 외 자원은 공유되지 않는다.

이는 마치 각 목적지마다 별도의 차선을 가진 도로와 같다. 경기장으로 가는 차들은 해당 차선에서 정체되어 있지만, 식료품점으로 가는 차는 별도의 차선을 통해 문제없이 진행된다. interconnection network의 장점은, 비용이 저렴한 buffer 같은 자원은 복제하고, 고비용인 bandwidth는 공유함으로써 이런 격리를 구현할 수 있다는 것이다. 불행히도 도로와 자동차에는 이 방법을 적용할 수 없다.

TSR은 2개의 traffic class를 가진 512개의 노드를 512개의 virtual channel만으로 지원하기 위해, 거리상 최대한 멀리 떨어진 두 노드는 최소 경로를 기준으로 공통 physical channel을 사용하지 않음을 이용한다. 따라서 두 노드는 같은 virtual channel 번호를 사용하더라도 간섭이 없다. 그림 15.11은 8-node ring에서 이를 설명한 예다. 노드 X로 가는 패킷은 화살표 방향의 링크만 사용하고, 노드 Y로 가는 패킷은 반대 방향 링크만 사용한다. 따라서 경로가 겹치지 않기 때문에 같은 virtual channel을 사용해도 문제가 없다.

15.8 참고 문헌 노트

QoS의 일반적인 주제 및 대규모 네트워크(예: 인터넷)에서의 구현 이슈에 대한 상세한 논의는 Peterson과 Davie의 저서에서 다루어진다. QoS가 라우터 설계에 미치는 영향은 Kumar 등이 다루었다. (σ, ρ) flow에 대한 정밀한 해설과 network delay 계산에의 활용은 Cruz가 설명하였다.

네트워크에서의 공정성 정의는 Jaffe가 초기에 다루었고, throughput fairness는 Nagle이 도입하였으며, Demers 등이 이를 실용적인 조건에 맞게 확장하였다. max-min fairness는 구현 비용이 높아 approximation 기법이 사용되며, 예로 Golestani의 stop-and-go queueing, Kim과 Chien의 rotating combined queueing 알고리즘이 있다. 후자는 interconnection network에 맞춰 설계되었다.

Yum 등은 virtual clock 알고리즘을 확장하여 MediaWorm router에서 rate 기반 서비스를 구현하였다. SGI SPIDER, Tandem ServerNet, MMR 등도 다양한 수준의 QoS를 적용한 상용/학술용 라우터이다. tree saturation은 Pfister와 Norton이 shared memory 시스템에서 동일한 메모리 주소로의 요청을 하나로 통합하는 buffer 구조를 통해 처음 지적하였다. flow 간 자원을 분리하는 대표적 기법으로는 virtual output queueing이 있으며, Tamir와 Frazier가 이를 다루었다.

15.9 연습문제

15.1 Burstiness 예제
Figure 15.1의 예제가 Section 15.2.2의 일반 multiplexer 모델에서 제시된 delay bound를 만족함을 확인하라.

15.2 동일 분할된 flow의 burstiness
하나의 (σ, ρ) flow를 rate가 ρ/2인 두 개의 flow로 나누었을 때, 각각의 sub-flow의 burstiness 상한이 (σ + L)/2임을 설명하라.

15.3 First-Come, First-Served Multiplexer
Section 15.2.2의 접근을 FIFO 방식의 multiplexer에 적용하라. 입력 flow가 각각 (σ₁, ρ₁), (σ₂, ρ₂)일 때, 최대 delay는 얼마인가?

15.4 Tree-Saturation의 영향
각각 processor와 memory module을 가진 p개의 노드가 존재한다고 하자. 각 노드는 일정 길이의 memory request를 생성하고, 이 중 h 비율은 “hot” memory location으로 향하고, 나머지는 균등하게 분산된다. hot memory로의 총 요청률은 얼마인가? hot module이 포화될 경우 모든 요청이 block된다고 할 때, p = 100, h = 0.01이라면 전체 시스템에서 활용 가능한 memory bandwidth의 비율은?

15.5 시뮬레이션
4×4 mesh network에서 TDM flow 예약을 고려하라. 시간은 T개의 slot으로 나뉘며, 각 flow는 하나의 slot을 요구한다. 각 flow는 source-destination 쌍에 대해 greedy 방식으로 가장 낮은 비용의 경로에 예약된다. 경로의 비용은 경로 상 모든 채널에서의 slot 사용량 중 최대값이다. 예약 품질은 가장 혼잡한 채널의 slot 수로 평가된다. 이 heuristic을 이용해 랜덤 연결을 예약하고, 식 (3.9)의 최적화 문제에 기반한 이론적 하한값과 비교하라.

Deadlock은 interconnection network에서 일반적으로 packet과 같은 여러 agent들이 서로 자원이 해제되기를 기다리며 더 이상 진행할 수 없는 상태를 말한다. 이들 대기 agent들의 순환이 형성되면 네트워크는 deadlock 상태에 빠진다. 간단한 예로 Figure 14.1을 보자. circuit-switched network를 통해 전송 중인 연결 A와 B는 각각 두 개의 channel을 점유하고 있으며, 세 번째 channel을 얻기 전까지는 진행할 수 없다. 하지만 서로 필요한 세 번째 channel은 상대가 점유하고 있어, 어떤 연결도 필요한 channel을 해제할 수 없다. 따라서 두 연결은 deadlock 상태에 빠지며, 외부 개입이 없으면 이 상태는 계속된다. Deadlock은 다양한 자원에 대해 발생할 수 있다. 여기서는 physical channel이지만, virtual channel이나 shared packet buffer에서도 발생 가능하다.

Deadlock은 네트워크에 치명적이다. 일부 자원이 deadlock된 packet들에 점유되면, 다른 packet들이 이 자원을 사용하지 못해 네트워크 전체가 마비될 수 있다. 이를 방지하려면 deadlock avoidance(네트워크가 절대 deadlock되지 않도록 하는 방식)나 deadlock recovery(deadlock 발생 시 이를 탐지하고 복구하는 방식)가 필요하다. 대부분의 현대 네트워크는 deadlock avoidance를 사용하며, 자원에 순서를 부여하고 packet이 이 순서를 따라 자원을 획득하도록 강제한다.

Livelock은 이와 밀접한 네트워크 병리 현상으로, packet이 계속 네트워크를 이동하지만 목적지에 도달하지 못하는 상태이다. 예를 들어 packet이 minimal이 아닌 경로를 허용받을 때 발생할 수 있으며, 이때는 deterministic 또는 probabilistic 방식으로 잘못된 경로 선택 횟수를 제한해야 한다.

14.1 Deadlock

14.1.1 Agent와 Resource

Deadlock에 관여하는 agent와 resource는 사용되는 flow control 방식에 따라 달라진다. Circuit switching의 경우 agent는 connection이고 resource는 physical channel이다. 연결이 설정되면 해당 경로의 모든 channel을 점유하며, 전송이 끝나기 전까지 해제하지 않는다. 따라서 하나의 연결은 여러 개의 channel을 무기한 점유할 수 있다.

Packet-buffer 방식(store-and-forward 또는 virtual cut-through 등)에서는 agent는 packet이며 resource는 packet buffer이다. Packet의 head가 네트워크를 따라 전파되며 각 노드에서 buffer를 획득해야 한다. 이 경우 packet은 한 시점에 하나의 buffer만 점유하며, 새 buffer를 얻은 후 이전 buffer는 일정 시간 내 해제된다.

Flit-buffer 방식에서는 agent는 역시 packet이지만, resource는 virtual channel이다. Packet의 head는 각 노드에서 virtual channel(control state와 flit buffer 포함)을 할당받으며, 여러 개의 virtual channel을 동시에 무기한 점유할 수 있다. 이는 하나의 virtual channel에 packet 전체를 담을 수 없기 때문이다.

14.1.2 Wait-For 관계와 Holds 관계

Agent와 resource는 wait-for 관계와 holds 관계로 연결된다. 예를 들어 Figure 14.1의 경우를 보자. Connection A는 channel u와 v를 점유하고 있고(waits for w), Connection B는 w와 x를 점유한 채(u를 기다림) 대기 중이다. 어떤 agent가 resource를 점유하고 있다면, 이 자원은 해당 agent가 해제해주길 기다리는 상태이다. 따라서 holds(a, b)는 waitfor(b, a)를 의미한다. 이 holds 관계를 반대 방향의 wait-for 관계로 다시 그리면 wait-for 그래프가 된다. Figure 14.2(b)의 사이클이 deadlock 상태임을 보여준다.

이처럼 agent와 resource 간의 엣지가 교차로 연결된 사이클이 존재할 때 deadlock이 발생한다. 즉,

1. Agent가 어떤 resource를 점유하고 있으면서, 다른 resource를 기다리고 있으며,
2. 이러한 관계가 순환(cycle)을 이루는 경우 (agent A₀가 R₀를 점유하고 R₁을 기다림, A₁이 R₁을 점유하고 R₂를 기다림, ..., Aₙ₋₁이 Rₙ₋₁를 점유하고 R₀을 기다림).

14.1.3 Resource Dependence

Wait-for 그래프에서 두 resource Ri와 Ri+1이 두 칸 떨어져 있다면, agent Ai가 Ri를 점유한 상태에서 Ri+1을 무한히 기다릴 수 있어야 한다. 이를 resource dependence라 하며 Ri → Ri+1 또는 Ri ⇒ Ri+1로 표현한다. Figure 14.1의 예에서는 u → v → w → x → u의 순환 관계가 존재한다. 이 관계는 전이적이며, a → b이고 b → c이면 a → c이다.

Figure 14.3의 resource dependence graph(자원 의존 그래프)는 각 resource가 vertex이며, 의존 관계는 방향 엣지로 표현된다. circuit switching에서는 physical channel 의존 그래프가 되며, packet-buffer 방식에서는 packet-buffer 의존 그래프, flit-buffer 방식에서는 virtual-channel 의존 그래프가 된다.

이러한 resource dependence graph에 사이클이 존재하면 deadlock이 발생할 가능성이 있다. 실제 deadlock이 발생하려면, agent가 자원을 점유하고 동시에 다른 자원을 기다리며 wait-for 그래프에 사이클을 만들어야 한다. 따라서 resource dependence graph의 사이클은 필요조건이지 충분조건은 아니다. Deadlock을 방지하기 위한 일반적인 전략은 이 graph에서 사이클을 제거하는 것이다. 그러면 wait-for 그래프에서 사이클이 생기지 않으며 deadlock도 방지된다.

14.1.4 예시

Figure 14.1의 4-node ring network를 packet-buffer flow control(노드당 하나의 packet buffer)로 바꿔 생각해 보자. 이 경우 agent는 packet이며 resource는 packet buffer이다. Figure 14.4(a)에 packet-buffer dependence graph가 나와 있다. 노드 0의 buffer(B₀)에 있는 packet은 buffer B₁을 얻기 전까지 B₀을 해제하지 않는다. 따라서 B₀ → B₁이라는 의존 관계가 생긴다.

Figure 14.4 설명

(a)는 packet-buffer flow control을 사용하는 네트워크의 resource(=packet buffer) dependence graph이다. 각 노드에 하나씩 있는 packet buffer(B0~B3)는 링 구조에서 다음 buffer를 점유하지 않으면 해제되지 않으므로 B0 → B1 → B2 → B3 → B0이라는 순환이 생긴다.

(b)는 이 상황에서 deadlock이 발생했을 때의 wait-for graph이다. 네 개의 packet(P0~P3)이 각각 하나의 buffer를 점유하고 있으며, 다음 buffer가 비워지기를 기다린다. Packet은 한 번에 하나의 buffer만 점유할 수 있으므로, 이와 같은 4개 packet 구성이 되어야 순환이 생기고 deadlock이 발생할 수 있다.

Flit-buffer flow control 예시 (Figure 14.5)

이제 동일한 4-node ring network를 flit-buffer flow control로 바꾸어 보자. 각 physical channel에 두 개의 virtual channel이 있다고 가정한다. Packet은 다음 채널에서 두 virtual channel 중 하나를 선택하여 대기할 수 있지만, 일단 선택한 channel에 대해 기다리며, 나머지 channel이 비어도 그쪽으로 바꾸지 않는다.

(a)는 각 virtual channel 간의 dependence를 보여주는 graph이며, 인접한 채널 간에는 모두 엣지가 있다.

(b)는 deadlocked 상태를 나타낸 wait-for graph이다. P0은 u0와 v0를 점유하고 w0를 기다리며, P1은 w0와 x0를 점유하고 v0를 기다린다. "1"로 끝나는 virtual channel은 사용되지 않는다. 만약 P0이 w0 또는 w1 중 사용 가능한 것을 선택할 수 있다면, 이 구성은 deadlock이 아니다. 모든 virtual channel 중 아무거나 사용할 수 있는 경우, deadlock 구성을 위해선 4개의 packet이 필요하며, 이는 연습문제로 제시된다.

14.1.5 High-Level (Protocol) Deadlock

Deadlock은 네트워크 외부 요인에 의해 발생할 수도 있다. Figure 14.6을 보자. 위쪽 network channel은 서버가 request packet을 제거해 주기를 기다리고 있는데, 서버는 내부 buffer가 제한되어 있어 reply packet이 먼저 소비되어야 request packet을 수신할 수 있다. 결과적으로 upper channel은 lower channel이 비워지기를 기다리는 셈이며, 이 wait-for 관계는 네트워크 내부가 아니라 서버 외부에 의해 생긴 것이다. 이러한 외부 요인에 포함된 wait-for loop에 의한 deadlock을 high-level 또는 protocol deadlock이라고 한다.

예를 들어 shared-memory multiprocessor에서는 각 노드의 memory server가 memory read/write request를 수신하고 처리 후 응답을 돌려보낸다. 내부 buffer가 제한적이면, Figure 14.6과 같이 서버로 들어오는 채널이 서버에서 나가는 채널을 기다리는 상황이 된다.

이런 외부 wait-for edge의 영향을 없애려면, 요청과 응답을 처리할 때 서로 다른 논리적 네트워크(logical network)를 사용하면 된다. 예: 서로 다른 virtual channel 또는 packet buffer 사용. 특히 cache-coherent 시스템에서는 하나의 transaction이 directory, owner, 다시 directory로 순차적으로 서버를 통과하기 때문에 각 단계마다 분리된 논리 네트워크를 사용하는 것이 일반적이다. 이는 Section 14.2에서 설명할 resource ordering의 특수한 경우이다.

14.2 Deadlock Avoidance

Deadlock은 resource dependence graph에 cycle이 없도록 만들면 방지할 수 있다. 이를 위해 자원에 대해 부분 순서(partial order)를 정의하고, agent가 이 순서를 따르도록 자원을 할당하도록 한다. 이렇게 하면, 순서상 높은 자원을 점유한 상태에서 낮은 자원을 기다리는 것이 금지되므로 cycle이 생기지 않는다. 일반적으로는 자원을 번호로 정렬하여 전체 순서(total order)를 적용한다.

모든 deadlock avoidance 기법은 어떤 형태로든 resource ordering을 사용하지만, 이 ordering이 routing에 미치는 영향은 다양하다. 어떤 방법은 routing에는 제한이 없고, 어떤 방법은 자원 수를 줄이기 위해 특정 경로를 허용하지 않기도 한다.

packet-buffer flow control에서는 노드마다 여러 개의 packet buffer가 있고, flit-buffer flow control에서는 하나의 physical channel에 여러 virtual channel이 있으므로, 동일한 물리 자원 내의 논리 자원에 순서를 부여함으로써 ordering을 구현할 수 있다. 하지만 circuit switching은 물리 채널 자체가 자원이므로, 각 채널이 ordering 내에서 한 위치만 차지할 수 있고, routing 제한이 불가피하다.

14.2.1 Resource Classes

Distance Classes: 자원을 class로 묶어 번호를 붙이고, packet이 자원을 할당할 때 오름차순으로만 접근하도록 제한하는 방식이다. 예: source에서 class 0의 자원을 할당받고, 이후 hop마다 class i+1의 자원만 할당할 수 있도록 한다.

이 시스템에서는 class i의 자원을 점유한 packet은 반드시 class i+1 자원을 기다려야 하므로, resource dependence graph에 cycle이 생기지 않는다. 따라서 deadlock이 발생하지 않는다.

Figure 14.8은 distance 기반 buffer class를 사용하는 4-node ring network의 예다. 각 노드 i는 hop 수 j에 따라 Bji buffer를 갖는다. 이 buffer는 j번 hop을 거친 packet을 수용하고, 다음 node i+1의 Bj+1,i+1로 전송한다. 이 구조는 spiral 형태의 비순환 의존 그래프를 만들어 deadlock을 방지한다.

이러한 "오르막" 자원 할당 규칙을 지키기 위해 packet은 현재 자신이 점유한 class 정보를 기억하고 있어야 한다. 따라서 distance class를 사용하는 경우 routing relation은 다음과 같이 정의된다:

R : Q × N → Q,
여기서 Q는 네트워크 내의 모든 buffer class 집합이다.

flit-buffer 방식에서도 유사하게 virtual channel에 이 방식을 적용할 수 있다. 이 hop-by-hop routing relation은 "오르막" buffer class 사용을 표현한다.

distance class는 어떤 topology에서도 자원 순서를 구현할 수 있는 일반적인 방법이지만, 단점은 네트워크의 지름(diameter)에 비례하는 수의 buffer나 virtual channel이 필요하다는 점이다.

Figure 14.8 설명

Distance class를 4-node ring network에 적용한 예이다. 각 노드 i는 4개의 buffer class를 가지며, buffer Bji는 목적지를 향해 j번 hop을 이동한 packet을 저장한다. 이 구조는 의존 그래프를 비순환적으로 만들기 때문에 deadlock을 방지할 수 있다.

Topology를 활용한 buffer class 최소화

어떤 네트워크에서는 topology를 활용해 필요한 buffer class 수를 크게 줄일 수 있다. 예를 들어, ring network에서는 두 개의 buffer class만으로도 자원을 순서화할 수 있다.

Figure 14.9 설명

Dateline buffer class를 ring에 적용한 예이다. 각 노드 i는 “0” buffer B0i와 “1” buffer B1i를 가진다. source 노드 s에서 주입된 packet은 B0s에 저장되고, dateline(노드 3과 0 사이)을 지날 때까지는 “0” buffer를 계속 사용한다. dateline을 지나면 “1” buffer(B10)를 사용하고 목적지까지 “1” buffer만 이용한다. 이 방식은 원형 의존 구조를 나선형 비순환 구조로 바꾸므로 deadlock을 방지할 수 있다.

Dateline 방식의 flit-buffer 적용 (Figure 14.10)

각 physical channel c는 두 개의 virtual channel c0, c1로 나뉜다. 모든 packet은 처음에 “0” virtual channel을 사용하고, dateline(노드 3)을 지나면 “1” virtual channel로 전환한다. 이때 routing function은 다음과 같은 형식을 가져야 한다:

R : C × N → C,
여기서 C는 virtual channel들의 집합이다.

이렇게 하면 Figure 14.5의 cyclic한 virtual channel dependence graph에서 일부 edge를 제거하여 acyclic하게 만들 수 있다.

Overlapping Resource Classes

distance class나 dateline class를 사용하면 resource dependence graph를 acyclic하게 만들 수 있지만, 부하 불균형(load imbalance)이 발생할 수 있다. 예를 들어 Figure 14.10에서 uniform traffic이 있을 경우, 대부분의 packet이 v0을 사용하고 v1은 거의 사용되지 않게 된다.

이러한 부하 불균형을 줄이기 위한 한 방법은 buffer class를 overlap시키는 것이다. 예를 들어, 32개의 packet buffer가 있을 때, 각 class에 16개씩 할당하는 대신 (Figure 14.11a), 각 class에 독점적인 buffer를 하나씩 두고 나머지 30개는 두 class가 공유하도록 구성할 수 있다 (Figure 14.11b). 이 방식은 대부분의 buffer를 공유함으로써 자원 활용률을 높일 수 있다.

그러나 overlap된 class에서 deadlock을 피하려면 중요한 조건이 있다. packet은 overlap 영역의 busy buffer를 기다려서는 안 된다. 즉, packet은 buffer B11과 같이 두 class가 모두 접근 가능한 buffer에 대해 기다려서는 안 된다. 그렇게 하면 다른 class의 packet과 교착 상태가 될 수 있기 때문이다.

해결 방법은 다음과 같다:

• packet은 특정 buffer가 아니라 class 자체에 대해 대기해야 한다.
• 즉, 해당 class에서 어떤 buffer든 idle 상태가 되기를 기다려야 하며, 독점 buffer가 결국 available해질 것이므로 deadlock은 발생하지 않는다.
• 만약 공유 buffer가 먼저 비게 된다면 이를 사용해 성능은 향상시킬 수 있다.

14.2.2 Restricted Physical Routes

resource를 class로 구성하여 deadlock을 방지하는 방식은 효과적이지만, 경우에 따라 많은 수의 자원이 필요할 수 있다. 이를 피하기 위한 대안은 routing function을 제한하는 것이다. 적절한 경로 제한을 통해 resource 간의 의존성을 줄이면, 적은 수의 resource class로도 cycle 없는 구조를 만들 수 있다.

Dimension Order (e-cube) Routing

deadlock을 피하기 위한 가장 간단한 routing 제한 중 하나는 k-ary n-mesh에서 dimension-order routing을 사용하는 것이다. 예를 들어 2D mesh에서는 다음과 같은 규칙이 있다:

• x 방향으로 +x로 이동 중인 packet은 +x, +y, −y 방향 channel만 대기 가능
• −x 방향 packet은 −x, +y, −y만 대기 가능
• y 방향에서는 +y는 +y만, −y는 −y만 대기 가능

이러한 제약을 기반으로 network의 channel을 나열하면 deadlock이 발생하지 않는다.

Figure 14.12 설명

3×3 mesh에서 dimension-order routing을 위한 channel numbering 예이다. 오른쪽 방향 channel을 먼저 나열하고, 그다음 왼쪽, 위, 아래 방향 순서로 번호를 매긴다. 이 방식은 routing 경로가 증가하는 번호의 channel을 따라가도록 보장하며, deadlock을 피할 수 있게 한다.

Turn Model

Dimension-order routing은 k-ary n-mesh network에서 deadlock 방지를 위한 routing 제약의 한 방식이지만, turn model은 mesh network에서 routing 알고리즘을 제약하는 좀 더 일반적인 프레임워크를 제공한다. turn model에서는 deadlock cycle을 구성하는 데 필요한 특정 방향 전환(turn)에 대해 정의하며, 2차원 예제로 설명이 시작된다.

Figure 14.13 설명 – Turn Model

(a) 2차원 mesh network에서 8개의 가능한 turn(예: +x → +y, +x → -y 등)이 있고, 이를 두 개의 추상적인 cycle로 나눌 수 있다. Deadlock을 피하려면 이 두 cycle 각각에서 최소 하나의 turn을 제거해야 한다.

(b) 예를 들어, +y → -x turn(North to West)을 제거하면 첫 번째 cycle을 깨뜨릴 수 있다.

(c) 여기에 두 번째 cycle에서 다른 turn을 추가로 제거함으로써 총 세 가지 deadlock-free routing 알고리즘을 만들 수 있다:

• West-first routing: South → West turn 제거. Packet은 West 방향으로 먼저 모두 이동한 뒤, 그 이후 다른 방향으로 이동 가능.
• North-last routing: North → East turn 제거. Packet은 North 방향을 제외한 다른 방향으로 자유롭게 이동 가능하지만, North로 들어선 후엔 계속 North로만 이동.
• Negative-first routing: East → South turn 제거. Packet은 South와 West 방향으로 먼저 이동한 후, North와 East 방향으로 이동.

이러한 turn 제한은 결국 resource ordering을 다르게 정의하는 것이며, dimension-order routing과 마찬가지로 total order를 만든다. Figure 14.14는 west-first routing이 적용된 3×3 mesh의 channel 순서를 보여준다.

Turn Model과 Dimension-Order Routing의 한계

이러한 deadlock-free routing 기법들은 routing 경로의 다양성을 줄여 네트워크 성능과 fault tolerance에 영향을 줄 수 있다. 특히 dimension-order routing은 경로 다양성을 0으로 만든다. 또한 torus와 같은 topology에서는 channel cycle을 제거할 수 없다.

14.2.3 Hybrid Deadlock Avoidance

지금까지의 방법은 자원을 나누고 번호를 부여하거나, routing path를 제한하여 deadlock을 피하는 방식이었지만 각각 단점이 있었다:

• Buffer class 방식: 노드당 많은 buffer 필요
• Routing 제한 방식: 경로 다양성 감소, 모든 topology에 적용 불가

현실적인 해결책은 두 방식을 혼합하는 것이다.

Torus Routing에서의 Hybrid 기법

Torus network에서는 각 dimension에 dateline class를 적용하고, 그 위에 dimension-order routing을 적용하면 deadlock을 피할 수 있다. dateline class가 torus를 mesh처럼 동작하도록 만들어주기 때문이다.

예: flit-buffer flow control에서는 각 physical channel에 두 개의 virtual channel을 둔다. Packet은 처음엔 virtual channel 0을 사용하고, 각 dimension의 dateline을 통과하면 virtual channel 1로 전환된다. 다음 dimension으로 넘어갈 때는 항상 다시 virtual channel 0에서 시작한다.

이처럼 virtual channel을 이용해 의존성을 끊고 다시 연결하는 방식은 다양한 상황에 일반화 가능하다.

예를 들어 Section 14.1.5에서 설명한 protocol deadlock에서도, 요청과 응답을 서로 다른 virtual channel로 분리하여 해결할 수 있다. underlying routing이 deadlock-free라면, request-reply protocol 자체가 deadlock을 만들지 않게 된다.

Planar-Adaptive Routing

이 기법은 virtual channel과 restricted physical route를 결합한 것으로, 제한된 adaptivity를 허용하면서도 channel dependence graph의 cycle을 방지한다.

• k-ary n-mesh에서 두 개의 인접 dimension (i, i+1)을 adaptive plane으로 정의
• 각 plane에서는 minimal adaptive routing을 허용
• plane 수는 n-1개이고, routing은 plane A₀ → A₁ → … → Aₙ₋₂ 순으로 진행

Figure 14.15 설명

• (a) k-ary 3-mesh에서 source와 destination 간 가능한 모든 minimal path
• (b) Planar-adaptive routing으로 허용된 path의 subset

이 방식은 network 크기나 dimension 수에 관계없이 virtual channel 수를 일정하게 유지하며, 경로 다양성은 상당 수준 확보된다.

Virtual Channel 구조

각 채널은 세 개의 virtual channel로 나뉘고, 각각은 di,v로 표시된다. 여기서 i는 dimension, v는 virtual channel ID.

• Plane Ai는 di,2, di+1,0, di+1,1을 포함
• Routing은 Ai에서 시작해, i번째 dimension이 목적지와 일치하면 다음 plane으로 이동
• 마지막 dimension까지 routing 후 packet은 목적지에 도달

deadlock-free를 보장하기 위해 각 plane 내의 virtual channel은 증가 방향과 감소 방향으로 나뉜다:

• 증가 방향: di,2⁺, di+1,0
• 감소 방향: di,2⁻, di+1,1

packet은 증가가 필요하면 증가 방향 채널만 사용하고, 감소 시에는 감소 방향 채널만 사용한다.

14.3 Adaptive Routing 

앞 절까지는 resource dependence graph에서 cycle을 제거하여 deadlock을 막는 구조였으며, 일부는 adaptive routing algorithm으로 자연스럽게 표현할 수 있다.

예:

• west-first routing은 packet이 west 방향으로 이동할지 여부를 network 상황에 따라 adaptive하게 결정할 수 있다.
• 일부 buffer class 기반 방법도 adaptive 요소를 포함할 수 있다.

그러나 이 절의 초점은 다음의 중요한 차이에 있다:

Adaptive routing은 cyclic resource dependence graph를 허용하면서도 deadlock-free가 될 수 있다.

이 개념은 path 다양성 감소 없이도 deadlock을 피할 수 있게 해 준다.

14.3.1 Routing Subfunctions and Extended Dependences

deadlock-free를 유지하면서도 cycle이 있는 dependence graph를 허용할 수 있는 핵심 아이디어는 다음과 같다:

모든 potential cycle에 대해 escape path를 제공하는 것이다.

즉, packet이 cycle에 갇힐 상황이 되어도, 탈출 가능한 deadlock-free 경로가 존재한다면 전체 네트워크는 deadlock-free 상태로 유지된다.

예제: 2D Mesh에서의 Escape Path 기반 Routing

flit-buffer flow control을 사용하고, 각 physical channel에 2개의 virtual channel을 둔 2D mesh를 예로 들어보자. channel은 xydv 형태로 표현되며, 이는 노드, 방향, virtual channel class를 의미한다. 예: 10e0는 node 10의 east 방향 virtual channel class 0이다.

Routing 규칙은 다음과 같다:

1. 모든 routing은 minimal이어야 한다.
2. class 1의 virtual channel(xyd1)은 어떤 방향의 어떤 class로도 route 가능
3. class 0의 virtual channel(xyd0)은 목적지에서 class 1으로만 route 가능
4. class 0의 virtual channel은 dimension order(x 먼저, 그다음 y)로만 class 0으로 route 가능

즉, source나 destination 중 하나라도 class 1이면 자유롭게 route 가능하지만, 둘 다 class 0이면 dimension order만 허용된다.

Figure 14.16은 위 규칙을 따르는 네 개 노드에 대한 virtual channel dependence graph를 보여준다. 00e0 → 10n0 → 11w1 → 01s1 → 00e0 의 cycle이 존재하지만, 각 packet은 escape path를 통해 cycle을 회피할 수 있다.

예를 들어 packet A는 00e0과 10n0을, packet B는 11w1과 01s1을 점유하고 있다고 하자. 만약 A가 11w1을 기다리고, B가 00e0을 기다리면 deadlock이 될 수 있다. 하지만 A는 11n0으로 route 가능하므로 escape path가 존재한다. 이러한 escape 경로가 있는 한, 그리고 packet이 busy 자원에 대해 기다리지 않는다면, deadlock은 발생하지 않는다.

Indirect Dependence

만약 규칙 1(minimal routing)이 없고 non-minimal routing이 허용된다면, indirect dependence에 의해 escape path에서도 cycle이 발생할 수 있다.

예를 들어 Figure 14.16에서 packet A가 00e0을 점유하고, packet B가 non-minimal 경로를 따라 10n0 → 11w1 → 01s1 을 점유하면, B는 00e0을 요구하게 되어, 00e0 → 10n0 → 11w1 → 01s1 → 00e0 형태의 indirect cycle이 형성된다.

이런 경우, escape path가 더 이상 deadlock-free를 보장하지 못한다.

해결 방법: escape channel 간에는 명시적인 순서를 부여하고, b ≼ a 인 escape channel로는 route를 금지한다. 예: class 1의 route는 minimal하게 제한함으로써 indirect dependence를 차단할 수 있다.

참고로, indirect dependence 문제는 flit-buffer flow control에서만 발생하며, packet-buffer flow control에서는 packet이 한 번에 하나의 buffer만 점유하므로 해당되지 않는다.

형식적 정의: Extended Dependence Graph

Adaptive routing을 위한 형식적인 deadlock-free 조건:

• 전체 routing relation R : C × N → P(C)
• escape routing subrelation R₁ ⊆ R, 해당 채널 집합 C₁ ⊆ C
• R₁은 connected하고, extended dependence graph에 cycle이 없어야 함
• 나머지 routing 관계는 Rᶜ = R − R₁

Extended Dependence Graph 정의:

• vertex: C₁에 속한 virtual channel
• edge:
  • direct dependence: ci → cj, if cj ∈ R₁(ci, x)
  • indirect dependence: ci → cj, 경로가 R₁ → Rᶜ(하나 이상) → R₁로 이어질 경우 발생

예: Figure 14.16에서 non-minimal 경로를 따라간 경우 indirect dependence가 발생

간단한 해결책: R₁에서 Rᶜ로의 전환을 금지하면 indirect dependence가 제거됨

Theorem 14.1 (Duato의 정리)

adaptive routing relation R이 deadlock-free가 되기 위한 조건:

연결된 routing subrelation R₁이 존재하고, R₁의 extended dependence graph에 cycle이 없다면 R은 deadlock-free이다.

이 정리는 wormhole flow control뿐 아니라 store-and-forward, cut-through network에도 적용된다. store-and-forward에서는 packet이 여러 채널을 동시에 점유할 수 없기 때문에 indirect dependence가 사라지고, direct dependence만 고려하면 된다.

14.3.2 Duato’s Protocol for Deadlock-Free Adaptive Algorithms

Duato의 정리는 이론적 기반을 제공하지만, 이를 실제 network 설계에 적용하는 구체적인 방법은 아래와 같다.

Duato의 프로토콜은 세 단계로 구성된다:

1. 기반 네트워크 설계: deadlock-free가 되도록 설계한다. 예: torus에서는 virtual resource를 추가해 cycle 제거
2. virtual resource 확장: 각 physical resource에 새로운 virtual resource를 추가한다.
   • wormhole: virtual channel
   • store-and-forward: buffer
     기존 virtual resource는 escape routing(R₁)을, 새로운 virtual resource는 일반 routing(Rᶜ)을 담당
3. flow control에 따른 제한:
   • packet-buffer flow control: Rᶜ에 제한 없음
   • flit-buffer flow control: R₁의 extended dependence graph가 acyclic해야 함

Duato의 방식은 보통 R₁을 dimension-order routing으로 설정하여 minimal adaptive routing 알고리즘을 구현하는 데 사용된다. 예를 들어, 3-ary 2-mesh에서 wormhole flow control과 함께 dimension-order routing을 escape path로 설정할 수 있다.

14.4 Deadlock Recovery

앞서 살펴본 방법들은 deadlock이 발생하지 않도록 사전에 방지하는 방식이었다. 이러한 방법은 routing 제약이나 자원 추가를 통해 cyclic dependence를 제거한다. 그러나 또 다른 접근법은 deadlock을 회피하지 않고, 발생 후 복구하는 것이다. 추가 자원 확보가 어렵거나 routing 제약에 따른 성능 저하가 우려되는 경우 이 접근법이 유리할 수 있다. 물론 deadlock이 드물게 발생하고 평균 성능이 중요할 때 적절하다.

deadlock recovery는 크게 두 단계로 나뉜다:

• 탐지(detection): 네트워크가 deadlock 상태인지 판단
• 복구(recovery): deadlock을 해제

탐지를 위해 wait-for graph 내 cycle을 찾는 것은 어렵고 비용이 크므로, 현실적 시스템에서는 보수적 탐지 방식을 사용한다. 보수적 탐지는 실제 deadlock인 경우는 반드시 탐지하지만, deadlock이 아닌 상태도 잘못 탐지할 수 있다(false positive). 일반적으로 timeout counter를 통해 구현한다. 각 자원에 counter를 설정하고, 전송이 발생하면 리셋한다. 일정 시간 동안 전송이 없으면 deadlock으로 간주하고 복구 단계를 시작한다.

14.4.1 Regressive Recovery

Regressive recovery에서는 deadlock된 packet이나 connection을 네트워크에서 제거한다.

예:

• circuit switching: 부분적으로 설정된 연결들 중 cycle을 형성한 경우 timeout이 초과되면 관련 연결을 해제하고 재시도한다.
• compressionless routing (wormhole 기반): flit이 끝까지 전송될 때까지 timeout을 측정하고, 시간 초과 시 해당 packet을 제거하고 재전송한다. 이를 위해 padding flit을 덧붙여 head가 목적지에 도달했음을 보장한다.

단점: 짧은 packet이 많을 경우 padding이 과도하게 들어가 throughput이 저하된다.

14.4.2 Progressive Recovery

Progressive recovery는 packet을 제거하지 않고 deadlock을 해제한다. 자원 낭비 없이 높은 성능을 기대할 수 있고, 반복 전송으로 인한 livelock 위험도 없다.

예: DISHA 아키텍처

• 각 노드에 shared escape buffer를 둠
• suspected deadlock 상황이 감지되면 해당 buffer를 통해 packet을 drain
• escape buffer는 deadlock-free routing sub-function에 의해 동작

Duato의 방식이 하드웨어로 구현된 예다. virtual channel이나 buffer가 값비싼 자원인 시스템에서는 이 접근이 유리하지만, 어떤 시스템에서는 shared buffer 도입 자체가 더 비쌀 수 있다.

14.5 Livelock

Livelock은 packet이 계속 움직이지만 목적지에 도달하지 못하는 상태이다. non-minimal routing에서 misroute 제한이 없으면 무한히 돌아다닐 수 있다. 또한 dropping flow control에서도 재입장 시마다 packet이 버려지면 목적지 도달이 불가능하다.

해결 방법:

• Deterministic avoidance: packet에 misroute 횟수 또는 age 기반 priority를 부여
  • misroute count가 임계값에 도달하면 더 이상 misroute 불가
  • age priority 방식은 일정 시간이 지나면 packet이 가장 높은 우선순위를 가지므로 도달 가능
• Probabilistic avoidance: packet이 T 사이클 동안 네트워크에 남아있을 확률이 T → ∞일 때 0으로 수렴하도록 설계
  • 예: 2-ary k-mesh, deflection routing, 단일 flit packet의 경우
    최대 이동 거리 Hmax = 2(k−1)
    history string에서 목적지 방향 이동 횟수 t와 deflection 횟수 d의 차이가 Hmax를 넘으면 도달 보장
    목적지 방향으로의 routing 확률이 항상 0보다 크다면, 결국 도달 확률은 1에 수렴

14.6 Case Study: Cray T3E에서의 Deadlock Avoidance

Cray T3E는 T3D의 후속 모델로, Alpha 21164 프로세서를 기반으로 최대 2,176개의 노드까지 확장 가능하다. topology는 3D torus이며, 기본적으로 8×32×8 3-cube로 구성되어 2,048개의 노드를 포함하며, 나머지는 redundancy 및 운영 체제 노드로 구성된다.

주요 설계 특징:

• T3E router는 CMOS ASIC으로 구현되어 ECL 기반보다 느리지만 latency 허용폭 증가로 보완
• adaptive routing을 사용하여 T3D의 dimension-order routing보다 throughput 향상 및 fault-tolerance 개선
• Duato의 protocol 적용
  • cut-through flow control 사용
  • 각 노드에는 최대 길이 packet을 저장할 수 있는 충분한 buffer 보유
  • 따라서 indirect dependence가 존재하지 않음 → routing sub-function이 deadlock-free면 전체도 deadlock-free

Routing sub-function: Direction-order routing

• +x → +y → +z → -x → -y → -z 순서
• packet header의 3비트를 통해 각 방향의 증가/감소 여부 지정
• +에서 −로는 전환 가능하나, −에서 +로는 불가 → mesh에서 deadlock 없음

Fault tolerance 향상 기법

• Initial hop: 시작 시 어느 증가 방향으로든 이동 가능
• Final hop: 모든 이동 후 −z 방향 허용
• Figure 14.18에서 faulty link를 우회하여 패킷이 목적지 도달 가능

Torus에서의 Deadlock 방지: Dateline 방식

• 각 dimension에 dateline 지정
• dateline을 넘는 packet은 VC0에서 시작해 dateline 이후 VC1로 전환
• dateline을 넘지 않는 packet은 VC0 또는 VC1 중 하나 선택
• VC 선택은 부하 균형을 목표로 최적화
  • 특정 physical channel의 VC별 packet 수를 균형 맞춤
  • Simulated annealing 기법으로 VC assignment 최적화 수행

Figure 14.18 설명

Figure 14.18은 direction-order routing 전에 initial hop을 허용함으로써 fault-tolerance가 어떻게 향상되는지를 보여준다. 회색 경로는 기본 direction-order routing이며, faulty channel(X 표기)을 통과한다. 그러나 −y 방향으로 initial hop을 한 후 우회 경로(굵은 선)를 통해 node 20에서 node 03으로 도달할 수 있다.

T3E의 virtual channel 구성 요약

• 2개 VC: torus 내 각 dimension의 dateline deadlock 방지
• 2개 VC: request / reply message용 별도 virtual network 구성 (high-level deadlock 방지)
• 1개 VC: minimal adaptive routing용
  → 총 5개 virtual channel이 T3E에서 사용됨

14.7 Bibliographic Notes

• 초기 deadlock-free 네트워크 연구에서는 자원을 번호 매겨 순서대로 접근하는 방식이 제안됨
• Linder와 Harden은 차원이 늘어날수록 필요한 virtual channel 수가 지수적으로 증가하는 adaptive routing deadlock-free 방법을 개발
• Glass와 Ni는 제한된 adaptivity를 허용하면서도 deadlock-free인 turn model을 제안
• Dally와 Aoki는 일부 non-minimal 경로와 제한된 dimension reversal을 허용하는 방법 제안
• Duato는 extended channel dependence graph를 도입하고, deadlock-free adaptive routing을 위한 이론을 확립
  • 이 방법은 Cray T3E, Reliable Router, Alpha 21364 등에 적용됨
• Planar adaptive routing은 제한된 자원으로 deadlock-free를 달성할 수 있는 구체적 예시
• Irregular topology에서는 up*/down* 알고리즘이 사용되며, DEC AutoNet에 적용된 바 있음
• Compressionless routing은 circuit switching 개념을 응용한 deadlock recovery 방식으로, Kim 등이 제안
• DISHA는 Duato 기반의 하드웨어 복구 방식
• VC 불균형 문제는 torus에서 특히 문제가 되며, Cray는 simulated annealing으로 VC 할당을 최적화함

14.8 Exercises (연습 문제 안내)

몇 가지 주요 연습문제 설명:

• 14.1: Figure 14.5의 네트워크에서 어떤 VC든 먼저 비는 쪽으로 선택 가능한 경우 deadlock configuration의 wait-for graph를 그려라.
• 14.2: 여러 oblivious routing 알고리즘이 deadlock-free인지 판단. channel dependence graph를 분석.
• 14.3: Figure 14.13(c)의 네 번째 turn 제거 방식이 왜 deadlock-free가 아닌지 설명.
• 14.4: turn model로 deadlock-free를 보장하려면 최소 몇 개의 turn을 제거해야 하는지 하한선 도출.
• 14.6: ring에서 dateline 방식의 virtual channel 불균형 문제를 해결하는 deadlock-free routing 알고리즘 설계.
• 14.7: planar adaptive routing이 k-ary n-mesh에서 deadlock-free임을 증명.
• 14.8: Fault-tolerant planar adaptive routing (FPAR)의 두 가지 case 분석을 통해 plane 간과 내부에서 deadlock-free를 보장하는지 검증.
• 14.9: Cray T3E의 direction-order routing이 deadlock-free임을 채널 나열로 증명하고, initial/final hop 확장이 deadlock-free인지 추가 검증.
• 14.10: dimension traversal 순서가 완전히 랜덤인 routing에서 n! VC 대신 적은 수로 deadlock-free를 유지할 수 있는 방법 찾기.
• 14.11: multi-flit packet이 있는 deflection routing에서는 probabilistic 방식이 livelock-free를 보장하지 않는 이유 설명.

네트워크에 버퍼를 추가하면 플로우 제어의 효율성이 크게 향상된다.
버퍼는 인접 채널들의 할당을 분리(decouple)시켜주기 때문이다.
버퍼가 없으면 두 채널은 연속된 사이클 동안 패킷(또는 flit)에 동시에 할당되어야 하며, 그렇지 않으면 패킷은 폐기되거나 잘못된 경로로 전달되어야 한다.
패킷이 머무를 곳이 없기 때문이다.
버퍼를 추가하면 두 번째 채널을 기다리는 동안 패킷(flits 포함)을 저장할 수 있어, 두 번째 채널의 할당을 지연시켜도 문제가 발생하지 않는다.

버퍼가 추가되면 플로우 제어 메커니즘은 채널 대역폭뿐 아니라 버퍼까지 할당해야 하며, 이들 자원을 어떤 단위(granularity)로 할당할지도 선택해야 한다.

그림 13.1과 같이, 버퍼와 채널 대역폭은 flit 또는 packet 단위로 할당할 수 있다.
대부분의 플로우 제어 방식은 두 자원을 동일한 단위로 할당한다.
패킷 단위로 채널 대역폭과 버퍼를 모두 할당하는 경우는 packet-buffer flow control이며, 이에는 store-and-forward flow control과 cut-through flow control이 있다 (13.1절에서 설명).
채널 대역폭과 버퍼를 모두 flit 단위로 할당하면, flit-buffer flow control이 된다 (13.2절에서 설명).
버퍼를 flit 단위로 할당하면 세 가지 주요 장점이 있다.

1. 라우터의 동작에 필요한 저장 공간이 줄어든다.
2. 혼잡한 지점에서 발생하는 backpressure가 출발지로 더 빠르게 전달된다.
3. 저장 공간을 더 효율적으로 사용할 수 있다.

그림 13.1에서 비대각선(off-diagonal) 조합은 일반적이지 않다.
예를 들어 채널을 패킷 단위로 할당하고, 버퍼를 flit 단위로 할당하는 경우는 동작하지 않는다.
전체 패킷을 전송하려면 그것을 수용할 수 있는 충분한 버퍼 공간이 필요하기 때문이다.
반대로, 버퍼를 패킷 단위로 할당하고 채널 대역폭을 flit 단위로 할당하는 조합은 가능하지만 드물다.
Exercise 13.1에서 이 방식을 더 자세히 다룬다.

13.1 Packet-Buffer Flow Control

라우팅 노드에 버퍼를 추가하면 채널 대역폭을 더 효율적으로 활용할 수 있다.
버퍼에 flit이나 packet을 저장하면, 입력 채널과 출력 채널 간의 자원 할당을 분리할 수 있다.
예를 들어 flit이 i 사이클에 입력 채널을 통해 전송되어 버퍼에 저장되었다면, 이후 j 사이클 동안 기다렸다가 i + j 사이클에 출력 채널이 할당되면 전송이 이루어진다.
버퍼가 없다면 flit은 i+1 사이클에 전송되거나 폐기되거나 잘못된 경로로 가야 한다.
버퍼를 추가하면 폐기나 misrouting으로 인한 채널 대역폭 낭비를 방지할 수 있으며, 회로 교환(circuit switching)에서의 유휴 시간도 제거할 수 있다.
따라서 buffered flow control을 통해 거의 100%에 가까운 채널 활용도를 달성할 수 있다.

버퍼와 채널 대역폭은 flit 또는 packet 단위로 할당할 수 있다.
먼저, 두 자원을 모두 packet 단위로 할당하는 store-and-forward 및 cut-through 플로우 제어 방식부터 살펴보자.

Store-and-Forward Flow Control

이 방식은 각 노드에서 패킷을 완전히 수신한 후에 다음 노드로 전달하는 구조다.
패킷을 전달하려면 두 가지 자원이 필요하다:

1. 채널 반대편 노드에 packet 크기의 버퍼
2. 해당 채널의 독점적인 사용

패킷이 도착하고 이 두 자원이 확보되면 다음 노드로 전달된다.
자원이 아직 준비되지 않았더라도, 채널은 유휴 상태가 아니며 현재 노드의 버퍼 한 개만 점유한다.

Figure 13.2는 5-flit 패킷이 충돌 없이 4-hop 경로를 따라 전달되는 store-and-forward 방식의 time-space diagram이다.
각 단계마다 전체 패킷이 한 채널을 지나고 나서 다음 채널로 전달된다.

이 방식의 주요 단점은 높은 지연(latency)이다.
각 홉마다 전체 패킷이 수신된 후에 다음 홉으로 이동하므로, 홉 수만큼 직렬화 지연(serialization latency)이 누적된다.
따라서 전체 지연 시간은 다음과 같다:

  H: 홉 수, tr: 홉당 라우터 지연, L: 패킷 길이(flits), b: 채널 대역폭

Cut-Through Flow Control

cut-through는 store-and-forward의 높은 지연을 줄이기 위한 방식이다.
패킷의 header가 수신되자마자 필요한 자원(버퍼와 채널)을 확보하면 즉시 전송을 시작한다.
패킷 전체가 도착할 때까지 기다리지 않는다.
이 방식도 버퍼와 채널 대역폭을 패킷 단위로 할당하지만, 각 홉마다 가능한 빨리 전송을 시작한다는 점이 다르다.

Figure 13.3(a)는 충돌 없는 경우, Figure 13.3(b)는 채널 2에서 3사이클 동안 충돌이 발생하는 cut-through의 time-space diagram이다.
자원이 곧바로 사용 가능하면 header 수신 즉시 다음 홉으로 전송된다.
충돌 시에는 channel 2가 사용 가능할 때까지 기다리지만, channel 1로의 전송과 버퍼링은 계속된다.

이 방식은 패킷이 가능한 빨리 전송되므로, 전체 지연이 아래와 같이 줄어든다:

cut-through는 높은 채널 활용도와 낮은 지연을 제공하지만, 두 가지 단점이 있다.

1. 버퍼를 패킷 단위로 할당하기 때문에 저장 공간의 효율성이 낮다.
    특히 deadlock 회피나 블로킹 방지를 위해 다수의 독립적인 버퍼 세트가 필요한 경우 비효율적이다.
2. 채널을 패킷 단위로 할당하므로 충돌 지연(contention latency)이 증가한다.
    예를 들어, 낮은 우선순위의 패킷이 먼저 채널을 점유하면, 높은 우선순위 패킷은 전체 패킷이 끝날 때까지 기다려야 한다.

다음 절에서는 자원을 packet이 아닌 flit 단위로 할당함으로써 버퍼를 더 효율적으로 사용하고 충돌 지연을 줄이는 방식을 다룬다.

13.2 Flit-Buffer Flow Control

13.2.1 Wormhole Flow Control

Wormhole flow control은 cut-through 방식과 유사하게 작동하지만, 자원을 packet이 아니라 flit 단위로 할당한다.
패킷의 head flit이 노드에 도착하면 다음 노드로 전달되기 전에 세 가지 자원을 확보해야 한다:

1. 해당 패킷을 위한 virtual channel (채널 상태)
2. 하나의 flit buffer
3. 하나의 채널 대역폭(flits worth)

패킷의 body flit은 이미 head flit이 할당한 virtual channel을 공유하며, flit buffer 하나와 채널 대역폭만을 추가로 확보하면 된다.
tail flit은 body flit과 동일하게 처리되지만, 전달되면서 virtual channel을 해제한다.

Virtual channel은 채널 상에서 패킷의 flit들을 처리하기 위한 상태 정보를 담고 있다.
최소한으로, 이 상태는 현재 노드의 출력 채널과 virtual channel의 상태(idle, waiting, active)를 포함한다.
추가적으로, 현재 노드에 버퍼된 flit들의 포인터나 다음 노드의 가용 flit buffer 수를 포함할 수도 있다.

Figure 13.4는 wormhole flow control을 이용해 하나의 노드를 통과하는 4-flit 패킷의 예를 보여준다.
그림 (a)~(g)는 사이클별 전달 과정을, (h)는 이를 요약한 time-space diagram이다.

• (a): 입력 virtual channel은 idle 상태이며, head flit이 도착한다. 원하는 upper 출력 채널은 busy 상태(L 입력에 할당됨).
• (b): head flit이 버퍼에 저장되고 virtual channel은 waiting 상태로 전환된다. 첫 번째 body flit이 도착.
• (c): head와 body flit이 버퍼에 저장되며, waiting 상태는 두 사이클 지속된다. flit buffer가 없어 두 번째 body flit은 입력 채널에서 멈춤.
• (d): 출력 채널이 사용 가능해지며 virtual channel이 active 상태로 전환되고, head flit이 전송된다.
• (e), (f): 나머지 body flit들이 순차적으로 전송됨.
• (g): tail flit이 전송되며 virtual channel은 idle 상태로 되돌아간다.

cut-through flow control과 비교하면, wormhole flow control은 훨씬 적은 수의 flit buffer만 필요로 하여 버퍼 공간의 효율성이 뛰어나다.
반면, cut-through는 여러 패킷 크기만큼의 버퍼 공간이 필요하며, 이는 wormhole보다 최소 한 자릿수 이상 큰 저장 공간을 요구한다.
하지만 이러한 버퍼 절약은 throughput의 일부 손실을 대가로 한다. wormhole은 패킷 중간에서 채널이 block될 수 있기 때문이다.

13.2.2 Virtual-Channel Flow Control

Virtual-channel flow control은 하나의 물리 채널에 여러 개의 virtual channels (channel state 및 flit buffer 포함)을 할당함으로써 wormhole flow control의 blocking 문제를 해결한다.
wormhole과 유사하게, head flit은 virtual channel, downstream flit buffer, 그리고 채널 대역폭을 할당받아야 한다.
body flit은 head flit이 확보한 virtual channel을 사용하지만, 여전히 buffer와 대역폭 확보가 필요하다.
그러나 wormhole과 달리, 이들은 대역폭 사용이 보장되지 않으며, 다른 virtual channel과의 경쟁이 발생할 수 있다.

virtual channel을 사용하면 blocking된 패킷을 다른 패킷이 우회할 수 있으므로, otherwise idle 상태인 채널 대역폭을 활용할 수 있다.

Figure 13.5는 2D torus 네트워크에서 패킷 A와 B가 충돌하는 상황을 보여준다.

• (a): wormhole flow control에서는 각 물리 채널당 하나의 virtual channel만 사용된다.
   패킷 B는 채널 p를 확보한 채 blocking되고, 패킷 A는 p를 할당받지 못해 channel p와 q가 비어 있음에도 진행 불가.
• (b): virtual-channel flow control을 적용해 각 물리 채널당 두 개의 virtual channel을 제공하면, 패킷 A는 node 2에서 두 번째 virtual channel을 확보해 channel p와 q를 사용하며 진행 가능.

이 상황은 다음과 같이 비유할 수 있다.
패킷 B는 막힌 사거리에서 좌회전을 기다리는 차량이고, 패킷 A는 뒤따르는 차량이다.
차로가 하나뿐이라면 A는 진행할 수 없지만, 좌회전 전용 차선을 추가하면 A는 B를 피해 직진할 수 있다.
이는 virtual channel이 물리적 채널의 대역폭을 증가시키지 않음에도 불구하고, 사용률을 높일 수 있음을 보여준다.

virtual channel flow control은 channel state의 할당을 채널 대역폭의 사용으로부터 분리(decouple)시킨다.
이 분리를 통해, 대역폭이 할당되어 있지 않더라도 채널 state만 가지고 있는 패킷에 의해 채널이 유휴 상태로 머무는 일이 방지된다.
결과적으로 wormhole보다 더 높은 throughput을 제공할 수 있으며, 동일한 총 버퍼 용량이 주어진 상황에서도, cut-through보다 우수한 성능을 보인다.
이는 여러 개의 짧은 flit buffer를 가진 virtual channel이 하나의 큰 packet buffer를 사용하는 cut-through보다 자원 사용 측면에서 더 효율적이기 때문이다.

Figure 13.6에서는 두 개의 virtual channel이 하나의 물리 채널을 공유하는 상황을 보여준다.
패킷 A와 B가 입력 1번과 2번을 통해 도착하고, 둘 다 동일한 출력 채널의 virtual channel을 확보한다.
두 패킷의 flit은 출력 채널에서 번갈아가며(interleaved) 전송되며, 각각 절반씩의 flit 주기를 사용한다.
패킷들이 입력에서는 full rate로 도착하지만 출력에서는 half rate로 나가므로, flit buffer는 포화되고 입력도 half rate로 제한된다.
입력에서의 간격(gap)은 물리 채널이 유휴 상태라는 뜻은 아니며, 다른 virtual channel이 이 시간대를 사용할 수 있다.

Figure 13.6은 두 개의 virtual channel이 하나의 물리 채널에서 flit을 교차 전송(interleave)하는 과정을 보여준다.
패킷 A는 입력 1번, 패킷 B는 입력 2번으로 동시에 도착하여 동일한 출력 채널을 요청한다.
두 패킷은 해당 출력 채널에 연결된 각자의 virtual channel을 확보하지만, flit 단위로 대역폭을 경쟁하며 사용해야 한다.
공정한 대역폭 분배가 이루어지면 두 패킷의 flit이 교대로 전송된다.
도착하는 flit 아래의 숫자는 각 virtual channel의 입력 버퍼에 저장된 flit 수를 나타내며, 버퍼 용량은 3 flit이다.
입력 버퍼가 가득 차면, 새로운 flit은 이전 flit이 나갈 때까지 차단된다.
출력 링크에서는 각 패킷의 flit이 격주기(every other cycle)로만 전송 가능하다.

Figure 13.7은 병목 링크(p)의 대역폭을 두 개의 virtual channel이 공유할 때 upstream과 downstream의 대역폭이 모두 절반으로 줄어드는 상황을 보여준다.
패킷 A(회색)와 B(검정)는 병목 링크 p에서 각각 50%의 대역폭만 사용한다.
병목 이후 downstream 링크에서는 이들 패킷이 최대 50%의 대역폭만 사용할 수 있으며,
병목 이전의 upstream에서도 node 1의 virtual channel 버퍼가 가득 차면 전송이 격주기로 제한되어 upstream 대역폭 역시 절반으로 줄어든다.
다른 virtual channel을 사용하는 패킷들은 이로 인해 남는 대역폭을 활용할 수 있다.

이러한 현상은 패킷의 길이가 길어질수록 source까지 blocking 현상이 전파될 수 있음을 의미한다.
한편, downstream에서도 사용되지 않는 idle 주기는 다른 패킷이 사용할 수 있다.

공정한 대역폭 할당 방식은 competing 패킷의 flit을 교차 전송하게 만들어 평균 latency를 증가시킨다.
반면, winner-take-all 방식은 하나의 패킷이 전송을 끝내거나 차단(blocked)될 때까지 모든 대역폭을 독점한 후, 다음 패킷으로 넘어가는 방식이다(Figure 13.8).

두 방식 모두 contention latency 총량은 같지만, winner-take-all 방식에서는 하나의 패킷이 지연 없이 빠르게 전송을 완료할 수 있다.
만약 먼저 전송되던 패킷이 도중에 block되면 채널은 즉시 다른 패킷에게 양도된다.
이처럼 공정하지 않은 대역폭 중재는 virtual-channel flow control에서 throughput 손실 없이 평균 latency를 줄일 수 있다.

Figure 13.9는 virtual channel을 구현하기 위해 복제되는 상태 정보를 나타낸 block diagram이다.
이 예시는 입력 포트 2개, 출력 포트 2개, 각 물리 채널당 2개의 virtual channel을 가진 라우터를 보여준다.

각 입력 virtual channel은 다음의 정보를 포함한다:

• channel status (idle, waiting, active)
• 현재 패킷에 할당된 출력 virtual channel 식별자
• flit buffer

각 출력 virtual channel은 할당 여부와 연결된 입력 virtual channel을 기록하는 상태 레지스터 하나만 가진다.

그림에는 다음 상태가 나타나 있다:

• 입력 virtual channel 1, 2: active 상태로, 상단 출력 virtual channel 1, 2로 패킷을 전송 중
• 입력 virtual channel 3: 출력 virtual channel을 기다리는 waiting 상태
• 입력 virtual channel 4: 아직 패킷이 도착하지 않은 idle 상태

virtual-channel flow control은 buffer를 2차원(virtual channels × flits per VC) 으로 구성한다.
입력당 고정된 수의 flit buffer가 있을 경우, 이를 어떻게 나눌지 선택할 수 있다.
예를 들어 입력당 16 flit의 저장 공간이 있으면, 다음과 같은 구성이 가능하다(Figure 13.10 참조):

• 하나의 virtual channel에 16-flit buffer
• 8-flit buffer를 가진 두 개의 virtual channel
• 4-flit buffer를 가진 네 개의 virtual channel
• 2-flit buffer를 가진 여덟 개의 virtual channel
• 1-flit buffer를 가진 열여섯 개의 virtual channel

일반적으로, virtual channel에 필요한 flit 수는 round-trip credit latency를 커버할 정도면 충분하며, 그 이상으로 깊게 만드는 것은 큰 성능 향상을 제공하지 않는다.
따라서, buffer 자원을 늘릴 때는 각 virtual channel의 flit 수를 늘리기보다는 virtual channel 수를 늘리는 것이 보통 더 효과적이다.

Virtual channel은 interconnection network의 다용도 도구(Swiss-Army™ Knife)와 같다.
block된 패킷을 우회시키는 데 사용될 수 있고(성능 향상), 다음 장에서는 deadlock 회피에도 활용된다.
네트워크 자체의 deadlock뿐 아니라 상위 계층 프로토콜 간의 종속성으로 인한 deadlock에도 대응 가능하다.
또한 virtual channel을 분리하여 서로 다른 priority traffic class에 대해 차등 서비스를 제공하거나, 목적지별로 트래픽을 분리함으로써 네트워크의 non-interfering 특성을 구현할 수도 있다.

13.3 Buffer Management and Backpressure

버퍼를 사용하는 모든 flow control 방식은 downstream 노드에 버퍼의 가용 여부를 알리는 수단이 필요하다.
그래야 upstream 노드는 다음 flit(또는 store-and-forward 및 cut-through 방식의 경우는 packet)을 보낼 때 버퍼가 비어 있는지를 알 수 있다.
이러한 버퍼 관리 방식은 downstream의 flit buffer가 가득 찼을 때 upstream 노드에게 전송을 중단하라는 backpressure를 제공한다.
현재 이러한 backpressure를 제공하기 위해 일반적으로 사용되는 저수준 flow control 방식은 다음 세 가지이다:

1. Credit-based
2. On/off
3. Ack/nack

각 방식을 차례로 살펴보자.

13.3.1 Credit-Based Flow Control

Credit-based flow control에서는 upstream 라우터가 downstream의 각 virtual channel에 존재하는 가용 flit buffer의 수를 세어 유지한다.
upstream 라우터가 flit을 전송하여 downstream buffer를 하나 사용하면, 해당 카운터를 감소시킨다.
이 카운트가 0이 되면 downstream buffer가 모두 가득 찼음을 의미하며, 새로운 flit은 buffer가 해제될 때까지 전송할 수 없다.
downstream 라우터가 flit을 전송하고 buffer를 해제하면, 해당 정보를 담은 credit을 upstream 라우터로 보내고, 이로 인해 카운터가 다시 증가한다.

Figure 13.11은 credit-based flow control의 타임라인을 보여준다.

시간 t1 직전, 채널의 downstream 끝 (node 2)의 모든 buffer는 가득 차 있다.
t1에서 node 2가 flit 하나를 전송하고, buffer 하나를 비우며 credit을 node 1로 보낸다.
credit은 t2에 도착하고, 짧은 처리 후 t3에서 flit이 전송되며, t4에 도착한다.
이어 t5에서 flit이 node 2에서 나가 buffer가 다시 비워지고, 새로운 credit이 다시 node 1로 보내진다.

t1에서 credit이 보내지고, t5에서 같은 buffer에 대한 credit이 다시 보내지기까지의 최소 시간이 credit round-trip delay (tcrt) 이다.
이는 wire delay와 양쪽 노드에서의 처리 시간을 포함하며, router의 성능에서 매우 중요한 매개변수이다.
만약 virtual channel에 단 하나의 flit buffer만 있다면, 매 flit 전송 전에 해당 buffer에 대한 credit을 기다려야 하므로, 최대 전송률은 tcrt당 1 flit이 된다.
즉, bit rate는 Lf / tcrt가 된다.
buffer 수가 F개라면, credit을 기다리기 전까지 F개의 flit을 보낼 수 있으므로, 전송률은 F flits per tcrt, 즉 F × Lf / tcrt 비트/초가 된다.

따라서, flow control이 채널 대역폭 b를 제한하지 않으려면 다음 조건이 필요하다:

Figure 13.12는 credit-based flow control의 동작을 flit 단위로 시각화한 것이다.

• (a): node 1은 node 2의 virtual channel에 대해 2개의 credit을 가지고 있다.
• (b): node 1은 head flit을 전송하고 credit 수는 1로 감소한다.
• (c): head flit이 node 2에 도착하고, 동시에 body flit이 전송되며 credit 수는 0이 된다.
• (d): node 1은 credit이 없기 때문에 flit을 더 이상 전송할 수 없다.
• (e): node 2는 head flit을 전송하여 buffer를 비우고, credit을 node 1에 보낸다.
• (f): credit이 도착하여 node 1의 credit 수가 증가하고, tail flit이 전송된다.
• (g): tail flit은 node 2로 전송되고 virtual channel이 해제된다.
• (h): tail flit이 node 2에서 전송되며, 마지막 credit이 node 1로 돌아온다.
• (i): 결과적으로 node 1은 다시 2개의 credit을 갖게 된다.

단점: 이 방식은 flit당 하나의 credit이 필요하므로, upstream으로의 신호량이 많아질 수 있으며, 특히 flit이 작을 경우 신호 오버헤드가 커진다.

13.3.2 On/Off Flow Control

On/off flow control은 경우에 따라 upstream 신호량을 크게 줄일 수 있다.
이 방식에서는 upstream 상태가 단일 제어 비트로 표현된다:

• on일 때: 전송 허용
• off 때: 전송 금지

이 상태가 바뀔 때만 신호가 전송된다.
예를 들어, control bit가 on인 상태에서 가용 buffer 수가 Foff 이하로 떨어지면 off 신호가 전송된다.
반대로 control bit가 off인 상태에서 가용 buffer 수가 Fon 이상으로 회복되면 on 신호가 전송된다.

Figure 13.13은 on/off flow control의 타임라인을 보여준다.

• t1: node 1이 flit을 전송하며, node 2의 가용 buffer 수가 Foff 미만이 된다. 이에 따라 node 2는 off 신호를 전송한다.
• off 신호가 도착하기 전까지, node 1은 계속 flit을 전송한다. 이 flit들은 off 신호가 전송되던 시점에 비어 있었던 Foff 개의 buffer에 저장된다.
• t6: node 2의 가용 buffer 수가 Fon 이상으로 증가하자 on 신호를 node 1로 보낸다.
• on 신호가 전송된 t6부터 node 1의 다음 flit이 도착하는 t9 사이 동안, node 2는 F − Fon개의 buffer에 저장된 flit을 전송한다.

Figure 13.13에서, flit이 t1에서 전송되며 node 2의 가용 버퍼 수가 Foff 미만으로 떨어지고, t2에서 off 신호가 전송된다.
이 신호는 t3에 node 1에 도착하며, 짧은 처리 시간 후 t4에서 flit 전송을 중단하게 한다.
t1과 t4 사이의 시간인 trt 동안 추가로 flit이 전송된다. 이 추가 flit이 buffer overflow를 일으키지 않도록 하려면 다음 조건을 만족해야 한다:

 Foff ≥ trt × b / Lf  (식 13.2)

그 후 node 2는 flit들을 전송하며 buffer를 해제하고, 가용 버퍼 수가 Fon을 초과하면 t6에서 on 신호를 전송한다.
이 on 신호는 t7에서 node 1에 도달하고, node 1은 t8에서 flit 전송을 재개한다.
이 on 신호로 인해 트리거된 첫 번째 flit은 t9에 도착한다.
이전과 마찬가지로, t6에서 t9 사이 동안 node 2가 전송할 flit이 부족해지지 않으려면 다음 조건이 필요하다:

 F − Fon ≥ trt × b / Lf  (식 13.3)

정리하면, on/off flow control이 제대로 동작하려면 최소한 다음 조건을 만족해야 한다:

 F ≥ 2 × trt × b / Lf

즉, 동작 자체를 위해서는 식 13.2가, full speed를 위해서는 식 13.3까지 만족해야 하며, 결과적으로 충분한 buffer 수가 확보되어야 upstream 신호량을 최소화할 수 있다.

13.3.3 Ack/Nack Flow Control

Ack/nack flow control은 credit-based 및 on/off 방식과 달리, buffer가 비워지는 순간부터 flit이 도착하는 시점까지의 지연을 최소한 0으로 줄일 수 있다.
평균적으로 buffer가 비워져 있는 시간은 trt / 2가 된다. 하지만 net 성능 향상은 없다.
flit 전송 후 ack을 기다리는 동안 buffer를 점유하므로 buffer 효율은 credit 방식보다 낮다.
또한, buffer가 없을 경우 flit을 폐기해야 하므로 bandwidth 효율도 떨어진다.

이 방식에서는 upstream 노드가 buffer 가용 상태를 유지하지 않는다.
대신, flit이 준비되면 낙관적으로(optimistically) downstream으로 전송한다.

• buffer가 있을 경우 → flit 수신 및 ack 전송
• buffer가 없을 경우 → flit 폐기 및 nack 전송

upstream 노드는 각 flit을 ack가 도착할 때까지 보관한다.
nack이 도착하면 해당 flit을 재전송한다.

여러 개의 flit이 동시에 전송되는 시스템에서는 flit과 ack/nack 간의 대응을 순서(ordering)로 유지한다.
하지만 nack이 발생하면 flit이 순서대로 도착하지 않을 수 있으므로, downstream 노드는 재전송된 flit이 도착할 때까지 이후 flit들을 임시 보관해야 한다.

Figure 13.14는 ack/nack flow control의 타임라인이다:

• t1: node 1이 flit 1을 보냄 → node 2는 buffer가 없어 flit 1을 폐기하고 nack 전송
• t2: flit 2가 전송됨
• t3: node 1이 nack을 수신하지만 flit 3을 이미 전송 중
• t4: flit 3 전송 완료 후 flit 1 재전송
• t5: flit 1 수신 → node 2는 순서를 유지하기 위해 flit 2와 3을 보관한 뒤 flit 1 수신 후 전송함

이 방식은 buffer와 bandwidth 사용 측면에서 매우 비효율적이기 때문에, 실제로는 거의 사용되지 않는다.
소규모 buffer 시스템에는 credit 방식, 대규모 buffer 시스템에는 on/off 방식이 보통 사용된다.

13.4 Flit-Reservation Flow Control

기존 wormhole 네트워크는 패킷 지연(latency)을 줄이는 데 효과적이지만, 이상적인 router 동작과 실제 pipeline 하드웨어 구현 간에는 차이가 있다.
Pipeline 구조에서는 flit 전송 단계가 여러 단계로 나뉘므로 hop 시간이 증가하고, 이로 인해 buffer 사용률도 영향을 받는다.

Figure 13.15는 credit-based wormhole flow control에서의 buffer 사용 예시이다:

1. flit이 현재 노드에서 다음 노드로 전송됨
2. 해당 buffer는 다음 hop으로 전송되기 전까지 점유됨
3. 이후 credit이 반대 방향으로 전송되고, wire propagation 시간 Tw,credit 소요됨
4. credit이 도착하면 pipeline delay 후 buffer 재사용 가능
5. 다음 flit은 credit을 받은 후 flit pipeline을 거쳐 다시 전송됨
6. flit은 다음 채널을 통해 Tw,data 시간 동안 전송되며 buffer에 저장됨

🧩 주요 타임라인 해석

1. Tw,data

• flit이 전송되어 다음 node에 도달하는 데 걸리는 wire propagation delay
• physical channel을 통해 flit이 전달되며, 이 기간 동안 buffer는 다음 node에 점유됨

2. Credit sent → Tw,credit → Credit received

• 다음 node에서 flit이 전송되고 나면, 해당 buffer가 비워짐
• 이 정보는 credit 신호로 원래 node로 전달됨
• 이 credit이 도달하는 데 걸리는 시간 = Tw,credit

3. Credit pipeline delay

• credit을 받아도 바로 사용할 수 있는 게 아니라, 라우터 내부 처리 지연 발생
• 이후 buffer는 다음 flit을 위해 다시 할당 가능

4. Flit pipeline delay

• credit을 받은 다음 flit도 바로 채널에 나갈 수 있는 게 아님
• flit pipeline을 통과해야 채널에 도달 가능

이러한 일련의 과정에서 buffer가 실제로 사용되는 시간은 전체의 일부에 불과하다.
남은 시간은 turnaround time이며, buffer가 실제로 활용되지 않는 시간이다.
turnaround time이 클수록 network throughput은 줄어든다.
Flit-reservation flow control은 turnaround time을 0으로 줄이고 flit pipeline 지연을 숨김으로써 throughput을 향상시킬 수 있다.

Flit-reservation 방식에서는 router의 제어 네트워크와 데이터 네트워크를 분리하여 pipeline 구현의 overhead를 숨긴다.
Control flit은 data flit보다 앞서 전송되며, 네트워크 자원을 미리 예약한다.
data flit이 도착할 때에는 이미 virtual channel 등의 자원이 예약되어 있어 지연 없이 전송이 가능하다.
이는 credit의 전달을 간소화하며, buffer의 turnaround time을 제거할 수 있다.

단, 혼잡 상태에서는 사전 예약이 불가능하므로, 이때는 일반 wormhole처럼 data flit이 자원이 예약될 때까지 대기한다.

Figure 13.16은 flit-reservation packet 구조를 보여준다:

• Control head flit에는 VC, type, routing 정보와 함께 td0라는 data offset 필드가 있다.
• 예: control flit이 t=3에 도착하고 td0=2이면, data flit은 t=5에 도착할 것으로 router는 예측 가능하다.
• 이를 통해 router는 data flit 도착 전에 자원을 예약할 수 있다.
• data flit에는 별도의 제어 필드가 필요 없다.

데이터 flit이 여러 개인 경우, 추가적인 control body flit이 head 뒤에 따라오며 각각의 data flit에 대응하는 offset 필드를 포함한다.

13.4.1 A Flit-Reservation Router

Figure 13.17은 flit-reservation router의 전체 구조를 보여준다.

그림에서는 간단히 하기 위해 단일 입력과 단일 출력만 표시되어 있으며, 입력과 출력 구조는 점선으로 분리되어 있다.

control flit이 라우터에 도착하면 routing logic으로 전달된다.
control head flit이 도착하면, 이 flit의 출력 virtual channel(다음 홉)이 계산되어 해당 입력 virtual channel과 연결된다.
이후 도착하는 control body flit들도 같은 출력 채널로 표시된다.

control flit이 출력 포트에 도달하면 output scheduler로 전달된다.
output scheduler는 control flit에 포함된 data offset 정보를 참조하여, 각 data flit의 buffer 공간을 다음 홉 라우터에서 예약한다.
다음 홉 라우터의 buffer 상태는 output reservation table에 저장되며, credit을 통해 지속적으로 업데이트된다.
모든 data flit의 예약이 완료되면 control flit은 다음 홉으로 전달된다.

control flit과 해당 data flit들을 라우터 내부에서 연결해주는 역할은 input reservation table이 담당한다.
control flit이 routing logic을 통과하면서 목적지 정보가 input reservation table에 기록된다.
각 data offset 값도 여기에 저장되며, output scheduler에서 예약이 완료되면 해당 정보가 다시 input scheduler에 전달된다.
input scheduler는 어떤 사이클에 buffer가 비워질지를 알고 있으므로, 그에 맞춰 flit을 전송할 수 있다.

13.4.2 Output Scheduling

output scheduler는 각 data flit의 미래 전송 시점을 결정한다.
data flit이 전송되기 위해서는 두 가지 조건을 충족해야 한다:

1. 물리적 출력 채널 예약
2. 다음 라우터에 충분한 buffer 공간 확보

이를 위해 output scheduler는 output reservation table을 관리하며, 앞으로 몇 사이클에 걸쳐 채널 사용 상태와 buffer 가용성을 추적한다.

Figure 13.18(a)는 output reservation table의 예시 상태다.
예를 들어, control flit이 t=0에 도착했고 data offset(td0)은 9라고 하자.
이는 data flit이 cycle 9에 도착함을 의미한다. 해당 정보는 output scheduler와 input reservation table로 전달된다.

output scheduler는 가능한 전송 시점을 찾는다:

• cycle 10은 채널이 이미 사용 중이므로 제외
• cycle 11은 buffer가 부족하므로 제외
• cycle 12가 최초의 유효한 전송 시점 → 예약 확정

따라서 output reservation table은 cycle 12의 채널 상태를 busy로 표시하고, 이후 cycle부터 buffer 수를 감소시킨다(Figure 13.18(b)).
추후 credit이 도착하면 buffer 수는 다시 복원된다.

control flit이 예약을 마치고 다음 홉으로 이동할 때, data flit의 상대적 전송 시간이 변경될 수 있다.
따라서 data offset(td0) 값을 업데이트해야 한다.
예를 들어 control flit이 다음 router에 t=2에 도착하고, data flit의 전송 시점이 cycle 12라면:

 td0 = 12 − 2 = 10

13.4.3 Input Scheduling

input scheduler와 input reservation table은 flit-reservation 라우터 내에서 data flit의 흐름을 관리한다.
control flit이 도착하면, 해당 data offset 정보를 통해 routing logic이 data flit의 도착 시간과 목적지 포트를 input reservation table에 기록한다(Figure 13.19 참조).

output scheduler가 data flit의 전송 시점을 결정하면, 이 정보는 input scheduler로 전달되고, input reservation table이 갱신된다.
또한 해당 정보는 credit 형태로 이전 노드에 전송되어 buffer 재사용 가능 시점을 알린다.

앞서 예시한 cycle 9에 도착하는 data flit은 cycle 10 초에 latching되어 기록된다.
cycle 12에 전송될 예정이므로 이 departure 시간도 table에 기록되며, 해당 포트 방향(East 등)도 함께 저장된다.

buffer 자체는 data flit이 도착하기 한 사이클 전에서야 실제로 할당되며, 이때 buffer in / buffer out 필드가 완성된다.

13.5 참고 문헌

• Cut-through flow control은 Kermani와 Kleinrock이 도입
• Wormhole flow control은 Dally와 Seitz에 의해 제안되어 Torus Routing Chip에서 처음 구현됨
• Virtual-channel flow control은 Dally가 refinement하여 제안
• 실제 적용 예시: Cray T3D, T3E, SGI Spider, IBM SP 네트워크
• Flit-reservation flow control은 Peh와 Dally가 개발함

13.6 연습문제

13.1 패킷 기반 buffer 할당 + flit 기반 채널 대역폭 할당의 장단점을 분석하고, cut-through와 다른 시간-공간 순서를 갖는 예제를 작성하라.

13.2 credit-based flow control의 overhead를 계산하라.
(조건: 패킷 길이 L, flit 크기 Lf, virtual channel 수 V)

13.3 입력 간 공유되는 buffer pool이 있는 라우터에서의 flow control 설계를 설명하라.
공정성을 위한 static + dynamic 할당 방식, signaling overhead 여부 포함.

13.4 입력 buffer pool이 single-ported인 flit-reservation router의 구조 수정 방안을 설명하고, 필요한 상태 정보가 있는지 기술하라.

13.5 flit-reservation에서의 동기화 문제: plesiochronous 시스템에서 발생할 수 있는 주기 삽입에 의한 제어/data misalignment 문제를 간단한 방법으로 해결하라.

Flow control은 네트워크 자원, 즉 channel bandwidth, buffer capacity, control state를 네트워크를 통해 전달되는 패킷에 어떻게 할당할지를 결정한다. 효과적인 flow-control 방식은 이 자원들을 효율적으로 할당하여 네트워크가 이상적인 bandwidth의 높은 비율을 달성하고, 낮고 예측 가능한 latency로 패킷을 전달할 수 있도록 한다. 반면, 비효율적인 flow-control 방식은 일부 자원을 유휴 상태로 방치하거나 다른 자원으로 비생산적인 작업을 하여 bandwidth를 낭비한다. 이런 경우, 제2장에서 다룬 것처럼, 네트워크는 이상적인 bandwidth의 극히 일부분만을 활용하며, latency도 높고 변동성이 크다.

Flow control은 자원 할당 문제 또는 경쟁 해결 문제로 볼 수 있다. 자원 할당 관점에서 보면, 패킷이 source에서 destination으로 진행하면서 channel, buffer, state 등의 자원이 할당되어야 한다. 같은 과정을 경쟁 해결 관점에서 보면, 예를 들어 두 개의 패킷이 같은 시간에 라우터의 서로 다른 입력에서 도착하여 동일한 출력을 요구할 때, flow-control 메커니즘은 경쟁을 해결하고 해당 channel을 하나의 패킷에 할당하며, 나머지 차단된 패킷은 다른 방식으로 처리한다.

가장 단순한 flow-control 메커니즘은 bufferless이며, 차단된 패킷을 임시 저장하는 대신 드롭(drop)하거나 잘못된 경로로 전송(misroute)한다. 그보다 조금 더 복잡하고 효율적인 방식은 circuit switching으로, 여기서는 패킷 헤더만 buffering한다. circuit switching에서는 패킷의 헤더가 payload보다 먼저 네트워크를 통과하며, 경로 상의 자원을 예약한다. 특정 노드에서 자원이 즉시 할당되지 않으면, 헤더는 해당 자원이 사용 가능해질 때까지 대기한다. 전체 경로(회로)가 예약되면 데이터를 전송할 수 있고, 사용 후에는 채널을 해제하여 회로를 종료한다. 이들 flow-control 메커니즘은 상대적으로 저렴한 저장 공간 사용을 피하려다 비싼 channel bandwidth를 낭비하기 때문에 효율성이 떨어진다.

더 효율적인 flow control은 네트워크 자원이 사용 가능해질 때까지 데이터를 buffering하여 달성할 수 있다. buffering은 인접한 채널 간의 자원 할당을 시간적으로 분리(decouple)시켜 제약을 줄이고 효율성을 높인다. buffering은 store-and-forward나 cut-through flow control처럼 packet 단위로 이루어질 수도 있고, wormhole 또는 virtual-channel flow control처럼 더 미세한 단위인 flit 단위로 이루어질 수도 있다. 큰 크기의 가변 길이 패킷을 고정 크기의 작은 flit으로 나누면, 각 노드에서 필요한 저장 공간을 크게 줄일 수 있다. 또한 flit 단위로 자원을 할당하면, 하나의 physical channel 위에 여러 개의 virtual channel을 구현하기가 쉬워져 blocking을 줄이고 throughput을 향상시킬 수 있다.

이번 장에서는 flow-control 문제(섹션 12.1), bufferless flow control(섹션 12.2), circuit switching(섹션 12.3)을 순서대로 다룬다. 이어지는 13장에서는 buffered flow-control 방식들을 설명한다. 이 두 장에서는 네트워크 내 자원의 할당에만 초점을 맞춘다. 14장에서 보듯이, deadlock-free 네트워크를 유지하기 위한 추가적인 제약 조건이 있으며, 또한 endpoint에서의 buffer memory 관리와 같은 자원 관리 문제, 즉 end-to-end flow control도 존재한다. 이들은 유사한 원리를 따르지만 본 장에서는 다루지 않는다.

12.1 자원과 할당 단위

인터커넥션 네트워크를 통과하기 위해서는 message가 channel bandwidth, buffer capacity, control state와 같은 자원을 할당받아야 한다. 그림 12.1은 하나의 네트워크 노드 내에서 이러한 자원들을 보여준다. 패킷이 노드에 도착하면 우선 control state가 할당되어야 한다. flow control 방식에 따라, channel당 하나의 control state만 존재할 수도 있고, 입력이 여러 패킷에 공유될 수 있다면 여러 개의 state가 존재할 수도 있다. control state는 패킷이 해당 노드 내에서 할당받은 자원과 노드 내 이동 상태를 추적한다. 다음 노드로 이동하기 위해서는 해당 노드의 출력 채널(output channel)에서 bandwidth를 할당받아야 한다. 일부 네트워크에서는 forward channel과 함께 반대 방향으로 흐르는 reverse channel의 bandwidth도 함께 할당된다. reverse channel은 일반적으로 acknowledgment나 flow-control 정보를 전달하는 데 사용된다. 또한 패킷이 노드에 도착하면 channel bandwidth가 사용 가능해질 때까지 buffer에 임시로 저장된다. 모든 flow-control 방식은 control state와 channel bandwidth의 할당을 포함하며, 일부 방식에서는 buffer 할당은 포함하지 않는다(12.2절에서 다룸).

그림 12.1
네트워크 노드 내 자원 할당

• Control state: 패킷의 channel/buffer 할당과 노드 내 진행 상태를 기록
• Channel bandwidth: flit을 다음 노드로 전송
• Buffers: channel bandwidth를 기다리는 동안 flit을 보관

자원 할당의 효율성을 높이기 위해, message를 control state 할당 단위인 packet으로 나누고, channel bandwidth 및 buffer capacity 할당 단위인 flit으로 다시 나눈다.

그림 12.2는 네트워크 자원이 할당되는 단위를 보여준다. 가장 상위의 message는 source terminal에서 destination terminal로 전달되는 논리적으로 연속된 비트 그룹이다. message는 길이가 임의적이므로 직접 자원이 할당되지는 않으며, 대신 길이가 제한된 하나 이상의 packet으로 나뉜다. packet의 길이를 제한하면 자원 할당의 크기와 지속 시간도 제한되며, 이는 flow control 메커니즘의 성능과 기능성 측면에서 중요하다.

packet은 routing 및 순서 지정의 기본 단위이다. packet 단위로 control state가 할당된다. 그림 12.2에서 보이듯이 packet은 message의 일부에 packet header가 앞에 붙어 구성된다. packet header는 routing information(RI)과 필요 시 sequence number(SN)를 포함한다. RI는 source에서 destination까지 패킷의 경로를 결정하는 데 사용되며, 이는 목적지 필드나 source route 등 다양한 형태일 수 있다(8장에서 설명됨). 패킷이 순서를 잃을 수 있는 경우에는 SN이 필요하다. 예를 들어, 서로 다른 경로를 통해 전달되는 경우가 이에 해당한다. 순서가 보장된다면 SN은 필요하지 않다.

packet은 다시 flow control digit 또는 flit으로 나뉜다. flit은 대부분의 flow control 방식에서 bandwidth 및 storage 할당의 기본 단위이다. flit은 routing 및 sequencing 정보를 포함하지 않으며, 따라서 같은 경로를 따라 순서를 유지해야 한다. 하지만 여러 개의 패킷이 하나의 physical channel을 통해 동시에 전송될 수 있는 시스템에서는 flit이 virtual-channel identifier(VCID)를 포함할 수 있다. 이는 flit이 어떤 packet에 속하는지를 나타낸다.

flit의 위치에 따라 head flit, body flit, tail flit, 또는 이들의 조합이 될 수 있다. head flit은 packet의 첫 번째 flit이며 routing 정보를 포함한다. 이후에 0개 이상의 body flit과 tail flit이 뒤따른다. 매우 짧은 packet의 경우 body flit이 없을 수 있으며, 극단적으로는 단일 flit로 이루어진 packet의 경우 head flit이 tail flit 역할도 한다. 패킷이 네트워크를 통과할 때 head flit은 해당 패킷을 위한 channel state를 할당하며, tail flit은 이를 해제한다. body와 tail flit은 routing이나 sequencing 정보를 가지지 않기 때문에 head flit을 따라가며 순서를 유지해야 한다.

flit은 다시 하나 이상의 phit(physical transfer digit)으로 나뉜다. phit은 한 클록 사이클 동안 channel을 통해 전송되는 정보의 최소 단위이다. 자원이 phit 단위로 할당되지는 않지만, link level protocol은 channel 상의 phit을 해석하여 flit의 경계를 파악해야 한다.

왜 flit으로 packet을 나누는가? 모든 자원 할당(channel state, buffer capacity, channel bandwidth)을 packet 단위로 할 수도 있다. 실제로 이 방식을 사용하는 flow control 정책들도 있다. 하지만 이들은 packet 크기 선택에 있어 상충되는 제약을 겪는다.

패킷 크기를 키우면 routing 및 sequencing에 드는 overhead를 분산할 수 있다. 반면, 패킷 크기를 작게 하면 자원을 더 세밀하게 효율적으로 할당할 수 있고 blocking latency를 줄일 수 있다. flit을 도입하면 이러한 상충을 제거할 수 있다. 패킷은 비교적 크게 유지하면서도 flit을 매우 작게 만들어 자원을 효율적으로 사용할 수 있다.

크기에 대한 명확한 규칙은 없지만, 일반적으로 phit은 1비트에서 64비트 사이이며, 보통 8비트이다. flit은 보통 16비트(2바이트)에서 512비트(64바이트) 사이이고, 일반적으로 64비트(8바이트)이다. packet은 보통 128비트(16바이트)에서 512킬로비트(64킬로바이트) 사이이며, 보통은 1킬로비트(128바이트)이다. 이러한 일반적인 크기를 기준으로 할 때, 하나의 64비트 flit은 8개의 8비트 phit으로 구성되고, 하나의 1킬로비트 packet은 16개의 64비트 flit으로 구성된다.

12.2 Bufferless Flow Control

가장 단순한 형태의 flow control은 buffering 없이 작동하며, channel state와 bandwidth만 경쟁하는 패킷에 할당한다. 이 경우 flow-control 방식은 arbitration을 수행하여 어떤 패킷이 요청한 채널을 사용할지를 결정해야 한다. arbitration 이후, 선택된 패킷이 해당 채널을 통해 전진한다. 이때 실패한 패킷은 buffering이 없기 때문에 보류할 수 없으며, 드롭(drop)하거나 잘못된 경로로 전송(misroute)해야 한다.

예를 들어, 그림 12.3(a)의 상황을 보자. 두 개의 패킷 A와 B가 bufferless 네트워크 노드에 도착하여 둘 다 출력 채널 0을 요청한다. 그림 12.3(b)는 드롭 방식의 flow control로 이 충돌을 처리하는 방식을 보여준다. 여기서는 A가 arbitration에서 승리하여 출력 링크를 통해 전진하고, B는 패배하여 폐기된다. 이때 B를 이 지점까지 전진시키는 데 사용된 channel bandwidth 등의 자원은 낭비된다. B는 source에서 다시 전송되어야 하며, 이 source는 B의 buffered 복사본을 갖고 있어야 한다고 가정한다. 또한, B가 성공적으로 수신되었는지 또는 재전송이 필요한지를 알려주는 acknowledgment 메커니즘도 필요하다. 대안으로, 그림 12.3(c)처럼 B를 다른 출력 채널로 misroute할 수도 있다. 이 경우에는 충분한 경로 다양성과 목적지까지 재경로 지정할 수 있는 라우팅 메커니즘이 필요하다.

그림 12.4는 그림 12.3(b)의 드롭 방식 flow control에 대해 explicit negative acknowledgment(NACK)를 사용하는 time-space 다이어그램이다. 이 도표는 Gantt 차트처럼 수직 축에는 자원(채널)의 사용을, 수평 축에는 시간을 나타낸다. 다이어그램에서는 5-flit 패킷이 4-hop 경로를 따라 전송되는 과정을 보여준다. 수직축에는 네 개 채널(03)의 forward(F) 및 reverse(R) 방향이 교차로 표시되고, 수평축은 flit cycle(017)을 나타낸다. 첫 번째 전송에서 패킷은 채널 3을 할당받지 못해 드롭되며, 이로 인해 NACK가 reverse 채널을 통해 source로 전달되고, 그에 따라 재전송이 시작된다.

패킷 전송은 cycle 0에서 head flit(H)이 채널 0을 통과하며 시작된다. body flit(B)은 cycle 1~3에서 따라오고, tail flit(T)은 cycle 4에서 따라온다. 이 경우 tail flit은 아직 acknowledgment를 받기 전이므로 채널 0을 해제하지 않는다. cycle 1과 2에서는 head flit이 채널 1과 2를 통과하지만, 채널 3에서 경쟁에 부딪혀 할당에 실패하고 드롭된다. 이 실패를 알리기 위해, 채널 2의 반대편 라우터가 cycle 3에서 NACK를 reverse 방향으로 보낸다. 이 NACK는 cycle 4와 5에 걸쳐 채널 1과 0의 reverse 방향을 통해 source에 도달하며, 경유하는 각 노드에서 자원을 해제시킨다.

source가 NACK를 받은 후, cycle 6에서 패킷을 재전송한다. 재전송된 패킷은 목적지까지 필요한 4개 채널을 모두 할당받아 전달된다. head flit은 cycle 9에 목적지에 도달하고, tail flit은 cycle 13에 도달한다. 이후 cycle 14에 acknowledgment(A)가 reverse 채널을 통해 전송되며, cycle 17에 source에 도착한다. acknowledgment가 도달할 때마다 해당 노드에서 자원이 해제된다.

2장에서 구현한 dropping flow control은 NACK를 사용하지 않는다. 대신 timeout을 통해 패킷이 드롭되었음을 감지한다.

그림 12.5는 이를 보여준다. 패킷은 처음 전송에서 채널 3 할당에 실패하지만, NACK 없이 채널 0~2까지는 계속 전송되고 tail flit이 통과할 때 자원을 해제한다. 따라서 채널 0, 1, 2는 각각 cycle 5, 6, 7에 해제된다.

timeout이 경과하고도 acknowledgment를 받지 못하면, source는 cycle 12에서 패킷을 재전송한다. 이 재전송은 cycle 15~19에 걸쳐 성공적으로 이루어지고, cycle 20에 acknowledgment가 전송되어 cycle 23에 도착한다. 이 방식에서는 tail flit 이후 자원이 해제되므로 acknowledgment도 reverse 채널에서 경쟁해야 하며, 경우에 따라 acknowledgment 자체가 드롭될 수도 있다. 이 경우, 비록 패킷이 정확히 수신되었더라도 재전송이 발생한다. 중복 패킷을 제거하고 정확히 한 번만 수신되도록 하기 위해 수신 측에서는 보통 sequence number 기반 메커니즘이 필요하다.

dropping flow control은 구조는 단순하지만, 나중에 드롭될 패킷에 bandwidth를 낭비하므로 매우 비효율적이다. explicit NACK 없이 dropping flow control의 throughput 계산 방법은 2장에서 다루었다.

한편, 그림 12.3(c)와 같은 misrouting은 패킷을 드롭하지는 않지만, 잘못된 방향으로 전송하여 bandwidth를 낭비한다. 어떤 경우에는 offered traffic이 임계점에 도달하면 네트워크 throughput이 오히려 감소하는 불안정성(instability)으로 이어질 수 있다. misrouting은 패킷이 잘못된 경로에서도 목적지까지 도달할 수 있도록 충분한 경로 다양성이 있는 네트워크에서만 가능하다. 예를 들어, butterfly 네트워크에서는 하나의 잘못된 hop만으로도 패킷이 도착할 수 없기 때문에 misrouting이 불가능하다. torus 같은 충분한 경로 다양성이 있는 네트워크에서는 misrouting이 가능하지만, 너무 자주 misroute되면 목적지에 가까워지지 않고 계속 순환하는 livelock 문제가 발생할 수 있다. 따라서 misrouting을 포함한 flow control 정책은 모든 패킷이 결국 전달된다는 forward progress 보장이 필수적이다.

12.3 Circuit Switching

Circuit switching은 bufferless flow control의 일종으로, 먼저 source에서 destination까지의 채널을 할당하여 circuit을 형성한 뒤, 하나 이상의 패킷을 그 위로 전송하는 방식이다. 더 이상 보낼 데이터가 없으면 circuit을 해제한다. 그림 12.6은 이 과정을 네 단계로 보여준다.

• 첫 번째 단계 (cycle 0~4): source에서 destination까지 request(R)가 전파되어 채널을 할당한다. 이 예시에서는 충돌 없이 바로 목적지까지 도달한다.
• 두 번째 단계 (cycle 6~10): circuit이 할당되면, acknowledgment(A)가 source로 되돌아온다.
• 세 번째 단계: acknowledgment가 도착하면 circuit이 완전히 설정되어 이후 별도의 제어 없이 임의 개수의 데이터를 보낼 수 있다. 예시에서는 4-flit 패킷 두 개가 전송되고, 그 사이에 idle cycle 3개씩 삽입되어 있다.
• 네 번째 단계 (cycle 26~30): 더 이상 보낼 데이터가 없으면 tail flit(T)을 전송하여 채널을 해제하고 circuit을 종료한다.

Circuit switching은 dropping flow control과 달리, request flit이 차단되면 드롭되는 것이 아니라 해당 위치에 유지된다. 그림 12.7은 그림 12.6과 동일하지만 request가 채널 3을 할당받기까지 4 cycle 동안 지연되는 예시를 보여준다. 이 기간 동안 head flit은 block되어 있으며, 채널 3의 근접 라우터에서 유지되면서 반복적으로 재-arbitrate를 수행한다.

그림 12.6 설명
5-hop 경로 상에서 두 개의 4-flit 패킷을 circuit switching으로 전송한 time-space 다이어그램이다. 경합은 없으며, tr = 1 cycle, D = 0이다. 전송은 네 단계로 이루어진다.
1단계: request(R)가 목적지까지 전파되며 각 hop에서 채널 상태를 확보한다.
2단계: request가 목적지에 도달하면, acknowledgment(A)가 reverse 채널을 따라 source로 되돌아온다.
3단계: acknowledgment가 source에 도착하면, data flit(D)이 예약된 채널을 따라 전송된다. 이 circuit이 열려 있는 동안에는 추가적인 패킷도 전송 가능하다.
4단계: tail flit(T)이 경로를 지나면서 채널을 해제한다.

channel 3에 대한 접근을 위해 head flit은 매 cycle마다 시도하며, 결국 cycle 7에서 채널 3을 획득하고 circuit 할당을 계속 진행한다. dropping flow control과 비교할 때, circuit switching의 장점은 패킷을 드롭하지 않고 자원을 낭비하지 않는다는 점이다. 각 hop에서 header를 버퍼링하기 때문에 항상 forward progress를 보장한다. 그러나 circuit switching은 latency가 크고 throughput이 낮은 단점이 있어, buffered flow control에 비해 덜 매력적일 수 있다.

그림 12.6과 12.7의 time-space diagram을 보면, circuit switching으로 하나의 패킷을 전송할 때의 zero-load latency는 다음과 같다:

(여기서 wire latency는 무시함)

• 첫 번째 항: 경로 설정 및 head flit 전송에 걸리는 시간 (경합 없음 가정)
• 두 번째 항: serialization latency
• 세 번째 항: 전파 시간(time of flight)
• 마지막 항: 경합 시간

이 식은 식 3.11에서 주어진 header latency의 3배가 되는데, 그 이유는 source에서 destination까지 경로를 세 번 통과해야 하기 때문이다. (회로 설정 요청, acknowledgment, 실제 데이터 전송)

그림 12.7 설명
경합이 존재하는 circuit switching의 time-space 다이어그램. 그림 12.6과 동일한 상황이지만, request가 cycle 3~6 동안 block되다가 cycle 7에서야 channel 3을 할당받는다.

이러한 세 번의 경로 통과는 짧은 패킷 하나만 전송하는 경우 latency에 큰 영향을 준다.
또한 throughput도 낮아지는데, 이유는 채널이 예약된 시간이 실제 데이터가 전송되는 시간보다 길기 때문이다. 예를 들어 단일 패킷이 전송될 경우, 각 채널은 다음과 같은 시간 동안 점유된다:

• setup 시간 2Htr 동안 채널은 유휴 상태이다.
• 이 시간 동안 다른 회로에 할당될 수도 없고, 현재 회로도 아직 데이터를 보내지 못하므로 bandwidth 낭비가 발생한다.
• 특히 단기간의 회로에서는 이 오버헤드가 상당히 크다.

Circuit switching의 장점은 매우 간단하게 구현 가능하다는 것이다.
라우터의 로직은 2장에서 설명한 dropping flow control 라우터와 거의 유사하며,

• 각 입력에 request를 유지하기 위한 레지스터와
• reverse 경로만 추가하면 된다.

12.4 참고 문헌 메모 (Bibliographic Notes)

• Circuit switching은 전화망에서 기원하였으나, 현대의 인터커넥션 네트워크에서는 흔히 사용되지 않는다.
• Dropping flow control은 비효율적이지만 단순하여, BBN Butterfly(섹션 4.5)와 그 후속 모델인 BBN Monarch(섹션 23.4)에서 사용되었다.
• Misrouting (deflection 또는 hot-potato routing이라고도 함)은 Baran[12]에 의해 소개되었고, HEP Multiprocessor[174]와 Tera Computer System[9]에서 사용되었다.

12.5 연습문제

12.1 Dropping flow control with explicit nacks
섹션 12.2 및 그림 12.4에서 설명한 explicit NACK을 사용하는 dropping flow control 방식에 대해, 네트워크 throughput의 최대 상한(용량의 비율로)을 구하라. 최대 패킷 길이는 F flits, 평균 hop 수는 H_avg, uniform 트래픽, 대칭 토폴로지를 가정하라.

12.2 Timeout interval for dropping flow control
섹션 12.2 및 그림 12.5에서 설명한 timeout을 사용하는 dropping flow control 방식에 대해, 최대 패킷 길이가 F flits이고 네트워크의 각 hop이 하나의 flit 시간(cycle)을 요구한다고 할 때, 최소 timeout 간격을 F, 네트워크 diameter를 이용하여 표현하라.

12.3 Livelock with dropping flow control and timeout
timeout 기반 dropping flow control에서는 acknowledgment를 위한 reverse 채널이 예약되지 않으므로, acknowledgment도 경합으로 인해 드롭될 수 있다. 이로 인해 발생할 수 있는 livelock 문제를 설명하고, 간단한 해결책을 제안하라.

12.4 Optimistic circuit switching
optimistic circuit switching 기법은 header와 함께 데이터를 speculative하게 전송함으로써 zero-load latency를 줄일 수 있다. 만약 header가 차단되면, 데이터는 드롭되고 NACK이 부분적으로 예약된 경로를 따라 되돌아간다. 반대로 header가 성공하면, 데이터는 회로가 설정되자마자 목적지에 도달한다. speculative 데이터가 드롭되는 경우와 그렇지 않은 경우 각각에 대해 time-space 다이어그램을 그려라. tr = 1 cycle, D = 0으로 가정한다. 이 방식이 idle 상태의 예약 채널을 줄일 수 있는가? 그렇다면 얼마나 줄일 수 있는가?

12.5 Reservation circuit switching
기존 circuit switching과 유사하지만, request 메시지가 각 채널을 미래의 일정 시간 동안 (예: 15 cycle 후부터 10 cycle 동안) 예약하는 방식의 flow control을 생각하자. 경로상의 각 라우터는 request가 수용 가능할 경우 예약을 수행한다. 만약 불가능하다면 NACK을 보내 연결을 위한 기존 예약을 모두 취소하고 다시 시도한다. request가 목적지까지 도달하면, acknowledgment가 source로 전송되어 모든 예약을 확정한다. reservation circuit switching이 기존 방식보다 유리함을 보여주는 상황의 time-space 다이어그램을 그려라.