Skip to main content
SpringerLink
Log in

Routing Sets and Hint-Based Routing

  • Conference paper
  • First Online:
Advances in Information and Communication (FICC 2019)

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 70))

Included in the following conference series:

  • 1514 Accesses

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

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Abley, J., Savola, P., Neville-Neil, G.: Deprecation of type 0 routing headers in ipv6. RFC 5095, Internet Engineering Task Force (2007)

    Google Scholar 

  2. 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

    Article  MathSciNet  MATH  Google Scholar 

  3. 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

    Article  Google Scholar 

  4. Biondi, A., Ebalard, P.: Ipv6 routing header security. In: CanSecWest Security Conference (2007)

    Google Scholar 

  5. 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

  6. 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

  7. Filsfils, C., Previdi, S., Ginsberg, L., Decraene, B., Litkowski, S., Shakir, R.: Segment routing architecture. RFC 8402, Internet Engineering Task Force (2018)

    Google Scholar 

  8. 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)

    Google Scholar 

  9. 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

  10. 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

    Article  Google Scholar 

  11. 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)

    Google Scholar 

  12. 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

  13. 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

    Article  Google Scholar 

  14. 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

    Article  Google Scholar 

  15. Meyer, D., Zhang, L., Fall, K.: Report from the IAB workshop on routing and addressing. RFC 4984, Internet Engineering Task Force (2007)

    Google Scholar 

  16. 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

  17. 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)

    Google Scholar 

  18. 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

  19. 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

  20. Westphal, C., Pei, G.: Scalable routing via greedy embedding. In: INFOCOM 2009, IEEE, pp. 2826–2830. IEEE (2009)

    Google Scholar 

  21. 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

    Google Scholar 

Download references

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

  1. George Mason University, Fairfax, VA, 22030, USA

    Ivan Avramovic

Authors
  1. Ivan Avramovic
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ivan Avramovic .

Editor information

Editors and Affiliations

  1. Faculty of Science and Engineering, Saga University, Saga, Japan

    Kohei Arai

  2. The Science and Information (SAI) Organization, Bradford, UK

    Rahul Bhatia

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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

Publish with us

Policies and ethics

Search

Navigation