Efficient Data Storage and Name Look-Up in Named Data Networking Using Connected Dominating Set and Patricia Trie

Abstract: Named data networking (NDN) has emerged as a new architecture derived from the strength and limitations of current Internet architecture to cope with today’s Internet usage. Several NDN features bring potential advantages in routing method over any Content Delivery Network (CDN). But the name based forwarding poses unique challenges to scale huge number of complex name structures and unbounded name spaces in limited amount of memory. Additionally, high look-up time is required while searching a data from a massive amount of database and huge number of communications are occurred for the real-life applications which require intensive updates (e.g., archival data, Internet banking). In this paper, we propose changes in current NDN architecture and forwarding method with an aim to develop a lightweight solution to the said problems. Instead of storing the database in all routers according to link state routing, we store them in selected nodes, called special nodes, using a compact data structure like binary Patricia trie. We exploit the concept of connected dominating set (CDS) to select such special nodes and develop modified algorithms for update dissemination and interest/data forwarding accordingly. Finally, the performance of the proposed scheme is analyzed through extensive experiments in real-world graphs with real dataset in terms of update, storage, and look-up time overheads. Then the same are compared with the existing routing method used in NDN. The results show a reduction of 70–80% in both the storage and update overheads and more than 60% reduction in FIB look-up time in the proposed method.