이제 Arestova 연구팀의 논문을 통해 정적(Offline) GCL 스케줄링 방법론을 자세히 살펴보겠습니다. 이들은 다양한 알고리즘과 최적화 기법을 통해 다음 목표를 달성하고자 했습니다:

• 스트림의 마감 시간(deadline) 준수 (가장 중요).
• 전체 스케줄 길이(makespan) 최소화.
• 효율적인 대역폭 활용 및 GCL 엔트리 수 최적화.

논문은 스케줄링 알고리즘의 입력 데이터 특성과 GCL의 기본 주기 설정 방식을 중요한 요소로 다룹니다 (논문 Fig. 6 참조).

1. 스트림 주기 (Stream Period) 특성

• 조화 (Harmonic) 주기: 모든 스트림 주기가 서로 정수배 관계이거나 특정 기본 주기의 배수인 경우. (예: 2ms, 4ms, 8ms는 모두 2ms의 배수).
  이론적으로 분석이 용이하지만, 실제 환경에서는 드물 수 있습니다.
• 비조화 (Non-harmonic) 주기: 스트림 주기들이 서로 정수배 관계가 아닌 경우. (예: 2ms, 5ms, 7ms).
  실제 산업/차량 환경에서 더 일반적입니다.

2. GCL 주기 (GCL Cycle Time) 결정 방식 (논문 Fig. 7 참조)

GCL이 반복되는 전체 시간을 어떻게 설정할 것인지에 대한 두 가지 주요 전략입니다:

논문에서 제시된 1S(One-Shot) 휴리스틱(Heuristic) 알고리즘의 핵심은 각 TSN 스트림에 대해 적절한 전송 슬롯을 찾는 것입니다 (논문 Section V-B 및 [17] 참조). 휴리스틱이란, 항상 최적의 해를 보장하지는 않지만, 경험적 규칙이나 직관에 기반하여 합리적인 시간 내에 만족스러운 해를 찾는 방법론을 말합니다. 이 알고리즘은 다음 원칙에 따라 동작합니다:

1. No-Wait 원칙 (End-to-End)

스트림이 송신 노드(talker)에서 전송을 시작하면, 중간 노드들의 egress 큐에서 다른 스트림에 의해 대기하는 시간 없이 목적지(listener)까지 도달해야 합니다. 즉, 경로상의 모든 링크에서 스트림은 예약된 전용 슬롯을 사용하며, 큐잉 지연이 발생하지 않습니다.

2. 슬롯 탐색 및 배치 (논문 Fig. 8, 9, 10 참조)

주어진 스트림 Sk (주기 pk, 초기 릴리즈 오프셋 Φk_orig, 마감시간 dk, 프레임 길이 lk)에 대해, 실제 스케줄링 오프셋을 Φ'k (Phi prime)이라 합니다 (Φ'k ≥ Φk_orig).

1. 초기 시도: 송신 노드에서 초기 스케줄링 오프셋 Φ'k = Φk_orig로 설정하고, 첫 번째 링크에서 이 시간에 스트림 Sk를 위한 슬롯을 찾습니다.
2. 경로상 전파 (No-Wait 유지): 스트림이 경로의 현재 링크 (i,j)에서 전송을 완료하면, 다음 링크 (j,m)에서의 도착 시간은 다음과 같이 계산됩니다:
   도착시간(j,m) = 시작시간(i,j) + Dktrans,(i,j) + Dprop,(i,j) + Dproc,j
   이 계산된 도착 시간에 다음 링크 (j,m)에서 Sk를 위한 슬롯이 즉시 사용 가능해야 합니다. (논문 Fig. 4, 5 참조)
3. 등간격 슬롯 (Equidistant Slots): 스트림 Sk가 GCL 주기 내에 여러 번 전송되어야 하는 경우 (즉, Hyperperiod / pk > 1), 각 인스턴스는 정확히 pk 시간 간격으로 배치되도록 합니다. 이는 지터(jitter, 전송 간격의 변동성) 감소에 도움을 줍니다. (논문 Fig. 8의 S1 예시)
   • HYPO 방식: Hyperperiod 내에서 pk 간격으로 빈 슬롯들을 탐색합니다.
   • GCD 방식: 스트림 주기가 GCD의 M배 (pk = M * GCD)인 경우, 첫 번째 인스턴스가 k번째 GCD 세그먼트에 배치되면, 다음 인스턴스는 (k+M)번째 GCD 세그먼트의 동일한 상대적 위치에 배치되도록 합니다. (논문 Fig. 9의 S2 예시: p2=4ms, GCD=2ms. S2가 GCD0에 배치되면 다음은 GCD2에 배치)
4. 슬롯 충돌 시 오프셋 조정: 만약 경로상의 어떤 링크에서 필요한 시간에 슬롯을 찾을 수 없다면 (다른 스트림이 이미 사용 중), 송신 노드에서의 시작 오프셋 Φ'k를 약간 증가시켜 (예: 다음 가능한 시간 단위로) 슬롯 탐색 과정을 1단계부터 다시 시도합니다.
5. 마감 시간 검증: 모든 경로에서 슬롯이 성공적으로 할당되면, 최종 종단 간 지연이 스트림의 마감 시간을 만족하는지 아래의 스케줄 가능성 조건으로 확인합니다. 만족하지 못하면 해당 Φ'k로는 스케줄링 실패입니다 (다른 Φ'k로 재시도 또는 스케줄 불가 처리).

3. 주요 수식 설명 (논문 참조)

1S 휴리스틱이 최적해를 찾지 못하거나 더 나은 스케줄을 탐색하기 위해, 논문은 유전 알고리즘(GA)을 사용합니다 (논문 Section II-B, V-E 참조). GA는 생물학적 진화 과정을 모방한 메타휴리스틱(Meta-heuristic) 탐색 기법입니다. 메타휴리스틱이란, 특정 문제에만 국한되지 않고 다양한 종류의 최적화 문제에 적용될 수 있는 상위 수준의 일반적인 문제 해결 전략이나 방법론을 의미합니다.

1. GA 기본 구성 요소

• 개체 (Individual) 및 염색체 (Chromosome):
  • 각 개체는 하나의 잠재적 해(스케줄)를 나타냅니다.
  • 염색체는 이 해를 인코딩한 것으로, 본 논문에서는 스케줄링할 스트림들의 순서(permutation)로 표현됩니다. (논문 Fig. 2)
    (예: 염색체 [S1, S3, S2, S4]는 S1, S3, S2, S4 순서로 1S 휴리스틱을 적용하여 스케줄링 시도)
  • 염색체에서 각 스트림 ID (예: S1)가 유전자(Gene)이고, 스트림 ID 값 자체가 대립형질(Allele)입니다.
• 적합도 함수 (Fitness Function):
  • 각 개체(즉, 특정 스트림 순서로 스케줄링한 결과)가 얼마나 좋은 해인지를 평가합니다.
  • 논문에서는 주로 makespan (모든 스트림의 전송이 완료되는 총 시간)을 최소화하는 것을 목표로 합니다. 마감 시간을 만족하지 못하는 스케줄은 매우 낮은 적합도를 갖거나 유효하지 않은 해로 간주됩니다.
• 선택 (Selection): 적합도가 높은 개체들이 다음 세대로 생존하거나 번식(교차 연산의 부모로 선택)될 확률이 높아집니다. 논문에서는 엘리트주의적 접근(elitist approach)을 언급하며, 이는 현재 세대에서 가장 우수한 개체(들)이 다음 세대로 그대로 전달됨을 의미합니다.
• 교차 (Crossover - 논문 Fig. 3의 PBX 예시):
  • 두 부모 개체의 염색체(스트림 순서) 일부를 조합하여 새로운 자식 개체를 생성합니다.
  • 논문에서는 PBX (Position-based Crossover, 위치 기반 교차)를 주로 사용합니다. PBX의 단계는 다음과 같습니다 (논문 Fig. 3 그림을 상상하며):
    1. 두 부모 염색체 P1, P2를 선택합니다. (예: P1=[S2,S3,S4,S5,S6,S1], P2=[S1,S2,S5,S3,S4,S6])
    2. 염색체 길이 내에서 무작위로 몇 개의 위치(position)를 선택합니다. (Fig. 3에서는 1번째와 4번째 위치 - 0부터 시작하는 인덱스로는 0과 3 - 를 선택했다고 가정할 수 있으나, 논문 그림은 1-based index로 {1, 4}를 사용하겠습니다.)
    3. 첫 번째 자식 염색체 O1을 만듭니다. 선택된 위치 {1, 4}에 있는 P1의 유전자(스트림)를 O1의 동일 위치에 복사합니다.
       (P1의 1번째는 S2, 4번째는 S5. 따라서 O1 = [S2, ?, ?, S5, ?, ?])
    4. O1의 나머지 빈칸을 채웁니다. P2의 유전자들을 P2에서의 순서대로 가져오되, O1에 아직 없는 유전자만 골라 빈칸에 순서대로 채웁니다.
       P2 순서: S1 (O1에 없음 -> O1[2]=S1), S2 (O1에 이미 있음 -> 건너뜀), S5 (O1에 이미 있음 -> 건너뜀), S3 (O1에 없음 -> O1[0]=S3. 어? 그림이랑 다르네. Fig 3 그림은 P1: [S2 S3 S4 S5 S6 S1], P2: [S1 S2 S5 S3 S4 S6] -> Selected Index {1,4} -> Offspring1: [S3 S2 S1 S5 S4 S6]. 이 그림대로 하려면, O1의 첫번째 빈칸 (index 0)은 P2의 첫번째 유전자(S1)가 아니고, P2에서 O1에 아직 없는 첫번째 유전자인 S3를 가져온다. 즉 P2: [S1, S2, S5, S3, S4, S6] -> O1의 index 0에 S3. O1: [S3, S2, ?, S5, ?, ?]. 다음 빈칸 index 2: P2의 다음 없는 유전자 S1 -> O1: [S3, S2, S1, S5, ?, ?]. 다음 빈칸 index 4: P2의 다음 없는 유전자 S4 -> O1: [S3, S2, S1, S5, S4, ?]. 다음 빈칸 index 5: P2의 다음 없는 유전자 S6 -> O1: [S3, S2, S1, S5, S4, S6]. 이것이 논문 그림과 일치합니다.)
    5. 두 번째 자식 염색체 O2는 P1과 P2의 역할을 바꿔 동일하게 생성합니다. (선택된 위치는 P2로부터, 나머지는 P1로부터)
• 돌연변이 (Mutation):
  • 개체의 염색체(스트림 순서) 일부를 무작위로 변경하여 유전적 다양성을 유지하고 지역 최적해(local optimum)에 빠지는 것을 방지합니다.
  • 논문에서는 Swap Mutator (교환 돌연변이)를 사용합니다: 염색체 내에서 무작위로 두 유전자(스트림)의 위치를 서로 맞바꿉니다.
• 반복 및 종료 조건: 위 선택, 교차, 돌연변이 과정을 여러 세대(generation) 동안 반복하거나, 미리 정의된 실행 시간 또는 적합도 개선이 없을 경우 종료합니다.

2. 정렬된 스트림을 위한 GA 조정 (논문 Fig. 14)

입력 스트림이 주기(period) 기준으로 미리 정렬된 경우(Sorted input), GA 연산 시 이 정렬 특성을 유지해야 합니다.

• 하위 그룹 (Subgroups): 염색체 내에서 동일한 주기를 가진 스트림들은 하나의 하위 그룹으로 묶입니다 (Fig. 14: P1,P2=2ms / P3,P4=4ms / P5,P6=8ms 그룹). 이 하위 그룹들은 주기 오름차순으로 정렬된 상태를 유지합니다.
• PBX-Sort 및 Swap-Sort: 기존 PBX와 Swap 연산을 수정하여, 교차와 돌연변이가 각 하위 그룹 내에서만 일어나도록 합니다. 전체 하위 그룹 간의 순서(즉, 주기 순서)는 변경되지 않습니다.

3. GA 파라미터 (논문 Table 1)

이 파라미터들은 실험적으로 결정되었으며, GA의 탐색 성능과 실행 시간에 영향을 줍니다.

스트림 스케줄이 성공적으로 결정된 후 (즉, 모든 스트림이 마감 시간을 만족하는 슬롯을 찾은 후), 논문은 GCL 자체의 효율성을 높이고 대역폭 낭비를 줄이기 위한 두 가지 최적화 기법을 적용합니다 (논문 Section V-C, V-D).

1. GCL 엔트리 병합 (Merging - 논문 Algorithm 1, Fig. 11, 12)

목표: TAS 하드웨어는 GCL 엔트리 수에 제한이 있으므로, 이 수를 최소화하는 것이 중요합니다. 이 알고리즘은 인접한 중요 트래픽 슬롯들 또는 슬롯과 GCL 경계 사이의 작은 간격을 병합하여 GCL 엔트리 수를 줄입니다.

(논문 Fig. 11은 단일 스트림의 경우 최소 2개의 GCL 엔트리(하나는 중요 트래픽용, 다른 하나는 나머지 시간 비임계 트래픽용)가 필요함을 보여줍니다. Fig. 12는 HYPO 방식에서는 9개 슬롯이 필요했지만, GCD 방식에서는 슬롯 정규화 및 병합 후 5개 슬롯으로 줄어드는 예시를 보여줍니다.)

2. 스케줄 압축 (Schedule Compression - 논문 Fig. 13)

목표: GCL 병합 후에도 여전히 스케줄된 중요 트래픽 슬롯들 사이에 존재할 수 있는 빈 공간(유휴 시간)을 줄여 대역폭 활용도를 높입니다.

논문은 제안된 16가지 스케줄링 알고리즘 변형들의 성능을 평가하기 위해 광범위한 시뮬레이션을 수행했습니다 (논문 Section VI). 알고리즘 조합은 Table 2에 요약되어 있으며 (H=Harmonic, NH=Non-Harmonic, GCD/HYPO, Rand/Sorted, ALT/Non-ALT, 1S/GA), 각 조합을 다른 네트워크 조건에서 테스트했습니다.

1. 실험 설정 (요약)

• 테스트 환경: Intel Core i7-8550U @ 1.88 GHz, 24GB RAM.
• 가변 파라미터:
  • 스위치 수: {3, 5, 10, 20, 30}
  • 엔드 스테이션 수: [스위치 수 * 1 또는 2] (각 스위치에 연결된 단말기 수)
  • 스트림 수: {50, 150, 200, 300, 500, 800}
  • 네트워크 토폴로지: Star, Ring, Meshed (무작위 경로 생성)
  • 링크 속도: 1 Gbps (표준)
• 스트림 주기 세트:
  • 조화(Harmonic): {2, 4, 8, 16, 32} ms
  • 비조화(Non-harmonic): {2, 4, 5, 10, 20} ms (차량 내부 네트워크 환경 참조)
• 실험 반복: 각 설정 조합(알고리즘, 스위치/스트림 수 등)에 대해 50회 실행하여 평균값 등을 사용.
• 주요 평가지표: 실행 시간(Time Performance), 스케줄 성공률(Schedulability), 최대 GCL 엔트리 수, 대역폭 낭비율(Wasted Bandwidth), 사용 가능한 잔여 대역폭(Left-over Bandwidth), 총 스케줄 길이(Makespan).

2. 주요 결과 심층 분석 (논문 Figures 15-19, Tables 3-4)

Arestova 연구팀은 자신들의 연구(Section VII)를 통해 다음과 같은 주요 결론을 도출했습니다:

• 알고리즘 설계의 중요성: 스케줄링 알고리즘의 수정(입력 데이터 순서, 스케줄링 절차, GCL 구성 방식)은 네트워크 리소스 사용률, 특히 조화(Harmonic) 주기 알고리즘 클래스에 큰 영향을 미칩니다.
• 휴리스틱의 효과: 정확하게 설계된 휴리스틱 알고리즘은 스케줄링 문제를 효과적으로 해결할 수 있으며, 그 이상의 복잡한 문제(GA가 다루는)에도 적합할 수 있습니다. (그러나 GA는 특정 상황에서 성공률을 높임)
• 'Alternating' 전략의 유용성 (조화 주기 시): 마감 시간 준수가 충분하다면, 'Alternating' 접근법 (GCD 세그먼트 간 부하 분산)은 적은 GCL 엔트리 수와 낮은 대역폭 낭비를 달성하는 데 적합합니다.
• GA와 'Alternating'의 시너지 (조화 주기 시): GA 변형과 'Alternating'을 결합하면 대역폭 통계 및 GCL 구성 측면에서 최상의 결과를 얻을 수 있습니다 (실행 시간은 길어짐).
• HYPO의 장점 (대역폭): 'Alternating'이 없는 GCD 변형과 비교할 때, 조화 및 비조화 주기 모두에서 HYPO 접근법은 낭비되거나 남은 대역폭 측면에서 훨씬 더 나은 결과를 보였습니다. 그러나 GCL 엔트리 수가 많아질 수 있습니다.
• 정렬의 제한적 효과: 입력 스트림을 정렬하는 것은 비정렬 방식에 비해 모든 경우에 뚜렷한 이점을 제공하지는 않았습니다.
• 비조화 주기의 성공률: 비조화 주기 알고리즘 클래스는 대규모 토폴로지에서 다른 알고리즘에 비해 낮은 스케줄 성공률을 보였습니다. 이 경우 GA가 성공률을 높이는 데 도움이 됩니다.
• 하드웨어 제약 고려: GCL 엔트리 수가 많은 경우(특히 HYPO), 실제 하드웨어 제한을 신중히 고려해야 하며, 슬롯 병합 접근 방식도 제한된 GCL 수를 고려하여 조정될 필요가 있습니다.