Research On Scalable High-Performance Unicast/Multicast Forwarding Algorithm

The high-performance multicast packet forwarding engine(PFE)is an essential component of high-end Ethernet switches and core IP routers that uses a membership query algorithm to get the exit information of data flows.The widely used query algorithm is the Bloom filter(BF),however,the algorithm has been shown to have many inevitable defects,such as false positives and difficulty in removing members.Another error-free membership query algorithm is scalar-pair vectors routing and forwarding(SVRF).Although it solves some deficiencies of BF,it also has some limitations in forwarding efficiency and scalability.Therefore,it is of great significance to design a scalable unicast and multicast packet forwarding algorithm to adapt to high-performance PFE.First,in order to improve the time efficiency of SVRF and optimize its space efficiency,this paper proposes Fractional-N scalar-pair vectors routing and forwarding(Frac-N SVRF)algorithm.Frac-N SVRF randomly assigns all forwarding entries in the forwarding table to N sub-blocks,each sub-block is an independent SVRF,and performs lookup operations in parallel.Since the amount of entry egress information stored in each sub-block is reduced,the time taken to perform a lookup operation is also reduced.Simulation experiments demonstrate that the time efficiency of Frac-N SVRF is improved by 2-3 orders of magnitude and the space efficiency is improved by about 12%.Secondly,this paper considers the egress-diversity of multicast forwarding entries for the first time,and proposes a Prime Filter Array(PFA)scheme for the low egress-diversity characteristics of multicast entries in most cases.In the process of building and forwarding,it only activates the storage scalar of a specific port,which makes the memory space more compact and the query speed is faster.Simulation experiments show that when the average exit diversity of all entries in the forwarding table is within a reasonable threshold,the space efficiency is improved by about 50% and the time efficiency is improved by 1-2 orders of magnitude.Finally,this paper comprehensively considers all possible egress diversity situations of multicast forwarding entries,and proposes divaricate heterogeneous scalar-pair vectors routing and forwarding(DH-SVRF).DH-SVRF divides all entries in the forwarding table into two different units to perform forwarding operations by pre-calculating the threshold of egress-diversity,that is,forwarding entries with egress-diversity on both sides of the threshold adopt different forwarding strategies.The paper also discusses the selection of the optimal exit diversity threshold and gives its calculation method.Simulation experiments have demonstrated that the DH-SVRF scheme has improved the space efficiency by 50% and the time efficiency by 2-3 orders of magnitude,and is also more in line with the needs of practical applications,and is expected to be used in carrier-level PFE.