SYSTEM AND METHOD OF REAL-TIME CONTROL AND SCHEDULING FOR ZERO-QUEUE DISTRIBUTED SYSTEMS

• US 20080130660A1
• Filed: 10/18/2007
• Published: 06/05/2008
• Est. Priority Date: 10/19/2006
• Status: Abandoned Application

• Current Assignee: IST International Incorporated
• Original Assignee: IST International Incorporated
• Inventors: Tsai, Wei K., ROS-GIRALT, JORDI
• Application Number:
  US11/874,756
• Publication Number:
  US 20080130660A1
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A system and method is provided that comprise a logical central controller; and a plurality of logical nodes; wherein a demand is performed such that to transport various commodities from a first set of at least one nodes among the plurality of logical nodes to a second set of at least one node of the plurality of logical nodes is achieved; and wherein said nodes are interconnected by directed links according to a graph, said commodities are allowed to be transported only on said directed links, simultaneous arrival (referred to as collision) of commodities at a node is lost, each transportation of said commodities across a directed link incurs.

Claims

1. A system comprising:

a logical central controller; and

a plurality of logical nodes;

wherein a demand is performed such that to transport various commodities from a first set of at least one nodes among the plurality of logical nodes to a second set of at least one node of the plurality of logical nodes is achieved; and

wherein said nodes are interconnected by directed links according to a graph, said commodities are allowed to be transported only on said directed links, simultaneous arrival (referred to as collision) of commodities at a node is lost, each transportation of said commodities across a directed link incurs a penalty of delay, and each commodity is transported via a fixed and unique path.

2. The system of claim 1 wherein nodes are of two types:

QoS type and non-QoS type, and the QoS type nodes must satisfy a plurality of real-time quality of service (QoS) measures, and the purpose of the system (called control system) is to exercise control to achieve system wide real-time QoS objectives.

3. The system of claim 2 wherein the commodities are data frames in a digital system.

4. The system of claim 3 wherein the control system schedules the sending of all data frames via a global clock realized with a global clock synchronization method.

5. The system of claim 4 wherein the control system schedules the sending of all data frames via a time division multiplexing method at the IP layer.

6. The system of claim 5 wherein the central controller uses sender-to-receiver delays, QoS type information, and QoS requirements to determine the schedule to allow real-time transmitting of data frames from QoS nodes, and real-time limiting of data frame transmissions from non-QoS nodes.

7. The system of claim 6 wherein the control system uses an adaptive algorithm to adjust begin times, end times, and guard times of all transmissions of QoS type to avoid collisions and achieve certain real-time QoS objectives, based on feedback from a plurality of receivers of data frames.

8. The system of claim 7 wherein the network of nodes forms a WiFi network or a network of Ethernet local area networks.

9. The system of claim 8 wherein a space-time trace of a schedule is formed by following the scheduled transmissions sequentially over time and connecting the directed links traversed sequentially.

10. The system of claim 9 wherein the control system chooses a schedule only if the corresponding space-time trace does not form a directed cycle.

11. The system of claim 10 wherein all feasible space-time traces contain a directed cycle, the control system chooses a guard time equal to the total delay in a directed cycle that exists in a space-time trace, and in particular, the system chooses the minimum delay traversed in the said directed cycles.

12. The system of claim 11 wherein the control system includes a QoS admission server to administer rejection and admission of live QoS nodes.

13. The system of claim 12 wherein an objective of the QoS admission server is to ensure feasibility of finding a schedule to satisfy the real-time QoS objectives.

14. The system of claim 13 wherein if a time slot is allotted to a QoS node but the node does not use up the allotted time, then all the QoS nodes in the current round in the schedule, following the node that does not use up the allotted time, are allowed to begin transmissions earlier by a constant or predetermined time period.

15. The system of claim 14 wherein the control system uses a two-phase approach, wherein the first phase uses global clock synchronization to establish a reference schedule, and the second phase uses incremental adjustments to fine-tune the schedule in an adaptive and convergent algorithm.

16. The system of claim 8 wherein each QoS transmission is preceded immediately by a special (called head) beacon and followed immediately by a special (called trail) beacon.

17. The system of claim 16 wherein the special head and trail beacons contain enough error correction coding to ensure proper receptions even at high noise at the intended receivers, assuming no collisions at the respective receivers.

18. The system of claim 17 wherein the positions of the special head and trail beacons are used as feedback to the adaptive algorithm to adjust the transmission schedule for the next round.

19. A method comprising the steps of:

providing a logical central controller;

providing a plurality of logical nodes; and

demanding to transport various commodities from a first set of at least one nodes among the plurality of logical nodes to a second set of at least one node of the plurality of logical nodes;

wherein said nodes are interconnected by directed links according to a graph, said commodities are allowed to be transported only on said directed links, simultaneous arrival (referred to as collision) of commodities at a node is lost, each transportation of said commodities across a directed link incurs a penalty of delay, and each commodity is transported via a fixed and unique path.

20. The method of claim 19, wherein nodes are of two types:

QoS type and non-QoS type, and the QoS type nodes must satisfy a plurality of real-time quality of service (QoS) measures, and the purpose of the system and method (called control system) is to exercise control to achieve system wide real-time QoS objectives.