Research On The Key Technologies Of Cluster Based Router

With the development of optical network and IPv6 network, speed of network interface grows rapidly, router must route and forward packet fast enough to fit its interface speed. For interface of 40 gigabit per second, routing and forwarding must be done within 8 ns, which is difficult to archive in a single processor. High speed router always process packets in a distributed architecture, which bind Forwarding Engine and Line Card one by one trough Switch Backplane to work distributed. We find it un-efficient because some FEs with heavy traffic may haven't enough power, while some FEs with low traffic may have surplus power. On the aspect of address lookup, most algorithms focus on high speed lookup, while pay little attention to fast updating and lost of prefix. This thesis proposes a new kind of router architecture called Router Cluster, and a IPv6 address lookup algorithm that support fast update, which can solve those problems. Router cluster has a physically distributed architecture that connects some routers together, sharing their traffic and processing power. Routers work on an abstract platform to co-operate with each other and build a high performance router with lower cost. This thesis discusses some problems of router cluster, such as software platform, traffic model, load balance, and address lookup. Queuing theory is used to analyze the traffic model and proper load balancing algorithm of router cluster. Since the traffic pass through different path may have different delay, keeping fairness of latency is most important. OPNet modeler is used to simulate and prove our solutions. First we design a layered open abstract platform to fit the requirement of router cluster and traditional distributed routers. It provides a uniform and abstract environment to hybrid routers of router cluster. We carefully design each layer of the platform which is called LOARD. A prototype of router cluster built with three PCs (Linux OS), is developed to prove that LOARD is reasonable and realizable, which is connected by Ethernet switch. After studied data flow of routers and router cluster, we propose two kind of traffic model: "Ratio Sharing"and "Parallel Sharing". We study two queue's scheduling and assure that local traffic and shared traffic has the same latency. Trough simulation, we find that the jitter of latency can be restricted within 8% when use our scheduler. Use traffic model of ratio sharing, a router cluster can provide the same delay of all traffic path. To resolve the new problems of process power sharing and load balancing, we propose an Adaptive Dynamic Assigning algorithm to limit maxim delay, which make sure that all cluster nodes can share traffic fairly. A counted transferring mechanism is used to avoid miss assigning and packet losing. VOQ and improved DRR scheduler is used to assure that all nodes can utilize inter connection fairly. Simulation shows us that Adaptive Dynamic Assigning can balance the traffic with minimal internal flow and limited latency. In this thesis we analyze IPv4 and IPv6 address lookup algorithm, including the distribution, usage, and assignment of IPv6 address, especially the requirement of fast update. We propose a partitioned and controlled prefix expanding (PCPE) algorithm, which can improve updating speed with low influence to lookup speed. A real IPv6 routing table of core router is used to test our algorithm. We prove that PCPE can speed up the updating of IPv6 routing table, and {1 6, (16,8,8,8,8),k}partition is the optimized solution of IPv6.