| The emergence of the Internet popularity of personal computers, wide application of micro-computing devices, have imposed significant impact on human society and changed people’s working and living style greatly. With proliferation of Internet application, types and numbers of application have been increased greatly and numbers of user have been continuous rising exponentially; consequently, demands for high-speed and high-efficiency relay systems with great-capacity are increasing rapidly. The fact that multimedia have been dominating the network traffic flows and changes in network application mode from B/S to co-existence of B/S and P2P, have imposed much difficulty for ensuring QoS. Deterioration of network operation environment has forced Subnetworks, End-system, and application systems facing severe security challenges. With wide application of wireless communication techniques and mobile devices, mobile access to Internet becomes more and more popular trend. All these problems have been challenging the Internet techniques with its more than30years’history, especially with its network architecture. As a result, people are calling for high-performance network devices, subnetworks, and new application systems.Backed up by the research on NGI (Next Generation Internet) architecture and technologies, the research work presented in this PhD thesis is devoted to high-performance switch fabric and switching techniques. An emphasis has been given to a particular CICQ (Combined Input Cross-point Queued, CICQ) switching structure, i.e. CICQ switch with a single buffer at cross-points, either equal to a cell length (for cell switching), or to the maximum frame length. CICQ can be seen as a special type of crossbar construct, which can ease the conflict between input and output logics as in input queuing crossbar enabled by buffers at cross-points to separate the input logic from output logic. As a result, it can pave the way for various distributed scheduling algorithms to improve the performance of switches and QoS provisioning. CICQ structure has drawn more and more attention from both academic and industrial communities with new progress in memory. Compared with traditional crossbar structure, CICQ has opened up a new way in supporting variable length frames apart from cell (fixed-length segments of a frame) switching, the traditional way for crossbar structure.The research results presented in this thesis involve two types switching, i.e. orthodox cell switching based on fixed length, say64bytes and variable-length data switching, which has not yet been fully explored up to date.With regard to cell switching, the author’s Long Queue Prioritized-Round Robin algorithm (LQP-RR) has been attempted to reduce the computational complexity (lower boundary:O(N log N)) of LQF-RR (Longest Queue First-Round Robin)-a typical CICQ algorithm, and to enable easy implementation. During scheduling, LQP-RR algorithm finds the long virtual output queue (VOQ) at input by using local variation of VOQ lengths with one comparison-operation. Therefore, LQP-RR algorithm can easily be implemented in hardware since its computing complexity has been reduced to O (1). Furthermore, the fairness of the algorithm can be ensured with the help of an auxiliary pointer for RR-polling. All these advantages of LQP-RR have paved the way for author to develop a better algorithm called HOPS (Hybrid Optimization Packet Scheduling) with features of low computing complexity, high-utility of the switch fabric, and shorter switching delay.The algorithm of HOPS intends to maximize the total throughput of a switch with the policy that there will be a cell to be output in each timeslot for as many output ports as possible so as to increase the utility of output ports. To do so, input scheduling algorithm has to direct cells to crosspoints so as to enable for as many as output ports that there will be a cell to output. The author has proved with the fluid model that the throughput for HOPS can approach to100%of the theoretic switching capability for allowable traffic tallying with the law of the large number. Simulation results have also shown that the algorithm of HOPS works stably for all admissible traffic pattern and switching delay is evidently shorter than those of existing algorithms without need of speeding-up for switch fabric. Finally, implementation of the algorithm of HOPS is quite simple since its computation complexity is the same as that of LQP-RR.As for variable-length data switching, the research results of this thesis involve direct variable-length frame switching as well as segmented variable-length data switching. In respect of direct frame switching, this dissertation introduced an algorithm called TFVD (Two-stage Flow-control for Variable-length Data) for CICQ switching structure with single buffer of maximum frame length. Compared with existing algorithms for variable-length frame switching in CICQ, TFVD has improved the throughput and fairness and shortened the time-delay. This is done via two-stage flow control and a Token Quota mechanism, with which the scheduler postpones a frame without enough Quota to a later time until enough quota has been accumulated so as to prevent long frames from excessively using the switching capability. Simulation results have shown that TFVD algorithm can improve the switching performance as well as fairness, and with burst traffic of98%full load, its time-delay is11%,17%, and25%shorter than existing algorithms-MQF-RR、DRR and PP-VOQ respectively.Regarding segmented variable-length data switching, this dissertation proposes a "Multi-frame Variable-length Segmentation with Feedback"(MVSF) strategy. With this strategy, a segment can be formed of pieces from multi-frames to avoid padding costs in single-frame segmentation. Furthermore, free space information of buffers at crosspoints is fed back to input scheduler for dynamic tuning of segmentation to prevent from buffer-overflow otherwise no segment can be delivered to the buffer. Simulation results have shown that the throughput and switching delay with MVSF strategy are better than those of existing segmentation strategies.Then, segmentation strategy of variable length packet in CICQ switch fabric is studied in this dissertation and a feedback variable size multi-packet segmentation strategy is proposed for CICQ switches. The new strategy eliminate the padding overhead and improve the efficiency of segmentation by merging the contiguous packets together, at the same time, the new strategy can adjust the length of segmentation unit by using the status of crosspoint, to ensure the switch system can work-conserving. Simulation demonstrated that the proposed scheme exhibits better performance than existing strategies.QoS enabled mechanism is an important technique concerning the performance of next generation switches/routers. Chapter5deals with the issue of upper and lower boundaries of time-delay in CICQ switches. Considering that performance of WF2Q algorithm approximates that of the ideal Generalized Processor Sharing (GPS) model, the author has applied WF2Q both to input and output scheduling in single buffer CICQ, i.e. WF2Q*-WF2Q. As a result, a mathematic expression of time-delay upper and lower boundaries of the near-ideal GPS-GPS reference model for variable-length data switching in single buffer CICQ is derived and proves that with the WF2Q*-WF2Q algorithm,time-delay is limitary in such CICQ. |
PDF Full Text Request