# 1 Introduction
[NULL]

## 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 Product overview
[NULL]

### 1.3.1 Product perspective
The Libra Scheduler is an add-on component to the Sun Grid Engine (SGE) cluster management system, operating within a Linux-based cluster environment. Libra's primary role is to provide market-based, economy-driven scheduling for batch jobs, focusing on Quality of Service (QoS) based on user utility rather than system performance.

The overall system operates as follows:
*   SGE receives jobs submitted by users.
*   SGE delegates these jobs to Libra for scheduling and allocation to appropriate workstations or execution hosts.
*   Libra communicates its scheduling decisions regarding workstation allocation back to the SGE resource manager.
*   The SGE resource manager then dispatches the job to the chosen workstation.
*   Once a job is assigned to a workstation, Libra is responsible for implementing its scheduling policy on the jobs executing at those workstations.
*   No modifications to the Linux kernel are required for Libra's operation.

#### System interfaces
The Libra Scheduler interfaces directly with the Sun Grid Engine (SGE) cluster management system.
*   SGE is responsible for initial job submission and dispatching jobs to execution hosts based on Libra's decisions.
*   Libra receives job information from SGE and provides scheduling decisions (e.g., job acceptance/rejection, execution host, queue) back to SGE.
*   The SGE interface will require adaptation to support additional job submission parameters specific to Libra's QoS-driven approach (e.g., budget, deadline).
*   Outputs related to job deletion or changes (e.g., updated cluster information, revised scheduling decisions) are facilitated by SGE functionality, not independently produced by Libra.

#### User interfaces
The Libra Scheduler supports two primary user types: the cluster user and the cluster administrator.
*   **Cluster User Interface:** Users interact with the system via the Linux command prompt or through the interface provided by the Sun Grid Engine cluster management system. This interface allows users to:
    *   Submit jobs with associated deadline, cost, and execution time.
    *   Query the cluster for the current cost per unit time for submitting new jobs.
    *   Monitor the status of their submitted jobs.
    *   Cancel jobs they have submitted.
    *   Check their credit balance.
    *   Check their usage history.
*   **Cluster Administrator Interface:** Administrators interact with the system via the Linux command prompt or through the interface provided by the Sun Grid Engine cluster management system. In addition to all user commands, administrators can:
    *   Check the status of each node in 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.
*   At present, only command-line or SGE-provided interfaces are supported. A Graphical User Interface (GUI) may be added in a later version.

#### Hardware interfaces
All hardware interfaces for Libra are inherited from the Sun Grid Engine (SGE) system, on top of which Libra operates. Libra will incorporate SGE's interfaces for managing and monitoring:
*   CPU usage
*   Memory usage
*   Swap file creation
*   Network communication

#### Software interfaces
The Libra Scheduler interfaces with the following software components:
*   **Sun Grid Engine (SGE)**
    *   **Name:** Sun Grid Engine
    *   **Version:** 5.3 (modified)
    *   **Source:** Sun Microsystems, Inc.
    *   **Purpose:** Libra directly interfaces with the modified SGE for job submission, resource allocation, and job execution management. SGE, in turn, interfaces with the underlying operating system and other necessary software components.
*   **Operating System**
    *   **Name:** Linux (implied)
    *   **Version:** [N/A]
    *   **Source:** Open source
    *   **Purpose:** SGE, and by extension Libra, operates on a Linux-based cluster. No modifications to the Linux kernel are required by Libra.
*   **Parallel Virtual Machine (PVM) libraries**
    *   **Name:** PVM (Parallel Virtual Machine)
    *   **Version:** [N/A]
    *   **Source:** University of Tennessee, Oak Ridge National Laboratory, and Emory University
    *   **Purpose:** Used by the cluster for the execution of embarrassingly parallel jobs.
*   **Message Passing Interface (MPI) libraries**
    *   **Name:** MPI (Message Passing Interface)
    *   **Version:** [N/A]
    *   **Source:** University of Chicago and Mississippi State University
    *   **Purpose:** Used by the cluster for the execution of embarrassingly parallel jobs.

#### Communications interfaces
Libra will utilize the existing communications architecture of the Sun Grid Engine itself. It will not introduce any unique communications interfaces beyond those provided by SGE.

#### Memory constraints
[N/A]

#### Operations
The Libra Scheduler supports various operational modes and functions:
*   **User-initiated operations:** Users can submit, monitor, cancel jobs, and query system status and personal account information through command-line or SGE interfaces.
*   **Administrator-initiated operations:** Administrators can perform all user operations, in addition to monitoring cluster health, managing system policies (cost, scheduling), and controlling any submitted job (cancel, suspend, resume).
*   **Automated processing:** Libra performs automated functions such as initializing jobs, accepting/rejecting jobs based on QoS parameters, calculating scheduling information (tickets, stride, pass), determining execution hosts and queues, dispatching jobs, updating cluster status, and executing jobs using the stride-scheduling algorithm.
*   **Data processing support functions:** Libra processes job parameters (budget, deadline, execution time) and cluster information (CPU load, node status, remaining job times, available memory) to make scheduling decisions.
*   **Backup and recovery operations:** [N/A]

#### Site adaptation requirements
The Libra Scheduler is designed to manage jobs on a homogenous Linux cluster. No specific site or mission-related features are defined for modification to adapt the software to a particular installation.

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

### 1.3.2 Product functions
The Libra Scheduler's primary function is to provide Quality of Service (QoS) computational economy in cluster computing by maximizing user utility. It achieves this by scheduling sequential and embarrassingly parallel batch jobs on homogeneous Linux clusters, prioritizing CPU time allocation based on user-defined budget and deadline constraints rather than traditional system performance metrics.

Key functions include:
*   **Job Prioritization and Allocation**: Allocating CPU time to jobs based on user-centric priorities derived from specified budgets and deadlines. The scheduler considers job parameters such as executable location, input data, output destination, system type, maximum execution time, and job parallelism type.
*   **Dynamic Resource Management**: Dynamically reallocating resources to accommodate urgent or high-priority jobs, allowing changes to resource limits, priorities, and execution order.
*   **Scalable Scheduling**: Ensuring performance does not degrade with the addition of nodes and jobs to the cluster.
*   **Configurable Policies**: Allowing for modification of scheduling policies to incorporate various QoS parameters.
*   **Integration and Separability**: Operating as a separable add-on to the Sun Grid Engine (SGE) cluster management system.
*   **Administrative Security**: Providing security for administrative operations.
*   **Job Accounting**: Offering at least a basic level of job accounting to support scheduling decisions.
*   **Economic Model Implementation**: Developing and applying a market-based, bid-based proportional resource-sharing model for resource pricing and allocation.
*   **Resource Enforcement**: Utilizing the proportional stride-scheduling algorithm to ensure actual resource allocation reflects the determined job share.
*   **User and Administrator Interfaces**: Ideally providing a Graphical User Interface (GUI) for users to submit jobs and administrators to oversee scheduling, though initially supporting command-line or SGE interfaces.

### 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 following items limit the supplier's options for the Libra Scheduler:

*   **Scope and Functionality**
    *   The scheduler will only manage sequential and embarrassingly parallel batch jobs.
    *   There will be no mechanism for users to interact with each other or bargain for resources.
    *   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.
    *   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
    *   Exhaustive searches of all job combinations will not be performed; heuristics will be developed for scheduling.

*   **Hardware and Environment**
    *   The current implementation and testing environment is limited to a network of four Pentium-III workstations with 128 MB RAM, running the Sun Grid Engine (SGE) on a Linux operating system.
    *   The scheduler will operate as a sub-component of the Sun Grid Engine cluster management system.
    *   No modifications to the Linux kernel are required.

*   **Interfaces**
    *   Initially, user and administrator interaction will be limited to a command-line Linux interface or the existing Sun Grid Engine interface; a Graphical User Interface (GUI) may be added in a later version.
    *   Libra will directly interface with the modified Sun Grid Engine cluster management system, version 5.3.
    *   Hardware and communication interfaces will be those provided by the Sun Grid Engine.

*   **Quality and Performance**
    *   A maximum bug rate of 1 bug per KLOC is targeted.
    *   All jobs are expected to be completed within a 10% error allowance, assuming accurate job statistics are submitted.
    *   The maximum response time for job submission will be 1 minute.
    *   The maximum cost charged to the user will not exceed the budget submitted by the user.

*   **Security**
    *   The scheduler must ensure the privacy of user job status.
    *   Full control over job execution must be maintained, preventing alteration of scheduling criteria or resource allocation without administrator authority.

*   **Development and Licensing**
    *   All coding will be done in standard C.
    *   All code will adhere to the Hungarian Naming Convention.
    *   The project will be open-source and released under the GNU General Purpose License (GPL); no components will be purchased.

## 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 Requirements
[NULL]

## 3.1 Functions
This section defines the fundamental actions performed by the Libra Scheduler and its interactions within the larger cluster management system. The functional requirements are partitioned into sub-functions, detailing their inputs, processing logic, and outputs.

### 3.1.1 Submit Job

This feature facilitates the submission of jobs by end-users or administrators. It is primarily handled by the Sun Grid Engine (SGE) interface, which will be adapted to include additional parameters required by Libra, or alternatively, a command-line interface will be used.

*   **Inputs:**
    *   User Information: Relevant user data such as name and authentication ID.
    *   Job Information: Details about the job to be submitted, including specifications for new jobs and status of already pending jobs.
    *   Cluster Information: Cluster type, scheduling mechanism details, current load status, submission directions, and criteria.
*   **Processing:**
    1.  The cluster determines if it is currently open for job submissions.
    2.  The system verifies if the user attempting to submit the job is a valid user.
    3.  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 feature allows users or administrators to view details about submitted jobs and their execution progress.

*   **Inputs:**
    *   User ID and Password: Required to ensure only the appropriate user can access job status.
*   **Processing:**
    1.  Authenticate the user based on the provided credentials.
    2.  Display available options regarding the submitted job(s).
    3.  Provide information about the progress of job execution.
    4.  Process selected options if the user chooses 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 feature enables 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 others like output directory or a delayed deadline may be permitted.

*   **Inputs:**
    *   User ID and Password: Required to ensure only the appropriate user can delete or change the job.
*   **Processing:**
    1.  Authenticate the user based on the provided credentials.
    2.  Remove the specified job from the queue.
    3.  Update the cluster status to reflect the job's removal.
    4.  Revise scheduling decisions for pending jobs and the submission of new jobs, as the resource availability has changed.
*   **Outputs:**
    *   Updated cluster information and scheduling decisions, 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 SGE.
*   **Responses to abnormal situations:** [N/A]

### 3.1.4 Initialize Job

This is a core functional requirement that prepares the scheduler for eventual scheduling and execution of a job. It is performed by the Libra scheduler once a job has been accepted by SGE, with information from the scheduler.

*   **Inputs:**
    *   User-submitted job information.
    *   Job ID assigned by SGE.
*   **Processing:**
    1.  Retrieve the detailed information about the job.
    2.  Set these details into variables that represent the current state of the cluster and its queues.
    3.  Pass the parsed job parameters to the scheduling module for further evaluation (e.g., `Accept/Reject Job`).
*   **Outputs:**
    *   Set 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 if the user's requirements (budget and deadline) can be satisfied.

*   **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 execution time of pending jobs.
*   **Processing:**
    1.  Based on the job parameters, the scheduler calculates a priority for the job, reflecting its deserved CPU time share according to specified criteria.
    2.  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 feature of Libra decides how a job will be scheduled based on its budget and deadline. It utilizes the Stride Scheduling Algorithm to enforce resource allocations proportional to a user's budget and deadline. This is performed after Libra has determined that a job can be accommodated.

*   **Inputs:**
    *   Job details: Job ID, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
*   **Processing:**
    1.  Allocate "tickets" to the job based on its budget and deadline, and in consideration of the budgets and deadlines of all other jobs on the potential execution host.
    2.  Calculate the job's "stride," which is the global stride constant divided by the number of allocated tickets.
    3.  Initialize the job's "pass" value to its calculated stride.
*   **Outputs:**
    *   The job's calculated tickets, stride, and pass values.
*   **Responses to abnormal situations:** [N/A]

### 3.1.7 Determine Execution Host

This feature 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, as well as the current cluster state.

*   **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:**
    1.  Libra first assesses the load on each available host and sorts them in ascending order to identify the least loaded host, ensuring load balancing.
    2.  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 feature takes the job and inserts it into the queue on the execution host previously determined by the scheduler. It also decides 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:**
    1.  The scheduler sends the job to the designated queue on the chosen execution host.
    2.  The job then joins the competition for resources within that queue.
*   **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 feature of Libra updates the cluster's status every time 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 (for scheduled jobs).
    *   Chosen execution host and queue (for scheduled jobs).
*   **Processing:**
    1.  Libra reserves the necessary amount of resources on the node for the job.
    2.  It updates the execution host's queue status to reflect the new job or job completion.
    3.  This information about the additional load or freed resources on the queue and node is then sent to the central information store on the master host.
*   **Outputs:**
    *   There is no direct output; this feature primarily performs internal system state updates.
*   **Responses to abnormal situations:** [N/A]

### 3.1.10 Execute Job

This feature continuously runs as long as there are jobs in the queues. It is responsible for making time-slicing decisions among all currently executing jobs, 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:**
    1.  The system examines all jobs across the cluster's queues.
    2.  It selects the job with the minimum "pass" value for execution.
    3.  The selected job is allotted a quantum of CPU time.
    4.  The "pass" value of that job is then advanced by its "stride" value.
    5.  In the event of a tie in "pass" values, jobs are ordered using an arbitrary First-In, First-Out (FIFO) policy.
    6.  This process repeats in a loop until no jobs remain to be run on a queue.
*   **Outputs:**
    *   Updated Cluster Information: Current 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, in conjunction with the Sun Grid Engine (SGE), requires a logical data store to manage information related to users, jobs, and the cluster environment. This data store is referred to as a "central information store" in the original SRS.

a) Types of information used by various functions:
*   **User Information**: User ID, authentication ID, password, name, credit balance, and usage history.
*   **Job Information**: Job ID, job type (sequential or embarrassingly parallel), standalone execution time, location of executable, input data sets, system type, budget, deadline, current status (e.g., pending, executing, completed, cancelled), progress of execution, assigned tickets, stride, pass, chosen execution host, and queue.
*   **Cluster Information**: Cluster type, scheduling mechanism details, current load status (CPU load, node status, remaining time of pending jobs, available memory, queue length, quanta allocated to pending jobs, revised expected finishing deadline of pending jobs), submission directions and criteria, cost structure, and scheduling policy.
*   **Node Information**: Node ID, status, load, available memory, and usage pattern history.

b) Frequency of use:
*   **High Frequency**: Job and cluster status information is frequently accessed and updated during job submission, acceptance, scheduling, execution, and completion. This includes CPU load, node status, queue length, and job progress.
*   **Moderate Frequency**: User credit balance and usage history are accessed when users query their accounts. Administrator-specific data such as node status, cluster usage patterns, cost structure, and scheduling policy are accessed by administrators as needed.
*   **Low Frequency**: Static cluster configuration details are accessed less frequently.

c) Accessing capabilities:
*   **Cluster Users**: Can submit jobs with associated parameters (deadline, cost, execution time), query the current cost per unit time, monitor the status of their submitted jobs, cancel their own jobs, check their credit balance, and view their usage history.
*   **Cluster Administrators**: Have all capabilities of a cluster user. Additionally, they can check the status of each node, view the usage pattern history of the cluster, check the status of all submitted jobs, check the load on each node, alter the cost structure of the cluster, alter the scheduling policy, and cancel, suspend, or resume any job.
*   **Libra Scheduler**: Requires comprehensive access to all job, user, and cluster information to perform scheduling decisions, update statuses, and enforce policies.

d) Data entities and their relationships:
*   **User**: Represents an individual or entity submitting jobs.
    *   Attributes: User ID (primary key), Name, Authentication ID, Password, Credit Balance, Usage History.
*   **Job**: Represents a computational task submitted by a user.
    *   Attributes: Job ID (primary key), Job Type, Standalone Execution Time, Executable Location, Input Data Location, System Type, Budget, Deadline, Status, Progress, Tickets, Stride, Pass, Assigned Host, Assigned Queue.
    *   Relationship: A User can submit multiple Jobs (one-to-many relationship).
*   **Node**: Represents a computational resource within the cluster.
    *   Attributes: Node ID (primary key), Status, Load, Available Memory, Usage History.
    *   Relationship: A Job is assigned to one Node (many-to-one relationship).
*   **Cluster**: Represents the overall computing environment.
    *   Attributes: Cluster Type, Scheduling Mechanism, Current Load Status, Cost Structure, Scheduling Policy.
    *   Relationship: A Cluster comprises multiple Nodes (one-to-many relationship).

e) Integrity constraints:
*   Job IDs and User IDs must be unique.
*   Budget and Deadline values for jobs must be non-negative.
*   Job status transitions must follow a predefined workflow (e.g., a job cannot move from 'completed' to 'pending').
*   Critical scheduling criteria and resource allocations can only be altered with administrator authority.

f) Security:
*   **Privacy**: User job status information must be private, accessible only by the submitting user or an administrator.
*   **Access Control**: Full control over job execution and alteration of scheduling criteria or actual resource allocation is restricted to administrators. User authentication (User ID and Password) is required for accessing and modifying personal job information.

g) Data retention requirements:
*   A basic level of job accounting and usage history must be retained to aid in scheduling policies and allow users and administrators to review past activities. Specific retention periods are not defined in the current requirements.

## 3.6 Design constraints
*   **Parent Component: Sun Grid Engine**
    The Libra scheduler will be a sub-component of SGE.
*   **Software Language**
    All coding will be done in standard C.
*   **Scheduling Constraints**
    Exhaustive searches of the entire set of combinations of jobs will not be done. Heuristics will be developed for this scheduling problem.

## 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 Verification
[NULL]

## 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
The verification of design constraints will involve the following approaches:

*   **Parent Component: Sun Grid Engine**
    Verification will involve integration testing to confirm that the Libra scheduler functions correctly as a sub-component of the Sun Grid Engine (SGE) version 5.3. This includes validating the communication and data exchange through the defined software interfaces with SGE.

*   **Software Language**
    Verification will be performed through code reviews and static analysis tools to ensure that all coding adheres to the standard C language specification.

*   **Scheduling Constraints**
    Verification will involve reviewing the design and implementation of the scheduling algorithms to confirm that they utilize heuristics and do not perform exhaustive searches of job combinations. Performance testing under various load conditions will also be conducted to ensure the efficiency expected from a heuristic-based approach.

## 4.7 Software system attributes
[N/A]

# 5 Appendices
[NULL]

## 5.1 Assumptions and dependencies
A number of factors that may affect the requirements specified in this SRS include:

*   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
*   **CPU**: Central Processing Unit
*   **FIFO**: First-In, First-Out
*   **GPL**: GNU General Purpose License
*   **GUI**: Graphical User Interface
*   **KLOC**: Kilolines of Code
*   **MPI**: Message Passing Interface
*   **PVM**: Parallel Virtual Machine
*   **QoS**: Quality of Service
*   **SGE**: Sun Grid Engine cluster management system
