Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-12-18
2001-06-19
Vincent, David R. (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000
Reexamination Certificate
active
06249521
ABSTRACT:
This application is related to the following commonly-assigned, copending applications, filed concurrently herewith, entitled: METHOD AND APPARATUS FOR AUTO-INCREMENTING THROUGH TABLE AND UPDATING SINGLE REGISTER IN MEMORY 08/993,834, METHOD AND APPARATUS FOR SCALING NUMBER OF VIRTUAL LANS IN A SWITCH USING AN INDEXING SCHEME 08/993,831, METHOD AND APPARATUS FOR CAPTURING SOURCE AND DESTINATION TRAFFIC 08/993,884, METHOD AND NETWORK SWITCH HAVING DUAL FORWARDING MODELS WITH A VIRTUAL LAN OVERLAY 08/993,835, METHOD AND APPARATUS FOR MANAGING BIN CHAINS IN A MEMORY 08/993,826, APPARATUS AND METHOD FOR GENERATING AN INDEX KEY FOR A NETWORK SWITCH ROUTING TABLE USING A PROGRAMMABLE HASH FUNCTION 08/992,795, SHARED ADDRESS TABLE WITH SOURCE AND DESTINATION TWO-PASS ALGORITHM 08/993,048 and METHOD AND APPARATUS FOR MANAGING LEARNING IN AN ADDRESS TABLE IN A MEMORY 08/994,691.
TECHNICAL FIELD
The present invention relates to network communications and more particularly, to generating data forwarding information in a network switch.
BACKGROUND ART
In computer networks, a plurality of network stations are interconnected via a communications medium. For example, Ethernet is a commonly used local area network scheme in which multiple stations are connected to a single shared serial data path. These stations often communicate with a switch located between the shared data path and the stations connected to that path. Typically, the switch controls the communication of data packets on the network.
When all of the stations connected to the network are simultaneously operating, packet traffic on the shared serial path can be heavy with little time between packets. In addition, data received by the switch may include data that is being transmitted to a single station (unicast), data that is being transmitted to multiple stations (multicast) or data that is being transmitted to all the stations (broadcast). In order for the data to be transmitted without delays, the switch must make data forwarding decisions for many packets being transmitted to a large number of destinations in a short amount of time.
One arrangement for generating frame forwarding decisions uses a direct addressing scheme, where the network switch accesses a fixed address table storing switching logic to generate a frame forwarding decision. However, these direct addressing arrangements may not support data transmissions from stations utilizing virtual local area network (VLAN) tagging as well as transmissions from stations that do not utilize VLAN tagging. In addition, as the number of stations in the network increases, such systems become impractical since a row-by-row search for the appropriate table entry may be too slow for making frame forwarding decisions for multiple received data frames.
SUMMARY OF THE INVENTION
There exists a need for a switching device that generates frame forwarding information for various types of data transmissions, including transmissions that utilize VLAN tags.
There is also a need for a switching device that reduces the amount of time spent searching for data forwarding information by utilizing a hashing scheme to generate a forwarding port vector.
These and other needs are met by the present invention, where data received by the network switch is routed to an internal decision making engine that includes an address table that represents a plurality of bins of entries. The network switch generates hash keys for the received source and destination addresses and the internal decision making engine uses these hash keys to search particular bins in the address table. The internal decision making engine generates a forwarding port vector and outputs the result for data forwarding purposes.
According to one aspect of the invention, a network switch is configured for controlling the communication of data frames between stations. The switch includes a receive device that receives data frames from connected stations. The switch also includes an address table for storing address information including both source addresses and destination addresses. The table represents a plurality of bins of address entries. A hash key generator is coupled to the receive device and generates a source address hash key and a destination address key. The internal decision making engine receives the hash keys, source address, destination address and receive port number and generates data forwarding information for the data frame.
Another aspect of the present invention provides a method for generating data forwarding information. The method includes receiving information from a data frame, the information including a source address and destination address. The method also includes generating a hash key from the source address and a hash key from the destination address. The method further includes searching at least one of a plurality of bins in an address table, based on the hash keys, for data forwarding information.
Other objects and advantages of the present invention will become readily apparent to those skilled in this art from the following detailed description. The embodiments shown and described provide illustration of the best mode contemplated for carrying out the invention. The invention is capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings are to be regarded as illustrative in nature, and not as restrictive.
REFERENCES:
patent: 5305321 (1994-04-01), Crayford
patent: 5515376 (1996-05-01), Murthy et al.
patent: 5663865 (1997-09-01), Kawada et al.
patent: 5862338 (1999-01-01), Walker et al.
patent: 5923654 (1999-07-01), Schnell
patent: 5949786 (1999-09-01), Bellenger
patent: 6098110 (2000-08-01), Witkowski et al.
Advanced Micro Devices , Inc.
Vincent David R.
LandOfFree
Method and apparatus for creating a port vector does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for creating a port vector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for creating a port vector will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2465168