# 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
- Product name: Libra Scheduler.
- What the product will do: Provide market-based, economy-driven service for managing batch jobs on clusters by scheduling CPU time according to user utility (budget and deadline) rather than purely system performance considerations, thereby providing Quality of Service (QoS) computational economy.
- Application, benefits, objectives and goals:
  - Operates as an add-on to the queuing, scheduling and resource managing module of the open source Sun Grid Engine (SGE) cluster management system (formerly Codine).
  - Schedules CPU time to maximize user utility within user-imposed constraints.
  - Manages sequential and embarrassingly parallel batch jobs on a homogeneous Linux cluster.
  - Can be adapted to other resources (beyond CPU time) and heterogeneous clusters.
  - No user-to-user bargaining mechanism (unlike grid systems such as Nimrod/G) to keep QoS user-centric and scheduler-driven.
- Consistency with higher-level specifications: [N/A]

## 1.3 Product overview
[NULL]

### 1.3.1 Product perspective
Libra is a sub-component of the Sun Grid Engine (SGE) cluster management system running on a Linux-based cluster. SGE receives jobs from users, delegates them to Libra for scheduling, and dispatches them to execution hosts per Libra’s allocation decisions. Libra implements the scheduling policy on jobs executing at workstations. No Linux kernel modifications are required.

#### System interfaces
- Interfaces with SGE modules for job submission, queue management, and dispatching.
- Libra provides:
  - Decision on execution host and queue for each accepted job.
  - Scheduling parameters per job (tickets, stride, pass) for proportional resource sharing.
  - Updates to cluster status maintained by SGE (e.g., node load, queue state).

#### User interfaces
- Two user types: cluster user and cluster administrator.
- Cluster user capabilities (via Linux CLI or SGE UI):
  - Submit jobs with deadline, budget (cost), and execution time.
  - Query current cost per unit time for submitting new jobs.
  - Monitor status of submitted jobs.
  - Cancel submitted jobs.
  - Check credit balance.
  - Check usage history.
- Cluster administrator capabilities (via Linux CLI or SGE UI), in addition to user capabilities:
  - Check status and load of each node.
  - Check status of all submitted jobs.
  - Review cluster usage history and patterns.
  - Alter cost structure and scheduling policy.
  - Cancel, suspend, and resume any job.

#### Hardware interfaces
- Inherits SGE’s hardware interfaces for:
  - CPU usage.
  - Memory usage.
  - Swap file creation.
  - Network communication.
- Cluster runs on homogeneous Linux workstations.

#### Software interfaces
- Sun Grid Engine (SGE) cluster management system (version 5.3).
- Operating system: Linux (no kernel changes required).
- Libraries for embarrassingly parallel jobs: PVM (Parallel Virtual Machine) and MPI (Message Passing Interface).

#### Communications interfaces
- Uses SGE’s communications architecture and protocols.
- No additional communications interfaces unique to Libra.

#### Memory constraints
- [N/A]

#### Operations
- User-initiated operations:
  - Submit job (with budget and deadline).
  - View job status.
  - Delete/change job (limited parameters; e.g., output directory, delayed deadline).
- Administrator operations:
  - Alter cost structure and scheduling policy.
  - Manage jobs (cancel, suspend, resume).
  - Monitor nodes and cluster load.
- Backup and recovery operations: [N/A]
- Modes of operation and unattended operation periods: [N/A]

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

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

### 1.3.2 Product functions
- Accept/reject job based on user-specified budget and deadline, job execution time, and current cluster load.
- Compute proportional shares and scheduling parameters per job using an economy model (bid-based proportional resource sharing) and enforce them via stride scheduling.
- Determine execution host and queue, considering load and job type (sequential vs. embarrassingly parallel).
- Dispatch jobs to execution queues when appropriate.
- Time-slice CPU among runnable jobs according to stride scheduling (min-pass selection, FIFO tie-break).
- Maintain and update cluster status on job scheduling and completion.
- Provide interfaces for users to submit, monitor, and manage their jobs; provide administrative controls for cost and policy adjustments.
- Provide basic job accounting to support scheduling policies.

### 1.3.3 User characteristics
- Cluster users:
  - Know the nature of their jobs (execution time estimate, resource needs).
  - Possess technical know-how to use CLI/SGE UI for job submission and monitoring.
- Cluster administrators:
  - Advanced cluster operators.
  - Fully qualified in Linux, SGE, and Libra.

### 1.3.4 Limitations
- Functional:
  - Manages only sequential and embarrassingly parallel batch jobs.
  - No mechanism for user-to-user bargaining or market negotiation.
  - No process migration for the purpose of reducing resource fragmentation.
  - Exhaustive search across all job combinations will not be performed; heuristics will be used.
- Platform:
  - Designed for homogeneous Linux clusters integrated with SGE.
  - No Linux kernel modifications required.
- Quality and operational constraints:
  - Maximum response time for job submission is 1 minute.
  - All jobs targeted to complete within a 10% allowance of deadline, assuming accurate user estimates.
  - Maximum user-submitted budget is an upper bound on charge.
- Project/testbed constraints:
  - Initial test environment: four Pentium-III workstations with 128 MB RAM each, running SGE on Linux.
  - Simulation tool may be required; may need to be designed if a suitable free tool is unavailable.

## 1.4 Definitions
- Cluster/Cluster Computing: Connecting two or more computers to act as an integrated collection of resources providing a single system image across nodes.
- QoS (Quality of Service): Meeting what users actually want, maximizing their utility.
- Computational Economy: Inclusion of user-specified QoS parameters (e.g., deadline, budget) so resource management is user-centric rather than system-centric.
- Linux: An open source operating system with extensive documentation and support.
- Grid Computing: Infrastructure that couples resources (computers, software, devices) across the Internet as a unified resource; grid computing uses such infrastructure for processing.
- Bid-based Proportional Resource-Sharing Model: Economic model allocating resources between competing users in proportion to their bids, adapted here using budget and deadline.
- Stride Scheduling: Deterministic algorithm enforcing resource allocations proportional to per-job ticket counts via stride and pass values.
- Process Migration: Moving a job from one system to another without restart.
- Sequential Jobs: Jobs that run on a single node and cannot be split.
- Embarrassingly Parallel Jobs: Parallel jobs comprised of independent parts with minimal inter-job communication.
- Job Accounting: Quantification of system resources used by a job.
- GUI: Graphical user interface.
- CPU: Central Processing Unit.
- SGE: Sun Grid Engine cluster management system.
- Open-source software: Software for which the code is freely available.
- Homogenous cluster: Cluster whose nodes have uniform characteristics (e.g., memory, disk) and OS.

# 2 References
- Compliance
  - [N/A]

- Guidance
  - 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.
  - 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.
  - 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, San Francisco, California, USA, April 2001.
  - Rajkumar Buyya, Heinz Stockinger, Jonathan Giddy, and David Abramson, Economic Models for Management of Resources in Peer-to-Peer and Grid Computing, Monash University.
  - B. N. Chun and D. E. Culler, Market-based proportional resource sharing for clusters. Submitted for publication, September 1999.

# 3 Requirements
[NULL]

## 3.1 Functions
- Submit Job
  - Inputs:
    - User information (name, authentication ID).
    - Job information (see Initialize Job).
    - Cluster information (cluster type, scheduling mechanism, current load status, submission criteria).
  - Processing:
    - Verify cluster acceptance of submissions.
    - Verify user is authorized.
    - Note: This differs from Accept/Reject Job, which evaluates feasibility against budget/deadline.
  - Outputs:
    - Boolean: cluster accepting submissions.
    - Boolean: user verified.
- View Job Status
  - Inputs:
    - User ID and password.
  - Processing:
    - Present options and current job execution progress; process option selection.
  - Outputs:
    - User view of options and job status details.
- Delete/Change Job
  - Inputs:
    - User ID and password.
  - Processing:
    - Remove job from queue or update allowed parameters (e.g., output directory, delayed deadline).
    - Update cluster status and revise scheduling decisions accordingly.
  - Outputs:
    - Updated cluster information and scheduling decisions (CPU load, node status, queue length, quanta allocation, revised expected completion times).
- Initialize Job
  - Inputs:
    - User-submitted job details plus SGE-assigned job ID.
  - Processing:
    - Retrieve and parse job details; set variables representing cluster and queue state.
    - Pass parsed parameters to scheduling for accept/reject.
  - Outputs:
    - Job details variables: job ID, job type, standalone execution time, executable/input locations, system type, budget, deadline.
- Accept/Reject Job
  - Inputs:
    - Job details (ID, type, execution time, locations, system type, budget, deadline).
    - Cluster information (CPU load, node status, remaining time of pending jobs).
  - Processing:
    - Determine job priority/share based on budget and deadline relative to other jobs and system state.
    - Assess feasibility to meet the deadline given execution time and competing workloads.
  - Outputs:
    - Boolean: accepted or rejected.
    - Suggested deadline or cost adjustments required for acceptance.
- Calculate Scheduling Information
  - Inputs:
    - Job details (ID, type, execution time, locations, system type, budget, deadline).
  - Processing:
    - Allocate tickets based on budget and deadline relative to other jobs on the execution host.
    - Compute stride (global stride constant divided by tickets) and initialize pass (equal to stride).
  - Outputs:
    - Scheduling info: tickets, stride, pass per job.
- Determine Execution Host
  - Inputs:
    - Job details (ID, type, execution time, locations, system type, budget, deadline).
    - Cluster information (CPU load, node status, remaining time of pending jobs, available memory).
  - Processing:
    - Rank hosts by ascending load to balance load.
    - Select appropriate queue considering job type and QoS parameters.
  - Outputs:
    - Chosen execution host and queue.
- Dispatch Job
  - Inputs:
    - Chosen execution host and queue.
  - Processing:
    - Insert job into queue at selected host; may delay dispatch to optimize overall QoS.
  - Outputs:
    - Scheduled job placed on appropriate host and queue.
- Update Cluster Status
  - Inputs:
    - Job details (ID, type, execution time, locations, system type, budget, deadline).
    - Chosen execution host and queue.
  - Processing:
    - Reserve required resources on the node.
    - Update execution host queue status and propagate to central information store on master host.
  - Outputs:
    - None (state update trigger).
- Execute Job
  - Inputs:
    - Scheduled job details and its assigned queue/node.
    - Scheduling information (tickets, stride, pass).
  - Processing:
    - Select job with minimum pass; allocate one quantum; advance its pass by its stride; FIFO on ties.
    - Repeat while jobs remain in the queue.
  - Outputs:
    - Updated cluster information (CPU load, node status, remaining time of pending jobs, available memory).

## 3.2 Performance requirements
- Response time:
  - The maximum response time for the submission of a job shall be 1 minute.
- Capacity:
  - The number of jobs schedulable is limited only by node capacity to fulfill deadlines; no inherent upper limit in Libra.
- Deadline sensitivity:
  - Assuming submitted job statistics are accurate, all jobs shall be completed within a 10% error allowance on deadlines.
- Cost sensitivity:
  - Under all circumstances, the maximum cost charged shall not exceed the maximum cost submitted by the user.

## 3.3 Usability requirements
- [N/A]

## 3.5 Logical database requirements
- [N/A]

## 3.6 Design constraints
- Parent component and platform:
  - Libra shall be a sub-component of Sun Grid Engine (SGE).
  - Operates on Linux; no kernel modifications required.
- Implementation language:
  - All coding shall be done in standard C.
- Scheduling constraints:
  - Exhaustive searches across all combinations of jobs shall not be performed; heuristics shall be used.
- Coding standards and conventions:
  - All code shall adhere to GNU General Public License requirements.
  - All code shall follow the Hungarian Naming Convention.

## 3.7 Software system attributes
- Reliability:
  - Maximum bug rate: 1 bug/KLOC.
  - The scheduler will not support job migration for reducing resource fragmentation.
- Availability:
  - In case of system outage, cluster downtime is limited to Linux OS boot time, less than five minutes.
- Security:
  - Ensure privacy of user job status.
  - Ensure full control over job execution; alteration of scheduling criteria or resource allocation requires administrator authority.
- Maintainability:
  - Supported by adherence to naming conventions and coding standards noted in Design constraints.
- Portability:
  - Tied to Linux environments with SGE and standard C; no kernel changes required. [Further portability details: N/A]

## 3.8 Supporting information
- Online user documentation and help:
  - Documentation shall comply with open-source requirements under the GNU General Public License.
  - Online user documentation shall be provided as Linux man pages.
- Licensing:
  - Libra shall be released under a GPL license and be open-source.
- Purchased components:
  - None; the entire project is open-source.
- Legal, copyright and notices:
  - Sun Grid Engine (SGE) is a trademark of Sun Microsystems, Inc.
  - Libra Scheduler is a 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.
- Apportionment of requirements:
  - Detailed pricing/costing policy (economic front-end) will be specified in a later version; core scheduling assumes given cost and budget.
  - Initial interfaces are CLI/SGE UI; a GUI may be added after basic functionality.
  - Decision pending on use/design of a simulation tool for testing.
- Note: Unless explicitly stated as a requirement above, these items are provided as supporting/background information.

# 4 Verification
[NULL]

## 4.1 Functions
- [N/A]

## 4.2 Performance requirements
- [N/A]

## 4.3 Usability requirements
- [N/A]

## 4.5 Logical database requirements
- [N/A]

## 4.6 Design constraints
- [N/A]

## 4.7 Software system attributes
- [N/A]

# 5 Appendices
[NULL]

## 5.1 Assumptions and dependencies
- The workability of SGE modules (e.g., process migration) with Libra’s scheduling policies is assumed.
- A basic module of job accounting and payment will be provided; detailed billing is not the scheduler’s focus.
- Users are assumed to have a fair estimate of job execution times to facilitate accept/reject decisions.
- Hardware testbed currently limited (four Pentium-III nodes with 128 MB RAM); larger dedicated resources would improve performance analysis.
- For testing, a simulation tool is required and may need to be specially designed if no suitable free tool is available.

## 5.2 Acronyms and abbreviations
- CPU: Central Processing Unit.
- FIFO: First-In, First-Out.
- GPL: GNU General Public License.
- GUI: Graphical User Interface.
- MPI: Message Passing Interface.
- PVM: Parallel Virtual Machine.
- QoS: Quality of Service.
- SGE: Sun Grid Engine.
