Hierarchical fair scheduling algorithm in a distributed measurement system

• US 7,860,918 B1
• Filed: 07/25/2006
• Issued: 12/28/2010
• Est. Priority Date: 06/01/2006
• Status: Expired due to Fees

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Lloyd, Michael Alan, Karam, Mansour, Baldonado, Omar Castillo, Pulido, Jose-Miguel
• Primary Examiner(s): NGUYEN, PHUOC H
• Application Number:
  US11/459,834
• Time in Patent Office: 1,617 Days
• Field of Search: 709/201, 709/223, 709/224
• US Class Current: 709/201
• CPC Class Codes: H04L 43/50 Testing arrangements

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.

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.

2. The method of claim 1, wherein the memberships of the first and second sets of objects are not coprime.

3. The method of claim 2, wherein step (b2) is performed using the following algorithm:

i=i+1 (mod(Na)); and

j=j+1 (mod(M)); and

wherein step (b3) is performed using the following algorithm;

i=i+1 (mod(N−

Na))+Na; and

j=j+1 (mod(M));

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, wherein M is the number of members in the second set, wherein Na is coprime to M, and wherein N−

Na is coprime with M.

4. The method of claim 1, further comprising:

(e) reordering the plurality of groupings of identifiers.

5. The method of claim 1, wherein step (d) comprises:

(d1) selecting a first identifier grouping in the plurality of groupings of identifiers;

(d2) generating a pseudo-random number;

(d3) converting the pseudo-random number into a floating point number;

(d4) converting the floating point number into a delta value; and

(d5) combining the delta value with at least one of a selected time interval and clock value to provide a scheduled time for a first event corresponding to the first identifier grouping.

6. The method of claim 1, wherein step (b2) is further performed using the following algorithm:

i=k+1 mod(M);

j=(k+l)+1 Mod(Na);

wherein k and l are whole numbers selected such that l<

Greatest Common Divisor and (Na, M) and (k<

Least Common Multiple (Na, M); and

wherein step (b3) is performed using the following algorithm;

i=k′

+1 mod(M);

j=(k′

+l′

)+1 mod(N−

Na)+Na; and

wherein k′ and

l′

are whole numbers selected such that l′

<

Greatest Common Divisor and (N−

Na, M) and (k′

<

Least Common Multiple (N−

Na, M).

7. The system of claim 1, wherein operation (b2) is performed using the following algorithm:

i=(P)(K)+A+1 mod(M);

j=(Q)(K)+l+B+1 mod(Na);

wherein K and l are whole numbers selected such that l<

Greatest Common Divisor (Na, M) and K<

Least Common Multiple (Na,M), wherein P is an integer selected to be coprime with M, Q is an integer selected to be coprime with Na, A is an integer between 0 and (M−

1), and B is an integer between 0 and (Na−

1); and

wherein step (b3) is performed using the following algorithm;

i=(P′

)(k′

)+A′

+1 mod(M)

j=(Q′

)(k′

)+l+B′

+1 mod(N−

Na)+Na

wherein k′ and

l′

are whole numbers selected such that l′

<

Greatest Common Divisor (N−

Na, M) and k′

<

Least Common Multiple (N−

Na, M), wherein P′

is an integer selected to be coprime with M, wherein Q is an integer selected to be coprime with (N−

Na), A′

is an integer selected to be between 0 and (M−

1), and B′

is an integer selected to be between 0 and (N−

Na)−

1; and

wherein Q, P, A, B, P′

, Q′

, A′ and

B′

can be changed from one cycle to the next.

8. The method of claim 1, where step (a) comprises assigning identifiers to the first and second sets of objects at random.

9. A non-transitory computer readable medium comprising processor executable instructions to perform all the steps of claim 1.

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.

12. The method of claim 11, wherein the memberships of the first and second sets of objects are not coprime.

13. The method of claim 11, wherein step (b2) is performed using the following algorithm:

i=i+1 (mod(Na));

j=j+1 (mod(M));

wherein step (b3) is performed using the following algorithm;

i=i+1 (mod(N−

Na))+Na;

j=j+1 (mod(M)); and

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, wherein M is the number of members in the second set, wherein Na is coprime to M, and wherein N−

Na is coprime with M.

14. The method of claim 11, wherein step (b2) is further performed using the following algorithm:

i=k+1 mod(M);

j=(k+l)+1 Mod(Na);

wherein k and l are whole numbers selected such that l<

Greatest Common Divisor and (Na, M) and (k<

Least Common Multiple (Na, M);

wherein step (b3) is performed using the following algorithm;

i=k′

+1 mod(M);

j=(k′

+l′

)+1 mod(N−

Na)+Na; and

wherein k′ and

l′

are whole numbers selected such that l′

<

Greatest Common Divisor and (N−

Na, M) and (k′

<

Least Common Multiple (N−

Na, M).

15. The method of claim 11, wherein step (b2) is further performed using the following algorithm:

i=(P)(K)+A+1 mod(M);

j=(Q)(K)+l+B+1 mod(Na);

wherein K and l are whole numbers selected such that l<

Greatest Common Divisor (Na, M) and K<

Least Common Multiple (Na, M), wherein P is an integer selected to be coprime with M, Q is an integer selected to be coprime with Na, A is an integer between 0 and (M−

1), and B is an integer between 0 and (Na−

1);

wherein step (b3) is performed using the following algorithm;

i=(P′

)(k′

)+A′

+1 mod(M);

j=(Q′

)(k′

)+l′

+B′

+1 mod(N−

Na)+Na;

wherein k′ and

l′

are whole numbers selected such that l′

<

Greatest Common Divisor (N−

Na, M) and k′

<

Least Common Multiple (N−

Na, M), wherein P′

is an integer selected to be coprime with M, wherein Q′

is an integer selected to be coprime with (N−

Na), A′

is an integer selected to be between 0 and (M−

1), and B′

is an integer selected to be between 0 and (N−

Na)−

1; and

wherein Q, P, A, B, Q′

, B′

, A′ and

B′

can be changed from one cycle to the next.

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.

17. The system of claim 16, wherein the memberships of the first and second sets of objects are not coprime.

18. The system of claim 16, wherein operation (b2) is performed using the following algorithm:

i=i+1 (mod(Na)); and

j=j+1 (mod(M)); and

wherein operation (b3) is performed using the following algorithm;

i=i+1 (mod(N−

Na))+Na; and

j=j+1 (mod(M));

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, wherein M is the number of members in the second set, wherein Na is coprime to M, and wherein N−

Na is coprime with M.

19. The system of claim 16, wherein operation (b2) is performed using the following algorithm:

i=k+1 mod(M);

j=(k+l)+1 Mod(Na);

wherein k and l are whole numbers selected such that l<

Greatest Common Divisor (Na, M) and k Least Common Multiple (Na,M); and

wherein step (b3) is performed using the following algorithm;

i=k′

+1 mod(M);

j=(k′

+l′

)+1 mod(N−

Na)+Na; and

wherein k′ and

l′

are whole numbers selected such that l′

<

Greatest Common Divisor and (N−

Na, M) and (k′

<

Least Common Multiple (N−

Na, M).

20. The system of claim 16, wherein operation (b2) is performed using the following algorithm:

i=(P)(K)+A+1 mod(M);

j=(Q)(K)+l+B+1 mod(Na);

wherein K and l are whole numbers selected such that l<

Greatest Common Divisor (Na, M) and K<

Least Common Multiple (Na,M), wherein P is an integer selected to be coprime with

M, Q is an integer selected to be coprime with Na, A is an integer between 0 and (M−

1), and B is an integer between 0 and (Na−

1); and

wherein step (b3) is performed using the following algorithm;

i=(P′

)(k′

)+A′

+1 mod(M)

j=(Q′

)(k′

)+l′

+B′

+1 mod(N−

Na)+Na

wherein k′ and

l′

are whole numbers selected such that l′

<

Greatest Common Divisor (N−

Na, M) and k′

<

Least Common Multiple (N−

Na, M), wherein P′

is an integer selected to be coprime with M, wherein Q is an integer selected to be coprime with (N−

Na), A′

is an integer selected to be between 0 and (M−

1), and B′

is an integer selected to be between 0 and (N−

Na)−

1; and

wherein Q, P, A, B, P′

, Q′

, A′ and

B′

can be changed from one cycle to the next.