Fractional-N SVRF Forwarding Algorithm for Low Port-Density Packet Forwarding Engines

摘要

High-performance multicast-enabled switches and routers are being constantly developed, which use a polynomial-time group membership query algorithm within the Packet Forwarding Engines (PFEs) to determine whether or not a packet is forwarded through a unique or multiple egress ports. Among these, Bloom filter (BF) and Scalar-pair Vectors Routing and Forwarding (SVRF) are being considered as two representations of the membership query algorithms. However, both approaches suffer from some fatal weaknesses such as space and time inefficiencies, especially for a carrier-grade PFE with high port-density feature. In order to solve these imperfections of SVRF, we propose an improved Fractional-N Scalar-matrix and Vectors Routing and Forwarding (Fractional-N SVRF) scheme based on re-examining the idea of the original SVRF. The Fractional-N SVRF preprocesses a scalar-matrix by dividing an n-element group into N-columns (sub-blocks), thus element’ keys belonging to distinct sub-blocks and sub-scalars are allowed to reuse relatively smaller identical prime keys. Based on Fractional-N SVRF, membership queries can be partitioned to leverage task parallelism, therefore better performance is achieved in terms of memory consumption and computational complexity.