System and method for multi-dimensional resource scheduling

• US 5,978,363 A
• Filed: 10/18/1996
• Issued: 11/02/1999
• Est. Priority Date: 10/18/1996
• Status: Expired due to Term

• Current Assignee: Telogy Networks, Inc. (Texas Instruments, Inc.)
• Original Assignee: Telogy Networks, Inc. (Texas Instruments, Inc.)
• Inventors: Dimitrijevic, Dragomir D., Berisford, Dale
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Myhre, James W.
• Application Number:
  US08/733,475
• Time in Patent Office: 1,110 Days
• Field of Search: 370/316, 370/317, 370/318, 370/319, 370/320, 370/325, 455/12, 455/13
• US Class Current: 370/319
• CPC Class Codes: H04B 7/18539 Arrangements for managing radio, resources, i.e. for establishing or releasing a connection
• CPC Class Codes: H04B 7/18543 for adaptation of transmission parameters, e.g. power control for detecting or preventing errors in the information received H04L1/00
• CPC Class Codes: H04B 7/212 Time-division multiple access [TDMA]

Abstract

A system and method is presented for multi-dimensional scheduling, unscheduling, and control of resources using a database approach. Indivisible resources, percentage divisible resources, and range divisible resources are scheduled, unscheduled, and controlled. Resources in telecommunication systems are scheduled, unscheduled, and controlled. Resources in satellite telecommunication systems are scheduled, unscheduled, and controlled.

Claims

1. A satellite communication system comprising:

a. at least one telecommunication satellite in orbit,

b. at least one ground site, communicating with said at least one satellite,

c. at least one first control modem communicating with each said at least one ground site,

d. at least one third party modem communicating with each said first control modem,

e. a network management ground site communicating with the satellites,

f. a second control modem electronically communicating with the network management ground site,

g. a network management center electronically communicating with the second control modem,

h. a scheduling terminal computer electronically communicating with the network management center,

i. scheduling and control software in the scheduling terminal computer with algorithms for multidimensional scheduling and unscheduling of (a) indivisible resources, (b) percentage divisible resources, and (c) range divisible resources, and

j. a database in the scheduling terminal computer containing data regarding the status of resources of the satellite system, and schedules for the use of such resources, wherein

(A) the algorithm for scheduling the use of an indivisible resource, comprises;

(Aa) receiving a request to schedule an indivisible resource for a requested interval,

(Ab) searching in a resource database for an available record that matches the request, and, if such an available record is not found, rejecting the request, otherwise,

(Ac) if an available record is found, making the available record unavailable for the requested interval,

(Ad) creating a new record for any portion of the available record prior to the requested interval, and

(Ae) creating a new record for any portion of the available record after the requested interval; and

(B) the algorithm for scheduling the use of a percentage divisible resource, the process comprises;

(Ba) receiving a request to schedule a percentage divisible resource,

(Bb) searching all database records corresponding to a time period to be effected by the request, and, if the available resource level is inadequate in any such records, then rejecting the request, otherwise,

(Bc) for each record that would be effected by satisfying the request, adjusting the available level up for any amount requested to be unscheduled, and adjusting the available resource level down for any resource requested to be scheduled,

(Bd) creating a new record for any time slot prior to the time of the time period to be effected by the requests with an uncharged level of the available resource, and merging the new prior record with any left slot with the same level of resource available, and

(Be) creating a new record for any time slot following the time of the time period to be effected by the requests with an uncharged level of the available resource, and merging the new following record with any right slot with the same level of resource available; and

(C) the algorithm for scheduling the use of a range divisible resource comprises;

(Ca) receiving a request to schedule a range divisible resource,

(Cb) searching for an available record in a resource database with time and range that matches the request, and if no such record is found, rejecting the request, otherwise

(Cc) finding all slots that intersect the requested slot,

(Cd) for each such intersecting slot, creating a new database record in a temporary table,

(Ce) deleting all slots that intersect the requested slot, and adding an unavailable database record for the requested slot, and

(Cf) running an unload temporary table routine, moving unaffected pieces of intersecting slots to the schedule table as new records and merging such new records with contiguous larger slots.

2. The system in claim 1, wherein

(D) the algorithm for unscheduling the use of an indivisible resource comprises:

(Da) receiving a request to unschedule an indivisible resource for a time period,

(Db) searching for a scheduled record for that resource in a resource database that matches the time period for the request, and if such a record is not found, rejecting the request, otherwise

(Dc) searching for a immediately prior available record for the scheduled resource which ends when the resource which is about to be unscheduled starts,

(Dd) searching for a immediately subsequent available record for the scheduled resource which starts when the resource which is about to be unscheduled ends,

(De) if there is no immediately prior available record and no immediately subsequent available record, then changing the scheduled record to available, otherwise

(Df) if there is a immediately prior available record and no immediately subsequent available record, then deleting the immediately prior available record, expanding the scheduled record to include the immediately prior available record, and changing the scheduled record to available, and otherwise,

(Dg) if there is a immediately subsequent available record and no immediately prior available record, deleting the immediately subsequent available record, expanding the scheduled record to include the immediately subsequent available record, and changing the scheduled record to available, and

(E) the algorithm for unscheduling the use of a range divisible resource comprises;

(Ea) receiving a request to unschedule a range divisible resource,

(Eb) searching for an available database record matching the requested resource, and, if no such record exists, rejecting the request, otherwise,

(Ec) deleting the record for the requested slot,

(Ed) determining how far the unscheduled slot may be extended, and adding all such records to a temporary table,

(Ee) finding all slots adjacent to the unscheduled slot,

(Ef) for all slots adjacent to the left of the unscheduled slot, determining how far the adjacent slots can be extended to the right, and creating a new slot if possible, then going to step Ej,

(Eg) for all slots adjacent to right of the unscheduled slot, determining how far the adjacent slots can be extended to the left, and creating a new slot if possible, then going to step Ej,

(Eh) for all slots adjacent below the unscheduled slot, determining how far the adjacent slots can be extended up, and creating a new slot if possible, then going to step Ej,

(Ei) for all slots adjacent above the unscheduled slot, determining how far the adjacent slots can be extended down, and creating a new slot if possible, then going to step Ej,

(Ej) deleting all found adjacent slots from the temporary table, adding modified records to the temporary table, and adding new records to the temporary table, and

(Ek) eliminating duplicate records and subset records from the temporary table and transferring other records from the temporary table to the schedule table.

3. A satellite communication system comprising:

a. at least one telecommunication satellite in orbit,

b. at least one ground site, communicating with said at least one satellite,

c. at least one first control modem communicating with each said at least one ground site,

d. at least one third party modem communicating with each said first control modem,

e. a network management ground site communicating with the satellites,

f. a second control modem electronically communicating with the network management ground site,

g. a network management center electronically communicating with the second control modem,

h. a scheduling terminal computer electronically communicating with the network management center,

i. scheduling and control software in the scheduling terminal computer with algorithms for multidimensional scheduling and unscheduling of (a) indivisible resources, (b) percentage divisible resources, and (c) range divisible resources, and

j. a database in the scheduling terminal computer containing data regarding the status of resources of the satellite system, and schedules for the use of such resources, wherein

the algorithm for scheduling the use of an indivisible resource, comprises;

(a) receiving a request to schedule an indivisible resource for a requested interval,

(b) searching in a resource database for an available record that matches the request, and, if such an available record is not found, rejecting the request, otherwise,

(c) if an available record is found, making the available record unavailable for the requested interval,

(d) creating a new record for any portion of the available record prior to the requested interval, and

(e) creating a new record for any portion of the available record after the requested interval.

4. A satellite communication system comprising:

a. at least one telecommunication satellite in orbit,

b. at least one ground site, communicating with said at least one satellite,

c. at least one first control modem communicating with each said at least one ground site,

d. at least one third party modem communicating with each said first control modem,

e. a network management ground site communicating with the satellites,

f. a second control modem electronically communicating with the network management ground site,

g. a network management center electronically communicating with the second control modem,

h. a scheduling terminal computer electronically communicating with the network management center,

i. scheduling and control software in the scheduling terminal computer with algorithms for multidimensional scheduling and unscheduling of (a) indivisible resources, (b) percentage divisible resources, and (c) range divisible resources, and

j. a database in the scheduling terminal computer containing data regarding the status of resources of the satellite system, and schedules for the use of such resources, wherein

the algorithm for scheduling the use of a percentage divisible resource, the process comprises;

(a) receiving a request to schedule a percentage divisible resource,

(b) searching all database records corresponding to a time period to be effected by the request, and, if the available resource level is inadequate in any such records, then rejecting the request, otherwise,

(c) for each record that would be effected by satisfying the request, adjusting the available level up for any amount requested to be unscheduled, and adjusting the available resource level down for any resource requested to be scheduled,

(d) creating a new record for any time slot prior to the time of the time period to be effected by the request, with an uncharged level of the available resource, and merging the new prior record with any left slot with the same level of resource available, and

(e) creating a new record for any time slot following the time of the time period to be effected by the request, with an uncharged level of the available resource, and merging the new following record with any right slot with the same level of resource available.

5. A satellite communication system comprising:

a. at least one telecommunication satellite in orbit,

b. at least one ground site, communicating with said at least one satellite,

c. at least one first control modem communicating with each said at least one ground site,

d. at least one third party modem communicating with each said first control modem,

e. a network management ground site communicating with the satellites,

f. a second control modem electronically communicating with the network management ground site,

g. a network management center electronically communicating with the second control modem,

h. a scheduling terminal computer electronically communicating with the network management center,

i. scheduling and control software in the scheduling terminal computer with algorithms for multidimensional scheduling and unscheduling of (a) indivisible resources, (b) percentage divisible resources, and (c) range divisible resources, and

j. a database in the scheduling terminal computer containing data regarding the status of resources of the satellite system, and schedules for the use of such resources, wherein

the algorithm for scheduling the use of a range divisible resource comprises;

(a) receiving a request to schedule a range divisible resource,

(b) searching for an available record in a resource database with time and range that matches the request, and if no such record is found, rejecting the request, otherwise

(c) finding all slots that intersect the requested slot,

(d) for each such intersecting slot, creating a new database record in a temporary table,

(e) deleting all slots that intersect the requested slot, and adding an unavailable database record for the requested slot, and

(i) running an unload temporary table routine, moving unaffected pieces of intersecting slots to the schedule table as new records and merging such new records with contiguous larger slots.