Cisco Technology, Inc.

Gregory S Goss

Christopher J Kappler

Scott Smith

Andrew T Hebb

Robert C Olsen

Albert A Slane

Achot Matevossian

A data communications device interconnected for channelized communication overcomes the problems associated with message traffic starvation on outgoing traffic channels by forming arbitration, or speed groups of logical interfaces and allocating scheduling resources in proportion to the bandwidth attributed to each group relative to the total bandwidth of the device. Incoming messages have a transmission rate based on QOS, content type, or other constraints. A categorizer determines arbitration groups of the outgoing messages based on the transmission rate of the message. The scheduler allocates dequeue requests among the groups according to the proportion allocated to the arbitration group. A dequeue manager drains the outgoing messages from the arbitration groups at a rate in proportion to the total percentage of outgoing transmission bandwidth represented by the group by selecting a message from among the arbitration groups according to the computed proportion.

Methods and apparatus for reducing arbitration delay in channelized systems by use of additional scheduling hierarchy

Queues are scheduled for outputting data using a hierarchical tree. Each level of the hierarchical tree includes multiple entries for storing status information associated with the queues. For example, a given entry of the tree stores multi-parameter status information associated with a corresponding queue to be serviced. To determine which of the queues is next in line for servicing, a logic circuit compares the multi-parameter status information stored in two or more entries of the tree. The next scheduled queue or highest priority queue in the tree is then serviced by outputting at least some of its data.

Methods and apparatus for scheduling tasks

Typically, queues in a router device are used to track data information such as packets or data flows for later transmission to another downstream communication device. To reduce overhead associated with tracking an average queue length of a queue, a metric reflecting average queue length (or estimated queue length) is updated based on the occurrence of an event such as when the contents of the queue are modified. More specifically, if data is added or deleted from the queue, the metric reflecting an average fullness of the queue over time is updated at substantially the same time as updating the instantaneous queue length metric associated with the queue. This technique of synchronously updating both IQL and AQL simplifies the overall task of maintaining queue length information.

Methods and apparatus for maintaining a queue

Conventional schedulers employ designs allocating specific processor and memory resources, such as memory for configuration data, state data, and scheduling engine processor resources for specific aspects of the scheduler, such as layers of the scheduling hierarchy, each of which consumes dedicated processor and memory resources. A generic, iterative scheduling engine, applicable to an arbitrary scheduling hierarchy structure having a variable number of hierarchy layers, receives a scheduling hierarchy structure having a predetermined number of layers, and allocates scheduling resources such as instructions and memory, according to scheduling logic, in response to design constraints and processing considerations. The resulting scheduling logic processes the scheduling hierarchy in iterative manner which allocates the available resources among the layers of the hierarchy, such that the scheduler achieves throughput requirements corresponding to enqueue and dequeue events with consideration to the number of layers in the scheduling hierarchy and the corresponding granularity of queuing.

Iterative architecture for hierarchical scheduling

A computerized device has dynamically modifiable hardware, such as an ASIC, that performs queue-scheduling operations. The hardware incorporates a generic sorting processor (GSP) that is dynamically configurable to implement various sorting algorithms to meet specific queue scheduling requirements for the computerized device. The computerized device extracts a first time stamp value and a second time stamp value associated with a first queue and a second queue, respectively. The computerized device receives instructions to configure a table of the GSP with scheduling entries. The computerized device compares the first time stamp value with the second time stamp value to form a comparison result. The computerized device then selects a decision instruction from the table, based upon the comparison result, and identifies a preferred queue of the first queue and the second queue, based upon the decision instruction.

Methods and apparatus for scheduling operation of a data source

One or more queues store data information such as packets or data flows for later transmission to downstream communication devices. A real-time clock tracks current time and an advancement of a moving time reference, which is displaced with respect to the current time of the clock by an offset value. Thus, as current time advances, the moving time reference also advances in time. Upon servicing a queue, a time stamp associated with the serviced queue is also advanced in time. To monitor a rate of outputting data from the one or more queues, a processor device at least occasionally adjusts the offset value so that the moving time reference and values of the time stamps advance in relation to each other. Consequently, by tracking a relative time difference between current time of the real-time clock and a relative advancement of time stamps, a rate of outputting data information from the queue is monitored over time.

Growing community of inventors

Dunstable, MA, United States of America

Gregory S Goss