Research On System Software Of High-performance Service Router

Recently, there has been an increased interest in expanding the set of services that Internet provides. The demand of extending the set of services, such as IPTV, Voice over IP and Virtual private Networks, represents an opportunity to extend the traditional domain of Internet routers beyond simple best-effort forwarding. High-performance service routers, lying in the network aggregation layer, are the service access points between versatile services of subscribers and service provider environment. Due to their critical position in the Next-Generation Internet (NGI), service routers should be extensible and robust when presented with unanticipated applications and workloads. They should dynamically allocate their resources across the services they support according to dynamically-established policies to ensure that each service gets the resources it needs. This dissertation studies the key issues of system software on service routers and makes four contributions.It is the software architecture that determines the scalability and flexibility of services routers. Most of current researches build their software on the commercial off-the-shelf components(Linux, etc.) and thus lack of the exploration on the real-world NPU-based distributed routers. This dissertation presents an extensible routing software platform for services routers called EROS (Extensible Routing Operation System), which is a modularized and layered system. EROS innovatively utilizes software forwarding engine to hide concrete hardware details and thus can be used in different network processor based routers. This dissertation also describes a novel distributed reliable communication mechanism (RCMS) designed for internal communication in EROS. The RCMS combines reliable multicast and TCP-socket based uni-cast,and could satisfy the reliability requirements of internal communication.Forwarding operation is a complex and important issue on data plane processing in services routers. The dissertation describes a novel policy based flow forwarding (PFF) mechanism designed for service routers. Unlike traditional per-packet forwarding method, PFF only performs extensive processing on the first packet of a flow, associates this flow with a policy and applies the result of this processing on subsequent packets in the flow. It is shown by model analysis that hash and flow-rule replacement algorithms determine the flow forwarding performance. Based on the theoretical result, the dissertation proposes a weighted LRU algorithm and compares different hash algorithms. The experiments on the real trace demonstrate that the proposed WLRU can increase flow rule match rate significantly.Fault recovery is one of the key issues in software system. This dissertation systematically presents possible implementation approaches on fault recovery mechanism in service routers. It shows by continuous-time Markov chain (CTMC) model and analysis that current protection approaches could not be effectively applicable for different application scenarios. Consequently, this dissertation proposes a novel Adaptive Fault-recovery Mechanism (AFM), which could dynamically select protection schemes in different scenarios. The experiments on the test bed show AFM are more effective than current protection schemes, achieving fast fail-over without causing extra burden on the system resources.This dissertation analyzes different bandwidth allocation (BA) models in IP networks and proposes a generic revenue-aware BA model. This dissertation classifies the RBA (Revenue-based Bandwidth Allocation) problems into SRBA (Strict RBA) and FRBA (Flexible RBA) problems. It also proves that RBA problem is equivalent to Knapsack problem and provides Enhanced Greedy Algorithms to solve it. The experiments on the service router show that the proposed algorithms are efficient and can be calculated in polynomial time.All the proposed algorithms and schemes have been implemented on a 128Gbps prototype service router designed for National High-Tech Research and Development Plan of China (Proj. No. 2003AA121110 and 2005AA121410). The project had been checked and accepted, and the router has been licensed by China Ministry of Information Industry.