Static and dynamic flow control using virtual input queueing...

Details Static and dynamic flow control using virtual input queueing... Static and dynamic flow control using virtual input queueing...

1999-02-16

2002-09-24

Chin, Wellington (Department: 2664)

Multiplex communications

Data flow congestion prevention or control

C370S371000

Reexamination Certificate

active

06456590

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention relates to flow control in network devices, and more specifically, defines virtual input queueing as a tool to provide systems and methods of static and dynamic flow control in shared memory Ethernet switching devices.
BACKGROUND OF THE INVENTION
Recent advances in computing and network interface technologies and hardware have created an environment in which single Personal Computers (PCs or workstations) are capable of bursting out data at the capacity of a traditional Local Area Network (LAN). These advances, when coupled with the growing interest in bandwidth-intensive multimedia applications, have served to increase the prominence of new high-speed switching technologies like Asynchronous Transfer Mode (ATM) and, more recently, fully-duplex, switched Ethernet.
An Ethernet switch is a frame switch that handles variable length Ethernet frames. The Ethernet switch is fully duplexed and makes forwarding decisions based on destination addresses contained within Ethernet frame headers. Existing standards provide for up to 100 Mbps link speeds, and an Institute of Electrical and Electronic Engineers Working Group (the IEEE 8.2.3 z Working Group) has specified a standard for 1 Gbps operation (known as Gigabit Ethernet).
Fully duplexed Ethernet switches can be divided into two broad categories based on their memory architecture, which will utilize either an input queued switch or an output queued switch. Most output queued switches are implemented by using a shared memory pool to host output queues. This architecture is referred as shared memory switch architecture.
FIG. 1
illustrates a block diagram of an input queue-based Ethernet switch
10
having 1-N input lines
22
connected to corresponding 1-N input ports
20
which electrically connect the 1-N input lines
22
with the Ethernet switch
10
. A data frame can flow through any one of the 1-N input ports
20
and into the Ethernet switch
10
, and simultaneously enter the Ethernet switch architecture 1-N receive channels
40
which couples each 1-N input port
20
to an input queue
70
. The frames are then transferred to and stored by an input queue
70
in the order received. There is an input queue
70
assigned to each input port (for a total of N input queues).
1-N transmit channels
60
are in electrical connection with each of the 1-N input queues
70
, and each of the 1-N transmit channels is in communication with an 1-N output port. Thus, each input queue
70
stores the received frames on an input-port basis until the output port can send the frames downstream, whereby the frames are transmitted to the appropriate 1-N transmit channel
60
, such that each 1-N transmit channel
60
communicate with a corresponding 1-N output port
30
. 1-N output lines
32
are connected to the 1-N output ports
30
, and the 1-N lines
32
provide the path for the data frames to travel from the appropriate 1-N transmit channels
60
to the correct downstream ports. Input queue-based Ethernet switches can monitor and direct the flow of traffic on a port-by-port basis. However, input queue-based Ethernet switches achieve only 58% of the throughput of shared memory Ethernet switches due to limitation of the head-of-line blocking.
FIG. 2
is a block diagram of a shared memory Ethernet switch
10
having 1-N input lines
22
connected to corresponding 1-N input ports
20
which electrically connect the 1-N input lines
22
with the Ethernet switch
10
. A data frame can flow through the 1-N input ports
20
into the Ethernet switch
10
and simultaneously enter the switch architecture at 1-N receive channels
40
, which couple each of the 1-N input ports
20
to a memory
50
, for temporarily storing frames, and for buffering the frames into output queues (not shown). The memory
50
also communicates with the 1-N transmit channels
60
. 1-N output lines
32
are coupled between 1-N output ports
30
and the 1-N transmit channels
60
, and transfer each data frame from the appropriate transmit channel
60
to various downstream ports. While achieving higher throughput than the input queue-based Ethernet switch, there is no mechanism in a shared memory Ethernet switch that allows for port-based flow control.
In addition, existing shared Carrier Sense Multiple Access/Collision Detection (CSMA/CD) networks are capable of gracefully handling periods of temporary congestion in bridges and routers through the use of collisions and random back-off mechanisms. However, in a point-to-point full-duplex (non-shared) Ethernet LAN switch, CSMA/DC methods of congestion control are no longer available. Thus, in an Ethernet switch, periods of congestion result in switch buffer overflows and frame losses.
Specifically, network congestion caused by overloading an Ethernet switch is one of the new challenges associated with fully duplexed Ethernet switches. Overload occurs in an Ethernet switch when the switch is receiving more frames than it can direct. Ethernet switches are equipped with buffering capability to accommodate congestion over a short time period. However, if the overload condition persists, the switch buffer will become full, causing switch to discard frame. This is referred as congestion.
Standardization efforts for full-duplex operation of Ethernet (switched Ethernet) have focused attention on the need for flow control at MAC (Media Access Control) sublayer. In the IEEE 802.3x standard, an optional MAC Control Sublayer (MAC Control) has been defined. The scheme is intended to provide vehicle for flow control on a hop-by-hop basis by allowing a port to “turn off” or “turn on” the transmitter of the upstream device for certain period of time. The basic vehicle for transmitting flow control information from one Ethernet port to the upstream device is a MAC Control frame, a special MAC frame. Control frames are of minimum legal size (64 bytes). The MAC Control Opcode field of the MAC Control frame specifies a Pause opcode. The MAC Control Parameters defines Pause Time which indicates the amount of time for which the upstream link transmitter should stop transmitting data frames. Upon receiving a new MAC Control Frame, the port of the upstream device will stop transmission for a time period specified in the new MAC Control Frame regardless of the previous MAC Control Frame. Conversely, sending a MAC Control Frame with Pause Time being set to zero will “turn on” a paused link.
The IEEE 802.3x flow control was developed with the input queued switch architecture in mind. Implementing flow control in an input queued Ethernet switch is straightforward as buffer occupancy of an input queue provides a good indication of overload status on the port. However, this is not the case for the shared memory switch.
FIG. 3
graphically illustrates the problem. In
FIG. 3
, switch memory is represented on the vertical axis, the total available switch memory is represented as M and time is represented on the horizontal axis. Also, let the buffer occupancy of the output queue of output port A be represented by dashed-dot line and the total buffer occupancy be represented by the solid line.
At time t
0
/t
a
, a input port A receives frames requiring the use of m
a
memory, while at time t
b
input port B receives frames requiring the use of m
b
memory, resulting in a total memory use of m
a
+m
b
. At time t
c
, input port receives frames requiring the use of m
c
memory. At a time t
1
, input port C begins receiving more and more frames of data, and by time t
2
, input port C is receiving data at a rate that causes the total switch memory demanded (m
a
+m
b
+m
c
) to exceed the available memory, M. Since shared memory Ethernet devices do not monitor traffic on the input ports, to deal with this situation, the switch is forced to pause all upstream devices. For simplicity, the pause is shown as being instantaneously implemented at t
2
. As the frames in the switch memory exit the switch downstream, the total memory used by the switch decreases until the pause is over and frames are again intr

Affiliated with

Also associated with

Rating

Static and dynamic flow control using virtual input queueing... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Static and dynamic flow control using virtual input queueing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Static and dynamic flow control using virtual input queueing... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2875800