Consistent overhead byte stuffing

Consistent overhead byte stuffing (COBS) – algorytm kodowania ciągu liczb (zwykle bajtów) w postaci ciągu, w którym nie występuje jeden wyróżniony symbol (zwykle zero). Jego pomysłodawcą i autorem jest Stuart David Cheshire(inne języki). Podstawową zaletą algorytmu jest znikomy narzut zwiększający rozmiar zakodowanych danych. Głównym zastosowaniem algorytmu jest wspomaganie pakietyzacji strumienia danych w transmisji szeregowej.

Historia

Prezentacja algorytmu miała miejsce na konferencji SIGCOMM poświęconej zagadnieniom komunikacyjnym jak również został on zgłoszony jako propozycja do wykorzystania w protokole PPP. Algorytm kodowania był tematem pracy doktorskiej, którą Stuart David Cheshire(inne języki) przedłożył na Uniwersytecie Stanforda w 1998. Rok później artykuł z opisem algorytmu został opublikowany czasopiśmie organizacji IEEE. W 2020 zaadaptowano wykorzystanie algorytmu dla półbajtów. W 2022 roku zauważono, że w sprzyjających okolicznościach działanie algorytmu można przeprowadzić równolegle na fragmentach danych co znacznie skraca czas przetwarzania zwłaszcza w realizacji sprzętowej.

Motywacja

W transmisji danych z wykorzystaniem łącza szeregowego w warstwie fizycznej warstwa łącza danych tworzy ramki, które kapsułkują dane z wyższej warstwy. Każda ramka zawiera znaczniki, które jednoznacznie pozwalają określić jej początek i koniec. W systemach opartych na transmisji danych w postaci ciągów tekstowych znacznik startu to jeden ze znaków, który nie jest używany w kodowaniu danych. W przypadku, gdy łącze danych ma przesyłać dowolne dane binarne, może się zdarzyć, że wśród nich pojawią się takie, które będą przyjmowały wartości tożsame z używanymi do rozpoznawania początku i końca ramki. Aby uniknąć takich kolizji stosowane są metody pozwalające na ich eliminację ze strumienia danych. Za przykład można wskazać SLIP lub PPP. Polegają one głównie na podmianie każdego bajtu mającego specjalne znaczenie przez odpowiednie zastąpienie sekwencją dwóch bajtów. Jeśli nastąpi próba wysłania danych składających się z samych „zarezerwowanych” wartości, to w takim przypadku długość danych do przesłania w warstwie fizycznej ulegnie podwojeniu.

W proponowanym algorytmie narzut związany z eliminacją wartości zarezerwowanych nie przekracza 1 bajta na każde 254 bajty danych.

Opis

W wersji podstawowej algorytm skupia się na sposobie zapisu ciągu liczb z pełnego zakresu liczb ośmiobitowych od 0 do 255 na odpowiadający mu ciąg liczb z zakresu od 1 do 255. Jeśli zachodzi konieczność eliminacji wartości innej niż zero, to można wszystkie bajty wyniku zamienić wykonując na nich funkcję XOR z wartością do usunięcia.

Kody

Do reprezentacji wartości oryginalnego ciągu COBS używa następujących kodów:

Kod (hex)ZnaczenieOpis
0100bajt o wartości zero
02 XXXX 00dowolny niezerowy bajt danych + bajt o wartości zero
03 XX XXXX XX 00dowolne dwa niezerowe bajty danych + bajt o wartości zero
nn XX … XXXX … XX 00(nn-1) niezerowych bajtów danych + bajt o wartości zero
FE XX … XXXX … XX 00253 niezerowe bajty danych + bajt o wartości zero
FF XX … XXXX … XX254 niezerowe bajty danych, po których nie ma bajtu o wartości zero

W powyższym zestawieniu kodów nie istnieje wartość 00, która jest niedozwolona.

Kodowanie

Ciąg wejściowy o dowolnej długości dzielony jest na fragmenty nie dłuższe niż 254 bajty, w których bajt o wartości zero występuje dokładnie na końcu. Jest on zastępowany w ciągu wyjściowym odpowiadającym mu kodem z domyślnym zerem. Jeśli taki podciąg nie istnieje to w jego miejsce jest wstawiany wyjątek zaczynający się kodem 255, który pozwala na kodowanie długich bezzerowych ciągów danych. Wyjątek stanowi również ostatni fragment nie dłuższy niż 253 bajty, który domyślnie zakłada istnienie wirtualnego zera tuż za ostatnim bajtem pakietu. Po zakodowaniu w wyjściowym strumieniu danych nie ma wartości zero, które można jednoznacznie wykorzystać do wskazania granic między pakietami.

Przykłady

Pusta kratka na końcu to wirtualne zero. Pogrubiona czcionka oznacza pierwszy bajt kodu. Wielokropek to ciąg niezerowych wartości.

Oryginalny przykład ze specyfikacji
dane 4500002C4C79000040064F37
kod 024501042C4C79010540064F37
Ciąg z sekwencją niezerowych bajtów od pozycji 9 do 264
pozycja 12345678…263264265266
dane 44696C6500007400…5461—
kod 0544696C65010274FF…035461
Ciąg z sekwencją 254 niezerowych bajtów na końcu
pozycja 1234567…258259260
dane F09F8D8600F09F…92A6—
kod 05F09F8D86FFF09F…92A6
Pusty pakiet
dane
kod 01
Bajt zero
dane 00
kod 0101

Własności

Obserwacje

Uwagi

  1. ↑ Literalnie Niesprzeczne nagłówkowe dopełnianie bajtowe.
  2. ↑ Na przykład w systemie Modbus jest to dwukropek.

Przypisy

  1. ↑ Stuart Cheshire, Mary Baker, Consistent Overhead Byte Stuffing, „ACM SIGCOMM '97”, Cannes 1997, DOI: 10.1145/263105.263168 (ang.).
    1. ↑ s. 1
    2. ↑ s. 3
    3. ↑ s. 7
    4. ↑ s. 2
    5. 1 2 3 4 5 6 s. 4
    6. ↑ s. 5
  2. ↑ J. Carlson, S. Cheshire, M. Baker, PPP Consistent Overhead Byte Stuffing (COBS) [online], Internet Draft, ietf.org, listopad 1997 [dostęp 2024-04-28] (ang.).
  3. ↑ Stuart David Cheshire, Consistent Overhead Byte Stuffing, marzec 1998, OCLC 82593294 [dostęp 2024-04-28] (ang.).
  4. ↑ Stuart Cheshire, Mary Baker, Consistent Overhead Byte Stuffing, „IEEE/ACM TRANSACTIONS ON NETWORKING”, 7 (2), IEEE, 1999, s. 159-172, DOI: 10.1109/90.769765 (ang.).
  5. ↑ Adewale Adetomi, Godwin Enemali, Tughrul Arslan, Enabling Dynamic Communication for Runtime Circuit Relocation, „IEEE Transactions on Very Large Scale Integration (VLSI) Systems”, 28 (1), 2020, s. 142-155, DOI: 10.1109/TVLSI.2019.2934927, Cytat: Adopting a similar technique to map the hex number set [0, F] to [1, F], we reserve the number zero to be used as the delimiter (ang.).
  6. ↑ Enrico Ronconi i inni, Multi-COBS: A Novel Algorithm for Byte Stuffing at High Throughput, „IEEE Access”, 2022, s. 78848-78859, DOI: 10.1109/ACCESS.2022.3194265 (ang.).
    1. 1 2 s. 78850 (3/12)
    2. ↑ s. 78855 (8/12)
  7. E.A. Jakubajtis, Lokalne sieci komputerowe, Warszawa: WNT, 1989, ISBN 83-204-1079-7.
    1. 1 2 s. 112
  8. Wojciech Mielczarek, Szeregowe interfejsy cyfrowe, Warszawa: Helion, 1993, ISBN 83-85701-23-0.
    1. ↑ s. 70-71, 81-82
    2. ↑ s. 71
  9. 1 2 Unexpected test result for test encoding of empty input #16, [w:] cobs.rs [online], github.com, 12 lipca 2022 [dostęp 2024-04-28] (ang.).
  10. Vladimir Oksman, Overview of different encapsulation technologies, IEEE, lipiec 2002 [dostęp 2024-04-28] (ang.).
    1. 1 2 slajdy 6 i 17
    2. 1 2 slajd 17
    3. ↑ slajd 6
  11. ↑ Keerat Singth, Implementing COBS ZPE in C#, „Proceedings of IRAJ International Conference”, Chennai, 26 października 2013, s. 6, ISBN 978-93-82702-34-4 [dostęp 2024-04-28] (ang.).
  12. ↑ Rolando Herrero, Fundamentals of IoT Communication Technologies, Springer, 2021, s. 50, ISBN 978-3-030-70080-5 (ang.).
  13. ↑ Mike Ash, The Complete Friday Q&A, t. III, Lulu.com, 2017, s. 264 (ang.).
  14. ↑ Pravin Bhagwat, Chatschik Bisdikian, Ibrahim Korpeoglu, Mahmoud Naghshineh, Statish K. Tripathi, Cordless Dialup Networking for Palmtop Computers [online], luty 1999, s. 8, IBM RC 21404(96651).
  15. ↑ Mun Wai Yuen, Ethernet encapsulation and emulation for DVB/MPEG multimedia wireless systems: base station and subscriber interface VHDL designs, wrzesień 2005, s. 87, ISBN 978-1-369-31445-8 (ang.).
  16. ↑ Jaime S. Cardoso, Bandwidth-efficient byte stuffing, „IEEE International Conference on Communications”, 2007, s. 1.
  17. consistent, [w:] Robert Szymula, PODRĘCZNY SŁOWNIK (ANGIELSKO-POLSKO-ROSYJSKI) TERMINÓW INFORMATYCZNYCH, Roman Hajczuk (red. nauk.), Białystok: Uniwersytet w Białymstoku, 2002, s. 57, ISBN 83-89031-29-9 [dostęp 2024-04-28].
  18. overhead, [w:] Informatyczny Słownik Angielsko-Polski [online], ComputerWorld [dostęp 2024-04-28] [zarchiwizowane 2024-04-28] (pol.).
  19. byte stuffing, [w:] Informatyczny Słownik Angielsko-Polski [online], ComputerWorld [dostęp 2024-04-28] [zarchiwizowane 2024-04-28] (pol.).

Linki zewnętrzne