Helix is a label-based multicast forwarding system that (i) is general and can be used to implement customized multicast trees in any network topology, (ii) does not introduce any forwarding loops or redundant traffic, (iii) is scalable as it requires only a small state to be maintained at a fraction of the routers, and (iv) does not impose significant processing overheads on routers.
Helix splits the information about a multicast tree into two parts: constant-size label attached to packets and small state at some routers in the tree. This information-split architecture leads to substantial improvements in the data plane performance, as well as allows Helix to strike a balance between the label overhead and the memory and processing overheads imposed on routers to handle labels and forward traffic on the multicast tree.
Helix has two components: (i) Controller that calculates a label to be attached to packets of the session and small state at some routers, and (ii) Packet processing algorithm that runs in the data plane at individual routers.
Helix encodes the tree link IDs using filters, which allow the multicast tree to include links not on the shortest paths. Although these probabilistic filters produce relatively small labels and can be processed efficiently in the data plane, they may result in false positives (i.e., incorrect forwarding). To ensure correctness, the data plane needs to store these false positives and check them before making decisions. This impacts the scalability of the data plane as it needs to maintain more state.
The key idea to reduce the maintained state is to encode both tree and false-positive link IDs inside the label. Thus, the data plane does not need to maintain all false positives. We design an algorithm based on recursive encoding. Our recursive encoding algorithm works in rounds to successively reduce the final state to be maintained at routers. Each round encodes a given set of link IDs based on the outputs of previous rounds, and produces a fixed-size label and an intermediate state. The proposed algorithm carefully controls the inputs of each round to guarantee the correctness of the final outputs.
We have developed a proof-of-concept implementation of Helix in a testbed that uses NetFPGA. Our experiments show that Helix can easily provide line-rate throughput and it consumes a negligible amount of the hardware resources.
The figure shows that the numbers of transmitted and received packets per second are the same (i.e., no packet losses). We also plot the achieved throughput in the same figure. The figure shows that our algorithm can sustain the required throughput for all packet sizes.
Helix can easily provide line-rate throughput and it consumes a negligible amount of the hardware resources. Helix also reduces the state size significantly compared to other systems.
Can be used in any network topology to implement customized multicast trees that satisfy the ISP traffic engineering objectives
Helix is theoretically proved to be correct. Helix guarantees to duplicate packets on and only on links that belong to the multicast tree
Network administrator is able to make the right balance between label overhead and state maintained at routers by configuring two meaningful parameters
Helix is reproducible. The instructions, requirements and code to run Helix in hardware and simulations are available here.
We believe that…
We designed Helix
