Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-02
2003-02-11
Mizrahi, Diane (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C709S224000, C709S209000, C370S398000
Reexamination Certificate
active
06519595
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to communication devices, and specifically, to admission control, queue management, and shaping/scheduling of flows in such communication devices.
2. Background Information
Small and medium businesses typically have networks comprised of local area networks (“LANs”), ranging between 10 Mega-bits per second (“Mbps”) to 100 Mbps, that carry information between stations for a wide range of applications. The applications can include a mixture of voice, video, interactive, web browsing, file transfers, etc., each of which has different requirements for bandwidth, latency, jitter, and data loss to ensure quality communication. The internal office LANs can either provide sufficient bandwidth or are economically upgradable to provide an order of magnitude increase in bandwidth.
The connection to a wide area network (“WAN”) is however another matter. The bandwidth is not easily upgradable due to the cost of WAN access circuits. Various queuing techniques have been employed in WAN access equipment in attempts to provide sharing of the limited circuit bandwidth among the different types of data. These queuing techniques typically have limited applications and undesirable characteristics. For example, in one queuing technique, queues are serviced in strict priority order, which tends to starve low priority data types. Another technique, called Weighted Fair Queuing (“WFQ”) solves the starvation effects. However, WFQ is computationally intensive, exhibits short term “unfairness”, and does not provide guaranteed bandwidth, delay bound, or jitter bound characteristics for data types that need these characteristics.
SUMMARY OF THE INVENTION
The present invention is a method and apparatus for providing shaping/scheduling for flows. In one embodiment, a method of shaping/scheduling flows includes determining an arrival rate of a data unit associated with a flow, transferring the flow in a peak rate queue if the data unit arrives at a greater rate than a permissible peak rate, transferring the flow in an allocated rate queue if the data unit arrives at a greater rate than an allocated rate but less than the permissible peak rate; or otherwise transferring the flow in an output queue if the data unit arrives at a rate less than the allocated rate.
REFERENCES:
patent: 4893307 (1990-01-01), McKay et al.
patent: 5021949 (1991-06-01), Morten et al.
patent: 5845081 (1998-12-01), Ranjarajan et al.
patent: 5850395 (1998-12-01), Hauser et al.
patent: 6085221 (2000-07-01), Graf
patent: 6163807 (2000-12-01), Hodgkinson et al.
patent: 6216127 (2001-04-01), Gans et al.
Subhash Suri et al., Leap Forward Virtual Clock: A New Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness, Washington University, Department of Computer Science, Oct. 27, 1997, 1-35.
“Fast and Scalable Layer Four Switching”, V. Srinivasan et al., Computer Communications Review, Oct. 1998.
“Small Forwarding Tables for Fast Routing Lookups”, Mikael Degermark et al., Department of Computer Science and Electrical Engineering, Computer Communications Review, Oct. 1998.
“Leap Forward Virtual Clock”, S. Suri et al, A New Fair Queuing Scheme w/Guarantted Delays & Throughput Fairness, Washington Univ., Dept. of Computer Science Oct. 27, 1997, 1-35.
“Practical Algorithm to Retrieve Information Coded in Alfanumeric,” Journal of the ACM, Oct. 1968.
Irell & Manella LLP
Mizrahi Diane
NMS Communications, Inc.
LandOfFree
Admission control, queue management, and shaping/scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Admission control, queue management, and shaping/scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Admission control, queue management, and shaping/scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149334