Multiplex communications – Pathfinding or routing
Reexamination Certificate
2002-03-05
2004-09-07
Coulter, Kenneth R. (Department: 2141)
Multiplex communications
Pathfinding or routing
C370S355000, C370S359000
Reexamination Certificate
active
06788671
ABSTRACT:
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
100
contains 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
,
118
and
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 the 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 in 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
122
would 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 inform 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
122
retransmits 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
100
can 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 ap
Prince Jeffrey
Ryals Randy
Blakely , Sokoloff, Taylor & Zafman LLP
Coulter Kenneth R.
Nortel Networks Limited
LandOfFree
Method and apparatus for managing the flow of data within a... 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 managing the flow of data within a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for managing the flow of data within a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213256