A MEMORY EFFICIENT ALGORITHM FOR IMPLEMENTING NDNFIB USING PATRICIA TRIE

Abstract

NAMED Data Networking (NDN) is emerging as the most promising among the proposed future internet architecture designs. The contents can he retrieved just by referring to their names in NDN. Packet names composed of strings separated by P are stored in the Forwarding Information Base (FIB) ofNDN. Operations like insertion, deletion, longest prefix matching and update are performed on FIB to route the packet to their desired destinations. Storing huge number of names of variable length in FIB has basically two major bottlenecks, large memory consumption and longer search time for longest prefix matching. So. an elfective algorithm is required. Encoding identical components in all the names with a unique integer can reduce memory as well as searching time for longest prefix matching. In this dissertation. we propose an online efficient algorithm for implementing NDN-FIB which is memory efficient as well as fast in longest prefix matching. We have used encoding technique and Patricia trie. We have done rigorous implementation and testing. In comparison to the other existing schemes our scheme's performance is better in terms of memory consumption. Our scheme is also extremely scalable as it can handle names with more than 14,000 components.