Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-08-09
2003-05-20
Nguyen, Steven (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C711S216000
Reexamination Certificate
active
06567404
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to packet switching.
2. Related Art
In a packet-switched network, a “router” is a device which receives packets on one or more input interfaces and which outputs those packets on one of a plurality of output interfaces, so as to move those packets within the network from a source device to a destination device. Each packet includes header information which indicates the destination device (and other information), and the router includes routing information which associates an output interface with information about the destination device (possibly with other information). The router can also perform other operations on packets, such as rewriting the packets' headers according to their routing protocol or to reencapsulate the packets from a first routing protocol to a second routing protocol. It is advantageous for routers to operate as quickly as possible, so that as many packets as possible can be switched in a unit time.
One problem which has arisen in the art is that packets can be in one of a plurality of routing protocols or encapsulations, and can therefore include header information which the router needs to switch the packet (and to perform other operations on the packet) in locations which vary from packet to packet. This requires the router to be able to locate the header information in one or more of various locations within the packet. Thus, methods by which the router might operate relatively quickly can be inflexible with regard to the location for the header information, while methods by which the router might operate flexibly with regard to the location for the header information can be relatively slow.
Some known routers, such as those described in U.S. Pat. No. 5,509,006, “Apparatus and Method for Switching Packets Using Tree Memory”, issued Apr. 16, 1996, in the name of inventor Bruce A. Wilford, and assigned to cisco Systems, Inc., can determine a type for the packet and therefore the location of the header information, by examining each byte of the packet header in turn. Thus, each byte of the packet header provides information regarding interpretation of successive bytes of the packet header, and the router can determine the header information needed to switch the packet in response to the relatively early bytes of the packet header. While this method achieves the goal of being relatively flexible with regard to the location for the header information, it can take many clock cycles to determine the proper header information, and is therefore not as relatively quick as desired.
Accordingly, it would be desirable to provide a method and system for locating header information in packet headers and switching packets in response to that header information, which is both relatively quick and flexible with regard to location of the header information. This advantage is achieved in an embodiment of the invention in which header information recognizers operate in parallel on the packet header to determnine the location of the header information, and the packet is switched responsive to the header information so located.
SUMMARY OF THE INVENTION
The invention provides a method and system for identifying header information in a packet header, and for switching (and otherwise operating on) the packet in response thereto. A first set of header information recognizers operate in parallel on the packet header so as to recognize a header format for the packet header and to determine relevant header information in response to that header format. A second set of header information recognizers operates on the header information to select one or more sets of words from the header information which are used for one or more lookups for treatment of the packet.
In a preferred embodiment, the same or similar header information is located in the packet header responsive to information which determines an encapsulation type for the packet, such as packets which use the IP version 4, rP version 6, or IPX protocols. The header information can include the destination address for the packet, or some combination of the destination address and additional information; the additional information can include the sending address, the input interface, a number of bits matched for the destination address, or some combination thereof.
REFERENCES:
patent: 4491945 (1985-01-01), Turner
patent: 4679189 (1987-07-01), Olson et al.
patent: 4893304 (1990-01-01), Giacopelli et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5249292 (1993-09-01), Chiappa
patent: 5271004 (1993-12-01), Proctor et al.
patent: 5309437 (1994-05-01), Perlman et al.
patent: 5440550 (1995-08-01), Follett
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5519858 (1996-05-01), Walton et al.
patent: 5524254 (1996-06-01), Morgan et al.
patent: 5651002 (1997-07-01), Van Seters et al.
patent: 5684797 (1997-11-01), Aznar et al.
patent: 5684954 (1997-11-01), Kaiserswerth et al.
patent: 5774698 (1998-06-01), Olnowich
patent: 5842224 (1998-11-01), Fenner
patent: 5870382 (1999-02-01), Tounai et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5983223 (1999-11-01), Perlman
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6157641 (2000-12-01), Wilford
patent: 6212183 (2001-04-01), Wilford
patent: 6307855 (2001-10-01), Hariguchi
patent: 2001/0012295 (2001-08-01), Wilford
patent: 2001/0051864 (2001-12-01), Kerr et al.
patent: WO 94/01828 (1994-01-01), None
patent: WO 96/34479 (1996-10-01), None
Shang-Tse Chuang et al. “Matching Output Queueing with a Combined Input and Output Queued Switch”, Stanford CSL-TR-98-758.
Willibald Doeringer et al. “Routing on Longest-Matching Prefixes”. IEEE/ACM Transactions on Networking, vol. 4. No. 1. Feb. 1996.
Jim Duffy. “Cisco goes with the flow”. San Jose, California. May 3, 1996.
Panka, Gupta et al. “Scheduling Algorithms for an Input-Queued Variable Length Packet Switch”. Stanford University. p. 1-34.
Nick McKeown et al. “Bridges, Routers and Switches”. Department of Electrical Engineering. Stanford University, Stanford, CA 94305-9030.
Tong-Bi Pei et al. “VLSI Implementation of Routing Tables: Tries and Cams”. Department of Electrical Engineering. Center for Telecommunications Research. Columbia University. 1991 IEEE.
Paul F. Tsuchiya. “A Search Algorithm for Table Entries with Non-contiguous Wildcarting”. Bellcore.
Cisco Technologies, Inc.
Nguyen Steven
Swernofsky Law Group PC
LandOfFree
Multiprotocol packet recognition and switching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiprotocol packet recognition and switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprotocol packet recognition and switching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3048354