“A method of managing forwarding database for efficient forwarding of data packets in a multi-port switch”

The following specification particularly describes the invention and the manner in which it is to be performed.

Field of the Invention

The invention relates generally to database management, and more particularly to management of frame forwarding information in switches.

Background of the Invention

In communications systems, Local Area Networks (LANs) provide communication between a limited numbers of stations located within a limited geography. A single LAN is known as a LAN segment, and a group of LANs joined together by one or more bridges or routers is known as an extended LAN. A typical LAN segment may connect hundreds of stations over a distance of several kilometers. A bridge or router may be used to connect multiple LAN segments, providing communication between a larger numbers of stations over a larger area, and preventing excessive local traffic from degrading overall network performance.

The bridge or router monitors the traffic on all the LAN segments to which it is attached, and determines a destination segment (or segments) for each particular frame. To make this determination, the addressing information in the frame is used to locate forwarding information in a forwarding database.

The forwarding information for a specific address is contained in the forwarding entry for that address. Each forwarding entry contains an address field and a forwarding information field. The forwarding information field contains forwarding information for frames containing the address found in the address field.

Add entry and delete entry operations are performed to update the forwarding database as stations are added to and removed from the LAN segments attached to the bridge or router. In many cases, the system manager requests add or delete entry operations through the user interface to the bridge or router.

Add entry operations may also be automatically issued by a learning process within the bridge or router. For example, when a frame is received on LAN segment S, having a station address A in its source address field, and there is no existing forwarding entry with address field equal to A in the forwarding database, a new forwarding entry is added to the forwarding database. The new forwarding entry has an address field equal to A, and forwarding information field indicating that frames received with destination address equal to A should be forwarded onto segment S. In this way, forwarding entries for new stations on the network are added without system manager intervention.

Forwarding entries may also be automatically deleted by an entry aging process within the bridge or router. For example, when a predetermined time period passes where no frame is received with source address equal to A, the aging process may delete the forwarding entry with address field equal to A. In this way, forwarding entries for stations that have been removed from the network are deleted without system manager intervention.

In known bridges, add entry and delete entry operations maintain the forwarding database as an ordered list, sorted on the basis of the address field of the forwarding entries. In a busy network may have from many thousands to a few million network elements. If we use Layer 2 switches to connect these network elements, the switch maintains a database (i.e. FDB) where the information of network elements is stored identified by their MAC addresses. For real time switching of packets, the switch has to fetch information from the FDB at a very high rate. Switches that support high capacity switching use Content Addressable Memories (CAM). However, CAM based implementations add significant cost in terms of number of transistors. CAMs require up to a factor of 100 more transistors than non-CAM based implementations. For cost sensitive applications, therefore, a CAM solution is not practical.

For these reasons and others, a new forwarding database management system and method is required, which reduces the time during which the forwarding database is in transition during switching operations and which also uses a minimum amount of shared resources. Moreover, the new forwarding database management system must be economical, and not rely on costly CAM technology to store the forwarding database.

Summary of the Invention

The following presents a simplified summary of one or more embodiments in order to provide a basic understanding of such embodiments. This summary is not an extensive overview of all contemplated embodiments, and is intended to neither identify key or critical elements of all embodiments nor delineate the scope of any or all embodiments. Its sole purpose is to present some concepts of one or more embodiments in a simplified form as a prelude to the more detailed description that is presented later.

In accordance with one aspect of the present invention is a method of managing forwarding database for efficient forwarding of data packets in a multi-port switch, the method comprising: constructing a data structure by assigning vendor IDs a ‘m’ bit code for the 2m vendor’s equipment, wherein the vendor IDs is a first 24 bit MAC address of the equipment, maintaining the forwarding database using the ‘m’ bit code i.e. Vendor Code and the second 24 bit MAC address of the equipment i.e. device IDs, adding a vendor specific offset to Device ID in order to segregate the overlapping range of the MAC addresses which are common in two or more Vendor’s equipment and fetching the address of the location of the MAC address information using the offset, vendor code and the device IDs.

In another aspect of the present invention is a system of managing forwarding database for efficient forwarding of data packets in a multi-port switch, the system comprising: a processor and a memory operably connected with the processor and having encoded thereon an overlay application, the overlay application executable by the processor to: constructing a data structure by assigning vendor IDs a ‘m’ bit code for the 2m vendor’s equipment, wherein the vendor IDs is a first 24 bit MAC address of the equipment, maintaining the forwarding database using the ‘m’ bit code i.e. Vendor Code and the second 24 bit MAC address of the equipment i.e. device IDs, adding a vendor specific offset to Device ID in order to segregate the overlapping range of the MAC addresses which are common in two or more Vendor’s equipment and fetching the address of the location of the MAC address information using the offset, vendor code and the device IDs.

The foregoing has outlined rather broadly the features and technical advantages of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features and advantages of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that they may readily use the conception and the specific embodiment disclosed as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.

Before undertaking the detailed description of the invention below, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document: the terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation; the term “or,” is inclusive, meaning and/or; the phrases “associated with” and “associated therewith,” as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like; and the term “controller” means any device, system or part thereof that controls at least one operation, such a device may be implemented in hardware, firmware or software, or some combination of at least two of the same. It should be noted that the functionality associated with any particular controller may be centralized or distributed, whether locally or remotely. Definitions for certain words and phrases are provided throughout this patent document, those of ordinary skill in the art should understand that in many, if not most instances, such definitions apply to prior, as well as future uses of such defined words and phrases.

Brief description of the drawings

For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, wherein like numbers designate like objects, and in which:

Figure 1 shows a table of forwarding database for efficient forwarding of data packets in a multi-port switch according to one embodiment of the present invention.

Figure 2 shows a flowchart of a method of managing forwarding database for efficient forwarding of data packets in a multi-port switch according to one embodiment of the present invention.

Figure 3 depicts a high-level block diagram of a computer suitable for use in performing the functions described herein.

Persons skilled in the art will appreciate that elements in the figures are illustrated for simplicity and clarity and may have not been drawn to scale. For example, the dimensions of some of the elements in the figure may be exaggerated relative to other elements to help to improve understanding of various exemplary embodiments of the present disclosure.

Throughout the drawings, it should be noted that like reference numbers are used to depict the same or similar elements, features, and structures.

Detail description of the Invention

In the following description, for purposes of explanation and not limitation, specific details are set forth such as particular architectures, interfaces, techniques, etc. in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced in other embodiments that depart from these specific details. That is, those skilled in the art will be able to devise various arrangements which, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope. In some instances, detailed descriptions of well-known devices, circuits, and methods are omitted so as not to obscure the description of the present invention with unnecessary detail. All statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure.

Thus, for example, it will be appreciated by those skilled in the art that block diagrams herein can represent conceptual views of illustrative circuitry embodying the principles of the technology. Similarly, it will be appreciated that any flow charts, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.

The functions of the various elements including functional blocks labeled or described as "computer", "processor" or "controller" may be provided through the use of dedicated hardware as well as hardware capable of executing software in the form of coded instructions stored on computer readable medium. A computer is generally understood to comprise one or more processors, and the terms computer and processor may be employed interchangeably herein. When provided by a computer or processor, the functions may be provided by a single dedicated computer or processor, by a single shared computer or processor, or by a plurality of individual computers or processors, some of which may be shared or distributed. Such functions are to be understood as being computer-implemented and thus machine-implemented. Moreover, use of the term "processor" or "controller" shall also be construed to refer to other hardware capable of performing such functions and/or executing software, and may include, without limitation, digital signal processor (DSP) hardware, reduced instruction set processor, hardware (e.g., digital or analog) circuitry, and (where appropriate) state machines capable of performing such functions.

Figure 1 shows a table of forwarding database 100 (Table) for efficient forwarding of data packets in a multi-port switch according to one embodiment of the present invention. In an example embodiment, a network may have from many thousands to a few million network elements. Layer 2 switches to connect these network elements, the switch maintain a database called Forwarding Database (FDB) where the information of network elements is stored identified by their MAC addresses. For real time switching of packets, the switch has to fetch information from FDB at a very high rate. The forwarding database includes a vendor ID, vendor Code, vendor Offset etc. The MAC address of a device has two parts i.e. (1) 24 bit Vendor ID and (2) 24 bit Device ID. In a customer network the number of vendors will be limited, due to same not all 24 bits are necessary. Assuming that the network is expected to have at the most 2m vendor’s equipment, assigning all Vendor IDs a ‘m’ bit code called Vendor Code and the same is used for maintaining the FDB. Further, FDB having the column of Vendor Offset which is used to segregate the overlapping range of the MAC addresses which are common in two or more Vendor’s equipment.

Figure 2 shows a flowchart of a method 200 of managing forwarding database for efficient forwarding of data packets in a multi-port switch according to one embodiment of the present invention.

At step 210, the method constructs a data structure by assigning vendor IDs a ‘m’ bit code for the 2m vendor’s equipment. The vendor IDs is a first 24 bit MAC address of the equipment. The constructing of data structures includes constructing an order data structure and storing a bit pattern indicative of the order data structure in the forwarding database.

At step 220, the method maintains the forwarding database using the ‘m’ bit code i.e. Vendor Code and the second 24 bit MAC address of the equipment i.e. device IDs. The maintaining of the forwarding database may be or may include Random Access Memory (RAM).

At step 230, the method adds a vendor specific offset to Device ID in order to segregate the overlapping range of the MAC addresses which are common in two or more Vendor’s equipment. Further, the forwarding database has a shorter access time to locate the MAC address. Furthermore, the forwarding database maintained for 2n locations using right most ‘n’ bits of MAC address added to the vendor offset, and wherein the m bit vendor ID and ’24-n’ left most bits of device id along with the learned port and learned time as data stored in the respective memory location.

At step 240, the method fetches the address of the location of the MAC address information using the offset, vendor code and the device IDs. To make the fetch operation fast, the method use device ID to generate the address of the location of the MAC address’ information in the RAM. Further, the method checks, if the size of FDB is to be limited to 2n entries, the method uses up to ‘n’ least significant bits of device ID and add/subtract the Vendor Offset. The result may be used to locate the information of the MAC address in the FDB. At the generated address in place of MAC address, the Vendor Code and the remaining (24-n) bits of the device ID are to be stored.

Using only 24-n+m bits in the memory per entry in place of 48 bits saves memory and triggers the reduction of cost. Moreover, by assigning dedicated RAM space for every vendor’s equipment to make fetch operation fast without using Content Addressable Memory. By reducing the memory space, the operation using the present method is faster. In addition, the method keeps some memory space for the MAC addresses which won’t be able to find place in the table to avoid duplicate entries. In case of FDB miss, these spaces will be checked for the MAC entry.

As used herein, the term “determining” encompasses a wide variety of actions. For example, “determining” may include calculating, computing, processing, deriving, investigating, looking up (e.g., looking up in a table, a database or another data structure), ascertaining and the like. Also, “determining” may include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory) and the like. Also, “determining” may include resolving, selecting, choosing, establishing and the like.

Information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals and the like that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles or any combination thereof.

The various illustrative logical blocks, modules and circuits described in connection with the present disclosure may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array signal (FPGA) or other programmable logic device (PLD), discrete gate or transistor logic, discrete hardware components or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any commercially available processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method or algorithm described in connection with the present disclosure may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module (i.e., the code, instructions, etc.) may reside in any form of storage medium that is known in the art. Some examples of storage media that may be used include random access memory (RAM), read only memory (ROM), flash memory, EPROM memory, EEPROM memory, registers, a hard disk, a removable disk, a CD-ROM and so forth. A software module may comprise a single instruction or code, or many instructions or strings/sets of code, and may be distributed over several different code segments or instruction sets, among different programs, and across multiple storage media. A storage medium may be coupled to a processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor.

The methods disclosed herein comprise one or more steps or actions for achieving the described method. The method steps and/or actions may be interchanged with one another without departing from the scope of the claims. In other words, unless a specific order of steps or actions is specified, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims.

FIG. 3 depicts a high-level block diagram of a computer suitable for use in performing functions described herein. As depicted in FIG. 3, computer 300 includes a processor element 302 (e.g., a central processing unit (CPU) and/or other suitable processor(s)), a memory 304 (e.g., random access memory (RAM), read only memory (ROM), and the like), a cooperating module/process 305, and various input/output devices 306 (e.g., a user input device (such as a keyboard, a keypad, a mouse, and the like), a user output device (such as a display, a speaker, and the like), an input port, an output port, a receiver, a transmitter, and storage devices (e.g., a tape drive, a floppy drive, a hard disk drive, a compact disk drive, and the like)).

It will be appreciated that the functions depicted and described herein may be implemented in software and/or hardware, e.g., using a general purpose computer, one or more application specific integrated circuits (ASIC), and/or any other hardware equivalents. In one embodiment, the cooperating process 305 can be loaded into memory 304 and executed by processor 302 to implement the functions as discussed herein. Thus, cooperating process 305 (including associated data structures) can be stored on a computer readable storage medium, e.g., RAM memory, magnetic or optical drive or diskette, and the like.

It will be appreciated that computer 300 depicted in FIG. 3 provides a general architecture and functionality suitable for implementing functional elements described herein and/or portions of functional elements described herein. For example, the computer 300 provides a general architecture and functionality suitable for implementing one or more of ESs , MS , BEBs , BCBs , and the like.

It is contemplated that some of the steps discussed herein as software methods may be implemented within hardware, for example, as circuitry that cooperates with the processor to perform various method steps. Portions of the functions/elements described herein may be implemented as a computer program product wherein computer instructions, when processed by a computer, adapt the operation of the computer such that the methods and/or techniques described herein are invoked or otherwise provided. Instructions for invoking the inventive methods may be stored in fixed or removable media, transmitted via a data stream in a broadcast or other signal bearing medium, and/or stored within a memory within a computing device operating according to the instructions.

Although various embodiments which incorporate the teachings of the present invention have been shown and described in detail herein, those skilled in the art can readily devise many other varied embodiments that still incorporate these teachings.

We Claim:

1. A method of managing forwarding database for efficient forwarding of data packets in a multi-port switch, the method comprising:

constructing a data structure by assigning vendor IDs a ‘m’ bit code for the 2m vendor’s equipment, wherein the vendor IDs is a first 24 bit MAC address of the equipment;

maintaining the forwarding database using the ‘m’ bit code i.e. Vendor Code and the second 24 bit MAC address of the equipment i.e. device IDs;

adding a vendor specific offset to Device ID in order to segregate the overlapping range of the MAC addresses which are common in two or more Vendor’s equipment; and

fetching the address of the location of the MAC address information using the offset, vendor code and the device IDs.

2. The method of claim 1, wherein the step of maintaining the forwarding database in a Random Access Memory (RAM).

3. The method of claim 1, wherein constructing a data structure includes constructing an order data structure and storing a bit pattern indicative of the order data structure in the forwarding database.

4. The method of claim 1, wherein the forwarding database has a shorter access time to locate the MAC address.

5. The method of claim 1, wherein the forwarding database is maintained for 2n locations using right most ‘n’ bits of MAC address added to the vendor offset, and wherein the m bit vendor ID and ’24-n’ left most bits of device id along with the learned port and learned time as data stored in the respective memory location.

6. A system of managing forwarding database for efficient forwarding of data packets in a multi-port switch, the system comprising:

a processor; and

a memory operably connected with the processor and having encoded thereon an overlay application, the overlay application executable by the processor to:

constructing a data structure by assigning vendor IDs a ‘m’ bit code for the 2m vendor’s equipment, wherein the vendor IDs is a first 24 bit MAC address of the equipment;

maintaining the forwarding database using the ‘m’ bit code i.e. Vendor Code and the second 24 bit MAC address of the equipment i.e. device IDs;

adding a vendor specific offset to Device ID in order to segregate the overlapping range of the MAC addresses which are common in two or more Vendor’s equipment; and

fetching the address of the location of the MAC address information using the offset, vendor code and the device IDs.