A Period-Aware Routing Method for IEEE 802.1Qbv TSN Networks

이 문서는 “A Period-Aware Routing Method for IEEE 802.1Qbv TSN Networks” 논문을 상세히 분석하고 요약한 것입니다.

1. 서론 (Introduction)

배경

• TSN (Time-Sensitive Networking): 산업 제어, 자동차 네트워크 등에서 요구되는 저지연(low-latency), 저지터(low-jitter) 통신을 보장하기 위한 이더넷 표준 기술.
• IEEE 802.1Qbv: TSN의 핵심 표준 중 하나로, 시간 인식 셰이퍼(Time-Aware Shaper)를 정의함. 이는 미리 계산된 스케줄에 따라 트래픽을 전송하여 결정론적 통신을 가능하게 함.
• 문제점: 좋은 스케줄을 만들기 위해서는 라우팅(Routing), 즉 각 데이터 흐름(Flow)의 경로를 먼저 결정해야 함. 라우팅 결과가 스케줄링의 품질, 즉 얼마나 많은 흐름을 수용할 수 있는지(schedulability)에 큰 영향을 미침.

기존 연구의 한계

1. 최단 경로 라우팅 (Shortest Path Routing): 가장 널리 쓰이지만, 특정 경로에 트래픽이 몰려 병목 현상을 유발하고 스케줄링 가능성을 낮춤.
2. 부하 분산 라우팅 (Load-Balanced Routing): 트래픽 부하를 네트워크 전체에 분산시켜 병목을 완화하려 함. 하지만 주기(Period)가 다른 흐름들의 특성을 고려하지 않음.
   • 주기적 흐름의 대역폭 사용은 분산적(decentralized)임. 즉, 단순히 대역폭 총량만 계산하는 것은 스케줄링 병목을 정확히 측정하지 못함.
   • 예를 들어, 남은 대역폭이 충분해 보여도, 흐름들의 주기적 특성 때문에 실제로는 스케줄링이 불가능한 경우가 발생함.

본 논문의 기여

1. 결합성 (Combinability) 개념 제시: 서로 다른 주기를 가진 흐름들이 충돌 없이 대역폭을 공유할 수 있는 능력을 ‘결합성’으로 정의. 이 결합성이 스케줄링의 핵심 요소임을 밝힘.
2. 새로운 병목 측정 지표 제안: 결합성을 수학적으로 분석하여, 기존의 부하량(MSTL)보다 더 정확하게 스케줄링 병목을 측정하는 새로운 지표 MSOW (Maximum Sum of Weight)를 제안.
3. 주기 인식 라우팅 알고리즘 (Period-Aware Routing, PAR) 개발: MSOW를 최소화하는 것을 목표로 하는 새로운 휴리스틱 라우팅 알고리즘을 제안하여 스케줄링 가능성을 향상시킴.
4. 성능 검증: 다양한 토폴로지, 부하, 흐름 유형에 대한 광범위한 실험을 통해 제안 알고리즘이 기존 방식보다 월등히 높은 스케줄링 성공률을 보임을 입증.

---

2. 관련 연구 (Related Work)

• 전통적인 이더넷 라우팅(STP, SP)은 TSN의 시간 결정적 요구사항을 만족시키기 어려움.
• TSN 라우팅 연구는 최근에 활발해졌으며, 대부분 부하 분산에 초점을 맞춤.
• ILP(Integer Linear Programming) 기반의 최적화 연구는 스케줄링 품질은 높지만, 계산 시간이 너무 오래 걸려 대규모 네트워크에 비실용적.
• 휴리스틱 부하 분산 알고리즘들은 빠르지만, 흐름들의 ‘주기’ 특성을 간과하여 부정확한 병목 평가를 함.
• 본 논문은 주기 간의 상호작용(결합성)에 주목한 최초의 연구라는 점에서 차별성을 가짐.

---

3. 시스템 모델 및 문제 정의

• 네트워크 모델: 유향 그래프 G = (V, E)로 모델링. V는 스위치와 단말기, E는 링크.
• 흐름 모델: 각 흐름 f는 (src, dst, siz, prd) 튜플로 정의됨.
  • src, dst: 출발지, 목적지
  • siz: 프레임 전송에 걸리는 시간 (크기)
  • prd: 주기
• 스케줄링 모델: No-wait 스케줄링 (중간 스위치에서 대기 없이 바로 전달).
• 문제 정의: 주어진 네트워크 토폴로지와 흐름 집합에 대해, 스케줄링 성공률을 최대화하는 각 흐름의 경로를 찾는 것.

---

4. 동기 부여 예제 (Motivation Example)

• 기존 방식의 문제점: 기존 방식은 MSTL (Maximum Scheduled Traffic Load), 즉 하이퍼 주기(모든 주기의 최소공배수) 동안 가장 바쁜 링크의 총 부하량을 최소화하려 함.
• 그림 2의 설명:
  • (a) 비주기적 흐름: 남은 대역폭이 8이면, 크기 8짜리 흐름 하나를 넣을 수 있음. 단순 계산이 유효.
  • (b) 주기적 흐름: 남은 대역폭 총량이 7이어도, 대역폭이 시간 축에 흩어져 있기 때문에 실제로는 크기가 훨씬 작은 흐름(F5, siz=1)만 수용 가능. F6, F7은 스케줄링 불가.
• 결론: 단순히 남은 대역폭의 총량을 계산하는 것은 주기적 트래픽의 스케줄링 가능성을 제대로 반영하지 못함.

---

5. 제안된 해결책 (Proposed Solution)

5.1. 흐름의 주기별 결합성 분석 (The Combinability of Different Periods of Flows)

• 핵심 아이디어: 두 흐름이 같은 경로를 공유할 때 충돌이 발생하는 조건을 수학적으로 분석.
• 분석 과정 (그림 3, 4 및 수식 5-13):
  • 흐름 1(주기 p1)과 흐름 2(주기 p2)가 충돌하는 조건은 n*p1 = a + m*p2 (단, a는 흐름 2의 시작 오프셋).
  • 이 식을 정리하면, 충돌이 발생하는 a는 반드시 GCD(p1, p2)의 배수가 됨.
  • 따라서, 충돌을 피할 수 있는 a의 경우의 수(num)는 p2 - p2 / GCD(p1, p2)가 됨.
• 결론:
  • GCD가 클수록 충돌을 피할 수 있는 방법이 많아져 결합성이 좋다.
  • GCD가 작을수록 (특히 1일 때) 결합성이 나빠 스케줄링이 어렵거나 불가능하다.

5.2. 새로운 병목 지표: MSOW (Maximum Sum of Weight)

• 가중치(wgt) 정의: 각 흐름이 경로에 가하는 스케줄링 부담을 나타내는 값. 결합성 분석 결과에 기반하여 정의됨.

  wgt = siz / (prd - prd / GCD)

  • GCD는 해당 경로를 지나는 모든 흐름 주기의 최대공약수.
• SOW (Sum of Weight): 한 경로를 지나는 모든 흐름의 wgt의 합. 이 값이 클수록 해당 경로는 스케줄링 병목이 될 가능성이 높음.
• MSOW (Maximum SOW): 네트워크 전체 경로 중 가장 큰 SOW 값.
• 라우팅 목표: 흐름들을 잘 라우팅하여 이 MSOW 값을 최소화하는 것.

5.3. 제안된 라우팅 알고리즘 (PAR)

전체 구조 (Algorithm 1):

1. 흐름 정렬 (Sorting): 스케줄링에 영향을 덜 주는 흐름부터 라우팅하기 위해 흐름들을 특정 순서로 정렬.
2. 경로 탐색 및 선택 (Routing): 정렬된 순서대로 각 흐름에 대해 최적의 경로를 선택.

세부 알고리즘:

• Algorithm 2 (흐름 정렬):
  • 다른 흐름과의 GCD가 1인 흐름 (결합성 최악) -> Class 0 (가장 먼저 처리, 단독 경로 유도)
  • 제거해도 전체 LCM에 영향을 주지 않는 흐름 (약수 관계) -> Class 1
  • 나머지 -> Class 2
  • Class 0, 1, 2 순으로, 그리고 각 클래스 내에서는 주기가 작은 순으로 정렬.
• Algorithm 3 (최적 경로 탐색):
  • 각 흐름에 대해 모든 가능한 단순 경로(simple path)를 찾음.
  • 각 후보 경로에 대해, 해당 흐름을 추가했을 때의 비용(cost)을 계산.

    cost = MSOW + K * hops

    • MSOW: 스케줄링 병목 지표 (핵심 최적화 목표).
    • K * hops: 경로 길이에 대한 페널티. 너무 긴 경로를 선택하는 것을 방지. K는 사용자 정의 상수.
  • 비용이 가장 낮은 경로를 최적 경로로 선택.
• Algorithm 4 (가중치 계산):
  • 경로에 새로운 흐름이 추가될 때, 해당 경로의 GCD가 바뀔 수 있음.
  • GCD가 바뀌면, 해당 경로를 지나는 모든 이전 흐름들의 wgt와 SOW를 다시 계산(Recalculate)하여 정확성을 유지.

---

6. 실험 및 평가 (Experiments and Evaluation)

설정:

• 비교 대상:
  • SPR (Shortest Path Routing): 최단 경로 우선.
  • LBR (Load-Balanced Routing): 최신 부하 분산 라우팅 기법.
  • PAR (Period-Aware Routing): 본 논문 제안 기법.
• 평가 지표: 100번의 무작위 흐름 생성 시뮬레이션 후, ILP 스케줄러의 결과인 성공(Solved), 시간 초과(Timeout), 실패(Infeasible) 비율. 성공률이 높을수록 우수.
• 실험 환경:
  • 토폴로지: 2가지 (크고 복잡한 구조, 작고 연결성 높은 구조).
  • 플로우 그룹: 2가지 (결합성 높은 그룹, 결합성 낮은 그룹).

결과 분석:

1. 부하 의존성 (그림 7):
   • 환경: 결합성 높은 흐름 그룹(Group 1).
   • 결과: 흐름의 개수가 적을 때는 세 알고리즘 모두 성능이 좋지만, 부하가 증가할수록(흐름 30개, 40개) PAR의 성공률이 LBR과 SPR을 크게 앞지름. LBR은 SPR보다 약간 개선된 성능을 보임.
   • 분석: 결합성이 좋아도 부하가 높아지면 병목 관리가 중요해짐. PAR이 병목을 더 정확하게 예측하고 관리함을 의미.
2. 토폴로지 의존성 (그림 8):
   • 환경: 다른 토폴로지(Topology 2)에서 동일한 실험 반복.
   • 결과: 토폴로지가 바뀌어도 경향은 비슷하게 나타남. PAR은 다른 토폴로지에서도 일관되게 우수한 성능을 보임.
3. 흐름 유형 의존성 (그림 9):
   • 환경: 결합성 낮은 흐름 그룹(Group 2). 스케줄링이 매우 까다로운 조건.
   • 결과: 결과가 극적으로 갈림.
     • SPR, LBR: 성공률이 매우 낮고 거의 차이가 없음.
     • PAR: LBR, SPR 대비 스케줄링 성공률을 두 배 이상 향상시킴.
   • 분석: 이 환경에서는 부하 분산보다 결합성이 나쁜 흐름들을 서로 다른 경로로 격리시키는 것이 핵심. LBR은 이 특성을 고려하지 못해 SPR과 차이가 없었지만, PAR은 GCD 기반의 결합성을 직접 다루기 때문에 압도적인 성능 향상을 보임.

---

7. 결론 (Conclusions)

• 본 논문은 주기적 흐름의 분산된 대역폭 사용 특성과 결합성이라는 새로운 개념을 도입하여 TSN 라우팅 문제에 접근.
• 기존의 부하 분산 지표가 부정확함을 보이고, 흐름들의 주기 간 최대공약수(GCD)가 결합성을 측정하는 핵심 요소임을 수학적으로 증명.
• 이를 바탕으로 새로운 병목 지표(MSOW)와 주기 인식 라우팅 알고리즘(PAR)을 제안.
• 실험 결과, 제안된 PAR 알고리즘은 다양한 환경, 특히 스케줄링이 까다로운 환경에서 기존 알고리즘들보다 월등히 높은 스케줄링 성공률을 달성함.
• 이는 더 복잡하고 다양한 흐름이 공존하는 미래의 TSN 네트워크에서 PAR 알고리즘이 큰 실용적 가치를 가질 것임을 시사함.

한계 및 미래 연구:

• 경로 길이 페널티 상수 K가 경험적으로 결정되는 한계가 있음.
• 향후에는 개별 흐름 단위가 아닌, 전체 네트워크의 병목을 전역적으로 고려하는 휴리스틱을 개발하여 경험적 파라미터 의존도를 낮출 필요가 있음.