Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-04-20
2001-11-06
Ngo, Ricky (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S421000, C700S052000, C709S223000
Reexamination Certificate
active
06314106
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data communication switching, and more particularly to receive processing in data communication switching architectures of the type which switch packets over dedicated transmission lines between a plurality of switching controllers.
Local area network (LAN) switches generally perform a switching function on an internal backplane operative between switching controllers supporting external network devices. Such switching has typically been accomplished by configuring the backplane as a shared packet bus and granting the switching controllers having packets for transmission control of the backplane in time-multiplexed fashion. A conventional LAN switch backplane is illustrated in FIG.
1
. LAN switch
10
includes switching controllers
110
,
120
,
130
,
140
performing a switching function by transmitting and receiving packets over shared packet bus
150
. Time-multiplexing is known to have been accomplished in such conventional LAN switches several ways. One way is assigning the controllers different clock cycles within a repetitive timing cycle and granting control of the bus to the controllers round-robin in accordance with their assigned clock cycles. Another way involves conducting a priority-based arbitration among the controllers having packets for transmission and granting control of the bus to the controller which “wins” the arbitration. Regardless of which bus control strategy is favored, reliance on a shared packet bus, and its inherent requirement of time-multiplexing packets for release to guarantee contention-free transmission, has led to congestion at the transmit side of the bus and inefficient use of receive processing resources. For example, unicast packets transmitted across the backplane are destined for a network device supported by only one of the controllers. However, where the backplane is a shared packet bus, all controllers must wait for a unicast packet to clear the backplane before a subsequent packet can be transmitted. This often results in clock cycles in which the receive processing resources of many controllers are idle, even while congestion may be developing at the transmit side of the backplane.
A more efficient approach would obviate the need to time-multiplex data for release across the backplane and, under normal operating conditions, would allow all packets awaiting transmission across the backplane to be forwarded without delay. However, to reap the full benefit of such “on the fly” transmission requires receive processing resources capable of efficiently handling parallel traffic. Otherwise, the conventional problem of underutilization of receive processing resources and transmit side congestion may inadvertently become one of overutilization of receive processing resources and receive side congestion.
SUMMARY OF THE INVENTION
In its most basic feature, the present invention eliminates the inefficiencies of shared bandwidth switch backplanes by implementing a dedicated bandwidth switch backplane having efficient receive processing capable of handling highly parallel traffic. The contemplated switching architecture has a plurality of switching controllers for transmitting and receiving packets across a backplane, with each controller having a transmit interface, a receive interface and filtering logic. The backplane includes a dedicated transmission line for each transmit interface such that all transmit interfaces may simultaneously propagate data bursts to all receive interfaces. Each receive interface includes a dedicated receive port for each transmission line and an output queue. Packets must pass a filtering check and a watermark check before the receive port is allowed to release them to the output queue. Highly efficient algorithms are applied to conduct the checks on the packets in a way which expedites receive processing and avoids contention.
In one aspect of efficient receive processing, a hybrid priority/port-based arbitration algorithm is used to sequence filtering checks on packets. The hybrid algorithm prioritizes and sequences packets according to how soon their receive port would be able to begin delivering them to the output queue in the event the filtering check were allowed to proceed and the filtering and watermark checks were passed; however, the hybrid algorithm assigns all packets for which delivery could not begin within a threshold number of clock cycles the lowest priority and filtering checks are sequenced on such low priority packets according to their receive port.
In another aspect of efficient receive processing, the outcome-dependence of the current packet's watermark check on the queueing decision made on the preceding packet is addressed efficiently by a watermark comparison algorithm which performs preliminary calculations using “projected” output queue write addresses for each possible outcome of the queueing decision on the preceding packet and using the actual outcome, when available, to select from among preliminary calculations.
In another aspect of efficient receive processing, if a packet passes the filtering check but fails the watermark check, a stall condition is triggered to restrict the transmission of additional packets to the packet's receive port until the watermark check is passed.
In another aspect of efficient receive processing, receive ports are operatively divided into one or more full-write receive ports and one or more selective-write receive ports for delivering their packets to the output queue. The full-write receive ports always write data, if available, to the queue on the clock cycles during which they are assigned writing privileges. On the clock cycles during which the selective-write receive ports are assigned writing privileges, data is read from the queue, unless the selective-write receive ports have indicated they wish to write to the queue, in which case the selective-write receive ports write to the queue. By configuring relatively low-traffic ports as selective-write ports, dequeueing may accomplished during unutilized “write” clock cycles, obviating the need to designate “read only” clock cycles.
These and other aspects of the present invention can be understood by reference to the following detailed description, taken in conjunction with the accompanying drawings which are briefly described below. Of course, the actual scope of the invention is defined by the appended claims.
REFERENCES:
patent: 5127000 (1992-06-01), Henrion
patent: 5521923 (1996-05-01), Willmann et al.
patent: 5914953 (1999-06-01), Krause et al.
patent: 6026075 (2000-02-01), Linville et al.
patent: 6084856 (2000-07-01), Simmons et al.
patent: 6092108 (2000-07-01), DiPlacido
patent: 6115387 (2000-09-01), Egbert et al.
patent: 6141323 (2000-10-01), Rusu
“exponeNT Switch Fabric Whitepaper,” May 1998, pp. 1-5, Berkeley Networks, Inc.
Haywood Christopher
King Wai
Stone Geoffrey C.
Alcatel Internetworking, Inc.
Christie Parker & Hale LLP
Ngo Ricky
Nguyen Steven
LandOfFree
Receive processing for dedicated bandwidth data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Receive processing for dedicated bandwidth data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Receive processing for dedicated bandwidth data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2584031