Head of line blocking

Details Head of line blocking Head of line blocking

1999-07-08

2004-12-07

Ton, Dang (Department: 2666)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S428000

Reexamination Certificate

active

06829245

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to network switching communication protocols generally and to prevention of head of line blocking in particular.
BACKGROUND OF THE INVENTION
A network switch creates a network among a plurality of end nodes, such as workstations, and other network switches connected thereto. Each end node is connected to one port of the network. The ports also serve to connect network switches together.
Each end node sends packets of data to the network switch which the switch then routes either to another of the end nodes connected thereto or to a network switch to which the destination end node is connected. In the latter case, the receiving network switch routes the packet to the destination end node.
Each network switch has to temporarily store the packets of data which it receives from the units (end node or network switch) connected to it while the switch determines how, when and through which port to retransmit the packets. Each packet can be transmitted to only one destination address (a “unicast” packet) or to more than one unit (a “multicast” or “broadcast” packet). For multicast and broadcast packets, the switch typically stores the packet only once and transmits multiple copies of the packet to some (multicast) or all (broadcast) of its ports. Once the packet has been transmitted to all of its destinations, it can be removed from the memory or written over.
Reference is now made to
FIG. 1
which schematically illustrates a portion of the data packet transfer process that takes place within the operations of a network switch
10
. Switch
10
comprises a central queuing manager
12
, an output buffer
14
, and a multiplicity of output ports
16
. Switch
10
receives incoming data
18
which it stores until transmission as queued data
24
in output buffer
14
. At the appropriate time, which is generally when the relevant output port
16
in available, switch
10
transfers the queued data
24
out of the relevant output port
16
as outgoing data
26
.
Output buffer
14
is either a pooled buffer which services the entire switch
10
or a plurality of dedicated queues within buffer
14
, one queue per output port
16
. The exemplary switch
10
shown in
FIG. 1
comprises a pooled output buffer
14
and two output ports
16
B and
16
C.
Incoming data
18
comprises data packets
30
,
32
,
34
arid
36
, which are designated for various destination ports
16
. Data
18
is received by manager
12
, which identifies the appropriate destination port
16
of the packets
30
,
32
,
34
, and
36
respectively, and dispatches them to the output buffer
14
. As an example unicast data packets
32
and
36
are designated for port
16
C, unicast data packet
30
is designated for port
16
B and multicast packet
34
is designated for both ports
16
B and
16
C. Output buffer
14
stores the queued data
24
until the relevant port
16
is available, at which point, the outgoing data
26
is transferred to the relevant port
16
.
Occasionally, one of the output ports
16
transfers at a faster pace than the other ports or, alternatively, receives more data then the other ports. For whatever reason, a condition may arise where the data
24
for one of the output ports
16
backs up in the output buffer
14
creating a condition where output buffer
14
is unable to receive more data. Manager
12
is aware of the backup in the output buffer
14
, typically through a fullness sensor (not shown) measuring the fullness of output buffer
14
, and, accordingly, stops receiving incoming data
18
to switch
10
.
All incoming data
18
not received by switch
10
is discarded, regardless of its destination output port
16
. Not only is the incoming data
18
destined for the full output port discarded but the incoming data
18
destined for the available ports are also discarded. This problem is known as “Head of Line Blocking”.
Although switch
10
no longer receives incoming data
18
, it continues to send outgoing data
26
, and thus, clears out the output buffer
14
. Once enough outgoing data
26
has been sent, output buffer
14
empties out and is again able to receive more data
24
. Manager
12
reopens inflow of data
18
to switch
10
.
For example, if port
16
B is backed up, then the output buffer
14
will become full with queued data
24
B, while output port
16
C will still available to transmit. Manager
12
halts the incoming flow of data
18
. All data
18
incoming into switch
12
is halted and discarded, including unicast data packets
32
and
36
and multicast data packet
34
which are designated for the available port
16
C.
SUMMARY OF THE PRESENT INVENTION
It is an object of the present invention to prevent Head of Line Blocking as much as possible.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a network switch which includes a plurality of output ports, at least one input port and a queuing manager. Each output port has a control unit associated therewith. The input port receives incoming data destined for various ones of the output ports. The queuing manager directs the incoming data to their destination output ports. Each control unit includes an output queue, a fullness/emptiness sensor and a head of line (HOL) mask. The output queue stores the incoming data destined for its associated output port. The sensor senses when the output queue reaches a fullness or an emptiness state. The HOL mask is connected to the output of the sensor and blocks inflow of the incoming data to the output queue when the sensor senses the fullness state and for enabling inflow when the sensor senses the emptiness state.
There is also provided. In accordance with a preferred embodiment of the present invention, a control unit for an output port of a network switch as described hereinabove.
Finally, there is provided, a method of controlling flow within a network switch, the method comprising the steps of sensing when an output queue of the network switch reaches a fullness or an emptiness state, blocking queueing of incoming data to the output queue when the fullness state is sensed, discarding of unicast packets destined to the full output port queue, avoiding queuing of multicast packets to said output port queue and enabling queueing when the emptiness state is sensed.


REFERENCES:
patent: 5448559 (1995-09-01), Hayter et al.
patent: 5455820 (1995-10-01), Yamada
patent: 5841722 (1998-11-01), Willenz
patent: 6144640 (2000-11-01), Simpson et al.
patent: 6185214 (2001-02-01), Schwartz et al.
patent: WO 9809471 (1998-03-01), None

Affiliated with

Also associated with

Rating

Head of line blocking does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Head of line blocking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Head of line blocking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3297188