NLRI storage aggregation of BGP-4 routing information

摘要

Border Gateway Protocol Version 4 (BGP-4) is the primary inter-domain routing protocol in the Internet. In BGP-4, every route described by a group of attributes can correspond to several Network Layer Reachability Information (NLRI) items. If dispersed routes are aggregated in this approach, a lot of benefits such as saving memory, optimizing routing management and reducing network payload are available. To increase the speed of the aggregation, we endeavor to reduce the comparisons of BGP-4's path attributes with complex formats. This paper starts from the features of BGP-4's two basic attributes, AS_PATH and NEXT_HOP. Next, we present a series of hash algorithms step by step and evaluate them with real data. Then we get the optimal one and analyze its complexities. At last, we introduce the full aggregation rules.