( 您好!臺灣時間:2022/08/15 09:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::


研究生(外文):Shi-Ming Zhao
論文名稱(外文):Next Generation IP-switching Routers
指導教授(外文):Nen-Fu Huang
外文關鍵詞:Next Generation IP-switching RoutersQoSlink speedsrouter throughputpacket forwarding ratespacket classificationQoS control
  • 被引用被引用:0
  • 點閱點閱:939
  • 評分評分:
  • 下載下載:30
  • 收藏至我的研究室書目清單書目收藏:2

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.

第一頁 上一頁 下一頁 最後一頁 top