臺灣博碩士論文加值系統

隨著網際網路應用的空前成長，對於高效能路由器的需求正與日俱增。而為了在這類高效能路由器中，提供複雜的加值性服務並且持續滿足良好之服務品質，有五項重要的設計關鍵必須加以考量。那就是：傳輸線速度，路由器吞吐量，封包轉送速率，封包辨識分類，以及服務品質之控制。事實上，前二項設計關鍵目前皆垂手可得。而在本篇論文中，我們著重於後三項關鍵要素，以便設計新一代網際網路交換式路由器。
設計新一代網際網路交換式路由器的關鍵要素之一，就是路由查詢的機制。對於每個輸入的網際網路封包而言，為了決定其下一站為何，網際網路的路由必須在路由查詢上，進行最長前置位元資訊之比對。在本篇論文中，我們提出一快速的單點路由查詢機制，該機制僅需極小量的高速隨機存取記憶體並且能夠透過管線設計方式加以實現。當透過管線設計方式加以實現時，所提之機制能夠達到每一次的記憶體存取便可以獲得一個路由查詢之結果。以現階段ＲＡＭＢＵＳ公司所出品的存取週期為０．８４奈秒之隨機存取記憶體而言，該機制幾乎達到每秒１２億個路由查詢，而這比目前任何已商品化的路由查詢機制還快出很多。
此外，為了有效率地提供複雜的加值性服務給許多具備不同需求的使用者，新一代網際網路交換式路由器必須以極快的速度進行封包辨識分類。封包辨識分類需要根據預先定義好的分類規則去剖析每個封包，並且依照符合的分類規則中擁有最高優先權者去對封包進行分類。本篇論文提出一能夠應用於需要支援幾十億位元資訊處理能力，同時並提供加值性服務給各式各樣網際網路應用的路由器中所需的封包辨識分類之機制。
正如大家所知道的，網際網路已有一段漫長的時間一直都是盡力式的網路。然而，這樣的網路行為已完全無法滿足形形色色的網際網路應用。而為了持續提供良好的服務品質，新一代網際網路交換式路由器也必須於每個封包完成辨識分類後，具成本效益地提供服務品質的控制。在本篇論文中，我們設計一個速率控制的機制。該機制能夠迅速地決定到達封包的離開時間，然後準時地將封包傳送出去。運用此一速率控制機制，新一代網際網路交換式路由器既不會產生任何毫無作用的假造封包也不會浪費任何頻寬，而且仍然能夠達到使用者所喜好的以速率為基礎的服務品質控制方式。

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.

Chapter 1 Introduction 1
1.1 Classless Interdomain Routing (CIDR) 2
1.2 IP-switching Router Architecture 3
1.3 Next Generation IP-switching Router Architecture 5
1.4 Outline of the Dissertation 7
Chapter 2 Related Work 9
2.1 Fast Routing Lookup Schemes 9
2.2 Packet Classification Problem 11
2.2.1 Generalized Packet Classification 11
2.2.2 IP Packet Classification 12
2.3 QoS Control Technology 12
2.3.1 Traditional Queuing-based QoS Control 14
2.3.2 Nonqueuing-based Active Rate Control for TCP 15
Chapter 3 A Novel IP-routing Lookup Scheme 17
3.1 Direct-lookup Scheme 17
3.2 Indirect-lookup Scheme 18
3.3 The Proposed Fast Routing Lookup Scheme 24
3.4 Hardware Implementation 32
3.5 Performance Analysis 35
Chapter 4 A Flexible Ternary Match Scheme for Packet Classification 38
4.1 Packet Classification VS. Ternary Match 38
4.2 Basic Idea of the Proposed Ternary Match Scheme 41
4.2.1 1×1 Ternary Match Scheme 41
4.2.2 1×2 Ternary Match Scheme 45
4.2.3 1×W Ternary Match Scheme 48
4.2.4 2×W Ternary Match Scheme 50
4.3 The Proposed Ternary Match Scheme 52
Chapter 5 A Novel Rate Control Scheme 57
5.1 Basic Idea of the Proposed Rate Control Scheme 57
5.2 Ideal TDQ-RCS 59
5.3 Approximation TDQ-RCS 64
5.4 Approximation TDQ-RCS with MSS 70
Chapter 6 Conclusions 74
Bibliography 76

[1] F. Baker, “Requirements for IP Version 4 Routers”. RFC 1812, June 1995.
[2] J.C.R. Bennett and H. Zhang, “WF2Q: Worst-case Fair Weighted Fair Queueing”. IEEE INFOCOM’96, pp. 120-128, March 1996.
[3] J.C.R Bennett and H. Zhang, “Why WFQ Is Not Good Enough for Integrated Services Networks”. NOSSDAV’96, April 1996.
[4] Z. Cao, Z. Wang, and E. Zegura, “Rainbow Fair Queueing: Fair Bandwidth Sharing Without Per-Flow State”. INFOCOM’00, March 2000.
[5] A. Clerget and W. Dabbous, “Tag-based Fair Bandwidth Sharing for Responsive and Unresponsive Flows”. INFOCOM’01, Anchorage, AK, April 2001.
[6] W.S. Cleveland, D. Lin, and D. Sun, “IP Packet Generation: Statistical Models for TCP Start Times Based on Connection-rate Superposition”. ACM SIGMETRICS’00, June 2000.
[7] S. Deering and R. Hinden, “Internet Protocol, Version 6 (IPv6) Specification, Request for Comments (Proposed Standard)”. RFC 1883, Internet Engineering Task Force, January 1996.
[8] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small Forwarding Tables for Fast Routing Lookups”. ACM SIGCOMM’97, pp. 3-14, Cannes, France, September 1997.
[9] A. Demers, S. Keshav, and S. Shenker, “Analysis and Simulation of A Fair Queueing Algorithm”. ACM SIGCOMM’89, pp. 1-12, September 1989.
[10] W. Doeringer, G. Karjoth, and M. Nassehi, “Routing on Longest-Matching Prefixes”. IEEE/ACM Transactions on Networking, Vol.4, No.1, pp.86-97, February 1996.
[11] D. Estrin, J. Postel, and Y. Rekhter, “Routing Arbiter Architecture”. ConnecXions, pp. 2-7, Vol. 8, August 1994.
[12] D. Feldmerier, “Improving Gateway Performance with A Routing-table Cache”. IEEE INFOCOM’88, pp. 298-307, New Orleans, Louisiana, March 1998.
[13] P. Gupta, S. Lin, and N. McKeown, “Routing Lookups in Hardware at Memory Access Speeds”. IEEE INFOCOM’98, pp. 1240-1247, San Francisco, CA, April 1998.
[14] N.F. Huang and S.M. Zhao, “A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers”. IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pp. 1093-1104, June 1999.
[15] N.F. Huang and S.M. Zhao, “Bit-Stream Ternary Match Scheme and Apparatus”. Taiwan Patent Application, December 1999, and United States Patent Application, January 2000.
[16] N.F. Huang and S.M. Zhao, “IP Routing Lookup Scheme and System for Multi-gigabit Switching Routers”. Approved by Taiwan Patent, November 2000, and United States Patent Application, February 1999.
[17] N.F. Huang and S.M. Zhao, “System and Method for Managing Flow Bandwidth Utilization in A Packet Communication Environment”. Taiwan Patent Application, November 2001, and United States Patent Application, December 2001.
[18] N.F. Huang ,S.M. Zhao, Jen-Yi Pan, and Chi-An Su, “A Fast IP Routing Lookup Scheme for Gigabit Switching Routers”. IEEE INFOCOM’99, New York, USA, March 1999.
[19] C. Labovitz, G. R. Malan, and F. Jahanian, “Internet Routing Instability”. ACM SIGCOMM’97, pp. 115-126, Cannes, France, September 1997.
[20] T.V. Lakshman and D. Stiliadis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching”. ACM SIGCOMM’98, pp. 203-214, Vancouver, Canada, September 1998.
[21] B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookups Using Multiway and Multicolumn Search”. IEEE INFOCOM’98, pp. 1248-1256, San Francisco, CA, April 1998.
[22] E.P. Markatos, “Speeding up TCP/IP: Faster Processors are not Enough”. Technical Report TR297, Institute of Computer Science, FORTH, December 2001. Appears in IEEE IPCCC 2002.
[23] K. Mehlhorn, S. Naher, and H. Alt, “A Lower Bound on the Complexity of the Union-split-find Problem”. SIAM Journal on Computing, Vol. 17, No. 1, pp. 1093-1102, December 1988.
[24] A. McAuley and P. Francis, “Fast Routing Table Lookup Using CAMs”. IEEE INFOCOM’93, pp. 1382-1391, San Francisco, CA, March 1993.
[25] S. Nilsson and G. Karlsson, “Fast Address Look-up for Internet Routers”. IFIP Internation Conference of Broadband Communications, 1998.
[26] R.L. Packer, Packeteer Inc., “Method for Rapid Data Rate Detection in A Packet Communication Environment Without Data Rate Supervision”. United States Patent, No. 5802106, September 1998.
[27] R.L. Packer, Packeteer Inc., “Method for Minimizing Unneeded Retransmission of Packets in A Packet Communication Environment Supporting A Plurality of Data Link Rates”. United States Patent, No. 6018516, January 2000.
[28] R.L. Packer, Packeteer Inc., “Method for Explicit Data Rate Control in A Packet Communication Environment Without Data Rate Supervision”. Untied States Patent, No. 6038216, March 2000.
[29] R.L. Packer, Packeteer Inc., “System for Manage Flow Bandwidth Utilization at Network, Transport and Application Layers in Store and Forward Network”. United States Patent, No. 6046980, April 2000.
[30] A. Parekh and R. Gallager, “A Generalized Processor Sharing Approach to Flow Control — The Single Node Case”. ACM/IEEE Transactions on Networking, Vol. 1, No. 3, pp. 344-357, June 1992.
[31] T. Pei and C. Zukowaki, “Putting Routing Tables in Sillicon”. IEEE Network Magazine, pp. 42-50, January 1992.
[32] Y. Rekhter and T. Li, ”An Architecture for IP Address Allocation with CIDR”. RFC 1518, September 1993.
[33] J. Reynolds and I. Postel, “Official Internet Protocols”. RFC 1011, Internet Engineering Task Force, 1987.
[34] V. Srinivasan, S. Suri, G. Varghese, “Packet Classification Using Tuple Space Search”. ACM SIGCOMM’99, Cambridge, MA, September 1999.
[35] D.C. Stephens, J.C.R. Bennett, and H. Zhang, “Implementing Scheduling Algorithms in High-Speed Networks”. IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pp. 1145-1158, June 1999.
[36] I. Stoica and H. Zhang, “Providing Guaranteed Services without Per Flow Management”. ACM SIGCOMM’99, pp. 81—94, Cambridge, MA, September 1999.
[37] H. Tan, D.L. Eager, M.K. Vernon, and H. Guo, “Quality of Service Evaluations of Multicast Streaming Protocols”. ACM SIGMETRICS’02, Marina Del Rey, CA, June 2002.
[38] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups”. ACM SIGCOMM’97, pp. 25-36, Cannes, France, September 1997.
[39] H. Wang and K.G. Shin, ”Layer-4 Service Differentiation and Isolation”. Technical Report, University of Michigan, June 2001.
[40] P.C. Wang, C.T. Chan and Y.C. Chen, “A Fast IP Lookup Scheme for High-Speed Networks”. IEEE Communications Letters, Vol. 5, No. 3, March 2001, pp. 125-127.
[41] Y.C. Woo, “A Modular Approach to Packet Classification: Algorithms and Results”. IEEE INFOCOM’00, Tel Aviv, Israel, March 2000.
[42] O. Yaron and M. Sidi, “Generalized Processor Sharing Networks with Exponentially Bounded Burstiness Arrivals”. Journal of High Speed Networks, Vol. 3, pp. 375-387, 1994.
[43] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, “RSVP: A New Resource Reservation Protocol”. IEEE Networks Magazine, September 1993.
[44] Z.L. Zhang, D. Towsley, and J. Kurose, “Statistical Analysis of Generalized Processor Sharing Scheduling Discipline”. ACM SIGCOMM’94, pp. 68-77, August 1994.
[45] Y. Zhao, D.L. Eager, and M.K. Vernon, “Efficient Delivery Techniques for Variable Bit Rate Multimedia”. MMCN’02, pp. 142-155, San Jose, CA, January 2002.
[46] Y. Zhao, D.L. Eager, and M.K. Vernon, “Network Bandwidth Requirements for Scalable On-Demand Streaming”. IEEE INFOCOM’02, New York, NY, June 2002.
[47] Intel Corp., Intel IXP1200 Network Processor (White Paper), 2000. Available WWW: http://developer.intel.com/design/network/products/ npfamily/ixp1200.html.
[48] Michigan University and Merit Network, Internet Performance Measurement and Analysis (IPMA) Project. Available WWW: http://nic.merit.edu/~ipma.
[49] Packeteer Inc., “TCP Rate Control-Bandwidth Management Without a Queue”. Available WWW: http://www.packeteer.com/solutions/resources/ tcprate-control.cfm.
[50] Stanford University Workshop on Fast Routing and Switching, December 1996. Available WWW: http://tiny-tera.standford.edu/ Workshop_Dec96/.
[51] The Routing Arbiter Project, Internet Routing and Network Statistic. Available WWW: http://www.ra.net/statistics/.
[52] W. Richard Stevens, Addison Wesley Longman Inc., TCP/IP Illustrated, Vol. 1, 1994.