US 7,583,678 B1Granted

Methods and apparatus for scheduling entities using a primary scheduling mechanism such as calendar scheduling filled in with entities from a secondary scheduling mechanism

AssigneeCisco Technology, Inc.

InventorsDanny Levy, Dalit Sagi

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods and apparatus are disclosed for scheduling entities in a system, such as, but not limited to a computer or communications system. Typically, calendar scheduling is used as a primary scheduling mechanism, with spare time allocated to a secondary scheduling mechanism. The secondary scheduling mechanism can use a round robin technique or variant thereof, or any other scheduling methodology. A calendar entry is examined to determine whether to process a calendar scheduled entity corresponding to the calendar entry or to process a secondary scheduled entity. Which scheduling entity to process is typically determined based on an eligibility of an entity corresponding to the primary scheduled event, a scheduling mechanism indicator, and/or an entity indicator. These combinations of scheduling mechanisms can be used to identify which packets to send, queues or ports to access, processes or threads to execute, or for any other purpose.

Claims16

Dependent claims

A method for scheduling, the method comprising:

storing both a plurality of primary scheduling entries and a plurality of secondary scheduling entries in one or more scheduling data structures in one or more memories, said one or more scheduling data structures used by a scheduler in its determination of the order of processing a plurality of entities, wherein the plurality of entities are distinct from the plurality of primary scheduling entries and from the plurality of secondary scheduling entries;
and wherein the plurality of entities are not stored in said one or more scheduling data structures;
the scheduler determining a next primary scheduling entry of the plurality of primary scheduling entries, said determined next primary scheduling entry including a scheduling mechanism indicator which is a value defining which of a plurality of options to process, said options including:
(a) an entity corresponding to said determined next primary scheduling entry, and (b) one or more entities corresponding to one or more next secondary scheduling entries in the plurality of secondary scheduling entries;
and
in response to the scheduling mechanism indicator of said determined next primary scheduling entry causing the processing of said defined option.

3 more elements

An apparatus for scheduling, the apparatus comprising:

one or more memories including a plurality of calendar scheduling entries and a plurality of round robin entries;
a plurality of packet queues configured to store packets;
and
a scheduler configured to initiate sending of packets from the plurality of packet queues based on the plurality of calendar scheduling entries and the plurality of round robin entries;
wherein the scheduler is configured to sequence through the plurality of calendar scheduling entries, and for each particular calendar entry of the plurality of calendar scheduling entries, evaluate a scheduling mechanism indicator which is a value included in said particular calendar entry in order to determine which of a plurality of options to perform, said options including:
(a) to send one or more packets from a queue of the plurality of packet queues corresponding to said particular calendar entry, and (b) to send one or more packets from a queue of the plurality of packet queues corresponding to one or more next round robin entries of the plurality of round robin entries;
wherein the plurality of calendar scheduling entries and a plurality of round robin entries are distinct from the plurality of packet queues and packets stored therein.

4 more elements

Dependencies are inferred from the claim text.