دانلود رایگان مقاله فشرده سازی جداول ارسال IP با زمان محدود بروز رسانی

Abstract

With the fast development of the Internet, the size of Forwarding Information Base (FIB) maintained at backbone routers is experiencing an exponential growth, making the storage support and lookup process of FIBs a severe challenge. One effective way to address the challenge is FIB compression, and various solutions have been proposed in the literature. The main shortcoming of FIB compression is the overhead of updating the compressed FIB when routing update messages arrive. Only when the update time of FIB compression algorithms is small bounded can the probability of packet loss incurred by FIB compression operations during update be completely avoided. However, no prior FIB compression algorithm can achieve small bounded worst case update time, and hence a mature solution with complete avoidance of packet loss is still yet to be identified. To address this issue, we propose the Unite and Split (US) compression algorithm to enable fast update with controlled worst case update time. Further, we use the US algorithm to improve the performance of a number of classic software and hardware lookup algorithms. Simulation results show that the average update speed of the US algorithm is a little faster than that of the binary trie without any compression, while prior compression algorithms inevitably seriously degrade the update performance. After applying the US algorithm, the evaluated lookup algorithms exhibit significantly smaller on-chip memory consumption with little additional update overhead.

7. Conclusion

With the rapid growth of FIB size in backbone routers, FIB compression becomes a hot topic in recent years, and various FIB compression algorithms have been proposed. The update performance will inevitably be degraded if a FIB is compressed. Only when the worst case of update time is small bounded, the risk of packet loss during updates can ultimately be avoided. Towards this goal, we propose the Unite and Split (US) compression algorithm in this paper to achieve fast update with small bounded worst case (i.e., at most three nodes need to be changed per update). Further, we use the US algorithm to improve the performance of several classic software and hardware lookup algorithms. Simulation results on real-world FIBs show that the compression ratio of US is about 65% with fast compression time (only about 28.5 ms), and the update speed of US is fast. In addition, the on-chip memory usage of several classic lookup algorithms is significantly reduced after applying US. To enable others to replicate the simulations, we released the source code of our US algorithm and related data set at Github [45].