Abstract
The number of addresses on the Internet grows rapidly, and thus there may be a point at which the state requirements for routing become unwieldy. The intent of this research is twofold. First to draw on compact routing theory with landmark routing, thus reducing router state requirements, but also to make the the implementation of theoretical routing protocols with low state requirements more feasible in a policy constrained network. To that end, conceptual organizational scheme called routing sets is presented, which would allow flexibility in the choice of routing policy. Furthermore, an IPv6 extension and algorithm is presented for routing using hints, which moves some of the routing responsibility onto the end hosts, potentially freeing routers of a great deal of the routing state burden.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abley, J., Savola, P., Neville-Neil, G.: Deprecation of type 0 routing headers in ipv6. RFC 5095, Internet Engineering Task Force (2007)
Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., Thorup, M.: Compact name-independent routing with minimum stretch. ACM Trans. Algorithms 4(3), 37:1–37:12 (2008). https://doi.org/10.1145/1367064.1367077
Bellovin, S.M.: Security problems in the TCP/IP protocol suite. SIGCOMM Comput. Commun. Rev. 19(2), 32–48 (1989). https://doi.org/10.1145/378444.378449
Biondi, A., Ebalard, P.: Ipv6 routing header security. In: CanSecWest Security Conference (2007)
Clark, D.: The design philosophy of the DARPA internet protocols. In: Symposium Proceedings on Communications Architectures and Protocols, SIGCOMM ’88, pp. 106–114. ACM, New York, NY, USA (1988). https://doi.org/10.1145/52324.52336
Drazic, B., Liebeherr, J.: Improving routing scalability in networks with dynamic substrates. In: Teletraffic Congress (ITC), 2014 26th International, pp. 1–9 (2014). https://doi.org/10.1109/ITC.2014.6932940
Filsfils, C., Previdi, S., Ginsberg, L., Decraene, B., Litkowski, S., Shakir, R.: Segment routing architecture. RFC 8402, Internet Engineering Task Force (2018)
Gavoille, C., Glacet, C., Hanusse, N., Ilcinkas, D.: On the communication complexity of distributed name-independent routing schemes. In: Distributed Computing, pp. 418–432. Springer, Berlin (2013)
Godfrey, P.B., Ganichev, I., Shenker, S., Stoica, I.: Pathlet routing. In: Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication, SIGCOMM ’09, pp. 111–122. ACM, New York, NY, USA (2009). https://doi.org/10.1145/1592568.1592583
Gulyas, A., Retvari, G., Heszberger, Z., Agarwal, R.: On the scalability of routing with policies. IEEE/ACM Trans. Networking PP(99), 1–1 (2014). https://doi.org/10.1109/TNET.2014.2345839
Johnson, D., Hu, Y., Maltz, D.: The dynamic source routing protocol (DSR) for mobile ad hoc networks for IPv4. RFC 4728, Internet Engineering Task Force (2007)
Karpilovsky, E., Rexford, J.: Using forgetful routing to control BGP table size. In: Proceedings of the 2006 ACM CoNEXT Conference, CoNEXT ’06, pp. 2:1–2:12. ACM, New York, NY, USA (2006). https://doi.org/10.1145/1368436.1368439
Kos, J., Aiash, M., Loo, J., Trek, D.: U-sphere: strengthening scalable flat-name routing for decentralized networks. Comput. Netw. 89, 14–31 (2015). https://doi.org/10.1016/j.comnet.2015.07.006
Mao, Y., Wang, F., Qiu, L., Lam, S., Smith, J.: S4: small state and small stretch compact routing protocol for large static wireless networks. IEEE/ACM Trans. Netw. 18(3), 761–774 (2010). https://doi.org/10.1109/TNET.2010.2046645
Meyer, D., Zhang, L., Fall, K.: Report from the IAB workshop on routing and addressing. RFC 4984, Internet Engineering Task Force (2007)
Singla, A., Godfrey, P.B., Fall, K., Iannaccone, G., Ratnasamy, S.: Scalable routing on flat names. In: Proceedings of the 6th International Conference, Co-NEXT ’10, pp. 20:1–20:12. ACM, New York, NY, USA (2010). https://doi.org/10.1145/1921168.1921195
Strowes, S.D., Mooney, G., Perkins, C.: Compact routing on the internet as-graph. In: 2011 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 852–857. IEEE (2011)
Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’01, pp. 1–10. ACM, New York, NY, USA (2001). https://doi.org/10.1145/378580.378581
Tsuchiya, P.F.: The landmark hierarchy: a new hierarchy for routing in very large networks. In: Symposium Proceedings on Communications Architectures and Protocols, SIGCOMM ’88, pp. 35–42. ACM, New York, NY, USA (1988). https://doi.org/10.1145/52324.52329
Westphal, C., Pei, G.: Scalable routing via greedy embedding. In: INFOCOM 2009, IEEE, pp. 2826–2830. IEEE (2009)
Yanbin, S., Yu, Z., Hongli, Z., Binxing, F., Jiantao, S.: An ICN-oriented name-based routing scheme. In: Wang, H., Qi, H., Che, W., Qiu, Z., Kong, L., Han, Z., Lin, J., Lu, Z. (eds.) Intelligent Computation in Big Data Era. Communications in Computer and Information Science, vol. 503, pp. 101–108. Springer, Berlin (2015). https://doi.org/10.1007/978-3-662-46248-5_13
Acknowledgements
The author would like to thank Dr. Robert Simon, who was instrumental in encouraging him to push this research through to completion.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Avramovic, I. (2020). Routing Sets and Hint-Based Routing. In: Arai, K., Bhatia, R. (eds) Advances in Information and Communication. FICC 2019. Lecture Notes in Networks and Systems, vol 70. Springer, Cham. https://doi.org/10.1007/978-3-030-12385-7_43
Download citation
DOI: https://doi.org/10.1007/978-3-030-12385-7_43
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-12384-0
Online ISBN: 978-3-030-12385-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)