Router with class of service mapping

Details Router with class of service mapping Router with class of service mapping

1997-12-31

2002-10-08

Felber, Joseph L. (Department: 2732)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S230000

Reexamination Certificate

active

06463068

ABSTRACT:

FIELD OF INVENTION
The invention relates generally to routers and switches and, more particularly, to routers and switches that support multiple classes of service for packet routing.
BACKGROUND OF THE INVENTION
At network multiplexing points, such as switches or routers, the handling of frames or packets is generally determined by rules associated with classes of service to which given frames or packets are assigned. The classes of service essentially define acceptable packet or frame delays and probabilities of packet or frame loss. (As used herein, the term “packet” refers to both frames and packets, and the term “router” refers to both switches and routers.)
The packets are typically assigned to classes of service based on information contained in the packet and/or traffic management rules established by either a network supervisor or a service provider. All packets assigned to the same class receive the same treatment. Being assigned to a “higher” class ensures that a packet will have a shorter maximum transmission delay and a lower probability of loss. Being assigned to a “lower” class may mean a longer delay and/or a greater probability of loss.
Generally, the router maintains at each output port a buffer for holding packets in queues associated with the classes of service. The queues ensure that packets are delivered in order within the various classes of service, and that the associated rules for maximum delays and probabilities of loss can be enforced. Since each queue is essentially separately maintained, the more classes the router supports the more processing and storage capacity is required for a given number of output ports. To support “x” classes, for example, the router must set aside buffer storage locations for each of the x queues at each of its “y” ports. Further, it must determine for each queue whether or not a next packet should be retained or discarded. The router thus makes x*y separate calculations based on queue length and/or available associated storage locations to determine whether to retain or discard the packets, where “*” represents multiplication.
Network standards, such as the (revised) 802.1p standard, have relatively recently increased the number of classes of service to eight classes. Routers operating under prior standards support four classes of service, and thus, must be upgraded, for example, with increased storage capacities of the output port buffers, to support the increased number of classes. Such upgrading may be prohibitively expensive and/or it may not be feasible. Accordingly, what is needed is a mechanism to operate a router that supports a relatively small number of classes of service in an environment in which packets are assigned to a greater number of classes. Such a mechanism should, without requiring the enlarged storage and processing capabilities conventionally associated with supporting the greater number of classes, maintain service distinctions associated with the greater number of classes and more importantly retain the order of packets within each of the greater number of classes.
SUMMARY OF THE INVENTION
A router maps packets assigned to 2
n+m
classes of service into 2
n
classes of service and assigns the packets to 2
m
levels of loss-priority within each of the 2
n
classes. The router includes a classifier that uses n bits of an (n+m)-bit “class of service identifier” to map the packets to the 2
n
classes, and the remaining m bits to assign the loss priorities. The router then controls packet retention/discard with a modified weighted random early detection scheme based in part on the 2
n+m
classes and in part on the 2
n
classes, to maintain the probability of loss distinctions and in-order packet handling associated with the 2
n+m
classes.
A scheduler controls the transmission of packets by each output port based on the 2
n
classes of service. The scheduler uses a weighted round robin scheme to ensure that packets from each of the classes are transmitted by each of the output ports within the prescribed maximum delay limits associated with the 2
n+m
classes of service.
The router includes an output buffer that holds the packets for all of the router's output ports. The router maintains a “free queue,” which links the buffer storage locations available for packet storage. To determine whether to retain or discard a given packet, the router compares a weighted average depth of the free queue with predetermined maximum and minimum thresholds that are associated with the particular one of the 2
n+m
classes of service to which the packet is assigned. If the weighted average exceeds the associated maximum threshold, the router retains the packet in a storage location that is then removed from the free queue and linked to a class of service per output port queue that corresponds to the class of service to which the packet is mapped by the classifier. If the weighted average depth falls below the associated minimum threshold, the router discards the packet. If the weighted average depth falls between the associated minimum and maximum thresholds, the router calculates a probability of discard and compares the probability to a “random” value. The router discards the packet if the probability exceeds the random value, and otherwise retains the packet.
The maximum and minimum thresholds are set relative to one another such that the loss priorities associated with the 2
n+m
classes are maintained. As discussed below, the router makes only one weighted average queue depth calculation for the free queue, and uses this calculation to determine whether to retain or discard packets for the 2
n
classes of service. This is in contrast to prior known routers that must maintain at each output port separate average queue depths for each of the class of service per port queues.


REFERENCES:
patent: 5953341 (1999-09-01), Yamanaka et al.
S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance”, Aug., 1993 IEEE/ACM Transactions on Networking, pp. 1-32.

Affiliated with

Also associated with

Rating

Router with class of service mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2930479