More Web Proxy on the site http://driver.im/

research-article

Open access

A type-theoretic model on NDN-TLV encoding

Authors:

Alexander Afanasyev,

Lixia ZhangAuthors Info & Claims

ICN '22: Proceedings of the 9th ACM Conference on Information-Centric Networking

Pages 91 - 102

https://doi.org/10.1145/3517212.3558093

Published: 06 September 2022 Publication History

Abstract

In Named-Data Networking (NDN), all packets are encoded in the Type-Length-Value (TLV) format. TLV encoding and decoding are implemented in every NDN library, and used by all applications and forwarders. Therefore, formal analysis of TLV encoding can assist NDN software development in the simplification of the code base, analysis of the performance, and improvement of robustness.

In this paper, we want to bring attention to the subtleties of TLV encoding. As an initial result, we develop a type-theoretical model of TLV encodable types, and give an algorithm to automatically derive encoding and decoding functions. We formally prove that the derived encoding and decoding functions are inverse to each other. To evaluate the practicality of automatically derived algorithms, we implement the proposed algorithms in C++ templates and evaluate them in three aspects: performance, memory usage, and code complexity. Our results show that our C++ library is competitive in these three aspects. Though our implementation is not fully automated, we show that it is possible to have a fully automated library in future that correctly produce the encoding and decoding functions. We also discussed the limitations of our model and problems worth attention. We hope our work can offer a starting point of further research on TLV, especially formal analysis and automated implementation.

References

[1]

The Go Authors. 2022. The Go Programming Language Specification. https://go.dev/ref/spec#Struct_types

[2]

Julian Bangert and Nickolai Zeldovich. 2014. Nail: A Practical Tool for Parsing and Generating Data Formats. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14). USENIX Association, Broomfield, CO, 615--628. https://www.usenix.org/conference/osdi14/technical-sessions/presentation/bangert

[3]

Sung Hyuk Byun, Jongseok Lee, Dong Myung Sul, and Namseok Ko. 2020. Multi-Worker NFD: An NFD-Compatible High-Speed NDN Forwarder. In Proceedings of the 7th ACM Conference on Information-Centric Networking (ICN '20). Association for Computing Machinery, New York, NY, USA, 166--168.

Digital Library

[4]

Dave Crocker and Paul Overell. 2008. Augmented BNF for Syntax Specifications: ABNF. RFC 5234.

[5]

Benjamin Delaware, Sorawit Suriyakarn, Clément Pit-Claudel, Qianchuan Ye, and Adam Chlipala. 2019. Narcissus: Correct-by-Construction Derivation of Decoders and Encoders from Binary Formats. Proc. ACM Program. Lang. 3, ICFP, Article 82 (July 2019), 29 pages.

Digital Library

[6]

CVE Details. 2021. Openssl : List of security vulnerabilities. https://www.cvedetails.com/vulnerability-list/vendor_id-217/Openssl.html

[7]

Chavoosh Ghasemi, Hamed Yousefi, Kang G. Shin, and Beichuan Zhang. 2019. On the Granularity of Trie-Based Data Structures for Name Lookups and Updates. IEEE/ACM Transactions on Networking 27, 2 (2019), 777--789.

Digital Library

[8]

Raymond Hettinger. 2022. Descriptor HowTo Guide. https://docs.python.org/3/howto/descriptor.html

[9]

International Telecommunication Union. 2002. Information Technology --- ASN.1 Encoding Rules --- Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER), and Distinguished Encoding Rules (DER). ITU-T Recommendation X.690.

[10]

Jana Iyengar and Martin Thomson. 2021. QUIC: A UDP-Based Multiplexed and Secure Transport. RFC 9000.

Digital Library

[11]

Van Jacobson, Diana K. Smetters, James D. Thornton, Michael F. Plass, Nicholas H. Briggs, and Rebecca L. Braynard. 2009. Networking Named Content. In Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies (CoNEXT '09).

[12]

Svilen Kanev, Juan Pablo Darago, Kim Hazelwood, Parthasarathy Ranganathan, Tipp Moseley, Gu-Yeon Wei, and David Brooks. 2015. Profiling a Warehouse-Scale Computer. SIGARCH Comput. Archit. News 43, 3S (June 2015), 158--169.

Digital Library

[13]

Stephen McQuistin, Vivian Band, Dejice Jacob, and Colin Perkins. 2020. Parsing Protocol Standards to Parse Standard Protocols. In Proceedings of the Applied Networking Research Workshop (ANRW '20). Association for Computing Machinery, New York, NY, USA, 25--31.

Digital Library

[14]

Eric Newberry, Xinyu Ma, and Lixia Zhang. 2021. YaNFD: Yet Another Named Data Networking Forwarding Daemon. In Proceedings of the 8th ACM Conference on Information-Centric Networking (ICN '21). Association for Computing Machinery, New York, NY, USA, 30--41.

Digital Library

[15]

Tahina Ramananandro, Antoine Delignat-Lavaud, Cédric Fournet, Nikhil Swamy, Tej Chajed, Nadim Kobeissi, and Jonathan Protzenko. 2019. EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats. In USENIX Security. USENIX. https://www.microsoft.com/en-us/research/publication/everparse/

[16]

Yakov Rekhter, Susan Hares, and Tony Li. 2006. A Border Gateway Protocol 4 (BGP-4). RFC 4271.

[17]

Eric Rescorla. 2018. The Transport Layer Security (TLS) Protocol Version 1.3. RFC 8446.

Digital Library

[18]

Junxiao Shi, Davide Pesavento, and Lotfi Benmohamed. 2020. NDN-DPDK: NDN Forwarding at 100 Gbps on Commodity Hardware. In Proceedings of the 7th ACM Conference on Information-Centric Networking (ICN '20). Association for Computing Machinery, New York, NY, USA, 30--40.

Digital Library

[19]

Erez Shinan. 2022. Welcome to Lark's documentation! https://lark-parser.readthedocs.io/en/latest/

[20]

Won So, Ashok Narayanan, and David Oran. 2013. Named data networking on a router: Fast and DoS-resistant forwarding with hash tables. In Architectures for Networking and Communications Systems. 215--225.

[21]

Christopher Strachey. 2000. Fundamental Concepts in Programming Languages. Higher-Order and Symbolic Computation 13, 1 (2000), 11--49.

Digital Library

[22]

Nikhil Swamy, Juan Chen, Cédric Fournet, Pierre-Yves Strub, Karthikeyan Bhargavan, and Jean Yang. 2011. Secure Distributed Programming with Value-Dependent Types. SIGPLAN Not. 46, 9 (sep 2011), 266--278.

Digital Library

[23]

NDN Project Team. 2021. ndn-cxx: NDN C++ library with eXperimental eXtensions. https://github.com/named-data/ndn-cxx/

[24]

NDN Project Team. 2021. NDN Packet Format Specification version 0.3. http://named-data.net/doc/NDN-packet-spec/current/index.html

[25]

NDN Project Team. 2021. NDN Protocol Design Principles. https://named-data.net/project/ndn-design-principles/

[26]

NDN Project Team. 2021. python-ndn documentation. https://python-ndn.readthedocs.io/en/latest/

[27]

Jeff Thompson. 2021. PyNDN: A Named Data Networking client library with TLV wire format support in native Python. https://github.com/named-data/PyNDN2

[28]

Haowei Yuan, Patrick Crowley, and Tian Song. 2017. Enhancing Scalable Name-Based Forwarding. In 2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS). 60--69.

Digital Library

Cited By

Akre PPacharaney U(2025)A Comprehensive Review of Mojo: A High-Performance Programming Language2025 6th International Conference on Mobile Computing and Sustainable Informatics (ICMCSI)10.1109/ICMCSI64620.2025.10883176(861-867)Online publication date: 7-Jan-2025
https://doi.org/10.1109/ICMCSI64620.2025.10883176
Bukhari SSharif KZhu L(2024)Standardized Blockchain Structure using TLV-Encoding for Large-scale Interoperability2024 6th International Conference on Blockchain Computing and Applications (BCCA)10.1109/BCCA62388.2024.10844490(279-284)Online publication date: 26-Nov-2024
https://doi.org/10.1109/BCCA62388.2024.10844490

Index Terms

A type-theoretic model on NDN-TLV encoding
1. Networks
  1. Network performance evaluation
    1. Network performance analysis
  2. Network protocols
    1. Presentation protocols
2. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Domain specific languages

Recommendations

A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew
SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data

In-memory data analytic systems that use vertical bit-parallel scan methods generally use encoding techniques. We observe that in such environments, there is an opportunity to turn skew in both the data and predicate distributions (usually a problem for ...
SPIHT Algorithm Combined with Huffman Encoding
IITSI '10: Proceedings of the 2010 Third International Symposium on Intelligent Information Technology and Security Informatics

SPIHT is computationally very fast and among the best image compression algorithms known today. According to statistic analysis of the output binary stream of SPIHT encoding, propose a simple and effective method combined with Huffman encode for further ...
NDN-RTC: Real-Time Videoconferencing over Named Data Networking
ACM-ICN '15: Proceedings of the 2nd ACM Conference on Information-Centric Networking

NDN-RTC is a videoconferencing library that employs Named Data Networking (NDN), a proposed future Internet architecture. It was designed to provide a platform for experimental research in low-latency, real-time multimedia communication over NDN. It ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICN '22: Proceedings of the 9th ACM Conference on Information-Centric Networking

September 2022

203 pages

ISBN:9781450392570

DOI:10.1145/3517212

Program Chairs:
Henning Schulzrinne
Columbia University
,
Matthias Wählisch
Freie Universität Berlin, Germany
,
Lixia Zhang
UCLA

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 September 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

US National Science Foundation

Conference

ICN '22

Sponsor:

SIGCOMM

ICN '22: 9th ACM Conference on Information-Centric Networking

September 19 - 21, 2022

Osaka, Japan

Acceptance Rates

Overall Acceptance Rate 133 of 482 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
495
Total Downloads

Downloads (Last 12 months)207
Downloads (Last 6 weeks)25

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Akre PPacharaney U(2025)A Comprehensive Review of Mojo: A High-Performance Programming Language2025 6th International Conference on Mobile Computing and Sustainable Informatics (ICMCSI)10.1109/ICMCSI64620.2025.10883176(861-867)Online publication date: 7-Jan-2025
https://doi.org/10.1109/ICMCSI64620.2025.10883176
Bukhari SSharif KZhu L(2024)Standardized Blockchain Structure using TLV-Encoding for Large-scale Interoperability2024 6th International Conference on Blockchain Computing and Applications (BCCA)10.1109/BCCA62388.2024.10844490(279-284)Online publication date: 26-Nov-2024
https://doi.org/10.1109/BCCA62388.2024.10844490

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten