# 1 Introduction

## 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 to the queuing, scheduling, and resource managing module of the open-source Sun Grid Engine (SGE) cluster management system. The scheduler offers market-based, economy-driven service for managing batch jobs on clusters by scheduling CPU time according to user utility rather than system performance considerations, thereby providing Quality of Service (QoS) computational economy in cluster computing.

As part of the project, Libra will manage sequential and embarrassingly parallel batch jobs on a homogenous Linux cluster. Its functionality can be adapted to schedule resources other than CPU time, even on a heterogeneous cluster. To provide QoS to users, there will be no mechanism for users to interact or bargain on resource use (unlike grid-computing environments such as Nimrod/G).

## 1.3 Product overview

### 1.3.1 Product perspective
Libra forms part of a larger system comprising the SGE cluster management system that runs on a Linux-based cluster. SGE is responsible for receiving jobs submitted by users and delegating them to Libra for scheduling and placement on appropriate execution hosts. Libra communicates its workstation allocation decision to the resource manager, which then dispatches the job to the chosen workstation. Once assignment to a workstation has occurred, Libra implements the scheduling policy on jobs executing at the workstations. No modifications to the Linux kernel are required.

- System interfaces
  - Integrates with SGE to receive job submissions, return allocation decisions, and update cluster status.
  - Interfaces with SGE’s resource manager for job dispatch to execution hosts.
- User interfaces
  - Command-line tools via Linux and SGE interface for two user types (cluster user and administrator).
  - User actions include: submit job (with deadline, cost, execution time), query current cost per unit time, monitor job status, cancel own jobs, check credit balance, and usage history.
  - Administrator actions include: check node and cluster status, view all jobs, check load, alter cost structure, alter scheduling policy, and cancel/suspend/resume any job.
- Hardware interfaces
  - Via SGE for CPU usage, memory usage, swap file creation, and network communication on homogenous Linux nodes.
- Software interfaces
  - Sun Grid Engine, version 5.3 (cluster management; job queueing/scheduling integration).
  - PVM and MPI libraries for execution of embarrassingly parallel jobs.
  - Linux operating system.
- Communications interfaces
  - Utilizes SGE’s communications architecture and network protocols; no unique communications beyond SGE.
- Memory constraints
  - [N/A]
- Operations
  - Normal operations include continuous scheduling and execution of jobs using stride scheduling, periodic updates to cluster status, and user/administrator command execution.
  - Unattended operations include batch job execution on queues.
  - Backup/recovery operations: in case of outage, recovery occurs via OS reboot (< 5 minutes).
- Site adaptation requirements
  - Cost structure and scheduling policy configurable by administrator.
  - Integration and configuration through SGE to match site-specific cluster characteristics.
- Interfaces with services
  - [N/A]

### 1.3.2 Product functions
- Accept and validate job submissions with QoS parameters (budget and deadline) and job specifications.
- Determine job accept/reject decisions based on feasibility against deadline and budget.
- Compute scheduling parameters (tickets, stride, pass) using a bid-based proportional resource-sharing model and stride scheduling.
- Select execution host and queue based on load, job type, and constraints.
- Dispatch accepted jobs to selected queues.
- Enforce proportional CPU allocations via stride scheduling across executing jobs.
- Update cluster status on job scheduling, dispatch, and completion.
- Provide user capabilities to view job status and cancel or change certain job parameters (within constraints).
- Provide administrative security and job accounting at a basic level.
- Support scalability, configurability, and separation from the cluster management system.

### 1.3.3 User characteristics
- Cluster user: Understands job nature and execution/resource requirements; able to use Linux/SGE interfaces.
- Administrator: Advanced cluster operator; fully qualified in Linux, SGE, and Libra Scheduler.

### 1.3.4 Limitations
- Functional limits:
  - Manages sequential and embarrassingly parallel jobs; no true interdependent parallel threads.
  - Homogenous Linux cluster assumed.
  - No user-to-user market interaction/bargaining.
  - No job migration for reducing resource fragmentation.
- Project/resource constraints:
  - Current test environment: four Pentium-III workstations with 128 MB RAM and SGE on Linux.
  - Simulation tool for testing may need to be developed if a suitable free tool is unavailable.
- Scheduling constraints:
  - No exhaustive search of all job combinations; heuristic approaches to be used.
- Quality and security:
  - Administrative security required; privacy of user job status enforced.
- Interfaces and dependencies:
  - Dependent on SGE modules for process migration and resource management.
- Future work:
  - Detailed pricing front-end and GUI to be specified/added in later versions.

## 1.4 Definitions
- Cluster/Cluster Computing: Connected computers acting as an integrated resource providing a single system image for high-performance applications.
- QoS (Quality of Service): Meeting user needs to maximize utility.
- Computational Economy: User-centric resource management based on user-specified QoS parameters (e.g., deadline, budget) rather than system-centric policies.
- Linux: Open-source operating system.
- Grid Computing: Infrastructure coupling distributed resources and presenting them as a unified resource.
- Bid-based Proportional Resource-Sharing Model: Allocates resources proportionally to user bids/priorities, here evaluated via deadline and budget.
- Stride Scheduling: Deterministic algorithm scheduling jobs in proportion to allocated tickets; stride inversely proportional to tickets.
- Process Migration: Moving a job between systems without restarting.
- Sequential Jobs: Jobs that run on a single node and cannot be split.
- Embarrassingly Parallel Jobs: Independent parts that can run on separate nodes with minimal communication.
- Job accounting: Quantifying 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 with freely available source code.
- Homogenous cluster: Cluster with uniform node characteristics and OS.

# 2 References
- 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

## 3.1 Functions
- Submit Job
  - Inputs: User information; job information; cluster information (type, scheduling mechanism, current load, submission criteria).
  - Processing: Verify cluster is accepting submissions and user is valid. Distinct from accept/reject based on QoS.
  - Outputs: Boolean for acceptance of submission window; boolean for user verification.
- View Job Status
  - Inputs: User ID and password.
  - Processing: Present available options and status of submitted jobs; process user selections.
  - Outputs: Views of available options and job progress.
- Delete/Change Job
  - Inputs: User ID and password.
  - Processing: Remove job from queue and update cluster status; revise scheduling/resource allocation; permit limited parameter changes (e.g., output directory, delayed deadline).
  - Outputs: Updated cluster information and scheduling decisions (CPU load, node status, queue length, quanta allocations, revised expected deadlines).
- Initialize Job
  - Inputs: User-submitted job details; SGE-assigned job ID.
  - Processing: Retrieve and parse job details; set scheduler state variables; pass parameters to scheduling for accept/reject.
  - Outputs: Parsed job details (Job ID, type, execution time, executable/data locations, system type, budget, deadline).
- Accept/Reject Job
  - Inputs: Job details; cluster information (CPU load, node status, remaining time of pending jobs).
  - Processing: Compute job priority/share based on budget and deadline; assess feasibility to meet deadline given execution time and current system state.
  - Outputs: Boolean accept/reject; suggested alternative deadline or cost if needed for acceptance.
- Calculate Scheduling Information
  - Inputs: Job details.
  - Processing: Allocate tickets based on budget/deadline relative to other jobs; compute stride (global_stride/tickets) and initial pass.
  - Outputs: Tickets, stride, and pass per job.
- Determine Execution Host
  - Inputs: Job details; cluster information (CPU load, node status, remaining time of pending jobs, available memory).
  - Processing: Sort hosts by load; select least loaded host; choose appropriate queue (sequential vs. embarrassingly parallel, budget, etc.).
  - Outputs: Chosen execution host and queue.
- Dispatch Job
  - Inputs: Chosen execution host and queue.
  - Processing: Insert job into selected queue; defer dispatch when appropriate to respect urgency/deadlines of other jobs.
  - Outputs: Scheduled job placed on appropriate host and queue.
- Update Cluster Status
  - Inputs: Job details; chosen execution host and queue.
  - Processing: Reserve required resources on node; update execution host queue status; propagate load updates to master host information store.
  - Outputs: None (internal state update).
- Execute Job
  - Inputs: Scheduled jobs; scheduling information (tickets, stride, pass).
  - Processing: Select job with minimum pass; allot quantum; advance job’s pass by stride; use FIFO tie-breaker; repeat while jobs remain.
  - Outputs: Updated cluster information (CPU load, node status, remaining time of pending jobs, available memory).

Responses to abnormal situations, detailed validity checks, and error handling and recovery: [N/A]

## 3.2 Performance requirements
- Response time: Maximum response time for job submission shall be 1 minute.
- Capacity: No inherent upper limit in Libra on number of jobs; practical limits governed by node capacity to meet job deadlines.
- Deadline sensitivity: Assuming accurate job statistics on submission, all jobs shall be completed within a 10% error allowance of their deadlines.
- Cost sensitivity: Under all circumstances, the user shall not be charged above the submitted maximum cost.

## 3.3 Usability requirements
[N/A]

## 3.5 Logical database requirements
[N/A]

## 3.6 Design constraints
- Parent component: Libra is a sub-component of Sun Grid Engine.
- Software language: Standard C.
- Scheduling constraints: No exhaustive combinatorial searches; heuristics will be developed.
- Supportability standards:
  - Naming convention: Hungarian Naming Convention.
  - Licensing/coding standards: GNU General Public License requirements for code and documentation.
- Licensing: Libra will be released under GPL and will be open-source.
- Purchased components: None (entire project is open source).

## 3.7 Software system attributes
- Reliability and maintainability
  - Maximum bug rate: ≤ 1 bug/KLOC.
  - No job migration for the purpose of decreasing resource fragmentation.
- Availability
  - Maximum time to repair: In case of outage, recovery is bounded by Linux OS boot time (< 5 minutes).
- Security
  - Ensure privacy of user job status.
  - Administrative control over job execution; prevent unauthorized alteration of scheduling criteria or resource allocation.
- Portability
  - [N/A]

## 3.8 Supporting information
- Online documentation: All documentation shall comply with GNU GPL requirements; man pages shall be provided on Linux.
- User interfaces: Command-line via Linux/SGE for users and administrators.
- Interfaces summary:
  - Hardware: Through SGE (CPU, memory, swap, network).
  - Software: SGE v5.3; PVM/MPI for embarrassingly parallel jobs; Linux OS.
  - Communications: Uses SGE’s communications architecture.
- Legal, copyright, and other 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.
- Deferred/apportioned requirements:
  - Detailed economic front-end (pricing/costing policy) to be specified in a later version; does not affect scheduling policies.
  - GUI may be added after basic functionality.
  - Simulation/testing tool may be developed or replaced with a suitable free generic tool.
- Appendices contain background research, data flow diagrams, and data dictionary.

# 4 Verification

## 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

## 5.1 Assumptions and dependencies
- SGE modules (including those relevant to process migration) are assumed to be workable with Libra’s scheduling policies.
- A basic job accounting and payment module will be provided; detailed billing is out of scope for the scheduler.
- Users are assumed to provide fair estimates of job execution times to facilitate accept/reject decisions.

## 5.2 Acronyms and abbreviations
- CPU: Central Processing Unit
- 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
- SRS: Software Requirements Specification