## 1.1 Purpose

The purpose of Libra is to provide an economy-driven cluster scheduler that maximizes user utility by allocating CPU time according to user-specified Quality of Service (QoS) parameters—primarily budget and deadline—rather than system-centric policies. Operating as an add-on to the Sun Grid Engine (SGE) on a homogeneous Linux cluster, Libra schedules sequential and embarrassingly parallel batch jobs to deliver QoS-oriented computational economy without user-to-user bargaining.

## 1.2 Scope

This SRS specifies the Libra Scheduler, an Economy-Driven Cluster Scheduler delivered as an add-on to the Sun Grid Engine (SGE) cluster management system (version 5.3) operating on Linux-based clusters. The product focuses on QoS-aware scheduling of batch jobs using user-specified constraints.

Products to be produced
- Libra Scheduler: an SGE-integrated scheduling module that implements market-based, economy-driven scheduling.
- Submission interface extensions to SGE: adaptations to accept additional QoS parameters (e.g., budget and deadline) required by Libra.

What the product will do
- Schedule CPU time based on user-centric QoS parameters (budget and deadline), rather than system-centric policies.
- Accept or reject jobs according to feasibility under stated QoS constraints and estimated execution time.
- Allocate resources proportionally using a bid-based proportional resource-sharing model and enforce allocations via stride scheduling.
- Select execution hosts and queues, dispatch jobs, and update cluster status during execution.
- Provide dynamic reallocation and prioritization so urgent, higher-priced jobs can be accommodated even under load.
- Support basic job accounting and administrative security; user interaction occurs via SGE/command-line interfaces.

Application, benefits, objectives, and goals
- Application: batch job scheduling on homogeneous Linux clusters managed by SGE, for sequential and embarrassingly parallel workloads.
- Objectives and goals:
  - Provide QoS computational economy in cluster computing.
  - Maximize user utility/satisfaction within user-imposed budget and deadline constraints.
  - Enable dynamic, configurable, and scalable scheduling policies separable from the cluster management system.
- Benefits:
  - Aligns resource allocation with user priorities (deadline and budget).
  - Supports load-balanced placement and proportional CPU sharing across competing jobs.

Scope boundaries
- In scope: scheduling of sequential and embarrassingly parallel jobs on homogeneous Linux clusters; resource considered is CPU time (extendable later).
- Out of scope: user-to-user interaction or bargaining (as in grid environments such as Nimrod/G); real parallel jobs with interdependent threads; Linux kernel modifications.

### 1.3.1 Product perspective

Libra is an economy-driven scheduler that operates as an add-on and sub-component of the Sun Grid Engine (SGE) cluster management system on a homogeneous Linux cluster. SGE receives user-submitted jobs and delegates scheduling to Libra. Libra evaluates acceptance based on user QoS parameters (budget, deadline), determines execution hosts/queues, and enforces proportional resource allocations (via stride scheduling). Libra communicates selected host/queue decisions and updates to SGE’s resource manager/dispatcher, which then dispatches jobs to execution hosts. No modifications to the Linux kernel are required. Libra is designed to be configurable and separable while running within SGE’s operational environment.

Major elements and interconnections (conceptual):
- Users/Administrators → SGE submission/management interfaces → Libra (accept/reject, scheduling decisions) → SGE resource manager/dispatcher → Execution hosts/queues on Linux nodes → Libra status updates to SGE master.
- Optional libraries used for embarrassingly parallel jobs: PVM and MPI.

#### System interfaces
- Interface: SGE Job Submission/Queue Management → Libra
  - Functionality: SGE passes job and cluster state to Libra for accept/reject and scheduling computations based on budget/deadline and execution time.
  - Interface description: Via SGE’s existing mechanisms; detailed message formats are [N/A].
- Interface: Libra → SGE Resource Manager/Dispatcher
  - Functionality: Libra returns execution host/queue selections and scheduling parameters (e.g., tickets/stride/pass) for dispatch.
  - Interface description: Via SGE’s existing mechanisms; detailed message formats are [N/A].
- Interface: Libra ↔ SGE Master Information Store
  - Functionality: Libra updates cluster status when jobs are scheduled/removed (node/queue load, remaining times).
  - Interface description: Via SGE’s information dissemination facilities; detailed message formats are [N/A].
- Interface: Libra → Linux (via SGE)
  - Functionality: Execution occurs under Linux; no kernel changes required.
  - Interface description: Indirect through SGE; [N/A] for low-level details.

#### User interfaces
- User types: Cluster user; Cluster administrator.
- Access: Linux command line and/or SGE interface.
- Cluster user actions:
  - Submit jobs with deadline, budget (cost), and execution time.
  - Query current cost per unit time for new jobs.
  - Monitor job status.
  - Cancel submitted jobs.
  - Check credit balance and usage history.
- Cluster administrator additional actions:
  - Check node/cluster status, usage patterns, loads.
  - Alter cost structure and scheduling policy.
  - Cancel, suspend, and resume any job.
- Style/interaction standards: [N/A].

#### Hardware interfaces
- Libra uses SGE’s hardware interfaces for:
  - CPU usage,
  - Memory usage,
  - Swap file creation,
  - Network communication.
- Supported devices/protocol details, configurations (ports, instruction sets, etc.): [N/A].
- Operating environment: Homogeneous Linux cluster. Specific node counts/specs are project constraints, not interface requirements.

#### Software interfaces
- Sun Grid Engine
  - Name: Sun Grid Engine
  - Mnemonic: SGE
  - Specification number: [N/A]
  - Version: 5.3
  - Source: Sun Microsystems (open-source distribution)
  - Purpose: Cluster job submission, resource management, dispatching, and communications; Libra integrates as a sub-component for QoS-driven scheduling.
  - Interface definition: Uses SGE’s documented interfaces; message content/format references: [N/A].
- Operating System
  - Name: Linux
  - Mnemonic: [N/A]
  - Specification number: [N/A]
  - Version: [N/A]
  - Source: Open-source
  - Purpose: Host OS for SGE, Libra, and executed jobs; no kernel modifications required.
  - Interface definition: Indirect via SGE; references: [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, ORNL, Emory University
    - Purpose: Enable execution of embarrassingly parallel jobs.
    - Interface definition: Standard library APIs; references: [N/A].
  - Name: Message Passing Interface
    - Mnemonic: MPI
    - Specification number: [N/A]
    - Version: [N/A]
    - Source: University of Chicago, Mississippi State University
    - Purpose: Enable execution of embarrassingly parallel jobs.
    - Interface definition: Standard MPI APIs; references: [N/A].

#### Communications interfaces
- Libra utilizes SGE’s communications architecture and does not introduce unique communications interfaces beyond SGE.
- Network protocols and configurations: [N/A].

#### Memory constraints
- Applicable characteristics and limits on primary/secondary memory: [N/A].

#### Operations
- Modes:
  - User-initiated operations via CLI/SGE interface (submit, monitor, cancel, query costs).
  - Administrator operations via CLI/SGE interface (cluster status, policy/cost changes, control of any job).
- Execution:
  - Continuous/unattended scheduling and time-slicing while jobs exist in queues (stride scheduling loop).
- Data processing support:
  - Basic job accounting to aid scheduling policies.
- Backup and recovery:
  - On outage, recovery involves Linux reboot; expected under five minutes.
  - Additional backup procedures: [N/A].

#### Site adaptation requirements
- Site-specific initialization and configuration may include:
  - Defining cost structure and pricing policy (administrator configurable).
  - Selecting and tuning scheduling policy parameters within Libra/SGE.
  - Configuring queues for sequential vs. embarrassingly parallel jobs.
  - Enabling and configuring PVM/MPI where required.
  - Defining cluster characteristics (homogeneous Linux nodes) within SGE.
- Safety limits/grid values/mission-specific data: [N/A].

#### Interfaces with services
- Interactions with external services (e.g., SaaS, cloud services): [N/A].

### 1.3.2 Product functions

Libra is an economy-driven scheduling add-on for Sun Grid Engine (SGE) on a homogeneous Linux cluster. It schedules CPU time to maximize user Quality of Service (QoS) based on user-specified budget and deadline, for sequential and embarrassingly parallel batch jobs, without user-to-user bargaining.

- Job submission and initialization
  - Accept job requests via SGE/command line; verify user and cluster submission state.
  - Collect and parse job specifications: executable and input locations, output destination, system type, maximum runtime, job type (sequential or embarrassingly parallel), budget, and deadline.
  - Initialize internal job state and register the job with the scheduler.

- QoS-driven admission control
  - Evaluate feasibility against declared execution time, budget, deadline, and current cluster load.
  - Accept or reject jobs; when infeasible under current terms, suggest revised cost or deadline conditions for acceptance.

- Share calculation and scheduling policy
  - Derive job priority/share from budget and deadline using a market-based (bid/proportional share) model.
  - Allocate tickets and compute stride/pass values to enforce proportional CPU shares.
  - Dynamically adjust priorities, resource limits, privileges, and execution order in response to changing load and QoS needs.
  - Support configurable scheduling policies incorporating QoS parameters.

- Resource selection and dispatch
  - Select execution host and queue based on host load, available memory, job type, execution time, budget, and deadline (favor least-loaded hosts for load balancing).
  - Dispatch jobs to selected queues at appropriate times; manage queue insertion and start timing.

- Execution-time CPU scheduling
  - Time-slice competing jobs using stride scheduling to deliver proportional CPU allocation.
  - Resolve ties with FIFO ordering and repeatedly advance passes until queues empty.

- Cluster state management
  - Reserve resources on selected hosts; update per-queue/host load and remaining times.
  - Propagate status updates to the master host’s central information store when jobs are scheduled or complete.

- Monitoring and control (user and administrator)
  - User: view job status; cancel jobs; change limited non-critical parameters (e.g., output directory, delayed deadline when permissible).
  - Administrator: monitor all jobs and nodes (status, load, usage patterns); alter cost structure and scheduling policy; cancel, suspend, and resume any job.

- Accounting, pricing, and quotas
  - Provide basic job accounting and usage history to support policy decisions.
  - Enable users to query current cost per unit time, check credit balance, and review usage history.
  - Ensure charged cost does not exceed user-submitted maximum budget.

- Integration and interfaces
  - Interface with SGE for job intake, dispatch, and resource management; rely on SGE/OS for hardware and communication.
  - Utilize MPI/PVM for executing embarrassingly parallel jobs.
  - Provide command-line interfaces for users and administrators; a GUI may be added later.

### 1.3.3 User characteristics

The product serves two distinct user groups whose characteristics influence usability:

- Cluster users (job submitters)
  - Role: Submit sequential or embarrassingly parallel batch jobs to the cluster and monitor/manage their own jobs.
  - Technical expertise: Able to use the Linux command line or Sun Grid Engine (SGE) interface; capable of supplying complete job parameters (executable/data locations, system type, estimated execution time, job type, budget, deadline).
  - Experience: Understands the nature and resource needs of their jobs; assumed to provide a fair estimate of execution time.
  - Educational level: [N/A]
  - Disabilities/accessibility: [N/A]

- Cluster administrators
  - Role: Oversee scheduling and cluster usage; administer policies and operations.
  - Technical expertise: Advanced cluster operators, fully qualified with Linux, SGE, and the Libra Scheduler.
  - Experience: Skilled in monitoring node/load status and all submitted jobs; altering cost structure and scheduling policy; and cancelling/suspending/resuming jobs with appropriate authority.
  - Educational level: [N/A]
  - Disabilities/accessibility: [N/A]

Note: User interaction is primarily via command-line or SGE interface; a GUI may be added later.

### 1.3.4 Limitations

- a) Regulatory requirements and policies
  - Must be released under GPL and remain open-source; all code and documentation must comply with the GNU General Public License.
  - Naming convention and coding standards are constrained (Hungarian Naming Convention; GPL-related practices).
  - No purchased components.

- b) Hardware limitations
  - Targeted for a homogeneous Linux cluster; no Linux kernel modifications permitted.
  - Current test environment is limited (four Pentium-III workstations with 128 MB RAM each), constraining validation and performance analysis.
  - Hardware interaction is limited to what Sun Grid Engine (SGE) exposes (CPU, memory, swap, network).

- c) Interfaces to other applications
  - Direct dependency on Sun Grid Engine (SGE) version 5.3; Libra is a sub-component and uses SGE’s interfaces and communications architecture.
  - Uses PVM/MPI libraries for embarrassingly parallel jobs.
  - User interaction is limited to the Linux command line and/or the SGE interface; a GUI is not initially provided.

- d) Parallel operation
  - Supports only sequential and embarrassingly parallel batch jobs; does not support tightly coupled parallel jobs with inter-thread communication.
  - Job migration for reducing resource fragmentation is not supported.

- e) Audit functions
  - Provides only a basic level of job accounting and payment functionality; comprehensive billing/audit features are out of scope.

- f) Control functions
  - Users generally cannot change critical QoS parameters (deadline, cost) after submission.
  - Administrative control is required to alter scheduling policies and cost structures; only administrators can cancel/suspend/resume any job.
  - Exhaustive combinatorial scheduling is not performed; heuristics are used.

- g) Higher-order language requirements
  - All implementation must be in standard C.

- h) Signal handshake protocols (e.g., XON-XOFF, ACK-NACK)
  - [N/A]

- i) Quality requirements (e.g., reliability)
  - No job migration for defragmentation.
  - Maximum bug rate targeted at 1 bug/KLOC.
  - Maximum time to repair limited to Linux reboot time (< 5 minutes).
  - Performance constraints include ≤ 1 minute response time for job submission, completion within 10% of specified deadlines (assuming accurate job statistics), and never charging above the user’s specified maximum cost.

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

- k) Safety and security considerations
  - Security: Ensures privacy of user job status and prevents unauthorized alteration of scheduling criteria or resource allocation (administrator authority required).
  - Safety: [N/A]

- l) Physical/mental considerations
  - Users must possess technical know-how to submit jobs; administrators must be advanced operators proficient with Linux, SGE, and Libra.

- m) Limitations sourced from other systems (including real-time requirements through interfaces)
  - Functional dependency on SGE modules (e.g., process migration behavior) is assumed to be compatible with Libra’s policies.
  - Scheduling capacity and acceptance are limited by node capacity and the accuracy of user-provided execution time estimates.
  - Communications and interfacing are constrained to those provided by SGE; no additional real-time signaling requirements are specified.

## 1.4 Definitions

- Cluster / Cluster Computing: Connecting two or more computers into an integrated resource that provides a single system image and transparently spreads processing of jobs across nodes for high-performance applications.

- Quality of Service (QoS): Meeting what users actually want, maximizing their utility, rather than solely optimizing system-centric metrics.

- Computational Economy: A user-centric resource management approach in which users specify QoS parameters (e.g., deadline and budget) that drive scheduling priorities and resource allocation, instead of system-centric policies (e.g., FIFO by submission time).

- Grid Computing: An infrastructure that couples distributed resources (computers, software, devices) across networks and presents them as a unified, widely usable resource for processing jobs.

- Bid-based Proportional Resource-Sharing Model: An economic model allocating resources proportionally to users’ bids (e.g., credits/tokens), where effective priority reflects users’ deadline and budget alongside system load; a scheduler enforces proportional allocation based on these priorities.

- Stride Scheduling: A deterministic scheduling algorithm that enforces proportional sharing using tickets. Each job’s stride is inversely proportional to its tickets; the job with the lowest pass runs next, and its pass increases by its stride, yielding precise proportional allocations.

- Process Migration: Moving a running job from one system to another without restarting execution from the beginning.

- Sequential Jobs: Jobs that must execute on a single node and cannot be split into independent parts.

- Embarrassingly Parallel Jobs: Parallel workloads composed of independent parts that can run on separate nodes with minimal inter-job communication, unlike tightly coupled parallel jobs.

- Job Accounting: Quantification and recording of system resources consumed by a job to support scheduling policies and usage tracking.

- Sun Grid Engine (SGE): A cluster management system that handles job submission, resource management, and integration with the scheduler.

- Homogenous Cluster: A cluster whose nodes have uniform characteristics (e.g., memory, storage) and run the same operating system.

# 2 References

The following documents are cited in this SRS. Each entry identifies the title, report number (if applicable), date, publishing organization, and source. Items not provided in the original SRS are marked [N/A].

## Compliance

- Title: GNU General Purpose License (GPL)
  - 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]

## Guidance

- Title: Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid
  - Authors: R. Buyya, D. Abramson, J. Giddy
  - Venue: HPC ASIA’2000, China
  - 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
  - Authors: R. Buyya, D. Abramson, J. Giddy
  - Venue: The 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000), Las Vegas, USA
  - 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
  - Authors: R. Buyya, D. Abramson, J. Giddy
  - Venue: 10th IEEE International Heterogeneous Computing Workshop (HCW 2001), with IPDPS 2001, San Francisco, California, USA
  - 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
  - Authors: Rajkumar Buyya, Heinz Stockinger, Jonathan Giddy, David Abramson
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: Monash University
  - Source: [N/A]

- Title: Market-based proportional resource sharing for clusters
  - Authors: B.N. Chun, D.E. Culler
  - Status: Submitted for publication
  - Report number: [N/A]
  - Date: September 1999
  - Publishing organization: [N/A]
  - Source: [N/A]

- Title: Linux manual (man) pages
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: [N/A]

- Title: Message Passing Interface (MPI) library documentation
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: [N/A]

- Title: Parallel Virtual Machine (PVM) documentation
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: [N/A]

## 3.1 Functions

This section specifies the functional behavior of the Libra Scheduler (an add-on to Sun Grid Engine, SGE), including input validity checks, operation sequences, responses to abnormal conditions, parameter effects, and input/output relationships. Functions are partitioned into sub-functions for clarity; this partitioning does not mandate a design structure.

High-level input/output sequence:
1) Submit Job (via SGE interface)
2) Initialize Job (in Libra)
3) Accept/Reject Job
4) Calculate Scheduling Information
5) Determine Execution Host
6) Dispatch Job
7) Execute Job (ongoing while queues are non-empty)
8) Update Cluster Status (on schedule and on completion)
9) View Job Status (user/admin query; read-only)
10) Delete/Change Job (optional; user/admin)

F1. Submit Job
- Purpose: Accept a job submission request via SGE, augmented with QoS parameters.
- Inputs:
  - User information (name, authentication id)
  - Job information: executable and input locations, system type, maximum execution time (standalone runtime), job type (sequential or embarrassingly parallel), budget, deadline, output destination
  - Cluster information (current load status, submission criteria)
- Validity checks on inputs:
  - Verify cluster is open for job submissions
  - Verify user identity/authorization
  - Check presence of required job parameters listed above
- Exact sequence of operations:
  1) Receive submission request via SGE or command line
  2) Check cluster submission state
  3) Authenticate user
  4) If checks pass, forward job metadata to Libra for initialization
- Outputs:
  - Boolean: cluster accepting submissions (true/false)
  - Boolean: user verified (true/false)
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: On system outage, cluster reboot occurs with Linux boot time less than five minutes
  - Error handling and recovery: [N/A]
- Effect of parameters:
  - Budget and deadline will determine downstream priority, tickets, host selection, and feasibility
  - Job type affects queue selection
- Relationship of outputs to inputs:
  - If cluster closed or authentication fails, submission is rejected; otherwise job proceeds to Initialize Job
  - Input/output sequence conforms to high-level sequence above
  - Formulas: [N/A]

F2. View Job Status
- Purpose: Allow user/admin to view submitted job details and execution progress.
- Inputs:
  - User id and password
- Validity checks on inputs:
  - Authenticate requester; ensure requester is authorized to view the job(s)
- Exact sequence of operations:
  1) Authenticate requester
  2) Retrieve job status and available options
  3) Present selected information to requester
- Outputs:
  - User view of available options and current job status/progress
- 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:
  - None (read-only)
- Relationship of outputs to inputs:
  - Output content corresponds to authenticated user’s jobs and selected view options
  - Formulas: [N/A]

F3. Delete/Change Job
- Purpose: Permit cancellation or limited modification of a submitted job.
- Inputs:
  - User id and password
  - Job identifier
  - Change request (e.g., output directory, delayed deadline)
- Validity checks on inputs:
  - Authenticate requester; verify authorization for the target job
  - Validate change type (deadline and cost normally not changeable; limited exceptions noted)
- Exact sequence of operations:
  1) Authenticate and authorize requester
  2) If cancel: remove job from queue
  3) If change permitted: apply change to job metadata
  4) Trigger scheduling recalculation as needed
- Outputs:
  - Updated cluster information and scheduling decisions (CPU load, node status, queue length, quanta allocated to pending jobs, revised expected finishing deadlines)
- 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:
  - Changes to allowed parameters (e.g., output directory) have no scheduling effect; a delayed deadline may relax constraints and impact scheduling
- Relationship of outputs to inputs:
  - Cancel input removes job; change input updates metadata and may trigger rescheduling
  - Formulas: [N/A]

F4. Initialize Job
- Purpose: Prepare scheduler state with a newly submitted job’s details.
- Inputs:
  - Job details from SGE (Job Id, Job type, standalone execution time, executable/input locations, system type, budget, deadline)
- Validity checks on inputs:
  - Verify presence and parsability of all required job fields
- Exact sequence of operations:
  1) Retrieve job metadata
  2) Parse and set internal variables representing job and cluster state
  3) Pass parsed parameters to acceptance module
- Outputs:
  - In-memory job representation with fields set for downstream processing
- 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:
  - Budget, deadline, and execution time directly affect subsequent acceptance and scheduling
- Relationship of outputs to inputs:
  - Output mirrors the validated input fields for the job
  - Formulas: [N/A]

F5. Accept/Reject Job
- Purpose: Decide feasibility of meeting the user’s QoS (budget, deadline) given current cluster state.
- Inputs:
  - Job details (see F4)
  - Cluster information (CPU load, node status, remaining time of pending jobs)
- Validity checks on inputs:
  - Ensure execution time, budget, and deadline are provided and valid (format/range)
- Exact sequence of operations:
  1) Estimate job priority/share based on budget/deadline relative to other jobs and system state
  2) Determine feasibility of completing by the specified deadline
  3) If infeasible under given budget/deadline, compute and return suggested alternative (deadline or cost) for acceptability
- Outputs:
  - Boolean: accept/reject
  - Suggested deadline and/or cost (precondition for acceptance)
- 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:
  - Higher budget and/or more relaxed deadline increase likelihood of acceptance
  - Execution time strongly influences feasibility
- Relationship of outputs to inputs:
  - Acceptance is a function of job’s budget, deadline, and execution time versus current load and pending work
  - Formulas: [N/A] (priority/share derivation not specified)

F6. Calculate Scheduling Information
- Purpose: Compute tickets, stride, and pass values to enforce proportional CPU allocations.
- Inputs:
  - Job details (see F4)
  - Context of other jobs on the execution host (their budgets/deadlines)
- Validity checks on inputs:
  - Presence of budget and deadline
  - Tickets must be positive before stride calculation
- Exact sequence of operations:
  1) Allocate tickets based on the job’s budget and deadline relative to other jobs on the host
  2) Compute stride = global_stride_constant / tickets
  3) Initialize pass = stride
- Outputs:
  - Scheduling information: tickets, stride, pass
- 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:
  - Higher budget and tighter deadline increase tickets, reducing stride and increasing CPU share
- Relationship of outputs to inputs:
  - Stride is inversely proportional to tickets; pass initialized from stride
  - Formulas:
    - stride = global_stride_constant / tickets
    - pass_initial = stride
    - Ticket allocation formula: [N/A] (policy-specific details not provided)

F7. Determine Execution Host
- Purpose: Choose the node and queue for job execution.
- Inputs:
  - Job details (see F4)
  - Cluster information (CPU load, node status, remaining time of pending jobs, available memory)
- Validity checks on inputs:
  - Availability of at least one suitable host and appropriate queue for job type
- Exact sequence of operations:
  1) Sort hosts by current load in ascending order
  2) Select least-loaded suitable host
  3) Select queue based on job type (sequential vs embarrassingly parallel) and QoS parameters
- Outputs:
  - Chosen execution host and 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:
  - Job type determines queue selection; budget/deadline may influence host/queue choice under load considerations
- Relationship of outputs to inputs:
  - Output host/queue is a function of current load, resource availability, and job characteristics
  - Formulas: [N/A]

F8. Dispatch Job
- Purpose: Place accepted job into the selected host’s queue at the appropriate time.
- Inputs:
  - Chosen execution host and queue
- Validity checks on inputs:
  - Verify host/queue availability at dispatch time
- Exact sequence of operations:
  1) Decide dispatch timing (may defer to allow priority jobs to run first)
  2) Insert job into target queue
- Outputs:
  - Scheduled job in its host and 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:
  - Budget/deadline priorities may affect dispatch timing relative to other jobs
- Relationship of outputs to inputs:
  - Dispatch uses the previously selected host/queue; no data conversion
  - Formulas: [N/A]

F9. Update Cluster Status
- Purpose: Maintain accurate cluster state when jobs are scheduled or complete.
- Inputs:
  - Job details (see F4)
  - Chosen execution host and queue
- Validity checks on inputs:
  - Verify the job/host/queue references are valid and current
- Exact sequence of operations:
  1) Reserve required resources on the node
  2) Update execution host queue status
  3) Send updated load/queue information to master host’s central store
- Outputs:
  - None (state update only)
- 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:
  - Resource reservations reflect job’s execution time and type
- Relationship of outputs to inputs:
  - Internal state changes reflect the input job and host/queue references
  - Formulas: [N/A]

F10. Execute Job
- Purpose: Time-slice CPU among runnable jobs per stride scheduling to enforce proportional shares.
- Inputs:
  - Scheduled jobs (with job details and assigned queues/nodes)
  - Scheduling information (tickets, stride, pass) for each job
- Validity checks on inputs:
  - Each job has valid stride and pass values; scheduling list is non-empty
- Exact sequence of operations:
  1) While a queue has jobs, select the job with the minimum pass value
  2) Allot one quantum to the selected job
  3) Advance that job’s pass by its stride
  4) On ties, break by FIFO order
  5) Repeat until the queue empties
- Outputs:
  - Updated cluster information (CPU load, node status, remaining time of pending jobs, available memory)
- 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:
  - Higher tickets (due to budget/deadline) reduce stride, increasing scheduling frequency and CPU share
- Relationship of outputs to inputs:
  - CPU time granted per cycle is proportional to tickets via stride scheduling
  - Formulas:
    - stride = global_stride_constant / tickets
    - pass_next = pass_current + stride
    - Job selection = argmin(pass) with FIFO tie-breaker

## 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 to be handled (quantified): [N/A]

- Dynamic numerical requirements:
  - Job submission response time: The system shall provide a response to the submission of a job within 60 seconds.
  - Deadline adherence: Assuming submitted job statistics are accurate, the system shall ensure that accepted jobs complete within 10% of their requested deadlines.
  - Capacity: The scheduler shall impose no inherent upper bound on the number of schedulable jobs; the effective limit is determined solely by the capacity of the nodes to fulfill job deadlines.
  - Cost adherence: Under all circumstances, the cost charged to a user shall not exceed the maximum cost the user submitted for the job.

- Workload conditions (normal and peak), throughput, and data volumes: [N/A]

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

## 3.3 Usability requirements

- Contexts of use
  - Users: cluster users and cluster administrators.
  - Environment: Linux-based clusters using the Sun Grid Engine (SGE).
  - Interaction modes: Linux command-line and/or SGE interface; no GUI is required in the current version.
  - User preconditions: users know job details (e.g., execution time, resources); administrators are advanced Linux/SGE/Libra operators.

- Effectiveness (quality in use)
  - Deadline adherence: assuming accurate job statistics, jobs will complete within a 10% error allowance of the stated deadline.
  - Task coverage: the system provides commands for submitting jobs with deadline/budget/execution time, querying current cost per unit time, monitoring job status, canceling jobs, and viewing credit balance and usage history; administrators can also check node/cluster status and history, alter cost structure and scheduling policy, and cancel/suspend/resume any job.
  - Measurable task success rate targets: [N/A]

- Efficiency (quality in use)
  - Job submission response time: ≤ 1 minute from submission to acknowledgement.
  - Operator effort targets (e.g., number of steps/keystrokes per task): [N/A]

- Satisfaction
  - User satisfaction targets (e.g., ratings, complaints thresholds, adoption rates): [N/A]

- Avoidance of harm and misuse
  - Privacy: only the appropriate user can view job status (user ID and password required).
  - Authorization: only administrators can alter scheduling criteria or actual resource allocation.
  - Cost protection: under all circumstances, the charged cost will not exceed the user-submitted maximum cost.
  - Safety-related misuse metrics or incident thresholds: [N/A]

- Learnability and operability
  - Operability: all required tasks must be performable via the Linux command line and/or SGE interface.
  - Documentation: man pages will be provided for online help.
  - Learnability targets (e.g., training time, error rates for first-time users): [N/A]

- Accessibility
  - Accessibility requirements (e.g., keyboard-only operation standards, screen-reader compatibility): [N/A]

## 3.5 Logical database requirements

Libra persists and retrieves operational state via the Sun Grid Engine (SGE) central information store on the master host. No separate database technology is specified.

### a) Types of information used by various functions
- User
  - Authentication identifier; name.
  - Credit balance; usage history.
  - Used by: Submit Job, View Job Status, Delete/Change Job, user/admin interfaces.
- Job
  - Job Id; job type (sequential or embarrassingly parallel); standalone execution time estimate; system type; budget (maximum cost); deadline; locations of executable and input data; output location; current status; assigned execution host and queue; submission/start/finish timestamps; expected finish time.
  - Used by: Initialize Job, Accept/Reject Job, Determine Execution Host, Dispatch Job, Execute Job, Update Cluster Status, View Job Status, Delete/Change Job.
- Scheduling parameters
  - Tickets, stride, pass (as computed by Calculate Scheduling Information).
  - Used by: Calculate Scheduling Information, Execute Job.
- Cluster status
  - CPU load; node status; remaining time of pending jobs; available memory; queue lengths.
  - Used by: Accept/Reject Job, Determine Execution Host, Execute Job, Update Cluster Status, administrator queries.
- Execution host (node) and queues
  - Host Id; capabilities (e.g., CPU, memory); current load; available queues; queue type (sequential vs embarrassingly parallel).
  - Used by: Determine Execution Host, Dispatch Job, Update Cluster Status, administrator queries.
- Accounting and usage history
  - Resource usage per job; cost charged; user usage history; cluster usage history.
  - Used by: user/admin interfaces; basic job accounting; policy tuning.
- Cost structure/pricing policy
  - Current cost per unit time; pricing configuration.
  - Used by: user query of current cost; Accept/Reject Job; administrator updates.
  - Detail level: [N/A] (pricing mechanism to be specified later).

### b) Frequency of use
- Job records: created per submission; read/updated at each scheduling/dispatch/execution event; finalized at completion.
- Scheduling parameters: computed/updated on acceptance and when priorities change; read on each dispatch quantum.
- Cluster status: updated on each schedule/dispatch/completion event; read frequently by schedulers and for status views.
- Execution host and queues: read on each placement decision; updated when jobs are enqueued/dequeued.
- User records: read on each authenticated request; updated infrequently (e.g., credit/accounting updates).
- Accounting/usage history: appended on job completion; read on user/admin reporting.
- Cost structure/pricing: read on user cost queries and acceptance decisions; updated infrequently by administrator.

### c) Accessing capabilities
- Cluster users
  - Create jobs; read status of own jobs; cancel own jobs; read own credit balance and usage history; query current cost per unit time.
- Cluster administrators
  - Read status of all jobs and all nodes; cancel/suspend/resume any job; alter cost structure and scheduling policy; read cluster load and usage history.
- Libra/SGE system components
  - Full read/write to operational state required for scheduling, dispatching, execution, and cluster status updates.

### d) Data entities and relationships
- User 1..n submits Job.
- Job 1..1 has SchedulingParameters (after acceptance).
- Job n..1 is placed in Queue.
- Queue n..1 belongs to ExecutionHost.
- ExecutionHost 1..n exposes Queue.
- ClusterStatus aggregates time-varying metrics per ExecutionHost and Queue.
- AccountingRecord n..1 references Job and n..1 references User.
- CostPolicy is referenced when evaluating acceptance and charging for a Job. Details: [N/A].

### e) Integrity constraints
- Identifiers must be unique: UserId, JobId, ExecutionHostId, QueueId.
- Referential integrity
  - A Job’s assigned Queue must belong to an existing ExecutionHost.
  - A Job with status “accepted/scheduled/running/completed” must reference existing SchedulingParameters (except prior to acceptance).
  - AccountingRecord must reference an existing Job and User.
- Parameter immutability and change control
  - Budget (maximum cost) and deadline are not normally changeable after submission; only administrator may authorize changes; delayed (later) deadlines may be permitted as specified. Exact policy details: [N/A].
- Charging constraint
  - Cost charged for a Job must not exceed the user-submitted maximum cost.
- Compatibility constraints
  - Job.system type must be compatible with target ExecutionHost (cluster is homogeneous Linux).
  - Job.type must match Queue.type (sequential vs embarrassingly parallel).
- Scheduling completeness
  - Accepted Job must have a computable schedule (tickets/stride/pass) prior to dispatch.
- Data validity
  - Execution time estimate must be present for acceptance evaluation; accuracy assumptions per SRS. Additional validation rules: [N/A].

### f) Security
- Privacy
  - Users may access only their own job status, credit balance, and usage history.
- Administrative control
  - Only administrators may alter scheduling policy, cost structure, and manage any job.
- Enforcement
  - Access control enforced through SGE/Linux authentication and role-based authorization. Mechanisms beyond role definitions: [N/A].
- Data at rest/in transit protections: [N/A].

### g) Data retention requirements
- Operational state (cluster status, in-queue/running jobs): retained for the lifetime of the job and for active scheduling; historical retention of these snapshots: [N/A].
- Completed jobs and accounting/usage history: retained for user/admin reporting and auditing. Retention duration and archival policy: [N/A].
- Administrative configuration (cost structure, scheduling policy): retained until changed; versioning/audit trail: [N/A].

## 3.6 Design constraints

The system design is constrained by the following external standards, platform dependencies, and project limitations:

- Parent platform and interfaces
  - Must operate as a sub-component of Sun Grid Engine (SGE) version 5.3 and use SGE’s APIs for CPU, memory, swap, and network interfaces.
  - Must utilize SGE’s communications architecture; no unique communications interfaces beyond SGE.
  - No modifications to the Linux kernel are permitted.

- Operating environment and workload
  - Must run on a Linux-based, homogeneous cluster.
  - Only sequential and embarrassingly parallel batch jobs are supported.

- Programming language and coding standards
  - All implementation shall be in standard C.
  - Code shall follow the Hungarian Naming Convention.

- Licensing and open-source requirements
  - The software shall be released under the GNU General Public License (GPL) and remain open-source.
  - Documentation shall comply with GPL requirements; online help is provided as Linux man pages.
  - No purchased components shall be used.

- External libraries and tools
  - For embarrassingly parallel jobs, PVM and MPI libraries shall be used.

- Scheduling/model constraints
  - Resource allocation must follow a market-based, bid-based proportional resource-sharing model.
  - Enforcement shall use proportional stride scheduling.
  - Exhaustive searches over all job combinations are disallowed; heuristics must be used.
  - Job migration for reducing resource fragmentation is not supported.

- User interface constraints
  - Interfaces are limited to the Linux command line and/or the SGE interface; a GUI is out of scope for the initial implementation.

- Project and testing limitations
  - Current hardware availability limits testing to a small cluster; a simulation tool may be required if a suitable free tool is not available.

## 3.7 Software system attributes

### Reliability
- Maximum bug rate: not more than 1 bug/KLOC.
- Job migration for defragmentation is not supported.
- [N/A] Additional reliability metrics (e.g., MTBF, fault tolerance mechanisms).

### Availability
- Maximum time to repair after outage: less than 5 minutes (Linux OS reboot).
- No Linux kernel modifications required.
- [N/A] Checkpointing, recovery, and application-level restart mechanisms.

### Security
- Privacy of user job status is enforced.
- Alteration of scheduling criteria or resource allocation requires administrator authority.
- Authentication (user ID and password) is required to view job status and to delete/change jobs.
- Administrative security is required.
- [N/A] Use of specific cryptographic techniques.
- [N/A] Security audit logs or history data requirements.
- [N/A] Module-level segregation for security functions.
- [N/A] Communication restrictions between program areas.
- [N/A] Data integrity checks for critical variables.
- [N/A] Data privacy controls beyond user job status privacy.

### Maintainability
- Code will follow the Hungarian Naming Convention.
- Coding will be done in standard C.
- The scheduler should be configurable.
- The scheduler should be separable from the cluster management system.
- Documentation will follow GNU GPL requirements with man pages for online help.
- [N/A] Explicit modularity requirements, interface stability guarantees, or complexity limits.

### Portability
- Implementation language: standard C (portable language).
- Target environment: Linux with Sun Grid Engine (version 5.3); uses PVM/MPI for embarrassingly parallel jobs.
- No Linux kernel modifications required.
- Functionality can be adapted to other resource types and heterogeneous clusters (outside current scope).
- [N/A] Percentage of host-dependent elements or code.
- [N/A] Required compiler or language subset.
- [N/A] Support for operating systems other than Linux.

## 3.8 Supporting information

This section consolidates supplemental materials and context referenced or implied elsewhere in the SRS.

- a) Sample input/output formats, cost analyses, and user surveys
  - Sample input/output formats: Functional subsections in Requirements (Section 3.1 of the original SRS) enumerate inputs and outputs for each feature (for example, job details, cluster information, scheduling information, and Boolean results). Concrete data formats, schemas, or sample values are not provided. [N/A]
  - Cost analysis studies or user surveys: Not provided. Pricing/costing specifics are deferred (see Apportionment of requirements in the original SRS). [N/A]

- b) Supporting/background information for readers
  - Appendix A — Background Research on:
    - Cluster computing
    - Market-based economic models
    - Cluster scheduling
    - Cluster management software
  - Appendix B — Data Flow Diagrams.
  - Appendix C — Data Dictionary.
  - Definitions (original SRS Section 1.3) and References (original SRS Section 1.4).

- c) Description of the problems to be solved by the software
  - Provide QoS-oriented, economy-driven scheduling for clusters by allocating CPU time according to user utility (budget and deadline) rather than system-centric policies.
  - Enable computational economy for batch jobs on a homogeneous Linux cluster managed by Sun Grid Engine (SGE), focusing on sequential and embarrassingly parallel jobs.
  - Allocate resources proportionally using a bid-based proportional resource-sharing model and enforce allocations using stride scheduling.
  - Operate dynamically (permit reallocation of resources), be scalable and configurable, ensure administrative security, and provide at least basic job accounting.

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

Requirement status of the above supporting items: The original SRS does not explicitly state whether these items are to be considered part of the requirements. [N/A]

## 4.1 Functions

This section defines the verification approaches and methods planned to qualify the software functions specified in 3.1 Functions. Verification will be performed on an SGE-backed testbed of Linux nodes and, where needed, with a simulation tool as noted in the SRS. For each function below, verification addresses: a) validity checks on inputs; b) exact sequence of operations; c) responses to abnormal situations; d) effect of parameters; and e) relationship of outputs to inputs.

General verification methods used across all functions:
- Requirements-to-test trace reviews and code inspections
- Unit tests of Libra modules
- Integration tests with SGE interfaces
- Scenario-based system tests with controlled job mixes and cluster loads
- Deterministic replay via fixed seeds and scripted workloads
- Log analysis of decisions (accept/reject, tickets/stride/pass, host/queue choice)

Submit Job
- Validity checks on inputs: Verify user authentication and presence/format of required job fields via negative and boundary test cases at the SGE submission interface.
- Exact sequence of operations: Confirm the system first checks cluster acceptance state, then verifies user, per described processing.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify that submission is rejected with a boolean outcome when the cluster is closed for submissions or user verification fails.
- Effect of parameters: Verify that submission acceptance depends only on cluster acceptance state and user validity; job parameters are not yet used to accept/reject at this step.
- Relationship of outputs to inputs:
  - Input/output sequences: Submit → check cluster open → check user → boolean results.
  - Formulas for conversion: [N/A]

View Job Status
- Validity checks on inputs: Verify only authenticated users can view their job status.
- Exact sequence of operations: Confirm options are presented, and selected status views are returned.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify unauthorized access is denied and no job data is disclosed.
- Effect of parameters: Verify user identity limits visibility to that user’s jobs; admin identity unlocks global visibility.
- Relationship of outputs to inputs:
  - Input/output sequences: Authenticate → request status → receive corresponding status view.
  - Formulas for conversion: [N/A]

Delete/Change Job
- Validity checks on inputs: Verify only the submitting user or admin can cancel or change permitted parameters.
- Exact sequence of operations: Confirm removal or modification is applied, then scheduling information is refreshed.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify rejection of changes to non-permitted parameters (e.g., cost/deadline), and proper rollback on partial failures.
- Effect of parameters: Verify allowed changes (e.g., output directory, delayed deadline) alter subsequent scheduling decisions as stated.
- Relationship of outputs to inputs:
  - Input/output sequences: Authenticate → request delete/change → apply → scheduler updates cluster info.
  - Formulas for conversion: [N/A]

Initialize Job
- Validity checks on inputs: Verify completeness and type/format of job details received from SGE; confirm presence of SGE job ID.
- Exact sequence of operations: Confirm retrieval of job details then setting of internal state variables before passing to scheduling.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify job initialization is aborted with clear error if required fields are missing or malformed.
- Effect of parameters: Verify internal state accurately reflects all provided job parameters.
- Relationship of outputs to inputs:
  - Input/output sequences: Receive job details → parse → set scheduler state → handoff to scheduling.
  - Formulas for conversion: [N/A]

Accept/Reject Job
- Validity checks on inputs: Verify budget, deadline, and execution time are present and within supported ranges; reject if missing.
- Exact sequence of operations: Confirm priority/share computation precedes feasibility assessment against current cluster status.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify that infeasible jobs produce a reject boolean and a suggested revised deadline or cost.
- Effect of parameters: Verify acceptance decisions vary predictably with budget, deadline, and execution time; higher budgets and later deadlines increase acceptance likelihood.
- Relationship of outputs to inputs:
  - Input/output sequences: Inputs → compute share/priority → assess feasibility → boolean decision + suggestion.
  - Formulas for conversion: [N/A]

Calculate Scheduling Information
- Validity checks on inputs: Verify availability of all jobs’ budget and deadlines on the execution host prior to ticket allocation.
- Exact sequence of operations: Confirm ticket allocation precedes stride and pass computation.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify computation aborts cleanly if any required parameter is missing.
- Effect of parameters: Verify tickets vary proportionally with user-centric priorities derived from budget and deadline relationships.
- Relationship of outputs to inputs:
  - Input/output sequences: Job set + parameters → tickets → stride → pass.
  - Formulas for conversion: Verify stride = global_stride_constant / tickets and initial pass = stride using known numeric cases.

Determine Execution Host
- Validity checks on inputs: Verify cluster load, node status, remaining time of pending jobs, and available memory are current and consistent.
- Exact sequence of operations: Confirm hosts are sorted by ascending load, then a host is selected, then a queue is chosen based on job type and parameters.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify selection is retried or deferred if the least-loaded host lacks the required resources (e.g., memory).
- Effect of parameters: Verify sequential versus embarrassingly parallel job type influences queue selection; budget/deadline influence host choice as specified.
- Relationship of outputs to inputs:
  - Input/output sequences: Cluster state + job parameters → sort hosts → select host → select queue.
  - Formulas for conversion: [N/A]

Dispatch Job
- Validity checks on inputs: Verify the chosen host and queue exist and are available at dispatch time.
- Exact sequence of operations: Confirm the dispatcher can delay sending the job to allow higher-urgency jobs to proceed, then enqueues the job.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify dispatch defers or resubmits on transient enqueue failure without duplicating the job.
- Effect of parameters: Verify urgency (e.g., deadline) can influence dispatch timing consistent with the description.
- Relationship of outputs to inputs:
  - Input/output sequences: Ready-to-dispatch job → possible delay → enqueue on chosen host/queue.
  - Formulas for conversion: [N/A]

Update Cluster Status
- Validity checks on inputs: Verify job identity, host, and queue are valid before updating.
- Exact sequence of operations: Confirm resource reservation occurs before queue status update, and that master host state is updated afterward.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify idempotent updates and no stale state on partial failures; reattempt update if needed.
- Effect of parameters: Verify updates reflect actual reserved resources for the job.
- Relationship of outputs to inputs:
  - Input/output sequences: Reserve resources → update queue → propagate to master store; no direct external output.
  - Formulas for conversion: [N/A]

Execute Job
- Validity checks on inputs: Verify each scheduled job has tickets, stride, and pass computed before execution.
- Exact sequence of operations: Confirm the loop repeatedly selects the job with minimum pass, assigns a quantum, and advances pass by stride; break ties FIFO; stop when no jobs remain.
- Responses to abnormal situations:
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults and failures: [N/A]
  - Error handling and recovery: Verify scheduler continues operating if a job completes or is removed unexpectedly; cluster information is updated.
- Effect of parameters: Verify quantum allocation proportions reflect ticket allocations; verify changing budget/deadline (if permitted via admin policy) alters ticket distribution and execution order accordingly.
- Relationship of outputs to inputs:
  - Input/output sequences: Ready jobs + scheduling info → repeated select/execute/advance → updated cluster state.
  - Formulas for conversion: Verify pass_next = pass_current + stride; verify observed CPU share closely matches tickets-based proportions over time.

Notes
- Where [N/A] appears, the original SRS does not specify behavior; verification cannot be defined beyond basic negative testing without added requirements.
- All verification dependent on SGE interfaces will be conducted with SGE 5.3 as specified.

## 4.2 Performance requirements

This section defines the verification approaches and methods to qualify the software against the Performance requirements in Section 3.2.

- Verification of 3.2.1 Response time (maximum 1 minute for job submission)
  - Method:
    - End-to-end timed tests of the submission path using the SGE interface and command line under both normal and peak cluster load.
    - Instrumentation to capture timestamps from user submit request to scheduler acknowledgement (or actionable response).
  - Workloads:
    - Normal load: representative mix of sequential and embarrassingly parallel jobs with typical sizes.
    - Peak load: stress conditions with high queue depth and saturated execution hosts.
  - Measurements:
    - Submission response time per request.
  - Pass/fail criteria:
    - For all tested submissions, response time shall be less than or equal to 60 seconds.

- Verification of 3.2.2 Capacity (no intrinsic upper limit in the scheduler; limited only by node capacity to fulfill deadlines)
  - Method:
    - Static analysis and code/configuration inspection to confirm absence of hard-coded limits on number of jobs/queues within the Libra scheduler (beyond limits imposed by SGE/OS).
    - Stress tests that enqueue progressively larger numbers of jobs until rejections occur due solely to infeasible deadlines or limits enforced by SGE/OS/environment.
  - Workloads:
    - Increasing queue sizes with varied deadlines and budgets; include cases where node capacity is known to be insufficient to meet some deadlines.
  - Measurements:
    - Reasons for any job rejection; observed upper bound before rejection; evidence of any scheduler-internal limit or failure mode.
  - Pass/fail criteria:
    - No rejections attributable to intrinsic limits within Libra.
    - When rejections occur, they are attributable to deadline infeasibility or external platform limits (e.g., SGE/OS constraints).

- Verification of 3.2.3 Deadline sensitivity (complete all accepted jobs within a 10% error allowance, assuming accurate submitted statistics)
  - Preconditions:
    - Test jobs include accurate execution-time estimates consistent with the assumption in the requirement.
  - Method:
    - Controlled workload execution with known-duration jobs and specified deadlines and budgets; run under normal and peak load.
    - Compare each accepted job’s actual completion time against its stated deadline.
  - Measurements:
    - For each accepted job: completion time, stated deadline, and the ratio completion_time/deadline.
  - Pass/fail criteria:
    - All accepted jobs complete within the stated deadline plus a 10% allowance (i.e., completion_time ≤ 1.10 × deadline).

- Verification of 3.2.4 Cost sensitivity (charged cost shall not exceed the user-submitted maximum cost)
  - Method:
    - Unit tests of pricing/charging functions with boundary budgets.
    - Integration tests across scheduling scenarios (dynamic reprioritization, varying load, different queues) to validate final charge computation at job completion.
    - Ledger/log inspection to reconcile computed charges with user-submitted maximum cost.
  - Measurements:
    - For each job: user-submitted maximum cost, computed total charge, and any interim cost accruals.
  - Pass/fail criteria:
    - For every job, the computed total charge is less than or equal to the user-submitted maximum cost; jobs that cannot be scheduled without exceeding the budget are rejected prior to execution.

- Evidence and artifacts produced (all items retained in the verification package)
  - Test plans and procedures for each performance requirement item.
  - Automated test logs with timestamps, workload descriptors, and results.
  - Configuration baselines of SGE, Libra, and OS for reproducibility.
  - Analysis reports demonstrating pass/fail determinations for each requirement.

- Test environment considerations
  - Primary execution on the available Linux cluster integrated with SGE as described in the SRS; where larger-scale validation is needed, a simulation tool may be used per project constraints. Tool selection/details [N/A].

## 4.3 Usability requirements

This section verifies usability aspects implied by the original SRS (primarily user interfaces and documentation). Where explicit usability requirements (effectiveness, efficiency, satisfaction, avoidance of harm) are not specified in the SRS, the corresponding verification item is marked [N/A].

- Verification of cluster user interface availability and basic task effectiveness
  - Basis in requirements: 3.8.1.1 Cluster User Interface; 2.6 Apportionment of requirements (CLI/SGE only at this stage)
  - Method: task-based functional demonstration on Linux command prompt and/or SGE interface using a standard user account
  - Tasks to verify:
    - Submit jobs with deadline, cost, and execution time
    - Query current cost per unit time for submitting new jobs
    - Monitor status of submitted jobs
    - Cancel user’s own jobs
    - Check user credit balance
    - Check user usage history
  - Evidence: execution transcripts and observed system responses confirming each task completes using the provided interfaces

- Verification of cluster administrator interface availability and basic task effectiveness
  - Basis in requirements: 3.8.1.2 Cluster Administrator Interface; 2.6 Apportionment of requirements
  - Method: task-based functional demonstration on Linux command prompt and/or SGE interface using an administrator account
  - Tasks to verify:
    - Check status of each node
    - Review usage pattern history of the cluster
    - Check status of all submitted jobs
    - Check load on each node
    - Alter cost structure
    - Alter scheduling policy
    - Cancel, suspend, and resume any job
  - Evidence: execution transcripts and observed system responses confirming each task completes using the provided interfaces

- Verification of role-based access in user interactions related to usability
  - Basis in requirements: 3.1.2 View Job Status (user authentication); 3.8.1 User Interfaces (distinct user/admin roles); 3.2.4 Security Considerations (privacy of user job status)
  - Method: authorization tests for representative commands and views
  - Checks:
    - Only the appropriate user can view the status of their own jobs
    - Non-administrator users cannot invoke administrator-only commands
  - Evidence: attempted access logs and system responses showing correct enforcement

- Verification of online help and documentation accessibility
  - Basis in requirements: 3.6 Online User Documentation and Help System Requirements
  - Method: documentation inspection and invocation of man pages for user and administrator commands
  - Checks:
    - Man pages exist and are accessible via Linux for each exposed command
    - Man pages describe purpose, parameters (e.g., deadline, cost, execution time), usage, and examples where applicable
  - Evidence: captured man page outputs and index listings

- Verification of interface modality constraints
  - Basis in requirements: 2.6 Apportionment of requirements (CLI/SGE interface; GUI optional later)
  - Method: environment setup and end-to-end task walkthroughs without any GUI
  - Checks:
    - All required user and administrator tasks can be performed via CLI/SGE interface alone
  - Evidence: task execution records demonstrating no dependency on a GUI

- Verification of usability effectiveness metrics
  - Basis in requirements: [N/A]
  - Method: [N/A]
  - Criteria: [N/A]

- Verification of usability efficiency metrics (e.g., time-on-task beyond performance response times)
  - Basis in requirements: [N/A]
  - Method: [N/A]
  - Criteria: [N/A]

- Verification of user satisfaction criteria
  - Basis in requirements: [N/A]
  - Method: [N/A]
  - Criteria: [N/A]

- Verification of avoidance of harm arising from use (usability-related)
  - Basis in requirements: [N/A]
  - Method: [N/A]
  - Criteria: [N/A]

## 4.5 Logical database requirements

This section defines the verification approaches and methods to qualify that any logical data store (e.g., the “central information store on the master host” referenced in the SRS) supports the logical database requirements implied by the system functions in Section 3.1.

- a) Types of information used by various functions
  - Items to be verified (from the SRS functions):
    - User information: user name, authentication ID.
    - Job details: Job ID (from SGE), job type (sequential/embarrassingly parallel), standalone execution time, executable and input locations, system type, budget, deadline, output location.
    - Cluster information: CPU load, node status, remaining time of pending jobs, available memory, queue status.
    - Scheduling information: tickets, stride, pass.
    - Accounting/usage: usage history, credit balance, cost charged/structure, pricing and scheduling policy parameters.
  - Verification methods:
    - Requirements-to-data traceability review mapping each function (Submit Job, Initialize Job, Accept/Reject Job, Calculate Scheduling Information, Determine Execution Host, Dispatch Job, Update Cluster Status, Execute Job, View Job Status, Delete/Change Job) to the data it creates/reads/updates.
    - Static schema/interface inspection to confirm presence and types of the above fields.
    - Functional tests: execute each function and verify creation/update/read of the expected data elements via queries or logs.

- b) Frequency of use
  - Expected patterns (from SRS behavior):
    - High-frequency writes on job scheduling/completion (Update Cluster Status, Execute Job loop).
    - Frequent reads for View Job Status by users; broader reads by administrators; writes on Submit Job and Delete/Change Job.
  - Verification methods:
    - Workload simulation with representative and peak mixes of job submissions, status polling, and completions; verify data consistency and absence of loss under continuous Execute Job scheduling cycles.
    - Performance observation that data operations under submission do not violate the 1-minute response-time requirement for Submit Job.

- c) Accessing capabilities
  - Access modes and roles:
    - User commands: submit, monitor status, cancel own jobs, check credit balance, check usage history.
    - Administrator commands: view all jobs and nodes, alter cost and scheduling policy, cancel/suspend/resume any job.
  - Verification methods:
    - Role-based access tests covering all commands and data scopes (user sees only own jobs and accounting; admin sees all).
    - Negative tests attempting unauthorized reads/updates (e.g., user altering cost/scheduling policy, viewing others’ job status).
    - CLI/SGE interface tests to ensure required queries and updates are supported.

- d) Data entities and their relationships
  - Entities inferred:
    - User, Job, Node (Execution Host), Queue, SchedulingInfo, ClusterStatus, AccountingRecord, PolicyConfig (cost/scheduling).
  - Relationships inferred:
    - User submits Job; Job assigned to exactly one Queue on one Node at a time; Job has one current SchedulingInfo; ClusterStatus aggregates per Node/Queue; AccountingRecord links to Job and User; PolicyConfig is global and admin-managed.
  - Verification methods:
    - Model/schema review to ensure entities and mandatory relationships exist with appropriate keys and foreign keys.
    - Referential integrity tests: reject orphans (e.g., SchedulingInfo without Job, Job referencing non-existent User/Queue/Node).
    - State-transition tests: ensure a Job cannot be simultaneously assigned to multiple Nodes/Queues.

- e) Integrity constraints
  - Constraints to verify:
    - Uniqueness of Job ID (from SGE).
    - Non-null/valid ranges for budget, deadline, execution time; budget/deadline generally immutable post-submission except explicitly permitted cases (e.g., delayed deadline) per Delete/Change Job.
    - Single active host/queue assignment per Job at any time.
    - Accounting rule: cost charged must not exceed user-specified maximum.
    - Data needed to assess deadline adherence (timestamps, completion times) available to support the 10% allowance check.
  - Verification methods:
    - Schema constraint inspection (primary/unique keys, not-null, check constraints).
    - Negative tests attempting invalid inserts/updates (e.g., duplicate Job IDs, negative budgets, changing budget/deadline as a non-admin).
    - Concurrency tests on Update Cluster Status to ensure atomicity and consistency of Job and ClusterStatus updates.
    - Accounting reconciliation tests: submit jobs with capped budgets and verify charged cost ≤ submitted maximum.

- f) Security
  - Security expectations:
    - Privacy of user job status; only owners and administrators can view specific job details.
    - Only administrators can alter scheduling criteria or resource allocation.
    - Authentication required for viewing, deleting, or changing jobs.
  - Verification methods:
    - Authentication and authorization tests for all data-accessing commands and interfaces.
    - Auditability checks: administrative actions that alter cost or scheduling policy are logged with user, timestamp, and change details.
    - Attempted privilege escalation tests to ensure protections around scheduling and cost structures.

- g) Data retention requirements
  - Retention period and archival requirements: [N/A]
  - Verification methods:
    - [N/A]

## 4.6 Design constraints

This section specifies how compliance with the design constraints will be verified, paralleling the corresponding constraints defined in the Requirements.

- Parent component: Sun Grid Engine (SGE)
  - Verification methods:
    - Architecture and code inspection to confirm Libra is implemented and invoked as an SGE sub-component and uses SGE interfaces only.
    - Build/packaging review to confirm dependency on SGE (e.g., headers/libraries) and absence of standalone execution mode.
    - Integration tests on a Linux cluster with SGE 5.3 to verify job submission, dispatch, and communication flow occur exclusively through SGE.
  - Evidence: reviewed design and code, build manifests, integration test reports.

- Software language: Standard C
  - Verification methods:
    - Source tree audit to confirm implementation files are C (.c/.h) and absence of other implementation languages.
    - Compiler conformance checks using a C compiler and strict standards options; build logs reviewed for non-C usage.
    - Static analysis to detect non-C constructs or foreign language artifacts.
  - Evidence: source inventory, compiler/build logs, static analysis reports.

- Scheduling constraints: Heuristic approach; no exhaustive search over job combinations
  - Verification methods:
    - Algorithm/design review to confirm heuristic scheduling strategies and absence of exhaustive combinatorial enumeration.
    - Complexity assessment to demonstrate expected polynomial-time behavior of scheduling decisions.
    - Performance tests with increasing numbers of jobs/hosts to verify scheduling time growth is consistent with a heuristic approach and not exponential.
  - Evidence: reviewed algorithms and complexity notes, performance test results, code inspection checklists.

- [N/A] External standards or regulatory constraints beyond those stated above

## 4.7 Software system attributes

This section describes the verification approaches to qualify the software against the software system attributes implied or stated in the requirements.

- Reliability
  - Maximum bug rate (≤ 1 bug/KLOC) [Req. 3.2.2]
    - Method: At delivery, compute KLOC using a standard counting tool and tally confirmed defects recorded during verification. Accept only if total confirmed defects at delivery do not exceed KLOC.
  - Maximum time to repair (< 5 minutes) [Req. 3.2.3]
    - Method: Conduct controlled outage/restart tests on the deployed cluster; time the full restart until the system is available for submissions. Accept only if measured time is under five minutes.
  - No job migration for defragmentation [Req. 3.2.1]
    - Method: Execute scenarios that would ordinarily trigger migration (e.g., queue rebalancing, host load changes) and instrument SGE/Libra to confirm no Libra-initiated job migration occurs.

- Availability
  - Defined availability target
    - [N/A]
  - Checkpoint/recovery/restart mechanisms
    - Restart verification covered by the Maximum time to repair test above. No checkpoint/restart requirements are specified. [N/A for checkpoint/recovery specifics]

- Security
  - Privacy of user job status; admin-only control over execution/scheduling changes [Req. 3.2.4; 3.8.1.1; 3.8.1.2; 3.1.2; 3.1.3]
    - Method: Multi-user access control tests verifying:
      - A user can view only their own job status; attempts to view others’ jobs are denied.
      - Non-admin users cannot alter scheduling criteria or resource allocations; administrators can perform these actions.
      - Authentication is enforced for viewing and deleting/changing jobs (User Id and Password required).
  - Cryptographic techniques
    - [N/A]
  - Logs/history datasets
    - Method: Confirm presence of basic job accounting and usage history accessible via user/admin interfaces as specified (submission history, usage history, credit balance). Validate that accounting records are produced for executed jobs.
  - Module function separation
    - [N/A]
  - Restricted communications between areas
    - [N/A]
  - Data integrity checks for critical variables
    - [N/A]
  - Assured data privacy
    - Method: Validate that job status data exposure is limited per user identity as above; verify administrator oversight is required for any data or scheduling changes.

- Maintainability
  - Naming convention: Hungarian [Req. 3.4.1]
    - Method: Static code analysis and code reviews using a checklist to verify identifiers conform to the stated convention.
  - Coding standards under GNU GPL requirement [Req. 3.4.2; 3.9]
    - Method: Repository/license audit confirming GPL licensing of source, presence of appropriate license headers and inclusion of license texts. [Note: No specific code-style standard beyond naming is specified.]
  - Modularity/complexity limits
    - [N/A]

- Portability
  - Use of a proven portable language: Standard C [Req. 3.5.2]
    - Method: Build with a standards-compliant C compiler; verify absence of non-standard extensions or compiler-specific pragmas required for correct build.
  - Operating system: Linux; no kernel modifications required [Req. 2.1; 3.8.3]
    - Method: System tests on a Linux-based cluster with SGE 5.3, PVM/MPI installed; confirm installation and operation require no kernel patches or modifications.
  - Percentage of host-dependent elements/code
    - [N/A]
  - Specific compiler or language subset
    - [N/A]

## 5.1 Assumptions and dependencies

- The Sun Grid Engine (SGE) cluster management system (version 5.3) is available and operational, including its queuing, resource management, and communications modules, and its modules (e.g., process migration) interoperate correctly with Libra’s scheduling policies.
- Libra operates as an add-on to SGE on a homogeneous Linux cluster; Linux is available on all nodes, and no Linux kernel modifications are required.
- The SGE user and administrator interfaces (or the Linux command line) are available and can be adapted to accept additional submission parameters (e.g., budget, deadline, execution time).
- Users submit required job parameters (including budget and deadline) and provide reasonably accurate estimates of standalone execution time.
- A basic job accounting and payment module is available; detailed pricing/costing policies will be defined later and are assumed not to alter scheduling policies, which assume a given budget and cost.
- Only sequential and embarrassingly parallel batch jobs are submitted; inter-user bargaining or market negotiation between users is not provided.
- PVM and MPI libraries are available on the cluster for executing embarrassingly parallel jobs.
- SGE provides Libra with necessary system/hardware metrics and controls (e.g., CPU load, memory usage, swap, network) and dispatch capabilities to execution hosts and queues.
- Authentication mechanisms (user ID and password) are available to restrict access to job status and job modification actions.

## 5.2 Acronyms and abbreviations

- SRS — Software Requirements Specification
- QoS — Quality of Service
- SGE — Sun Grid Engine (cluster management system)
- GUI — Graphical User Interface
- CPU — Central Processing Unit
- RAM — Random Access Memory
- Mb — Megabyte (as used in the document’s hardware description)
- ID — Identifier (e.g., authentication ID)
- FIFO — First-In, First-Out
- KLOC — Thousand Lines Of Code
- GPL — GNU General Public License
- GNU — GNU’s Not Unix
- PVM — Parallel Virtual Machine
- MPI — Message Passing Interface
- HPC — High Performance Computing
- PDPTA — Parallel and Distributed Processing Techniques and Applications (conference)
- HCW — Heterogeneous Computing Workshop
- IPDPS — International Parallel and Distributed Processing Symposium
- IEEE — Institute of Electrical and Electronics Engineers
- IEEE CS — IEEE Computer Society