Abstract
With the unprecedented growth of Internet applications, demands of powerful routers are rapidly increasing. In such routers, five key design issues must be illustrated for providing sophisticated value-added services and to continue to furnish good quality of service (QoS). Those are: link speeds, router throughput, packet forwarding rates, packet classification, and QoS control. Actually, the first two issues are currently readily available. In this dissertation, we inspect the last three issues to design next generation IP-switching routers.One of key design issues for next generation IP-switching routers is the routing lookup scheme. For each incoming IP packet, the IP-routing is required to perform a longest-prefix match on the routing lookup in order to determine the packet’s next hop. In this dissertation, we propose a fast unicast routing lookup scheme, which only needs tiny high-speed RAM and can be implemented using a hardware pipeline. When implemented using a hardware pipeline, the proposed scheme can achieve one routing lookup every memory access. With current 0.84ns RDRAM, this scheme furnishes approximately 1,200×106 routing lookups/second, which is much faster than any current commercially available routing lookup scheme.Besides, next generation IP-switching routers must perform packet classification at high speeds for efficiently providing sophisticated value-added services to users with a variety of requirements. Packet classification requires parsing each packet according to predefined filters (or rules), and classifying the packet based on the matched filter with the highest priority. This dissertation presents a scheme that can be applied to accomplish packet classification in routers, which need to support multigigabit processing capacities and to furnish value-added services for widely varying Internet applications.As everybody knows, the Internet is always a best-effort network for a long time. Such behavior, however, does not satisfy widely varying Internet applications any more. In order to continue to furnish good QoS, next generation IP-switching routers also have to cost-effectively perform QoS control after classifying each packet. In this dissertation, we design a rate control scheme. This scheme can rapidly determine the departure time of the arrival packet, and then transmit out the packet on schedule. Using this rate control scheme, next generation IP-switching routers neither generate any dummy packet nor waste any bandwidth, but still accomplish user-friendly rate-based QoS control manner.