L2-xconnect SFC Rendering Options

[rastislavs]

The l2xconn SFC renderer currently works with the following limitations:

1. It always renders a chain into a single data path, even if more replicas of some pods matching
   selectors in the chain are present.
2. The rendered data path may not be optimal in some cases, e.g. the traffic needs to traverse between more nodes than it would be necessary.

The current logic is implemented by the getPreferredSFPod and getPreferredSFInterface methods.
To address the issues described above, these would need to be changed to a more sophisticated rendering algorithm, that would:

• render multiple paths (multiple instances) for the same service chain, if more instances of some service functions are available,
• if possible, select shortest path for service chains, where the "path" between two service functions is
  assumed to be much longer inter-node than intra-node. Things like link utilization and error-rate on the link between two nodes can be taken into consideration as well.

Since L2 traffic cannot be effectively load-balanced between multiple interfaces on VPP, we have to assume that in order to have multiple instances of the same service chain, we need multiple traffic inputs - pods or external interfaces where the chain starts. Also, once traffic enters a (service function) pod, it always has to be forwarded to exactly one next service function pod / external interface.

Examples - Unidirectional Chains

Let's use graph theory to discuss some particular rendering options for a L2 SFC. For the pictures below, let's assume that the SFC has been defined as a unidirectional chain between 4 service functions:
A -> B -> C -> D
A and/or D (input and output service functions) can be external interfaces or pods, B and Care pods. Each one of them can have multiple instances. Graph nodes represent the service functions, graph edges represent interconnections between them:

3-2-2-3 replicas - 3 available paths:

This means we have 3 instances of the service chain, with is determined by the number of input nodes. Note the node B1: it can have multiple inputs, but only one output. Also note C2: it can only have one output, therefore the output node D3 is disconnected. The picture shows one possible rendering, other renderings of this case are possible. The actual rendering should depend on weights applied to graph edges and shorter paths should be preferred.

1-2-2-3 replicas - 1 available path:

If we have only one traffic source, we can only have one instance of the chain. The disconnected nodes act as a backup in case that one of the active nodes would crash.

3-2-2-1 replicas - 3 available paths:

In this case we can have multiple paths, that would all end in a single output node.

3-2-1-3 replicas - 3 available paths:

We again have multiple paths, that concentrate in the node C1 and end in a single output node.

Examples - Bidirectional Chains

The situation is little bit more complex if the service chains are bi-directional. In that case,
we could use the same priciples as for uni-directional traffic, just apply it twice - in both directions.
However, we need to take special attention to not render different paths one way and the way back, since most of the networking protocols do not like assymetric traffic routing. Simpler would be to use a different rule: only one input and only one output for each graph node. Let's take a look at a few rendering options:

3-2-2-3 replicas - 2 available paths:

This means we have 2 instances of the service chain, with is determined by the minimum of the instances per service function (B and C have 2 instances).

3-2-1-3 replicas - 1 available path:

There is only 1 instance of the service chain, with is determined by the minimum of the instances
per service function (C has only 1 instance). Again, this rendering is only one of the available options, should be selected by the weights applied to graph edges and the shortest path should be preferred.

[milanlenco]

Interesting graph-theory problem you have got here, looking forward to the algorithm :)

It will be important to ensure that every node calculates the same paths on every update. With weights based solely on placement of pods across nodes this should be relatively easy, but metrics like link-utilization or error-rate could be tricky. First, this information is not propagated across nodes, secondly they could change quite often, causing frequent changes in routing. I would maybe leave these dynamic metrics for later, or define something "more static", e.g. node utilization that would be given by the number of pods deployed on it (although I guess that K8s tries to ensure that distribution of pods across nodes is even, so it might not be that helpful) , etc.

[rastislavs]

@milanlenco ACK, weights based solely on placement of pods across nodes should be good enough

[AdelBouridah]

@milanlenco and @rastislavszabo We can begin by algorithms that avoid network metrics informations like for exemple a Round-Robin that allocate pods to data paths only in a circulaire manner. Then, enhanced algorithm would be proposed and compared to the simple Round-Robin, ...etc.

[AdelBouridah]

@rastislavszabo and @milanlenco as SFC problem is divided into two sub problem: 1. CNFs (Pods) Placements Then 2. Traffic steering over them (creating data paths). lets the first one decided by k8s as always done. In the second sub-problem and for pods selection (the issue to be tacked in the code actually by getPreferredSFPod and getPreferredSFInterface): lets pick the pod of the less used node (as indicate by @milanlenco ) or simply pick nodes in a Round-Robin manner (to avoid using node utilization metric).

[AdelBouridah]

@rastislavszabo When we take into account several SFCs the graphe theory will change a little about the number of paths. In fact, SFCs may share the use of some Service Functions e.g. SFC1 may use A,B, C, D and SFC2 may use A, B, D so the numbers of possible paths for each SFC will depend on all the required SFCs.