Reducing the overhead of SRv6
In this project, we want to investigate how to synthesise SRv6 configuration whilst minimising the overhead.
What is Segment Routing?
In destination routing, e.g. IGP, routes are computed according to the shortest routes. Often, however, network operators will want to be able to change some routes dynamically, e.g. to circumvent a failure. Changing the weights of the network’s links is impractical and cannot implement any combination of source-destination routes.
In contrast, source routing is a paradigm in which the source the packet decides of the route that the packet should take to the destination. It is very flexible as any source-destination path may be implemented (for example, implementing disjoint backup paths [3]). Unfortunately it is very impractical to implement (imagine having to specify the whole route for every destination)
Segment routing places itself between both paradigms. It is based on destination routing, but the source of the packet may specify a few points it wishes the packet to go through, so-called segments. In a nutshell, the routing will by default follow the shortest path unless told otherwise by the segments.
Sounds marvellous, but what can we improve?
Segment Routing over IPv6 (SRv6) [1,2] is an implementation of segment routing over IPv6 where segments are encoded as IPv6 addresses. The problem that SRv6 introduces is that by adding more segments, in order to fulfil the operator’s specifications, we increase the header size and therefore the communication overhead.
Recent works have proposed algorithms to minimise the total number of segments [4]. However, we wish to show that this is only one side of the story and that we can further reduce the overhead by considering the placement of the segments on the path and the weight of each flow.
Milestones
- First, you should investigate different SRv6 implementations and show what overhead could be gained by synthesising better segments.
- Then, you should come up with an algorithm that solves the minimisation or approximates it.
- Finally you should implement and evaluate this algorithm.
Requirements
- Be familiar with internet routing (at least basic networking course).
- Interest in designing algorithms.
- Some knowledge in mathematical optimisation, in particular linear programming.
That sparked your interest?
This work will be co-supervised by Ricardo Santos from Técnico Lisboa. If you like the idea of trying to improve network configuration synthesis, just send us an email, we will happily talk about it.
References
- IETF. RFC 8986: “Segment Routing over IPv6 Network Programming”. Feburary 2021.
- Cisco. “SRv6 Introduction.”. Online Presentation 2021.
- F. Aubry, S. Vissicchio, O.Bonaventure and Y. Deville “Robustly Disjoint Paths with Segment Routing”, CoNEXT 2018.
- L. Bocheng et. al. “AutoSRv6: Configuration Synthesis for Segment Routing Over IPv6”, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 43, NO. 2, FEBRUARY 2025
