# 1 Introduction
[NULL]

## 1.1 Purpose
This Software Requirements Specification (SRS) describes the requirements and specifications of Libra, an economy-driven cluster scheduler. It explains functional features, interfaces, design constraints, and performance characteristics for stakeholders such as owners and users of high-performance clusters, cluster management software, job schedulers, and grid resources.

## 1.2 Scope
- Product name: Libra Scheduler.
- What it does: Provides market-based, economy-driven scheduling of CPU time to manage batch jobs on clusters, optimizing Quality of Service (QoS) based on user utility (budget and deadline) rather than purely system-centric performance policies.
- Application, benefits, objectives:
  - Operates as an add-on to the Sun Grid Engine (SGE) cluster management system.
  - Schedules sequential and embarrassingly parallel batch jobs on homogeneous Linux clusters.
  - Enforces proportional resource allocation using a bid-based economic model and stride scheduling to meet user QoS constraints.
  - Aims to maximize user satisfaction while maintaining efficient cluster utilization.
- Consistency: Designed to integrate with SGE without kernel modifications.

## 1.3 Product overview
[NULL]

### 1.3.1 Product perspective
Libra is a sub-component of the Sun Grid Engine (SGE) cluster management system on Linux. SGE receives job submissions and delegates scheduling to Libra. Libra determines resource allocation and communicates execution host and queue decisions back to SGE’s resource manager, which dispatches jobs. Libra also implements the runtime scheduling policy on execution hosts. No Linux kernel changes are required.

- System interfaces
  - Interfaces with SGE for job submission, queueing, dispatching, and resource management.
  - Exchanges cluster status information (CPU load, node status, pending job times) with SGE’s master host resource manager.
  - [N/A] for formal system interface specifications or message formats.

- User interfaces
  - Command-line access via Linux and/or SGE’s interface.
  - Cluster user commands:
    - Submit jobs with deadline, budget (cost), and execution time.
    - Query current cost per unit time for new job submissions.
    - Monitor job status.
    - Cancel submitted jobs.
    - Check credit balance and usage history.
  - Cluster administrator commands (in addition to user commands):
    - Check per-node status and cluster load.
    - Review cluster usage history and all submitted jobs.
    - Alter cost structure and scheduling policy.
    - Cancel, suspend, and resume any job.
  - A GUI is desirable but not required in the initial version.

- Hardware interfaces
  - Uses SGE’s hardware interfaces for CPU usage, memory usage, swap file creation, and network communication.
  - No direct hardware control beyond what SGE exposes.
  - [N/A] for specific hardware configuration protocols.

- Software interfaces
  - Sun Grid Engine (SGE), version 5.3 (source: Sun Microsystems), serves as the cluster manager.
  - Linux operating system (open source).
  - PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) libraries for execution of embarrassingly parallel jobs.
  - [N/A] for formal specification numbers, detailed message formats, or versions for PVM/MPI beyond their identification.

- Communications interfaces
  - Utilizes SGE’s communications architecture; no additional communications protocols are introduced by Libra.
  - [N/A] for protocol-level details.

- Memory constraints
  - [N/A]

- Operations
  - User-initiated operations include job submission, status query, and job cancellation/changes (with limited changeability for critical parameters such as budget and deadline).
  - Administrator operations include system monitoring, policy and cost adjustments, and job control.
  - Continuous runtime scheduling uses stride scheduling to time-slice jobs on execution hosts.
  - Recovery: In case of outage, restart is bounded by Linux boot time (< 5 minutes).
  - [N/A] for backup procedures and unattended operation specifics.

- Site adaptation requirements
  - Configurable scheduling policies to incorporate QoS parameters.
  - Configurable cost structure by administrators.
  - [N/A] for additional site-specific data or initialization sequences.

- Interfaces with services
  - [N/A]

### 1.3.2 Product functions
- Submission gating: Determine if the cluster is open for submissions and authenticate users.
- Initialize job: Parse and register job parameters received from SGE.
- Accept/Reject job: Decide feasibility against user-entered budget and deadline, propose alternative budget/deadline if needed.
- Calculate scheduling information: Allocate tickets and compute stride/pass per job using a bid-based proportional resource-sharing model and stride scheduling.
- Determine execution host and queue: Choose host/queue considering load, job type (sequential or embarrassingly parallel), budget, and deadline.
- Dispatch job: Insert into the chosen queue at the chosen host at an appropriate time.
- Update cluster status: Reserve resources, update queue/node status, and publish load changes to the master host.
- Execute job: Enforce proportional CPU allocations via stride scheduling, assigning quanta based on lowest pass value across jobs.
- User/administrator utilities: View job status, delete/cancel jobs, limited parameter changes (non-critical), administrative monitoring, policy and cost structure changes.
- Accounting basics: Maintain minimal job accounting to support scheduling policies.

### 1.3.3 User characteristics
- Users: Cluster users submitting jobs; cluster administrators overseeing scheduling and usage.
- User knowledge: Ability to characterize job execution time and resource needs; familiarity with Linux command-line or SGE interface.
- Administrator expertise: Advanced skills in Linux, SGE, and the Libra scheduler.

### 1.3.4 Limitations
- Supported jobs: Sequential and embarrassingly parallel jobs only; no support for tightly-coupled parallel jobs.
- Cluster environment: Homogeneous Linux clusters; functionality may be adaptable to heterogeneous environments but is not the current target.
- Economic interaction: No user-to-user bargaining mechanisms; not a grid-scale market like Nimrod/G.
- Scheduling: No exhaustive combinatorial searches; relies on heuristics and proportional allocation.
- Process migration: Not supported for reducing resource fragmentation.
- Interfaces: Initially command-line/SGE interface; GUI is optional and deferred.
- Parent dependency: Operates as an add-on within SGE; leverages SGE’s hardware and communications interfaces.
- Quality limits:
  - Maximum bug rate: 1 bug/KLOC.
  - Deadline adherence: Jobs completed within 10% error allowance (assuming accurate user-provided statistics).
  - Cost cap: Users are never charged more than the specified maximum budget.

## 1.4 Definitions
- Cluster/Cluster Computing: Connected computers acting as an integrated resource with a single system image used for high-performance applications (e.g., AI, simulations, scientific computing).
- QoS (Quality of Service): Meeting user needs to maximize their utility.
- Computational Economy: Inclusion of QoS parameters (e.g., deadline, budget) to prioritize user-centric scheduling over system-centric policies.
- Linux: Open-source operating system.
- Grid Computing: Infrastructure coupling distributed resources (computers, software, devices) across the Internet as a unified resource for processing jobs.
- Bid-based Proportional Resource-Sharing Model: Economic model allocating resources proportional to user bids (credits/priorities), here derived from deadlines and budgets under system load considerations.
- Stride Scheduling: Deterministic algorithm enforcing proportional resource allocation via tickets (rights), stride (inverse of tickets), and pass values.
- Process Migration: Moving a job between systems without restarting it.
- Sequential Jobs: Jobs that run on a single node and cannot be split.
- Embarrassingly Parallel Jobs: Parallel jobs with independent parts requiring minimal inter-job communication, executable as separate sequential jobs.
- 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 with freely available source code.
- Homogeneous cluster: Cluster with uniform node characteristics running the same 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, 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.
  - R. Buyya, H. Stockinger, J. Giddy, D. 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).
    - Job information (including system type, execution time, job type, locations, output destination).
    - Cluster information (cluster type, scheduling mechanism, current load, submission criteria).
  - Processing:
    - Determine if the cluster accepts submissions.
    - Verify user authentication.
    - Note: Distinct from Accept/Reject Job, which considers budget/deadline feasibility.
  - Outputs:
    - Boolean: submission window open/closed.
    - Boolean: user verification success/failure.

- View job status
  - Inputs: User ID and password.
  - Processing: Present options and retrieve job progress/status views.
  - Outputs: User-facing job status and available options.

- Delete/Change job
  - Inputs: User ID and password.
  - Processing: Remove job from queue or apply permissible parameter changes (e.g., output directory or relaxed deadline). Update scheduling and cluster state.
  - Outputs: Updated cluster information (CPU load, node status, queue length, allocated quanta, revised expected completion times).

- Initialize job
  - Inputs: User-submitted job details; SGE-assigned job ID.
  - Processing: Retrieve and parse job details; set internal state variables; pass parameters to scheduling module.
  - Outputs: Registered job details (ID, type, standalone exec time, executable/data locations, system type, budget, deadline).

- Accept/Reject job
  - Inputs: Job details; cluster information (CPU load, node status, remaining times of pending jobs).
  - Processing: Compute job priority/share from budget and deadline; determine if completion by deadline is feasible given execution time and competing workloads.
  - 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 on the execution host; compute stride (global stride constant ÷ tickets) and initial pass (equal to stride).
  - Outputs: Scheduling parameters (tickets, stride, pass).

- Determine execution host
  - Inputs: Job details; cluster information (CPU load, node status, remaining times of pending jobs, available memory).
  - Processing: Sort hosts by ascending load; select least loaded; choose appropriate queue based on job type, budget, etc.
  - Outputs: Selected execution host and queue.

- Dispatch job
  - Inputs: Selected host and queue.
  - Processing: Insert job into the queue at the execution host at an appropriate time.
  - Outputs: Job scheduled on the chosen host and queue.

- Update cluster status
  - Inputs: Job details; selected host and queue.
  - Processing: Reserve required resources; update execution host queue and node status; propagate updated load/info to the master host’s information store.
  - Outputs: [N/A] (internal state update; no direct user-visible output).

- Execute job
  - Inputs: Scheduled jobs with their queue and node; scheduling parameters (tickets, stride, pass).
  - Processing: Select job with minimum pass; allocate a quantum; advance its pass by its stride; use FIFO tie-breaker; loop while jobs remain in the queue.
  - Outputs: Updated cluster information (CPU load, node status, remaining time of pending jobs, available memory).

- Input validity checks
  - User authentication required for submission, status view, and deletion/changes.
  - Submission acceptance depends on cluster submission window status.

- Responses to abnormal situations
  - [N/A] for overflow handling, communication failures, hardware faults, and explicit error handling/recovery behaviors.

- Effect of parameters
  - Budget and deadline critically influence acceptance decisions and proportional resource allocation.
  - Job type (sequential vs. embarrassingly parallel) influences queue selection and execution strategy.

- Relationship of outputs to inputs
  - Acceptance decisions map from budget, deadline, and execution time under current load.
  - Scheduling parameters (tickets/stride/pass) derive from budget/deadline relative to other jobs.

## 3.2 Performance requirements
- Response time: Maximum 1 minute to respond to the submission of a job.
- Capacity: No inherent upper limit in Libra; practical limit is determined by node capacity to meet job deadlines.
- Deadline sensitivity: Assuming accurate user-specified statistics, all jobs shall complete within a 10% error allowance of their deadlines.
- Cost sensitivity: Under all circumstances, charges shall not exceed the user’s specified maximum budget.

## 3.3 Usability requirements
- [N/A]

## 3.5 Logical database requirements
- Types of information:
  - Minimal job accounting information to support scheduling policies.
  - User credit balance and usage history (as exposed via user/admin commands).
- Integrity/security: Privacy of user job status must be ensured; administrative control over job execution and scheduling criteria is required.
- Frequency/access/retention/relationships: [N/A]

## 3.6 Design constraints
- Parent component: Libra is a sub-component/add-on to Sun Grid Engine (SGE).
- Software language: Standard C.
- Scheduling constraints: No exhaustive combinatorial searches; heuristics with proportional allocation are used.
- Naming convention: Hungarian Naming Convention.
- Licensing: GNU General Public License (GPL); open-source release.
- Documentation: Man pages and documentation per GPL/open-source requirements.
- Purchased components: None; all components are open-source.

## 3.7 Software system attributes
- Reliability
  - Maximum bug rate: 1 bug/KLOC.
- Availability
  - Maximum time to repair after outage: less than five minutes (Linux boot time).
- Security
  - Ensure privacy of user job status.
  - Prevent alteration of scheduling criteria or resource allocation without administrator authority.
- Maintainability
  - [N/A] beyond adherence to naming conventions and coding standards.
- Portability
  - Runs on Linux within SGE; no kernel modifications required.

## 3.8 Supporting information
- Background research material on cluster computing, market-based models, cluster scheduling, and cluster management software.
- Data Flow Diagrams (DFDs) and Data Dictionary to explain and interpret functional flows.
- Legal and copyright 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.
- Packaging/export/security instructions: [N/A]
- The above items are provided as supporting information; unless explicitly stated elsewhere, they are not requirements.

# 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
- Assumes SGE modules (including process migration capabilities if any) interoperate with Libra’s scheduling policies.
- A basic module for job accounting and payment is available; detailed economic front-end (pricing) is deferred and does not affect scheduling logic assuming budget/cost inputs are provided.
- Users can reasonably estimate job execution times to enable accept/reject decisions.
- For testing, a simulation tool may be required; it may need to be developed if a suitable open-source tool is not available.
- Hardware for performance testing is limited (e.g., four Pentium-III workstations with 128 MB RAM); larger dedicated clusters would improve analysis.

## 5.2 Acronyms and abbreviations
- CPU: Central Processing Unit
- DFD: Data Flow Diagram
- FIFO: First-In, First-Out
- GPL: 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
