Consistent overhead byte stuffing

Consistent overhead byte stuffing[a] (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[1] jak również został on zgłoszony jako propozycja do wykorzystania w protokole PPP[2]. Algorytm kodowania był tematem pracy doktorskiej, którą Stuart David Cheshire(inne języki) przedłożył na Uniwersytecie Stanforda w 1998[3]. Rok później artykuł z opisem algorytmu został opublikowany czasopiśmie organizacji IEEE[4]. W 2020 zaadaptowano wykorzystanie algorytmu dla półbajtów[5]. 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[6].

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[7.1]. Każda ramka zawiera znaczniki, które jednoznacznie pozwalają określić jej początek i koniec[7.1][8.1]. 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[b][8.2]. 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[1.1]. Polegają one głównie na podmianie każdego bajtu mającego specjalne znaczenie przez odpowiednie zastąpienie sekwencją dwóch bajtów[1.2]. 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[1.3].

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

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[1.5].

Kody

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

Kod (hex) Znaczenie Opis
01 00 bajt o wartości zero
02 XX XX 00 dowolny niezerowy bajt danych + bajt o wartości zero
03 XX XX XX XX 00 dowolne dwa niezerowe bajty danych + bajt o wartości zero
nn XX … XX XX … XX 00 (nn-1) niezerowych bajtów danych + bajt o wartości zero
FE XX … XX XX … XX 00 253 niezerowe bajty danych + bajt o wartości zero
FF XX … XX XX … XX 254 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[1.5].

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[1.5]. 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[1.5]. Po zakodowaniu w wyjściowym strumieniu danych nie ma wartości zero, które można jednoznacznie wykorzystać do wskazania granic między pakietami[1.5].

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[1.6]
dane 45 00 00 2C 4C 79 00 00 40 06 4F 37
kod 02 45 01 04 2C 4C 79 01 05 40 06 4F 37
Ciąg z sekwencją niezerowych bajtów od pozycji 9 do 264[6.1]
pozycja 1 2 3 4 5 6 7 8 … 263 264 265 266
dane 44 69 6C 65 00 00 74 00 … 54 61 —
kod 05 44 69 6C 65 01 02 74 FF … 03 54 61
Ciąg z sekwencją 254 niezerowych bajtów na końcu[6.1]
pozycja 1 2 3 4 5 6 7 … 258 259 260
dane F0 9F 8D 86 00 F0 9F … 92 A6 —
kod 05 F0 9F 8D 86 FF F0 9F … 92 A6
Pusty pakiet[9]
dane
kod 01
Bajt zero
dane 00
kod 01 01

Własności

Obserwacje

  • Strumień danych zakodowanych algorytmem COBS dzielony jest na pakiety w miejscu napotkania wartości specjalnej 0x00. Zachowanie na okoliczność występowania sekwencji zer w takim ciągu nie jest zdefiniowane. Jednym z rozwiązań jest przyjęcie, że oznacza ona brak pakietu[9].
  • Ciąg zerowych bajtów może być więc wykorzystany jako wypełnienie jeżeli brakuje danych do transmisji[10.3].
  • Protokół MS/TP, używany jako warstwa łącza danych w transmisji po RS-485 w protokole BACnet, stosuje algorytm COBS do eliminacji wartości specjalnej 0x55 z bloku danych i sumy kontrolnej. Sekwencja bajtów 0x55 0xFF oznacza w nim początek nowej ramki[12].
  • Algorytm COBS może być dobrym wyborem w przypadku implementacji pakietyzacji przy połączeniach z wykorzystaniem protokołu TCP[13].
  • Algorytm nie jest powszechnie stosowany w praktyce[10.2]. Jednym z powodów może być brak oficjalnego wsparcia w ramach standardu PPP[14].
  • Algorytm operuje na buforach danych, wobec czego nie może być stosowany w przypadku gdy oczekiwane jest natychmiastowe generowanie danych wyjściowych w przetwarzaniu potokowym[15].
  • W przypadku obsługi pakietów o niewielkich rozmiarach, stały jednobajtowy narzut może być odbierany jako znaczny[16]. Dla pakietów jednobajtowych narzut stanowi 100%, a dla czterobajtowych 25% oryginalnej wiadomości[6.2].

Uwagi

  1. ↑ Literalnie Niesprzeczne[17] nagłówkowe[18] dopełnianie bajtowe[19].
  2. ↑ Na przykład w systemie Modbus jest to dwukropek[8.2].

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. ↑ a b c d e f 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. ↑ a b 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. ↑ a b s. 112
  8. ↑ Wojciech Mielczarek, Szeregowe interfejsy cyfrowe, Warszawa: Helion, 1993, ISBN 83-85701-23-0.
    1. ↑ s. 70-71, 81-82
    2. ↑ a b s. 71
  9. ↑ a b 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. ↑ a b slajdy 6 i 17
    2. ↑ a b 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

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.