Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus interface architecture
Reexamination Certificate
2001-05-01
2004-02-03
Vo, Tim (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus interface architecture
C710S316000, C709S241000, C370S229000, C370S232000
Reexamination Certificate
active
06687781
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to network switches and in particular to a network switch employing a weighting system for distributing excess forwarding bandwidth among several traffic flows buffered by a network switch port.
2. Description of Related Art
A network switch routes data transmissions such as ethernet packets between a set of network buses. A typical network switch includes a set of input switch ports for receiving packets arriving on the buses, a set of output switch ports for forwarding packets outward on the buses, and a switch fabric such as a crosspoint switch for routing packets from each input switch port to the output switch ports that are to forward them. Network input and output switch ports typically include buffer memories for storing packets until they can be forwarded.
Some network switch input switch ports include protocol processors for converting each incoming packet to a sequence of cells of uniform size. The input port stores the cells in its buffer memory until it can forward them through the switch fabric to one of the output ports. Each output switch port in turn stores cells received via the switch fabric in its buffer memory and later forwards them to another protocol processor which reassembles them into a packet to be forwarded outward on a network bus.
Each input or output switch port has a maximum bandwidth or rate (in cells or packets per second) at which it may forward cells or packets. Some network systems classify packet or cells according to a set of “flows”, each having a defined class of service with respect to the portion of a switch port's bandwidth that may be allocated to forwarding the packets assigned to a particular flow. A switch port may allocate each flow (or group of flows) a predetermined guaranteed minimum portion of the port's available forwarding bandwidth. A switch port may also allocate each flow a share of the port's excess bandwidth up to a predetermined maximum limit for each flow.
A switch port therefore must reserve a sufficient amount of its bandwidth to cover the sum of minimum bandwidths of all flows regardless of whether they are active. A flow is “active” if cells or packets assigned to that flow await forwarding from the switch port's buffer memory. The port dynamically allocates its remaining “excess bandwidth” to the active flows. Typically when a flow becomes active, the switch port allocates it any unused portion of the switch port's excess bandwidth up to the flow's maximum allowable bandwidth. Conversely, when a flow becomes inactive, the port terminates the flow's allocation of excess bandwidth so that it can allocate that portion of excess bandwidth to the next flow to become active.
Such a bandwidth allocation system has two problems. First, when a flow is inactive, its reserved minimum bandwidth remains unused and therefore wasted. Second, a port's excess bandwidth is not fairly distributed among active flows but is instead allocated based only on the amount of the port's bandwidth that happens to be unused when a flow becomes active.
What is needed is a bandwidth allocation system for a network switch port which allocates forwarding bandwidth only to active flows and not to inactive flows, and which more fairly allocates the port's excess bandwidth among active flows.
BRIEF SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, a traffic manager for a network switch port stores incoming cells in a cell memory and later forwards them out of the cell memory and the switch port. Each cell is assigned to one of several flow queues and each flow queue has an assigned minimum forwarding bandwidth with which cells of that flow queue must be forwarded from the cell memory and has an assigned maximum bandwidth with which cells of that flow queue may be forwarded.
In accordance with another aspect of the invention, when any flow queue is active (i.e., when it has cells currently stored in the cell memory), the traffic manager allocates a sufficient amount of the switch port's available cell forwarding bandwidth to each active flow queue so that cells of that flow queue are forwarded with at least the flow queue's assigned minimum bandwidth.
In accordance with a further aspect of the invention, each flow queue has an assigned forwarding weight. The traffic manager also dynamically allocates a portion of the switch port's excess forwarding bandwidth, above that needed to accommodate each active flow queue's minimum bandwidth, among all active flow queues in relative proportion to each active flow queue's assigned forwarding weight. Thus the actual forwarding bandwidth allocated to each active flow queue is the sum of its assigned minimum forwarding bandwidth and its allocated portion of excess bandwidth. However the traffic manager limits the actual forwarding bandwidth allocated to any one flow queue so that it does not exceed the flow queue's assigned maximum forwarding bandwidth.
It is accordingly an object of the invention to dynamically allocate the cell forwarding bandwidth of the switch port among active flow queues in a manner that makes efficient use of the switch port's cell forwarding bandwidth.
It is another object of the invention to dynamically allocate to each active flow queue a forwarding bandwidth within a range defined by its assigned minimum and maximum forwarding bandwidths.
It is further object of the invention to ensure that cell forwarding bandwidth is at all times fairly allocated among active flow queues in accordance with a predetermined weighting system.
The concluding portion of this specification particularly points out and distinctly claims the subject matter of the present invention. However those skilled in the art will best understand both the organization and method of operation of the invention, together with further advantages and objects thereof, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.
REFERENCES:
patent: 6408005 (2002-06-01), Fan et al.
patent: 6430155 (2002-08-01), Davie et al.
patent: 6546017 (2003-04-01), Khaunte
Divivier Robert J.
Wynne John M.
Bedell Daniel J.
Smith-Hill and Bedell
Vo Tim
Zettacom, Inc.
LandOfFree
Fair weighted queuing bandwidth allocation system for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair weighted queuing bandwidth allocation system for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair weighted queuing bandwidth allocation system for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3351647