Research On Architecture And Key Techniques Of Parallel Router Design

Continuing growth in traffic, the size of Internet as well as the Internet applications puts forward great challenge to backbone router design. First, the capacity and port density of the switch can hardly keep up with the growth of traffic resulting from increasing link speeds and the number of hosts on the Internet. Second, IP-lookup performance in core routers can hardly keep up with the growth of FIB size resulting from widely used multi-homed technology and increased Internet size. Third, with the development of Internet applications such as IPv6, QoS, multicast, security, etc. packet process power can hardly fix the contradiction between increasing packet rate and increasing complexity of packet processing. Recently, parallel router architectures introducing parallelism inside routers appears to be an efficient way to scale Internet routers to very high capacities and forwarding rates.Parallel design brings load balancing and packet reordering problems inside routers. Load balancing is prerequisite to achieving delay and throughput guarantees in parallel router architectures. Unfortunately, load balancing may incur out-of-order packets which trigger unnecessary retransmissions and TCP timeouts, thus decreasing TCP throughout and increasing packet delay. How to deal with this contradiction is a crucial problem in parallel router design. The existing scheduling mechanisms maintaining packet ordering either require complex, centralized schedulers, or rely on simple distributed scheduling algorithms that lack throughput guarantees. Aiming at the problems above, by thorough analyzing queuing model and distribution properties of cells in parallel router architectures we propose a load-balancing technique and a cooperative scheduling mechanism which are all distributed and can enforce packet ordering and load-balancing, reduce complexity of scheduling and communication overhead as well as provide delay and throughput guarantees.A router logically consists of two consecutive stages namely forwarding stage and switching stage. These two processing stages are implemented in different hardware components and performed in order, which hinders parallelism development inside routers. We originally propose a distinct packet processing mechanism concurrently exploiting parallelism of switching and forwarding operations. This packet processing mechanism partitions FIB lookup function and distributes FIB lookups to switch fabrics so as to distributedly perform packet forwarding in the process of packet switching, which provide theoretical, technical and practical value for solving FIB limits confronting modern routers.We make comprehensive research on crucial problems of load balancing, packet reordering, delay and throughput guarantees, communication complexity and FIB limits for parallel router design. The major contributions of this dissertation are as follows. 1. To make a better tradeoff between load balancing and packet ordering we propose a fine-grained frame dispatching algorithm called UFFS-k (Uniform Fine-grain Frame Spreading (UFFS-k, where k is the aggregate factor) based on flow mapping which is distributed and can operate independently in each input. UFFS-k dispatches cells based on local VOQs' state information, moreover, without any communication overhead it guarantees packet ordering and achieves 100% throughput with 0(1) time complexity. As the simulation results demonstrate, UFFS-k reduces packet delay considerably and has better capacity of load balancing.2. Due to communication and scheduling complexity, heterogeneous parallel router architectures have difficulties in maintaining packet ordering and implementing with low-cost hardware components. We propose an IOQ (In-order Queuing) PPS architecture based on CIOQ switch planes. By using a simple collaborative scheduling mechanism between round-robin demultiplexing at inputs and synchronous switching at central switch planes, our scheme guarantees a way for cells of a flow to be read in order from different switch planes, thus avoiding packet reordering at output ports. IOQ PPS achieves packet-level load balancing over multiple independent switch planes and eliminates the speedup requirement for the internal switch planes. As the experiment results demonstrate, IOQ PPS offers improved delay performance compared to existing PPS designs.3. To address FIB limits confronting parallel router design, we propose a parallel packet process mechanism performing packet forwarding in switch fabrics—FIS (forwarding in switching) which partitions IP lookup function and distributes IP lookups to multiple lower speed and heterogeneous nodes called FSN (Forwarding and Switching Node) which performs forwarding and switching independently. By partitioning FIB table and by constructing mapping relationship between FIB table and FSNs, IP-lookup complexity is reduced considerably. Further, the distributed storing of FIB table among FSNs eliminates memory bottleneck of parallel lookup mechanism, thus improving the FIB scalability of modern routers. We make comprehensive research on the key technologies of FIS mechanism including the partition of routing table, the logical mapping from subtries to FSNs, as well as the FIS-oriented IP-lookup mechanism. Our work underlies the design and implementation of FIS hardware prototype system.4. We propose an IPv6 binary lookup algorithm based on prefix scope called PSB-BS (prefix scope based binary search) for putting FIS in practice. The efficiency of PSB-BS algorithm can be attributed to two key aspects. First, the subtrie format based on prefix scope eliminates the presentation of path information which contributes to a reduction in the memory space occupied by the search structure. Second, the binary search scheme based on prefix scope compresses the search path, thus reducing the number of memory access. We map IPv6 forwarding table to FSNs in FIS by constructing binary search trie of PSB-BS algorithm. The experiment results demonstrate the average search time of FSN varies stably with the increased number of prefixes, which reflect better scalability of PSB-BS algorithm.In summary, our work presents solutions to several key problems of parallel router design, and has academic and practical value for improving the performance, size and scalability of modern routers and advancing the practicability of parallel technologies for routers.