Studies On CQS In High-Speed Network Elements

The quality of service (QoS) is one of the most important areas of Internet development. As the Internet originally developed for data communications is now used more and more for real-time applications, there is a need for better service than the "best effort". The research topics about QoS range from routing, multicast, implement models to QoS signaling, protocol, and so on.We only study basic components:CQS, which is rated to QoS traffic transmission: admission controlling, traffic scheduling, queueing, and flow classifying. We focus on the traffic scheduling and flow classifying in this paper. The major work of the dissertation is outlined as follow:In Chapter 1, we first present the concept quality of service, describe the current evolution of QoS architecture, mechanisms, and protocols in the Internet. A short review of the proposed standard approaches to QoS(e.g. differentiated services, integrated services, and label switching technologies) is given. Finally we introduce our dedicated research topics in this area.In Chapter 2, we look at the problem of traffic control and the research in this area. We first explain the basic components of admission control. We then talk about some well known admission control schemes: l)Measurement-based Admission Control(MBAC); 2)Endpoint Admission Control(EAC); 3)Policy-based Admission Control(PAC); 4)Subnet Bandwidth Manager(SBM). An analysis of their performances and a comparison of the results follow. Finally, we discuss traffic parameter control: policing and shaping.In Chapter 3, we discuss the queueing for input-queued, output-queued, and combined input/output-queued switch. We mainly study scheduling algorithms based on input-queued and output-queued and show that output queueing can afford the best QoS guarantee but has a poor expansibility; The input queueing, through has a high scalability, lacks of the necessary QoS features. In this chapter, we devote to the packet scheduling algorithms which are suitable to both queueing. Based on rate-proportional server(RPS), we present an efficient and simple fair queueing algorithm, called SMFQ(Start-Potential Mean Fair Queueing) which has O(l) complexity for the virtual time computation while has fairness properties batter than SPFQ. The same as SPFQ, when combined with a shaping mechanism(or select packet for transmission with SEFF policy)to achieve an ideal worst-case fairness index, SMFQ satisfies all the properties necessary to make the resulting system a work-conserving scheduler. In this chapter, we discuss that it is not true that PFQ algorithm when approximates a fluid rate-proportional server with SEFF policy can achieve the same worst-case fairness as that of WF2Q. We give a new value of worst-case fairness index for it and show that is inferior to the index of WF2Q. Some related statements and conclusions presented before are required for revision and the new results for them are given in this chapter.In Chapter 4, we introduce and analyze packet classification algorithm. Routers must perform packet classification at high speeds to support advanced functions such as firewalls and QoS routing. While several efficient solutions are known for the one-dimensional IP lookup problem, the mult-dimensional packet classification has proved to be far more difficult. Existing filter schemes with fast lookup time do not scale to large filter database. Based on tuple space search, apacket classification algorithm called bitmap vector of tuple space for multi-dimensional conflict-free filters is presented in this chapter. The result of the performance analysis in two-dimension and multi-dimension shows that the scheme provides better worst case bounds about time and space complexity than what have existed, so the algorithm is more scalable and faster. The novel approach can be easily implemented both from software and hardware which made this algorithm more practical to applications.