Hierarchical fair scheduling algorithm in a distributed measurement system
First Claim
1. A method for scheduling events between first and second sets of objects, comprising:
- (a) a scheduling server, comprising a processor and memory, providing identifiers to members of first and second sets of objects, the identifiers used for the members of a set being unique within that set and the identifiers being typically consecutively numbered within each set;
(b) the scheduling server using modular arithmetic to generate first and second sequences of the identifiers for each of the first and second sets, respectively, wherein the modular arithmetic is one of;
i=i+1 (mod(N));
j=j+1 (mod(M));
(b′
)wherein the first and second sets of objects are coprime, wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein N is the number of members in the first set, and wherein M is the number of members in the second set;
i=k+1 mod(N);
j=k+l+1 mod(M);
(b″
)wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein k and l are whole numbers selected such that l<
Greatest Common Divisor (N, M) and k<
Least Common Multiple (N, M), wherein N is the number of members in the first set, and wherein M is the number of members in the second set;
i=(P)(k)+A+1 mod(M);
j=(Q)(k)+l+B+1 mod(N);
(b″
′
)wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein k and l are whole numbers selected such that l<
Greatest Common Divisor (N, M) and k<
Least Common Multiple (N, M), wherein N is the number of members in the first set, wherein M is the number of members in the second set, wherein P is an integer selected to be coprime with M, wherein Q is an integer selected to be coprime with N, A is an integer selected to be between 0 and (M−
1), and B is an integer selected to be between 0 and (N−
1);
where Q, P, A and B can be changed from one cycle to the next(c) the scheduling server associating identifiers from the first and second sequences to provide a plurality of groupings of identifiers, each grouping of identifiers comprising at least one identifier from each of the first and second sequences; and
(d) the scheduling server scheduling a corresponding event for each of the grouping of identifiers.
9 Assignments
0 Petitions
Accused Products
Abstract
The present invention provides embodiments of a network monitoring system that includes a scheduling agent for generating groupings of test agents and scheduling network measurements to be performed by each test agent grouping. The system may provide identifiers to members of first and second sets of objects. Then, the system can generate first and second sequences of the identifiers for each of the first and second sets, respectively and associate the identifiers to provide a plurality of groupings of identifiers. Finally the system may schedule a corresponding event for each of the grouping of identifiers. The systems and methods present can require very little state memory, ensure fair coverage of the object groupings; and can avoid the problems associated with round robin scheduling.
-
Citations
20 Claims
-
1. A method for scheduling events between first and second sets of objects, comprising:
-
(a) a scheduling server, comprising a processor and memory, providing identifiers to members of first and second sets of objects, the identifiers used for the members of a set being unique within that set and the identifiers being typically consecutively numbered within each set; (b) the scheduling server using modular arithmetic to generate first and second sequences of the identifiers for each of the first and second sets, respectively, wherein the modular arithmetic is one of;
i=i+1 (mod(N));
j=j+1 (mod(M));
(b′
)wherein the first and second sets of objects are coprime, wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein N is the number of members in the first set, and wherein M is the number of members in the second set;
i=k+1 mod(N);
j=k+l+1 mod(M);
(b″
)wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein k and l are whole numbers selected such that l<
Greatest Common Divisor (N, M) and k<
Least Common Multiple (N, M), wherein N is the number of members in the first set, and wherein M is the number of members in the second set;
i=(P)(k)+A+1 mod(M);
j=(Q)(k)+l+B+1 mod(N);
(b″
′
)wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein k and l are whole numbers selected such that l<
Greatest Common Divisor (N, M) and k<
Least Common Multiple (N, M), wherein N is the number of members in the first set, wherein M is the number of members in the second set, wherein P is an integer selected to be coprime with M, wherein Q is an integer selected to be coprime with N, A is an integer selected to be between 0 and (M−
1), and B is an integer selected to be between 0 and (N−
1);where Q, P, A and B can be changed from one cycle to the next (c) the scheduling server associating identifiers from the first and second sequences to provide a plurality of groupings of identifiers, each grouping of identifiers comprising at least one identifier from each of the first and second sequences; and (d) the scheduling server scheduling a corresponding event for each of the grouping of identifiers. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A system for scheduling an event, comprising:
a scheduling server, comprising; a memory; a processor in communication with the memory, the processor operable to execute a scheduling agent, the scheduling agent operable to; (a) provide identifiers to members of first and second sets of objects, the identifiers used for the members of a set being unique within that set and the identifiers being consecutively numbered within each set; (b) use modular arithmetic to generate first and second sequences of the identifiers for each of the first and second sets, respectively, wherein the modular arithmetic is one of;
i=i+1 (mod(N));
j=j+1 (mod(M));
(b′
)wherein the first and second sets of objects are coprime, wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein N is the number of members in the first set, and wherein M is the number of members in the second set;
i=k+1 mod(N);
j=k+l+1 mod(M);
(b″
)wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein k and l are whole numbers selected such that l<
Greatest Common Divisor (N, M) and k<
Least Common Multiple (N, M), wherein N is the number of members in the first set, and wherein M is the number of members in the second set;
i=(P)(k)+A+1 mod(M);
i=(Q)(k)+l+B+1 mod(N);
(b″
′
)wherein i is the identifier for a selected object in the first set, j is the identifier for a selected object in the second set, wherein k and l are whole numbers selected such that l<
Greatest Common Divisor (N, M) and k<
Least Common Multiple (N, M), wherein N is the number of members in the first set, wherein M is the number of members in the second set, wherein P is an integer selected to be coprime with M, wherein Q is an integer selected to be coprime with N, A is an integer selected to be between 0 and (M−
1), and B is an integer selected to be between 0 and (N−
1);(c) associate identifiers from the first and second sequences to provide a plurality of groupings of identifiers, each grouping of identifiers comprising at least one identifier from each of the first and second sequences; and (d) schedule a corresponding event for each of the grouping of identifiers.
-
11. A method for scheduling events between first and second sets of objects, comprising:
-
(a) a scheduling server, comprising a processor and memory, providing identifiers to members of first and second sets of objects, the identifiers used for the members of a set being unique within that set and the identifiers being typically consecutively numbered within each set; (b) the scheduling server using modular arithmetic to generate first and second sequences of the identifiers for each of the first and second sets, respectively, wherein generating the first and second sequences comprises; (b1) dividing the first set into at least first and second subsets of objects, wherein the memberships of the at least first and second subsets of objects are coprime with the membership of the second set of objects; (b2) using modular arithmetic to generate first and second partial sequences of the identifiers for each of the first subset and second set, respectively; (b3) using modular arithmetic to generate third and fourth partial sequences of the identifiers for each of the second subset and second set, respectively, wherein the first sequence includes the first and third partial sequences and the second sequence includes the second and fourth partial sequences; (c) the scheduling server associating identifiers from the first and second sequences to provide a plurality of groupings of identifiers, each grouping of identifiers comprising at least one identifier from each of the first and second sequences; and (d) the scheduling server scheduling a corresponding event for each of the grouping of identifiers. - View Dependent Claims (12, 13, 14, 15)
-
-
16. A system for scheduling an event, comprising:
a scheduling server, comprising; a memory; and a processor in communication with the memory, the processor operable to execute the scheduling server executing a scheduling agent,; and
the scheduling agent operable to;(a) provide identifiers to members of first and second sets of objects, the identifiers used for the members of a set being unique within that set and the identifiers being consecutively numbered within each set; (b) use modular arithmetic to generate first and second sequences of the identifiers for each of the first and second sets, respectively, wherein using modular arithmetic comprises; (b1) dividing the first set into at least first and second subsets of objects, wherein the memberships of the at least first and second subsets of objects are coprime with the membership of the second set of objects; (b2) using modular arithmetic to generate first and second partial sequences of the identifiers for each of the first subset and second set, respectively; and (b3) using modular arithmetic to generate third and fourth partial sequences of the identifiers for each of the second subset and second set, respectively, wherein the first sequence includes the first and third partial sequences and the second sequence includes the second and fourth partial sequences; (c) associate identifiers from the first and second sequences to provide a plurality of groupings of identifiers, each grouping of identifiers comprising at least one identifier from each of the first and second sequences; and (d) schedule a corresponding event for each of the grouping of identifiers. - View Dependent Claims (17, 18, 19, 20)
Specification