Methods and systems for fast packet forwarding

Details Methods and systems for fast packet forwarding Methods and systems for fast packet forwarding

2006-01-10

2006-01-10

Jung, Min (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S400000, C707S793000, C709S238000

Reexamination Certificate

active

06985483

ABSTRACT:
Methods and systems for fast packet forwarding include traversing a trie data structure stored in on-chip memory based on bits in an input address. The bits in the input address result in a predetermined location in the data structure. The number of bits that have a first value and that are located before the determined location is calculated. The calculated number of bits corresponds to an offset in a second memory device of an address to which the packet having the input address is to be forwarded. The address can be extracted using a single access to an off-chip memory device.

REFERENCES:
patent: 5491694 (1996-02-01), Oliver et al.
patent: 5566170 (1996-10-01), Bakke et al.
patent: 5598410 (1997-01-01), Stone
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5790546 (1998-08-01), Dobbins et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5917820 (1999-06-01), Rekhter
patent: 5920886 (1999-07-01), Feldmeier
patent: 5983223 (1999-11-01), Perlman
patent: 5991299 (1999-11-01), Radogna et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6014659 (2000-01-01), Wilkinson et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6058431 (2000-05-01), Srisuresh et al.
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6119171 (2000-09-01), Alkhatib
patent: 6128664 (2000-10-01), Yanagidate et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6147976 (2000-11-01), Shand et al.
patent: 6154446 (2000-11-01), Kadambi et al.
patent: 6157955 (2000-12-01), Narad et al.
patent: 6173384 (2001-01-01), Weaver
patent: 6181698 (2001-01-01), Hariguchi
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6212183 (2001-04-01), Wilford
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6216168 (2001-04-01), Dev et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6243720 (2001-06-01), Munter et al.
patent: 6396842 (2002-05-01), Rochberger
patent: 6522632 (2003-02-01), Waters et al.
patent: 6571313 (2003-05-01), Filippi et al.
patent: 6697363 (2004-02-01), Carr
patent: 6711661 (2004-03-01), Zabarski et al.
patent: 6877005 (2005-04-01), Hunter et al.
Lampson et al., “IP Lookups Using Multiway and Multicolumn Search,” IEEE, p. 1248-1256, (1998).
Waldvogel et al., “Scalable High Speed IP Routing Lookups,” ACM, p. 25-36, (1997).
Degermark et al., “Small Forwarding Tables for Fast Routing Lookups,” ACM, p. 3-14, (1997).
Michigan University and Merit Network, “Internet Performance Measurement and Analysis Project,” http:/
ic.merit.edu/ipma, p. 1-17, (2002).
Nick McKeown, “How Scalable is the Capacity of (Electronic) IP Routers,” Optical Fiber Communication Conference, p. 1-36, (Mar. 2001).
Chiueh et al., “Cache Memory Design for Networking Processors,” Proceedings of Sixth International Symposium on High-Performance Computer Architecture, p. 1-10, (2000).
Yazdani et al., “Fast Scalable Schemes for the IP Address Lookup Problem,” Proc. IEEE Conference on High Performance Switching and Routing, p. 83-92, (2000).
Wei et al., “Just-In-Time Signaling for WDM Optical Burst Switching Networks,” Journal of Lightwave Technology, vol. 18 (No. 12), p. 2019-2037, (Dec. 2000).
Listanti et al., “Architectural and Technological Issues for Future Optical Internet Networks,” IEEE Communications Magazine, p. 82-92, (Sep. 2000).
Chiueh et al., “High-Performance IP Routing Table Lookup Using CPU Caching,” Proc. IEEE INFO-COM '99, p. 1421-1428, (1999).
McKeown et al., “High Performance Switches and Routers: Theory and Practice,” Hot Interconnects Tutorial Slides, http://tiny-tera.standford.edu
ickm/talks/index.html, p. 1-126, (1999).
Nilsson et al., “IP-Address Lookup Using LC-Tries,” IEEE Journal on Selected Areas in Communications, vol. 17 (No. 6), p. 1083-1092, (Jun. 1999).
Huang et al., “A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers,” IEEE Journal on Selected Areas in Communications, vol. 17 (No. 6), p. 1093-1104, (Jun. 1999).
Gupta et al., “Routing Lookups in Hardware at Memory Access Speeds,” Proc. IEEE INFOCOM'98 , p. 1240-1247, (1998).
J.M. Rabney, “Digital Integrated Circuits, A Design Perspective,” Prentice Hall, Ch. 8, p. 446-454, (1996).
Keith Sklower, “A Tree-Based Packet Routing Table for Berkeley Unix,” Technical Report, p. 1-14.

Affiliated with

Also associated with

Rating

Methods and systems for fast packet forwarding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and systems for fast packet forwarding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for fast packet forwarding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3601408