802.1Qbv 네트워크에서의 대역폭 활용 및 게이트 제어 목록 구성 최적화

IEEE 802.1 시간 민감형 네트워킹(TSN) 태스크 그룹은 2012년부터 IEEE 802 네트워크를 통해 결정적이고 시간 비판적인 서비스를 제공하기 위한 다양한 표준을 개발해 왔습니다. 시간 인식 셰이퍼(TAS)는 시간 민감형 네트워크 트래픽의 정확한 전달 및 셰이핑을 가능하게 하기 위해 도입된 TSN의 핵심 구성 요소입니다. 이를 통해 선택된 트래픽 클래스에 대한 독점적인 전송 슬롯을 구성할 수 있습니다. TAS의 이점을 최대한 활용하기 위해, TAS 기반 네트워크에서 스트림 종단 간 전송 시간을 최적화하는 시간 비판적 네트워크 스트림 전송 스케줄을 찾기 위한 수많은 스케줄링 알고리즘이 제시되었습니다. 그러나 기존 연구의 대부분은 중요 네트워크 트래픽 스케줄링이 하드웨어에서 제한되는 중요 전송 슬롯의 필요 수와 다른 트래픽 클래스에 대한 결과적인 대역폭 활용에 어떤 영향을 미치는지 다루지 않습니다. 본 논문에서는 TAS 기반 네트워크에서 중요 네트워크 스트림을 스케줄링하기 위한 선택된 휴리스틱 및 메타휴리스틱 알고리즘이 네트워크 리소스 활용에 어떤 영향을 미치는지, 그리고 압축 알고리즘을 사용하여 TAS 구성을 개선할 수 있는 방법을 조사했습니다. 따라서 기존 알고리즘을 활용하고 입력 데이터 순서, 스케줄링 절차 및 TAS 구성에 영향을 미치는 대안을 제안합니다. 평가 결과, 제안된 수정 사항 중 일부는 대역폭 활용도를 개선하고 중요 트래픽에 대한 전송 슬롯 수를 크게 줄일 수 있음을 보여주었습니다. 또한 압축 알고리즘은 일부 경우 현저한 개선을 가져올 수 있습니다.

시간 민감형 네트워킹(TSN) [1]의 도입은 실시간 시스템에서 이더넷 기술을 사용할 수 있는 가능성을 보여줍니다. 한편으로는 동일한 네트워크에서 중요 트래픽과 비중요 트래픽의 공존이 허용되고, 다른 한편으로는 공급업체 종속성을 피할 수 있으면서도 서로 다른 공급업체 및 장치 간의 상호 운용성이 확립될 수 있다는 점에서 특히 매력적입니다. 특히 시간 비판적 네트워크 트래픽(TSN 스트림)과 관련하여 서비스 품질(QoS), 특히 지연 시간 보장 및 낮은 지터 [2]를 제공하기 위한 다양한 메커니즘을 특징으로 합니다. 연구에서 가장 널리 사용되는 TSN 셰이퍼 중 하나는 [3]에서 소개된 시간 인식 셰이퍼(TAS)입니다. 이는 트래픽 클래스에 시간 슬롯을 할당하는 원리로 작동합니다.

그러나 이 메커니즘은 표준 자체에서 지원되지 않는 적절한 구성에 의존하며 중요 네트워크 트래픽의 양과 네트워크 인프라에 크게 좌우됩니다. 부적절한 구성은 훨씬 더 나쁜 지연 시간, 지터 및 대역폭 활용으로 이어지거나, 안전이 중요한 애플리케이션이 관련된 경우 심각한 결과를 초래할 수 있는 마감 시간 누락으로 이어질 수도 있습니다. 자율 주행과 같은 혁신은 수많은 안전 중요 애플리케이션, 다수의 센서 및 액추에이터, 결과적으로 더 높은 안전 중요 네트워크 트래픽 부하 [4]를 동반합니다.

여러 논문에서 TAS의 시간 비판적 슬롯 구성과 함께 시간 민감형 네트워크 트래픽 스케줄링을 다루었습니다. 그러나 대다수는 개별 네트워크 스트림의 종단 간 지연 준수에 초점을 맞추었고 TAS 구성의 어려움과 한계를 고려하지 않았습니다. 한편, 구성 가능한 슬롯 수는 하드웨어에 의해 제한되며, 이는 종종 생략되어 제안된 알고리즘을 무효화할 수 있습니다. 다른 한편으로는 구성된 슬롯 사이에 사용 불가능한 간격이 발생하여 대역폭이 낭비될 수 있습니다. TSN은 혼합 중요성을 촉진하여 중요 및 비중요 네트워크 트래픽이 동일한 네트워크에 공존할 수 있도록 하므로, 중요 네트워크 트래픽의 낭비된 대역폭 및 리소스 활용에 대한 조사는 특히 덜 중요한 트래픽에 대해 관련성이 높아집니다. 자동차나 기차와 같은 운송 시스템에서는 인포테인먼트, 텔레매틱스 및 원격 진단과 관련된 네트워크 트래픽을 발견할 수 있습니다. 실시간 트래픽이 대역폭 활용과 관련하여 효과적으로 계획되지 않으면 필수 리소스를 독점하고 낭비함으로써 인포테인먼트, 텔레매틱스 및 진단 시스템의 성능에 영향을 미칠 수 있습니다. 그러나 사용 불가능하고 남은 대역폭을 비중요 트래픽 클래스에 대해 고려하는 것은 자주 생략됩니다.

본 논문에서는 주기적이고 중요한 TSN 스트림을 스케줄링하고 기존 알고리즘의 앞서 언급한 한계를 해결하기 위해 TAS 구성 및 대역폭 활용의 한계를 고려하는 휴리스틱 알고리즘 및 메타 휴리스틱 알고리즘 세트를 소개합니다. 따라서 입력 데이터 속성 및 시퀀스, 스케줄링 최적화 기술 및 특정 TAS 특성을 변경하여 제안된 알고리즘이 합성 시나리오에 미치는 영향을 조사합니다. 실행 시간, 스케줄링 가능성, 확장성 및 대역폭 활용에 대한 알고리즘을 검토하고 사용자의 요구 사항에 따라 적절한 TAS 알고리즘 선택에 대한 권장 사항을 제공합니다. 또한 [5]에서 제안된 스케줄 압축의 이점을 연구하여 중요 트래픽에 대한 구성된 슬롯 수와 대역폭 낭비를 줄일 것을 약속합니다.

우리의 주요 기여는 종단 간 지연 시간 준수에 초점을 맞출 뿐만 아니라 처음부터 입력 데이터 속성 및 리소스 특성과 한계를 고려하는 알고리즘 설계입니다. 이 알고리즘은 기존 연구에서 대부분 무시되는 스케줄링 단계와 TAS 구성 단계를 포함합니다. 또한 우리가 아는 한, 802.1Qbv 네트워크에 대한 네트워크 리소스 할당에 대한 철저한 평가를 제시하며, 이는 그 범위에서 타의 추종을 불허합니다.

논문은 다음과 같이 구성됩니다. 섹션 II에서는 이 논문의 기본 사항을 소개합니다. 관련 연구는 섹션 III에서 다룹니다. 섹션 IV에서는 시스템 모델을 제시하고 섹션 V에서는 적용된 스케줄링 알고리즘을 제시합니다. 섹션 VI에서는 알고리즘을 평가하고 비교합니다. 섹션 VII에서는 결론을 도출합니다.

TSN은 시간, 안정성 및 리소스 관리 동기화 메커니즘 외에도 지연 시간 보장을 제공하기 위해 TAS를 포함한 셰이퍼 및 스케줄러 세트를 제공합니다. 네트워크 트래픽 분류는 TAS의 핵심 기능입니다. 이는 네트워크 트래픽을 가상 근거리 통신망(VLAN) 태그(이더넷 헤더 내)의 우선 순위 코드 포인트(PCP) 값을 기반으로 여러 네트워크 클래스로 나눕니다. PCP 값은 0-7의 정수 범위를 가져 8개의 트래픽 클래스를 생성합니다. TSN 스트림이라는 용어는 소스(송신자)에서 시작하여 하나 이상의 대상(수신자) [6]으로 전파되는 하나 이상의 일관된 네트워크 패킷 시퀀스를 정의합니다. TAS는 시분할 다중 접속(TDMA) 원리에 따라 작동하며, 시간을 여러 슬롯으로 나누어 하나 이상의 트래픽 클래스를 위해 동시에 예약할 수 있습니다. 정의된 비중첩 시간 슬롯 시퀀스는 구성 가능한 주기 후에 반복됩니다. 시간 슬롯의 스케줄은 게이트 제어 목록(GCL) [3]으로 표시됩니다. 시간 슬롯팅 원리를 구현하기 위해 표준 802.1Qbv는 물리적 포트의 각 송신 큐에 하나씩 소위 게이트를 도입했습니다(그림 1 참조). 일반적으로 각 트래픽 클래스에 대해 하나씩 8개의 송신 큐가 물리적 포트 [7]에서 사용 가능합니다. [8]에 따르면, 실시간 트래픽을 포함하는 가장 높은 우선 순위 트래픽에는 하나의 송신 큐로 충분합니다. 하나의 게이트는 GCL 항목에서 활성으로 설정될 때마다 트래픽을 통과시킵니다. 그렇지 않으면 비활성화되어 큐의 프레임이 전송되는 것을 방지하므로 전송 선택에서 큐가 고려되지 않습니다. 그림 1a에서 큐는 각 GCL 항목의 비트 배열로 인코딩됩니다. 가장 왼쪽 위치는 가장 높은 우선 순위와 관련이 있고 가장 오른쪽 위치는 가장 낮은 우선 순위와 관련이 있습니다. 0은 게이트가 비활성임을 의미하고 1은 슬롯에서 활성임을 나타냅니다. 이 그림은 GCL에 따라 게이트 드라이버에 의해 제어되는 시간 인식 게이트가 있는 8개의 송신 큐를 보여줍니다. 우선 순위 7의 큐는 스케줄링된/중요 트래픽을 위한 큐를 나타냅니다. 이 큐는 [T0;T1] 및 [T2;T3] 간격에서 독점적으로 서비스됩니다. 여러 게이트가 동시에 활성화되면 전송 선택은 가장 높은 우선 순위의 큐를 먼저 서비스하는 엄격한 우선 순위 스케줄링(SP)과 같은 스케줄링 알고리즘에 따라 작동합니다. 큐의 프레임은 선입 선출 방식으로 제거됩니다. TAS의 이점을 얻으려면 공통된 시간 개념이 필요합니다. 이는 IEEE 802.1 AS [9]에서 최대 1µs의 편차로 제공될 수 있습니다.

또한 게이팅 메커니즘만으로는 중요 시간 슬롯이 비중요 네트워크 트래픽의 침입으로부터 보호되지 않습니다. 중요 트래픽에 대한 슬롯 시작 시간 직전에 비중요 이더넷 프레임 전송이 시작된 경우 즉시 선점할 수 없습니다. 최악의 경우 이더넷 데이터 및 물리 계층 오버헤드를 고려한 1542바이트의 최대 전송 단위(MTU) 크기 패킷의 침입을 의미합니다. 침입 상황을 피하기 위해 IEEE 802.1Qbv는 시간 슬롯 끝에 적용되고 게이트와 관련된 소위 가드 밴드를 정의합니다. 활성 가드 밴드 간격에서 전송 준비가 된 패킷은 보류되며 해당 클래스에 할당되지 않은 시간 슬롯으로 침입하지 않습니다. 이는 가드 밴드가 고정된 크기(최악의 경우 MTU 전송 크기)를 갖고 프레임이 침입을 유발하지 않고 통과할 수 있는지 확인하는 특수 논리를 특징으로 하지 않는 경우 발생합니다 [3]. 그림 1b는 유선 직렬화를 보여주고 가드 밴드가 고정된 크기를 가지는 사용 사례를 보여줍니다. TAS 사이클 n에서 중요하지 않은 프레임 하나가 가드 밴드가 시작되기 직전에 도착하여 전송됩니다. 다른 중요하지 않은 프레임은 TAS 사이클 n+1에 도착합니다. 이 프레임은 중요하지 않은 슬롯에 맞을 수 있음에도 불구하고 가드 밴드에 의해 보류되어 대역폭이 낭비됩니다. 이 그림은 또한 예약된 슬롯이 완전히 활용될 필요는 없다는 것을 분명히 보여줍니다. 사용되지 않는 슬롯 시간, 특히 중요 슬롯에서의 시간은 대역폭 낭비로 이어집니다. 그림 1b에서, 사이클 n의 S1과 S2 사이에 이러한 사용되지 않는 여유 공간이 발생하며, 이는 우선순위가 낮은 트래픽 클래스에 할당될 수 있습니다. TDMA 원칙은 중요 트래픽에 이점을 제공하지만 다른 트래픽 클래스에는 단점을 보여줍니다.

그러나 실행 가능한 게이트 구성을 찾는 것은 복잡한 작업입니다. 수백 개의 시간 비판적인 네트워크 스트림이 모든 스트림이 종단 간 전송 마감 시간을 충족할 수 있도록 지금까지 소규모 또는 대규모 네트워크에 걸쳐 스케줄링되어야 할 수 있기 때문입니다. 서로 다른 송신 포트의 두 개 이상의 게이트가 하나 이상의 스트림을 공유할 때마다 인접 장치의 게이트 시간은 조정되어야 합니다. 그 목적은 불필요한 지연을 피하는 것입니다. 이를 위해서는 본 연구에서 다룰 신중한 스케줄링 접근 방식이 필요합니다.

우리는 중요하지 않은 슬롯의 낭비된 대역폭에 대해 충분한 지식이 없으므로 가정을 할 수 없습니다. 그러나 필요한 슬롯 수와 결과적인 가드 밴드로 스케줄링 알고리즘을 평가하고 중요 슬롯에서 낭비된 대역폭을 결정할 수 있습니다. TSN 스트림의 스케줄링, 네트워크의 GCL 구성, 그리고 중요 슬롯의 대역폭 활용에 대해 더 자세히 다룰 것입니다.

고려된 알고리즘 중 일부는 유전 알고리즘(GA) [10]을 사용하므로 이 섹션에서 소개합니다. GA는 생물학적 진화 과정, 즉 자연 선택과 유전학을 포함하는 과정에서 영감을 얻었습니다. 이는 여러 단계로 구성된 무작위 검색 기술입니다([11] 참조):

1) 초기화: 개체의 초기 모집단이 생성됩니다. 이 모집단은 첫 번째 세대를 나타냅니다. 각 개체는 문제에 대한 해결책을 나타내며 인코딩된 염색체로 구성됩니다. 염색체는 종종 비트 또는 문자열 표현 [12]을 갖는 유전자 값 세트를 갖습니다. 2) 적합도 평가: 각 개체는 해결책의 품질을 나타내는 적합도 함수를 통해 적합도 값을 할당받습니다. 3) 선택: 다음 세대를 위해 개체의 일정 비율이 선택됩니다. 더 나은 적합도 값을 가진 개체가 생존할 가능성이 더 높습니다. 4) 재생산: 이 단계에서 선택된 개체는 두 개체에 교차 연산을 적용하거나 하나 이상의 개체를 무작위로 돌연변이시켜 교배되고 돌연변이됩니다. 이 과정은 새로운 자손을 생성합니다. 5) 교체: 모집단 크기를 유지하면서 개체의 일부가 생성된 자손으로 교체됩니다. 종종 엘리트주의적 접근 방식 [13, p. 347]에 설명된 대로 최상의 개체가 다음 세대로 넘어갑니다. 6) 반복 또는 종료: 단계 1-5를 다시 실행하거나 종료 조건(예: 세대 수 또는 지정된 실행 시간)이 충족될 때까지 반복합니다.

TSN 스트림 스케줄링은 순열 문제 [11]에 매핑될 수 있습니다. 각 염색체는 스케줄링될 모든 스트림의 시퀀스를 인코딩하며, 변수로 인식될 수 있는 각 유전자는 스트림의 고유 식별자(예: 문자열 표현)를 포함합니다. 유전자 값은 대립 유전자라고도 합니다. 염색체는 스트림이 왼쪽에서 오른쪽으로 스케줄링되는 순서를 설명합니다. 그림 2는 스트림 인코딩의 예를 보여줍니다. 평가 단계에서 위치 기반 교차(PBX)와 스왑 돌연변이 연산자가 우리 문제에 가장 적합하다는 것을 발견했습니다.

PBX는 두 개의 개체를 취하고 염색체 크기보다 작은 임의의 위치 수를 결정합니다. 그림 3에서는 인덱스 1과 4를 선택합니다. 두 개의 새로운 자손이 생성됩니다. 자손의 염색체는 선택된 위치에 의해 결정되는 유전자를 상속하며, 각 자손은 부모 중 하나로부터 상속받습니다. 그림 3의 자손1은 개체1로부터 인덱스 1의 S2와 인덱스 4의 S5를 상속받습니다. 자손의 나머지 위치는 부모의 유전자 순서를 준수하면서 다른 부모의 고유한 요소로 채워집니다. 우리 예에서는 자손1의 인덱스 0에 개체2의 값 S2를 사용합니다. 그러나 S2는 이미 자손1에 있으므로 S3로 계속합니다. S3는 자손1에 없으므로 인덱스 0 등에 배치될 수 있습니다. 스왑 돌연변이 연산자는 모집단에서 한 개체를 가져와 염색체에서 두 개의 무작위 유전자를 선택합니다. 그런 다음 유전자 위치가 바뀝니다. 자세한 정보는 이전 연구 [11]를 참조하십시오.

본 연구에서는 TSN 스트림 스케줄링을 위한 다양한 알고리즘을 소개하고, 추가적으로 TAS 구성 방법을 제공하는 동시에 네트워크 리소스 사용에 대한 심층적인 평가를 수행합니다. TAS 관련 스케줄링 문제는 여러 번 다루어지고 검토되었습니다. 그러나 우리가 아는 한, 대역폭 활용 및 낭비 최적화와 함께 스케줄링 및 구성에 대한 통합된 접근 방식을 제시하는 다른 연구는 없습니다. 먼저 GCL 구성 및 리소스 활용을 고려하지 않고 주로 종단 간 스트림 지연 준수에 초점을 맞춘 관련 TSN 스케줄링 접근 방식을 검토할 것입니다. 이 분야에서 가장 많이 검토된 연구 중 하나는 Craciunas 등의 [14]입니다. 저자들은 만족도 계수 이론(SMT)을 사용하며, 이는 주어진 공식(이 경우 제약 조건)에 대해 만족 가능한지 여부를 결정합니다. 이 접근 방식은 흐름 및 장치 크기를 변경하면서 4시간 범위 내에서 최대 1500개의 TSN 스트림을 스케줄링할 수 있습니다. 그들은 주로 스케줄링 측면과 결과적인 런타임 성능에 중점을 두었습니다. 또한 그들의 알고리즘은 여러 송신 큐를 사용할 수 있도록 합니다. 런타임 측면에서 우리의 성능은 유사한 네트워크 토폴로지의 성능을 능가합니다. 그러나 해당 데이터가 제공되지 않았으므로 성공률이나 결과적인 종단 간 지연을 비교할 수 없습니다. [10]에 제시된 접근 방식은 GA를 적용하여 시간 민감형 네트워크에서 시간 트리거 트래픽을 스케줄링합니다. 저자들은 상호 의존성이 있는 TSN 스트림의 라우팅 및 스케줄링 문제를 해결하기 위한 GA를 제안하지만 GCL 구성에 대해서는 자세히 다루지 않습니다. 우리가 라우팅 문제나 스트림의 상호 의존성을 다루지 않는다는 점을 감안할 때 이 연구와의 직접적인 비교는 불가능합니다. 그러나 TAS 기반 스케줄링을 위한 유전 알고리즘 설계, 특히 하나의 스트림을 하나의 유전자와 연관시키는 염색체 인코딩 및 결과적인 스케줄의 메이크스팬을 개략적으로 설명하는 적합도 함수에서 유사점을 공유합니다.

또한 TSN 스트림의 공동 스케줄링과 GCL 구성에 주목하는 몇 가지 연구가 있습니다. Dürr와 Nayak [5]은 TSN 스트림 스케줄링을 위한 타부 검색 알고리즘을 구현하고 무대기 원칙을 통합했습니다. 스케줄링 단계 후 GCL 항목 수와 가드 밴드를 줄이기 위해 압축 알고리즘을 수행합니다. 우리는 무대기 접근 방식을 채택하고 이후에 수정된 압축 함수도 수행합니다. 유사한 네트워크 구성에 대해 제안된 알고리즘은 인용된 연구에 비해 런타임 측면에서 우수한 성능을 보여줍니다. 이 연구와 달리 우리는 서로 다른 조화 또는 비조화 주기를 허용하는 반면, [5]는 모든 스트림에 대해 동일한 주기를 고려합니다. 그럼에도 불구하고 저자들은 스케줄링 가능성이나 대역폭 활용에 관한 평가는 제시하지 않았습니다. Jing 등 [15]은 가드 밴드를 줄이기 위해 최대 4개의 큐를 사용하여 네트워크에서 허용되는 GCL 항목 수를 고정한다고 가정합니다. 그들은 SMT, 최적화 계수 이론(OMT) 및 사용자 정의 휴리스틱 접근 방식을 적용하여 스케줄링 문제를 해결합니다. SMT 변형은 최대 100개의 흐름을 포함하는 소규모 사용 사례에 대한 실행 가능한 스케줄을 찾는 데 약 2일이 걸립니다. OMT 접근 방식은 이틀 안에 최대 10000개의 스트림을 스케줄링할 수 있습니다. 휴리스틱 접근 방식은 다른 휴리스틱 접근 방식보다 성능이 뛰어나 스케줄링해야 하는 GCL 항목이 줄어들지만 스케줄 비율은 약간 더 나빠집니다. 이 접근 방식과 비교하여 우리는 스케줄링된 트래픽에 대한 하나의 송신 큐에 중점을 둡니다. 제안된 여러 접근 방식은 최대 800개의 스트림과 30개의 스위치에 대한 결과적인 GCL 항목 수를 유지하거나 능가할 수 있습니다. 그러나 논문에서 사용된 네트워크 리소스에 대한 지식이 충분하지 않습니다. 또한 더 낮은 런타임을 보여주고 산업 및 자동차 사용 사례에 더 가까운 평가를 수행합니다. 또한 GCL 항목 수와 대역폭 활용을 제어하기 위한 더 다양한 절차를 제공합니다. [16]에 제시된 연구는 SMT 솔버를 적용하여 TSN 스트림을 스케줄링합니다. 우리 접근 방식의 일부와 유사하게 모든 스트림 주기의 최대 공약수(GCD)로 GCL 주기를 설정합니다. 소규모 사용 사례로 알고리즘을 평가하고 GCD 기반 접근 방식이 더 나은 런타임을 보여주고 구성된 슬롯을 재사용할 수 있다고 명시합니다. 그러나 저자들은 GCL 구성이나 대역폭 활용에 대한 통계는 보고하지 않습니다.

우리는 [17]과 [18]을 기반으로 시스템 모델을 설명합니다. 네트워크는 양방향 그래프 G(N, L)로 표시되며, 여기서 N은 네트워크 노드 집합을 정의하고 L은 노드 간 링크 집합을 정의합니다. 각 링크 lij ∈ L은 노드 ni ∈ N과 nj ∈ N (i != j) 사이의 단방향 논리적 링크를 정의합니다. 메서드 r(li,j)은 li.j의 링크 속도를 반환합니다. 스케줄링될 스트림은 집합 S로 표시됩니다. 각 스트림 sk ∈ S는 튜플 (pk, Ok, dk, lk, ptk)로 정의되며, pk는 스트림 주기, Ok는 송신자의 릴리스 오프셋, dk는 pk 시작을 참조한 상대적 마감 시간, lk는 물리 및 데이터 계층 프로토콜 오버헤드를 포함한 sk의 크기, ptk는 링크 시퀀스로 구성된 스트림 경로를 나타냅니다. 함수 talk(sk)는 스트림의 송신자를 반환하고 list(sk)는 수신자를 반환합니다. 단순화를 위해 각 스트림에는 하나의 수신자가 있고 하나의 이더넷 프레임을 전달한다고 가정합니다. 상당한 스트림 지연은 다음과 같습니다([17] 참조): • 스트림 sk가 링크 lij에서 유선으로 sk의 비트를 전송하는 데 걸리는 시간을 설명하는 전송 지연 Dtrans,k = (lk × 8 비트/바이트)/r(li,j)), • 케이블 속성에 따라 비트가 링크의 한쪽 끝에서 다른 쪽 끝으로 이동하는 데 걸리는 시간을 나타내는 전파 지연 Dprop, 그리고 • 스위칭 논리에 따라 네트워크 노드 ni의 처리 지연 Dproc.

일부 스트림 지연 및 특성은 예시 스트림 S1에 대해 그림 4에 설명되어 있습니다. 우리는 스트림이 송신자에서 전송을 시작할 때마다 송신 포트 큐에서 다른 스트림을 만나지 않고 경로를 따라 이동하는 것을 나타내는 무대기 방식으로 TSN 스트림을 스케줄링하는 데 중점을 둡니다. 따라서 스트림은 네트워크 리소스에 독점적으로 액세스하며 큐잉 지연을 경험하지 않습니다. 큐잉 지연 고려는 자체 연구 분야를 정의하며 예를 들어 네트워크 미적분학 [19], [20]과 같은 분석 프레임워크를 사용하여 수행할 수 있습니다. 그림 5는 S1에 대한 무대기 스케줄링을 보여줍니다. 상단 시나리오에서 S1은 오프셋 Φ1 = 0으로 링크 lij에 할당됩니다. 다음 링크 lj,m에서의 무대기 전송 시작 시간은 Φ1 + Dlij trans.1 + Dprop + Dproc이 됩니다. 이 시간 단계에 이미 다른 스트림이 스케줄링되어 있고 S1이 전송을 기다려야 하므로 무대기 가정을 위반하게 됩니다.

따라서 첫 번째 링크 lij에서 S1을 필요한 오프셋만큼, 이 경우 점유된 슬롯의 크기만큼 이동해야 합니다. 결과적으로 S1은 조정된 시작 오프셋 Φ*1 > 0을 얻고 무대기 원칙이 충족됩니다. 나머지 지연은 정적 지연 및 하드웨어 종속으로 간주됩니다. 결과적으로 스트림 오프셋 ok를 무시한 sk의 종단 간 전송 지연 e2ek는 다음과 같이 계산됩니다: 모든 lij ∈ ptk에 대해: e2ek = Σ (Dproc + Dtrans,k + Dprop) (방정식 1)

그림 1에서 송신자는 종단 스테이션에서 처리 지연을 고려하지 않습니다. 실제 시스템에서 고려해야 하는 클록 편차도 무시합니다. 스케줄은 다음 조건이 모든 스케줄링된 스트림 sk ∈ S에 대해 만족될 경우 실행 가능합니다: Φ*k + e2ek ≤ dk. (방정식 2)

시스템 모델에서 가정한 내용을 따르는 TAS 가능 네트워크에 대한 스케줄링 알고리즘 분류를 섹션 V-A에서 제시할 것입니다. 구현 세부 정보는 섹션 V-C에서 제시될 것입니다. 제시된 스케줄링 접근 방식의 주요 목표는 스트림 종단 간 마감 시간을 준수하고 메이크스팬을 최소화하는 것입니다. 메이크스팬은 가장 빠른 스트림의 전송 시작부터 결과 스케줄에서 가장 늦은 스트림의 전송 종료 시간까지의 유효한 스케줄 길이를 정의합니다. 우리 연구의 목표는 어떤 알고리즘이 최상의 메이크스팬을 제공하는지 조사하는 것뿐만 아니라 어떤 스케줄링 변형이 가장 효율적인 대역폭 활용 및 GCL 구성을 제공하는지 조사하는 것입니다. 따라서 입력 데이터 속성을 고려하고 입력 데이터 순서, 스케줄링 절차 및 GCL 구성에 영향을 미치는 알고리즘 변형을 제안합니다.

이 연구의 주요 부분은 종단 간 스트림 지연 및 네트워크 리소스 활용과 관련된 스케줄 품질에 영향을 미치는 스케줄링 알고리즘 설계입니다. 따라서 그림 6에 설명된 대로 TAS 알고리즘의 계층적 분류를 확인했습니다. 계층의 각 수준에는 고유한 구별 특성이 있습니다. 이 구별은 TAS 속성, 다른 응용 분야 및 사용 사례에서 파생되었으며 메이크스팬과 네트워크 리소스 활용에 영향을 미칩니다. 최상위 수준에서 스케줄링 알고리즘을 스트림 주기가 선택되는 방식을 나타내는 조화 및 비조화 변형으로 세분화합니다. 이 분류는 입력 데이터의 특성을 나타냅니다. 조화 주기는 비조화 주기와 대조적으로 서로의 배수입니다. 조화 주기는 [21]과 [22]에 명시된 대로 산업 실시간 통신 시스템의 특징입니다. 특히 자동차 시스템에서는 비조화 주기도 관련이 있습니다[23]. 일반적으로 모든 스케줄링 알고리즘은 모든 스트림 주기의 최소 공배수인 하이퍼피리어드 hp 길이의 스케줄을 생성합니다. 각 스트림 sk는 경로의 각 링크에서 하이퍼피리어드 내에 hp/pk번 스케줄링되어야 합니다. 스케줄은 각 하이퍼피리어드 후에 반복됩니다. 각 TAS 가능 송신 포트에 대한 최종 결과 GCL 주기는 조화 및 비조화 주기의 경우 하이퍼피리어드 크기에 맞춰지거나 조화 주기의 경우 스트림 주기의 GCD로 변환 및 축소될 수 있습니다. 이 세분화는 그림 6의 조화 클래스 아래에 설명되어 있으며 TAS의 GCL 구성에 영향을 미칩니다. GCD는 가장 작은 주기의 크기를 가지며 다른 모든 주기와 하이퍼피리어드는 그 배수입니다. GCL 주기를 GCD로 줄이면 섹션 V-D에 자세히 설명된 대로 중요 트래픽에 필요한 GCL 항목 수를 줄이는 데 도움이 됩니다. GCL 주기를 줄이려면 하이퍼피리어드를 GCD 길이의 여러 세그먼트로 세분화하여 hp/GCD 세그먼트를 생성해야 합니다(그림 7a 상단 및 하단 시나리오 참조). 이 그림은 다른 스트림이 이미 스케줄링된(점유된 슬롯) 송신 포트에서 S1과 S2의 예시적인 스케줄링을 보여줍니다. 원칙적으로 GCD 및 하이퍼피리어드 변형(HYPO)에서 스트림 sk를 계획하는 것은 sk가 링크의 GCD 세그먼트 경계를 넘어 계획되지 않는다는 중요한 예외를 제외하고 유사하게 작동합니다(섹션 V-C). GCL 주기가 GCD로 설정되고 GCL 주기 간의 전송 동작이 하드웨어에서 명확하게 정의되지 않으므로 GCD 알고리즘은 GCD 경계를 넘어 스트림을 계획하지 않습니다. 그림 7b는 두 GCD 주기 사이에 S2를 배치하는 HYPO 알고리즘을 보여줍니다. 비조화 주기의 GCD는 스트림 주기보다 훨씬 작을 수 있고 결과적으로 상당한 계획 및 관리 오버헤드로 이어질 수 있으므로 비조화 분기는 GCD 분기를 무시합니다.

다음은 조화 및 비조화 변형에 적용됩니다. 각 변형은 무작위 순서의 스트림 또는 정렬된 스트림 순서로 실행될 수 있습니다. 이 분류는 데이터의 입력 순서를 나타냅니다. 정렬은 스트림 주기의 오름차순으로 수행됩니다. 결과적으로 계획할 첫 번째 스트림은 가장 작은 주기를 가진 스트림입니다. 정렬 접근 방식은 낮은 주기(더 높은 속도)의 작업을 먼저 계획하는 작업 스케줄링을 위한 잘 확립된 속도 단조 알고리즘 [24]과 관련될 수 있습니다.

추가적으로 GCD 클래스의 교대 및 비 교대 버전을 고려합니다. 교대는 부하 분산 접근 방식을 따르며 GCD의 배수인 주기를 가진 스트림이 가장 적게 점유된 GCD 세그먼트에 먼저 계획됨을 의미합니다. 교대 분기는 스케줄링 단계와 통합된 대역폭 활용을 위한 최적화 프로세스를 나타냅니다. 그림 7a는 교대 및 비 교대 접근 방식의 예를 보여줍니다. 두 경우 모두 GCD 기간의 배수인 4ms 주기의 S1이 첫 번째 GCD 세그먼트에 스케줄링됩니다. 그런 다음 4ms 주기의 S2도 스케줄링됩니다. 첫 번째 세그먼트가 이제 더 높은 점유율을 가지므로 교대 접근 방식에서는 S2가 두 번째 세그먼트에 스케줄링됩니다. 비 교대 시나리오에서는 S2가 첫 번째 세그먼트의 첫 번째 맞는 슬롯에 스케줄링됩니다.

분류 트리의 리프는 스케줄링 문제를 해결하는 절차를 설명합니다. 입력 스트림은 스케줄링 문제에 특화되어 설계된 휴리스틱 접근 방식으로 스케줄링될 수 있습니다. 주어진 스트림 순서로 한 번 실행되고 평가됩니다(1S, 원샷). 다른 옵션은 GA입니다. 휴리스틱과의 차이점은 GA가 스트림 순서의 여러 순열을 조사하고 여러 세대에 걸쳐 진화시켜 개체의 적합도 값을 나타내는 메이크스팬을 개선한다는 것입니다.

하나의 스케줄링 알고리즘은 조화/비조화 세분화에서 시작하여 1S/GA 리프로 끝나는 알고리즘 클래스의 조합으로 정의되며, 이는 16가지 다른 조합으로 이어집니다. 한 가지 조합은 예를 들어 H_GCD_Sorted_ALT_GA입니다. 그림 8은 전체 스케줄링 절차의 단계를 보여줍니다. 선택된 조합에 관계없이 동일한 단계를 따릅니다. 첫 번째 주요 단계는 알고리즘 선택입니다. 처음에는 스케줄링을 위해 조화 또는 비조화 주기를 가진 스트림 세트가 주어집니다. 이러한 스트림의 주기를 기반으로 조화 또는 비조화 변형을 선택합니다. 그런 다음 입력 데이터를 순서대로 정렬할지 아니면 무작위로 둘지 결정하여 해당 결정을 스케줄링 클래스에 매핑합니다. 조화 클래스로 작업하고 GCL 주기를 GCD에 맞추려는 경우 GCD 클래스를 선택합니다. 이 경우 교대 접근 방식을 선택하여 균형 효과를 적용할 수 있습니다. 그런 다음 알고리즘은 주어진 스트림 순서에서 차례로 하나의 스트림을 추출하고 섹션 V-C에서 제안된 슬롯 검색 전략에 따라 1S 또는 GA 절차로 적절한 스케줄링 슬롯을 찾으려고 시도합니다. 성공하면 모든 링크에서 스트림의 슬롯 점유가 결정되어 GCL 설정으로 전달되며, 여기서 활용되는 각 링크의 지정된 GCL 항목이 계산됩니다(섹션 V-D). 원하는 경우 GCL 구성은 섹션 V-E에서 소개된 스케줄 압축 절차를 사용하여 이후에 최적화될 수 있습니다.

기본 스케줄링 단계는 제시된 16개 알고리즘 중 하나를 사용하여 실행 가능한 스케줄을 찾는 것으로 구성됩니다. 모든 알고리즘은 [17]에서 소개한 슬롯 검색 알고리즘을 사용합니다. 이전 연구 [17]에서 제시된 구현은 H_GCD_Rand_1S 접근 방식만 다룹니다. 본 논문에서는 [17]의 슬롯 검색 알고리즘을 재사용하고 교대, 정렬 및 HYPO 변형으로 확장합니다. 스케줄링 단계 동안 중요 트래픽에 대한 슬롯만 고려하고 전체 대역폭이 중요 트래픽에 사용 가능하다고 가정합니다.

[17]에서 제안된 슬롯 검색 알고리즘과 마찬가지로 스케줄링 알고리즘의 목표는 각 스트림 sk에 대해 경로 ptk를 따라 큐잉 지연 없이 정적 네트워크 지연만 경험하도록 적합하고 겹치지 않는 슬롯을 찾는 것입니다. 알고리즘은 송신자에서 초기 오프셋 Φk로 시작하여 ptk의 각 링크에 sk를 배치하려고 시도합니다. 적합한 슬롯이 없으면 적절한 빈 슬롯이나 실행 가능한 해결책을 찾을 수 없을 때까지 Φk가 Φ*k로 이동됩니다. ptk의 각 링크에서 하나의 스트림 주기만큼 떨어진 등거리 시간 슬롯을 찾고 연속 링크 lij와 ljm의 슬롯이 무대기 접근 방식을 유지하기 위해 Dtrans,k + Dprop + Dproc 시간 단계만큼 떨어져 있도록 요구합니다. 등거리 슬롯은 종단 간 시간의 지터를 줄이는 데 도움이 됩니다. 각 송신 포트는 비어 있고 점유된 시간 슬롯을 추적합니다. 스트림이 스케줄링될 때마다 새로운 시간 슬롯을 점유하고 빈 슬롯을 줄입니다. sk가 하이퍼피리어드에 여러 번 맞는 경우 각 링크에서 hp/pk 등거리 슬롯을 찾습니다. 이러한 단계는 모든 변형에 공통적입니다.

그림 9는 링크 li,j에서 Φ1 = 0 및 p1 = hp/2인 S1에 대한 HYPO 기반 계획 프로세스를 보여줍니다. S1은 하이퍼피리어드 내에서 두 번 스케줄링되어야 합니다. 알고리즘은 간격 [0;p1) 및 [p1;hp)에서 빈 슬롯을 찾습니다. 여기서 S1을 첫 번째 세그먼트와 두 번째 세그먼트의 빈 슬롯에 배치하여 시작 시간이 pk만큼 떨어지도록 할 수 있습니다. 빈 슬롯 내 S1의 위치는 빈 슬롯의 시작 또는 종료 시간과 일치할 필요는 없습니다. 경우에 따라 Φ1을 이동하여 실행 가능한 슬롯을 찾아야 합니다. 다음 링크에서 Φ*1+Dtrans,1 + Dprop + Dproc에서 시작하는 슬롯 검색을 진행합니다(그림 5 참조).

GCD 기반 접근 방식은 하나의 스트림 주기만큼 떨어진 GCD 세그먼트에서 빈 슬롯을 찾는다는 차이점을 제외하고 유사하게 작동합니다. 비 교대 GCD 클래스에 대한 세그먼트 기반 검색은 이전 연구 [17]에서 이미 제시되었습니다. 그림 10과 그림 11은 크기가 2ms인 4개의 GCD 세그먼트를 사용한 예시적인 GCD 계획을 보여줍니다. S1과 같이 주기가 2ms인 스트림은 각 GCD 세그먼트에 스케줄링됩니다. 주기가 4ms인 스트림 S2는 하나의 스트림 주기만큼 떨어진 두 개의 세그먼트(예: 첫 번째 및 세 번째 세그먼트(GCD 인덱스 0 및 2) 또는 두 번째 및 네 번째 세그먼트)에 스케줄링되어야 합니다. 비 교대 GCD 및 HYPO 접근 방식은 가장 빠른 적합 및 첫 번째 적합 솔루션을 적용하는 반면, 교대 버전은 가장 적게 점유된 GCD에서 슬롯 검색을 시작하는 부하 분산 전략을 구현합니다. 그림 10에서 S2는 초기 오프셋 Φ2 = 0ms를 갖습니다. 비 교대 접근 방식은 [Φ2/GCD] = 0 및 2로 인덱싱된 가장 빠른 세그먼트에서 l2에 충분히 큰 빈 슬롯을 검색합니다. 그림 11에서 Φ2 = 2.5ms입니다. 따라서 비 교대 알고리즘은 인덱스 1과 3에서 슬롯 검색을 시작합니다. 교대 알고리즘은 세그먼트 {0,2}와 {1,3}의 대역폭 점유를 검사하고 가장 적게 점유된 조합에서 슬롯 검색을 시작합니다. 다른 알고리즘 클래스는 슬롯 검색 알고리즘에는 영향을 미치지 않고 순서와 전체 절차에 영향을 미칩니다.

성공적인 스케줄은 각 스트림에 대한 최종 전송 오프셋과 점유된 슬롯을 제공하고 네트워크 리소스에 대한 독점적인 액세스를 보장합니다. 그 후 GCL 항목 구성이 완료되어야 합니다. 네트워크는 활용되는 모든 송신 포트의 GCL 주기를 모든 스트림의 하이퍼피리어드로 설정하고 경로를 따라 각 스트림에 대해 하나의 GCL 항목을 할당할 수 있습니다. 구성 시간은 스트림의 점유된 슬롯에 의해 주어집니다. 그러나 결과적인 GCL 항목 할당에는 다른 트래픽 클래스에서 사용할 수 없는 많은 간격이 있을 수 있습니다. 또한 TAS의 모든 트래픽 클래스에 대한 구성 가능한 슬롯 수는 종종 강력하게 제한됩니다. 소규모 및 실험적 설정의 경우 약 128 GCL 항목에서 최대 1024 항목 [16]까지 다양합니다. 따라서 각 스트림에 대해 독점적인 항목을 만드는 것이 불가능할 수 있습니다. 그림 13a에서 HYPO 알고리즘은 9개의 슬롯을 할당하는 반면, 그림 13b에서 GCD 알고리즘은 동일한 양의 중요 네트워크 트래픽에 대해 5개의 슬롯을 생성합니다.

이러한 과제는 그림 12의 예에서 강조됩니다. 네트워크에서 하나의 스트림만 스케줄링되는 경우 통과하는 모든 포트의 GCL 주기를 스트림 주기로 설정할 수 있습니다. t = 0에서 전송을 시작하는 스트림 sk에 GCL 슬롯을 할당한다는 것은 중요 트래픽용 슬롯 하나와 다른 트래픽 클래스용 슬롯 하나 등 최소 두 개의 슬롯을 구성하는 것을 의미합니다. 스트림이 t > 0인 링크에서 전송되는 경우 sk 전송 전후에 중요하지 않은 트래픽을 위한 다른 슬롯을 만들거나 이전 또는 다음 시간 창을 스트림 슬롯과 병합할 수 있습니다. 슬롯 병합은 필요한 GCL 항목 수를 줄이지만 사용되지 않는 대역폭으로 이어질 수 있습니다. 더 많은 스트림의 경우 구성, 병합 및 GCL 주기에 대해 더 많은 결정을 내려야 합니다.

알고리즘 1의 슬롯 구성 방법은 중요 스트림에 대한 GCL 슬롯을 구성하고 최적화합니다. 그 사이의 슬롯은 최선형 트래픽 클래스를 위해 예약됩니다. 이 알고리즘은 스케줄링 알고리즘 중 하나에서 생성된 점유된 스트림 슬롯의 유효 집합 C를 수신합니다.

먼저 링크 속도에 따라 유선상 1542바이트의 MTU 크기 프레임 전송 시간을 나타내는 maxTrans를 결정합니다(알고리즘 1의 라인 1). 스케줄링 알고리즘이 GCD 변형인 경우 GCD 범위의 항목을 만들기 위해 유효 전송 시간을 정규화해야 합니다(라인 2). 슬롯 정규화는 다음과 같이 표시됩니다: newSlotStartTime = oldSlotStartTime % GCLPeriod newSlotEndTime = oldSlotEndTime % GCLPeriod.

정규화된 뷰는 GCD 알고리즘에 대해 그림 13b에 제시되며, 그림 13a는 GCD에 대한 비정규화된 뷰와 동시에 HYPO 접근 방식에 대한 정규화된 표현을 보여줍니다. 정규화는 HYPO 변형에는 영향을 미치지 않습니다. 정규화된 스트림 슬롯을 전송 슬롯 시작 시간의 오름차순으로 정렬합니다(라인 3). GCL 주기는 알고리즘 분류에 따라 GCD 또는 하이퍼피리어드로 설정됩니다. 가장 빠른 슬롯부터 시작하여 먼저 GCL 주기 시작과 가장 빠른 슬롯 refSlot 시작 사이에 간격이 있는지 확인합니다(라인 5-7). 간격이 maxTrans보다 작으면 사용되지 않는 창을 스트림 슬롯과 병합하고 낭비된 대역폭을 합산합니다. 섹션 II-A에서 논의한 대로 가드 밴드는 maxTrans의 고정된 크기를 갖는다고 가정합니다. 이 선택된 창 크기는 더 작은 창 크기와 대조적으로 가드 밴드 시간 전에 도착하는 경우 최소한 하나의 최선형 이더넷 프레임이 통과할 수 있도록 보장합니다. 라인 9-10에서는 다음 슬롯(slot)을 제거하고 slot과 참조 슬롯 refSlot 사이의 간격을 계산합니다. 차이가 maxTrans보다 크거나 같으면 refSlot의 시간과 크기로 GCL 항목을 만들고 slot.start와 refSlot.end 사이의 간격을 다른 트래픽 클래스를 위해 남겨둡니다(라인 11-13). 이 경우 slot은 다음 반복에서 참조 슬롯이 됩니다. 슬롯 간의 차이가 maxTrans보다 작으면(라인 14) 두 시작 시간의 최소값(라인 16)과 두 종료 시간의 최대값(라인 17)을 취하여 refSlot과 slot을 병합합니다. 예시적인 슬롯 병합 접근 방식은 그림 13에 설명되어 있습니다. GCD 변형에서 slot의 시작 시간은 refSlot의 시작 시간보다 크거나 같지만, 정규화하고 시간을 시작 시간별로 정렬하므로 종료 시간은 더 작을 수 있습니다. 병합된 슬롯은 이 조건에서 다음 반복의 참조 슬롯입니다.

이 절차를 모든 슬롯에 대해 반복하고(라인 8-18) 마지막으로 마지막 슬롯과 GCL 주기 종료 사이의 간격을 검사합니다(라인 20-24). 전체 절차 동안 병합된 슬롯에 있는 모든 간격을 합산하여 낭비된 대역폭도 계산합니다(라인 6,15). HYPO 변형에서 사용되지 않는 슬롯은 인접한 두 중요 슬롯 사이(그림 13a)와 하나의 중요 슬롯과 GCL 주기의 시작 또는 끝 사이(그림 12 참조)에만 발생합니다. GCD 기반 변형에서는 병합된 슬롯을 다른 GCD에서 실행되는 여러 스트림에서 사용할 수 있습니다(그림 13b 참조). 하나의 정규화된 스트림 슬롯이 다른 슬롯(예: 그림 13b의 S2 및 S3가 있는 S1)과 겹치는 경우 영향을 받는 모든 GCD 세그먼트(우리 예에서는 GCD0 및 GCD1)에 대한 낭비된 슬롯 크기의 평균을 취합니다. 특히 교대 접근 방식은 다른 스트림에 의한 병합된 슬롯의 재사용을 지원합니다[16]. 알고리즘에 GCL 항목의 특정 제한을 포함하지는 않지만 그렇게 하도록 알고리즘을 확장할 수 있습니다.

본 논문에서 적용되는 또 다른 접근 방식은 스케줄 압축입니다. 이는 [5]에서 간략하게 소개되었습니다. 스케줄 압축은 그림 14에 설명된 대로 낭비되는 대역폭을 줄이고 스트림 전송이 서로 더 가까워지도록 스케줄링된 스트림을 이동하려고 시도합니다. 슬롯 구성 부분 후 스케줄 압축이 유용한지 검토합니다. 따라서 스케줄링된 스트림을 결과적인 종단 간 시간의 내림차순으로 정렬합니다. 가장 늦은 종단 간 시간을 가진 첫 번째 스트림(참조 스트림)을 선택하고 정렬된 목록에서 경로를 교차하는 스트림을 찾습니다. 그런 다음 교차하는 스트림의 최대 종단 간 마감 시간이 누락되지 않도록 교차하는 스트림을 참조 스트림에 더 가깝게 이동하려고 시도합니다. 이동은 sk의 결과 오프셋 Φ*k를 증가시키는 것으로 구성됩니다. 따라서 다른 스케줄링된 스트림과 겹치지 않고 교차하는 스트림의 전체 경로에서 실행 가능한 이동 값을 찾아야 합니다. 정렬된 목록의 다음 스트림을 참조 스트림으로 사용하여 절차를 계속합니다. 이동 작업으로 인해 연속적인 스트림이 분리되고 대역폭 활용이 악화되는 경우 이동 단계를 무시합니다. 마지막으로 이동된 버전이 대역폭 활용을 개선하는지 여부에 따라 이전 계획을 사용할지 아니면 이동된 계획을 사용할지 최종적으로 결정합니다.

섹션 II-B에서는 스트림의 입력 순서를 염색체에 인코딩하는 방법과 적용할 수 있는 교차 및 돌연변이 연산자를 제시했습니다. 이러한 특성은 무작위 순서 알고리즘 클래스에 적합합니다. 그러나 정렬된 알고리즘 클래스는 스트림의 정렬된 순서(주기별)를 유지할 수 있도록 염색체 인코딩 및 진화 연산자에 약간의 조정이 필요합니다. 정렬된 접근 방식은 염색체에 하위 그룹을 만듭니다. 각 하위 그룹은 스트림 주기로 식별됩니다. 동일한 주기를 가진 스트림은 동일한 하위 그룹에 할당됩니다(그림 15 참조). 하위 그룹은 염색체 내 하위 그룹 주기의 오름차순으로 정렬됩니다. 이 알고리즘에 대해 선택된 교차 연산자는 수정된 PBX 버전인 PBX-Sort이고 선택된 돌연변이 연산자는 스왑 돌연변이의 수정된 버전인 Swap-Sort입니다. 차이점은 수정된 연산자가 전체 염색체가 아닌 하위 그룹에서 작동한다는 것입니다. 요약하자면, 무작위로 추출된 하위 그룹에 적용되며 하위 그룹 내 변경으로 이어질 수 있습니다.

GA 알고리즘 클래스에 대해 선택된 매개변수는 표 1에 요약되어 있습니다. 일반적으로 더 큰 모집단 크기와 더 많은 세대 수가 공간 탐색 및 활용을 위한 더 나은 해결책으로 이어질 수 있습니다. 그러나 런타임 폭증을 피하기 위해 모집단 크기 30과 세대 수 20을 선택했습니다. 교차 및 돌연변이 연산자와 비율의 선택은 실험적으로 결정되었습니다.

우리는 이전 연구 [17]의 Java 기반 GCD 방법을 사용하여 스케줄링 알고리즘 세트를 개발했으며, 여기에는 H_GCD_Rand_GA 변형만 포함되었습니다. 정렬, 교대, GA 및 모든 HYPO 변형으로 구현을 확장했습니다. GA 변형은 Java 언어로 작성된 Jenetics 프레임워크2의 도움으로 구현되었습니다. 평가는 1.88GHz 클록 속도와 24GB RAM을 갖춘 Intel(R) Core(TM) i7-8550U CPU에서 수행되었습니다. 스케줄링 알고리즘의 모든 변형을 테스트하기 위해 다음 매개변수를 변경했습니다: • 스위치 수: {3, 5, 10, 20, 30} • 종단 스테이션 수: [ [1;2] * 스위치 수 ] • 스트림 수: {50, 150, 200, 300, 500, 800} • 토폴로지: {스타, 링, 메시} • 스트림 길이: 84-1542바이트, 스트림당 하나의 프레임 • 전송 모드: 유니캐스트 스위치와 스트림 세트를 소규모에서 중간 규모 및 대규모 산업 네트워크로 그룹화하여 다음과 같은 결과를 얻었습니다([25] 참조): • 소규모/중간 규모 네트워크(SMN): {3, 5, 10} 스위치 및 {50, 150, 200} 스트림 • 대규모 네트워크(LN): {20, 30} 스위치 및 {300, 500, 800} 스트림 링크 속도는 오늘날 네트워크에서 잘 나타나는 1Gbps(초당 기가비트)로 설정되었습니다. 네트워크 토폴로지는 무작위로 생성되며 스트림도 무작위로 할당됩니다. 스트림 주기의 선택은 다음 조사에 상당한 영향을 미칩니다. 집합 {2, 4, 8, 16, 32} ms는 조화 주기를 식별합니다. 비조화 주기는 [23]에서 차량 도메인에 대해 식별된 대로 {2, 4, 5, 10, 20} ms입니다. 16개 알고리즘 클래스를 정의하는 그림 6의 모든 알고리즘 조합을 스위치 수, 스트림 수 및 실험의 각 조합에 대해 50번 실행했습니다. 스트림 주기는 조화 및 비조화 변형에 따라 다르지만 각 그룹 내에서는 동일합니다. 조화 및 비조화 사용 사례는 직접 비교할 수 없습니다. 그러나 주기 선택이 실험에 어떤 영향을 미치는지 설명하고자 합니다. 평가의 주요 목적은 스케줄링 알고리즘 실행에서 파생된 수치 결과를 기반으로 시간 성능, 스케줄링 가능성, 확장성 및 대역폭 활용을 관찰하는 것입니다. (각주 2: https://jenetics.io/)

합리적인 런타임은 신속한 프로토타이핑 및 재구성 시나리오에 특히 중요합니다. 그림 16은 스트림 수에 따른 다양한 알고리즘의 평균 시간 성능(초)을 보여줍니다. 실행 가능한 스케줄만 고려합니다. 스트림 수가 증가함에 따라 런타임이 증가하는 것이 분명해집니다. 휴리스틱 접근 방식은 선형적으로 30초 미만으로 수행되는 반면, GA는 200개 이상의 스트림에 대해 높은 런타임 증가를 보여줍니다. GA는 많은 수의 스트림에 대해 몇 분 범위에서 수행됩니다. 또한 이 그림은 HYPO 기반 알고리즘이 평균적으로 더 나쁜 성능을 보인다는 것을 보여줍니다. GCD를 사용하고 세그먼트를 교대하는 GA가 다른 GA 변형보다 성능이 좋습니다. 브리지 수가 증가함에 따른 시간 성능에 대해서도 유사한 결론을 도출할 수 있습니다(그림 16b 참조). 실험 NH_HYPO_Sorted_GA는 30개 스위치에 대해 개선됩니다. 한 가지 이유는 스트림이 네트워크 전체에 더 잘 분산되어 있기 때문일 수 있습니다. 따라서 슬롯 검색 알고리즘은 충돌하는 스트림을 덜 찾고 더 빠른 해결책을 찾습니다.

특히 1S 휴리스틱 알고리즘과 관련하여 성공률이 중요해집니다. GA는 수백 가지의 다양한 솔루션을 평가하고 순열하는 반면, 1S 알고리즘은 단 하나의 시도만 가집니다. 성공률은 실행 가능한 솔루션을 찾은 성공적인 실행 수(#s)를 성공적인 실행과 실패한 실행(#f)의 합으로 나눈 값으로 구성됩니다: #s / (#s + #f). 그림 17은 스트림 및 스위치 수와 관련된 모든 알고리즘의 성공률을 보여줍니다. {3,5,10} 스위치 및 {50,150,200} 스트림의 경우 모든 알고리즘이 100% 성공률을 보입니다. {20,30} 스위치 및 {50,150,200} 스트림의 조합의 경우 모든 비조화 변형이 더 나쁜 성능을 보이며, 특히 800개 스트림의 경우 더욱 그렇습니다. 반면 다른 알고리즘은 (거의) 100% 성공률을 제공합니다. GA 클래스는 비조화 실험에 대해 더 높은 성공률을 보입니다. 그림은 정렬이 성공률과 관련하여 비조화 사용 사례에 이점을 제공하지 않음을 보여줍니다.

네트워크 장치는 메모리가 제한적이고 종종 단순한 논리를 가지고 있으므로 결과적인 GCL 항목 수가 중요합니다. 이 시점에서 독자에게 중요 트래픽에 대해 계산된 항목 수가 실제 구성의 일부일 뿐임을 상기시킵니다. 구성을 평가하기 위해 모든 송신 포트 중에서 결과적인 중요 슬롯의 최대 수를 관찰했습니다. 이 숫자는 필요한 하드웨어 크기 조정을 결정합니다. 스케줄링 및 구성 단계 후 각 송신 포트에 대한 GCL 항목 수를 결과에서 추출할 수 있습니다. 그림 18a는 GCD에 대한 스위치 및 스트림 수가 증가함에 따라 항목 수가 증가하고 그림 18b는 HYPO 클래스에 대한 항목 수를 보여줍니다. 모든 GCD 기반 변형은 HYPO 알고리즘보다 낮은 숫자를 제공합니다. 무엇보다도 교대 변형, 특히 GA와 함께 사용되는 경우 최대 GCL 항목과 관련하여 최상의 성능을 보여줍니다. 비조화 알고리즘은 조화 및 HYPO 기반 변형보다 성능이 뛰어납니다. 한 가지 이유는 경우에 따라 홀수 주기를 더 잘 활용할 수 있기 때문입니다. 정렬 변형은 비정렬 변형과 유사하게 수행됩니다. 또한 스케줄 압축이 없는 경우(gclMaxWC)와 있는 경우(gclMaxC) 송신 포트에서 필요한 GCL 슬롯의 최대 수에 대한 백분율 개선/감소를 조사했습니다: impGclMax% = (gclMaxWC - gclMaxC) / gclMaxWC * 100%.

그림 18c는 GCD에 대한 impGclMax%를, 그림 18d는 HYPO 변형에 대한 impGclMax%를 보여줍니다. 압축 알고리즘은 GCD 기반 접근 방식을 최대 4%까지 개선할 수 있으며, 이는 덜 중요한 전송 슬롯이 필요함을 의미합니다. GCL 슬롯 수 개선은 GCL 항목 수가 훨씬 더 높기 때문에 하이퍼피리어드를 사용하는 알고리즘에 더 큰 영향을 미칩니다.

그림 19a는 GCD에 대한 대역폭 낭비를, 그림 19b는 HYPO 클래스에 대한 대역폭 낭비를 보여줍니다. 이 값은 그림 1의 sumUpWasted 단계에서 계산된 모든 사용된 포트에 대한 전체 네트워크의 대역폭 낭비를 나타냅니다. 여러 유사한 실험이 있으므로 유사한 테스트에 대해 기록된 모든 값의 최대값을 취합니다. 이 경우 모든 HYPO 변형은 교대 없는 GCD 변형보다 성능이 우수하며, 특히 NH_HYPO_Rand_1S 및 H_HYPO_Rand_1S가 그렇습니다. 다른 HYPO 알고리즘과 GCD 교대 1S 및 GA 변형은 중간에 위치합니다.

압축 후 낭비된 대역폭을 wastedC로 나타냅니다. 개선율(impWasted%)은 다음과 같이 설명됩니다: impWasted% = (wastedWC - wastedC) / wastedWC * 100%.

그림 19c는 압축 알고리즘이 특히 H_GCD_Rand_ALT_1S에 대해 낭비된 대역폭을 최대 7%까지 개선할 수 있음을 보여줍니다. 그림 19d에 설명된 대로 압축 기술은 HYPO 클래스에 대해서는 거의 장점이 없습니다. 또 다른 흥미로운 메트릭은 다른 트래픽 클래스의 잔여 대역폭입니다. 따라서 전체 네트워크에서 잔여 대역폭을 계산했습니다. 일반적으로 모든 HYPO 기반 알고리즘이 더 높은 사용 가능 대역폭을 보이며, 그 뒤를 H_GCD_Rand_ALT_GA 및 H_GCD_Sorted_ALT_GA 접근 방식이 따릅니다(그림 20 참조). 비 교대 GCD 알고리즘 H_GCD_Rand_1S, H_GCD_Rand_GA, H_GCD_Sorted_1S 및 H_GCD_Rand_GA가 최악의 성능을 보입니다. 또한 이 시나리오에서 교대 접근 방식은 높은 이점을 보여줍니다. 그러나 중요 GCL 슬롯 수가 많을수록 중요하지 않은 슬롯 수가 더 많아지고 중요하지 않은 트래픽 전송을 방해할 수 있는 가드 밴드가 더 많아집니다. 실제 사용 가능한 대역폭은 분석적으로 관찰하거나 시뮬레이션을 사용하여 관찰해야 합니다. 800개 스트림과 20-30개 스위치에 대한 링크의 최대 관찰된 활용률은 약 73%였지만 소규모 네트워크의 경우 최대 12%의 낮은 활용률을 보였습니다. 평균 활용률은 더 낮았습니다.

마지막으로, 조화 클래스(그림 3의 결과를 바탕으로 표 3 참조)와 비조화 클래스(그림 4의 결과를 바탕으로 표 4 참조) 각각에 대해 실행 가능한 솔루션들의 결과적인 메이크스팬(makespan)을 비교했습니다. 이 표들은 각 실험에서 가장 좋은 결과를 보인 기준 해법(H_GCD_Sorted_GA 또는 NH_HYPO_Sorted_GA) 대비 다른 알고리즘들의 메이크스팬이 얼마나 저하되었는지를 백분율로 나타냅니다. H_GCD_Sorted_GA는 모든 조화 주기 실험에서 가장 작은 메이크스팬을 제공하며 표 3의 기준선 역할을 합니다. 교대(Alternating) 버전들은 부하 분산 전략으로 인해 GCD의 첫 번째 적합(first-fit) 선택을 하지 않으므로 더 나쁜 메이크스팬을 보입니다. 비조화 주기 실험에서는 NH_HYPO_Sorted_GA가 가장 좋은 메이크스팬을 보이며 표 4의 기준선이 됩니다.

우리 연구에서는 이상적인 클록을 가정하고 작동합니다. 그러나 장치 클록 간의 드리프트는 실제 환경에서 일반적입니다. TSN용으로 설계된 IEEE 802.1AS-2020 사양 [9]은 마스터 클록과 슬레이브 클록 간에 1µs 이하의 클록 편차를 보장합니다. 장치 간 지연을 간단히 조정함으로써 이 편차는 시스템 모델에 원활하게 통합될 수 있어 실제 환경에서 제안된 알고리즘의 관련성과 적용 가능성을 보장합니다.

또한 장치의 시간 정밀도를 고려하지 않았습니다. 현재 우리 구현은 1나노초 정밀도를 가정합니다. 그러나 시간 스케일을 조정하여 각 시간 정밀도를 시스템 모델에 통합할 수 있습니다.

또한 우리 연구는 주로 유니캐스트 전송 모드에 중점을 두어 멀티캐스트 스트림을 간과했습니다. 우리 알고리즘은 멀티캐스트 스트림을 관리할 수 있지만 시스템 모델 설명을 용이하게 하기 위해 유니캐스트 스트림을 강조하기로 선택했습니다.

추가적으로 우리 분석은 중요 슬롯 내의 낭비된 대역폭에만 초점을 맞췄습니다. 실제 시나리오에서는 중요하지 않은 트래픽 클래스에 할당된 가드 밴드로 인해 추가적인 대역폭 낭비가 발생할 가능성이 있습니다. 이는 구성된 GCL 항목 수가 증가하면 대역폭 낭비가 증폭되어 HYPO 변형의 효율성을 잠재적으로 감소시킬 수 있다는 주장을 제기합니다. 그러나 중요하지 않은 트래픽의 동작에 대한 통찰력이 제한적이고 애플리케이션 도메인에 따라 크게 다르므로 이러한 조사는 시뮬레이션이나 분석 방법을 통해 수행해야 합니다.

본 논문에서는 무대기 접근 방식으로 중요 TSN 스트림을 스케줄링하고, 스트림의 지터 및 종단 간 지연을 최소화하며, GA 기반 접근 방식에서 스케줄의 메이크스팬을 최소화하는 휴리스틱 및 메타 휴리스틱 알고리즘 세트를 제시했습니다. 이 알고리즘은 입력 데이터 순서, 스케줄링 절차 및 GCL 구성에 다양한 수정을 적용합니다. 이는 필요한 GCL 슬롯 수와 대역폭 활용에 영향을 미칩니다. 런타임, 성공률, 필요한 GCL 항목의 최대 수, 그리고 대역폭 활용 및 낭비와 관련된 다양한 스케줄링 접근 방식을 평가했습니다. 조화 주기만 있고 최대 종단 간 마감 시간 준수가 충분하다면 교대 접근 방식이 적은 수의 GCL 항목과 낮은 대역폭 낭비를 제공하는 데 적합합니다. 교대는 대역폭의 더 나은 활용과 GCL 슬롯의 더 나은 재사용을 허용하는 부하 분산 접근 방식을 적용합니다. 또한 런타임이 중요한 요소가 아니라면 교대와 함께 사용하는 GA 변형이 조화 주기를 사용할 때 대역폭 통계 및 GCL 구성에 대한 최상의 결과를 제공합니다. 일반적으로 모든 GA 변형은 조화 및 비조화 분기에서 런타임을 제외한 모든 메트릭을 고려할 때 평균적으로 더 나은 성능을 보입니다. 정렬 버전은 비정렬 접근 방식에 비해 상당한 장점을 보이지 않습니다. 일반적으로 GCD 기반 알고리즘은 필요한 GCL 항목 수를 줄이는 데 유용합니다. HYPO와 결합된 조화 및 비조화 접근 방식은 교대 없는 GCD 변형에 비해 낭비 및 잔여 대역폭과 관련하여 훨씬 더 나은 결과를 보이지만 더 큰 토폴로지의 경우 필요한 GCL 항목 수가 많아질 수 있습니다. 이 경우 하드웨어 제한을 신중하게 고려해야 하며 슬롯 병합 접근 방식을 제한된 수의 GCL 항목을 고려하도록 조정해야 합니다. 또한 비조화 알고리즘 클래스는 다른 모든 알고리즘보다 큰 토폴로지에 대해 더 낮은 성공률을 보입니다. 또한 비조화 알고리즘 클래스는 정렬 접근 방식의 이점을 많이 얻지 못하는 반면, GA 추가는 더 큰 토폴로지에 대해 더 높은 성공률에 도달하는 데 도움이 됩니다. 또한 스케줄 압축은 개별적인 경우 결과에서 약간의 개선을 보였습니다.

요약하자면, 평가는 스케줄링 알고리즘 수정이 특히 조화 알고리즘 클래스의 경우 네트워크 리소스 사용에 큰 영향을 미치며, 정확하게 설계된 휴리스틱 알고리즘이 스케줄링 문제 및 그 이상을 해결하는 데 적합하다는 것을 보여줍니다. 이러한 고려 사항은 문헌에서 종종 무시됩니다.

TSN은 표준 이더넷 네트워크에서 시간 결정적 데이터 전송을 가능하게 하는 IEEE 표준 기술 그룹입니다. 기존 이더넷의 '최선형(best-effort)' 전송 방식과 달리, TSN은 특정 데이터 스트림이 정해진 시간 내에 예측 가능하게 전달되도록 보장합니다. 이는 산업 자동화, 자동차 내부 네트워크, 전문 오디오/비디오 전송 등 실시간성과 높은 신뢰성이 요구되는 다양한 애플리케이션에서 중요합니다. TSN을 통해 중요 데이터와 비중요 데이터가 동일한 네트워크 인프라를 공유하면서도 중요 데이터의 시간 제약 조건을 만족시킬 수 있습니다.

TAS는 TSN의 핵심 구성 요소 중 하나로, 시간 분할 다중화(TDMA) 원리를 사용하여 네트워크 스위치의 송신 포트에서 트래픽을 스케줄링합니다. TAS는 각 트래픽 클래스에 대해 특정 시간 슬롯 동안 게이트를 열고 닫는 방식으로 작동합니다. 이 게이트의 열림/닫힘 패턴은 게이트 제어 목록(GCL)에 의해 정의됩니다. 본 논문에서 TAS는 시간 비판적인 스트림(예: 제어 명령)이 정해진 시간 내에 전송되도록 보장하는 주요 메커니즘으로 사용됩니다. 연구의 초점은 이러한 TAS의 GCL 구성을 최적화하여 대역폭 활용도를 높이고 필요한 GCL 항목 수를 줄이는 데 있습니다.

GCL은 TAS에서 각 시간 슬롯 동안 어떤 트래픽 클래스의 게이트가 열리고 닫힐지를 정의하는 스케줄 표입니다. 이 목록은 반복되는 주기를 가지며, 하드웨어적으로 스위치에 설정됩니다. GCL 항목 수는 하드웨어 자원의 제약을 받기 때문에, 너무 많은 항목을 필요로 하는 스케줄은 실제 구현이 불가능할 수 있습니다. 또한, GCL 구성 방식에 따라 사용되지 않는 시간 간격(대역폭 낭비)이 발생할 수 있습니다. 이 논문에서는 효율적인 네트워크 운영을 위해 GCL 항목 수를 최소화하고, 동시에 중요 트래픽 슬롯 내의 대역폭 낭비를 줄이는 방향으로 GCL 구성을 최적화하는 방법을 연구합니다.

조화 주기란 스트림들의 전송 주기가 서로 정수배 관계에 있는 경우를 의미합니다 (예: 2ms, 4ms, 8ms). 반면, 비조화 주기는 스트림들의 주기가 서로 정수배 관계가 아닌 경우입니다 (예: 2ms, 5ms, 10ms). 이 논문에서는 입력 스트림들의 주기 특성에 따라 조화 또는 비조화 시나리오를 구분하여 스케줄링 알고리즘을 평가합니다. 일반적으로 조화 주기를 가진 시스템은 스케줄링이 더 용이하고 예측 가능성이 높지만, 실제 많은 시스템(특히 자동차 등)은 비조화 주기를 가진 스트림들을 포함합니다. 따라서 두 가지 경우 모두에 대한 알고리즘 성능 분석이 중요합니다.

유전 알고리즘은 생물학적 진화 원리에 기반한 최적화 기법입니다. 이 논문에서는 TSN 스트림 스케줄링 순서를 찾는 데 GA를 적용합니다. 각 가능한 스케줄링 순서를 '염색체'로 표현하고, 각 염색체의 '적합도'(예: 전체 스케줄 완료 시간인 메이크스팬)를 평가합니다. 그런 다음, 선택, 교차, 돌연변이와 같은 유전 연산을 통해 더 나은 적합도를 가진 해(스케줄)를 탐색해 나갑니다. GA는 복잡한 스케줄링 문제에서 휴리스틱 방법보다 더 광범위한 해 공간을 탐색하여 좋은 해를 찾을 가능성을 높일 수 있지만, 계산 시간이 더 오래 걸릴 수 있습니다.

스케줄 압축은 이미 생성된 스케줄에서 스트림들의 전송 시작 시간을 조정하여 스트림 간의 빈 공간(낭비된 대역폭)을 줄이려는 기법입니다. 스트림들의 마감 시간을 위반하지 않는 범위 내에서, 스케줄된 스트림들을 서로 더 가깝게 '압축'함으로써 네트워크 대역폭 활용도를 높이는 것을 목표로 합니다. 이 논문의 평가에 따르면, 특정 조건(특히 GCD 기반 알고리즘)에서 스케줄 압축은 낭비되는 대역폭을 줄이고 필요한 GCL 항목 수를 줄이는 데 기여할 수 있습니다.

A: GCD 기반 스케줄링과 HYPO 기반 스케줄링은 게이트 제어 목록(GCL)의 주기를 결정하는 방식에서 주요 차이가 있습니다. • **GCD (Greatest Common Divisor) 기반 스케줄링:** GCL의 주기를 모든 스트림 주기의 최대공약수로 설정합니다. 이는 GCL의 길이를 짧게 유지하여 필요한 GCL 항목 수를 줄이는 데 도움이 될 수 있습니다. 스트림들은 이 짧은 GCD 주기 내에 맞추어 스케줄링되며, GCD 주기 경계를 넘어서는 스케줄링은 일반적으로 허용되지 않습니다 (그림 7a 참조). 이 방식은 특히 모든 스트림 주기가 조화적( 서로 배수 관계)일 때 효과적일 수 있습니다. • **HYPO (Hyperperiod) 기반 스케줄링:** GCL의 주기를 모든 스트림 주기의 최소공배수인 하이퍼피리어드로 설정합니다. 하이퍼피리어드는 모든 스트림의 전체 반복 패턴을 포함하는 가장 짧은 시간 간격입니다. 스트림은 하이퍼피리어드 내에서 스케줄링되며, GCD 주기 경계에 제약을 받지 않습니다 (그림 7b 참조). 이 방식은 다양한 주기를 가진 스트림들을 유연하게 스케줄링할 수 있지만, GCL의 길이가 길어져 더 많은 항목을 필요로 할 수 있습니다. 본 논문에서는 이 두 가지 접근 방식과 그 변형들을 비교하며 각각의 장단점을 분석합니다.

A: 정적 스케줄링은 시스템이 실행되기 전에(오프라인에서) 모든 작업(이 경우, 네트워크 스트림)의 실행 순서와 시간 할당을 미리 결정하는 방식입니다. 한 번 스케줄이 결정되면, 시스템 실행 중에는 이 스케줄이 변경되지 않고 그대로 따릅니다. 이 논문에서 정적 스케줄링은 TSN 스트림들이 네트워크를 통해 전송될 시간과 경로를 사전에 계산하고 고정하는 것을 의미합니다. 이는 시간 결정성을 보장하는 데 매우 중요합니다. 예를 들어, 자율 주행 차량의 센서 데이터나 제어 명령과 같이 마감 시간 준수가 필수적인 스트림들은 정적 스케줄링을 통해 예측 가능한 시간에 목적지에 도달하도록 보장받을 수 있습니다. 논문에서 제안된 알고리즘들은 이러한 정적 스케줄을 생성하고 최적화하는 것을 목표로 합니다.

A: 네, 주요 수식과 알고리즘을 쉽게 풀어 설명드리겠습니다. • **방정식 (1) - 종단 간 전송 지연 (e2ek):** 이 수식은 하나의 데이터 스트림(예: 센서 데이터 패킷)이 네트워크 상의 출발지에서 목적지까지 도달하는 데 걸리는 순수 시간을 계산합니다. 이 시간은 패킷이 각 네트워크 장비(스위치 등)를 통과할 때 발생하는 처리 지연(Dproc), 패킷이 케이블을 통해 전송되는 데 걸리는 전송 지연(Dtrans,k), 그리고 신호가 케이블을 따라 이동하는 전파 지연(Dprop)의 합으로 이루어집니다. 기본적으로 '패킷이 얼마나 빨리 네트워크를 여행하는가'를 나타냅니다. (자세한 설명은 본문 내 수식 아래 'formula-explanation' 박스 참조) • **방정식 (2) - 스케줄 실행 가능 조건 (Φ*k + e2ek ≤ dk):** 이 수식은 생성된 스케줄이 실제로 유효한지를 판단하는 기준입니다. Φ*k는 스트림 k가 전송을 시작하는 시간, e2ek는 위에서 설명한 총 전송 시간, dk는 해당 스트림이 목적지까지 도착해야 하는 마감 시간입니다. 즉, '스트림의 실제 도착 시간(시작 시간 + 총 전송 시간)이 정해진 마감 시간보다 빠르거나 같아야 한다'는 조건입니다. 이 조건이 모든 스트림에 대해 만족되면 스케줄은 성공적이라고 할 수 있습니다. (자세한 설명은 본문 내 수식 아래 'formula-explanation' 박스 참조) • **알고리즘 1 (createCritGCLEntries):** 이 알고리즘은 스케줄링된 중요 스트림들을 바탕으로 실제 네트워크 스위치에 설정될 게이트 제어 목록(GCL) 항목들을 생성하는 과정을 설명합니다. 목표는 필요한 GCL 항목 수를 최소화하고, 동시에 슬롯들을 병합하는 과정에서 발생할 수 있는 대역폭 낭비를 계산하는 것입니다. 예를 들어, 매우 짧은 간격으로 연이어 전송되는 두 스트림이 있다면, 각각 별도의 GCL 항목을 만들기보다는 하나의 항목으로 병합하여 하드웨어 자원을 절약하려고 시도합니다. 이때 병합으로 인해 스트림 사이에 생기는 작은 빈 공간이 '낭비된 대역폭'으로 기록될 수 있습니다. (자세한 설명은 본문 '그림 12' 아래 알고리즘 설명 박스 참조) 이러한 수식과 알고리즘은 TSN 네트워크에서 데이터가 제시간에 안정적으로 전달되도록 스케줄을 짜고, 그 스케줄을 효율적으로 네트워크 장비에 설정하기 위한 핵심적인 도구들입니다.

A: 자율 주행 시스템은 수많은 센서(카메라, LiDAR, 레이더 등)로부터 데이터를 수집하고, 이를 기반으로 주변 환경을 인식하며, 차량을 제어하기 위한 명령을 액추에이터(조향, 제동 시스템 등)로 전달해야 합니다. 이러한 데이터와 명령들은 매우 시간 민감적이며, 정해진 시간 내에 신뢰성 있게 전달되지 않으면 심각한 안전 문제로 이어질 수 있습니다. 본 연구에서 제안하는 TSN 스케줄링 및 TAS 구성 최적화 기술은 자율 주행 차량 내부 네트워크에 직접 적용될 수 있습니다. 1. **시간 결정성 보장:** 센서 데이터, 제어 신호 등 안전에 중요한 스트림들이 예측 가능한 시간 내에 차량 내 ECU(전자제어장치) 간에 전달되도록 보장하여 시스템의 신뢰성을 높입니다. 2. **자원 효율성 증대:** GCL 항목 수를 최적화하고 대역폭 낭비를 줄임으로써, 제한된 차량 내 네트워크 자원을 효율적으로 사용할 수 있게 합니다. 이는 더 많은 센서나 기능을 추가할 수 있는 여유를 제공하거나, 네트워크 하드웨어 비용을 절감하는 데 기여할 수 있습니다. 3. **혼합 중요도 트래픽 관리:** 자율 주행 차량 네트워크에는 안전에 중요한 데이터뿐만 아니라 인포테인먼트 데이터와 같이 덜 중요한 데이터도 공존합니다. 본 연구의 알고리즘은 중요 트래픽의 QoS를 보장하면서 비중요 트래픽도 함께 처리할 수 있는 효율적인 스케줄링 방안을 제공합니다. 결론적으로, 이 연구는 자율 주행 차량이 보다 안전하고 효율적으로 작동하는 데 필요한 핵심 네트워크 기술인 TSN의 성능을 극대화하는 데 기여할 수 있습니다.

본 연구의 주요 기여는 다음과 같습니다: 1. 다양한 TSN 스케줄링 알고리즘(휴리스틱 및 유전 알고리즘 기반)을 제안하고, 이들이 TAS 구성 및 네트워크 자원 활용(대역폭, GCL 항목 수)에 미치는 영향을 종합적으로 분석했습니다. 2. 입력 데이터의 주기 특성(조화/비조화), GCL 주기 설정 방식(GCD/하이퍼피리어드), 입력 순서 정렬, 교대 스케줄링 전략 등 다양한 요소를 고려한 알고리즘 분류 체계를 제시하고 각 조합을 평가했습니다. 3. 스케줄 압축 기법의 효과를 정량적으로 분석하고, 특정 시나리오에서의 유용성을 입증했습니다. 4. 실제 네트워크 장치의 제약(제한된 GCL 항목 수)과 성능 목표(낮은 지연, 높은 대역폭 활용)를 동시에 고려한 통합적 접근 방식을 제시하여, 기존 연구에서 간과되었던 TAS 구성의 실제적 측면을 다루었습니다.

본 연구는 몇 가지 가정 하에 진행되었으며, 이에 따른 한계점이 존재합니다: 1. 이상적인 클록 동기화를 가정했습니다. 실제 시스템의 클록 편차는 시스템 모델에 통합될 수 있지만, 본 연구에서는 명시적으로 다루지 않았습니다. 2. 장치의 시간 정밀도(예: 나노초 수준)를 가정했지만, 다양한 정밀도에 대한 영향은 분석되지 않았습니다. 3. 주로 유니캐스트 전송에 초점을 맞추었으며, 멀티캐스트 스트림 스케줄링은 상세히 다루지 않았습니다. 4. 비중요 트래픽의 동적인 동작과 가드 밴드로 인한 추가적인 대역폭 낭비는 심층적으로 분석되지 않았습니다. 향후 연구 방향으로는 이러한 한계점들을 극복하기 위해, 실제 클록 편차 및 정밀도 모델링, 멀티캐스트 스케줄링 통합, 그리고 시뮬레이션을 통한 비중요 트래픽과의 상호작용 분석 등을 포함할 수 있습니다. 또한, 제안된 알고리즘들을 실제 하드웨어 플랫폼에 적용하여 실질적인 성능을 검증하는 것도 중요한 다음 단계가 될 것입니다.