Abstract:
A system coupled between at least one input port and at least one output port comprises at least one queue, each queue being identified by a QID and operable to receive and buffer data in at least one service flow from the at least one input port. The system further comprises a predetermined at least one token allocated to each queue, each token indicative whether a predetermined amount of data may be dequeued from a queue and transmitted to the output port. The system comprises at least one group of queues where each queue in the group has a subordinate QID identifying a subordinate queue in the group having a lower priority for reallocating unused tokens. The at least one output port receives at least one output flow comprising the dequeued data from the at least one queue.

Description:
BACKGROUND 
       [0001]    In various communication applications, it is often desirable to prioritize data and voice traffic competing for limited bandwidth in a network connection. In particular, in a network equipment connecting a number of customer equipment on one or more local area networks (LANs) to a carrier network, the communication traffic in competition for access to the carrier network may include VoIP, video, and data traffic. These different types of traffic generally have different requirements in terms of bandwidth, jitter, latency, and frame loss. For example, VoIP traffic have low bandwidth requirements and demands low latency, jitter, and frame loss because the caller and callee are carrying on a real-time conversation. On the other hand, video data traffic requires higher bandwidth and can tolerate higher jitter, latency, and frame loss. Typically, the network equipment connecting the customer equipment on LANs or VLANs to a carrier network utilizes a work-conserving scheduler to prioritize traffic onto the uplink, or alternatively provides only a single bandwidth controlled service. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0002]    Aspects of the present disclosure are best understood from the following detailed description when read with the accompanying figures. It is emphasized that, in accordance with the standard practice in the industry, various features are not drawn to scale. In fact, the dimensions of the various features may be arbitrarily increased or reduced for clarity of discussion. 
           [0003]      FIG. 1  is a simplified block diagram of a plurality of network equipment connecting local area networks each having one or more Ethernet virtual circuits of various bandwidths transmitting and receiving data frames over a carrier network; 
           [0004]      FIG. 2  is a simplified block diagram of an embodiment of a network equipment operable to provide aggregated shaping of multiple prioritized classes of service flows; 
           [0005]      FIG. 3  is a simplified block diagram of an embodiment of certain modules of the network equipment operable to provide aggregated shaping of multiple prioritized classes of service flows; 
           [0006]      FIG. 4  is a more detailed block diagram of an embodiment of upstream (ingress) aggregated shaping of one or more prioritized class of service flows; 
           [0007]      FIG. 5  is a simplified exemplary diagram of a group of queues linked by subordinate QID; and 
           [0008]      FIG. 6  is a more detailed block diagram of an embodiment of downstream (egress) aggregated shaping of multiple prioritized class of service flows. 
       
    
    
     DETAILED DESCRIPTION 
       [0009]      FIG. 1  is a simplified block diagram of a plurality of access gateways  10 - 14  coupled to local area networks (LANs) or virtual LANs (VLANs) and to Ethernet virtual circuits (EVCs)  16 - 20  of various bandwidths over a carrier network  22 , such as a wide area network (WAN). Access gateways  10 - 14  are operable to provide aggregated shaping of multiple prioritized class of service (CoS) flows  24 - 28 . Preferably, the access gateways support the IEEE 802.1ad, 802.1ag, 802.1D, 802.1Q, 802.3ah, and other applicable standards. Although the description herein specifies LANs, VLANs, and WANs, the system and method described herein other types of computer networks and virtual connections. 
         [0010]      FIG. 2  is a simplified block diagram of an embodiment of a network equipment  10 . Network equipment  10  is coupled to one or more customer ports  29  to receive and transmit one or more service flows  24 . The traffic in the service flows may include VoIP, video, and data traffic that have different bandwidth, latency and jitter requirements. A customer Ethernet virtual circuit (EVC) connection is identified by a unique X-tag at a customer port  29 . The data frames in the service flows  24  arriving on the customer ports  29  are sorted and classified by a classification module  30  and forwarded in CoS flows to other processing modules, including one or more queues  32  that perform buffering and shaping. The queues are further grouped and prioritized to form groups of queues which enable aggregated scheduling of the grouped queues subject to one another. As a result, groups of queues  32  related by network port EVC or output LAN port are scheduled subject to each other. The groups have strict priority for determining frame egress ordering subject to the availability of tokens. Details of the aggregated scheduling are set forth below. Data frames are removed from the queues  32  (dequeued) and transmitted over one or more Ethernet virtual circuits  16  out to the carrier network  22  via at least one network port  39  according to certain parameters of the service flows, such as committed information rate (CIR) and excess information rate (EIR), and the CoS for the queue. This aspect is described in more detail below. The Ethernet virtual circuits at the network port  39  are identified by a unique S and C tag combination. Any queue may be mapped to any output port and the frames from any input port may be entered into any queue. 
         [0011]      FIG. 3  is a simplified block diagram of an embodiment of certain modules of the network equipment  10  operable to provide aggregated shaping of multiple prioritized classes of service flows. Network equipment  10  is coupled to one or more local area network ports  29  on one side and to one or more network ports  39  leading to a carrier network  22  that may be a wide area network (WAN), for example. The carrier network  22  may comprise other types of networks and network equipment to transmit communications traffic. The network equipment  10  includes the classification module  30  that performs priority classification on incoming data frames and forwards the data frames in CoS flows. The classification module  30  may perform the classification depending on one or more properties of the frame, including for example, VID and/or PRI fields of the VLAN tag(s) and/or the IP layer TOS/DSCP fields of the frame. A customer port  29  may be configured as a TLS (transparent LAN services) or TVLS (transparent VLAN services) type. According to the type of port, the data frames may be accepted or discarded in response to the VLAN tag and VID values, or other parameters. When a customer port  29  is operating in a VLAN-aware mode, frames belonging to the service flows which have the proper VLAN tags are passed downstream. Data frames in service flows received from customer ports  29  operating in a VLAN-unaware or transparent mode, the service flows must be classified and the proper tags “pushed” or inserted into the data frames. The access gateway  10  is operable to support classification of services based on layer 2 protocol information, i.e., the media access control (MAC) header and the VLAN tags, and layer 3 information, i.e., the type of service (TOS) and differentiated services code point (DSCP) fields. The data traffic are thus identified by CoS classes. 
         [0012]    A transformation module  38  is operable to perform certain VLAN tag operations on incoming data frames. The transformation module  38  “pushes” or inserts the proper C VLAN tags into the data frames and may make other transformations. The X tag identifies a CoS flow belonging to the customer port and is mapped to a C tag on the network port. A policing module  40  is operable to check the conformance of the data frames to declared traffic characterization parameters. The policing module  40  meters the incoming flow and determines whether to pass the frame if the frame is within the service profile, marking it as “drop eligible” and passing the flow if it is outside the committed service parameters but within the excess service parameters, or dropping the frame immediately if it is outside the excess service parameters. The policing module  40  may test incoming traffic against a number of bandwidth profile parameters, such as the committed information rate (CIR), the committed burst size (CBS), the excess information rate (EIR), and/or the excess burst size (EBS). A single VLAN can have multiple policing flows to police the rate of different member PRI codepoints as separate CoS classes. 
         [0013]    A buffering module  42  comprises one or more queues that buffer data frames in the CoS flows until the frames are de-queued according to the scheduling algorithms of a shaping module  44 . One or more CoS flows from the policing module can flow into a queue. Queues related by network port EVC or output LAN port are grouped in such a way as to determine a service. As a result, groups of queues  32  related by network port EVC or output LAN port are scheduled subject to each other. The groups have strict priority for determining frame egress ordering subject to the provisioned bandwidth and shaping parameters. The shaping module  44  uses a token bucket method to remove the data from the queues in response to the CIR, CBS, EIR, EBS, CoS, the availability of bandwidth, and other provisioning parameters. Details of the operations of the buffering module and the shaping module are set forth below. 
         [0014]      FIG. 4  is a more detailed block diagram of an embodiment of upstream (ingress) aggregated shaping of multiple prioritized class of service flows. One or more service flows  24  are received from one or more customer ports  29  coupled to LANs or VLANs. The service flow data frames may be identified by the port they are received from and the X VLAN tag. The service flows are first processed by the classification module  30 , transformation module  38 , and policing module  40 , collectively show as one block in  FIG. 4 . The VLAN data frames in the service flows  50  existing in these modules comprise X, C, and S VLAN tags. A double-tagged network virtual circuit connection is identified by a unique S and C tag combination at the determined network port. A singly-tagged network virtual circuit connection is identified by either a unique S or C tag. Each policed CoS flows  50  is typically provided to a queue  32 , however, multiple CoS flows may be linked to the same queue. Each queue is identified by a queue identifier (QID) and assigned a CIR token bucket  52  and an EIR token bucket  54 . Each queue is allocated a fixed number of bytes from a shared buffer memory pool. The queues do not compete with one another for memory once the allocation has been completed. The queues may be of different sizes based on a provisioned value Each queue is provisioned to have a certain number of tokens for the CIR token bucket  52  that correlates to a maximum guaranteed traffic rate. The number of tokens in the EIR bucket  54  correlates to the excess traffic rate. The maximum number of tokens allocated to the CIR bucket  52  is a function of the CBS and the maximum number of tokens allocated to the EIR bucket  54  is a function of the EBS. These tokens are replenished at regular intervals. 
         [0015]    Each queue is provisioned with CIR, CBS, EIR, EBS, subordinate QID, and CoS parameters. The CoS indicates the class of service of the queue and can range from 0 to 7. The subordinate QID identifies the queue to which unused CIR and EIR tokens should be passed. As long as there are still unused tokens available, the tokens are passed to the queues in the group as identified by the subordinate QID.  FIG. 4  shows QoS groups  60 - 68 , where groups  60 - 64  are each a group of one queue. A prioritized grouping of queues are therefore formed by using the subordinate QID. The use of subordinate QID enables the grouping of queues related by network port EVC or output LAN port to be scheduled subject to each other by using the same allocation of tokens according to CoS priority. A subordinate flag may be used to indicate whether a queue has a subordinate QID. Each group of queues also has associated therewith a group CIR token number, which is greater than or equal to the sum of CIR tokens allocated and replenished for all queues in the group. Further, the number of tokens allocated and replenished to each queue in response to the excess information rate is no greater than the number of tokens replenished for the group CIR token number. 
         [0016]      FIG. 5  is a simplified exemplary diagram of a queue grouping  70  linked by queue priority and the subordinate QID. The queues  71 - 74  in the group  70  are related by network port EVC or output LAN port. In the example shown in  FIG. 5 , queue  72  has the highest priority (CoS). The subordinate QID of queue  72  points or identifies queue  71  as the subordinate queue that should be allocated any left over CIR and EIR tokens not used to dequeue data from queue  72 . The subordinate QID of queue  71 , in turn identifies queue  73  as its subordinate queue that should receive an allocation of unused tokens from queue  71 . Queue  74  is the subordinate queue of queue  73 , as indicated by the subordinate QID of queue  73 . The queues  71 - 74  are therefore linked by the subordinate QID in descending priority and the group of queues are “scheduled” subject to one another. Therefore, these groups of queues related by network port EVC or output LAN port are scheduled subject to each other. The intra-group scheduling is performed as a result, in a work-conserving manner. The overall scheduling of the groups which are members of the output port may or may not be work conserving, depending upon the provisioning of the aggregate of the groups. 
         [0017]      FIG. 6  is a more detailed block diagram of an embodiment of downstream (egress) aggregated shaping of multiple prioritized classes of service flows. Downstream flow, i.e., from the network port  39  to the customer ports  29 , is processed similarly to the upstream flow. The network EVCs  16  from the network port  39  are first processed by the classification, transformation, and policing modules, collectively shown as block  90 . The classification module determines the classification of the flows from the network port  39 . The transformation module operates on the VLAN tags, such as stripping the S and C tags from the frames. Data frames with invalid S and C tags are discarded. The policing module meters the frame flow based on specified CIR, CBS, EIR, and EBS service parameters. The data frames are then buffered and stored in egress queues  92  until they are dequeued and transmitted to the customer ports  29  according to the scheduling algorithm and available egress bandwidth. The data frames are dequeued by the scheduler using CIR and EIR buckets  94  and  96  in a similar manner as described above in conjunction with  FIG. 4 , and transmitted to the appropriate customer port  29 . 
         [0018]    The network equipment described herein is operable to control bandwidths offered to the carrier network from the network edge for multiple services, while offering different classes of service within each network service. The system and method described herein are applicable to any suitable network equipment coupled between two or more computer networks. 
         [0019]    Although embodiments of the present disclosure have been described in detail, those skilled in the art should understand that they may make various changes, substitutions and alterations herein without departing from the spirit and scope of the present disclosure. Accordingly, all such changes, substitutions and alterations are intended to be included within the scope of the present disclosure as defined in the following claims. In the claims, means-plus-function clauses are intended to cover the structures described herein as performing the recited function and not only structural equivalents, but also equivalent structures.