Software programmable calendar queue cache

Details Software programmable calendar queue cache Software programmable calendar queue cache

1999-12-16

2004-05-04

Perveen, Rehana (Department: 2182)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C710S053000, C710S054000, C710S055000, C710S006000, C710S029000, C710S039000, C709S241000, C709S241000, C709S241000

Reexamination Certificate

active

06732199

ABSTRACT:

TECHNICAL FIELD
The present invention relates to a calendar queue for enforcing quality of service action specs and, in particular, to a calendar queue that utilizes a fast lookup logic to speed the process of filling and emptying the cache.
BACKGROUND
In one type of policy network, a Calendar Queue is used to schedule the output packets after policy enforcement according to the corresponding bandwidth (QoS Action Spec) which specifies when and how often the packets should depart. Conventionally, the mechanism is based on a queue that includes a plurality of equally spaced time slots. One timeslot represents one bandwidth unit. If the queue is implemented by hardware, then one time slot can be one external memory location, with these slots being contiguous external memory space. The operation is shown in FIG.
1
.
When the packet for a given QoS Action Spec leaves the system, the conventional system first invalidates the current slot and advances to the new slot for next schedule after a bandwidth interval. If the new slot turns out to be valid (occupied by another QoS Action) then the system searches for the nearest invalid slot after the occupied one to schedule the next packet. In
FIG. 1
, the QoS Action Spec #20 that has a bandwidth equal to 2 represents this case.
The Action Spec #20, according its bandwidth, should be inserted to the time slot
2
. But since the slot
2
has been occupied by the Action Spec #21 then the available slot
3
is selected. Checking the valid bit and searching the first available invalid bit involve a lot of memory access operations. Use of external memory creates a long latency for scheduling the packets. Even worse, if the memory is also shared by other processors, the arbitration time can make the latency even longer.
SUMMARY
The present invention is a method of scheduling packet output in accordance to a quality of service (QoS) action specification. A calendar queue of bandwidth timeslots is maintained, wherein the bandwidth timeslots are organized into groups. Look-up logic circuitry is invoked that inspects the bandwidth timeslots of a group in the queue substantially simultaneously. The look-up logic circuitry determines from the group a first unoccupied bandwidth timeslot in which a current packet can be scheduled and also determines from the group a first occupied bandwidth timeslot which contains a next packet to transmit.


REFERENCES:
patent: 5371852 (1994-12-01), Attanasio et al.
patent: 5473599 (1995-12-01), Li et al.
patent: 5764895 (1998-06-01), Chung
patent: 5842007 (1998-11-01), Tarsky et al.
patent: 5864854 (1999-01-01), Boyle
patent: 6016315 (2000-01-01), Chambers et al.
patent: 6061784 (2000-05-01), Tarsky et al.
patent: 6104700 (2000-08-01), Haddock et al.
patent: 6205154 (2001-03-01), Schmidt et al.
patent: 6247061 (2001-06-01), Douceur et al.
patent: 6335935 (2002-01-01), Kadambi et al.
U.S. patent application Ser. No. 09/465,123, Lin, filed Dec. 16, 1999.
Abadi, M., et al., “Secure Web Tunneling,” http://pa.bell-labs,com/~abadi/Papers/tunnel/206.html, pp. 1-13 (Dec. 16, 2000).
“Intel ISP Program Case Studies: UUNET Canada Leads the Industry in Move to Virtual Provate Networks,” http:www.intel.com/isp/casestudies/uunet.htm, pp. 1-4 (2000).
“Tunnel Switching: 3Com Technology Boosts VPN Security and Flexibility,” http://www.3com.com/technology/tech_net/white—papers/503049.html, pp. 10 (1999).
“Vitural Multi-megabit Access Path: Affordable and Available Internet and IP Access at Speeds Greater than T1,” http://www.tiaranetworks.com/vmapwp.html, pp. 1-9 (1999).
“Web Workshop—Virtual Private Networking: An Overview,” http://msdn.Microsoft.com/workshop/server/feature/vpnovw.asp, pp. 1-16 (May 29, 1998).
Feguson, Paul and D. Senie, “Network Ingress Filtering: Defeating Denial of Service Attacks Which Employ IP Source Address Spoofing,” http://andrew2.Andrew.cmu.edu/rfc/rfc2267.html, pp. 1-16 (Jan. 1998).
“The NetBoost Policy Engine: Comprehensive Platform Enables Today's Leading Policy Enforcement Applications to Operate at Full Wire Speed,” NetBoost Corporation, pp. 1-9 (1998).
“The NetBoost Policy Appliance: Device Enables Concurrent Operation of Multiple Policy Enforcement Applications to Operate at Full Wire Speed,” NetBoost Corporation (1998).
“NetBoost PE—1000: Network Application Engine,” NetBoost Corporation (1998).
NetBoost SKD: Software Development Kit, Net Boost Corporation (1998)..
“A New Breed: The Net Boost Platform for Policy Enforcement Applications,” NetBoost Corporation, pp. 1-11 (1998).
Russell, Paul, “Keeping the TCP/IP Stream Flowing,” Linux Magazine, http://www.linux-mag.com/1999-08/bestdefemse02.html, pp. 1-8 (Aug. 1999).

Affiliated with

Also associated with

Rating

Software programmable calendar queue cache does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Software programmable calendar queue cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software programmable calendar queue cache will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3221913