Research On Name Lookup In Named Data Networking

Named Data Networking (NDN), recently proposed as a clean-slate future Internetarchitecture, embraces Internet’s functionality transition: from host-centriccommunication to content-centric dissemination. Different from IP-based networkrouters, NDN routers forward packets by content names, which have variable andunbounded lengths. Further, an NDN name routing table could be several orders ofmagnitude larger than the current IP routing table. This kind of complex nameconstitution plus the huge-sized name routing table makes wire-speed NDN namelookup an extremely challenging task. Practical name lookup mechanism design andimplementation, therefore, requires substantial innovation and re-engineering. Toconquer these challenges, this dissertation proposes a number of innovative methodsand mechanisms. The main contributions of this dissertation are as below:1. A GPU-based name lookup engine is desgined and implemented. The innovativename lookup algorithm, stream-based pipeline solution and name interweavedmechanishm ensure practical per-packet latency (less than0.1ms) while achievingwire-speed name lookup. Extensive experiments demonstrate the feasibility ofimplementing wire-speed name lookup with large-scale name tables at low cost, usingtoday’s commodity GPU devices. Extensive experimental results show that GPU-basedname lookup engine can achieve lookup throughput of63.52million searches persecond on large-scale name tables containing10million of name entries with a strictconstraint of no more than the telecommunication level0.1ms per-packet lookuplatency.2. A two-stage Bloom filter-based name lookup approach named NameFilter isproposed and applied to name lookup engine. In the first stage, name prefixes aremapped into String-oriented Bloom filters based on their lengths, and the longest prefixof a name is determined by inquiring the Bloom filters at this stage. The second stagedivides name prefixes into groups according to their associated next-hop port(s), witheach group stored into a Bloom filter. The destination port(s) corresponding to thatparticular longest prefix will be reported by searching the second stage Bloom filters.Evaluation results on a name prefix table with10M entries show that the optimized name lookup engine achieves lookup throughput of37million searches per second atlow memory cost of234.27MB only. The results also demonstrate that NameFilter canachieve3million per second incremental updates and exhibit good scalability tolarge-scale prefix tables.3. A scalable name component encoding mechanism is proposed to enhace thescalability and practicality of name lookup engine. With the assistance of localcomponent encoding mechanism and state transition array, name component encodingmechanism makes GPU-based name lookup engine be a practical solution by effectivelybalancing the various name lookup performances including memory space, lookupspeed, lookup latency, forwarding table building time and update rate.