RE40467 Method and apparatus for managing the flow of data within a switching device.
ABSTRACT – A method and apparatus for managing the flow of data within a switching device is provided. The switching device includes network interface cards connected to a common backplane. Each interface card is configured to support the maximum transfer rate of the backplane by maintaining a “pending” queue to track data that has been received but for which the appropriate routing destination has not yet been determined. The switching device includes a switch controller that maintains a central card/port-to-address table. When an interface card receives data with a destination address that is not known to the interface card, the interface card performs a direct memory access over a bus that is separate from the backplane to read routing data directly from the central table in the switch controller. Each interface card builds and maintains a routing information table in its own local memory that only includes a routing information for the destination addresses that the interface card is most likely to receive.
FIELD OF THE INVENTION
The present invention relates to controlling data flow within a switch, and more specifically, to information distribution and buffering mechanisms for controlling data flow between multiple network interfaces over a common backplane.
BACKGROUND OF THE INVENTION
Computer networks consist of a plurality of network devices connected in a way that allows the network devices to communicate with each other. Special purpose computer components, such as hubs, routers, bridges and switches, have been developed to facilitate the process of transporting information between network devices.
FIG. 1 is a block diagram of a typical switching device 100. Switching device 100contains slots for holding network interface cards 102, 104 and 106 and a backplane 108 for transporting information between the various interface cards 102, 104 and 106. The interface cards 102, 104 and 106 have ports that are connected to network devices that are located external to switching device 100. For example, port 110 of interface card 104 is connected to a network device 112. Port 114 of network interface card 106 is connected to network devices 116, 118and 120.
Before switching device 100 can accurately route data between devices connected to different ports of different cards, switching device 100 must know which devices are connected to which ports. Switching device 100 obtains this knowledge by inspecting the source addresses associated with incoming data.
Typically, incoming data is encapsulated in a structure (e.g. a packet or a cell) that contains both a destination address and a source address. The destination address identifies the device or group of devices to which the data is to be sent. The source address identifies the device from which the data is sent. For the purposes of explanation, the term “cell” shall be used herein to refer to any data structure that contains data and source/destination information, including but not limited to Ethernet packets, ATM cells, and token ring packets.
When an interface card receives a cell that specifies a previously unknown source address, the interface card stores a port-to-address entry in a locally-maintained table. The interface card transmits a message to a central switch controller 122 to notify the switch controller 122 that a device with a specified address is connected to the particular port of the network interface card. Based on the information contained in this message, the switch controller 122 adds a card/port-to-address entry in a centrally-maintained card/port-to-address table. The card/port-to-address entry indicates that the specified port of the interface card that received the cell is connected to a device that has the source address that was specified in the cell. When all interface cards on the switching device 100 report to the switch controller 122 the addresses of the devices to which they are connected to this fashion, the switch controller 122 is able to create and maintain a relatively complete table that maps addresses to ports on controller cards.
As mentioned above, switching device 100 allows network devices connected to the ports of one interface card to communicate with network devices connected to the ports of other interface cards by allowing the network interface cards to transmit information to each other over backplane 108. For example, network device 112 can communicate with network device 116 by transmitting data to interface card 104 in a cell that identifies network device 116 as the desired destination. For the purposes of explanation, it shall be assumed that the address of network device 116 is ADDRX.
Circuitry on the interface card 104 transmits a message over backplane 108 to the switch controller 122 to indicate that the interface card 104 has received a cell with the destination address ADDRX. Switch controller 122 searches for ADDRX in its card/slot-to-address table to determine where interface card 104 should send the cell. In the present example, the card/slot-to-address table in switch controller 122would contain an entry to indicate that ADDRX is the address of a device connected to port 114 of interface card 106. The switch controller 122 transmits a message containing this information over backplane 108 to interface card 104.
Based on the information contained in the message, interface card 104 routes the cell over the backplane 108 to interface card 106. Interface card 106 receives the cell from backplane 108. Upon receiving the cell, interface card 106 transmits a message over backplane 108 to switch controller 122 to inform switch controller 122 that interface card 106 has received a message with the destination address ADDRX. Switch controller 122 transmits a message over backplane 108 to interface card 106 to form interface card 106 that address ADDRX is associated with a device connected to port 114 of interface card 106. Based on this information, interface card 106 transmits the cell through port 114 to device 116.
One significant disadvantage of routing cells through switching device 100 in the manner described above is that the messages that are sent between the switch controller 122 and the various interface cards to determine the appropriate routing paths are sent over backplane 108. Consequently, less bandwidth is available for transmitting the actual cells between the interface cards.
A second disadvantage to the switching scheme described above is the amount of time that elapses between when an interface card receives a cell and the time at which the interface card knows where to send the cell. During this time interval, the interface card may receive a whole series of cells for the same destination. To prevent data loss, the interface card would have to include a much larger buffer than would otherwise be required if the interface card could immediately retransmit the cell.
In an alternate approach, the interface card does not wait for the reply from the switch controller 122. Rather, the interface card simply transmits the cells that it does not know how to route to the switch controller 122. The switch controller 122retransmits the cells to the appropriate destination based on information contained in its table. The switch controller also transmits the appropriate routing information to the interface card so that the interface card will be able to route cells with that destination address in the future.
One disadvantage of this approach is that the same cells are routed over the backplane twice, increasing the amount of traffic on the backplane. A second disadvantage of this approach is that it places a heavy burden on the switch controller, because at any given time every interface card in the switch could be sending cells for the switch controller to reroute.
A third disadvantage is that cells may arrive at their intended destination out of sequence. For example, an interface card may receive a series of cells 1 . . . N for an unknown destination. Initially, the interface card sends the cells to the switch controller. After the interface card has sent M (where 1<M<N) cells to the switch controller, the interface card receives the reply message from the switch controller that indicates how to route the cells. The interface card will then transmit the remaining cells (M+1) . . . N directly to the appropriate card/port. In this scenario, cell M+1 is likely to arrive at the destination card/port prior to cell M, since cell M is sent to the switch controller first.
In another alternative approach, each interface card within switching device 100can locally store a complete card/port-to-address table. According to this approach, each interface card that detects a new source address will place a message on backplane 108 that indicates the card and slot on which the message with the new source address was received. Each interface card would read the message off the backplane 108 and add the appropriate card/port-to-address entry in its own table. Thus, when an interface card receives a cell, the interface card can quickly determine the appropriate destination for the cell from its own table without having to send or receive messages over the backplane 108. By reducing the messaging traffic over backplane 108, the throughput of switching device 100is increased. By reducing the delay between receipt of a cell and transmission of the cell, the buffer size within each interface card can be reduced.
An approach in which each interface card maintains a complete card/port-to-address table, such as the approach described above, has the disadvantage that the table may become very large. Each card would have to reserve large amounts of memory to store the table, and contain the control circuitry for managing a large table. Further, each interface card will typically only use a relatively small amount of the data stored in the table. For example, interface card 104 will never need to know the addresses of devices connected to interface card 106 that only communicate with other devices connected to interface card 106.
Even when a local card/port-to-address table is used by an interface card to determine how to route a cell, there is some interval between the time at which the cell is received by the interface card and the time at which the cell is transmitted by the interface card. During this interval, the cell must be stored somewhere within the interface card. FIG. 2 illustrates a typical buffer mechanism 200 that may be employed by interface card 104 to store cells during this interval.
Referring to FIG. 2, it illustrates the buffering circuitry of interface card 104 of FIG. 1 in greater detail. Interface card 104 includes a first-in-first-out (FIFO) buffer 202, a buffer control unit 206 and a main buffer 204. FIFO buffer 202 is coupled between backplane 108 and main buffer 204. Buffer control unit 206 is coupled to and controls both FIFO buffer 202 and main buffer 204. In addition to port 110, interface card 104 includes ports 208 and 210. Ports 110, 208 and 210 are coupled to main buffer 204.
The main buffer 204 is used to temporarily store both data cells that are to be transmitted out ports 110, 208 and 210, and data cells that are to be transmitted to backplane 108. The main buffer 204 includes a plurality of cell slots, each of which is capable of storing one cell of data.
Buffer control unit 206 maintains a plurality of queues, including one queue (212, 214 and 216) for each of ports 110, 208, and 210, a queue 220 for backplane 108, and a “free slot” queue 218. Buffer control unit 206 stores pointers to the cell slots of main buffer 204 in the various queues. Specifically, each cell slot within main buffer 204 has a unique pointer. The pointer to each cell slot of main buffer 204 is stored in the queue that corresponds to the destination of the data that is currently stored within the cell slot. For example, if a cell slot currently stores data to be sent on the backplane 108, then the pointer to the cell slot is stored in the queue 220that corresponds to the backplane.
When interface card 104 receives a cell, the interface card 104 must determine the destination of the cell, as described above. Once the destination of the cell has been determined, buffer control unit 206 causes the cell to be stored in main buffer 204 and updates the queues to reflect that the cell is to be sent to the appropriate destination.
Specifically, when a cell is to be sent out a port, the pointer to the cell slot in which the cell resides is placed in the queue associated with the port. When a cell is to be transmitted over the backplane 108, the buffer control unit 206 places the pointer to the cell slot in which the cell resides in the queue 220 associated with the backplane 108.
When a cell of data is transmitted by interface card 104, the cell slot that contained the cell no longer contains data to be transmitted. To indicate that the cell slot is now available to store incoming data, the buffer control unit 206 places the pointer to the cell slot in the free slot queue 218. When storing a cell of data in main buffer 204, the buffer control unit 206 pulls a pointer from the free slot queue 218, and uses the cell slot indicated by the pointer to store the cell of data.
At any given moment all of the other interface cards on backplane 108 may be placing cells on backplane 108 that are destined for devices connected to interface card 104. To process the cells without losing data, interface card 104 must be able to sustain, for at least brief periods of time, a backplane-to-card transfer rate equal to the maximum transfer rate supported by backplane 108 (e.g. 3.2 gigabytes per second).
Typically, buffer control unit 206 determines the appropriate destination for cells at a rate (e.g. 1.2 gigabytes per second) that is slower than the maximum transfer rate of the backplane 108. Therefore, to sustain brief periods in which cells arrive at the high transfer rate of the backplane 108, the information contained on backplane 108 is transferred from the backplane 108 into the high speed FIFO buffer 202 of interface card 104. During the interval in which a cell is stored in FIFO buffer 202, interface card 104 determines the destination of the cell. Once the destination of the cell has been determined, buffer control unit 206 removes the cell from FIFO buffer 202 and stores the cell in the main buffer 204.
The buffering system illustrated in FIG. 2 has the significant disadvantage that high speed FIFO buffers are expensive. Further, every interface card in the switch must have its own of FIFO buffer to support the maximum transfer rate of the backplane. Consequently, the increased cost of high speed FIFO buffers is incurred for every interface card in the switch.
Based on the foregoing, it is clearly desirable to provide a switching device in which the delay between when an interface card receives a cell and the time at which the interface card transmits the cell is reduced. It is further desirable to provide a switching device in which the amount of traffic on the backplane that is used to determine how to route cells is reduced. Further, it is desirable to reduce the size and complexity of tables that are maintained locally in interface cards. In addition, it is desirable to provide a buffering system that allows interface cards to receive data off the backplane at the backplane’s maximum transfer rate without requiring the use of high speed FIFO buffers.
SUMMARY OF THE INVENTION
A method and apparatus for managing the flow of data within a switching device is provided. The switching device includes network interface cards connected to a common backplane. Each interface card is configured to support the maximum transfer rate of the backplane by maintaining a “pending” queue to track data that has been received but for which the appropriate destination has not yet been determined. The switching device includes a switch controller that maintains a central card/port-to-address. When an interface card receives data with a destination address that is not known to the interface card, the interface card performs a direct memory access over a bus that is separate from the backplane to read routing data directly from the central table in the switch controller. Each interface card builds and maintains a routing information table in its own local memory that only includes routing information for the destination addresses that the interface card is most likely to receive.