Technique for supporting tiers of traffic priority levels in...

Details Technique for supporting tiers of traffic priority levels in... Technique for supporting tiers of traffic priority levels in...

1999-03-05

2003-04-08

Vincent, David (Department: 3661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S468000

Reexamination Certificate

active

06546017

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field Of Invention
The present invention relates generally to methods and apparatus for transmitting digital data in packet-switched networks. More specifically, the present invention relates to methods and apparatus for supporting tiers of traffic priority levels in a packet-switched network.
2. Background
Today's integrated service networks are able to support a plurality of different service classes, which may include a bandwidth-guaranteed service class and a best-effort service class. Further, protocols that enable high-speed data access over these integrated service networks, such as cable networks or linked networks (e.g. LANs, WANs, Internet, etc.) have recently been configured to support differentiated Quality of Service (QoS) within selected service classes.
When a scheduler or router has outstanding requests from plurality of different subscribers, it should be able to differentiate and offer better service to selected subscribers (who have subscribed for a higher grade of service) as compared to other subscribers (who have subscribed for lower grade of service). As a result, service providers are now offering differentiated service, particularly within the best-effort service class (herein referred to as “tiered best-effort”), whereby different grades or priority levels of service within the best effort class are offered to the subscriber, each with a different pricing plan.
For example, a conventional tiered best-effort service may provide eight differentiated priority levels of best-effort service, each with a different pricing plan. Thus, a subscriber may choose to pay more money for a relatively higher priority best-effort service, whereby, presumably, packets having a relatively higher priority of best-effort service will be routed faster than packets with relatively lower priority best-effort service.
Companies which implement tiered best-effort service typically implement some type of grant prioritization scheme for handling the tiered best-effort traffic. Conventional traffic prioritization algorithms use separate FIFO queues for queuing bandwidth requests (in cable modem networks) or packets (in packet-switched networks) related to a particular priority level of service. A strict priority server is typically used to service the FIFO queues in order of their priority. Thus, for example, in a tiered best-effort service class having eight distinct levels of priority (0-7), 8 separate FIFO queues will typically be provided for servicing bandwidth requests or packets related to each distinct priority level. This can be seen, for example, in
FIG. 8
of the drawings.
FIG. 8A
shows an example of a plurality of bandwidth request/packets or packets being received at a cable network head end or router. The requests/packets of
FIG. 8A
are all within the tiered best-effort service class, which in this example includes eight levels of priority (level 7-level 0). Each request/packet has an associated priority level (P) and arrival time (T).
FIG. 8B
shows a plurality of FIFO queues
810
which are used for queuing the received request/packets of
FIG. 8A
until each request/packet is able to be processed. As shown in
FIG. 8B
, each priority level within the tiered best-effort service class has its own respective FIFO queue. Queue
802
corresponds to priority level 7, queue
804
corresponds to priority level 6, and queue
806
corresponds to priority level 0 within the tiered best-effort service class.
A number of conventional scheduling techniques may be employed to service the queued request/packets within queue array
810
. One common technique used to service bandwidth requests and/or packets is the use of a strict priority server. The following example provides a brief illustration of how tiered best-effort service is conventionally implemented in a cable modem networks using a strict priority service algorithm.
The process starts with a bandwidth request being sent on the upstream channel by a cable modem at the subscriber end. When the bandwidth request is. received at the cable head end, the service ID (SID) of the cable modem is identified, and from this service ID the particular class of service (i.e. static priority level) associated with the requesting modem's service class is determined. The received bandwidth request is then enqueued in the appropriate FIFO queue within the queue array
810
corresponding to it's associated level of priority. Thus, for example, bandwidth request A (
FIG. 8A
) is associated with priority 7, and therefore enqueued in queue
802
of FIG.
8
B. The remainder of the bandwidth requests B-K of
FIG. 8A
are similarly queued within queue array
810
, according to each request's associated priority level.
A static priority server is used to service the queued bandwidth requests of FIG.
8
B. According to the static priority service algorithm, FIFO queues associated with the highest priority level(s) are serviced completely before serving FIFO queues associated with lower priority levels. In the example of
FIG. 8
, the queued bandwidth requests in FIFO queue
802
would be serviced first (until the queue is empty), followed by queue
804
, and eventually queue
806
.
One common problem associated with conventional prioritization techniques such as the above-described strict priority scheduling technique, is the requirement of maintaining a separate FIFO queue for each respective priority level within a particular service class for each individual upstream channel [i]. This requirement not only increases complexity and overhead of the network, but also decreases resource utilization since a predetermined amount of memory is typically reserved and allocated for implementing each queue within structure
810
, meaning that this allocated memory is unavailable for use for other purposes. Another drawback to the above-described technique is that it is not easily scalable to accommodate changes in the number of static priority levels within a particular service class. In other words, an additional and separate queue must be implemented for each new priority level included within a particular service class. Furthermore, the software for the scheduling algorithm must also be modified to accommodate servicing of the additional priority queues.
Another problem of the above-described technique relates to starvation of low priority traffic. For example, in serving the bandwidth requests of
FIG. 8B
in the manner described above, it is possible to get a continuous supply of bandwidth requests in the higher priority FIFO queues, which results in starvation of the bandwidth requests queued in the lower priority FIFO queues. To address this problem, it is often necessary to implement a weighted round robin servicing algorithm which uses a fairness algorithm in serving the FIFO queues to ensure that the low priority FIFO queues are sufficiently service so as not to be starved by a continues supply of bandwidth requests in the higher priority FIFO queues.
The round robin scheduling technique is commonly known to those skilled in the art and is described, for example, in the publication “Round-Robin Space Scheduling for Max-Min Fairness in Data Networks,” by Ellen L. Hahne, IEEE Journal on Selected Areas in Communications, Volume 9, pages 1024-1036, September 1991, herein incorporated by reference in its entirety for all purposes.
In the weighted Round Robin server implementation, each FIFO queue is pre-assigned a weight, which for example, may be expressed in terms of a number of rounds (e.g. bandwidth requests) to be dequeued from a particular queue during a given cycle, or expressed in terms of a number of bytes to be processed from that queue during a given cycle. By assigning higher weights to the higher priority FIFO queues, a greater number of packets will be processed from these queues, thereby achieving prioritization. At the same time, assigning a small weight to the lower priority queues ensures that at least a minimum number of rounds will be processed from these queues d

Affiliated with

Also associated with

Rating

Technique for supporting tiers of traffic priority levels in... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Technique for supporting tiers of traffic priority levels in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for supporting tiers of traffic priority levels in... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3084845