Electrical computers and digital processing systems: multicomput – Miscellaneous
Reexamination Certificate
2000-09-05
2004-04-27
Meky, Moustafa M. (Department: 2157)
Electrical computers and digital processing systems: multicomput
Miscellaneous
C709S226000
Reexamination Certificate
active
06728749
ABSTRACT:
GOVERNMENT INTEREST
The invention described herein may be made, used and licensed by the United Sates for governmental purposes without paying me any royalty.
BACKGROUND OF THE INVENTION
1. Field of the Invention
In one aspect this invention relates to scheduling techniques to be applied to a Local Area Network (LAN) system. In a further aspect this invention relates to a method of scheduling LAN operations to ensure continued operation of critical functions during an overload condition. In yet a further aspect this invention relates to the control function systems used in land combat vehicles and aircraft operation. In still another aspect, this invention relates to systems that are required to perform critical operations continuously in a harsh environment. The present invention speaks to the issue of fault tolerance in these types of systems.
2. Prior Art
In general, land vehicles and aircraft increasingly use embedded, distributed, real-time control systems to function. In particular, the more advanced land combat vehicles are migrating to LAN based computer architectures. The real time LAN in military vehicles provides the data communications infrastructure to control and monitor many different systems in the vehicle. The LAN must be designed so that time constraints associated with message transmissions can all be met under nominal conditions. However, while performing continuous operations in a harsh environment, a number of events could occur, i.e., component failure, electromagnetic interference, etc, that would result in permanent or transient faults in the network resulting in network overload. Under these conditions, it is unavoidable that some processes are not serviced in a timely manner. This may cause one or more subsystems using the LAN to fail. Not all sub-systems have the same value with respect to the use of LAN resources, especially when survival is paramount Furthermore, the value of a subsystem will change over time, depending on the system state and external conditions. Systems that are most important to the vehicle's survival should be given priority use of the LAN based on value considerations as opposed to time based considerations. Classical approaches to fault tolerance do not detect the presence of a fault until one or more subsystems fail at which time it may too late to recover.
The utilization of a particular LAN servicing several different systems is generally expressed by the formula:
U
n
=
∑
i
=
1
n
c
i
T
i
where U
n
is the utilization of a network that transmits n message streams, c
i
is the augmented transmission time for a message i, and T
i
is the inter-arrival times for message stream i. If U
n
is less than or equal to the utilization bound of the LAN for a given scheduling policy, then the scheduling policy is feasible and the LAN will meet each systems timing requirements. If U
n
exceeds the LAN's bound then the scheduling policy will cause certain messages to be transmitted late.
Military vehicles are exposed to conditions that are likely to over load the computing system of the vehicle. Examples are large EMF surges or destruction of a part of the vehicle containing LAN resources. While in the fault condition, the vehicle must still retain critical operational capabilities such as responding to an enemy attack. In an overload situation, when some operations will unavoidably be completed late, mission critical operations, must be given priority over non-mission critical operations. It is also necessary for best results that the LAN have a means to detect at an early stage when mission critical operations are in danger of being untimely in order to institute an adaptive scheduling procedure before the mission critical operations start to decay.
SUMMARY OF THE INVENTION
Briefly in the present invention, the real-time LAN of this invention connects and provides processing resources for various vehicle systems. The LAN will normally use a time based scheduling algorithm for determining which of several system messages should be transmitted next under normal conditions. Two classical examples of time based scheduling algorithms are Earliest Deadline First (EDF) and Rate Monotonic Scheduling (RMS). These classical scheduling schemes have been shown to be optimal algorithms that will provide the best possible results absent a system fault. Since each system in the vehicle has a need to transmit real-time messages via the LAN, these classical scheduling methods can be used to order the transmission of the pending messages. The LAN and associated shared resources are normally constructed with sufficient robustness to provide full service to all systems under nominal conditions and still have some unused capacity. The time based algorithm criteria used to schedule which information gets priority under nominal conditions is not capable of detecting the existence of a fault or overload condition.
The process of this invention uses the LAN's inherent excess capacity to provide a warning when there is a fault in the LAN that may lead to an overload and possible failure in one or more systems. The inventive process assigns the excess LAN capacity to those systems that are designated mission critical. This assignment of the excess capacity takes place in two steps: first, in the determination of feasibility, we use an altered (pseudo) inter-arrival time that is equal to the inter-arrival time value T
i
decremented by an additional value equal to the Worst Case Blocking Time, WCBT. The WCBT is the longest time interval that message transmissions can be blocked. In the case of a priority driven media arbitration, WCBT is equal to the time taken to transmit the largest frame assuming the LAN is operating under normal conditions. Decrementing each T
i
for each critical message by the WCBT ensures there is at least one scheduling opportunity for each mission critical frame before the frame will be scheduled late.
Secondly, the remaining excess capacity is distributed among the mission critical systems using a proportioning scheme based on the particular mission critical system's unique processing time (c
i
). This further modifies the pseudo T
i
which will be used to determine LAN feasibility for the set of transmitted messages and which will subsequently be used by the scheduler to determine scheduling priority of individual system messages. Once the pseudo T
i
has been generated, any mission critical frame that the scheduler algorithm perceives as being late, using the pseudo T
i
will signal that the system has suffered a fault and is beginning to use excess LAN capacity. The fault status is indicated because LAN feasibility was originally verified using the pseudo T
i
and this condition has been violated. The only source of violation would be a fault of some kind. While the excess network capacity may maintain the system for a period of time, the existence of the fault signals the possibility that failure is impending. In this situation, the system will shift to a value based scheduling mode for the duration of the fault. In the event the fault is transient, i.e. an EMF burst, once the scheduler determines that the mission critical systems have regained a state where they are on time for at least one a full cycle, the scheduling will be returned to the time based mode and all messages regardless of importance will again be transmitted.
REFERENCES:
patent: 5838968 (1998-11-01), Culbert
patent: 6212562 (2001-04-01), Huang
patent: 6446126 (2002-09-01), Huang et al.
patent: 6658448 (2003-12-01), Stefaniak et al.
Carter Clifford C.
Kuhn David L.
Meky Moustafa M.
Soderling Gail S.
The United States of America as represented by the Secretary of
LandOfFree
Adaptive scheduling technique for mission critical systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive scheduling technique for mission critical systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive scheduling technique for mission critical systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3259035