Network scheduler for real time applications

Details Network scheduler for real time applications Network scheduler for real time applications

1999-04-30

2004-10-05

Vu, Viet D. (Department: 2154)

Electrical computers and digital processing systems: multicomput

Computer network managing

Network resource allocating

C718S103000, C719S314000, C719S321000

Reexamination Certificate

active

06801943

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to real time applications and more specifically to a network scheduler for such applications.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright© 1998, 1999 Honeywell, Inc., All Rights Reserved.
BACKGROUND OF THE INVENTION
Real time systems comprise programs that must execute relative to priorities or within strict constraints on response time. Some examples of real-time systems include industrial plant controllers, medical monitors, communications networks, and aircraft or spacecraft flight control systems. One difficulty in designing real-time systems is in the strict requirement to meet processing deadlines and not in the actual speed of processing. A real-time system need not be complex or high performance. Checking radioactivity levels in a nuclear power plant or checking a pulse rate on a medical patient may require only simple processing. However, a failure to meet a processing deadline, such as decreasing plant power or sounding a medical alarm, can be literally fatal.
One example of a real time system is a multimedia system. Multimedia is increasingly recognized as an enabling technology with diverse applications from interactive training to medical diagnosis to control applications, for example. In the context of control applications, the term “multimedia” implies a much broader scope than the traditional usage of the term that refers to audio, video and text. In the context of control applications, multimedia encompasses both the traditional multimedia data as well as image data and spectral data. Image data refers to still images, full-motion video, and graphics. Image data is obtained from sources such as video, X-ray, and scanning electron microscopy to name a few. Spectral data refers to sensor data. Spectral data is obtained from sources such as infrared, color, acoustic emission, ultrasound, microwave, laser, and optical sensors and devices, for example.
A multimedia-based control system imposes stringent requirements on a network. A key network requirement for multimedia-based control systems is that the underlying network must support real time tasks. Performance criteria for a network in such a control system are very different than those of a typical information network. Some basic performance criteria for a control network are (1) the guarantee of critical traffic, (2) the avoidance of priority inversion, and (3) the guarantee of deadlines. Priority inversion occurs when a lower priority task is allocated the resources before a higher priority task.
When scheduling real time tasks in a network, a priority or a deadline is associated with the task. For many real time tasks, failure to meet the deadline or failure to avoid priority inversion is considered a system fault. The priority or the deadline associated with a task is commonly specified globally at the user or application level. However, a kernel-level scheduling mechanism does not allow users or applications to exercise control over scheduling policies. As a result, user or application-level scheduling policies fail when kernel-level scheduling cannot enforce the same policy.
For these and other reasons, there is a need for a mechanism to guarantee correct scheduling order of real time tasks according to the user or application specified priorities or deadlines.
SUMMARY OF THE INVENTION
A network scheduler for real time applications is described. According to one aspect of the invention, a network scheduler acts as a proxy scheduler across different scheduling domains for the purpose of achieving correct deadline and priority based scheduling of network packets. An application specifies real time requirements in terms of deadlines or periodicities. An appropriate scheduling algorithm is applied based on the application task periodicities and deadlines. Simple primitives excercise control over operating system threads over scheduling domains to control their suspension and execution. The scheduling mechanism functions as a middleware system.
Another aspect of the invention is a scheduling method for an application distributed across a plurality of processing nodes. The scheduling method comprises a proxy scheduling mechanism at every node between the boundaries of a plurality of scheduling domains within a processing node. The scheduling method achieves overall end to end deadline and priority based scheduling for distributed real time applications running over a plurality of processing nodes with multiple scheduling domains.
The present invention is applicable to a variety of operating system platforms and middleware solutions for real time systems. The present invention allows user-level defined attributes, such as priorities and deadlines, and desirably overcomes constraints resulting from vendor specific operating system mechanisms that do not preserve such user specified attributes of real time behavior. The primitives of the invention allow various scheduling policies such as priority based or deadline based scheduling policies.
Still other and further embodiments, aspects and advantages of the invention will become apparent by reference to the drawings and by reading the following detailed description.


REFERENCES:
patent: 5109515 (1992-04-01), Laggis et al.
patent: 5732087 (1998-03-01), Lauer et al.
patent: 5812844 (1998-09-01), Jones et al.
patent: 5946487 (1999-08-01), Dangelo
patent: 5991790 (1999-11-01), Shah et al.
patent: 6065037 (2000-05-01), Hitz et al.
patent: 6076174 (2000-06-01), Freund
patent: 6157955 (2000-12-01), Narad et al.
patent: 6223204 (2001-04-01), Tucker
patent: 6289369 (2001-09-01), Sundaresan
patent: 6418460 (2002-07-01), Bitar et al.
patent: 6587865 (2003-07-01), Kimbrel et al.
patent: 0554615 (1993-08-01), None
Abbott, R.K., et al., “Scheduling I/O Requests with Deadlines: a Performance Evaluation”,IEEE,pp. 113-124, (1990).
Arvind, K., et al., “A Local Area Network Architecture for Communication in Distributed Real-Time Systems,”,The Journal of Real-Time Systems, 3(2), pp. 115-147, (May. 1991).
Biyabani, S.R., et al., “The Integration of Deadline Criticalness in Hard Real-Time Scheduling”,Proceedings: Real-Time Systems Symposium,Huntsville, Albama, pp. 152-160, (1988).
Boyer, P.E., et al., “A reservation principle with applications to the ATM traffic control”,Computer Networks and ISDN Systems, 24,North-Holland, pp. 321-334, (1992).
Chipalkatti, R., et al., “Scheduling Policies for Real-Time and Non-Real-Time Traffic in a Statistical Multiplexer”,IEEE Infocom, The Conference on Computer Communications,pp. 774-783, (1989).
Chung, J., et al., “Algorithms for Scheduling Periodic Jobs to Minimize Average Error”,Proceedings: Real-Time Systems, Symposium,Huntsville, Alabama, pp. 142-151, (1988).
Chung, J., et al., “Scheduling Periodic Jobs that Allow Imprecise Results,”,IEEE Transactions on Computers, 39(9), pp. 1156-1174, (Sep. 1990).
Clark, D.D., et al., “Supporting Real-Time Applications in an Integrated Servies Packet Network: Architecture and Mechanism”,Computer Communications Review, 22(4), pp. 14-26, (Oct. 1992).
Coulson, G., et al., “Protocol Support for Distributed Multimedia Applications”,Network and Operating System Support for Digital Audio and Video,Heidelberg, Germany, pp. 45-56, (1991).
Ferrari, D., “Client Requirements for Real-Time Communication Services”,IEEE Communications Magazine, 28(11), pp. 65-72, (Nov. 1990).
Ferrari, D., et al., “A Scheme for Real-Time Channel Establishment in Wide-Area Networks”,IEEE Journal of Selected Areas in Communications, 8(3), pp. 368-379, (Apr. 1990).
Gallassi, G., et al., “ATM: Bandwith Assignment and Bandwidth E

Affiliated with

Also associated with

Rating

Network scheduler for real time applications does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Network scheduler for real time applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network scheduler for real time applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3329212