Receive processing for dedicated bandwidth data communication switch backplane
First Claim
1. In a data switching system having a plurality of switching controllers for exchanging data units over a backplane, each controller having an interface for transmitting data on the backplane and an interface having a plurality of ports for receiving data off the backplane in parallel from all transmitting interfaces, wherein each port is assigned a different clock cycle within a repetitive timing cycle for initiating the release of a data unit to a queue, and wherein each data unit must pass a filtering check and a watermark check to receive queueing clearance, a method for conducting receive processing, comprising:
- sequencing the data units for conducting a filtering check;
conducting the filtering check on the data units in accordance with the sequence;
conducting a watermark check on the data units;
filtering the data units which fail the filtering check;
delaying the data units which pass the filtering check and fail the watermark check, until the watermark check is passed; and
queueing the data units which pass the filtering check and the watermark check.
1 Assignment
0 Petitions
Accused Products
Abstract
A dedicated bandwidth switch backplane has efficient receive processing capable of handling highly parallel traffic. Packets must pass a filtering check and a watermark check before the receive port is allowed to release them to a queue. Highly efficient algorithms are applied to conduct the checks on the packets in a way which expedites receive processing and avoids contention. A hybrid priority/port-based arbitration algorithm is used to sequence filtering checks on pending packets. A watermark comparison algorithm performs preliminary calculations on the current packet using “projected” output queue write addresses for each possible outcome of the queueing decision on the preceding packet and using the actual outcome to select from among preliminary calculations to efficiently address the outcome-dependence of the current packet'"'"'s watermark check on the queueing decision made on the preceding packet. Receive ports are operatively divided into full-write receive ports and selective-write receive ports for delivering their packets to the output queue. On the clock cycles where the selective-write receive port is assigned writing privileges, data is read from the queue, unless the selective-write receive port has indicated it wishes to write to the queue, in which case the selective-write receive port writes to the queue. The full-write receive ports always write data, if available, to the queue on the clock cycles where they are assigned writing privileges.
107 Citations
20 Claims
-
1. In a data switching system having a plurality of switching controllers for exchanging data units over a backplane, each controller having an interface for transmitting data on the backplane and an interface having a plurality of ports for receiving data off the backplane in parallel from all transmitting interfaces, wherein each port is assigned a different clock cycle within a repetitive timing cycle for initiating the release of a data unit to a queue, and wherein each data unit must pass a filtering check and a watermark check to receive queueing clearance, a method for conducting receive processing, comprising:
-
sequencing the data units for conducting a filtering check;
conducting the filtering check on the data units in accordance with the sequence;
conducting a watermark check on the data units;
filtering the data units which fail the filtering check;
delaying the data units which pass the filtering check and fail the watermark check, until the watermark check is passed; and
queueing the data units which pass the filtering check and the watermark check. - View Dependent Claims (2, 3, 4)
-
-
5. In a data queueing system including a plurality of ports each having a data unit for release to a queue and each assigned a different clock cycle within a repetitive timing cycle for initiating the release of the data unit to the queue, and wherein each data unit must pass a filtering check as a condition for receiving queueing clearance, a method for sequencing data units received on the ports for the filtering check, comprising:
-
(a) determining the port on which the data units were received;
(b) determining the current clock cycle within a repetitive timing cycle;
(c) from the determinations in (a) and (b), assigning a priority to each data unit as a function of the number of clock cycles the data unit'"'"'s port would have to wait before initiating the release of the data unit in the event queueing clearance for the data unit were received; and
(d) sequencing the data units in accordance with their assigned priorities. - View Dependent Claims (6, 7, 8)
-
-
9. In a data queueing system in which data units must pass a watermark check as a condition for receiving queueing clearance, a method for conducting the watermark check, comprising:
-
determining the size of the data unit for the current watermark check;
calculating a, where a is the sum of a minimum projected write address and the size of the current data unit;
calculating b, where b is the sum of a maximum projected write address and the size of the current data unit;
calculating c, where c is the sum of a watermark and the current read address;
determining if the data unit for the preceding watermark check received queueing clearance;
if the preceding data unit received queueing clearance and b≦
c, replacing the minimum projected write address with the maximum projected write address, passing the current data unit and replacing the maximum projected write address with b;
if the preceding data unit received queueing clearance b>
c, replacing the minimum projected write address with the maximum projected write address and failing the current data unit;
if the preceding data unit did not receive queueing clearance and a≦
c, replacing the maximum projected write address with a and passing the current data unit; and
if the preceding data unit did not receive queueing clearance and a>
c, failing the current data unit. - View Dependent Claims (10, 11, 12, 13, 14)
-
-
15. In a data queueing system having a plurality of ports which include a first group and a second group, wherein each group has at least one port and no port within the first group is within the second group, a method of queueing and dequeueing data within a repetitive timing cycle, comprising:
-
for each port within the first group, on each of the clock cycles within the repetitive timing cycle on which the port has writing privileges, determining whether the port has data for release and, if the port has data for release, releasing data from the port to the queue, and otherwise reading data from the queue; and
for each port within the second group, on each of the clock cycles within the repetitive timing cycle on which the port has writing privileges, if the port has data for release, releasing data from the port to the queue. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification
-
- Resources
-
Current AssigneeAlcatel SA (Nokia Corporation)
-
Original AssigneeAlcatel SA (Nokia Corporation)
-
InventorsStone, Geoffrey C., Haywood, Christopher, King, Wai
-
Granted Patent
-
Time in Patent OfficeDays
-
Field of Search
-
US Class Current370/412
-
CPC Class CodesH04L 45/7453 using hashingH04L 49/101 using crossbar or matrixH04L 49/254 Centralised controller, i.e...H04L 49/3018 Input queuingH04L 49/351 for local area network [LAN...
