US 7,733,895 B2 · Non-preemptive scheduling in network elements

Abstract

A graph based on a data traffic matrix represents the occupancy of a set of virtual output queues to an optical crosspoint packet data switch. Edges in the graph are assigned to a matching in order of decreasing weight, provided that the edges do not conflict with other edges previously placed in the matching. If a conflict is found for a particular edge, a new matching is created and the conflicting edge is placed in the new matching. The process iterates until all edges are covered, resulting in creating a collection of matchings. The collection of matchings is transformed into a schedule such that each matching defines a switch configuration and the weight of the heaviest edge determines its holding time. The length of the obtained schedule equals the total cost of the collection. The cost of the collection is the total weight of the matchings plus the product of the re-configuration delay and the number of matchings.

Claims32

Dependent claims

A method providing non-preemptive scheduling in a network element, comprising the computer-implemented steps of:

creating and storing a graph, wherein edges represent cells of an optical crossbar switch directed from inputs to outputs thereof, wherein each of the edges has an associated weight value, wherein weight values represent occupancy of a corresponding input queue of the optical switch;
creating and storing a matching that includes a plurality of edges;
adding, to the matching, all edges that are compatible with the matching, in order of decreasing weight;
marking in the graph as covered all the edges that have been added to the matching;
and
repeating the preceding three steps until all the edges in the graph are covered;
wherein the computer-implemented steps are performed by one or more computing devices comprising one or more processors.

4 more elements

A method providing non-preemptive scheduling in a network element, comprising the computer-implemented steps of:

creating and storing a traffic demand matrix, wherein rows of the matrix represent inputs to an optical crossbar switch, columns of the matrix represent outputs, and values in the matrix represent quantities of cells directed from associated inputs to associated outputs;
creating and storing a graph based on the traffic demand matrix, wherein edges represent cells of an optical crossbar switch directed from inputs to outputs thereof, wherein each of the edges has an associated weight value, wherein weight values represent occupancy of a corresponding input queue of the optical switch;
creating and storing a first matching that includes a plurality of edges;
identifying a heaviest uncovered edge in the graph and placing the heaviest uncovered edge in the first matching;
creating one or more other matchings;
adding, to a particular one of the other matchings, all other edges that are compatible with that particular matching, in order of decreasing weight;
marking in the graph as covered all the edges that have been added to the matching;
and
repeating the preceding three steps until all the edges in the graph are covered;
selecting a maximum of the weights of all edges in a matching as a holding time value for the matching;
creating and storing a schedule for the optical crossbar switch, wherein the schedule comprises all the matchings and associated holding time values;
wherein the computer-implemented steps are performed by one or more computing devices comprising one or more processors.

9 more elements

An apparatus providing non-preemptive scheduling in a network element, comprising:

one or more processors;
means for creating and storing a traffic demand matrix, wherein rows of the matrix represent inputs to an optical crossbar switch, columns of the matrix represent outputs, and values in the matrix represent quantities of cells directed from associated inputs to associated outputs;
means for creating and storing a graph based on the traffic demand matrix, wherein edges represent cells of an optical crossbar switch directed from inputs to outputs thereof, wherein each of the edges has an associated weight value, wherein weight values represent occupancy of a corresponding input queue of the optical switch;
means for creating and storing a first matching that includes a plurality of edges;
means for identifying a heaviest uncovered edge in the graph and placing the heaviest uncovered edge in the first matching;
means for creating one or more other matchings;
means for adding, to a particular one of the other matchings, all other edges that are compatible with that particular matching, in order of decreasing weight;
means for marking in the graph as covered all the edges that have been added to the matching;
and
means for repeating the functions of the preceding three means until all the edges in the graph are covered;
means for selecting a maximum of the weights of all edges in a matching as a holding time value for the matching;
means for creating and storing a schedule for the optical crossbar switch, wherein the schedule comprises all the matchings and associated holding time values.

9 more elements

One or more computer-readable storage media storing instructions which, when executed by one or more processors, cause the one or more processors to:

create and store a graph, wherein edges represent cells of an optical crossbar switch directed from inputs to outputs thereof, wherein each of the edges has an associated weight value, wherein weight values represent occupancy of a corresponding input queue of the optical switch;
create and store a matching that includes a plurality of edges;
add, to the matching, all edges that are compatible with the matching, in order of decreasing weight;
mark in the graph as covered all the edges that have been added to the matching;
and
repeat the preceding three steps until all the edges in the graph are covered;
wherein the instructions are to be executed by one or more computing devices comprising one or more processors.

4 more elements

One or more computer-readable storage media storing instructions which, when executed by one or more processors, cause the one or more processors to:

create and store a traffic demand matrix, wherein rows of the matrix represent inputs to an optical crossbar switch, columns of the matrix represent outputs, and values in the matrix represent quantities of cells directed from associated inputs to associated outputs;
create and store a graph based on the traffic demand matrix, wherein edges represent cells of an optical crossbar switch directed from inputs to outputs thereof, wherein each of the edges has an associated weight value, wherein weight values represent occupancy of a corresponding input queue of the optical switch;
create and store a first matching that includes a plurality of edges;
identify a heaviest uncovered edge in the graph and placing the heaviest uncovered edge in the first matching;
create one or more other matchings;
add, to a particular one of the other matchings, all other edges that are compatible with that particular matching, in order of decreasing weight;
mark in the graph as covered all the edges that have been added to the matching;
and
repeat the preceding three steps until all the edges in the graph are covered;
select a maximum of the weights of all edges in a matching as a holding time value for the matching;
create and store a schedule for the optical crossbar switch, wherein the schedule comprises all the matchings and associated holding time values;
wherein the instructions are to be executed by one or more computing devices comprising one or more processors.

9 more elements

Dependencies are inferred from the claim text.

Non-preemptive scheduling in network elements

Life of this patent

Non-preemptive scheduling in network elements

Life of this patent

Abstract

Claims32