Multiple key lookup arrangement for a shared switching logic...

Details Multiple key lookup arrangement for a shared switching logic... Multiple key lookup arrangement for a shared switching logic...

2000-02-11

2004-02-24

Pham, Chi (Department: 2663)

Multiplex communications

Communication techniques for information carried in plural...

Adaptive

C370S412000

Reexamination Certificate

active

06697380

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to layer
2
and layer
3
switching of data packets in a nonlocking network switch configured for switching data packets between subnetworks.
2. Background Art
Local area networks use a network cable or other media to link stations on the network. Each local area network architecture uses a media access control (MAC) enabling network interface devices at each network node to access the network medium.
The Ethernet protocol IEEE 802.3 has evolved to specify a half-duplex media access mechanism and a full-duplex media access mechanism for transmission of data packets. The full-duplex media access mechanism provides a two-way, point-to-point communication link between two network elements, for example between a network node and a switched hub.
Switched local area networks are encountering increasing demands for higher speed connectivity, more flexible switching performance, and the ability to accommodate more complex network architectures. For example, commonly-assigned U.S. Pat. No. 5,953,335 discloses a network switch configured for switching layer
2
type Ethernet (IEEE 802.3) data packets between different network nodes; a received data packet may include a VLAN (virtual LAN) tagged frame according to IEEE 802.1 q protocol that specifies another subnetwork (via a router) or a prescribed group of stations. Since the switching occurs at the layer
2
level, a router is typically necessary to transfer the data packet between subnetworks.
Efforts to enhance the switching performance of a network switch to include layer
3
(e.g., Internet protocol) processing may suffer serious drawbacks, as current layer
2
switches preferably are configured for operating in a non-blocking mode, where data packets can be output from the switch at the same rate that the data packets are received. Newer designs are needed to ensure that higher speed switches can provide both layer
2
switching and layer
3
switching capabilities for faster speed networks such as 100 Mbps or gigabit networks.
However, such design requirements risk loss of the non-blocking features of the network switch, as it becomes increasingly difficult for the switching fabric of a network switch to be able to perform layer
3
processing at the wire rates (i.e., the network data rate). For example, switching fabrics in layer
2
switches merely need to determine an output port for an incoming layer
2
data packet. Hence, conventional layer
2
switches can perform an address table lookup for switching information merely by searching the address table using a MAC address as a key. For example, a hash function may be performed on a 48-bit MAC address to generate a hash key having a less number of bits, for example, 4 bits. The hash key is then used for accessing an address table configured for storing bin entries and heap entries.
FIG. 1
is a diagram illustrating an address table
100
storing bin entries
102
and heap entries
104
. The bin entries serve as an index for a range of heap entries
104
, where the heap entries
104
assigned to a given bin entry (e.g.,
102
) have the same hash key generated for the respective MAC addresses. Each heap entry
104
includes a MAC address field
105
, a switching information field
106
that includes switching information for the corresponding MAC address field
105
, and a next entry field
108
that specifies the next heap entry
104
belonging to the corresponding bin entry
102
, effectively forming a linked list of heap entries
104
for each of the bin entries
102
. If the hash key is a 4-bit value, then the address table
102
would include up to sixteen bin entries
102
that could be addressable by the corresponding hash key value. Hence, a switching logic generates a hash key from a MAC address, identifies one of the bin entries based on the hash key, and performs a sequential search of the heap entries
104
belonging to be identified bin entry for the appropriate MAC address. Use of the bin entries
102
for searching of the heap entries
104
provides the advantage of reduced search times, since only the heap entries
104
belonging to a given bin entry
102
need to be searched, as opposed to searching the entire address table
100
as a linked list for a given MAC address.
Layer
3
processing, however, requires not only searching of layer
3
switching information based on an Internet Protocol (IP) address, but also may require additional processing to associate a MAC address to an IP address. Hence, the address table
100
of FIG.
1
and the stored switching information
106
would need to be duplicated for IP address lookup operations because multiple keys (MAC address and IP address) would be necessary to perform layer
3
processing. Consequently, the amount of address table space necessary to add layer
3
processing would be dramatically increased, substantially increasing the cost of the layer
3
switch.
SUMMARY OF THE INVENTION
There is a need for an arrangement that enables a network switch to provide layer
2
switching and layer
3
switching capabilities for 100 Mbps and gigabit links without blocking of the data packets.
There is also a need for an arrangement that enables a network switch to provide layer
2
switching and layer
3
switching capabilities with minimal address table sizes to reduce size and cost of the network switch.
There is also a need for an arrangement that enables a switching module of a network switch to perform layer
3
processing using a shared table having both layer
2
and layer
3
address information and switching information.
These and other needs are attained by the present invention, where a network switch includes a switching module having a shared address table storing address entries for both layer
2
and layer
3
address search operations for layer
2
and layer
3
processing. The shared address table is configured for storing in each address entry two key entries, and two pointer fields, enabling each address entry of the shared address table to logically belong to two separate and independent tables for search purposes.
One aspect of the present invention provides a method in a network switch. The method includes receiving a first layer
2
frame at a network switch port, the first layer
2
frame including a layer
2
address and a layer
3
address. The method also includes searching for the layer
2
address in a table having a plurality of table entries, each table entry configured for storing layer
2
and layer
3
address information and a corresponding switching decision. The method also includes searching for the layer
3
address in the table. The searching of the layer
2
and layer
3
addresses from the same table reduces the overall memory space required, since the same table can be used to share data for layer
2
and layer
3
switching operations. Hence, the same table can be used for multiple independent searches.
Another aspect of the present invention provides an integrated network switch configured for executing layer
3
switching decisions. The integrated network switch includes network switch ports, each configured for receiving a layer
2
frame including a Media Access Control (MAC) address and an Internet Protocol (IP) address. The integrated network switch also includes a switching module having a shared address table configured for storing in each table entry a MAC address field, an IP address field, and a switching information field for the corresponding MAC address field and IP address field. The switching module is configured for searching the shared address table using one of the MAC address and the IP address as search keys for the MAC address field and the IP address field, respectively. Use of the shared address table for both MAC address searching and IP address searching eliminates the necessity for duplicating switching information in separate address tables. Hence, each table entry within the shared address table can store all relevant information necessary for performing layer

Affiliated with

Also associated with

Rating

Multiple key lookup arrangement for a shared switching logic... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiple key lookup arrangement for a shared switching logic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple key lookup arrangement for a shared switching logic... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3349395