Network performance requirements are stringent and for good reason given the cost of failure. However, failures will happen and network architects spend a lot of time designing and implementing mechanisms to route desired traffic over a target set of failures (for example, up to k links fail simultaneously) and ensure the network is congestion free.
A typical way to achieve congestion-free routing is to preallocate capacity to tunnels, and then route traffic based on the allocated capacity. However, this often leads to conservative throughput because the routing path is not flexible enough.
We at the Internet Systems Lab at Purdue University have been working on designing a new routing mechanism called PCF, which sustains high throughput with low response overhead while providing tractable failure analysis (for up to k simultaneous link failures).
Logical sequence
The key idea behind PCF is to add flexibility in routing by introducing a notion called logical sequence.
As shown in Figure 1, a logical sequence from s to t consists of a series of nodes that are referred to as logical hops. And each consecutive hop is referred to as a logical segment.
To use a logical sequence, we need to allocate capacity to the sequence, as other congestion-free schemes need to allocate capacity to the physical tunnels. Allocating capacity on the sequence essentially ensures that each logical segment has enough capacity.
For each segment, PCF allows it to use its underlying physical tunnels, or other logical sequences connecting this segment. For example, in Figure 1, the segment s-v1 has two underlying physical tunnels and one logical sequence. If the sum of allocation to these three is x unit, then this segment can support x unit of traffic. If every segment from s to t can support x unit, then you can send x unit of traffic from s to t through this logical sequence.
When provided with physical tunnels and logical sequences, PCF models can compute the best allocation to maximize the throughput upon target failures; the performance gain will depend on the choice of logical sequences.
In testing our mechanism, we found that even a simple heuristic of using sequences of nodes in the shortest paths as logical sequences can bring significant performance benefits.
Implementing PCF is easy
When logical sequences do not recursively depend on each other, a local proportional routing mechanism can be used to implement the model. In such cases, we can always redistribute traffic on the active tunnels and logical sequences.
For example, in Figure 2, based on the allocation, 60% of traffic from s to t will be sent through logical sequence q1 and 40% of traffic from s to t will be sent through physical tunnel l1. And for the traffic sent through q1, it will be sent through logical segment s-u and u-t. And on each segment, the same redistribution rule will be applied, and the traffic will be carried by l2 and l3 eventually.
Another implementation approach is to use a centralized controller. On each failure, the centralized controller can solve a linear system to determine the new routing.
For the topology in Figure 2, the linear system will directly tell you that l2 and l3 will carry 60% of traffic from s to t, and l1 will carry the rest. This information can be installed in routers as weights of tunnels. It is usually very fast to solve a linear system, so it will not add much overhead to the online operation.
PCF models and other materials
PCF models are available on Github. You can define your topology, traffic demand, maximum number of link failures, physical tunnels and logical sequences, and our models will compute the maximum throughput that can be guaranteed along with the allocation to achieve such throughput. We’ve also developed and shared a tool here to automatically generate a set of logical sequences given topology and traffic demand.
If you’re interested in learning more about the PCF project, check out our website where you’ll also find a paper and video of a presentation we recently gave at SIGCOMM 2020. And if you have any questions please leave a comment below.
Chuan Jiang is a PhD student at Purdue University advised by Professor Sanjay Rao.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.