Study On Several Problem About Cell Scheduling Or Packet Scheduling In High-speed Router

This dissertation is a part of project "Study on Switching & Routing mechanism, Protocols and Algorithms in very high speed network node ", which is supported by the foundation of 863 Hi-Tech Research and Development Program of China (863 HTRDP) under Grant 2001 -AA-12-4-011.To find ways using the switch fabric resource in high-speed router more efficiently, two optimized cell payload solutions for fix-sized cell-by-cell scheduling (for short, cell scheduling) are present. Likewise, a novel Parallel Packet Switch (PPS) based on memory devices offered nowadays and a novel variable-length packet-by-packet scheduling (for short, packet scheduling) algorithm are also present. The contributions include: On cell scheduling: based on IP packet length statistic data sampled from more than 10 sites, the efficiency analysis of IP packets Segmentation and Reassembly (SAR) technology in cell scheduling, the concept of optimal SAR cell, the Adaptive Segmentation and Reassembly (ASAR) solution adapting IP traffic, and the Mergence and Separation plus Segmentation and Reassembly (MAS+) solution are present. On packet scheduling: A novel multi-stage buffering PPS and the Distributed Variable-Length Packet Scheduling (DVLPS) algorithm are present.The problem statement, motivation and research background of variable-length IP packets cell scheduling and packet scheduling in high-speed router, are narrated in Chapter one. At the end of this chapter, the work has been done is outlined.In Chapter two, based on the statistic data sampled from more than 10 sites, a method which analyzes the efficiency of SAR technology in cell scheduling is present.And, the efficiency of an ASIC (Application Specific Integrated Circuit) with SAR technology is analyzed. The concept of optimal SAR cell of IP packets cell scheduling in high-speed router is present.The ASAR solution in cell scheduling is present in Chapter 3. With this technology, the router can adapt IP packet distribution changes brought by the locations of the router in different networks, and adapt the IP traffic changes in a network. Computer simulations testing the performance improvement based on sample data are also given.In Chapter 4, MAS+ solution in cell scheduling is present. This solution reduces IP packet Fix-sized Processing Cost (FPC) efficiently, and prolongs the arbitration interval. Computer simulations for testing performance improvement and of latency analysis are also given.In Chapter 5, a novel multi-stage buffering PPS is present. And the distributed variable-length packet scheduling algorithm (DVLPS) used in the PPS is also present. Analysis of the PPS and the packet scheduling algorithm and a part of performance testing results are also present.