일관된 오버헤드 바이트 스터핑
Consistent Overhead Byte StuffingCOBS(Consistent Overland Byte Stuffing)는 데이터 바이트를 인코딩하는 알고리즘으로, 패킷 콘텐츠에 관계없이 효율적이고 신뢰할 수 있으며 모호하지 않은 패킷 프레임을 초래하므로, 수신 애플리케이션이 잘못된 형식의 패킷으로부터 쉽게 복구할 수 있다.패킷 구분 기호(패킷 간 경계를 나타내는 특수 값) 역할을 하기 위해 일반적으로 0인 특정 바이트 값을 사용한다.0을 구분 기호로 사용할 경우 알고리즘은 0 데이터 바이트를 0이 아닌 값으로 대체하여 0 데이터 바이트가 패킷에 나타나지 않도록 하여 패킷 경계로 잘못 해석된다.
바이트 스터핑은 '불법' 또는 '예비' 값(패킷 구분 기호 등)을 포함할 수 있는 데이터 바이트 시퀀스를 해당 값의 발생이 없는 잠재적으로 더 긴 시퀀스로 변환하는 프로세스다.변환된 시퀀스의 추가 길이를 일반적으로 알고리즘의 오버헤드라고 한다.COBS 알고리즘은 최악의 경우 오버헤드를 엄격히 제한하여 최소 1바이트와 최대 ⌈n/254⌉ 바이트(254의 1바이트, 반올림)로 제한한다.따라서 인코딩된 바이트 시퀀스를 전송하는 시간은 매우 예측가능하며, 이는 지터가 문제가 될 수 있는 실시간 애플리케이션에 COBS를 유용하게 만든다.알고리즘은 계산적으로 저렴하며 그 평균 오버헤드가 다른 모호하지 않은 프레임 알고리즘에 비해 낮다.[1][2]
그러나 COBS는 최대 254바이트의 룩어헤드를 필요로 한다.첫 번째 바이트를 전송하기 전에, 다음 254바이트에서 첫 번째 0바이트(있는 경우)의 위치를 알 필요가 있다.
패킷 프레임 및 스터핑
패킷화된 데이터가 어떤 시리얼 매체를 통해 전송될 때, 패킷 경계를 구분하기 위해 일부 프로토콜이 필요하다.이것은 프레임 마커, 특별한 비트 시퀀스 또는 패킷 사이의 경계가 어디에 있는지 나타내는 문자 값을 사용하여 이루어진다.데이터 스터핑은 송신 전 패킷 데이터를 변환해 프레임 마커의 발생을 모두 제거하는 과정으로, 수신자가 마커를 감지했을 때 마커가 패킷 사이의 경계를 나타내는 것을 확인할 수 있다.
COBS는 [0,255] 범위의 임의의 바이트 문자열을 [1,255] 범위의 바이트로 변환한다.데이터에서 0바이트를 모두 제거했으므로 이제 0바이트를 사용하여 변환된 데이터의 끝을 모호하게 표시할 수 있다.이는 변환된 데이터에 0바이트를 추가함으로써 이루어지며, 따라서 COBS 인코딩된 데이터(페이로드)로 구성된 패킷을 형성하여 패킷의 끝을 모호하게 표시한다.
(다른 바이트 값은 패킷 구분 기호로 예약할 수 있지만 0을 사용하면 설명이 간단해진다.)
COBS 인코딩 프로세스를 설명하는 두 가지 동등한 방법이 있다.
- 접두사 블록 설명
- 일부 바이트를 인코딩하려면 먼저 0바이트를 추가한 다음 0바이트가 아닌 254바이트 또는 0–253바이트 다음에 0바이트가 되는 그룹으로 구분하십시오.추가된 0바이트 때문에, 이것은 항상 가능하다.
- 후행 0바이트(있는 경우)를 삭제하고 0이 아닌 바이트 수(+1)를 미리 입력하여 각 그룹을 인코딩하십시오.따라서 인코딩된 각 그룹은 255 바이트의 바이트를 미리 입력하여 254 비 0 바이트를 255 바이트로 인코딩하는 것을 제외하고는 원본과 동일한 크기가 된다.
- 특별한 예외로서 패킷이 0이 아닌 254바이트의 그룹으로 끝나는 경우에는 후행 0바이트를 추가할 필요가 없다.이것은 어떤 상황에서 1바이트를 저장한다.
- 링크된 목록 설명
- 먼저, 패킷의 시작 부분에 0바이트를 삽입하고, 254 비 0바이트의 실행 후에 0바이트를 삽입한다.이 인코딩은 분명히 되돌릴 수 있다.패킷의 끝에 0바이트를 삽입할 필요는 없다. 만약 그것이 정확히 254바이트가 아닌 것으로 끝난다면 말이다.
- 둘째, 각 0 바이트를 다음 0 바이트 또는 패킷의 끝에 대한 오프셋으로 교체한다.첫 번째 단계에서 추가된 추가 0 때문에 각 오프셋은 최대 255가 보장된다.
인코딩 예제
이러한 예는 다양한 데이터 시퀀스가 COBS 알고리즘에 의해 어떻게 암호화되는지를 보여준다.이 예에서 모든 바이트는 16진수 값으로 표현되며, 인코딩된 데이터는 텍스트 형식과 함께 표시되어 다음과 같은 다양한 특징을 나타낸다.
- 굵은 글꼴은 인코딩으로 변경되지 않은 데이터 바이트를 나타낸다.0이 아닌 모든 데이터 바이트는 변경되지 않은 상태로 유지된다.
- 녹색은 인코딩에 의해 변경된 0 데이터 바이트를 나타낸다.인코딩 중에 모든 0 데이터 바이트는 다음 0 바이트(즉, 1 + 0이 아닌 바이트 수)의 오프셋으로 대체된다.해석해야 하는 것은 사실상 다음 패킷 바이트에 대한 포인터다: 주소 지정된 바이트가 0이 아닌 경우 해석을 요구하는 다음 바이트를 가리키는 것은 다음 그룹 헤더 바이트 0 데이터 바이트다. 주소된 바이트가 0이면 패킷의 끝이다.
- 빨간색은 다음 그룹에 대한 오프셋을 포함하는 그룹 헤더 바이트이기도 하지만 데이터 바이트에는 해당하지 않는 오버헤드 바이트다.이것들은 두 곳에 나타난다: 인코딩된 모든 패킷의 시작과 254 비 0 바이트의 모든 그룹 뒤에.
- 데이터 수신기에 대한 패키지 종료를 나타내기 위해 모든 패킷의 끝에 파란색 0 바이트가 나타난다.이 패킷 구분 기호 바이트는 COBS의 적절한 일부가 아니며 인코딩된 출력에 추가된 추가 프레임 바이트다.
| 예 | 인코딩되지 않은 데이터(헥스) | COBS(헥스)로 인코딩 |
|---|---|---|
| 1 | 00 | 01 01 00 |
| 2 | 00 00 | 01 01 01 00 |
| 3 | 11 22 00 33 | 03 11 22 02 33 00 |
| 4 | 11 22 33 44 | 05 11 22 33 44 00 |
| 5 | 11 00 00 00 | 02 11 01 01 01 00 |
| 6 | 01 02 03 ...FD FE | FF 01 02 03 ...FD FE 00 |
| 7 | 00 01 02 ...FC FD FE | 01 FF 01 02 ...FC FD FE 00 |
| 8 | 01 02 03 ...FD FE FF | FF 01 02 03 ...FD FE 02 FF 00 |
| 9 | 02 03 04 ...FE FF 00 | FF 02 03 04 ...FE FF 01 01 00 |
| 10 | 03 04 05 ...FF 00 01 | FE 03 04 05 ...FF 02 01 00 |
아래는 위의 표의 사례 3을 사용하여 각 수정된 데이터 바이트가 어떻게 위치하는지, 그리고 데이터 바이트 또는 프레임 바이트의 끝 부분으로 어떻게 식별되는지 보여주는 도표 입니다.
[OHB] : 오버헤드 바이트(프레임 시작) 3+ ---------------------------------------------- : 첫 번째 0 기호 2+------------------------------------------------------------------------ : 다음 0 기호 [EOP] : 패킷 끝 기호 0을 가리키는 0 데이터 바이트다.0 1 2 3 4 5 : 바이트 위치 03 11 22 02 33 00 : COBS 데이터 프레임 11 22 00 33 : 추출된 데이터 OHB = 오버헤드 바이트(다음 0 기호까지 포인트) EOP = 패킷 끝
사례 7에서 10은 255개 이상의 패킷 길이에 대해 인코딩되는 데이터에 따라 오버헤드가 어떻게 달라지는지를 보여준다.
실행
다음 코드는 C 프로그래밍 언어로 COBS 인코더 및 디코더를 구현한다.
#include <stddef.h> #include <stdint.h> #include <assert.h> /** COBS에서 데이터를 버퍼로 인코딩 @param data 인코딩할 데이터를 입력하는 포인터 @param 길이 인코딩할 바이트 수 @param buffer 인코딩된 출력 버퍼에 대한 포인터 @return 인코딩 버퍼 길이(바이트) @참고 구분 기호 바이트를 출력하지 않음 */ size_t cbsEncode(경시하다 공허하게 하다 *자료, size_t 길이, uint8_t *완충하다) { 주장하다(자료 && 완충하다); uint8_t *인코딩하다 = 완충하다; // 인코딩된 바이트 포인터 uint8_t *코데프 = 인코딩하다++; // 출력 코드 포인터 uint8_t 부호를 붙이다 = 1; // 코드값 을 위해 (경시하다 uint8_t *바이트 = (경시하다 uint8_t *)자료; 길이--; ++바이트) { 만일 (*바이트) // 0이 아닌 바이트, 작성 *인코딩하다++ = *바이트, ++부호를 붙이다; 만일 (!*바이트 부호를 붙이다 == 0xff) // 입력이 0 또는 블록 완료, 다시 시작 { *코데프 = 부호를 붙이다, 부호를 붙이다 = 1, 코데프 = 인코딩하다; 만일 (!*바이트 길이) ++인코딩하다; } } *코데프 = 부호를 붙이다; // 최종 코드 값 작성 돌아오다 (size_t)(인코딩하다 - 완충하다); } /** COBS 버퍼에서 데이터 디코딩 @param buffer 인코딩된 입력 바이트에 대한 포인터 @param 길이 디코딩할 바이트 수 @param data 디코딩된 출력 데이터에 대한 포인터 @return 성공적으로 디코딩된 바이트 수 @note 구분 기호 바이트가 발견되면 디코딩 중지 */ size_t cobsDecode(경시하다 uint8_t *완충하다, size_t 길이, 공허하게 하다 *자료) { 주장하다(완충하다 && 자료); 경시하다 uint8_t *바이트 = 완충하다; // 인코딩된 입력 바이트 포인터 uint8_t *암호를 해독하다 = (uint8_t *)자료; // 디코딩된 출력 바이트 포인터 을 위해 (uint8_t 부호를 붙이다 = 0xff, 막다 = 0; 바이트 < 완충하다 + 길이; --막다) { 만일 (막다) // 블록 바이트 디코딩 *암호를 해독하다++ = *바이트++; 다른 { 만일 (부호를 붙이다 != 0xff) // 인코딩 0, 작성 *암호를 해독하다++ = 0; 막다 = 부호를 붙이다 = *바이트++; // 다음 블록 길이 만일 (!부호를 붙이다) // 구분 기호 코드가 발견됨 부숴뜨리다; } } 돌아오다 (size_t)(암호를 해독하다 - (uint8_t *)자료); } 참고 항목
참조
- ^ Cheshire, Stuart; Baker, Mary (April 1999). "Consistent Overhead Byte Stuffing" (PDF). IEEE/ACM Transactions on Networking. 7 (2): 159–172. CiteSeerX 10.1.1.108.3143. doi:10.1109/90.769765. Retrieved November 30, 2015.
- ^ Cheshire, Stuart; Baker, Mary (17 November 1997). Consistent Overhead Byte Stuffing (PDF). ACM SIGCOMM '97. Cannes. Retrieved November 23, 2010.
