## 1.1 Purpose

This Software Requirements Specification defines the requirements and specifications for Libra, an economy-driven cluster scheduler. It describes the scheduler’s functional features, interface details, design constraints, and performance characteristics. The document is intended for users and owners of high-performance clusters, cluster management software stakeholders, job scheduler developers/administrators, and grid resource stakeholders.

## 1.2 Scope

This SRS defines Libra, an Economy-Driven Cluster Scheduler delivered as an add-on to the Sun Grid Engine (SGE) cluster management system for Linux-based clusters.

- Product(s) to be produced
  - Libra Scheduler: an economy-driven scheduling module integrated with SGE.
  - SGE interface extensions/CLI support to capture and use QoS parameters (deadline, budget, execution time) for job submission, monitoring, and control.
  - Basic job accounting capability to support scheduling policies and usage tracking.
  - Optional GUI may be added after core functionality.

- What the product(s) will do
  - Provide market-based, QoS-driven scheduling of batch jobs by allocating CPU time according to user utility (deadline and budget) rather than system-centric policies.
  - Accept or reject jobs based on feasibility of meeting user-specified constraints and suggest alternative cost/deadline when needed.
  - Compute proportional shares using a bid-based proportional resource-sharing model and enforce allocations via stride scheduling.
  - Determine execution hosts/queues, dispatch jobs, and dynamically adjust resource allocations; maintain and update cluster status.
  - Support sequential and embarrassingly parallel batch jobs on a homogeneous Linux cluster (leveraging PVM/MPI via SGE for parallel execution).

- Application, benefits, objectives, and goals
  - Application: high-performance cluster computing (e.g., scientific and engineering batch workloads) managed by SGE on homogeneous Linux clusters; primarily scheduling CPU time, with extensibility to other resources and heterogeneous clusters.
  - Objectives and goals:
    - Provide QoS-oriented computational economy and maximize user utility/satisfaction.
    - Meet user-imposed deadlines and budget constraints while optimizing resource utilization.
    - Enable dynamic reallocation so urgent, higher-priced jobs can complete on time under varying load.
    - Ensure scalability, configurability (policy pluggability), separability from the cluster manager, administrative security, and basic job accounting.
    - Maintain user privacy and control over job execution.
  - Benefits: user-centric scheduling, predictable completion relative to deadlines, and improved utilization aligned with user priorities.

- Scope boundaries and consistency
  - Operates as an add-on to SGE; no Linux kernel modifications are required.
  - Manages sequential and embarrassingly parallel batch jobs; does not enable user-to-user bargaining or grid-wide market interactions.
  - Open-source release under GPL.
  - Consistent with the broader system context described for SGE-managed Linux clusters and the stated objectives of providing QoS-based, economy-driven scheduling.

### 1.3.1 Product perspective

Libra is an add-on, economy-driven scheduler that operates as a sub-component of the Sun Grid Engine (SGE) cluster management system on a homogeneous Linux cluster. SGE receives user job submissions and delegates scheduling decisions to Libra. Libra returns accept/reject decisions and execution host/queue selections to SGE’s resource manager, which dispatches jobs. Once jobs are assigned to execution hosts, Libra enforces proportional resource allocations using stride scheduling. No Linux kernel modifications are required.

Major elements and interconnections:
- Users and administrators interact via the Linux command line and/or the SGE interface.
- SGE handles job submission, authentication, queuing, and dispatch; it invokes Libra for scheduling decisions.
- Libra evaluates job parameters (budget, deadline, execution time), computes priorities/tickets/strides, selects execution hosts/queues, and updates cluster status.
- Execution hosts run jobs on Linux; PVM/MPI libraries are used for embarrassingly parallel jobs.
- Cluster status (CPU load, node status, remaining time, available memory) is maintained via SGE’s information store.

#### System interfaces
- Interface: SGE → Libra
  - Functionality: Provide job initialization and cluster status required for scheduling.
  - Content:
    - Job details: job ID, type (sequential or embarrassingly parallel), standalone execution time, executable and input locations, system type, user budget, deadline.
    - Cluster information: CPU load, node status, remaining time of pending jobs, available memory, submission directions/criteria.
- Interface: Libra → SGE
  - Functionality: Return scheduling decisions and status updates.
  - Content:
    - Accept/Reject decision plus suggested deadline or cost (preconditioned acceptance).
    - Chosen execution host and queue for dispatch.
    - Scheduling information used at execution (tickets, stride, pass).
    - Cluster status updates to SGE’s central information store upon schedule/completion events.
- Interface: Libra ↔ Resource manager (within SGE)
  - Functionality: Dispatch timing and queue placement per Libra’s decisions.
  - Content: Dispatch triggers and queue placement for scheduled jobs.

#### User interfaces
- Access via Linux command prompt and/or SGE’s user interface.
- Cluster user capabilities:
  - 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 and usage history.
- Cluster administrator additional capabilities:
  - View status and load of all nodes and jobs.
  - Review cluster usage history.
  - Alter cost structure and scheduling policy.
  - Cancel, suspend, and resume any job.

#### Hardware interfaces
- Libra uses SGE’s hardware interfaces:
  - CPU usage monitoring and control.
  - Memory usage and swap file handling.
  - Network communication across cluster nodes.
- Target environment: homogeneous Linux cluster nodes.
- Configuration specifics (e.g., number of ports, instruction sets): [N/A]

#### Software interfaces
- Sun Grid Engine
  - Name: Sun Grid Engine; Mnemonic: SGE; Specification number: [N/A]; Version: 5.3; Source: Sun Microsystems (open-source).
  - Purpose: Cluster job queuing, submission, dispatch, and resource management; hosts Libra as a sub-component.
  - Interface: Job submission and status APIs, queue and dispatch controls; message content includes job details, cluster status, accept/reject decisions, host/queue selections. Reference to defining interface document: [N/A]
- Operating System
  - Name: Linux; Mnemonic: Linux; Specification number: [N/A]; Version: [N/A]; Source: Open-source.
  - Purpose: Execution platform for SGE/Libra and jobs; no kernel modifications required.
  - Interface: Standard OS services utilized via SGE; defining interface document: [N/A]
- Parallel libraries (for embarrassingly parallel jobs)
  - Name: Parallel Virtual Machine; Mnemonic: PVM; Specification number: [N/A]; Version: [N/A]; Source: University of Tennessee, Oak Ridge National Laboratory, Emory University.
  - Name: Message Passing Interface; Mnemonic: MPI; Specification number: [N/A]; Version: [N/A]; Source: University of Chicago and Mississippi State University.
  - Purpose: Enable execution of embarrassingly parallel jobs across nodes.
  - Interface: Library calls used by jobs; defining interface document: [N/A]

#### Communications interfaces
- Libra utilizes SGE’s communications architecture; no unique communications interfaces beyond SGE.
- Network protocols and transport specifics: [N/A]

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

#### Operations
- Modes of operation:
  - User-initiated operations: job submission, status queries, cancellations, and administrative adjustments (cost structure, scheduling policy).
  - Continuous unattended operations: scheduling loop (stride scheduling), dispatch timing, and execution on hosts while queues are non-empty.
- Interactive vs. unattended:
  - Interactive during submission, querying, and administrative commands.
  - Unattended during job scheduling/execution and cluster status updates.
- Data processing support:
  - Basic job accounting and usage history to aid scheduling.
- Backup and recovery:
  - On outage, recovery occurs with Linux reboot; cluster downtime less than five minutes.

#### Site adaptation requirements
- Site-specific configuration includes:
  - Cluster type and homogeneity assumptions; node and queue definitions.
  - Pricing/cost structure and submission criteria.
  - Scheduling policy selection and parameters (e.g., global stride constant).
  - Enablement and configuration for sequential vs. embarrassingly parallel job queues.
  - Administrative security settings and user authentication arrangements.

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

### 1.3.2 Product functions

The Libra Scheduler provides economy-driven, QoS-aware scheduling of batch jobs on a Linux cluster managed by Sun Grid Engine (SGE). Functions are organized below by core scheduling workflow, user-facing capabilities, administrator capabilities, and supporting services.

Core scheduling workflow
- Submit and validate job
  - Accept job submissions via SGE/command line with required parameters (executable and input locations, output destination, system type, max run time, job type: sequential or embarrassingly parallel, budget, deadline).
  - Verify user identity and whether the cluster is currently accepting submissions.
- Initialize job
  - Retrieve and parse submitted job details; register the job with scheduler state using SGE-assigned job ID.
- Admit (accept/reject) job
  - Evaluate feasibility against user QoS constraints (budget, deadline) and current cluster state (CPU load, node status, remaining time of pending jobs).
  - Return accept/reject decision; if needed, suggest alternative deadline or cost required for acceptance.
- Compute scheduling parameters
  - Allocate tickets based on budget/deadline relative to competing jobs.
  - Derive stride and pass to enforce proportional resource shares (stride scheduling).
- Select execution host and queue
  - Rank hosts by load to balance utilization.
  - Choose appropriate queue based on job type and constraints; consider available memory and pending workload.
- Dispatch job
  - Place accepted jobs into the selected host/queue at an appropriate time, considering pending deadlines and system load.
- Execute and time-slice
  - Run jobs using proportional stride scheduling: select job with minimum pass, allocate a quantum, advance its pass; break ties FIFO.
- Update cluster state
  - Reserve resources, update queue/node status after scheduling and upon job completion; propagate state to master host.

User-facing functions (cluster users)
- Submit jobs with budget and deadline constraints.
- Query current cost per unit time for new submissions.
- Monitor status and progress of submitted jobs.
- Cancel submitted jobs.
- View credit balance and personal usage history.

Administrator functions
- View status of all jobs and each cluster node, including load and usage patterns.
- Alter cost structure and scheduling policy (configurable, policy-pluggable operation).
- Cancel, suspend, and resume any job.
- Perform user-level actions (submit, monitor, query) as needed for administration.

Supporting services
- QoS and economy enforcement
  - Allocate CPU time according to user-centric priorities (budget, deadline) rather than submission order; support dynamic reallocation of resource shares.
- Job accounting (basic)
  - Maintain basic accounting to support scheduling policies and user billing/usage history.
- Security and access control
  - Authenticate users; protect job status privacy; restrict modification of scheduling criteria and allocations to administrators.
- Interfaces and operability
  - Integrate with SGE for job submission, dispatch, and resource control; support command-line interaction for users and administrators.
  - Execute sequential and embarrassingly parallel jobs; leverage PVM/MPI as required for the latter.

### 1.3.3 User characteristics

The product targets two user groups whose characteristics influence usability: cluster users (job submitters) and cluster administrators.

- Cluster users
  - Educational level: [N/A]
  - Experience/skills: Must know the nature of their jobs (execution time and resource needs) and be able to estimate execution times; understand and provide QoS parameters (deadline, budget); specify job type (sequential or embarrassingly parallel), executable/data locations, system type, and output locations; authenticate to the system.
  - Technical expertise: Able to use the Linux command line or the Sun Grid Engine (SGE) interface to submit, monitor, and manage jobs.
  - Disabilities/accessibility considerations: [N/A]

- Cluster administrators
  - Educational level: [N/A]
  - Experience/skills: Advanced cluster operators; fully qualified in using Linux, SGE, and the Libra Scheduler; capable of overseeing scheduling and cluster usage, altering cost structure and scheduling policy, and managing jobs and nodes.
  - Technical expertise: Expert-level proficiency with Linux and SGE; comfortable operating via command-line tools and SGE interfaces.
  - Disabilities/accessibility considerations: [N/A]

### 1.3.4 Limitations

- a) Regulatory requirements and policies
  - Must be open-source and released under the GNU General Public License (GPL); all documentation also in accordance with GPL.
  - Coding standards include adherence to the Hungarian Naming Convention.
  - Legal notices and trademarks for SGE, Libra, MPI, and PVM apply.

- b) Hardware limitations
  - Designed for a homogeneous Linux cluster; nodes are assumed to have uniform characteristics (e.g., same memory and disk) and run Linux.
  - No modifications to the Linux kernel are required or permitted.
  - Testing environment is constrained to a small cluster (four Pentium-III workstations with 128 MB RAM), which may limit performance validation.
  - Resource management in scope is CPU time; adaptation to other resources is outside the initial project scope.

- c) Interfaces to other applications
  - Operates as a sub-component/add-on to Sun Grid Engine (SGE) version 5.3; relies on SGE for job submission, dispatch, resource management, and communications.
  - For embarrassingly parallel jobs, depends on PVM and MPI libraries.
  - No unique communications interfaces beyond those provided by SGE.
  - The SGE user interface may require adaptation to accept additional QoS parameters (budget, deadline); alternatively, a command-line interface is used.

- d) Parallel operation
  - Supports only sequential and embarrassingly parallel jobs; does not support tightly coupled parallel jobs with interdependent threads.
  - Does not support job migration for reducing resource fragmentation.

- e) Audit functions
  - Provides at least a basic level of job accounting to aid scheduling; detailed payment/accounting is assumed but not the focus.
  - Users can check credit balance and usage history; administrators can review cluster usage patterns.

- f) Control functions
  - Administrators can alter cost structure, scheduling policy, and cancel/suspend/resume any job.
  - Users can cancel their own jobs; post-submission changes to critical QoS parameters (deadline, cost) are generally not permitted, except limited cases (e.g., output directory, delayed deadline).
  - Dynamic changes to resource limits, priorities, privileges, and execution order are within scheduler scope as permitted by SGE.

- g) Higher-order language requirements
  - Implementation is restricted to standard C.

- h) Signal handshake protocols
  - [N/A]

- i) Quality requirements (e.g., reliability)
  - Maximum bug rate of 1 bug/KLOC.
  - Maximum time to repair (system reboot) is less than five minutes.
  - Privacy of user job status and administrative control over job execution are required.
  - Performance constraints include maximum 1-minute response time for job submission, completion within a 10% deadline error (given accurate estimates), and charging not to exceed user-specified maximum cost.

- j) Criticality of the application
  - [N/A]

- k) Safety and security considerations
  - Administrative security is required; unauthorized alteration of scheduling criteria or resource allocation is not permitted.
  - Safety-specific requirements are not specified.

- l) Physical/mental considerations
  - [N/A]

- m) Limitations sourced from other systems (including real-time requirements through interfaces)
  - Operation depends on the workability and behavior of SGE modules (e.g., process migration) with Libra’s scheduling policies.
  - Relies on Linux OS and SGE for hardware and communications interfaces; no independent real-time signaling is defined by Libra.
  - Scheduling guarantees depend on users providing fair/accurate execution time estimates.
  - Availability of a simulation/testing tool is uncertain and may require a custom solution.

## 1.4 Definitions

- Cluster computing — Connecting multiple computers to act as an integrated resource with a single system image, transparently distributing job processing across nodes for high-performance applications.

- Quality of Service (QoS) — Meeting what users actually want, maximizing their utility (e.g., honoring deadlines and budgets over system-centric policies).

- Computational economy — A user-centric resource management approach where user-specified QoS parameters (such as deadline and budget) drive scheduling decisions over system-centric policies like FIFO.

- Grid computing — An infrastructure that couples diverse resources (computers, software, devices) across the Internet and presents them as a unified resource for executing jobs.

- Bid-based proportional resource-sharing model — An economic model that allocates resources in proportion to users’ bids (tokens/credits). In Libra, priorities (tickets) are derived from users’ deadlines and budgets considering system load, and resources are allocated proportionally.

- Stride scheduling — A deterministic scheduling algorithm that enforces proportional resource sharing using tickets; a job’s stride is inversely proportional to its tickets, so more tickets lead to more frequent scheduling and a larger resource share.

- Process migration — Moving a running job from one system to another without restarting it.

- Sequential job — A job that must run on a single node and cannot be split.

- Embarrassingly parallel job — A job composed of independent parts that can run on separate nodes with minimal inter-job communication.

- Job accounting — Quantifying the system resources consumed by a job.

- Sun Grid Engine (SGE) — The cluster management system that interfaces with users, delegates scheduling decisions to Libra, and dispatches jobs to execution hosts.

- Homogeneous cluster — A cluster whose nodes have uniform characteristics (e.g., memory, disk) and run the same operating system.

# 2 References

## 2.1 Compliance

- Title: GNU General Purpose License
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: [N/A]

- Title: Hungarian Naming Convention
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: [N/A]

## 2.2 Guidance

- Title: Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid
  - Report number: [N/A]
  - Date: 2000
  - Publishing organization: IEEE CS Press, USA
  - Source: [N/A]

- Title: An Economy Driven Resource Management Architecture for Global Computational Power Grids
  - Report number: [N/A]
  - Date: June 26–29, 2000
  - Publishing organization: [N/A]
  - Source: [N/A]

- Title: An Economy Grid Architecture for Service-Oriented Grid Computing
  - Report number: [N/A]
  - Date: April 2001
  - Publishing organization: [N/A]
  - Source: [N/A]

- Title: Economic Models for Management of Resources in Peer-to-Peer and Grid Computing
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: Monash University
  - Source: [N/A]

- Title: Market-based proportional resource sharing for clusters
  - Report number: [N/A]
  - Date: September 1999
  - Publishing organization: [N/A]
  - Source: [N/A]

- Title: Appendix A – Background Research
  - Report number: [N/A]
  - Date: 10th Nov, 2001
  - Publishing organization: [N/A]
  - Source: This SRS, Section 5 Appendices

- Title: Appendix B – Data Flow Diagrams
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: This SRS, Section 5 Appendices

- Title: Appendix C – Data Dictionary
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: This SRS, Section 5 Appendices

## 3.1 Functions

This section defines the fundamental actions of the Libra Scheduler (operating as an add-on to Sun Grid Engine, SGE) for accepting and processing inputs and generating outputs. Functions are partitioned into sub-functions that collectively realize the scheduling workflow.

Overview workflow (input/output sequence):
- Submit Job → Initialize Job → Accept/Reject Job → Calculate Scheduling Information → Determine Execution Host → Dispatch Job → Update Cluster Status → Execute Job → Update Cluster Status
- At any time: View Job Status; Delete/Change Job (may trigger rescheduling and status updates)

### 3.1.1 Submit Job
- Inputs:
  - User information (name, authentication id)
  - Job information: executable/data locations; system type; maximum run time; job type (sequential or embarrassingly parallel); budget; deadline
  - Cluster information: current load status; submission directions/criteria
- Validity checks:
  - Verify whether the cluster is open for job submissions
  - Verify that the submitting user is valid
- Sequence of operations:
  - Check cluster submission state
  - Authenticate/verify user
  - Provide result to caller (distinct from Accept/Reject Job decision)
- Outputs:
  - Boolean: cluster accepting submissions
  - Boolean: user verified
- Effect of parameters:
  - None at this step beyond gating access; detailed effects occur later

### 3.1.2 Initialize Job
- Inputs:
  - User-submitted job details; SGE-assigned Job Id
- Validity checks:
  - [N/A]
- Sequence of operations:
  - Retrieve job details from submission
  - Parse and set scheduler state variables representing job information
  - Forward parsed parameters to the scheduling module
- Outputs:
  - Job details set in internal state: Job Id, Job type, Standalone execution time, Executable/data locations, System type, Budget, Deadline
- Effect of parameters:
  - Establishes the canonical job attributes used by all downstream functions

### 3.1.3 Accept/Reject Job
- Inputs:
  - Job details (as initialized)
  - Cluster information: CPU load, node status, remaining time of pending jobs
- Validity checks:
  - [N/A]
- Sequence of operations:
  - Compute a priority/share for the job based on budget and deadline relative to other jobs
  - Determine feasibility to meet the deadline given execution time and current/pending workload
- Outputs:
  - Boolean: job accepted or rejected
  - Suggested deadline or cost (precondition for acceptance)
- Effect of parameters:
  - Budget and deadline dominate acceptance and priority/share determination
  - Execution time and current system load govern feasibility

### 3.1.4 Calculate Scheduling Information
- Inputs:
  - Job details (as initialized)
- Validity checks:
  - [N/A]
- Sequence of operations:
  - Allocate tickets to the job based on its budget and deadline, and those of competing jobs
  - Compute stride and initial pass:
    - stride = global_stride_constant / tickets
    - pass_initial = stride
- Outputs:
  - Scheduling information: tickets, stride, pass
- Effect of parameters:
  - Higher budget or tighter deadline increase tickets, reducing stride and increasing scheduling frequency
  - Exact ticket allocation function: [N/A]

### 3.1.5 Determine Execution Host
- Inputs:
  - Job details (as initialized)
  - Cluster information: CPU load, node status, remaining time of pending jobs, available memory
- Validity checks:
  - [N/A]
- Sequence of operations:
  - Sort hosts by load (ascending)
  - Select least loaded host
  - Select appropriate queue based on job type (sequential or embarrassingly parallel), budget, etc.
- Outputs:
  - Chosen execution host and queue
- Effect of parameters:
  - Job type dictates queue class; load and remaining times drive host choice; budget/deadline influence queue selection where applicable

### 3.1.6 Dispatch Job
- Inputs:
  - Chosen execution host and queue
- Validity checks:
  - [N/A]
- Sequence of operations:
  - Insert job into the target queue on the selected host
  - Allow queuing delay to accommodate earlier execution for more urgent jobs
- Outputs:
  - Scheduled job placed on host/queue
- Effect of parameters:
  - Budget/deadline (via tickets/stride) influence when the dispatcher allows the job to join active competition for CPU time

### 3.1.7 Update Cluster Status
- Inputs:
  - Job details; chosen execution host and queue
- Validity checks:
  - [N/A]
- Sequence of operations:
  - Reserve required resources on the node
  - Update execution host queue status
  - Send updated load/queue information to the master host’s central information store
- Outputs:
  - None (state update side effects only)
- Effect of parameters:
  - Job resource requirements and scheduling state determine the magnitude and content of updates

### 3.1.8 Execute Job
- Inputs:
  - Scheduled jobs (with node/queue assignments)
  - Scheduling information: tickets, stride, pass
- Validity checks:
  - [N/A]
- Sequence of operations (stride scheduling):
  - Repeatedly select the job with minimum pass
  - Allocate a CPU quantum to the selected job
  - Advance the job’s pass by its stride
  - Break ties using FIFO order
  - Continue until no jobs remain in the queue
- Outputs:
  - Updated cluster information: CPU load, node status, remaining time of pending jobs, available memory
- Effect of parameters:
  - Tickets/stride from budget/deadline govern CPU share; tie-breaking uses FIFO when passes are equal
- Notes:
  - No job migration is supported for decreasing resource fragmentation

### 3.1.9 View Job Status
- Inputs:
  - User Id and password
- Validity checks:
  - Authenticate the requesting user
- Sequence of operations:
  - Present available options and status views for the user’s jobs
  - Process the selected viewing options
- Outputs:
  - User-facing view of job options and execution progress
- Effect of parameters:
  - [N/A]

### 3.1.10 Delete/Change Job
- Inputs:
  - User Id and password
- Validity checks:
  - Authenticate the requesting user (and enforce privileges)
- Sequence of operations:
  - Remove the job from the queue (cancel), or apply permitted changes (e.g., output directory or a delayed deadline when allowed)
  - Update cluster status
  - Revise scheduling decisions and resource allocations for pending jobs and forthcoming submissions
- Outputs:
  - Updated cluster information and scheduling decisions: CPU load; node status; queue length; quanta allocated to pending jobs; revised expected finishing deadlines of pending jobs
- Effect of parameters:
  - Core scheduling parameters (deadline, budget) would not normally be changeable; permitted changes may alter future scheduling and status updates

### 3.1.11 Abnormal situations and recovery
- Overflow:
  - [N/A]
- Communication facilities (failures/abnormalities):
  - [N/A]
- Hardware faults and failures:
  - In case of system outage, the cluster will be down while the Linux operating system boots up; expected time to repair is less than five minutes
- Error handling and recovery:
  - [N/A]

### 3.1.12 Relationship of outputs to inputs and formulas
- Input/output sequences:
  - Submission/authentication outcomes gate initialization
  - Acceptance decision gates calculation of tickets/stride/pass
  - Host/queue selection follows from job parameters and cluster load
  - Dispatch transitions a job from pending to runnable
  - Execution updates cluster status based on CPU allocation determined by stride scheduling
- Formulas:
  - stride = global_stride_constant / tickets
  - pass_initial = stride; pass_next = pass_current + stride after each quantum
  - Ticket allocation function (from budget, deadline, and competing jobs): [N/A]
- Output dependencies:
  - Accept/Reject output depends on budget, deadline, execution time, and current/pending workload
  - Scheduling information depends on allocated tickets
  - Host/queue selection depends on current load, remaining times, available memory, and job type
  - Cluster status updates depend on job scheduling and execution events

## 3.2 Performance requirements

Static numerical requirements:
- Number of terminals supported: [N/A]
- Number of simultaneous users supported: [N/A]
- Amount and type of information handled (quantitative limits): [N/A]
- Capacity: The scheduler shall impose no inherent upper bound on the number of jobs; the effective maximum is limited only by the capacity of the cluster nodes to meet job deadlines.

Dynamic numerical requirements:
- Job submission response time: For each submission request, the system shall return an acceptance or rejection decision within 60 seconds.
- Deadline adherence: Assuming submitted job statistics (e.g., execution-time estimates) are accurate, 100% of accepted jobs shall complete within ±10% of the user-specified deadline.
- Cost adherence: For every job, the total cost charged shall not exceed the user-specified maximum budget.
- Transaction/task throughput under normal and peak load: [N/A]
- Data processing volume within specified time periods (normal and peak): [N/A]

## 3.3 Usability requirements

- Contexts of use
  - Two user types, each with its own interface: cluster user and cluster administrator.
  - Interaction via Linux command line and/or the Sun Grid Engine (SGE) interface; no GUI is required in the initial release. A GUI might be added after basic functionality is implemented.
  - User skills: users must know job characteristics and how to use the submission interface; administrators must be advanced operators proficient with Linux, SGE, and Libra.

- Effectiveness
  - Task coverage for cluster users (commands shall exist to):
    - submit jobs with associated deadline, cost, and execution time,
    - query current cost per unit time for submitting new jobs,
    - monitor status of submitted jobs,
    - cancel jobs submitted by the user,
    - check user credit balance,
    - check user usage history.
  - Task coverage for administrators (in addition to user commands, commands shall exist to):
    - check status of each node and the load on each node,
    - check status of all submitted jobs,
    - check cluster usage pattern/history,
    - alter the cost structure,
    - alter the scheduling policy,
    - cancel, suspend, and resume any job.
  - Measurable task success targets: [N/A]

- Efficiency
  - Job submission response time shall be less than or equal to 1 minute.
  - Other measurable efficiency targets (e.g., time/steps to complete common tasks): [N/A]

- Satisfaction
  - User satisfaction criteria or targets (e.g., ratings, surveys, complaints thresholds): [N/A]
  - Interface modality expectations: command-line and SGE interfaces are acceptable; GUI is optional and not required for baseline usability.

- Avoidance of harm in use
  - Privacy and control: the system shall ensure privacy of user job status and prevent alteration of scheduling criteria or resource allocation without administrator authority.
  - Financial protection: under all circumstances, the maximum cost charged shall not exceed the user-submitted maximum cost.
  - Additional harm-avoidance criteria (e.g., prevention of irreversible user actions without confirmation beyond job cancel/resume): [N/A]

- Help and documentation
  - On-line user documentation shall be provided as Linux man pages.
  - Additional usability aids (tutorials, contextual help, examples): [N/A]

- Accessibility and internationalization
  - Accessibility requirements (e.g., keyboard-only use, screen reader compatibility) and language support: [N/A]

## 3.5 Logical database requirements

This system uses a centralized information store on the master host (as part of/alongside SGE) to persist job, cluster status, scheduling, and basic accounting data needed by Libra’s functions.

- Types of information used by functions
  - Submit Job: User credentials/identity; job specifications (job id, job type, standalone execution time, executable and input locations, system type, budget, deadline); cluster submission policy/open-for-submission flag.
  - Initialize Job: Parsed job specifications; SGE-assigned job id; linkage to user.
  - Accept/Reject Job: Job parameters (budget, deadline, execution time); current cluster information (CPU load, node status, remaining time of pending jobs); suggested alternative deadline/cost if applicable.
  - Calculate Scheduling Information: Scheduling allocations (tickets, stride, pass) per job and per execution host/queue; global stride constant.
  - Determine Execution Host: Host/node status, available memory, CPU load, queue descriptors; job parameters (type, budget, deadline, execution time).
  - Dispatch Job: Target execution host and queue; job state transition to scheduled/running.
  - Update Cluster Status: Per-node load, queue lengths, remaining time of pending jobs; job state (submitted, accepted, scheduled, running, completed, canceled).
  - Execute Job: Scheduling information (tickets, stride, pass); per-quantum updates to remaining time and pass values.
  - User/Admin Interfaces: User credit balance; usage history/accounting records; cluster-wide status views; cost structure; scheduling policy metadata.

- Frequency of use
  - Job and Job Parameters: High read/write at submission and state changes; frequent reads for status queries.
  - Cluster/Node/Queue Status: Very high write frequency on each scheduling/dispatch/completion event; high read frequency for placement and status views.
  - Scheduling Information (tickets/stride/pass): Very high read/write in the scheduling loop; updated each quantum for running jobs.
  - Accounting/Usage Records: Write on job completion and at significant state changes; read for usage history and admin reporting.
  - Cost Structure and Scheduling Policy: Low write (administrative changes), moderate read during admission control and scheduling.
  - User Credentials/Identity/Credit Balance: Low write, moderate read (authentication, balance checks).

- Accessing capabilities
  - Query by job id, user id, job state, deadline window, and submission time.
  - Query by node/queue to obtain current load, available memory, and queue length.
  - Retrieve and update scheduling allocations per job efficiently during the scheduling loop.
  - Aggregate queries for administrator dashboards (usage patterns, node load, all submitted jobs).
  - Concurrency control to support frequent scheduler updates with consistent, read-mostly user/admin queries.
  - Atomic state transitions for jobs (e.g., accepted → scheduled → running → completed/canceled).

- Data entities and relationships
  - User: uniquely identified user with authentication and accounting profile; has many Jobs; has many AccountingRecords.
  - Job: belongs to a User; has one JobParameters; has many SchedulingAllocations (over time); is dispatched to one Queue on one HostNode at a time; has many AccountingRecords.
  - JobParameters: execution time (standalone), executable/input locations, system type, budget, deadline, job type (sequential or embarrassingly parallel).
  - HostNode: part of the Cluster; has many Queues; has associated NodeStatus snapshots/metrics.
  - Queue: belongs to a HostNode; contains many Jobs (by state); has QueueStatus.
  - ClusterStatus/NodeStatus/QueueStatus: time-stamped metrics (CPU load, remaining time of pending jobs, available memory, queue length).
  - SchedulingAllocation: per-job fields (tickets, stride, pass), optionally versioned over time; references Job and HostNode/Queue.
  - AccountingRecord: per-job usage and charge entries (start/end times, CPU time consumed, cost computed); references Job and User.
  - CostStructure: current pricing parameters used for admission control and charging.
  - SchedulingPolicy: configurable policy metadata used by the scheduler.
  - AuthenticationCredential: tied to User; used to verify access.

- Integrity constraints
  - User.username is unique; Users must be authenticated to view their own job status.
  - Job must reference a valid User and have a unique job id (consistent with SGE).
  - JobParameters.budget ≥ 0; JobParameters.execution_time > 0; JobParameters.deadline ≥ Job.submission_time.
  - For accepted jobs, exactly one active SchedulingAllocation per execution context; SchedulingAllocation.tickets > 0; stride > 0; pass ≥ 0.
  - Job.type determines valid queue selection (sequential vs. embarrassingly parallel).
  - Dispatch requires a valid HostNode and Queue that are in service.
  - Completion requires end_time ≥ start_time.
  - Charged cost for a job must be ≤ user-submitted maximum budget.
  - Cluster/Node/Queue status records must reference existing nodes/queues and have monotonically increasing timestamps.

- Security
  - Role-based access control: users can access only their own jobs, balances, and usage history; administrators can access all cluster, policy, and job data and perform changes.
  - Administrative actions (alter cost structure, scheduling policy; cancel/suspend/resume any job) require administrator role.
  - Protect integrity of scheduling data (tickets/stride/pass) from non-administrative modification.
  - Authentication required for all user and administrator queries/commands.
  - Audit trail via AccountingRecords and admin action logs for accountability.

- Data retention requirements
  - Job records and statuses: [N/A]
  - Scheduling allocations history (for audit/debug): [N/A]
  - Cluster/node/queue status snapshots: [N/A]
  - Accounting/usage records and user credit history: [N/A]
  - Administrative policy and cost structure change history: [N/A]

## 3.6 Design constraints

- Licensing and openness
  - Must be released under the GNU General Public License (GPL); source code and documentation must comply with GPL requirements.
  - Only open-source components are permitted; no purchased/proprietary components.
  - Documentation must be provided as Linux man pages and comply with GPL-related documentation practices.
  - Must respect third-party copyrights/trademarks (Sun Grid Engine, MPI, PVM).

- Parent system and interfaces
  - Libra is a sub-component of Sun Grid Engine (SGE) and must remain compatible with SGE version 5.3.
  - Must use SGE’s hardware and communications interfaces (CPU/memory usage, swap, network) and SGE’s communications architecture; no unique communications stack beyond SGE.
  - For embarrassingly parallel jobs, must use PVM and MPI libraries provided by the cluster environment.

- Platform and OS
  - Runs on a Linux-based cluster; no modifications to the Linux kernel are allowed.
  - Target deployment is a homogeneous cluster environment.

- Implementation standards
  - All coding must be done in standard C.
  - Code must follow the Hungarian Naming Convention.

- Algorithmic/model constraints
  - Scheduling must implement a market-based, bid-based proportional resource-sharing model.
  - Resource allocation enforcement must use the stride-scheduling algorithm.
  - Scheduling must rely on heuristics; exhaustive search over all job combinations is disallowed.

- Functional scope limitations
  - Supports only sequential and embarrassingly parallel batch jobs.
  - No job/process migration will be used for reducing resource fragmentation.
  - Users do not interact/bargain with each other (no peer negotiation mechanisms).

- Project/environment limitations
  - Current test environment is a small, homogeneous Linux cluster (four Pentium-III nodes with 128 MB RAM); extensive scalability testing may require a simulator or additional freely available tools.

## 3.7 Software system attributes

### Reliability
- Maximum defect density at delivery: not more than 1 bug/KLOC.
- Job migration for the purpose of decreasing resource fragmentation is not supported.

### Availability
- Maximum time to repair after a system outage (Linux reboot): less than five minutes.

### Security
- Ensure privacy of user job status.
- Only administrators can alter scheduling criteria or actual resource allocation.
- Authentication (user ID and password) is required to view job status and to delete/change jobs.
- Provide administrative security.
- Provide at least a basic level of job accounting and usage history to support auditing and charging.

### Maintainability
- Implementation language: standard C.
- Naming convention: Hungarian Naming Convention.
- Coding standards/licensing: code will be written as required by the GNU General Purpose License.
- Configurable scheduling: allow various scheduling policies to be modified to incorporate QoS parameters; administrators can alter cost structure and scheduling policy via the interface.
- Separation: the scheduler shall be separable from the cluster management system.
- No modifications to the Linux kernel are required.

### Portability
- Use of a proven portable language: standard C.
- Operating system: Linux-based cluster.
- Parent component/environment: runs as a sub-component of Sun Grid Engine (version 5.3).
- External libraries: PVM and MPI are used for embarrassingly parallel jobs.
- Kernel changes: none required.

### Scalability
- The scheduler should be scalable; performance should not degrade with the addition of nodes and jobs to the cluster.

## 3.8 Supporting information

- Sample input/output formats, cost analysis studies, user surveys
  - Sample input/output formats: [N/A]
  - Descriptions of cost analysis studies: [N/A]
  - Results of user surveys: [N/A]
  - Note: Textual descriptions of inputs and outputs for each function are provided in Section 3.1 (e.g., Submit Job, Accept/Reject Job, Execute Job).

- Supporting/background information for readers
  - Background research topics are identified in Appendix A (Cluster Computing; Market-based Economic Models; Cluster Scheduling; Cluster Management Software).
  - Data Flow Diagrams are referenced in Appendix B and the associated Data Dictionary in Appendix C to aid interpretation of functional flows described in Section 3.1.
  - Definitions, acronyms, and abbreviations are provided in Section 1.3 (e.g., QoS, Computational Economy, Bid-based Proportional Resource-Sharing Model, Stride Scheduling, Embarrassingly Parallel Jobs).
  - References are listed in Section 1.4.

- Description of the problems to be solved by the software
  - Provide QoS-oriented, economy-driven scheduling for cluster batch jobs by honoring user-specified budget and deadline, shifting from system-centric to user-centric resource allocation (Sections 1.2, 1.3.3, 2.2).
  - Allocate CPU time proportionally to user priority derived from budget/deadline using a bid-based proportional resource-sharing model enforced via stride scheduling (Sections 1.3.6, 1.3.7, 2.2, 3.1.6, 3.1.10).
  - Operate as an add-on to Sun Grid Engine (SGE) on a homogeneous Linux cluster without kernel modifications; manage sequential and embarrassingly parallel jobs; support dynamic reallocation, scalability, configurability, and administrative security (Sections 1.2, 2.1, 2.2, 3.8).
  - Avoid exhaustive combinatorial searches; employ heuristics; do not support process migration for fragmentation reduction (Sections 3.5.3, 3.2.1).

- Special packaging instructions (security, export, initial loading, media)
  - [N/A]

- Normative status of this information
  - Unless explicitly stated elsewhere as a “requirement” within Section 3, the items in this Supporting information subsection (including appendices and background materials) are informative only and are not to be considered part of the binding requirements.

## 4.1 Functions

This section defines how each functional requirement in 3.1 will be verified. For each sub-function, verification covers: a) input validity checks; b) sequence of operations; c) responses to abnormal situations; d) effects of parameters; and e) relationships of outputs to inputs. Where the SRS does not specify behavior, [N/A] is stated.

Submit Job
- Validity checks on inputs: Unit/integration tests through SGE submission to verify presence and type/format of User Information, Job Information (including executable/data paths, system type, execution time, job type), and Cluster Information; verify rejection when cluster is closed for submissions and for invalid users.
- Sequence of operations: Integration tests with SGE to assert that submission goes through SGE, Libra is consulted, and booleans “accepting submissions” and “user verified” are returned; verify via instrumented logs.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Test that submission is only allowed when cluster-open flag is true and user authentication succeeds.
- Relationship of outputs to inputs:
  - Input/output sequences: Submit → SGE validates → Libra consulted → booleans returned (accepting, verified).
  - Formulas: [N/A]

View Job Status
- Validity checks on inputs: Authentication tests ensure only the job owner or admin views status.
- Sequence of operations: UI/API tests confirm options are listed and selected views return job progress; verify correct state retrieval from SGE.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify user identity affects visibility (owner vs admin).
- Relationship of outputs to inputs:
  - Input/output sequences: Auth → list options → retrieve status per selection.
  - Formulas: [N/A]

Delete/Change Job
- Validity checks on inputs: Authorization tests for delete/change scoped to owner/admin; verify only permitted parameters are changeable (e.g., output directory, delayed deadline as allowed by SRS).
- Sequence of operations: Integration tests confirm: remove job → update cluster status → reschedule pending jobs.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify that changing critical parameters (deadline, cost) is blocked unless permitted as specified.
- Relationship of outputs to inputs:
  - Input/output sequences: Auth → delete/change → state updated → revised scheduling.
  - Formulas: [N/A]

Initialize Job
- Validity checks on inputs: Unit tests ensure all required job fields (Job Id, type, execution time, paths, system type, budget, deadline) are present and parsable.
- Sequence of operations: Integration tests verify retrieval of job details → state variables set → parameters passed to scheduling module.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify that parsed values populate the scheduler state accurately.
- Relationship of outputs to inputs:
  - Input/output sequences: Accept by SGE → Libra initializes → state populated.
  - Formulas: [N/A]

Accept/Reject Job
- Validity checks on inputs: Tests with combinations of budget, deadline, and execution time (accurate estimates as assumed) to ensure evaluator receives valid ranges and units.
- Sequence of operations: Property-based tests check that priority/share is computed then feasibility-by-deadline evaluated, producing accept/reject and optional suggested adjustments.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify that tighter deadlines or lower budgets influence rejection likelihood and suggested alternatives, consistent with QoS goals.
- Relationship of outputs to inputs:
  - Input/output sequences: Job details → priority/share computed → feasibility check → boolean + suggestion.
  - Formulas: [N/A] (no explicit acceptance formula specified)

Calculate Scheduling Information
- Validity checks on inputs: Ensure job has valid budget, deadline, and execution time before ticket allocation.
- Sequence of operations: Unit tests validate order: allocate tickets → compute stride = global_stride / tickets → set initial pass = stride.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify that higher priority (from budget/deadline) yields more tickets and thus shorter stride.
- Relationship of outputs to inputs:
  - Input/output sequences: Details → tickets/stride/pass.
  - Formulas for input to output conversion: Verify stride = global_stride / tickets and initial pass = stride.

Determine Execution Host
- Validity checks on inputs: Verify presence and freshness of Cluster Information (CPU load, node status, remaining times, memory).
- Sequence of operations: Integration tests confirm hosts sorted by ascending load → least-loaded chosen → queue selected based on job type and QoS parameters.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify job type (sequential vs embarrassingly parallel) and QoS parameters alter queue choice; load affects host choice.
- Relationship of outputs to inputs:
  - Input/output sequences: Cluster snapshot + job details → host/queue decision.
  - Formulas: [N/A]

Dispatch Job
- Validity checks on inputs: Ensure a valid target host/queue exists and job remains accepted.
- Sequence of operations: Tests confirm deferral is allowed; when dispatched, job joins competition for resources on selected queue.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify dispatch timing can be influenced by urgency (deadline) relative to others if applicable.
- Relationship of outputs to inputs:
  - Input/output sequences: Host/queue → enqueue → ready-to-run state.
  - Formulas: [N/A]

Update Cluster Status
- Validity checks on inputs: Confirm job identity and selected host/queue are valid before update.
- Sequence of operations: Tests verify resource reservation → queue status updated → master host’s central store updated.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify larger resource needs cause larger reservations and impact load metrics accordingly.
- Relationship of outputs to inputs:
  - Input/output sequences: Schedule/finish event → reservation/release → global state update.
  - Formulas: [N/A]

Execute Job
- Validity checks on inputs: Ensure every running job has valid tickets, stride, and pass values before selection.
- Sequence of operations: Deterministic scheduler tests verify: select job with minimum pass → allocate a quantum → advance its pass by its stride → FIFO tie-breaker; repeat until queue empty.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: [N/A]
- Effect of parameters: Verify that more tickets (from budget/deadline priority) result in more frequent scheduling (shorter stride).
- Relationship of outputs to inputs:
  - Input/output sequences: Scheduling info + queued jobs → time-sliced execution → updated cluster info.
  - Formulas for input to output conversion: Verify proportionality of CPU share to tickets over time as implied by stride scheduling.

End-to-end verification
- Validity checks on inputs: Scenario tests submit jobs with complete/invalid parameter sets to confirm acceptance gating at submission and initialization.
- Sequence of operations: Trace-based tests confirm the pipeline order for accepted jobs: Submit → Initialize → Accept/Reject → Calculate Scheduling → Determine Host → Dispatch → Update Status → Execute → Update Status on completion.
- Responses to abnormal situations: [N/A]
- Effect of parameters: Workload tests verify QoS behavior: deadlines and budgets influence acceptance, ticket allocation, host/queue selection, and execution frequency.
- Relationship of outputs to inputs: Long-run measurements validate that scheduling outcomes (completion by deadlines within stated error allowance and proportional CPU shares) reflect the specified inputs and computed scheduling information.

## 4.2 Performance requirements

This section defines the verification approaches and methods to qualify compliance with the performance requirements. The items are organized in parallel with the Performance requirements (Requirements 3.2).

Verification of static numerical requirements
- Number of terminals to be supported: [N/A]
- Number of simultaneous users to be supported: [N/A]
- Amount and type of information to be handled: [N/A]

Verification of dynamic numerical requirements
- Response time (Requirement: maximum response time for the submission of a job is 1 minute)
  - Method: Measure the elapsed time from the user invoking the submission command (via Linux command line or SGE interface) to receipt of the submission acknowledgment (accept/reject) returned by SGE/Libra.
  - Conditions: Execute under normal load and peak load (queues heavily populated with pending jobs). Include sequential and embarrassingly parallel jobs.
  - Instrumentation: Timestamped SGE and Libra logs; client-side timestamp at command invocation and acknowledgment receipt.
  - Pass/fail criteria: For every submission measured, acknowledgment is returned within 60 seconds.

- Capacity (Requirement: no upper limit inherent in Libra; the maximum number of jobs schedulable is limited only by node capacity to meet deadlines)
  - Method: Incrementally increase the number of submitted jobs beyond the point where cluster nodes can meet deadlines, while observing Libra’s behavior.
  - Conditions: Vary job mixes (sequential and embarrassingly parallel) and ranges of budgets and deadlines; conduct tests on the available Linux cluster and, where needed, with a simulation tool as noted in project constraints.
  - Evidence to collect: Presence/absence of any Libra-imposed hard cap on queued or schedulable jobs; reasons for accept/reject decisions; stability of queue handling through SGE; absence of Libra-specific failures attributable to queue length.
  - Pass/fail criteria: No Libra-specific fixed upper limit is encountered; job acceptance/rejection is driven by QoS constraints (e.g., deadlines/budgets, node capacity) rather than an internal Libra cap.

- Deadline sensitivity (Requirement: assuming submitted job statistics are accurate, all jobs are completed with a 10% error allowance)
  - Method: Submit workloads where the execution time estimates are accurate, record each accepted job’s declared deadline and its completion time as reported by SGE/Libra.
  - Conditions: Normal and peak load; include both sequential and embarrassingly parallel jobs; vary budgets and deadlines.
  - Metric: For each accepted job, compute whether completion occurs within the allowed 10% error tolerance relative to the declared deadline.
  - Pass/fail criteria: 100% of accepted jobs complete within the 10% error allowance under the assumption of accurate submitted statistics.

- Cost sensitivity (Requirement: under all circumstances, the maximum cost payable submitted by the user is the maximum charged)
  - Method: For each executed job, compare the user-submitted maximum cost/budget with the cost recorded by the job accounting module.
  - Conditions: Include a range of budgets and deadlines; normal and peak load conditions.
  - Evidence to collect: Job submission parameters (budget), job accounting records, and any pricing outcomes.
  - Pass/fail criteria: For every job, charged cost is less than or equal to the user-submitted maximum cost.

Test environment and tools
- Environment: Linux-based cluster running Sun Grid Engine (version referenced in Interfaces) with Libra integrated; execution includes PVM/MPI where applicable for embarrassingly parallel jobs.
- Tools and data sources: SGE command-line interface or SGE UI, Libra and SGE logs, and the basic job accounting module. A simulation tool may be used for load generation if a generic free tool is not available (per project constraints).

Reporting
- For each test, provide a summary of procedures, raw measurements, and a pass/fail determination mapped to the corresponding performance requirement.

## 4.3 Usability requirements

This section describes the verification approaches and methods to qualify usability. Where explicit usability objectives are not defined in Requirements, applicable items are marked [N/A]. Verification is aligned with relevant requirements for user interfaces (3.8.1), online documentation (3.6), user characteristics (2.3), security/privacy (3.2.4), and performance (3.3.1).

- Scope and context
  - Interfaces under test: Linux command-line and Sun Grid Engine (SGE) interfaces available to cluster users and administrators (3.8.1).
  - Participants: representative cluster users and administrators as characterized in 2.3 (users with sufficient technical know-how; administrators as advanced cluster operators).

- Effectiveness ([N/A] measurable targets)
  - Method: task-based usability testing on a Linux cluster running SGE (version per 3.8.3), using realistic workloads.
  - User tasks (3.8.1.1):
    - Submit jobs with deadline, cost, and execution time.
    - Query current cost per unit time for new jobs.
    - Monitor status of submitted jobs.
    - Cancel own jobs.
    - Check credit balance.
    - Check usage history.
  - Administrator tasks (3.8.1.2):
    - Check status of each node and per-node load.
    - Check cluster usage history and status of all jobs.
    - Alter cost structure.
    - Alter scheduling policy.
    - Cancel, suspend, and resume any job.
  - Evidence: test scripts, execution logs, and pass/fail per task against expected outcomes.
  - Acceptance criteria: [N/A].

- Efficiency
  - Method: measure task completion times and interaction steps for the tasks above.
  - Conformance check: verify job submission response time ≤ 1 minute (3.3.1 Response time).
  - Additional timing/step-count thresholds: [N/A].

- Satisfaction ([N/A] objectives)
  - Method: post-task qualitative feedback (e.g., debrief interviews) focused on clarity of commands and options within CLI/SGE context.
  - Quantitative satisfaction targets: [N/A].

- Avoidance of harm in use
  - Method: role/authorization usability checks aligned with security and privacy (3.2.4) and functional access controls (3.1.2, 3.1.3, 3.8.1):
    - Verify users cannot view or change other users’ job status.
    - Verify only administrators can alter cost structure or scheduling policy, and can cancel/suspend/resume any job.
    - Verify cancellation of a job by a user affects only that user’s jobs.
  - Evidence: attempted unauthorized actions result in denial with appropriate system response; audit/log entries where available.
  - Quantitative harm-avoidance targets: [N/A].

- Documentation and help (3.6)
  - Method: documentation audit of man pages for all user and administrator commands listed in 3.8.1.
    - Verify existence and accessibility via standard man interfaces.
    - Verify coverage of required parameters (deadline, cost, execution time) and expected outputs; include usage examples where provided.
  - Evidence: checklist of commands with documentation presence and content verification results.
  - Readability/coverage metrics: [N/A].

- Learnability, memorability, accessibility
  - Verification objectives and measures: [N/A].

## 4.5 Logical database requirements

This section defines the verification approaches for the logical database requirements (parallel to 3.5 a–g), using only the information stated or implied in the original SRS.

- a) Types of information used by various functions
  - Information types drawn from the SRS:
    - Job details: job ID (from SGE), job type (sequential or embarrassingly parallel), standalone execution time, executable and input locations, system type, budget, deadline.
    - Scheduling information: tickets, stride, pass.
    - Cluster information: CPU load, node status, remaining time of pending jobs, available memory; chosen execution host and queue.
    - User information: user identity and authentication data.
    - Accounting and usage: credit balance, usage history; basic job accounting/payment data.
  - Verification approaches:
    - Submit and initialize a job; verify persistence and retrievability of all required job detail fields keyed by the SGE job ID.
    - After Calculate Scheduling Information, verify scheduling records (tickets, stride, pass) are stored and associated with the job.
    - On Update Cluster Status and Dispatch Job, verify the central information store on the master host reflects updated node/queue state and the job’s assigned execution host and queue.
    - Via user/admin interfaces, verify retrieval of job status, credit balance, and usage history returns consistent data.

- b) Frequency of use
  - Specified in SRS:
    - Update Cluster Status is triggered every time a job is scheduled on a host and when a job ends and is removed.
  - Verification approaches:
    - Event-driven tests: submit, dispatch, complete, and delete jobs; verify that each event produces a corresponding and timely update in the cluster information store.
    - [N/A] for any other specified operation frequencies or throughput rates.

- c) Accessing capabilities
  - Specified capabilities:
    - Users: submit jobs (with deadline, cost, execution time), monitor status of submitted jobs, cancel own jobs, check credit balance, check usage history.
    - Administrators: view status of all jobs, node status and load, usage pattern history; alter cost structure and scheduling policy; cancel/suspend/resume any job.
    - Access via Linux command prompt or SGE interface.
  - Verification approaches:
    - Role-based access tests using the stated interfaces to confirm users can access only their own job/status/accounting data, and administrators can access/modify cluster-wide data and controls.
    - Negative tests: verify users cannot access other users’ job status or administrative functions.

- d) Data entities and their relationships
  - Entities (implied by functions): User, Job, SchedulingInformation, Node, Queue, ClusterState, Accounting/UsageRecord.
  - Relationships (implied by flows):
    - Job belongs to a User.
    - Job is assigned to one execution host (Node) and one Queue at a time.
    - SchedulingInformation is associated with a Job on its execution host.
    - ClusterState aggregates Node/Queue state and pending job remaining times.
    - Accounting/UsageRecord links to User and Job.
  - Verification approaches:
    - After Determine Execution Host and Dispatch Job, verify a single (host, queue) association per job and presence of the job in that queue.
    - After Execute Job iterations, verify SchedulingInformation updates (pass advancement by stride) remain correctly linked to the job.
    - Consistency checks that ClusterState equals the aggregation of Node/Queue states.
    - [N/A] for detailed keys, cardinalities, or schema not specified.

- e) Integrity constraints
  - Stated constraints:
    - Authentication is required to view job status and to delete/change jobs.
    - Administrative authority is required to alter scheduling criteria, execution, or cost structures.
    - Deadline and cost are “not normally” changeable once submitted; limited changes (e.g., output directory, delayed deadline) may be permitted.
    - Maximum charged cost must not exceed the user’s submitted maximum.
    - No job migration for reducing resource fragmentation (job remains on its assigned host).
  - Verification approaches:
    - Attempt unauthorized reads/writes of job records and administrative settings; verify enforcement.
    - Attempt to modify immutable fields (deadline, cost) post submission/acceptance; verify rejection except for expressly permitted cases.
    - Billing/accounting reconciliation: verify charged cost ≤ submitted maximum for completed jobs.
    - Attempt to trigger job migration; verify it is not performed.
    - [N/A] for additional field-level constraints (e.g., ranges, formats) not specified.

- f) Security
  - Stated objectives: privacy of user job status; administrative security; prevention of unauthorized alteration of scheduling criteria or resource allocation.
  - Verification approaches:
    - Authentication/authorization tests for both user and administrator roles across all data access paths (CLI/SGE interface).
    - Multi-user isolation tests ensuring users cannot view others’ job status.
    - [N/A] for audit logging, encryption, or specific security standards not specified.

- g) Data retention requirements
  - Stated/implicit needs: ability for users to check usage history; minimal job accounting maintained.
  - Verification approaches:
    - Complete and cancel jobs; verify usage history and accounting records persist and remain queryable post completion/cancellation.
    - [N/A] for explicit retention durations, archival, or deletion policies not specified.

## 4.6 Design constraints

This section defines how compliance with each Design Constraint in Requirements 3.6 will be verified.

- Parent component: Sun Grid Engine (SGE)
  - Design review: Confirm Libra is architected and packaged as an SGE sub-component, interacting only through SGE’s documented interfaces and extension points.
  - Code inspection: Trace all integration points to SGE APIs/daemons; verify no direct kernel scheduling hooks or bypass of SGE’s resource manager.
  - Integration tests: Execute end-to-end job flows (submit → schedule → dispatch → execute) via SGE, validating that all control and data paths traverse SGE.
  - Deployment validation: Install and run on an SGE-managed cluster; verify operation without any non-SGE communication or hardware control paths.

- Software language: Standard C
  - Build enforcement: Configure the build to use a C toolchain only; fail builds if non-C sources or C++/other language link-time artifacts are detected.
  - Static analysis: Run language-aware analyzers on the entire codebase to ensure only C is used.
  - Source audit: Periodic audits to confirm all production source files are C and that no language extensions contradict the “standard C” requirement.

- Scheduling constraints: Heuristics only; no exhaustive searches over job combinations
  - Algorithm review: Formal review of the scheduler design documenting the heuristic approach and explicitly excluding exhaustive combinatorial enumeration.
  - Code inspection: Verify absence of exponential/factorial iteration over job sets; check complexity of core scheduling routines.
  - Complexity benchmarking: Measure scheduling-decision latency as job count increases; demonstrate non-exponential growth and adherence to expected heuristic performance.
  - Workload tests: Run synthetic and mixed workloads to confirm the scheduler makes decisions within acceptable time bounds without resorting to exhaustive search.

## 4.7 Software system attributes

- Reliability
  - Verify maximum bug rate ≤ 1 bug/KLOC by:
    - Counting delivered KLOC of the scheduler code base (standard C only) and tallying confirmed defects found during integration, system, and acceptance testing; confirm defect density threshold at release.
    - Reviewing defect logs to ensure classification and counting rules are consistent across test phases.
  - [N/A] Mean time between failures, fault tolerance, and fault-injection criteria are not specified.

- Availability
  - Verify maximum time to repair (service restoration after outage) < 5 minutes by:
    - Performing controlled shutdowns and restarts of the cluster; time OS boot and service startup on the master host until the scheduler and SGE accept new submissions.
    - Repeating across at least three trials; all must meet the < 5 minutes criterion.
  - [N/A] Checkpoint, recovery, and restart mechanisms for running jobs are not specified.

- Security
  - Verify privacy of user job status:
    - Attempt authenticated access to job status using correct user credentials; expect success for own jobs and denial for other users’ jobs.
    - Attempt unauthenticated/invalid credential access; expect denial and no disclosure.
  - Verify administrator-only control over scheduling criteria and resource allocation:
    - Execute alteration attempts (e.g., change deadlines, budgets, priorities) as non-admin users; expect denial.
    - Execute same operations as administrator; expect success and auditable outcome via SGE/CLI output.
  - Verify user/administrator command permissions:
    - Users can cancel only their own jobs; administrators can cancel/suspend/resume any job; confirm via positive and negative tests.
  - [N/A] Use of cryptographic techniques is not specified.
  - [N/A] Security logging or history data sets are not specified.
  - [N/A] Security-driven module separation is not specified.
  - [N/A] Communications restrictions beyond SGE defaults are not specified.
  - [N/A] Data integrity checks for critical variables are not specified.
  - [N/A] Assurances beyond job-status privacy are not specified.

- Maintainability
  - Verify adherence to naming convention:
    - Perform static code inspections to confirm use of the Hungarian Naming Convention across all source files and interfaces.
  - Verify coding standards and licensing conformance:
    - Check presence of GPL-required notices and conformance to GPL distribution requirements in source and documentation.
  - [N/A] Specific modularity, interface, or complexity limits are not specified.
  - [N/A] Maintenance procedures or turnaround targets (other than availability-related reboot time) are not specified.

- Portability
  - Verify use of a proven portable language and toolchain:
    - Build the scheduler with a standard C compiler on a supported Linux distribution without kernel modifications; confirm successful compile and link against SGE 5.3, MPI, and PVM where required.
    - Execute basic functional smoke tests on a homogeneous Linux cluster to confirm runtime compatibility.
  - Verify kernel independence:
    - Confirm installation and operation on a stock Linux kernel (no patches or custom modules).
  - [N/A] Percentage of host-dependent elements and code is not specified.
  - [N/A] Use of a particular compiler version or language subset beyond “standard C” is not specified.
  - [N/A] Porting to non-Linux operating systems is not specified.

## 5.1 Assumptions and dependencies

- The Sun Grid Engine (SGE) cluster management system is available and operational, delegating submitted jobs to Libra and dispatching scheduled jobs to execution hosts.
- SGE v5.3 is available and can be modified to integrate Libra and to accept additional submission parameters (e.g., budget, deadline, execution time).
- SGE modules (including those related to process migration) are compatible with Libra’s scheduling policies.
- A Linux operating system is available on all cluster nodes; no kernel modifications are required.
- The cluster environment is homogeneous (uniform node characteristics and same operating system).
- Only sequential and embarrassingly parallel batch jobs are submitted and managed.
- PVM and MPI libraries are available for executing embarrassingly parallel jobs.
- Users provide reasonably accurate estimates of job execution times to enable accept/reject and scheduling decisions.
- A basic job accounting and payment module exists outside Libra to provide budget/credit information and usage history.
- An economic pricing/front-end mechanism will be defined/provided later; Libra assumes given budgets and costs for scheduling.
- User and administrator interactions are through the Linux command line or SGE’s interface; no GUI is available initially.
- The communications, hardware, and resource usage interfaces are provided by SGE (CPU, memory, swap, and network).
- A simulation/testing tool (generic or custom) will be available for testing and performance analysis.
- There is no user-to-user negotiation/bargaining mechanism for resources (unlike grid systems such as Nimrod/G).

## 5.2 Acronyms and abbreviations

- SRS — Software Requirements Specification
- QoS — Quality of Service; meeting what users actually want, maximizing their utility
- SGE — Sun Grid Engine; cluster management system used with Libra
- CPU — Central Processing Unit
- GUI — Graphical User Interface
- GPL — GNU General Purpose License; open-source license referenced for Libra
- MPI — Message Passing Interface; library used for parallel computing
- PVM — Parallel Virtual Machine; library used for parallel computing
- FIFO — First-In, First-Out; job ordering policy for tie-breaking
- RAM — Random Access Memory
- ID — Identifier (e.g., user ID)