An Efficient Pending Interest Table content search in NDN through Stable Bloom Filter

Abstract

Named Data Networking (NDN) has gained importance in today’s era due to a paradigm shift in the Internet usage pattern which revolves around the content rather than the respective host addresses. Modern users are more concerned about what the data is irrespective of from where the data is coming. Three important data structures used by NDN routers for packet forwarding are Content Store (CS), Pending Interest Table (PIT) and Forwarding Information Base (FIB). Search time of PIT is quite high since its size grows with addition of new content names and the Interest packets which are not served by CS are searched in millions of existing entries in the PIT. Look up time can be improved if, instead of checking all the available entries, initial scanning is done to determine whether the required content name exists in the PIT or not. In this work, a Stable Bloom Filter (SBF) based PIT called S-PIT is proposed to minimize the PIT search time by identifying the existence of query content through SBF. The experiments performed on synthetic and real datasets show that S-PIT outperforms existing data structures which include Hash Table and Name Component Encoding (NCE) in terms of memory consumption, content insertion time, average search time and false positive rate respectively.