## 1.1 Purpose
This SRS describes the requirements and specifications of Libra, an Economy-Driven Cluster Scheduler. It explains the functional features of the scheduler, along with interface details, design constraints, and related considerations such as performance characteristics. The SRS is intended for users and owners of high-performance clusters, cluster management software, job schedulers, and grid resources.

## 1.2 Scope
The Libra Scheduler is an add-on component designed for the open-source Sun Grid Engine (SGE) cluster management system. Its primary function is to provide a market-based, economy-driven service for managing batch jobs on homogenous Linux clusters. The scheduler will allocate CPU time for sequential and embarrassingly parallel batch jobs, prioritizing user utility and Quality of Service (QoS) parameters over traditional system performance considerations.

The main objective of the Libra Scheduler is to implement a computational economy within cluster computing, enabling resource management based on user-centric criteria such as budget and deadline. This approach aims to maximize user satisfaction by ensuring jobs are completed according to their specified QoS levels. The current scope does not include mechanisms for users to interact or bargain for resources among themselves. While its functionality is adaptable to schedule resources other than CPU time and operate on heterogeneous clusters, the initial implementation will focus on CPU time allocation for sequential and embarrassingly parallel jobs on homogenous Linux clusters.

### 1.3.1 Product perspective
The Libra Scheduler operates as an add-on component within a larger system, the Sun Grid Engine (SGE) cluster management system, which runs on a homogenous Linux-based cluster. SGE is responsible for receiving jobs submitted by users and then delegating these jobs to Libra for scheduling and allocation to appropriate workstations or execution hosts. Libra communicates its scheduling decisions regarding workstation allocation back to SGE's resource manager, which then dispatches the job to the chosen workstation. Once a job is assigned to a workstation, Libra is responsible for implementing its economy-driven scheduling policy on the jobs executing at those workstations. No modifications to the Linux kernel are required for Libra's operation.

#### System interfaces
Libra directly interfaces with a modified version 5.3 of the Sun Grid Engine (SGE) cluster management system. SGE, in turn, interfaces with the underlying Linux operating system and any other software components it requires for its functionality.

#### User interfaces
There are two primary user types for the Libra Scheduler: the cluster user and the cluster administrator. Both user types are able to interact with the system through the Linux command prompt or via the interface provided by the Sun Grid Engine cluster management system. A Graphical User Interface (GUI) is considered a potential future enhancement but is not part of the initial implementation.

#### Hardware interfaces
All hardware interfaces utilized by Libra are those inherited from the Sun Grid Engine, upon which it operates. These include SGE's interfaces for managing CPU usage, memory usage, swap file creation, and network communication.

#### Software interfaces
*   **Name:** Sun Grid Engine
    *   **Mnemonic:** SGE
    *   **Specification number:** [N/A]
    *   **Version number:** 5.3 (modified)
    *   **Source:** Open source
    *   **Discussion of purpose:** SGE acts as the primary cluster management system, handling job submission and dispatch. Libra integrates with SGE to provide economy-driven scheduling decisions, receiving jobs from SGE and returning allocation decisions.
    *   **Definition of interface:** [N/A]
*   **Name:** Linux
    *   **Mnemonic:** [N/A]
    *   **Specification number:** [N/A]
    *   **Version number:** [N/A]
    *   **Source:** Open source
    *   **Discussion of purpose:** Linux is the operating system on which the SGE cluster management system and, consequently, the Libra Scheduler run. No modifications to the Linux kernel are required.
    *   **Definition of interface:** [N/A]
*   **Name:** Parallel Virtual Machine libraries
    *   **Mnemonic:** PVM
    *   **Specification number:** [N/A]
    *   **Version number:** [N/A]
    *   **Source:** University of Tennessee, Oak Ridge National Laboratory, and Emory University
    *   **Discussion of purpose:** These libraries are used by the cluster for the execution of embarrassingly parallel jobs.
    *   **Definition of interface:** [N/A]
*   **Name:** Message Passing Interface libraries
    *   **Mnemonic:** MPI
    *   **Specification number:** [N/A]
    *   **Version number:** [N/A]
    *   **Source:** University of Chicago and Mississippi State University
    *   **Discussion of purpose:** These libraries are used by the cluster for the execution of embarrassingly parallel jobs.
    *   **Definition of interface:** [N/A]

#### Communications interfaces
Libra utilizes the existing communications architecture provided by the Sun Grid Engine itself. It does not introduce any unique or additional communications interfaces beyond those inherent to SGE.

#### Memory constraints
[N/A]

#### Operations
The Libra Scheduler's operations are primarily focused on providing Quality of Service (QoS) computational economy in cluster computing by maximizing user utility.

*   **User-initiated operations:**
    *   Users can submit jobs, specifying parameters such as budget, deadline, and estimated execution time.
    *   Users can query the cluster for current cost per unit time for new jobs.
    *   Users can monitor the status of their submitted jobs.
    *   Users can cancel their submitted jobs.
    *   Users can check their credit balance and usage history.
*   **Administrator-initiated operations:**
    *   Administrators can perform all user-initiated operations.
    *   Administrators can check the status of each node in the cluster.
    *   Administrators can check the usage pattern history of the cluster.
    *   Administrators can check the status of all submitted jobs.
    *   Administrators can check the load on each node.
    *   Administrators can alter the cost structure of the cluster.
    *   Administrators can alter the scheduling policy of the cluster.
    *   Administrators can cancel, suspend, and resume any job.
*   **System operations (Libra's core functionality):**
    *   Initialize jobs by retrieving user-submitted details and setting cluster state variables.
    *   Accept or reject jobs based on user-defined budget and deadline, considering cluster load and pending jobs.
    *   Calculate scheduling information (tickets, stride, pass) using a market-based economic model (bid-based proportional resource-sharing) and the stride-scheduling algorithm.
    *   Determine the optimal execution host and queue for a job, prioritizing load balancing and job type (sequential or embarrassingly parallel).
    *   Dispatch jobs to their chosen execution hosts and queues.
    *   Update cluster status (resource reservation, queue load) whenever a job is scheduled or completed.
    *   Execute jobs by time-slicing based on the stride-scheduling algorithm, selecting the job with the minimum pass value.
*   **Backup and recovery operations:** [N/A]

#### Site adaptation requirements
[N/A]

#### Interfaces with services
[N/A]

### 1.3.2 Product functions

The Libra Scheduler's primary function is to maximize user utility by providing Quality of Service (QoS) computational economy in cluster computing. It achieves this by scheduling CPU time based on user-defined parameters such as allocated budget and job deadline, rather than solely on system performance.

The major functions of the Libra Scheduler include:

*   **Job Allocation and Prioritization:** Allocating jobs to cluster resources based on user-centric priorities derived from budget and deadline, as well as other job specifications like executable location, system type, maximum execution time, and whether the job is sequential or embarrassingly parallel.
*   **Dynamic Resource Management:** Dynamically reallocating resources, changing job priorities, privileges, and execution order to accommodate urgent or high-value jobs, even if submitted later or during high system load.
*   **Scalable and Configurable Scheduling:** Maintaining performance as the cluster size and job count increase, and allowing for configurable scheduling policies that can incorporate various QoS parameters.
*   **Resource Accounting:** Providing a basic level of job accounting to track resource usage, which aids in scheduling decisions.
*   **Economic Model Implementation:** Utilizing a market-based, bid-based proportional resource-sharing model to determine resource pricing and allocation according to user constraints.
*   **Proportional Resource Enforcement:** Employing the stride-scheduling algorithm to ensure that actual resource allocation accurately reflects the calculated job share.
*   **System Integration:** Operating as a separable add-on to the Sun Grid Engine (SGE) cluster management system, leveraging its capabilities for job submission, dispatch, and cluster status management.
*   **Security:** Providing administrative security and control over scheduling criteria and resource allocation.

### 1.3.3 User characteristics
There are two primary classes of users for the Libra Scheduler:
*   **Cluster User**: This user submits jobs to the cluster. They need to understand the exact nature of the jobs they submit, including execution time and required resources. They must also possess the technical know-how to use the job submission interface.
*   **Cluster Administrator**: This user oversees scheduling and cluster usage. They must be an advanced cluster operator, fully qualified in using Linux, the Sun Grid Engine (SGE), and the Libra Scheduler.

### 1.3.4 Limitations
*   The Libra Scheduler will only manage sequential and embarrassingly parallel batch jobs to be run on a homogenous Linux cluster.
*   There will be no mechanism for users to interact with each other or bargain on the use of resources.
*   The current hardware environment for implementation and testing consists of a network of four Pentium-III workstations with 128 MB RAM.
*   A simulating tool for testing may need to be specially designed if a generic one is not readily and freely available.
*   Only a basic module for job accounting and payment considerations will be provided, as these are not the primary focus of the scheduler.
*   Detailed requirements for the economic front-end, including exact costing and pricing policies, will be specified in a later version.
*   Initially, only a command-line Linux interface or the interface of the Sun Grid Engine (SGE) cluster management system will be used for user and administrator interaction; a Graphical User Interface (GUI) is not part of the initial implementation.
*   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
*   A maximum bug rate of 1 bug per KLOC is targeted.
*   In case of system outage, the cluster will be down for less than five minutes while the Linux operating system boots up.
*   The Libra scheduler will ensure the privacy of user job status and full control over job execution, preventing alteration of scheduling criteria or actual resource allocation without administrator authority.
*   Assuming submitted job statistics are accurate, the Libra scheduler will ensure all jobs are completed with a 10% error allowance.
*   Under all circumstances, the maximum cost charged to the user will not exceed the budget submitted by the user.
*   The Libra scheduler will be a sub-component of the Sun Grid Engine (SGE) cluster management system.
*   All coding will be done in standard C.
*   Exhaustive searches of the entire set of combinations of jobs will not be performed; heuristics will be developed for the scheduling problem.
*   All hardware, software, and communication interfaces of Libra will be those of the Sun Grid Engine, on top of which it will be running.
*   Libra will be released under a GPL license and will be open-source.

## 1.4 Definitions
*   **Cluster/Cluster Computing**: Clustering involves connecting two or more computers together to take advantage of combined computational power and resources. Hence, a cluster works as an integrated collection of resources that can provide a single system image spanning all its nodes.
*   **QoS**: Quality of Service – meeting what users actually want, thus maximizing their utility.
*   **Computational Economy**: Refers to the inclusion of user-specified QoS parameters with jobs so that resource management is based on a user-centric approach rather than on a system-centric approach.
*   **Linux**: An open source operating system, with extensive documentation and user support.
*   **Grid Computing**: A grid is an infrastructure that couples resources such as computers (PCs, workstations, clusters and so on), software (for special purpose applications) and devices (printers, scanners) across the Internet and presents them as a unified integrated single resource that can be widely used. Grid computing refers to using a grid for processing jobs and processes.
*   **Bid-based Proportional Resource-Sharing Model**: An economic model that specifies one way of allocating (cluster) resources between competing users based on what their criteria is, such as deadline and budget. In this model, the amount of resource allocated to users is proportional to the values of their bids.
*   **Stride Scheduling**: A scheduling algorithm to enforce resource allocations proportional to a user’s priority or share. A pool of tickets represents resource rights to a shared resource. A stride is inversely proportional to the number of tickets allocated to a job, hence representing the interval (in terms of CPU time) between two successive scheduling of a job.
*   **Process Migration**: The process of moving a job from one computer system to another without restarting the job from the beginning.
*   **Sequential Jobs**: Jobs that must be run on a single node, and cannot be split into separate jobs.
*   **Embarrassingly Parallel Jobs**: Parallel jobs that are comprised of independent parts that can be split up and performed on separate nodes as if they are sequential jobs, with minimal inter-job communication necessary.
*   **Job accounting**: A method of quantifying the system resources used by a job.
*   **Open-source software**: Software for which the code is freely available for use and research.
*   **Homogenous cluster**: A cluster in which the nodes or workstations have uniform characteristics such as the same memory size and hard disk space. They run the same operating system.

# 2 References

## Guidance

*   **[1]** R. Buyya, D. Abramson, and J. Giddy, "Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid," HPC ASIA’2000, China, IEEE CS Press, USA, 2000.
    *   Publishing Organization: IEEE CS Press, USA
    *   Date: 2000
    *   Source: [N/A]

*   **[2]** R. Buyya, D. Abramson, J. Giddy, "An Economy Driven Resource Management Architecture for Global Computational Power Grids," The 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000), Las Vegas, USA, June 26-29, 2000.
    *   Publishing Organization: [N/A] (Conference proceedings)
    *   Date: June 26-29, 2000
    *   Source: [N/A]

*   **[3]** R. Buyya, D. Abramson, and J. Giddy, "An Economy Grid Architecture for Service-Oriented Grid Computing," 10th IEEE International Heterogeneous Computing Workshop (HCW 2001), with IPDPS 2001, SF, California, USA, April 2001.
    *   Publishing Organization: IEEE
    *   Date: April 2001
    *   Source: [N/A]

*   **[4]** Rajkumar Buyya, Heinz Stockinger, Jonathan Giddy, and David Abramson, "Economic Models for Management of Resources in Peer-to-Peer and Grid Computing," Monash University.
    *   Publishing Organization: Monash University
    *   Date: [N/A]
    *   Source: [N/A]

*   **[5]** B.N. Chun and D.E. Culler, "Market-based proportional resource sharing for clusters." Submitted for publication, September 1999.
    *   Publishing Organization: [N/A]
    *   Date: September 1999
    *   Source: [N/A]

## 3.1 Functions

The Libra Scheduler provides an economy-driven approach to managing batch jobs on clusters, focusing on Quality of Service (QoS) based on user utility. The core functions involve accepting, scheduling, and executing jobs while interacting with the underlying Sun Grid Engine (SGE) cluster management system. The functional requirements are partitioned into the following sub-functions:

### 3.1.1 Submit Job

This function allows end-users or administrators to submit jobs to the cluster. It is primarily facilitated by the Sun Grid Engine (SGE) interface, which may be adapted to include additional Libra-specific submission parameters, or through a command-line interface.

*   **Inputs:**
    *   User Information: User name and authentication ID.
    *   Job Information: Details about the job to be submitted, including specifications for `Initialize Job`.
    *   Cluster Information: Cluster type, scheduling mechanism details, current load status, submission directions, and criteria.
*   **Processing:**
    *   The cluster determines if it is currently open for job submissions.
    *   The system validates the user attempting to submit the job.
    *   This decision is distinct from the `Accept/Reject Job` feature, which evaluates job parameters like budget and deadline.
*   **Outputs:**
    *   Boolean value indicating whether the cluster is accepting submissions.
    *   Boolean value indicating whether the user has been verified.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.2 View Job Status

This function enables users or administrators to view details about submitted jobs and monitor their execution progress.

*   **Inputs:**
    *   User ID and Password: Required to ensure only authorized users can view job status.
*   **Processing:**
    *   Displays available options regarding the submitted job.
    *   Provides information about the progress of job execution.
    *   Processes selected options if choices are provided to the user to view different aspects of job information.
*   **Outputs:**
    *   A user-specific view of available options and information about jobs submitted by that user.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.3 Delete/Change Job

This function allows users or administrators to cancel a job or, under specific circumstances, modify certain job parameters. Critical parameters like deadline and cost are generally not changeable, but modifications such as output directory or a delayed deadline may be permitted.

*   **Inputs:**
    *   User ID and Password: Required to ensure only authorized users can delete or change the job.
*   **Processing:**
    *   Removes the specified job from the queue.
    *   Updates the cluster status to reflect the job's removal.
    *   Revises scheduling decisions for pending jobs and the submission of new jobs.
*   **Outputs:**
    *   Updated cluster information, including CPU load, node status, queue length, quanta allocated to pending jobs, and revised expected finishing deadlines of pending jobs. These outputs are facilitated by the Sun Grid Engine and not independently produced by Libra.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.4 Initialize Job

This is a core functional requirement that prepares the scheduler for eventually scheduling and executing a job. Libra performs this function once a job has been accepted by SGE, using information from the scheduler.

*   **Inputs:**
    *   Information submitted by the user about the job.
    *   The job ID assigned by SGE.
*   **Processing:**
    *   Retrieves the detailed information of the job.
    *   Sets these details into variables that represent the state of the cluster and its queues.
    *   Passes the parsed parameters to the scheduling module for further evaluation (e.g., acceptance or rejection).
*   **Outputs:**
    *   A set of variables representing the exact job details: Job Id, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.5 Accept/Reject Job

This function is responsible for determining whether a user's job can be satisfied given its budget and deadline constraints.

*   **Inputs:**
    *   Job details: Job Id, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
    *   Cluster information: Current CPU load, node status, and remaining execution time of pending jobs.
*   **Processing:**
    *   Based on the job parameters, the scheduler calculates a priority for the job, reflecting the share of CPU time it deserves according to the specified criteria.
    *   The scheduler determines if the job can be completed by its requisite deadline, considering its execution time and the execution status of other pending jobs across various nodes.
*   **Outputs:**
    *   A boolean value indicating whether the job has been accepted or rejected.
    *   A suggested deadline or cost, which may be offered to the user as a precondition for job acceptance.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.6 Calculate Scheduling Information

This function decides how a job will be scheduled based on its budget and deadline. It utilizes the Stride Scheduling Algorithm to enforce resource allocations (CPU cycles) proportional to a user’s budget and deadline. This is performed by Libra once a job has been deemed accommodable.

*   **Inputs:**
    *   Job details: Job Id, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
*   **Processing:**
    *   Allocates "tickets" to a job based on its budget and deadline, as well as the budgets and deadlines of all other jobs on the potential execution host.
    *   Calculates the job's "stride" (inversely proportional to tickets, representing the interval between successive scheduling) and initializes its "pass" value (initially equal to its stride).
*   **Outputs:**
    *   Scheduling information for the job: its allocated tickets, stride, and pass values.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.7 Determine Execution Host

This function selects the specific node and queue where a job will be placed for execution. The decision is based on the job’s budget, execution time, and deadline.

*   **Inputs:**
    *   Job details: Job Id, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
    *   Cluster Information: Current CPU Load, Node Status, Remaining Time of Pending Jobs, Available Memory.
*   **Processing:**
    *   Libra first evaluates the load on each available host, sorting them in ascending order to identify the least loaded host, thereby ensuring load balancing.
    *   It then selects the appropriate queue on the chosen host, considering factors such as whether the job is sequential or embarrassingly parallel, its budget, and other relevant criteria.
*   **Outputs:**
    *   The chosen execution host and the specific queue on that host.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.8 Dispatch Job

This function takes the scheduled job and inserts it into the designated queue on the chosen execution host. It determines the optimal time to send the job for execution, potentially allowing other jobs to complete or be scheduled earlier if their deadlines are more urgent.

*   **Inputs:**
    *   The chosen execution host and the queue on which to place the job for execution.
*   **Processing:**
    *   The scheduler sends the job to the appropriate queue, where it then joins the competition for resources.
*   **Outputs:**
    *   The scheduled job, now placed in its appropriate host and queue.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.9 Update Cluster Status

This function updates the cluster's status whenever a job is scheduled for execution on a host or when a job completes and is removed from the cluster.

*   **Inputs:**
    *   Job details: Job Id, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
    *   Chosen execution host and queue.
*   **Processing:**
    *   Libra reserves the necessary amount of resources for the job on the selected node.
    *   It updates the execution host's queue status.
    *   Sends information about the additional load on the queue and node to the central information store on the master host.
*   **Outputs:**
    *   There is no direct output; this function primarily performs an internal update and acts as a trigger.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.10 Execute Job

This function continuously runs as long as there are jobs in the queues. It is responsible for time-slicing between all currently executing jobs, with scheduling decisions made based on the stride-scheduling algorithm.

*   **Inputs:**
    *   Scheduled Job: Job details, including the queue and node where it is scheduled to run.
    *   Scheduling Information: The job’s tickets, stride, and pass values.
*   **Processing:**
    *   It examines all jobs across the cluster and selects the one with the minimum pass value.
    *   Allots a quantum of CPU time to the selected job.
    *   Advances the pass value of that job by its stride.
    *   In the event of a tie in pass values, jobs are ordered using a First-In, First-Out (FIFO) policy.
    *   This loop repeats until no jobs remain to be run on a queue.
*   **Outputs:**
    *   Updated Cluster Information: CPU Load, Node Status, Remaining Time of Pending Jobs, Available Memory.
*   **Responses to Abnormal Situations:** [N/A]

## 3.2 Performance requirements
*   **Response Time:** The maximum response time for the submission of a job shall be 1 minute.
*   **Capacity:** The maximum number of jobs schedulable is limited only by the capacity of the cluster nodes to fulfill the jobs’ deadlines; there is no inherent upper limit within the Libra scheduler itself.
*   **Deadline Sensitivity:** Assuming submitted statistics for jobs are accurate, the Libra scheduler shall ensure that all jobs are completed with a 10% error allowance.
*   **Cost Sensitivity:** Under all circumstances, the maximum cost payable as submitted by the user shall be the maximum cost charged to the user.

## 3.3 Usability requirements
The primary usability objective of the Libra Scheduler is to provide Quality of Service (QoS) by meeting user expectations and maximizing user utility and satisfaction. This is achieved by prioritizing user-specified job parameters such as budget and deadline over system-centric performance considerations.

Specific usability requirements include:

*   **User Satisfaction and Effectiveness:**
    *   The system shall ensure that all jobs are completed within a 10% error allowance of the specified deadline, assuming accurate job statistics are provided.
    *   The system shall ensure that the maximum cost charged to the user does not exceed the budget submitted by the user.
    *   Users shall be able to submit jobs with associated deadline, cost, and execution time.
    *   Users shall be able to query the cluster for the current cost per unit time for submitting new jobs.
    *   Users shall be able to monitor the status of their submitted jobs.
    *   Users shall be able to cancel their submitted jobs.
    *   Users shall be able to check their credit balance and usage history.
    *   Administrators shall be able to check the status of each cluster node, usage patterns, and all submitted jobs.
    *   Administrators shall be able to check the load on each cluster node.
    *   Administrators shall be able to alter the cost structure and scheduling policy of the cluster.
    *   Administrators shall be able to cancel, suspend, and resume any job.

*   **Efficiency:**
    *   The maximum response time for the submission of a job shall be 1 minute.

*   **User Interface:**
    *   The system shall provide a command-line interface through Linux for both cluster users and administrators.
    *   The system shall leverage and adapt the interface provided by the Sun Grid Engine cluster management system for user and administrator interaction.
    *   Ideally, a Graphical User Interface (GUI) shall be provided for all components, including job submission for users and oversight for administrators, in future iterations.

*   **Documentation and Help:**
    *   Online user documentation shall be provided in the form of man pages accessible through Linux.

*   **Security and Control (Avoidance of Harm):**
    *   The Libra scheduler shall ensure the privacy of user job status.
    *   The Libra scheduler shall ensure full control over job execution, preventing alteration of scheduling criteria or actual resource allocation without administrator authority.

## 3.5 Logical database requirements

The Libra Scheduler, while not explicitly defining a relational database, requires a persistent data store to manage various types of information critical for its operation. This includes user-centric job parameters, cluster status, and scheduling decisions.

a) types of information used by various functions;

*   **User Data:**
    *   User ID, authentication ID, password.
    *   Credit balance.
    *   Usage history.
*   **Job Data:**
    *   Job ID.
    *   Job type (sequential or embarrassingly parallel).
    *   Standalone execution time.
    *   Location of executable and input data sets.
    *   System type.
    *   Budget allocated by the user.
    *   Deadline required by the user.
    *   Current job status (e.g., pending, executing, completed, cancelled).
    *   Scheduling information: tickets, stride, pass.
    *   Assigned execution host and queue.
*   **Cluster Data:**
    *   Cluster type.
    *   Scheduling mechanism details.
    *   Current load status (CPU load, node status, remaining time of pending jobs, available memory).
    *   Submission directions and criteria.
    *   Usage pattern history of the cluster.
    *   Cost structure of the cluster.
    *   Scheduling policy of the cluster.
*   **Pricing Data:**
    *   Current cost per unit time for submitting new jobs.

b) frequency of use;

*   **High Frequency:** Job Data (status, scheduling information, execution host, queue) and Cluster Data (load, node status, pending jobs, available memory) are frequently accessed and updated during job submission, scheduling, execution, and status monitoring.
*   **Moderate Frequency:** User Data (credit balance, usage history) is accessed upon user request.
*   **Low Frequency:** Administrator-specific Cluster Data (cost structure, scheduling policy) is accessed and altered by administrators.

c) accessing capabilities;

*   **Cluster User:**
    *   Submit jobs with associated deadline, cost, and execution time.
    *   Query the cluster to establish the current cost per unit time for submitting new jobs.
    *   Monitor the status of submitted jobs.
    *   Cancel jobs submitted by them.
    *   Check their credit balance.
    *   Check their usage history.
*   **Cluster Administrator:**
    *   All capabilities available to a Cluster User.
    *   Check the status of each node of the cluster.
    *   Check the usage pattern history of the cluster.
    *   Check the status of all submitted jobs.
    *   Check the load on each node of the cluster.
    *   Alter the cost structure of the cluster.
    *   Alter the scheduling policy of the cluster.
    *   Cancel, suspend, and resume any job.

d) data entities and their relationships;

*   **Entities:**
    *   User
    *   Job
    *   Cluster Node
    *   Queue
    *   Scheduling Policy
    *   Cost Structure
*   **Relationships (Implicit):**
    *   A User submits multiple Jobs (one-to-many).
    *   A Job is associated with specific Scheduling Information (tickets, stride, pass).
    *   A Job is assigned to one Cluster Node and one Queue for execution.
    *   A Cluster Node can host multiple Jobs.
    *   A Queue can contain multiple Jobs.
    *   The system maintains a global Scheduling Policy and Cost Structure, which can be altered by an Administrator.
    *   Job Accounting data (usage history, credit balance) is associated with a User.

e) integrity constraints;

*   **Job Completion:** All accepted jobs are expected to be completed within their specified deadline, with a 10% error allowance, assuming accurate submitted statistics.
*   **Budget Adherence:** The maximum cost charged to a user for a job will not exceed the budget allocated by the user.
*   **User Authentication:** Only authenticated users are permitted to view or modify their own job details.
*   **Administrator Authority:** Alteration of scheduling criteria or actual resource allocation is restricted to administrators.

f) security;

*   **Data Privacy:** The system must ensure the privacy of user job status.
*   **Access Control:** User ID and password authentication will be enforced for accessing user-specific information and job status.
*   **Authorization:** Full control over job execution and the ability to alter scheduling criteria or resource allocation will be restricted to administrators.

g) data retention requirements.

*   A basic level of job accounting and usage history will be maintained to aid in scheduling policies and allow users to check their usage. Specific data retention periods are not defined in this version of the SRS.

## 3.6 Design constraints

The design of the Libra scheduler is subject to the following constraints:

*   The Libra scheduler will function as a sub-component of the Sun Grid Engine (SGE) cluster management system.
*   All coding will be done in standard C.
*   Scheduling algorithms will rely on heuristics rather than exhaustive searches of the entire set of job combinations.
*   The system is designed to operate and be tested on a cluster consisting of four Pentium-III workstations, each with 128 MB RAM, running the Linux operating system with SGE.
*   Initial user and administrator interfaces will be limited to the Linux command prompt or the existing Sun Grid Engine interface; a Graphical User Interface (GUI) is not part of the initial implementation.
*   The detailed costing and pricing policy for the economic front-end will be specified in a later version and is not part of the current design scope.
*   A custom simulation tool may need to be designed for testing purposes if a suitable generic one is not readily and freely available.

## 3.7 Software system attributes

### Reliability
*   The maximum bug rate will be 1 bug/KLOC.
*   In case of system outage, the cluster will be down while the Linux operating system boots up, which will take less than five minutes.

### Availability
*   In case of system outage, the cluster will be down while the Linux operating system boots up, which will take less than five minutes.

### Security
*   The Libra scheduler will ensure the privacy of user job status.
*   The Libra scheduler will ensure full control over job execution, preventing alteration of scheduling criteria or actual resource allocation without administrator authority.
*   The system will provide administrative security.

### Maintainability
*   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
*   The scheduler should be separable from the cluster management system.
*   All code will be written as specified by the Hungarian Naming Convention.
*   All code will be written as required by the GNU General Purpose License.

### Portability
*   The system is intended to run on a homogenous Linux cluster.
*   No modifications to the Linux kernel are required.
*   All coding will be done in standard C.

## 3.8 Supporting information

### Problem Description
The Libra Scheduler addresses the current lack of a holistic scheduling mechanism in cluster computing that enables differing Quality of Service (QoS) levels for various clients.

### Apportionment of Requirements
Detailed requirements for the economic front-end, specifically the exact costing and pricing policy for charging users, will be specified in a later version of this SRS. The pricing mechanism will not affect the scheduling policies, as they assume a given cost and budget and schedule resources accordingly.

Currently, user and administrator interaction will be limited to a command-line Linux interface or the interface provided by the Sun Grid Engine cluster management system. A Graphical User Interface (GUI) may be added once the basic functionality is implemented.

The decision regarding whether a custom software tool for simulation and testing purposes will be designed or if a generic, freely available tool will be used remains to be made.

### Online User Documentation and Help System
All documentation will adhere to the requirements for open-source software under the GNU General Purpose License. Additionally, online user documentation will be provided in the form of man pages, accessible through Linux.

### Licensing
The Libra Scheduler will be released under a GPL license and will be open-source.

### Legal, Copyright, and Other Notices
*   Sun Grid Engine (SGE) is a copyright trademark of Sun Microsystems, Inc.
*   Libra Scheduler is a copyright trademark of Mr. Rajkumar Buyya, Monash University.
*   MPI is a copyright of the University of Chicago and Mississippi State University.
*   PVM is a copyright of the University of Tennessee, Oak Ridge National Laboratory, and Emory University.

### Additional Supporting Information
Further supporting information is provided in the appendices:
*   Appendix A: Background Research (dated 10th Nov, 2001) on Cluster Computing, Market-based Economic Models, Cluster Scheduling, and Cluster Management Software.
*   Appendix B: Data Flow Diagrams, which diagrammatically explain the functionality of the Libra scheduler.
*   Appendix C: Data Dictionary, which should be used to interpret and understand the Data Flow Diagrams.

## 4.1 Functions

This section outlines the verification approaches and methods planned to qualify the functional requirements of the Libra Scheduler. Each functional feature will undergo rigorous testing to ensure it performs as specified, handles inputs correctly, processes information accurately, and responds appropriately to various conditions, including abnormal situations.

### 4.1.1 Submit Job
*   **Verification Objectives:** To confirm that the system correctly processes job submission requests, validates user credentials, and determines the cluster's availability for new submissions.
*   **Verification Methods:** Unit and integration testing will be employed. Test cases will cover valid and invalid user authentication, and scenarios where the cluster is open or closed for submissions.
*   **Key Scenarios/Checks:**
    *   Successful submission with valid user credentials when the cluster is accepting jobs.
    *   Rejection of submission with invalid user credentials.
    *   Rejection of submission when the cluster is not accepting jobs.
    *   Verification that the SGE interface correctly captures and passes additional submission parameters (budget, deadline).
    *   Confirmation of correct boolean outputs for all submission attempts.

### 4.1.2 View Job Status
*   **Verification Objectives:** To ensure users and administrators can accurately view the status and details of submitted jobs.
*   **Verification Methods:** Test cases will involve authenticated users querying their own job statuses and administrators querying all job statuses. Real-time updates will be monitored.
*   **Key Scenarios/Checks:**
    *   Successful retrieval and display of job status for an authenticated user's jobs.
    *   Attempted retrieval of job status for another user's jobs (should be denied for regular users).
    *   Verification of accurate job progress information (e.g., pending, running, completed, failed).
    *   Testing of various options for viewing different aspects of job information.

### 4.1.3 Delete/Change Job
*   **Verification Objectives:** To confirm that jobs can be correctly deleted or modified by authorized users, and that such actions trigger appropriate updates to cluster status and scheduling decisions.
*   **Verification Methods:** Test cases will cover authorized and unauthorized attempts to delete or change jobs. Monitoring of cluster state and scheduling queues will confirm updates.
*   **Key Scenarios/Checks:**
    *   Successful deletion of a job by its owner or an administrator.
    *   Attempted deletion of a job by an unauthorized user (should be denied).
    *   Verification that the deleted job is removed from all relevant queues and data structures.
    *   Confirmation that cluster status (CPU load, node status, queue length) is updated post-deletion.
    *   Verification that scheduling decisions for remaining jobs are revised correctly.
    *   Successful modification of permitted job parameters (e.g., output directory, delayed deadline).
    *   Attempted modification of crucial, non-changeable parameters (e.g., budget, original deadline) (should be rejected).

### 4.1.4 Initialize Job
*   **Verification Objectives:** To ensure that all user-submitted job parameters are correctly retrieved, parsed, and prepared for the scheduling process.
*   **Verification Methods:** Unit testing will focus on the parsing logic. Integration testing will confirm the flow of information from SGE to Libra's internal representation.
*   **Key Scenarios/Checks:**
    *   Successful parsing and storage of all specified job details (Job Id, type, execution time, location, system type, budget, deadline) for valid inputs.
    *   Robustness testing with malformed or missing input parameters to ensure graceful error handling.
    *   Verification that the parsed job details are accurately passed to the subsequent scheduling modules.

### 4.1.5 Accept/Reject Job
*   **Verification Objectives:** To verify that the scheduler accurately determines job acceptance based on user-defined budget and deadline, considering current cluster load and pending jobs.
*   **Verification Methods:** Extensive test cases will simulate various job submissions under different cluster load conditions. Expected outcomes (accept/reject, suggested parameters) will be compared against actual results.
*   **Key Scenarios/Checks:**
    *   Acceptance of jobs that can be completed within their deadline and budget under current cluster conditions.
    *   Rejection of jobs that cannot meet their deadline or budget constraints.
    *   Verification of the calculated job priority based on budget and deadline.
    *   Accuracy of suggested deadlines or costs provided for rejected jobs.
    *   Testing edge cases such as jobs with very tight deadlines, very high budgets, or extremely long execution times.
    *   Verification of responses to abnormal situations like sudden changes in cluster load or resource availability during evaluation.

### 4.1.6 Calculate Scheduling Information
*   **Verification Objectives:** To confirm that the economic model correctly allocates tickets and calculates stride and pass values based on job budget and deadline.
*   **Verification Methods:** Unit testing will be used to verify the mathematical calculations. Test cases will involve various combinations of job parameters and competing jobs.
*   **Key Scenarios/Checks:**
    *   Verification that ticket allocation is proportional to budget and deadline as defined by the bid-based proportional resource-sharing model.
    *   Confirmation that stride is correctly calculated as inversely proportional to the number of tickets.
    *   Accuracy of the initial pass value calculation.
    *   Testing with multiple jobs having diverse budget and deadline constraints to ensure fair and proportional allocation.

### 4.1.7 Determine Execution Host
*   **Verification Objectives:** To ensure the scheduler correctly identifies the optimal execution host and queue for a job based on load balancing and job type.
*   **Verification Methods:** Simulation of cluster states with varying node loads and resource availability. Test cases will cover different job types (sequential, embarrassingly parallel).
*   **Key Scenarios/Checks:**
    *   Selection of the least loaded host when multiple options are available.
    *   Correct queue selection based on job type (sequential vs. embarrassingly parallel).
    *   Consideration of other cluster information such as available memory and remaining time of pending jobs in host selection.
    *   Verification of responses to abnormal situations, such as all hosts being overloaded or specific queues being unavailable.

### 4.1.8 Dispatch Job
*   **Verification Objectives:** To confirm that the accepted job is successfully placed into the designated queue on the chosen execution host.
*   **Verification Methods:** Integration testing will verify the interaction with the SGE queuing system. Monitoring of target queues will confirm job placement.
*   **Key Scenarios/Checks:**
    *   Successful insertion of a job into the specified queue on the chosen host.
    *   Verification that the job is correctly registered within the host's queue system.
    *   Testing of scenarios where the target queue or host might become temporarily unavailable between determination and dispatch, ensuring appropriate error handling.

### 4.1.9 Update Cluster Status
*   **Verification Objectives:** To ensure that the cluster's status information is accurately and consistently updated whenever a job is scheduled or removed.
*   **Verification Methods:** Monitoring of the central information store and individual node statuses after job scheduling and completion/deletion events.
*   **Key Scenarios/Checks:**
    *   Verification that resources required by a job are correctly reserved on the node upon scheduling.
    *   Confirmation that the execution host's queue status and load information are accurately updated and propagated to the central information store.
    *   Testing for data consistency and atomicity of updates, especially under concurrent scheduling/deletion events.
    *   Verification that updates occur correctly when a job completes or is deleted.

### 4.1.10 Execute Job
*   **Verification Objectives:** To verify that the stride-scheduling algorithm correctly manages CPU time allocation among competing jobs, ensuring proportional resource sharing and accurate pass value updates.
*   **Verification Methods:** Simulation and system-level testing with multiple concurrent jobs having varying scheduling information (tickets, stride, pass). Monitoring of CPU allocation and job progress.
*   **Key Scenarios/Checks:**
    *   Verification that the job with the minimum pass value is consistently selected for execution.
    *   Confirmation that the pass value of the executed job is correctly advanced by its stride.
    *   Testing of proportional resource allocation among jobs with different ticket counts.
    *   Verification of the FIFO tie-breaking mechanism.
    *   Monitoring of updated cluster information (CPU load, node status, remaining time) during execution.
    *   Testing responses to abnormal situations such as job crashes or unexpected termination, ensuring proper resource release and queue management.

## 4.2 Performance requirements
Verification of the performance requirements will involve the following approaches and methods:

*   **Response Time Verification**:
    *   **Method**: Conduct load testing by submitting jobs under varying system loads, including low, medium, and high CPU utilization and different queue lengths. The time elapsed from the initiation of a job submission to the system's confirmation of job acceptance will be measured.
    *   **Criteria**: The measured response time for job submission shall not exceed 1 minute.

*   **Capacity Verification**:
    *   **Method**: Perform stress testing by progressively increasing the number of concurrent jobs submitted to the cluster. Monitor the scheduler's behavior and the cluster's resource utilization (CPU, memory, network) until jobs begin to consistently miss their deadlines due to node saturation.
    *   **Criteria**: The scheduler shall continue to process and attempt to schedule jobs without internal failure or imposing an artificial upper limit before the underlying cluster nodes reach their capacity to fulfill job deadlines. This may require a simulation tool or a larger testbed for comprehensive analysis.

*   **Deadline Sensitivity Verification**:
    *   **Method**: Execute test suites comprising jobs with diverse, predefined deadlines and accurately estimated execution times. The actual completion time of each job will be monitored and compared against its specified deadline.
    *   **Criteria**: All jobs shall be completed within a 10% error allowance of their specified deadlines, assuming the submitted job statistics are accurate.

*   **Cost Sensitivity Verification**:
    *   **Method**: Submit jobs with explicitly defined maximum budgets. Upon job completion, the actual cost charged for each job will be retrieved from the job accounting system.
    *   **Criteria**: The charged cost for any job shall not exceed the user-specified maximum budget under any circumstances.

## 4.3 Usability requirements
[N/A]

## 4.5 Logical database requirements
[N/A]

## 4.6 Design constraints

*   **Parent Component: Sun Grid Engine**
    *   Verification: Integration testing will be conducted to ensure that the Libra scheduler functions correctly as a sub-component of the Sun Grid Engine (SGE) system. This includes verifying proper communication and data exchange between Libra and SGE modules.
*   **Software Language**
    *   Verification: Code reviews and static analysis tools will be employed to confirm that all software components are implemented exclusively in standard C.
*   **Scheduling Constraints**
    *   Verification: Design documentation and code reviews of the scheduling algorithms will be performed to confirm that exhaustive searches are not implemented. Performance testing with various job loads will be conducted to validate that the scheduler relies on developed heuristics and maintains acceptable performance characteristics, rather than exhibiting behavior consistent with exhaustive search for large problem sets.

## 4.7 Software system attributes
[N/A]

## 5.1 Assumptions and dependencies
*   The workability of the Sun Grid Engine cluster management system modules, such as those dealing with process migration, with the scheduling policies provided by the Libra Scheduler is assumed.
*   A basic module of job accounting and payment considerations will be provided, as they are not the focus of the scheduler.
*   Users are assumed to have a fair estimate of job execution times, so that the decision to accept or reject a job is facilitated.

## 5.2 Acronyms and abbreviations
*   **Cluster/Cluster Computing:** Connecting two or more computers together to take advantage of combined computational power and resources, working as an integrated collection of resources that can provide a single system image spanning all its nodes.
*   **CPU:** Central processing unit of a computer.
*   **Computational Economy:** The inclusion of user-specified Quality of Service (QoS) parameters with jobs so that resource management is based on a user-centric approach rather than on a system-centric approach.
*   **Embarrassingly Parallel Jobs:** Parallel jobs comprised of independent parts that can be split up and performed on separate nodes as if they are sequential jobs, with minimal inter-job communication necessary.
*   **Grid Computing:** An infrastructure that couples resources such as computers, software, and devices across the Internet and presents them as a unified integrated single resource.
*   **GUI:** Graphical user interface.
*   **Homogenous cluster:** A cluster in which the nodes or workstations have uniform characteristics such as the same memory size and hard disk space, and run the same operating system.
*   **Job accounting:** A method of quantifying the system resources used by a job.
*   **Linux:** An open source operating system.
*   **Open-source software:** Software for which the code is freely available for use and research.
*   **Process Migration:** The process of moving a job from one computer system to another without restarting the job from the beginning.
*   **QoS:** Quality of Service – meeting what users actually want, thus maximizing their utility.
*   **SGE:** Sun Grid Engine cluster management system.
*   **Sequential Jobs:** Jobs that must be run on a single node and cannot be split into separate jobs.
*   **Stride Scheduling:** A scheduling algorithm to enforce resource allocations proportional to a user’s priority or share, where a stride is inversely proportional to the number of tickets allocated to a job.