물론입니다. 제공해주신 학술 논문 전체(14페이지)를 한국어로 번역하고, 원문의 구조를 최대한 살려 정리했습니다.
기술 용어의 경우, 학계 및 산업계에서 통용되는 번역을 우선 사용했으며, 적절한 번역이 없거나 원어의 의미를 명확히 할 필요가 있는 경우 ‘한글 번역 (원어)’ 형식으로 표기했습니다.
아래는 논문 전체의 번역본입니다. 이 내용을 복사하여 워드 프로세서나 텍스트 편집기에 붙여넣고 PDF로 저장하시면 됩니다.
ANNA ARESTOVA, KAI-STEFFEN HIELSCHER, and REINHARD GERMAN 프리드리히-알렉산더 대학교 에를랑겐-뉘른베르크, 에를랑겐 91058 독일 교신 저자: Anna Arestova (이메일: anna.arestova@fau.de).
이 연구는 MBPLE4Mobility 프로젝트의 일환으로 개발되었으며, 독일 연방 경제기후보호부의 지원을 받았습니다.
IEEE 802.1 시감응형 네트워킹(TSN) 태스크 그룹은 2012년부터 IEEE 802 네트워크를 통해 결정적이고 시간-민감 서비스를 제공하기 위한 다양한 표준을 개발해왔습니다. 시간 인식 셰이퍼(Time-Aware Shaper, TAS)는 시간-민감 네트워크 트래픽의 정밀한 전달 및 셰이핑을 가능하게 하기 위해 도입된 TSN의 핵심 구성 요소입니다. 이는 선택된 트래픽 클래스에 대한 독점적인 전송 슬롯 구성을 허용합니다. TAS의 이점을 최대한 활용하기 위해, TAS 기반 네트워크에서 시간-민감 네트워크 스트림의 종단 간 전송 시간을 최적화하는 전송 스케줄을 찾기 위한 수많은 스케줄링 알고리즘이 제시되었습니다. 그러나 대부분의 기존 연구는 민감한 네트워크 트래픽의 스케줄링이 하드웨어에서 제한되는 민감한 전송 슬롯의 필요 개수와 다른 트래픽 클래스에 대한 결과적인 대역폭 활용에 어떤 영향을 미치는지 다루지 않습니다. 본 논문에서는 TAS 기반 네트워크에서 민감한 네트워크 스트림을 스케줄링하기 위한 휴리스틱 및 메타휴리스틱 알고리즘의 선택된 집합이 네트워크 자원 활용에 미치는 영향과, 압축 알고리즘을 사용하여 TAS 구성을 개선할 수 있는 방법을 조사했습니다. 이를 위해 기존 알고리즘을 활용하고 입력 데이터 순서, 스케줄링 절차 및 TAS 구성에 영향을 미치는 대안을 제안합니다. 평가 결과, 제안된 수정 사항 중 일부는 대역폭 활용을 개선하고 민감한 트래픽에 대한 전송 슬롯 수를 크게 줄일 수 있음을 보여주었습니다. 더 나아가, 압축 알고리즘은 특정 경우에 현저한 개선을 가져올 수 있습니다.
색인 용어: TSN, 실시간, 스케줄링, 이더넷 네트워크
시감응형 네트워킹(TSN) [1]의 도입은 실시간 시스템에서 이더넷 기술을 사용할 가능성을 열어주었습니다. 이는 한편으로는 동일한 네트워크에서 민감한 트래픽과 비민감 트래픽의 공존이 허용되고, 다른 한편으로는 공급업체 종속성을 피하면서 다른 공급업체 및 장치 간의 상호 운용성을 확립할 수 있다는 점에서 특히 매력적입니다. 특히 시간-민감 네트워크 트래픽(TSN 스트림)과 관련하여, 지연 시간 보장 및 낮은 지터 [2]와 같은 서비스 품질(QoS)을 제공하기 위한 다양한 메커니즘을 특징으로 합니다. 연구에서 가장 널리 사용되는 TSN 셰이퍼 중 하나는 [3]에서 소개된 시간 인식 셰이퍼(TAS)입니다. 이는 트래픽 클래스에 시간 슬롯을 할당하는 원리로 작동합니다. 그러나 이 메커니즘은 표준 자체에서 지원되지 않으며, 민감한 네트워크 트래픽의 양과 네트워크 인프라에 크게 의존하는 적절한 구성에 의존합니다. 부적절한 구성은 지연 시간, 지터 및 대역폭 활용을 악화시키거나, 특히 안전-민감 애플리케이션이 관련된 경우 심각한 결과를 초래할 수 있는 마감 시간 누락으로 이어질 수 있습니다. 특히 자율 주행과 같은 혁신은 수많은 안전-민감 애플리케이션, 다수의 센서 및 액추에이터, 그리고 결과적으로 더 높은 안전-민감 네트워크 트래픽 부하를 동반합니다 [4].
여러 논문([5]–[7])에서 TAS의 시간-민감 슬롯 구성과 함께 시간-민감 네트워크 트래픽의 스케줄링을 다루었습니다. 그러나 대다수는 개별 네트워크 스트림의 종단 간 지연 준수에 초점을 맞추었고, TAS 구성의 어려움과 한계를 고려하지 않았습니다. 한편으로는 구성 가능한 슬롯의 수가 하드웨어에 의해 제한되고, 다른 한편으로는 구성된 슬롯 사이에 사용 불가능한 간격이 발생하여 대역폭이 낭비될 수 있습니다. 더욱이, 비민감 트래픽 클래스를 위한 잔여 대역폭에 대한 고려는 종종 생략됩니다. 혼합 중요도(mixed-criticality)가 TSN의 대표적인 특징이므로, 다른 트래픽을 위한 잔여 대역폭 고려를 포함하는 것이 적절합니다.
본 논문에서는 주기적이고 민감한 TSN 스트림을 스케줄링하고 TAS 구성의 한계를 고려하는 휴리스틱 및 메타휴리스틱 알고리즘 집합을 소개합니다. 이를 위해, 제안된 알고리즘이 입력 데이터 속성 및 순서, 스케줄 최적화 전략, 그리고 전용 TAS 속성에 미치는 영향을 조사합니다. 우리는 알고리즘의 실행 시간, 스케줄 가능성, 확장성 및 대역폭 활용도를 조사하고, 적절한 TAS 알고리즘 선택에 대한 권장 사항을 제시합니다. 또한, [6]에서 제안된 스케줄 압축의 이점을 검토합니다.
논문의 구조는 다음과 같습니다. 2장에서는 본 논문의 기초를 소개합니다. 3장에서는 관련 연구를 다룹니다. 4장에서는 시스템 모델을 제시하고, 5장에서는 적용된 스케줄링 알고리즘을 설명합니다. 6장에서는 알고리즘을 평가하고 비교하며, 7장에서 결론을 내립니다.
TSN은 시간 동기화, 신뢰성 및 자원 관리 메커니즘 외에도 지연 시간 보장을 제공하기 위해 TAS를 포함한 셰이퍼 및 스케줄러 집합을 제공합니다. 네트워크 트래픽의 분류는 TAS의 핵심 기능입니다. 이는 이더넷 헤더의 가상 로컬 영역 네트워크(VLAN) 태그에 있는 우선순위 코드 포인트(PCP) 값을 기반으로 네트워크 트래픽을 여러 네트워크 클래스로 나눕니다. PCP 값은 0-7의 정수 범위를 가지며, 결과적으로 8개의 트래픽 클래스가 생성됩니다. TSN 스트림이라는 용어는 소스(talker)에서 시작하여 하나 이상의 목적지(listener)로 전파되는 하나 이상의 일관된 네트워크 패킷 시퀀스를 정의합니다 [8]. TAS는 시분할 다중 접속(TDMA) 원리에 따라 작동하며, 이는 시간을 여러 슬롯으로 나누어 하나 이상의 트래픽 클래스를 위해 동시에 예약할 수 있도록 합니다. 정의된 비중첩 시간 슬롯 시퀀스는 구성 가능한 주기가 지난 후 반복됩니다. 시간 슬롯의 스케줄은 게이트 제어 목록(GCL) [3]으로 표현됩니다. 시간 슬롯 원리를 구현하기 위해, 802.1Qbv 표준은 물리적 포트의 각 송신 큐(egress queue)에 하나씩, 이른바 게이트(gates)를 도입했습니다(그림 1a 참조). 일반적으로 물리적 포트에는 각 트래픽 클래스에 대해 하나씩, 8개의 송신 큐가 사용 가능합니다 [9]. [10]에 따르면, 실시간 트래픽을 포함하는 최고 우선순위 트래픽에는 하나의 송신 큐로 충분합니다. 게이트가 GCL 항목에서 활성으로 설정되면 트래픽을 통과시킵니다. 그렇지 않으면 비활성화되어 큐의 프레임 전송을 막고, 따라서 해당 큐는 전송 선택에서 고려되지 않습니다. 그림 1a에서 큐는 각 GCL 항목의 비트 배열로 인코딩됩니다. 가장 왼쪽 위치는 가장 높은 우선순위, 가장 오른쪽은 가장 낮은 우선순위에 해당합니다. 0은 게이트가 비활성, 1은 활성임을 의미합니다. 그림은 GCL에 따라 게이트 드라이버에 의해 제어되는 시간 인식 게이트가 있는 8개의 송신 큐를 보여줍니다. 우선순위 7의 큐는 스케줄된/민감한 트래픽을 위한 큐를 나타냅니다. 이 큐는 [T0;T1] 및 [T2;T3] 간격에서 독점적으로 서비스됩니다. 여러 게이트가 동시에 활성화되면, 전송 선택은 최고 우선순위 큐를 먼저 서비스하는 엄격한 우선순위(strict-priority) 스케줄링과 같은 스케줄링 알고리즘에 따라 작동합니다. 큐의 프레임은 선입선출(first come, first serve) 방식으로 제거됩니다. TAS의 이점을 활용하려면 공통된 시간 개념이 필요합니다. 이는 IEEE 802.1AS [11]에서 최대 1µs의 편차로 제공될 수 있습니다.
(그림 1은 원본 PDF의 시각 자료로, 텍스트로 설명합니다.) 그림 1: TAS 구성 예시. (a) 시간 인식 셰이퍼(Time-Aware Shaper): 큐 7부터 0까지 있으며, 각 큐는 시간 인식 게이트에 연결됩니다. 게이트 제어 목록(GCL)은 T0, T1, T2 등의 시간에 어떤 큐의 게이트를 열지(1) 또는 닫을지(0)를 정의합니다. (b) 유선상의 직렬화(Serialization on the wire): 민감한 스트림(S1, S2)은 예약된 슬롯에 전송되고, 비민감 프레임은 다른 슬롯에 전송됩니다. 가드 밴드(Guard band)는 민감 슬롯을 보호하며, 이로 인해 대역폭 낭비가 발생할 수 있습니다.
게이팅 메커니즘만으로는 비민감 네트워크 트래픽이 민감 시간 슬롯으로 침입하는 것을 막을 수 없습니다. 비민감 이더넷 프레임의 전송이 민감 트래픽의 슬롯 시작 시간 직전에 시작되면 즉시 선점(preempted)될 수 없습니다. 최악의 경우, 이는 이더넷 데이터 및 물리 계층 오버헤드를 고려한 1542바이트의 최대 전송 단위(MTU) 크기 패킷의 침입을 의미합니다. 침입 상황을 피하기 위해, IEEE 802.1Qbv는 시간 슬롯 끝에 적용되고 게이트와 연관된 이른바 가드 밴드를 정의합니다. 활성 가드 밴드 간격 내에서 전송 준비가 된 패킷은 보류되며, 할당되지 않은 시간 슬롯으로 침입하지 않습니다. 이는 가드 밴드가 고정된 크기(최악의 경우 MTU 전송 크기)를 가지고 프레임이 침입 없이 통과할 수 있는지 확인하는 특별한 로직이 없는 경우에 발생합니다 [3]. 그림 1b는 유선상의 직렬화를 보여주며 가드 밴드가 고정 크기인 사용 사례를 보여줍니다. 하나의 비민감 프레임이 TAS 주기 n에서 가드 밴드 시작 직전에 도착하여 전송됩니다. 다른 비민감 프레임은 TAS 주기 n+1에 도착합니다. 비민감 슬롯에 들어갈 수 있음에도 불구하고, 가드 밴드에 의해 보류되어 대역폭이 낭비됩니다. 이 그림은 또한 예약된 슬롯이 완전히 활용될 필요가 없음을 명확히 합니다. 특히 민감 슬롯에서 사용되지 않은 시간(slack)은 대역폭 낭비로 이어집니다. 그림 1b에서 이러한 미사용 여유 시간은 주기 n에서 S1과 S2 사이에 발생하며, 이는 낮은 우선순위 트래픽 클래스에 할당될 수 있었습니다. TDMA 원칙은 민감 트래픽에 이점을 제공하지만, 다른 트래픽 클래스에는 단점을 보입니다.
그러나 실현 가능한 게이트 구성을 찾는 것은 복잡한 임무입니다. 수백 개의 시간-민감 네트워크 스트림이 소규모 또는 대규모 네트워크에서 모든 스트림이 종단 간 전송 마감 시간을 충족할 수 있도록 스케줄링되어야 할 수 있기 때문입니다. 인접 장치의 게이트 시간은 둘 이상의 게이트가 다른 송신 포트에서 적어도 하나의 스트림을 공유할 때마다 조정되어야 합니다. 목적은 불필요한 지연을 피하는 것입니다. 이를 위해서는 우리가 이 연구에서 다룰 신중한 스케줄링 접근 방식이 필요합니다.
우리는 비민감 슬롯의 낭비된 대역폭에 대해 충분한 정보가 없기 때문에 가정을 할 수 없습니다. 그러나 우리는 스케줄링 알고리즘을 필요한 슬롯 수와 결과적인 가드 밴드로 평가하고 민감 슬롯의 낭비된 대역폭을 결정할 수 있습니다. 우리는 TSN 스트림의 스케줄링, 네트워크의 GCL 구성, 그리고 민감 슬롯의 대역폭 활용에 대해 더 자세히 다룰 것입니다.
고려된 알고리즘 중 일부는 유전 알고리즘(GA) [7]을 사용하므로, 이 섹션에서 소개합니다. GA는 자연 선택과 유전학을 포함하는 생물학적 진화 과정에서 영감을 받았습니다. 이는 여러 단계로 구성된 무작위 탐색 기법입니다 [12]:
TSN 스트림 스케줄링은 순열 문제(permutation problem) [12]로 매핑될 수 있습니다. 각 염색체는 스케줄링될 모든 스트림의 시퀀스를 인코딩하며, 변수로 인식될 수 있는 각 유전자는 스트림의 고유 식별자(예: 문자열 표현)를 포함합니다. 유전자의 값은 대립유전자(allele)라고도 합니다. 염색체는 스트림이 왼쪽에서 오른쪽으로 스케줄링되는 순서를 설명합니다. 그림 2는 스트림 인코딩의 예를 보여줍니다. 평가 단계에서 우리는 위치 기반 교차(Position-based Crossover, PBX)와 스왑 돌연변이(Swap mutator)가 우리 문제에 가장 적합하다는 것을 발견했습니다.
(그림 2와 3은 원본 PDF의 시각 자료로, 텍스트로 설명합니다.) 그림 2: 문자열 인코딩. 염색체는 유전자(S1, S2, …)의 시퀀스로 구성됩니다. 각 유전자의 값(대립유전자)은 특정 스트림을 나타냅니다. 그림 3: PBX 연산자. 두 부모 개체(Individual 1, Individual 2)에서 특정 위치(예: 1, 4)의 유전자를 선택하여 자손(Offspring 1, Offspring 2)에게 물려줍니다. 나머지 위치는 다른 부모의 유전자를 순서대로 채워 넣습니다.
PBX는 두 개체를 가져와 염색체 크기보다 작은 임의의 위치 수를 결정합니다. 그림 3에서는 인덱스 1과 4를 선택합니다. 두 개의 새로운 자손이 생성됩니다. 자손의 염색체는 선택된 위치에 의해 결정된 유전자를 상속받으며, 각 자손은 한 부모로부터 상속받습니다. 그림 3의 Offspring1은 인덱스 1에서 S2, 인덱스 4에서 S5를 Individual1로부터 상속받습니다. 자손의 나머지 위치는 다른 부모의 유전자 순서를 준수하면서 고유한 요소로 채워집니다. 예제에서, 우리는 Individual2의 값 S2를 가진 유전자를 Offspring1의 인덱스 0에 배치하려고 시도합니다. 그러나 S2는 이미 Offspring1에 존재하므로 S3로 계속 진행합니다. S3는 Offspring1에 없으므로 인덱스 0에 배치될 수 있습니다. 스왑 돌연변이는 집단에서 한 개체를 가져와 염색체에서 두 개의 임의 유전자를 선택한 다음, 유전자 위치를 바꿉니다. 더 자세한 정보는 이전 연구 [12]를 참조하십시오.
TAS 관련 스케줄링 문제는 여러 번 다루어지고 검토되었습니다. 가장 많이 검토된 연구 중 하나는 Craciunas 등의 [5]입니다. 저자들은 만족성 모듈로 이론(Satisfiability Modulo Theories, SMT)을 사용하여 주어진 공식(이 경우 제약 조건)이 만족스러운지 결정합니다. 이 접근 방식은 흐름과 장치의 크기를 다양하게 하여 4시간 범위 내에서 최대 1500개의 TSN 스트림을 스케줄링할 수 있습니다. 그들은 주로 스트림 스케줄링에 초점을 맞추었고 GCL 구성 문제는 다루지 않았습니다. 또한, 그들의 알고리즘은 여러 송신 큐의 사용을 허용합니다. [7]에서 제시된 접근 방식은 GA를 적용하여 시간-민감 네트워크에서 시간-트리거 트래픽을 스케줄링합니다. 저자들은 TSN 스트림의 라우팅 및 스케줄링 문제를 해결하기 위해 GA를 제안하지만 GCL 구성에 대해서는 자세히 다루지 않습니다. 우리는 라우팅 문제를 고려하지 않습니다.
또한 TSN 스트림의 공동 스케줄링과 GCL 구성에 주목하는 몇 가지 연구가 있습니다. Dürr 등 [6]은 TSN 스트림 스케줄링을 위한 타부 탐색(Tabu Search) 알고리즘을 구현하고 무대기(no-wait) 원칙을 통합했습니다. 스케줄링 단계 후, 그들은 GCL 항목과 가드 밴드의 수를 줄이기 위해 압축 알고리즘을 수행합니다. 우리는 무대기 접근 방식을 채택하고 수정된 압축 함수를 나중에 수행합니다. 이 연구와 비교하여, 우리는 다른 조화(harmonic) 또는 비조화(non-harmonic) 주기를 허용하는 반면, [6]은 모든 스트림에 대해 동일한 주기를 고려합니다. 가드 밴드 수를 줄이기 위해, Jing 등 [15]은 네트워크에서 최대 4개의 큐를 사용하여 고정된 수의 허용된 GCL 항목을 가정합니다. 그들은 SMT, 최적화 모듈로 이론(OMT) 및 맞춤형 휴리스틱 접근 방식을 적용하여 스케줄링 문제를 해결합니다. SMT 변형은 최대 100개의 흐름을 포함하는 작은 사용 사례에 대해 실현 가능한 스케줄을 찾는 데 약 2일이 걸립니다. OMT 접근 방식은 이틀 안에 최대 10000개의 스트림을 스케줄링할 수 있습니다. 휴리스틱 접근 방식은 다른 휴리스틱 접근 방식보다 성능이 뛰어나 더 적은 GCL 항목을 생성하지만, 약간 더 나쁜 스케줄 비율을 보입니다. 이 접근 방식과 비교하여, 우리는 스케줄된 트래픽을 위한 하나의 송신 큐에 초점을 맞춥니다. 제안된 접근 방식 중 일부는 최대 800개의 스트림과 30개의 스위치에 대해 결과적인 GCL 항목 수를 따라잡거나 능가할 수 있습니다. 그러나 논문에서 사용된 네트워크 자원에 대한 충분한 정보가 없습니다. 더 나아가, 우리는 더 낮은 실행 시간을 보여주고 산업 및 자동차 사용 사례에 더 가까운 평가를 수행합니다. [16]에서 제시된 연구는 SMT 솔버를 적용하여 TSN 스트림을 스케줄링합니다. 우리 접근 방식의 일부와 유사하게, 그들은 GCL 주기를 모든 스트림 주기의 최대공약수(GCD)로 설정합니다. 그들은 작은 사용 사례로 알고리즘을 평가하고 GCD 기반 접근 방식이 더 나은 실행 시간을 보이고 구성된 슬롯을 재사용할 수 있다고 말합니다. 그러나 저자들은 GCL 구성이나 대역폭 활용에 대한 통계를 보고하지 않습니다.
우리는 [17], [18]을 기반으로 시스템 모델을 설명합니다. 네트워크는 양방향 그래프 G(N, L)로 표시되며, 여기서 N은 네트워크 노드 집합을, L은 노드 간 링크 집합을 정의합니다. 각 링크 lij ∈ L은 노드 ni ∈ N과 nj ∈ N (i != j) 사이의 단방향 논리적 링크를 정의합니다.
(그림 4와 5는 원본 PDF의 시각 자료로, 텍스트로 설명합니다.) 그림 4: 스트림 S1의 스트림 및 지연 특성. 스트림 S1은 발신자 talk(S1)에서 수신자 list(S1)로 경로 pt1을 따라 이동합니다. 각 링크(li,j)에서 전송 지연(Dtrans), 전파 지연(Dprop), 처리 지연(Dproc)이 발생합니다. 그림 5: 그림 4에 대한 S1의 무대기(no-wait) 스케줄링. 상단 시나리오: S1이 다른 스트림으로 점유된 슬롯을 만나면, 무대기 가정을 위반합니다. 하단 시나리오: 스트림 S1의 시작 오프셋(φ1)을 조정하여 충돌을 피하고 무대기 가정을 만족시킵니다.
r(li,j)는 링크 li,j의 링크 속도를 반환합니다. 스케줄링될 스트림은 집합 S로 표시됩니다. 각 스트림 sk ∈ S는 튜플 (pk, φk, dk, lk, ptk)로 정의됩니다. 여기서 pk는 스트림 주기, φk는 pk 시작을 기준으로 한 발신자의 릴리스 오프셋, dk는 pk 시작을 기준으로 한 상대적 마감 시간을 나타냅니다. 우리는 마감 시간이 주기와 같다고 가정합니다. 그러나 이 가정은 조정될 수 있습니다. 결과적인 스케줄링 오프셋은 스케줄링 알고리즘에 의해 조정될 수 있으며 Φk, Φk ≥ φk ≥ 0으로 설명됩니다. sk의 크기는 물리 및 데이터 계층 프로토콜 오버헤드를 포함하여 lk로 정의됩니다. 스트림 경로는 링크 시퀀스로 구성된 ptk로 표시됩니다. 함수 talk(sk)는 스트림의 발신자를, list(sk)는 수신자를 반환합니다. 단순화를 위해, 각 스트림은 하나의 수신자를 가지며 하나의 이더넷 프레임을 전달한다고 가정합니다. 고려되는 스트림 지연은 다음과 같습니다 [17]:
예시 스트림 S1에 대한 일부 스트림 지연 및 특성이 그림 4에 설명되어 있습니다. 우리는 스트림이 발신자에서 전송을 시작할 때마다 송신 포트 큐에서 다른 스트림을 만나지 않고 경로를 따라 이동하는 무대기(no-wait) 방식으로 TSN 스트림을 스케줄링하는 데 중점을 둡니다. 따라서 스트림은 네트워크 리소스에 독점적으로 액세스하며 큐잉 지연을 겪지 않습니다. 큐잉 지연 고려는 그 자체로 연구 분야이며, 예를 들어 네트워크 미적분학(Network Calculus) [19], [20]과 같은 분석 프레임워크를 사용하여 수행될 수 있습니다. 그림 5는 S1의 무대기 스케줄링을 보여줍니다. 상단 시나리오에서 S1은 링크 li,j에 오프셋 Φ1 = 0으로 할당됩니다. 다음 링크 lj,m에서의 무대기 전송 시작 시간은 Φ1 + Dtrans,1 + Dprop + Dproc이 됩니다. 이 시간 단계에 이미 다른 스트림이 스케줄링되어 있고 S1이 전송을 기다려야 하므로, 우리는 무대기 가정을 위반하게 됩니다. 따라서 우리는 첫 번째 링크 li,j에서 S1을 필요한 오프셋만큼, 이 경우 점유된 슬롯의 크기만큼 이동시켜야 합니다. S1은 결과적으로 조정된 시작 오프셋 Φ’1 > 0을 가지게 되고, 무대기 원칙이 충족됩니다.
나머지 지연은 정적 지연 및 하드웨어 종속으로 간주됩니다. 결과적으로, 스트림 오프셋 Φk를 무시한 스트림 sk의 종단 간 전송 지연 e2ek는 다음 식으로 계산됩니다: e2ek = Σ (Dproc + Dtrans,k + Dprop) (식 1, 경로의 모든 링크에 대해)
식 (1)에서, 발신자는 종단 스테이션에서 처리 지연을 고려하지 않습니다. 우리는 또한 실제 시스템에서 고려되어야 할 클럭 편차를 무시합니다. 스케줄은 식 (2)가 모든 스케줄된 스트림에 적용될 경우 실현 가능합니다. ∀sk ∈ S: Φ’k + e2ek ≤ dk (식 2)
(이하 내용은 알고리즘 분류, 세부 구현, GCL 구성 최적화, 스케줄 압축, 유전 알고리즘 조정 등 기술적인 세부 사항에 대한 설명입니다. 각 섹션의 핵심 내용을 요약하여 번역합니다.)
(그림 6은 알고리즘 분류를 나타내는 트리 구조입니다.) 알고리즘은 크게 조화(Harmonic) 주기와 비조화(Non-harmonic) 주기를 다루는 경우로 나뉩니다. 조화 주기는 서로 배수 관계에 있지만, 비조화 주기는 그렇지 않습니다.
핵심 스케줄링 단계는 제시된 알고리즘 중 하나를 사용하여 실현 가능한 스케줄을 찾는 것입니다. 모든 알고리즘은 우리가 [17]에서 제안한 슬롯 탐색 알고리즘을 사용합니다. 이 논문에서는 교대, 정렬 및 하이퍼주기 변형으로 알고리즘을 확장합니다. 스케줄링 단계 동안, 우리는 민감 트래픽을 위한 슬롯만 고려하고 전체 대역폭이 민감 트래픽에 사용 가능하다고 가정합니다.
알고리즘의 목표는 각 스트림 sk에 대해 경로 ptk를 따라 큐잉 지연 없이 정적 네트워크 지연만 겪도록 적합하고 겹치지 않는 슬롯을 찾는 것입니다. 알고리즘은 발신자에서 초기 오프셋 φk로 시작하여 sk를 ptk의 각 링크에 배치하려고 시도합니다. 적합한 슬롯이 없으면 Φk는 적절한 빈 슬롯이 발견되거나 실현 가능한 해를 찾을 수 없을 때까지 Φ’k로 이동합니다.
성공적인 스케줄은 각 스트림에 대한 최종 전송 오프셋과 점유된 슬롯을 제공하고 네트워크 리소스에 대한 독점적인 액세스를 보장합니다. 그 후, GCL 항목의 구성이 완료되어야 합니다. GCL 항목 수를 줄이기 위해 슬롯을 병합하는 최적화 과정을 거칩니다. 인접한 두 민감 스트림 슬롯 사이의 간격이 최대 전송 단위(MTU) 프레임의 전송 시간보다 작으면, 두 슬롯과 그 사이의 간격을 하나의 더 큰 민감 슬롯으로 병합합니다. 이는 GCL 항목 수를 줄이지만, 사용되지 않는 대역폭(낭비)을 발생시킬 수 있습니다.
[6]에서 소개된 스케줄 압축 기법을 적용합니다. 이 기법은 스케줄된 스트림들을 서로 더 가깝게 이동시켜 낭비되는 대역폭을 줄이려고 시도합니다. 스케줄된 스트림들을 결과적인 종단 간 시간의 내림차순으로 정렬한 후, 가장 늦은 스트림을 기준으로 다른 스트림들을 충돌 없이 최대한 가깝게 이동시킵니다.
정렬된 스트림 순서를 사용하는 GA의 경우, 염색체 인코딩과 진화 연산자를 약간 조정해야 합니다. 동일한 주기를 가진 스트림들을 하나의 하위 그룹으로 묶고, 이 하위 그룹들을 주기 오름차순으로 정렬합니다. 교차 및 돌연변이 연산은 전체 염색체가 아닌 이 하위 그룹 내에서만 작동하도록 수정됩니다(PBX-Sort, Swap-Sort).
평가는 Intel Core i7-8550U CPU, 24GB RAM 환경에서 수행되었습니다. 스위치 수(3~30개), 스트림 수(50~800개), 네트워크 토폴로지(스타, 링, 메시)를 다양하게 하여 실험했습니다. 링크 속도는 1Gbps로 설정했습니다. 조화 주기 집합은 {2, 4, 8, 16, 32} ms, 비조화 주기 집합은 {2, 4, 5, 10, 20} ms를 사용했습니다.
본 논문에서는 무대기(no-wait) 접근 방식을 사용하여 민감한 TSN 스트림을 스케줄링하는 휴리스틱 및 메타휴리스틱 알고리즘 집합을 제시했습니다. 이 알고리즘들은 입력 데이터 순서, 스케줄링 절차, GCL 구성에 다양한 수정을 적용하며, 이는 필요한 GCL 슬롯 수와 대역폭 활용에 영향을 미칩니다.
평가 결과, 다음과 같은 결론을 도출할 수 있습니다.
요약하면, 스케줄링 알고리즘의 수정은 특히 조화 주기 알고리즘 클래스에서 네트워크 자원 사용에 큰 영향을 미치며, 정교하게 설계된 휴리스틱 알고리즘이 스케줄링 문제를 해결하는 데 매우 적합하다는 것을 보여줍니다. 이러한 고려 사항은 문헌에서 종종 간과됩니다.
(원본 논문의 참고문헌 목록입니다. 번역하지 않고 그대로 둡니다.)
[1] Time-Sensitive Networking (TSN) Task Group. [Online]. Available: https://1.ieee802.org/tsn/ … (이하 생략) … [25] A. Arestova, L. Maile, N. Halikulov, K.-S. Hielscher, and R. German, “Joint Task and Flow Scheduling for Time-Triggered and Strict-Priority Networks,” in 2023 International Conference on Computing, Networking and Communications (ICNC), 2023, pp. 608–614.
(저자들의 약력입니다.)
ANNA ARESTOVA … REINHARD GERMAN … KAI-STEFFEN J. HIELSCHER …