Path-Aware Network with Residue Number System : Intrinsic Path Verification and High-Performance Routing

• Everson Scherrer Borges IFES / UFES
• Magnos Martinello UFES
• Cristina Klippel Dominicini IFES
• Moises R. N. Ribeiro UFES

DOI: https://doi.org/10.5753/sbrc_estendido.2026.19736

Resumo

The Internet’s end-to-end design keeps routers simple by delegating complexity to end hosts, but provides little or no path verification. As a result, many available paths remain unused, their quality unknown, and risks such as traffic deviation or forwarding errors may arise. Effective path awareness requires three essential properties: (i) Verifiability ensuring packets traverse the intended path; (ii) Controllability enabling explicit path selection; and (iii) Visibility providing path information to support routing decisions. Existing approaches to path verification impose significant computational overhead and cannot be efficiently deployed on programmable switches, relying on mechanisms such as origin tracing, chained MACs, or nested cryptographic structures that are not natively integrated into the routing process. This work introduces a path-aware network architecture that combines source routing with the Residue Number System (RNS). A routeID encodes the entire path and is decoded at each hop via modular operations. Beyond routing, the routeID enables intrinsic path verification: it serves as a key for Proof-of-Transit (PoT) lookups — extending the IETF RFC draft via Mersenne-based Shamir Secret Sharing — and, in a second tableless design, drives a chain of hash operations forming a path signature, a property unattainable in existing routing systems.

Referências

Anderson, T., Birman, K., Broberg, R., Caesar, M., Comer, D., Cotton, C., Freedman, M. J., Haeberlen, A., Ives, Z. G., Krishnamurthy, A., Lehr, W., Loo, B. T., Mazières, D., Nicolosi, A., Smith, J. M., Stoica, I., van Renesse, R., Walfish, M., Weatherspoon, H., and Yoo, C. S. (2014). A brief overview of the nebula future internet architecture. SIGCOMM Comput. Commun. Rev., 44(3):81–86.

Barrera, D., Chuat, L., Perrig, A., Reischuk, R. M., and Szalachowski, P. (2017). The scion internet architecture. Commun. ACM, 60(6):56–65.

Borges, E., Rodriguez, F., Guimarães, R. S., Martinello, M., Dominicini, C. K., Ribeiro, M. R. N., Marin, E., and Rothenberg, C. (2025). Crc4ever: Cyclic redundancy check for enhanced verification and efficient routing. In Proceedings of the ACM SIGCOMM 2025 Posters and Demos, ACM SIGCOMM Posters and Demos ’25, page 178–180, New York, NY, USA. Association for Computing Machinery.

Borges, E. S., Bonella, V. B., Dos Santos, A. J., Menegueti, G. T., Dominicini, C. K., and Martinello, M. (2023). In-situ proof-of-transit for path-aware programmable networks. In 2023 IEEE 9th International Conference on Network Softwarization (NetSoft), pages 170–177. IEEE.

Borges, E. S., da Cunha Pontes, E., Mate, C., Loui, F., Martinello, M., and Ribeiro, M. R. (2022). Freerouter in a nutshell: A”protocoland”routing platform for open and portable carrier-class testbeds. In Workshop de Testbeds, pages 36–46. SBC.

Borges, E. S. et al. (2024a). Pint-box: Path-aware networking in a tofino box. In 2024 IEEE NFV-SDN, pages 1–2.

Borges, E. S., Martinello, M., Bonella, V. B., dos Santos, A. J., Gomes, R. L., Dominicini, C. K., Guimarães, R. S., Menegueti, G. T., Barcellos, M., and Ruffini, M. (2024b). Pot-polka: Let the edge control the proof-of-transit in path-aware networks. IEEE Transactions on Network and Service Management.

Bu, K., Laird, A., Yang, Y., Cheng, L., Luo, J., Li, Y., and Ren, K. (2020). Unveiling the mystery of internet packet forwarding: A survey of network path validation. ACM Computing Surveys (CSUR), 53(5):1–34.

Dominicini, C. et al. (2020). Polka: Polynomial key-based architecture for source routing in network fabrics. In 2020 6th IEEE Conference on Network Softwarization (NetSoft), pages 326–334. IEEE.

Godfrey, P. B., Ganichev, I., Shenker, S., and Stoica, I. (2009). Pathlet routing. In Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication, SIGCOMM ’09, page 111–122, New York, NY, USA. Association for Computing Machinery.

Jia, Z., Zhang, Z., Rexford, J., Walker, D., and Wetherall, D. (2020). Adding path awareness to the internet architecture. IEEE Transactions on Network and Service Management, 17(3):2080–2093.

Krähenbühl, C., Wyss, M., Basin, D., Lenders, V., Perrig, A., and Strohmeier, M. (2023). FABRID: Flexible Attestation-Based routing for Inter-Domain networks. In 32nd USENIX Security Symposium (USENIX Security 23), pages 5755–5772, Anaheim, CA. USENIX Association.

Legner, M., Klenze, T., Wyss, M., Sprenger, C., and Perrig, A. (2020). Epic: every packet is checked in the data plane of a path-aware internet. In Proceedings of the 29th USENIX Conference on Security Symposium, SEC’20, USA. USENIX Association.

Martinello, M., Gomes, R. L., Borges, E. S., Layber, H. C., Bonella, V. B., Dominicini, C. K., Guimarães, R., Ribeiro, M., and Barcellos, M. (2024). Pathsec: Path-aware secure routing with native path verification and auditability. In 2024 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN), pages 1–7.

Naous, J., Walfish, M., Nicolosi, A., Mazieres, D., Miller, M., and Seehra, A. (2011). Verifying and enforcing network paths with icing. In Proceedings of the Seventh Conference on Emerging Networking Experiments and Technologies, pages 1–12.

Postel, J. (1981). Internet protocol. RFC 791, Internet Engineering Task Force (IETF).

Sunshine, C. A. (1977). Source routing in computer networks. ACM SIGCOMM Computer Communication Review, 7(1):29–33.

Szabo, N. S. and Tanaka, R. I. (1967). Residue Arithmetic and Its Applications to Computer Technology. McGraw-Hill, New York.

Trammell, B. (2022). Current open questions in path-aware networking. IRTF, RFC 9217.

Ventorim, D., Borges, E., Guimarães, R., Martinello, M., Ribeiro, M., Dominicini, C., Schwarz, M., Xavier, B., Bezerra, J., Kiran, M., and Newman, H. (2025). A path-aware routing for data intensive science: Proposal, deployment and evaluation in high-performance testbed. In Anais do XXX Workshop de Gerência e Operação de Redes e Serviços, pages 71–84, Porto Alegre, RS, Brasil. SBC.

Wu, B. et al. (2018). Enabling efficient source and path verification via probabilistic packet marking. In 2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS), pages 1–10.

Zhang, F. et al. (2014). Mechanized network origin and path authenticity proofs. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS ’14, page 346–357, New York, NY, USA. ACM.