×

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
First Claim
Patent Images

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 all claims
  • 9 Assignments
Timeline View
Assignment View
    ×
    ×