Segment Routing and the Journey of a Packet

Simple Routing Topologuy

On the Internet, packets of data travel around the network using a technology called Internet Protocol (IP). Network routers use protocols like OSPF to guide traffic to its destination by the shortest and simplest path. Routers find the destination’s address in the packet header. We call this process “destination-based packet forwarding”.

Destination-based packet forwarding always tries to use the shortest path. In Figure 1, all routers use the OSPF protocol. A data packet going from network N1 to network N2 uses the path {R1, R4} because it is the shortest.

Let’s imagine that an Internet Service Provider (ISP) has a customer who wants higher link bandwidth than 1 Mbps. Then the router will send traffic via {R1, R2, R4} or {R1, R3, R4}, paths, even though they are not the shortest. These are “non-optimal” paths. Guiding traffic this way is called “traffic engineering”. Traffic engineering can be complex in this kind of network.

One important way to send packets to their destination using non-optimal paths is called “source routing.” In source routing, a data packet has its own complete information about the network path it should take.

Segment Routing.

Segment Routing (SR) is how a packet knows which path to take. SR uses computer code for this. An SR path, from beginning to end, is broken into smaller parts called segments. These segments use IGP protocols like ISIS or OSPF. The path that a packet should follow is coded as a list of segments in that packet. These segments show sub-paths that combine to form the desired path. The path state doesn’t have to be stored in a router. Instead, the packet’s path is kept in the packet header. So the network doesn’t have to store SR-encoded flows.

There are two types of segments: nodal segments and adjacency segments. A nodal segment is the shortest path to a node. It needs support from an IGP to find that shortest path. To advertise its nodal segment ID to other nodes, the segment needs ISIS or OSPF. The path is either a single-hop or a multi-hop. For example, a node N advertises its nodal SID X using an ISIS LSP in the network. For all its 1-hop neighbours, nodal SID X shows a single-hop path to N. For other nodes, X shows a multi-hop path to N.

An adjacency segment shows when two nodes are linked. The local node advertises the adjacency using the IGP. The remote node is at the other end of the adjacency. An adjacency segment is a one-hop path. Adjacency segment ID also identifies a local service. As in draft [1], section 3.2, a node can give a local service segment ID to identify a specific service at its site. For example, we might want to give some firewalling or monitoring service for a set of flows when a packet reaches a certain node.

How to define and create segments in a network topology

Look at Figure 2. Every node with a nodal segment ID advertises it through an IGP. The IGP protocols which do this are ISIS and OSPF. These segment IDs get flooded in the network. That’s why every node “knows” about that nodal segment ID. But it’s different with the adjacency segment identifier (SID). If a node has an adjacency SID for a link between itself and its neighbour, that gets advertised in the entire network with IGP (say ISIS) LSP flooding. That adjacent SID tells us if there is a local service at its site. But that only applies to the advertising node. No network nodes have to bother with that adjacency SID. So no nodes store any entry in their FIB for adjacency SID. Here are some examples:

Segment Routing Network

EXAMPLE OF SEGMENT ROUTING IN A SMALL TOPOLOGY:

In figure 2, the end-user wants to reach from node A to node Z with 10 mbps guaranteed bandwidth. The shortest path from A to Z is A-B-C-D-Z. But this path cannot give 10 Mbps link bandwidth. This is because the link between C to D and D to Z is only 1 Mbps. So the best path for the packet is A-B-C-G-H-Z.

To follow this path, the packet has to travel the first segment from A-B-C. C redirect the packet to adjacent node G. Then, the packet travels the second segment G-H-Z. To do this, two node segments and one adjacency segment are advertised. Node C and Z advertises its “nodal SID” in the entire network. Only one “adjacency SID” is advertised by node C for its interface linked to node G. At node C, we must steer the traffic to adjacent node G. We then take the traffic to C-G path. This path support high bandwidth. So node C has advertised the adjacency SID for the C to G path.

The picture below shows the FIB table of each node.

Segment Routing FIBs

Explanation of the FIB tables

Node A receives ISIS-LSP from C (C advertises its nodal SID as 20). Node A knows that C is not its 1-hop neighbour because of its ISIS protocol. So, Node A sees that an ingress data packet has its MPLS label set to 20. It knows this data packet wants to reach node C. So node A swaps the incoming level of 20 by the same label. It knows that a label value of 20 is the shortest path to node C. The IGP (which is ISIS here) tells node A that interface A-B is on the shortest path towards node C.

You can see this in the first row of the FIB table for node A. When node B receives that ISIS-LSP from node C, it knows through IGP that C is its 1-hop neighbour. Now Node B receives an ingress packet with label 20. (This is node segment ID of Node C.) Node B then “pops” that label because Node B is the last hop towards Node C. The outgoing label doesn’t matter in this case. The out interface has been set as B-C.

In figure 2, AS 99 realizes there is some kind of local service at node C. So it reroutes the traffic to node G. This adjacency SID is important only to that specific node. It is also only important for the specific link between C and G.

What if a customer wants to use the local service at node C for a packet headed to node Z? Then, the operator creates the path in the packet header as {20, 99, 30}. The operator then injects that packet in the SR network at node A. Node A uses the nodal SID 20, and sends the packet to B. B “pops” that label 20 and sends the packet with label stack {99, 30} to node C. Node C knows that a local service (ID 99) has been requested at its site. So Node C then performs that requested service. Maybe it’s a firewall or encryption service. Then node C “pops” the label 99 from the packet header. It forwards the packet with only one label {30} to node G. To do this, it uses out interface C-G. Node G checks in its FIB table. It sees that it should swap with label 30 and then forward that packet to node H. It uses interface G-H for this. Node H “pops” label 30 and delivers the data packet to node Z, using interface H-Z. You can see this process figure 4 below.

Segment Routing Stack

SEGMENT ROUTING OFFERS THE FOLLOWING ADVANTAGES:

  1. Segment routing makes the network simper by running only one IGP like ISIS or OSPF. This way, the network needs fewer protocols.
  2. Since segment routing needs fewer protocols, there is less need for troubleshooting.
  3. Segment routing avoids directed LDP sessions between the core routers.
  4. Segment routing avoids millions of TE LSPs in the network. This is because SR does the traffic engineering. So no separate TE LSPs need to be advertised in the network.
  5. Segment routing supports SDN. This is because network control is programmable here. For destination based routing, data traffic always follows the shortest or optimal path through the network. But segment routing lets data traffic travel through alternate paths. This is possible because the packet header has the code for the entire network path as a sequence of segments. The operator has a lot of flexibility to control the network path for the data traffic.
  6. Segment routing uses the efficient MPLS data plane. We already have that today. it uses MPLS Pop and Swap, which are simplified operations. That means existing MPLS devices don’t need replacement. Software upgrade is enough. This protects current investments.
  7. Segment routing allows virtualization. The network does not contain any application state because the path state is in the packet. The path state is encoded as a list of segments. The network does not hold any state for the SR-encoded flows. So a single physical network can have a segment of any shape, based on application need. The shape can change from application to application.
  8. Segment routing avoid millions of labels in its FIB, compared to the LDP database.

Here are two cases that explain this:

The example is a fully-mesh topology with 'n' nodes in it.

Case1: Every node is a segment routing enabled router. Every node advertises its nodal SID in the network. So, every node, in the worst case, will have (n-1) number of entries in their respective FIB. This corresponds to (n-1) “nodal SIDs”. Since it is a fully-mesh topology, every node is connected to (n-1) nodes via links. So every node can hold (n-1) more entries in their the FIB that corresponds to its (n-1) “adjacency SIDs/ local service IDs”. This is a “worst case scenario.” A node really may not have any adjacency SID configured or have less than (n-1).

So, FIB size of any such router = (n-1) + (n-1) = Order of (n)

Case2: In the same fully-mesh topology, every node is an LDP router. That means every node holds entries in its FIB table that correspond to every adjacency information in the network.

So, FIB size of any such router = n(n-1)/2 = Order of (n2)

We can have the following local services at an end node in a segment:

  1. Access restrictions: A detecting node forwards a sender traffic packet only if it comes from a set on known senders.
  2. Protocol Specific access: Only data traffic packets of certain types like TCP are allowed, but not UDP packets.
  3. Restricted TE for different customers: If a host is not a privileged customer, they can’t have the TE services.
  4. Security services: Network security services like encryption and authentication between two nodes.

The future of Segment Routing

Segment routing in the real world is an extension to ISIS/ OSPF protocols. But, these are IGP protocols that can operate within an Autonomous System (AS). So, Segment Routing along with ISIS/ OSPF only works in an area within an AS. But, what about inter-AS communication” How can we steer data traffic from a source end in one AS to the destination end in another AS? The answer is PCE (Path Computation Element) plus BGP-LS (Link State) and Segment Routing extensions for BGP. By combining PCE and Segment routing, an ISP can provide future inter domain routing.

Authors: Sougato Adhikari, Kingshuk Mandal

Additional Resources:

IxNetwork

Routing and Switching solutions

References:

https://tools.ietf.org/html/draft-filsfils-spring-segment-routing-use-cases-01

limit
3