Network switching device with disparate database formats

• US 6,678,269 B1
• Filed: 10/05/1998
• Issued: 01/13/2004
• Est. Priority Date: 10/05/1998
• Status: Expired due to Fees

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Ganesh, Jayasenan Sundara, Cathey, James E., Michels, Timothy Scott, Helbling, Michael Dale
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Nguyen, Brian
• Application Number:
  US09/166,620
• Time in Patent Office: 1,926 Days
• Field of Search: 370/389, 370/392, 370/395.1, 370/396, 370/397, 370/400, 370/401, 370/412, 370/428, 370/429, 370/352, 370/368, 370/465, 370/469, 370/471, 370/395.31, 370/395.32, 370/470, 709/238, 709/230
• US Class Current: 370/389
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]

Abstract

A switching device for forwarding network traffic to a desired destination on a network, such as a telephone or computer network. The switching device includes multiple ports and uses a lookup table containing lookup keys to determine which port to forward network traffic over. The lookup table includes disparate forwarding databases that contain database entries in different formats. For example, one forwarding databases may relate to MAC addresses, while another database relates to IP addresses. The disparate databases are maintained in a single lookup table and a binary search engine searches the table without regard to the database format. Like-kind database entries are grouped within the lookup table and the lookup table is maintained in sorted order by prepending format identification bits to the lookup keys. Memory availability for the disparate databases can be dynamically changed allowing customization for a particular user application. Consequently, memory can be efficiently used and reallocated if needed.

Claims

1. In a switching device having a plurality of ports, each port having a plurality of forwarding databases wherein each forwarding database has an associated database format compatible with at least one format of a network frame, a method of transmitting the network frame within a port comprising the steps of:

(a) receiving the network frame wherein the network frame has a plurality of characteristics comprising a destination address and a format property;

(b) determining a partial search key from the destination address of the network frame;

(c) determining one or more format identification bits from the format property of the network frame wherein the determined one or more format identification bits are associable with one of the plurality of forwarding databases; and

(d) generating a full search key by concatenating, to the partial search key, the one or more format identification bits as the most significant bits of a fill search key;

(e) identifying a forwarding database associated with the most significant bits of the full search key;

(f) searching a plurality of forwarding information entries, according to the full search key, within the identified forwarding database;

(g) determining, by the search engine, at least one destination port from the searched forwarding information entries;

(h) storing the network frame within a switch fabric; and

(i) transmitting the network frame from the switch fabric via the at least one determined port.

2. The method of claim 1 further comprising the steps, preceding the transmitting step, of establishing a connection in the switch fabric and communicating a network frame send signal wherein the switch fabric is a cross-bar switch.

3. The method of claim 1 wherein the step of storing further comprises the steps of designating a network frame storage location within the switch fabric, storing the network frame at the designated location within the switch fabric, and transmitting, by the switch fabric, the network frame location within the switch fabric to the plurality of ports.

4. The method of claim 1 wherein the plurality of forwarding databases is stored in dynamically allocated memory of a memory device.

5. The method of claim 1 wherein the plurality of forwarding databases is contained within a single memory device.

6. The method of claim 1 wherein the at least one destination port determined by the search engine further includes a null destination.

7. The method of claim 1 comprising the step, preceding the transmitting step, of communicating the determined port to the remaining at least one destination port via the switch fabric.

8. The method of claim 1 wherein at least one forwarding database comprises forwarding entries supporting an Internet Protocol version 4(IPv4) protocol format.

9. The method of claim 1 wherein at least one forwarding database comprises forwarding entries supporting an Internet protocol version 6 (IPv6) protocol fromat.

10. The method of claim 1 wherein at least one forwarding database comprises forwarding entries supporting a Media Access Control (MAC) format.

11. A method of routing a network frame from a switching device comprising a plurality of ports and a plurality of forwarding databases, the method comprising the steps of:

(a) receiving a network frame comprising a network destination address and a network frame protocol;

(b) extracting one or more format identification bits from the network frame protocol;

(c) generating a search key from the network destination address of the network frame;

(d) selecting a forwarding database from the plurality of forwarding databases using said one or more format identification bits, wherein the selected forwarding database comprises forwarding information entries characterized by a common network frame protocol, the network frame protocol of the forwarding information entries of each forwarding database being different than the network frame protocol of the forwarding information entries of every other forwarding database;

(e) searching the selected forwarding database with the search key;

(f) identifying at least one destination port of the plurality of ports from the forwarding information entries of the selected forwarding database; and

(g) transmitting the network frame towards the at least one destination port;

wherein the search for the destination port is limited to one or more contiguous forwarding information entries within the selected forwarding database of the plurality of forwarding databases.

12. The method of claim 11, wherein one or more of the plurality of forwarding databases comprises forwarding information entries characterized by a network frame protocol selected from the group consisting of:

IPv4, IPv6, IPX, and Appletalk.

13. The method of claim 12, wherein the forwarding information entries of a first forwarding database comprise IPv4 destination addresses and an associated port identifier, and the forwarding information entries of a second forwarding database comprise IPv6 destination addresses and an associated port identifier.

14. The method of claim 11, wherein the plurality of forwarding databases are sequentially ordered within a single memory.

15. The method of claim 14, wherein the step of generating a search key includes the step of prepending the one or more format identification bits from the network frame protocol to the partial search key.

16. The method of claim 15, wherein the step of selecting a forwarding database from the plurality of forwarding databases occurs automatically due to the presence of the one or more format identification bits.