Research On Compression And Lookup Of Virtual Routing Tables

Network virtualization can multiplex the physical substrate network and build multiple virtual networks on it with relatively low cost.These virtual networks can provide various network services for users with different needs,and can also provide a realistic environment to evaluate network innovative designs,so as to promote the innovation of the Internet.Virtual routers are the key equipment of virtual networks,and the research on the forwarding technique of virtual routers is significant for improving the performance of the virtual networks.This dissertation focuses on the research of the separate forwarding mechanism and the shared forwarding mechanism of the virtual routers,and proposes the FIB compression and lookup algorithms corresponding to the two forwarding mechanisms.Our main contributions are as follows:(1)With regard to the linearly increasing storage overhead of the FIBs using the separate forwarding mechanism,we propose a fast FIB compression algorithm-the US algorithm.By changing the trie structure of a FIB,the number of prefixes in the compressed FIB is only 65% of that of the FIB before compression.The US algorithm not only guarantees the FIB update speed in the worst case,but also can be applied to most existing FIB compression and lookup algorithms.(2)Considering that the on-chip memory capacity is limited in the virtual routers using the separate forwarding mechanism,we propose to apply the Minimal Perfect Hash Tables(MPHTs)to FIB lookup and name it the MPHL algorithm.MPHL achieves the information theoretic optimum on-chip memory usage.We propose a novel fast incremental update algorithm to circumvent the limitation of MPHT's no support for insertions,and the average update complexity is O(1).The average lookup complexity of both IPv4 and IPv6 FIBs is O(1).(3)Considering that the existing FIB lookup algorithms using the shared forwarding mechanism are either too slow or supporting a limited number of virtual FIBs,we propose a novel FIB lookup algorithm based on Bloom filters.Its lookup speed is close to the offchip memory access speed and is regardless of the number of virtual FIBs.Based on this,we propose a novel FIB compression algorithm named the A&E algorithm,which reduces the on-chip memory usage by around 1/3.(4)We design and implement the MAVIN virtual network platform to provide high performance virtual networks.We propose a novel MAC address coding scheme to isolate different virtual networks in layer-2.Comparing to tunnel-based virtualization scheme,MAC address coding scheme brings no additional overhead of packets encapsulation and decapsulation during packets forwarding.We carry out extensive experiments to evaluate the forwarding performance and scalability of MAVIN.