Demo for the Task Management Project

In one of the DARPA/ITO funded research projects, we address the following research issues:

We have characterized load sharing with three component policies: the transfer policy, the location policy, and the information policy, and carefully tailor each policy to reduce the probabilities of (1) transferring an overflow task to an ``incapable workstation''; (2) multiple workstations sending their overflow tasks to the same workstation; (3) excessive task transfers; (4) excessive communication overheads. We have also implemented the load sharing scheme as a portable software layer in the Sun Solaris environment. To facilitate monitoring of the task management system, we have implemented a Java monitor. More details on the Java monitor can be found here.

This demo is a series of AVI movies captured directly from the display by HyperCam and consists of demos for two sets of experiments.

• In the first set of experiments, we show the capability of the software layer to redistribute the workload. Specifically, we show how each workstation distributes overflow jobs in a decentralized manner to the other workstations. Because of the priority lists used in the location policy, the overflow jobs are shown to be evenly distributed among capable workstations.
  
  
• In the second set of experiments, we show the capability of the software layer to support fault tolerance. Llama will submit a remote job to gorrila (which will then crash). For demonstrative purposes, the only function this job performs is to write consecutive integers to llama's screen, starting from 0. After the job is executed for some time, we manually turn off gorrila. This emulates the scenario in which gorrila crashes. The operation of writing to llama's screen stops at this point. Since all the processes running on each participating workstation are periodically checkpointed and sent back to their home workstations, the most recent checkpoint file of this job has been sent back to llama, and will be restarted on vulture, the first runnable workstation in llama's priority list.

Demo for NetSim^Q

DVMRP (43-second avi file, 122KB)

This is a simple demonstration on how DVMRP operates on the Ohio Computer and Communication ATM Research Network (OCARNet). In the demo, node 0 is the sender (which keeps sending data packets) and node 15, 23, 24, 25, and 26 are the receivers in a multicast group. On-tree nodes and links are labeled in red. As the demo shows, a multicast tree is contructed and torn down by (repeatedly) going through the flooding phase, the pruning phase, and the flushing phase. (Note how a router that is not a group member initially receives data packets in the flooding phase and gets pruned when a prune message is set upstream in the pruning phase.)

CBT (41-second avi file, 94KB)

This is a simple demonstration on how CBT operates on the OCARNet. In the demo, the core is node 14 (Columbus) and nodes 2, 7, 10, 20, 23, 24 are group members in a multicast group. On-tree nodes and links are labeled in red. A link turns aqua to indicate a join-request or a quit-notification message is being forwarded on it.

Comparison among VC, STFQ, SCFQ, and WF²Q (42-second, avi file, 605KB)

In this demo, we compare four scheduling algorithms: VirtualClock (VC), WF²Q+ (an approximation of WF²Q), Self Clock Fair Queueing (SCFQ) and Start Time Fair Queueing (STFQ). The parking lot scenario is used as the network topology (see below). Four connections are established with parameters shown in the following table. In particular, packets of the four connections all traverse, and compete for the link bandwidth, on link 2 at node 4. The clips show the message schedule under the different scheduling algorithms on link 2 at node 4. Also provided are the average queueing delay and the average backlog. (The average queueing delay is obtained as follows. When a packet is transmitted, the average queueing delay is updated using the formula d = d * 0.9 + new_d * 0.1, where d is the running average and new_d is the queueing delay the packet just experienced. The average backlog is the time average of backlog in each connection queue.)

Comparisons among Real-Time Task Scheduling Algorithms

• RM vs EDF scheduling algorithms

  This demo gives the task schedules generated by the rate monotoinc and earliest-deadline-first algorithms.

  Liu and Layland showed that the rate-monotonic (RM) algorithm is optimal for fixed priority-driven scheduling schemes, and the deadline-driven algorithm, or termed elsewhere the earliest-deadline-first (EDF) algorithm, is optimal for dynamic priority-driven scheduling schemes. The RM algorithm assigns priorities to tasks according to their periods. Tasks with shorter periods get higher priorities. Since the periods of tasks are fixed, their priorities are also fixed. The EDF algorithm assigns priorities to tasks according to the deadlines of the current job requests. The earlier a job's deadline is, the higher its priority is. Therefore, the priority of a task changes with time.

  Liu and Layland further defined e_i/P_i as the processor utilization of task T_i, and showed that (i) a task set can be feasibly scheduled by the EDF algorithm if and only if the total utilization factor U _T = sum_{1 <= i <= n} e_i / P_i is less than or equal to one, and (ii) the least upper bound for a task set to be feasibly scheduled by the RM algorithm is K(n) = n(2^1/n - 1), i.e., if U _T = sum_{1 <= i <= n} e_i / P_i <= K(n) then the task set is guaranteed to be schedulable by the RM algorithm. Note, however, that if the utilization factor U _T is larger than K(n), it is not known whether or not the task set T can be feasibly scheduled by the RM algorithm.
  
  

• RM vs DCTS scheduling algorithms

  This demo gives the task schedules generated by the rate-monotonic and distance-constrained scheduling algorithms.

  A common approach to scheduling hard real-time tasks with repetitive requests is the periodic task model, in which each task T_i has a period P_i and an execution time e_i. T_i must be executed once in each of its periods. Execution of the task in any one period is scheduled independently of executions of the same task in other periods. That is, each execution, called a job request (or simply, a job), of a task has a fixed ready time and a fixed deadline, which are the beginning and the end of its period, respectively. Every job must start its execution after its ready time and completes before its deadline.

  The periodic task model, however, does not suffice to characterize the timing requirements of all real-time systems. For example, some real-time tasks must be executed in a (temporal) distance-constrained manner, rather than just periodically. The temporal distance between any two consecutive executions of a task should not be longer than a certain amount of time. These types of timing constraints, which we call temporal distance constraints, require an acceptable temporal distance between the times that two consecutive job requests of a task are executed. In other words, a job request of a task has a relative deadline depending on when its predecessor was actually executed. The schedule obtained by using the periodic task model with a period P may not necessarily satisfy the above criterion. We, thus, propose a real-time task model, termed as the Distance-Constrained Task System (DCTS), to remedy the deficiency of the periodic task model.

  Using techniques developed for the pinwheel problem, we have devised a DC scheduling scheme which efficiently schedules distance-constrained task sets. We have also derived a schedulability condition (density threshold) for the scheduling scheme. The density threshold serves as a measure for providing the fundamental predictability requirement in hard real-time applications, i.e., the schedulability of a task set can be checked by comparing the total density of the task set with the density threshold. The derived density threshold turns out to be exactly the same as the utilization bound for scheduling periodic tasks using the well-known rate-monotonic algorithm.

Comparisons among Message Scheduling Algorithms for Providing Temporal QoS

• Comparison among different GPS scheduling algorithm family

  Both PGPS and WF²Q+ are approximation algorithms to generalized process sharing (GPS). Specifically, a GPS server that serves N connections is characterized by N positive real numbers, a₁, a₂,...., a_N. The server operates at a fixed rate r and is work-conserving. At any time t, the service rate for a connection M_i with a non-empty queue is exactly (a_i / sum_j a_j) r, where the summation is over the set of backlogged connections.

  GPS is impractical due to the fact that packets cannot be infinitely divisible and that the scheduler can at most serve one connection at its full capacity at any time. PGPS and WF²Q+ are thus proposed to approximate GPS. Both algorithms keep track of the finishing time of a packet (i.e., the time when the packet completes its service) under GPS and emulate GPS by serving packets in the increasing order of their finishing times under GPS. The difference between PGPS and WF²Q+ lies in the way a server picks up the next new packet for transmission. When a PGPS server is ready to transmit a new packet at time t, it selects, among all the connections whose packets have arrived at time t, the connection whose packet would complete service in the corresponding GPS first. On the other hand, a WF²Q+ selects, among all connections whose packets have started receiving service in the corresponding GPS at time t, the connection whose packet would complete service in GPS first. It is well-known that although the service received by a connection under PGPS cannot fall much behind that under GPS, it can be quite far ahead of that under GPS, while the difference between the services provided by WF²Q+ and GPS is always less than one packet.
  

• Comparison between DCTS and Stop-and-Go scheduling algorithms
  

  The traffic is generated under the (C,D)-smooth traffic model.

Return to DRCL Page, Task Management Page, or Communication Software Page.
This page is jointly prepared by Hung-Ying Tyan, Yi Ye, and Jennnifer Hou.
Date last modified -- March 5, 1998.
Direct comments concerning this WWW site to: jhou@ece.osu.edu