Research On Key Technologies Of Parallel Router Architecture

The rapid growth of Internet traffic sets a great demand on network capacity. Dense Wavelength Division Multiplexing (DWDM) is making fiber-optic links with very high bandwidth, which satisfies the underlying users' demand. Routers can not keep up with the growth of user traffic and link bandwidth at present, and thus become the bottleneck of the Internet. Deploying the parallel router architecture can efficiently improve the router performance. Parallel router is comprised of multiple lower speed forwarding and switch modules which operate independently and in parallel. Parallel router is scalable and costs effectively.Load balance is the key to improving the throughput of parallel router. Unfortunately, load balance may cause packet reordering, which will unnecessarily trigger the TCP congestion control mechanism, and thus deteriorate the performance of TCP connections and the network utility. How to deal with the contradiction is a big problem in parallel router design.Analysis of the effect of packet reordering on TCP throughput and the reorder rate caused by parallel processing is important to compromise between load balance and packet order guarantee. This dissertation establishes a quantitative relationship among packet loss rate, reorder rate, and TCP throughput in NewReno algorithm. Based on the relationship, the effect on TCP throughput caused by reordered packets is analyzed. This dissertation estimates the reorder rate caused by parallel processing based on the traffic captured in the Internet2. According to the analysis, this dissertation points out that packet order guarantee should be considered during parallel processing, and reasonable tradeoff must be made between it and load balance. The parallel router should first guarantee the packet order under light load, and do more load balance with the increase of the load.Switch is the core of router. This dissertation presents the PSIQC parallel switch architecture comprised of input-queued crossbar switches, and its cell scheduling algorithm, RRDS. RRDS algorithm avoids packet reordering, balances the load efficiently, and has high throughput. It scales well with the size of PSIQC. A revised version of PSIQC based on split queues that is initialed as SQ-PSIQC is proposed. SQ-PSIQC not only has the characteristics of PSIQC, but also reduces the memory bandwidth requirement, and improves the performance. LS-RRDS algorithm is proposed based on RRDS and local sequence number mechanism. LS-RRDS and the buffer admission control mechanism are deployed in PSIQC to make it fault tolerant. Taking advantage of the round robin working property of RRDS, LS-RRDS tolerates lots of cell losseswith, little cost.In order to make forwarding decision at line rate in high speed networks, this dissertation presents a parallel forwarding engine comprised of several network processors. An adaptive load dispatching algorithm based on a mapping table, AIHDA, is proposed. AIHDA dispatches the incoming packets to different NPs according to the workload at each NP and traffic characteristics. It compromises between load balance and packet order guarantee, and has good performance.