## 1.1 Purpose

The purpose of Libra is to provide an economy-driven, QoS-oriented cluster scheduler—integrated as an add-on to the Sun Grid Engine (SGE)—that allocates CPU time based on user utility. Libra schedules sequential and embarrassingly parallel batch jobs on a homogeneous Linux cluster by prioritizing user-specified budget and deadline over system-centric policies, using a bid-based proportional resource-sharing model enforced via stride scheduling to maximize user satisfaction.

## 1.2 Scope

This specification defines Libra, an Economy-Driven Cluster Scheduler delivered as an add-on module to the Sun Grid Engine (SGE) cluster management system running on Linux.

- Product to be produced:
  - Libra Scheduler (add-on to SGE).

- What the product will do:
  - Provide market-based, QoS-driven scheduling of batch jobs by considering user-specified budget and deadline.
  - Determine job accept/reject decisions based on feasibility against user constraints and current cluster load.
  - Allocate CPU time proportionally according to user-centric priorities (budget/deadline), enforcing allocations via proportional (stride) scheduling.
  - Select execution hosts and queues within the cluster and dispatch accepted jobs.
  - Maintain basic job accounting information to support scheduling.

- Application, benefits, objectives, and goals:
  - Application: High-performance cluster computing for sequential and embarrassingly parallel batch jobs on a homogeneous Linux cluster managed by SGE.
  - Benefits: Maximizes user utility by honoring QoS constraints; supports dynamic, responsive reallocation under varying load; enables differentiated service levels for different users.
  - Objectives and goals:
    - Provide QoS-oriented computational economy in cluster computing.
    - Optimize resource utilization within user-imposed budget and deadline constraints, prioritizing user satisfaction over raw system throughput.
    - Operate as a configurable, scalable scheduling component separable from (but integrated with) SGE.

- Scope boundaries and non-goals:
  - No kernel modifications are required.
  - No user-to-user bargaining or market negotiation (unlike grid systems such as Nimrod/G).
  - Out of scope for this version: tightly coupled parallel jobs (only sequential and embarrassingly parallel are supported); detailed pricing policy (to be specified later).
  - Designed for homogeneous Linux clusters; functionality can be adapted to other resources and heterogeneous clusters in future work.

This scope is consistent with the stated role of Libra as an SGE sub-component that delivers market-based, QoS-driven scheduling for batch workloads on Linux clusters.

### 1.3.1 Product perspective

Libra is an add-on scheduler that operates as an element of the Sun Grid Engine (SGE) cluster management system on a Linux-based, homogeneous cluster. SGE receives user job submissions, invokes Libra to make economy/QoS-driven scheduling decisions, and then dispatches jobs to execution hosts according to Libra’s host/queue selection and scheduling metadata. Libra enforces proportional resource allocations at execution hosts using stride scheduling. No Linux kernel modifications are required. For embarrassingly parallel jobs, the cluster uses MPI/PVM libraries under SGE; Libra’s role remains scheduling and placement, not inter-process communication.

Major elements and interconnections (textual block diagram):
- Users and administrators interact via Linux/SGE command-line tools.
- SGE (qmaster/queue manager/resource manager/dispatcher) accepts jobs and queries Libra.
- Libra computes accept/reject, host/queue selection, and scheduling metadata (tickets/stride/pass), and updates cluster status.
- SGE dispatches jobs to execution hosts and coordinates execution.
- Execution hosts run jobs (sequential or embarrassingly parallel) on Linux; MPI/PVM may be used by applications.
- SGE provides hardware and communications interfaces; Libra uses these via SGE.

System interfaces:
- Interface to SGE job submission/queueing:
  - Functionality: Receive job descriptors from SGE; compute accept/reject based on budget/deadline/execution time and cluster state.
  - Interface description: Exchange of job metadata (job ID, type, execution time, budget, deadline, system type, I/O locations) and cluster status (CPU load, node status, pending time). Message/content formats are those provided by SGE 5.3 APIs [N/A].
- Interface to SGE resource manager/dispatcher:
  - Functionality: Provide selected execution host and queue; provide scheduling metadata (tickets, stride, pass) to enforce proportional sharing.
  - Interface description: Host/queue identifiers and scheduling attributes passed through SGE mechanisms [N/A].
- Interface to SGE cluster information store:
  - Functionality: Update cluster/queue/node status when jobs are scheduled, dispatched, or complete.
  - Interface description: Status updates for CPU load, remaining times, available memory via SGE facilities [N/A].

User interfaces:
- Logical characteristics:
  - Two user types: cluster user and cluster administrator.
  - Access via Linux command line and/or SGE CLI.
  - User actions: submit jobs with deadline, cost, execution time; query current cost per unit time; monitor status; cancel own jobs; check credit balance and usage history.
  - Administrator actions (in addition to user actions): view node/cluster status and usage patterns; view all jobs; inspect per-node load; alter cost structure; alter scheduling policy; cancel/suspend/resume any job.
  - Style guide and detailed UI conventions: [N/A].

Hardware interfaces:
- Libra uses SGE’s hardware interfaces; no direct device control and no kernel changes.
- Supported device classes (via SGE): CPU usage, memory usage, swap file creation, network communication.
- Configuration characteristics (ports/instruction sets/devices/protocol specifics): [N/A].
- Cluster profile: homogeneous Linux nodes; available memory considered during host selection. Example deployment used Pentium-III nodes with 128 MB RAM (project test environment).

Software interfaces:
- Sun Grid Engine
  - Name: Sun Grid Engine; Mnemonic: SGE; Specification number: [N/A]; Version: 5.3; Source: Sun Microsystems.
  - Purpose: Parent cluster/queue manager; Libra is a sub-component/add-on that supplies QoS/economy-driven scheduling decisions.
  - Interface: Job descriptors, host/queue selection, scheduling metadata (tickets/stride/pass), and status updates via SGE 5.3 documented APIs [N/A].
- Operating system
  - Name: Linux; Mnemonic: [N/A]; Specification number: [N/A]; Version: [N/A]; Source: Open-source.
  - Purpose: Execution environment for SGE and jobs; no kernel modifications required.
  - Interface: Standard process execution and resource accounting via SGE; interface details per Linux/SGE documentation [N/A].
- MPI
  - Name: Message Passing Interface; Mnemonic: MPI; Specification number: [N/A]; Version: [N/A]; Source: University of Chicago and Mississippi State University.
  - Purpose: Library used by applications for embarrassingly parallel jobs; Libra does not call MPI directly but schedules such jobs.
  - Interface: Application-level MPI usage; interaction with Libra is indirect through SGE job descriptors [N/A].
- PVM
  - Name: Parallel Virtual Machine; Mnemonic: PVM; Specification number: [N/A]; Version: [N/A]; Source: University of Tennessee, Oak Ridge National Laboratory, and Emory University.
  - Purpose: Library used by applications for embarrassingly parallel jobs; Libra schedules these jobs via SGE.
  - Interface: Application-level PVM usage; interaction with Libra is indirect through SGE job descriptors [N/A].

Communications interfaces:
- Libra utilizes SGE’s communications architecture for intra-cluster coordination.
- Network protocols and transport specifics are as provided by SGE; additional requirements: [N/A].

Memory constraints:
- No special memory constraints imposed by Libra beyond those managed by SGE and execution hosts.
- Numeric limits/footprint requirements: [N/A].

Operations:
- Modes: User-initiated operations (submit, query, cancel) via CLI; continuous unattended scheduling/execution by Libra/SGE.
- Interactive vs unattended periods: Submissions/queries are interactive; scheduling, dispatch, and enforcement run continuously unattended.
- Data processing support: Basic job accounting to aid scheduling; administrative security to control job execution criteria.
- Backup and recovery: On outage, recovery relies on OS reboot; expected restart time less than five minutes.
- Special operations: No job migration for fragmentation reduction.

Site adaptation requirements:
- Site-specific configuration via SGE and Libra:
  - Cluster host lists, queues, resource limits, and load reporting (SGE).
  - Scheduling policy parameters (e.g., proportional sharing policy, stride constant), and cost/pricing structure adjusted by administrator.
- Initialization data and safety/limit values specific to site: [N/A].
- Adaptation to heterogeneous clusters or non-CPU resources is conceptually possible but out of current scope.

Interfaces with services:
- Interactions with SaaS/cloud services: [N/A].

### 1.3.2 Product functions

Libra provides QoS-driven, market-based scheduling for batch jobs on a Linux cluster managed by Sun Grid Engine (SGE). It prioritizes user utility (budget and deadline) over purely system-centric goals and supports sequential and embarrassingly parallel jobs.

Major function areas:

- User job lifecycle
  - Submit job with parameters: executable and input locations, output location, system type, max run time, job type (sequential or embarrassingly parallel), budget, and deadline.
  - Validate submission context: verify user identity and whether the cluster is currently accepting submissions.
  - Initialize job by retrieving and parsing submitted details and recording state needed for scheduling.
  - Admission control (accept/reject) based on feasibility against budget/deadline, estimated execution time, and current cluster load; propose alternative deadline or cost if needed.
  - View job status with authenticated access to progress and options.
  - Cancel job and, in limited cases, change non-critical parameters (e.g., output directory, later deadline).

- Scheduling and resource allocation
  - Compute economic priority (tickets) from user budget and deadline in relation to competing jobs (bid-based proportional resource-sharing model).
  - Enforce proportional CPU shares using stride scheduling (tickets, stride, pass) to meet QoS constraints.
  - Dynamically adjust resource limits, priorities, privileges, and execution order to reflect changing conditions and urgent jobs.

- Host and queue selection
  - Select execution host and queue based on load (favor least loaded hosts), job type, available memory, and feasibility with deadlines and budgets.
  - Provide basic load balancing through host sorting by current load.

- Dispatch and execution control
  - Dispatch jobs to the chosen host/queue at the appropriate time, allowing earlier execution of more urgent jobs when needed.
  - Execute jobs with time-slicing determined by stride scheduling (pick minimum pass, allocate quantum, advance pass).
  - Support execution of embarrassingly parallel workloads via the cluster’s MPI/PVM environment.

- Cluster state management and monitoring
  - Reserve resources and update execution host and central master state upon job start and completion.
  - Maintain and expose cluster metrics: CPU load, node status, queue lengths, remaining times of pending jobs, and available memory.

- Administrative operations
  - Monitor node status, load, all submitted jobs, and usage patterns.
  - Adjust cost structure and scheduling policy.
  - Cancel, suspend, and resume any job (administrator authority).

- Accounting and pricing support
  - Provide basic job accounting and payment support.
  - Enforce cost constraints so that charges never exceed the user’s submitted maximum.
  - Allow users to query current cost per unit time, check credit balance, and review usage history.

- Security and access control
  - Authenticate users and protect privacy of job status.
  - Restrict modification of critical scheduling parameters to authorized administrators.

Functional relationships (textual lifecycle):

1) User submits job → 2) Job initialized → 3) Admission control (accept/reject with possible counter-offer) → 4) Scheduling information computed (tickets/stride/pass) → 5) Execution host and queue selected → 6) Job dispatched → 7) Job executed with proportional time-slicing → 8) Cluster state updated continuously → 9) Job completes; accounting recorded; status available to user/admin.

### 1.3.3 User characteristics

The Libra Scheduler has two intended user groups: cluster users (job submitters) and cluster administrators. Both groups primarily interact via the Linux command line and/or the Sun Grid Engine (SGE) interface; online help is provided as Linux man pages.

- Cluster users (job submitters)
  - Role: Submit, monitor, and manage batch jobs (sequential or embarrassingly parallel) within specified budget and deadline constraints.
  - Educational level: [N/A]
  - Experience: Must understand the nature of their jobs and be able to provide accurate estimates of execution time and resource needs; capable of using the SGE or Linux command-line submission and monitoring tools.
  - Technical expertise: Familiarity with Linux command line or SGE interface; ability to specify job parameters (execution time, resources, system type, input/output locations, budget, deadline) and interpret job status.
  - Disabilities/accessibility: [N/A]

- Cluster administrators
  - Role: Oversee scheduling and cluster usage, configure policies and pricing, monitor nodes and jobs, and control job lifecycle (cancel/suspend/resume).
  - Educational level: [N/A]
  - Experience: Advanced cluster operators; fully qualified in Linux, SGE, and the Libra Scheduler.
  - Technical expertise: Proficient in Linux administration and SGE management; able to alter cost structures and scheduling policies; monitor cluster load and node status; use command-line and SGE administrative interfaces.
  - Disabilities/accessibility: [N/A]

### 1.3.4 Limitations

- a) Regulatory requirements and policies
  - Libra will be released under the GPL and must comply with GNU General Public License requirements.
  - Coding is required “as required by the GNU General Purpose License.”
  - Documentation must meet open-source/GPL requirements.
  - Administrative policies enforce that only administrators can alter scheduling criteria or actual resource allocation.

- b) Hardware limitations
  - Designed for a homogeneous Linux cluster; no Linux kernel modifications are required or permitted.
  - Test environment is limited to four Pentium-III workstations with 128 MB RAM each, which constrains implementation/testing scale and performance analysis.
  - Capacity is ultimately limited by node resources (CPU, memory, available memory per node).

- c) Interfaces to other applications
  - Libra is a sub-component of Sun Grid Engine (SGE) v5.3 and must conform to its interfaces and behaviors.
  - For embarrassingly parallel jobs, PVM and MPI libraries are used and must be available.
  - User/admin interactions occur via Linux CLI and/or SGE interfaces; no standalone GUI is guaranteed in the initial version.

- d) Parallel operation
  - Supports only sequential and embarrassingly parallel batch jobs; does not support tightly coupled parallel jobs with interdependent threads.
  - No user-to-user interaction or bargaining (i.e., no grid-level market negotiation).

- e) Audit functions
  - Only a basic level of job accounting is provided; detailed accounting and payment mechanisms are out of scope.

- f) Control functions
  - Users generally cannot modify critical scheduling parameters (e.g., budget, deadline) after submission; administrators retain override controls.
  - Exhaustive search over all job combinations is not performed; scheduling relies on heuristics.

- g) Higher-order language requirements
  - All implementation is in standard C.
  - Hungarian Naming Convention is required.

- h) Signal handshake protocols
  - No unique communication or handshake protocols are defined by Libra; it utilizes SGE’s communications architecture. Specific protocol details are not specified. [N/A]

- i) Quality requirements (e.g., reliability)
  - Maximum bug rate: 1 bug/KLOC.
  - Maximum time to repair after outage: Linux reboot under 5 minutes.
  - Job migration for the purpose of reducing resource fragmentation is not supported.

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

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

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

- m) Limitations sourced from other systems (including real-time requirements through interfaces)
  - Dependence on SGE modules (e.g., process migration and other mechanisms) is assumed for correct operation.
  - Communications and hardware interfaces are inherited from SGE (CPU usage, memory usage, swap, network).
  - Performance expectations include a maximum job submission response time of 1 minute and completion deadline adherence within a 10% error allowance.

## 1.4 Definitions

- Cluster (Cluster Computing): An integrated collection of connected computers (nodes) presenting a single system image that transparently distributes jobs across nodes for high-performance applications.

- Quality of Service (QoS): Meeting user-specified utility goals; in Libra this is driven primarily by user-provided deadline and budget constraints.

- Computational Economy: A user-centric resource management approach where scheduling decisions prioritize user QoS parameters (e.g., deadline and budget) over system-centric policies (e.g., first-come-first-served).

- Bid-based Proportional Resource-Sharing Model: An economic model allocating resources in proportion to users’ bids (tokens/credits), where effective priority derives from user constraints such as deadline and price; Libra adapts this to compute job shares and schedule proportionally.

- Stride Scheduling: A deterministic proportional-share scheduling algorithm using tickets to represent resource rights; each job’s stride is inversely proportional to its tickets, causing higher-ticket jobs to be scheduled more frequently.

- Tickets (stride scheduling): Abstract resource-share units assigned to a job (based on its budget and deadline relative to competing jobs) that determine its fraction of CPU time.

- Stride (stride scheduling): The scheduling interval for a job, computed as a global stride constant divided by the job’s tickets; a shorter stride implies more frequent scheduling.

- Pass (stride scheduling): A running value used to select the next job to execute; the job with the minimum pass is chosen, and its pass is advanced by its stride after each quantum.

- Process Migration: Moving an executing job from one node to another without restarting it from the beginning.

- Sequential Job: A job that must execute on a single node and cannot be partitioned into independent parts.

- Embarrassingly Parallel Job: A parallel workload decomposable into independent parts that run on separate nodes with minimal inter-process communication.

- Job Accounting: Quantification of system resources consumed by a job (e.g., CPU time, memory) for tracking and policy purposes.

- Homogenous Cluster: A cluster whose nodes share uniform characteristics (e.g., memory, disk, operating system).

- Execution Host: The specific node selected to run a job, including the queue on that node where the job is placed.

# 2 References

## 2.1 Compliance

- GNU General Public License (GPL)
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: [N/A]
  - Source: [N/A]

- Sun Grid Engine (SGE) Documentation, Version 5.3
  - Report number: [N/A]
  - Date: [N/A]
  - Publishing organization: Sun Microsystems, Inc.
  - Source: [N/A]

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

## 2.2 Guidance

- 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 Computer Society Press (IEEE CS Press), USA
  - Source: HPC ASIA’2000 proceedings, China

- 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: The 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000) proceedings, Las Vegas, USA

- An Economy Grid Architecture for Service-Oriented Grid Computing
  - Report number: [N/A]
  - Date: April 2001
  - Publishing organization: IEEE
  - Source: Proceedings of the 10th IEEE International Heterogeneous Computing Workshop (HCW 2001) with IPDPS 2001, San Francisco, California, USA

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

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

## 3.1 Functions

This section defines the fundamental functions of the Libra Scheduler operating with Sun Grid Engine (SGE), including input validity checks, exact operation sequences, responses to abnormal conditions, parameter effects, and the relationship of outputs to inputs. Functions are partitioned into sub-functions for clarity.

System-level sequence of operations
- Submit Job (via SGE interface)
- Initialize Job (Libra)
- Accept/Reject Job (Libra)
- If accepted:
  - Determine Execution Host (Libra)
  - Calculate Scheduling Information (Libra)
  - Dispatch Job (via SGE)
  - Update Cluster Status (Libra)
  - Execute Job (Libra, continuous while jobs exist)
  - Update Cluster Status on completion (Libra)
- At any time: View Job Status (SGE/Libra), Delete/Change Job (SGE/Libra)

3.1.1 Submit Job
- Purpose
  - Allow a user to submit a batch job with QoS parameters (budget and deadline) via SGE.
- Input validity checks
  - Cluster accepting submissions: boolean check provided by SGE.
  - User authentication and authorization: verification of user identity via SGE.
  - Job specification presence: executable location, input data location, system type, maximum execution time, job type (sequential or embarrassingly parallel), budget, deadline. Missing mandatory fields cause rejection at submission or during Accept/Reject Job.
- Exact sequence
  - User invokes submission through SGE or command line.
  - SGE validates cluster submission state and user identity.
  - Job is enqueued in SGE pending Libra processing.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If cluster down, submission deferred until system available; overall system reboot time is less than five minutes.
  - Error handling and recovery: If user verification fails or cluster not accepting submissions, return boolean failure and do not enqueue the job.
- Effect of parameters
  - Budget and deadline are captured for downstream scheduling and acceptance decisions.
  - Execution time estimate is used for feasibility checking.
  - Job type influences queue selection and parallel execution strategy.
- Outputs and I/O relationship
  - Outputs: boolean flags indicating cluster accepting submissions and user verified status.
  - Input/output sequence: user request → SGE checks → boolean outcome → job registered for Libra if checks pass.
  - Formulas: [N/A]

3.1.2 View Job Status
- Purpose
  - Allow user or administrator to view job details and execution progress.
- Input validity checks
  - Authentication via user ID and password to restrict visibility to authorized users.
- Exact sequence
  - User requests status.
  - System verifies identity.
  - System displays available status options and selected details.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If nodes or master are down, latest known status is limited to last update; normal operation resumes after reboot (<5 minutes).
  - Error handling and recovery: If authentication fails, deny access and prompt for credentials.
- Effect of parameters
  - None beyond access control.
- Outputs and I/O relationship
  - Outputs: user view of available job options and current status.
  - Input/output sequence: request with credentials → verify → present status.
  - Formulas: [N/A]

3.1.3 Delete/Change Job
- Purpose
  - Permit cancellation of a job or limited parameter changes (e.g., output directory, delayed deadline under specific circumstances).
- Input validity checks
  - Authentication and authorization of the requesting user or administrator.
  - Change constraints: critical parameters (budget, original deadline) are normally not changeable.
- Exact sequence
  - Receive delete or change request.
  - Verify identity and allowed operation.
  - If permitted, remove job from queue or apply permissible changes.
  - Trigger rescheduling/update of cluster state.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If host unavailable, defer action until communication restored; then apply change and update state.
  - Error handling and recovery: On invalid request or insufficient permissions, reject with reason; on partial failures, maintain consistent state by not applying any changes.
- Effect of parameters
  - Changing deadline to a later time may be permitted and will lower priority in subsequent scheduling.
- Outputs and I/O relationship
  - Outputs: updated cluster information and scheduling decisions (CPU load, node status, queue length, quanta allocation, revised expected finish times).
  - Input/output sequence: request → validation → apply → update cluster → expose updated state.
  - Formulas: [N/A]

3.1.4 Initialize Job
- Purpose
  - Prepare the scheduler by retrieving and setting internal variables for a newly submitted job.
- Input validity checks
  - Verify presence and parseability of job details from submission and SGE-assigned job ID.
- Exact sequence
  - Retrieve job details from SGE.
  - Parse and set internal variables representing job state.
  - Pass parsed parameters to scheduling module.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If retrieval fails due to host issues, retry after system recovery (<5 minutes).
  - Error handling and recovery: On missing or invalid fields, mark job for rejection in Accept/Reject Job.
- Effect of parameters
  - All captured parameters determine feasibility, priority, and host selection in later functions.
- Outputs and I/O relationship
  - Outputs: structured job details (Job ID, Job Type, Standalone Execution Time, Executable/Input Locations, System Type, Budget, Deadline).
  - Input/output sequence: SGE record → parsed internal representation.
  - Formulas: [N/A]

3.1.5 Accept/Reject Job
- Purpose
  - Decide feasibility of meeting the user’s deadline given budget and execution time, considering current cluster load.
- Input validity checks
  - Verify presence of Budget, Deadline, and Execution Time; ensure types and ranges are valid.
- Exact sequence
  - Compute a priority/share for the job based on its constraints relative to current jobs.
  - Estimate ability to finish by the deadline given execution time and pending workload.
  - Accept if feasible; otherwise reject with suggested modifications.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If cluster state is unavailable, defer decision until status available.
  - Error handling and recovery: On infeasible constraints, provide suggested deadline or cost for conditional acceptance.
- Effect of parameters
  - Budget and Deadline strongly influence the computed share and acceptance.
  - Execution Time estimate affects feasibility testing.
- Outputs and I/O relationship
  - Outputs: boolean accepted/rejected; suggested deadline or cost for acceptance.
  - Input/output sequence: job parameters + cluster state → feasibility/priority → decision and suggestions.
  - Formulas: [N/A]

3.1.6 Calculate Scheduling Information
- Purpose
  - Compute per-job scheduling parameters to enforce proportional resource allocation reflecting QoS.
- Input validity checks
  - Presence of Budget and Deadline for the job and for competing jobs on the execution host.
- Exact sequence
  - Allocate tickets to the job based on its Budget and Deadline relative to other jobs on the target host.
  - Compute stride and initial pass.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: Defer calculation if host/job lists are unavailable; recompute when available.
  - Error handling and recovery: On missing comparative data, postpone dispatch until calculation succeeds.
- Effect of parameters
  - Higher Budget and tighter Deadline yield more tickets, hence shorter stride and more frequent scheduling.
- Outputs and I/O relationship
  - Outputs: Scheduling Information (tickets, stride, pass).
  - Input/output sequence: job and peer parameters → tickets → stride/pass.
  - Formulas
    - stride = global_stride_constant ÷ tickets
    - initial pass = stride

3.1.7 Determine Execution Host
- Purpose
  - Select the target node and queue for the job.
- Input validity checks
  - Availability of cluster load metrics, node status, remaining time of pending jobs, and available memory.
- Exact sequence
  - Sort hosts by load in ascending order to promote load balancing.
  - Select the least-loaded suitable host.
  - Select queue based on job type and QoS parameters.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: Exclude failed or unreachable hosts from consideration; if no host available, block until one becomes available or reject.
  - Error handling and recovery: If selection fails, return to queue selection after status refresh.
- Effect of parameters
  - Job type directs queue selection (sequential vs embarrassingly parallel).
  - Budget/Deadline can bias queue choice if policies differentiate queues.
- Outputs and I/O relationship
  - Outputs: chosen execution host and queue.
  - Input/output sequence: cluster state + job parameters → host/queue.
  - Formulas: [N/A]

3.1.8 Dispatch Job
- Purpose
  - Enqueue the job on the selected host/queue at the appropriate time.
- Input validity checks
  - Confirm chosen host and queue are still valid and available at dispatch time.
- Exact sequence
  - Send job to the selected queue via SGE.
  - Join competition for CPU according to scheduling parameters.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If dispatch fails due to host issues, retry or select an alternative host per Determine Execution Host.
  - Error handling and recovery: On dispatch failure, log and reattempt after Update Cluster Status.
- Effect of parameters
  - QoS parameters may influence dispatch timing to respect deadlines.
- Outputs and I/O relationship
  - Outputs: scheduled job placed on host/queue.
  - Input/output sequence: host/queue selection → dispatch → queue entry confirmation.
  - Formulas: [N/A]

3.1.9 Update Cluster Status
- Purpose
  - Maintain an up-to-date view of resource reservations and queue loads when jobs are scheduled or complete.
- Input validity checks
  - Verify job identity and target host/queue; ensure measurable resource metrics are available.
- Exact sequence
  - Reserve required resources for the job on the node.
  - Update execution host queue status.
  - Propagate updated load to central information store on the master host.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If master is unavailable, queue updates locally and synchronize when master recovers.
  - Error handling and recovery: Ensure idempotent updates to avoid double-counting on retries.
- Effect of parameters
  - Job resource profile influences reservation amounts and load metrics.
- Outputs and I/O relationship
  - Outputs: none; side effects are persisted state updates.
  - Input/output sequence: event trigger → update local → update master.
  - Formulas: [N/A]

3.1.10 Execute Job
- Purpose
  - Time-slice CPU among runnable jobs to enforce proportional shares.
- Input validity checks
  - Presence of valid scheduling information (tickets, stride, pass) for all runnable jobs.
- Exact sequence
  - Repeatedly select the job with the minimum pass value on the queue.
  - Allocate one quantum to the selected job.
  - Advance the job’s pass by its stride.
  - On ties, break using FIFO.
  - Continue until no runnable jobs remain on the queue.
- Responses to abnormal situations
  - Overflow: [N/A]
  - Communication facilities: [N/A]
  - Hardware faults/failures: If a node fails during execution, overall system is down until OS reboots (<5 minutes); process migration is not supported.
  - Error handling and recovery: After recovery, normal scheduling resumes; treatment of partially executed jobs is not specified.
- Effect of parameters
  - Higher ticket counts (from Budget/Deadline) yield shorter strides and more frequent CPU allocation.
- Outputs and I/O relationship
  - Outputs: updated cluster information (CPU load, node status, remaining time of pending jobs, available memory).
  - Input/output sequence: scheduling info + runnable set → selected job → quantum → updated passes and cluster metrics.
  - Formulas
    - Selection predicate: choose job with minimal current pass
    - pass_next = pass_current + stride

3.1.11 Interfaces used by functions
- User interfaces
  - Cluster user and administrator interfaces via Linux command prompt or SGE UI, supporting submission, monitoring, cancellation, and administration functions.
- Hardware interfaces
  - SGE’s CPU, memory, swap, and network interfaces are used; Libra defines no new hardware interfaces.
- Software interfaces
  - Libra interfaces with SGE 5.3; PVM and MPI libraries are used for embarrassingly parallel jobs.
- Communications
  - Libra uses SGE’s communications architecture; no unique communications defined.
- Abnormal condition handling for communications
  - [N/A]

## 3.2 Performance requirements

- Static capacity limits
  - Number of terminals supported: [N/A]
  - Number of simultaneous users supported: [N/A]
  - Maximum number of jobs: No intrinsic upper limit in the scheduler; bounded only by the underlying cluster’s capacity to meet job deadlines.
  - Amount/type of information handled: [N/A]

- Dynamic performance
  - Job submission response time: The maximum response time for the submission of a job shall be 1 minute.
  - Deadline adherence: Assuming submitted job statistics (e.g., execution time) are accurate, all accepted jobs shall be completed within a 10% error allowance of the user-specified deadline.
  - Cost cap enforcement: Under all circumstances, the amount charged to a user shall not exceed the maximum cost (budget) submitted by that user.

- Workload conditions
  - Normal workload quantitative limits: [N/A]
  - Peak workload quantitative limits: [N/A]

## 3.3 Usability requirements

- Contexts of use
  - The system shall support two user types: cluster user and cluster administrator, each interacting via the Linux command prompt or the Sun Grid Engine (SGE) interface.
  - [N/A] Additional contexts of use (e.g., GUI, remote/mobile access, accessibility accommodations).

- Effectiveness
  - The user interface shall expose commands enabling users to:
    - submit jobs with associated deadline, cost, and execution time,
    - query the current cost per unit time for submitting new jobs,
    - monitor the status of submitted jobs,
    - cancel jobs submitted by the user,
    - check the user’s credit balance,
    - check the user’s usage history.
  - The user interface shall expose commands enabling administrators to:
    - check the status of each node,
    - check the cluster usage history,
    - check the status of all submitted jobs,
    - check the load on each node,
    - alter the cluster cost structure,
    - alter the scheduling policy,
    - cancel, suspend, and resume any job.
  - When a job is rejected, the system shall provide a suggested deadline or cost as a precondition for acceptance.
  - [N/A] Quantitative task success criteria (e.g., task completion rates, error rates).

- Efficiency
  - The maximum response time for job submission shall be 1 minute.
  - [N/A] Additional time-on-task or throughput targets for other user tasks.

- Satisfaction
  - [N/A] User satisfaction targets (e.g., survey scores, complaint thresholds).

- Learnability and operability
  - Online user documentation shall be provided as Linux man pages.
  - [N/A] Learnability targets (e.g., time to first successful submission, training time).

- Error prevention, security, and avoidance of harm
  - Viewing, deleting, or changing a job shall require user authentication (user ID and password) to ensure only the appropriate user can act on the job.
  - Users shall not normally be able to change critical scheduling parameters (deadline, cost) after submission; such alterations require administrator authority.
  - The scheduler shall ensure privacy of user job status and maintain administrative control over job execution so that alteration of scheduling criteria or resource allocation is not possible without administrator authority.
  - Under all circumstances, the maximum cost charged shall not exceed the maximum cost submitted by the user.
  - [N/A] Additional safeguards against misuse or accidental harmful operations (e.g., confirmations, undo).

## 3.5 Logical database requirements

This section specifies the logical data needs implied by the Libra scheduler’s features and its interaction with Sun Grid Engine (SGE). Libra maintains and consults a central information store on the master host to support acceptance decisions, scheduling, dispatching, execution-time updates, user/admin queries, and job accounting/usage history.

a) Types of information used by various functions
- Submit Job
  - User information (name, authentication id).
  - Job specifications (executable and input locations, output location, system type, maximum run time, job type, budget, deadline).
  - Cluster submission status (whether accepting submissions).
- View Job Status
  - Job status/progress, execution host and queue, expected finish time, remaining time of pending jobs.
- Delete/Change Job
  - Job record and allowed mutable parameters (e.g., output directory; delayed deadline where permitted).
  - Cluster status impacted by removal/change.
- Initialize Job
  - Parsed job details and SGE-assigned job id; persisted as scheduler-visible variables/records.
- Accept/Reject Job
  - Job parameters (budget, deadline, execution time estimate).
  - Cluster information (CPU load, node status, remaining time of pending jobs).
  - Decision outcome (accepted/rejected) and any suggested alternative deadline or cost.
- Calculate Scheduling Information
  - Scheduling parameters (tickets, stride, pass) computed per accepted job.
- Determine Execution Host
  - Host/node load and status; available memory; queue characteristics.
  - Selected execution host and queue.
- Dispatch Job
  - Job placement into chosen host/queue; dispatch timestamp/state.
- Update Cluster Status
  - Reserved resources on node; queue lengths; node load; aggregated cluster status on master.
- Execute Job
  - Runtime scheduling fields (pass updates, remaining time) and cluster metrics (CPU load, node status, available memory).
- User/Admin Account and Policy Queries
  - Credit balance, usage history.
  - Current cost per unit time; cost structure and scheduling policy settings.

b) Frequency of use
- High frequency (continuous/periodic during execution)
  - Execute Job (updates to pass/remaining time).
  - Update Cluster Status (on each job schedule/removal; during execution as loads change).
- Medium frequency (per job life cycle event)
  - Initialize Job, Accept/Reject Job, Calculate Scheduling Information, Determine Execution Host, Dispatch Job.
- Low frequency (on-demand by humans)
  - Submit Job, View Job Status, Delete/Change Job, account/usage history queries, admin policy/cost structure changes.

c) Accessing capabilities
- Query capabilities
  - By user: list and filter jobs owned by the user; retrieve job status/progress; retrieve credit balance and usage history; query current cost per unit time.
  - By administrator: retrieve status of all jobs; per-node load and queue status; cluster-wide usage patterns/history; cost structure and scheduling policy settings.
- Update capabilities
  - Scheduler/SGE: create/update job records; write scheduling parameters (tickets, stride, pass); update job state transitions; update node/queue/cluster status; reserve/release resources; write accounting usage.
  - Administrator: update cost structure and scheduling policy; cancel/suspend/resume any job.
- Access patterns
  - Support concurrent reads/writes by scheduler components and SGE.
  - Efficient retrieval by keys: job id, user id, node id, queue id.

d) Data entities and their relationships
- User
  - Attributes: user id, authentication id, credit balance.
  - Relationships: User submits many Jobs; User has many Accounting Records and Usage History entries.
- Job
  - Attributes: SGE job id, owner (user id), job type (sequential or embarrassingly parallel), standalone execution time estimate, executable/input/output locations, system type, budget, deadline, submission time, state (submitted, accepted, queued, running, completed, cancelled), acceptance decision, suggested alternative deadline/cost (if any), selected execution host and queue.
  - Relationships: Job has one Scheduling Information; Job executes on one Host via one Queue; Job generates many Accounting Records/usage entries.
- Scheduling Information
  - Attributes: job id (FK), tickets, stride, pass.
  - Relationships: belongs to Job.
- Host (Execution Node)
  - Attributes: host id, CPU load, available memory, status.
  - Relationships: Host has many Queues; many Jobs are dispatched to Host via its Queues.
- Queue
  - Attributes: queue id, host id (FK), queue type/capabilities, queue length.
  - Relationships: Queue belongs to Host; Queue contains many Jobs.
- Cluster Status (master-store aggregates)
  - Attributes: per-host and per-queue summaries; remaining time of pending jobs; submission acceptance flag.
  - Relationships: aggregates Hosts, Queues, and Jobs.
- Accounting Record / Usage History
  - Attributes: record id, job id (FK), user id (FK), resource usage metrics, cost charged.
  - Relationships: belongs to Job and User.
- Cost Structure / Current Price
  - Attributes: current cost per unit time and related parameters configurable by administrator.
  - Relationships: referenced by Accept/Reject and user price query.

e) Integrity constraints
- Identifiers and referential integrity
  - Job id (from SGE) is unique; foreign keys from Scheduling Information and Accounting Records reference existing Jobs; Queue references an existing Host.
- Domain constraints
  - Job type ∈ {sequential, embarrassingly parallel}.
  - Budget and cost charged are non-negative.
  - Standalone execution time estimate is positive.
  - System type matches supported platform (Linux).
- Temporal/semantic constraints
  - Deadline ≥ submission time.
  - Acceptance implies feasibility against current cluster status (as determined by Accept/Reject).
  - Maximum cost charged to a user must not exceed the maximum cost submitted by the user (Cost sensitivity).
  - Post-acceptance changes to critical parameters (budget, deadline) are not normally permitted; allowed changes (e.g., output directory, delayed deadline where permitted) must not invalidate acceptance constraints.
- Consistency
  - Scheduling parameters (tickets, stride, pass) must correspond to current job set on the execution host.
  - Cluster aggregates on the master host must reflect per-host/queue updates.

f) Security
- Access control
  - Privacy of user job status must be enforced: only the owning user can view their jobs; administrators can view all jobs.
  - Only administrators can alter cost structure, scheduling policy, or cancel/suspend/resume any job irrespective of ownership.
- Authentication
  - User id and password (authentication id) are required to access user-specific data and actions.
- Administrative security
  - Ensure full control over job execution and prevent unauthorized alteration of scheduling criteria or resource allocation without administrator authority.

g) Data retention requirements
- Usage history and job accounting must exist to support user/admin queries; specific retention durations are: [N/A]
- Retention periods for cluster status snapshots, scheduling parameters after job completion, and logs: [N/A]

## 3.6 Design constraints

- Licensing and openness
  - Must be released under the GNU General Public License (GPL) and remain open-source.
  - Code and documentation must comply with GPL requirements; no purchased components.

- Platform and parent system
  - Must run as an add-on/sub-component of Sun Grid Engine (SGE) on a Linux-based cluster.
  - Must directly interface with SGE version 5.3 and use SGE’s hardware and communications interfaces; no unique communications beyond SGE.
  - No modifications to the Linux kernel are permitted.

- Programming language and coding conventions
  - All implementation must be in standard C.
  - Naming must follow the Hungarian Naming Convention.

- External libraries and middleware
  - For embarrassingly parallel jobs, PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) must be used.

- Algorithmic and scheduling constraints
  - Resource allocation must follow a market-based, bid-based proportional resource-sharing model.
  - Enforcement of proportional allocations must use the stride scheduling algorithm.
  - Exhaustive combinatorial searches are not allowed; heuristics must be used.

- Scope limitations affecting design
  - Only sequential and embarrassingly parallel jobs are supported.
  - Target deployment is a homogeneous Linux cluster.
  - Job migration to reduce resource fragmentation is not supported.

- User interface and documentation
  - User and administrator interaction is limited to the Linux command line and/or the SGE interface; a GUI is deferred.
  - Online documentation must be provided as Linux man pages.

- Project environment limitations
  - Development and testing resources are limited to a small cluster (four Pentium-III workstations with 128 MB RAM).
  - A simulation tool may be required for testing if a suitable open-source option is not available.

## 3.7 Software system attributes

- Reliability
  - Maximum bug rate at delivery: 1 bug/KLOC.
  - The scheduler will not support job migration for the purpose of decreasing resource fragmentation.

- Availability
  - Maximum time to repair (following outage): system availability restored after Linux OS reboot in less than 5 minutes.
  - Checkpointing: [N/A]
  - Recovery/restart mechanisms beyond OS reboot: [N/A]
  - Target availability level (e.g., percentage uptime): [N/A]

- Security
  - Administrative security is required: alteration of scheduling criteria or actual resource allocation is not possible without administrator authority.
  - Privacy: the system shall ensure the privacy of user job status; only the appropriate user may view or modify their jobs.
  - Authentication: user ID and password are required to view job status and to delete/change a job.
  - Cryptographic techniques: [N/A]
  - Logs/history data sets: a basic level of job accounting and usage history shall be provided.
  - Functional segregation (assignment of functions to different modules): [N/A]
  - Restricted communications between programme areas: [N/A]
  - Data integrity checks for critical variables: [N/A]

- Maintainability
  - Implementation language: standard C.
  - Naming convention: Hungarian Naming Convention.
  - Modularity/architecture: the scheduler should be separable from the cluster management system and configurable to allow various scheduling policies that can be modified to incorporate QoS parameters.
  - Complexity limitation: exhaustive searches of all job combinations will not be performed; heuristics will be developed.
  - Documentation: online user documentation provided as Linux man pages.
  - Open-source under GPL, facilitating ongoing maintenance and community contributions.

- Portability
  - Target operating system/environment: Linux-based clusters; no modifications to the Linux kernel are required.
  - Language portability: implemented in standard C.
  - External dependencies: operates as a sub-component of Sun Grid Engine (SGE) 5.3; uses PVM and MPI libraries for embarrassingly parallel jobs; hardware interfaces are those provided by SGE.
  - Percentage of elements with host-dependent code: [N/A]
  - Percentage of code that is host dependent: [N/A]
  - Particular compiler or language subset required: [N/A]
  - Particular operating system required: Linux.

## 3.8 Supporting information

The following items are provided to aid understanding of the system context and intent. Unless otherwise stated, they are not to be considered binding requirements.

- a) Sample input/output formats, cost analysis, and user surveys
  - Sample input/output formats: [N/A]
  - Cost analysis studies: [N/A]
  - User survey results: [N/A]
  - Available input and output data elements described in this SRS:
    - User/job submission inputs:
      - User information: name, authentication ID
      - Job details: Job ID (assigned by SGE), job type (sequential or embarrassingly parallel), standalone execution time (maximum run length), location of executable and input data sets, system type, budget, deadline, output location
    - Cluster/system state inputs:
      - Cluster type and scheduling mechanism, current load status, submission directions/criteria, CPU load, node status, remaining time of pending jobs, available memory
    - Decision and status outputs:
      - Admission decision: boolean accept/reject, suggested deadline or cost if constraints cannot be met
      - Scheduling information: tickets, stride, pass
      - Placement decision: chosen execution host and queue
      - Status and accounting outputs: updated CPU load, node status, remaining time of pending jobs, available memory; user-visible job status/options
- b) Supporting or background information
  - Background research topics (Appendix A, dated 10 Nov 2001): Cluster Computing, Market-based Economic Models, Cluster Scheduling, Cluster Management Software
  - Data Flow Diagrams (Appendix B) and Data Dictionary (Appendix C)
  - Architectural context:
    - Libra operates as an add-on scheduler within Sun Grid Engine (SGE) on a Linux-based homogeneous cluster; no Linux kernel modifications required
    - Uses a bid-based proportional resource-sharing model and stride scheduling to enforce allocations proportional to user-centric priorities (deadline and budget)
    - Executes sequential and embarrassingly parallel batch jobs; PVM/MPI libraries are available for parallel execution as supported by the cluster
  - Constraints and environment notes:
    - Testbed described as four Pentium-III workstations with 128 MB RAM each, running SGE on Linux
    - Simulation/testing tool may be required; choice of tool undecided
- c) Problems to be solved by the software
  - Provide QoS-driven, market-based scheduling on clusters to maximize user utility, honoring user-specified deadline and budget
  - Enable dynamic reallocation of resources so urgent, higher-paying jobs can meet deadlines even under load
  - Allocate CPU time proportionally based on user-centric priorities while maintaining scalability and configurability
  - Support admission control (accept/reject) based on feasibility given execution time estimates and current cluster load
  - Manage execution of sequential and embarrassingly parallel jobs on a homogeneous Linux cluster through SGE
  - Provide basic administrative security and job accounting sufficient to support scheduling policies
- d) Special packaging instructions for code and media
  - [N/A]

These supporting information items are provided for context and clarification only and are not part of the mandatory requirements unless explicitly referenced as such in the requirements sections.

## 4.1 Functions

This section defines how each functional requirement in 3.1 will be verified, covering input validity checks, operation sequences, responses to abnormal situations, effects of parameters, and the relationship of outputs to inputs (including I/O sequences and formulas). Where the original SRS does not specify expected behavior, [N/A] is stated. Verification will be performed in the SGE 5.3 environment on Linux via command-line/SGE interfaces and, where applicable, using a simulation tool as noted in 2.4 and 2.6.

- 3.1.1 Submit Job
  - Validity checks on inputs: Verify cluster “accepting submissions” gate and user authentication via SGE.
  - Exact sequence of operations: Verify submission gate and user validation occur before any acceptance decision.
  - Responses to abnormal situations:
    - Overflow: [N/A]
    - Communication facilities: [N/A]
    - Hardware faults and failures: Verify submissions are refused during cluster downtime; overall recovery is governed by 3.2.3 (Linux reboot < 5 minutes).
    - Error handling and recovery: [N/A]
  - Effect of parameters: Verify capture of all declared job parameters (deadline, budget, execution time, job type, system type, I/O locations).
  - Relationship of outputs to inputs: Verify Boolean outputs reflect submission gate status and user verification as specified.
  - Verification approach: Functional tests via SGE CLI with valid/invalid users and open/closed submission states; interface inspection for presence of additional submission parameters.

- 3.1.2 View Job Status
  - Validity checks on inputs: Verify access control using user ID/password; only job owner or administrator can view.
  - Exact sequence of operations: Verify authentication precedes presentation of options and job status information.
  - 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: [N/A]
  - Relationship of outputs to inputs: Verify that the displayed status corresponds to the authenticated user’s jobs.
  - Verification approach: Functional tests via CLI/SGE to check authorization filtering and available options rendering.

- 3.1.3 Delete/Change Job
  - Validity checks on inputs: Verify authenticated ownership or admin rights before delete/change.
  - Exact sequence of operations: Verify queue removal precedes cluster status and scheduling updates.
  - 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 deadline and cost are not changeable by users under normal operation; verify that permitted changes (e.g., output directory or delayed deadline if allowed) take effect.
  - Relationship of outputs to inputs: Verify cluster information and scheduling decisions are updated as specified.
  - Verification approach: Functional tests deleting/canceling jobs and attempting restricted/allowed parameter changes; observe updated cluster/queue state via SGE.

- 3.1.4 Initialize Job
  - Validity checks on inputs: Verify presence and parsability of all required job details and SGE-assigned job ID.
  - Exact sequence of operations: Verify retrieval of job details precedes setting internal scheduler variables and passing to scheduling.
  - 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 all captured parameters are available to downstream scheduling decisions.
  - Relationship of outputs to inputs: Verify internal state mirrors submitted job details exactly.
  - Verification approach: Unit tests on parsing and state-setting; integration test confirming handoff to scheduling module.

- 3.1.5 Accept/Reject Job
  - Validity checks on inputs: Verify required inputs are present (budget, deadline, execution time, cluster status metrics).
  - Exact sequence of operations: Verify priority/share derivation precedes feasibility check against deadline and cluster load.
  - 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 budget and deadline influence acceptance decision as the primary criteria.
  - Relationship of outputs to inputs: Verify Boolean decision is consistent with feasibility; verify suggested deadline/cost is produced when rejection would otherwise occur.
  - Verification approach: Scenario-based tests with varying budgets/deadlines and cluster loads (including simulated loads); check accept/reject and suggestion outputs.

- 3.1.6 Calculate Scheduling Information
  - Validity checks on inputs: Verify presence of job details and all competing jobs’ budget/deadline inputs for the execution host.
  - Exact sequence of operations: Verify 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: [N/A]
  - Effect of parameters: Verify that budget and deadline impact ticket allocation as specified.
  - Relationship of outputs to inputs:
    - Input/output sequences: Verify tickets -> stride -> pass order.
    - Formulas: Verify stride = global stride constant / tickets and initial pass = stride.
  - Verification approach: Unit tests validating stride/pass calculations; integration tests ensuring per-host competition context is used; [N/A] for the exact ticket allocation formula beyond stated dependence.

- 3.1.7 Determine Execution Host
  - Validity checks on inputs: Verify availability of CPU load, node status, remaining time of pending jobs, available memory, and job details.
  - Exact sequence of operations: Verify hosts are sorted by ascending load and the least-loaded host is chosen before queue selection.
  - 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 job type (sequential vs. embarrassingly parallel), budget, and execution time influence queue selection.
  - Relationship of outputs to inputs: Verify chosen host/queue reflect load-balancing and job constraints.
  - Verification approach: Integration tests with controlled load profiles (including via simulation) to confirm least-loaded host selection and appropriate queue assignment.

- 3.1.8 Dispatch Job
  - Validity checks on inputs: Verify that a chosen execution host and queue exist prior to dispatch.
  - Exact sequence of operations: Verify insertion into the selected queue occurs at the intended time, allowing for intentional waiting if applicable.
  - 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: [N/A]
  - Relationship of outputs to inputs: Verify that the job appears in the designated host/queue.
  - Verification approach: Integration tests that observe queue state transitions via SGE.

- 3.1.9 Update Cluster Status
  - Validity checks on inputs: Verify job details and selected host/queue are provided when updating.
  - Exact sequence of operations: Verify resource reservation precedes queue status update and propagation to the master host’s central information store.
  - 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: [N/A]
  - Relationship of outputs to inputs: Verify that node/queue load reflects the added/removed job accurately.
  - Verification approach: Integration tests that add/remove jobs and confirm updated CPU load, node status, remaining times, and available memory through SGE reporting.

- 3.1.10 Execute Job
  - Validity checks on inputs: Verify availability of scheduling information (tickets, stride, pass) for all runnable jobs.
  - Exact sequence of operations: Verify selection of the job with minimum pass, allocation of a quantum, and update of its pass by adding its stride; verify FIFO tie-breaker.
  - 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 tickets/stride/pass values govern CPU share proportionality.
  - Relationship of outputs to inputs: Verify updated cluster information (CPU load, node status, remaining times, memory) reflects the enforced proportional sharing.
  - Verification approach: Controlled multi-job runs (including simulation) to confirm proportional CPU allocation per stride scheduling and correct tie-breaking; monitor SGE-reported metrics.

General notes on abnormal situations across 3.1:
- Overflow handling, communication failures, and detailed error handling/recovery at the function level are not specified in the SRS. [N/A]
- Hardware faults/failures handling at the function level is not specified. System-level recovery time is specified in 3.2.3 and will be verified separately.

## 4.2 Performance requirements

This section defines the approaches and methods to verify the performance requirements specified in Section 3.2 (Performance requirements). Each verification item parallels the corresponding requirement.

- Response time (job submission acknowledgment within 1 minute)
  - Verification method:
    - Conduct end-to-end submission latency tests measuring wall-clock time from invocation of the submission interface (CLI/SGE) to receipt of scheduler acknowledgment (accept/reject).
    - Execute tests under varying load conditions: idle, typical, and peak queue loads (with concurrent submissions and executing jobs).
    - Instrumentation: timestamped client logs, SGE scheduler/master logs, and Libra logs.
    - Sample size: multiple runs per load condition sufficient to observe worst-case behavior.
  - Acceptance criteria:
    - Maximum observed submission response time ≤ 60 seconds across all runs and load conditions.

- Capacity (no upper limit inherent in the Libra scheduler)
  - Verification method:
    - Submit a progressively increasing number of jobs until the underlying cluster/SGE or QoS feasibility prevents further acceptance.
    - Observe acceptance/rejection reasons to confirm rejections arise from QoS infeasibility (e.g., deadlines not satisfiable given current load) or underlying platform limits, not from a Libra-imposed hard cap.
    - Inspect configuration and code paths for absence of explicit Libra queue-size or job-count caps beyond those provided by SGE/OS.
    - Monitor stability (no crashes or deadlocks) as the pending job count grows.
  - Acceptance criteria:
    - No Libra-specific limit encountered prior to SGE/OS/platform limits.
    - Rejections (when they occur) cite QoS or platform constraints, not a Libra job-count ceiling.
    - Scheduler remains stable while handling large pending queues.

- Deadline sensitivity (completion within 10% error allowance, assuming accurate user-provided execution times)
  - Verification method:
    - Prepare a synthetic workload with jobs whose standalone execution times are known and match the user-submitted estimates.
    - Assign budgets and deadlines per the requirement model; include mixes of sequential and embarrassingly parallel jobs.
    - Run under light, typical, and peak loads.
    - For all accepted jobs, collect actual completion times from SGE/Libra logs and compare to the submitted deadlines.
    - Verify accept/reject decisions are consistent with the feasibility model used by Libra.
  - Acceptance criteria:
    - For each accepted job J with submitted deadline D, actual completion time C satisfies C ≤ 1.10 × D.
    - Jobs that cannot satisfy the above are rejected during admission control.

- Cost sensitivity (charged cost shall not exceed user-submitted maximum cost)
  - Verification method:
    - Submit jobs across a range of user budgets, including boundary values.
    - After completion, retrieve job accounting records and computed charges.
    - Include cases where execution runs long (within the accepted QoS model) to test upper bound enforcement.
  - Acceptance criteria:
    - For every job, recorded total charge ≤ user-submitted maximum cost.
    - No charge in excess of the submitted maximum is observed in accounting outputs.

- Static numerical performance items
  - Number of terminals supported: [N/A]
  - Number of simultaneous users supported: [N/A]
  - Amount and type of information to be handled (numerical limits): [N/A]

- Dynamic numerical performance items (throughput/transactions over time under normal/peak)
  - Transactions/tasks per time period targets: [N/A]
  - Data volume per time period targets: [N/A]

## 4.3 Usability requirements

The following verification approaches will be used to qualify usability-related requirements, aligned with the stated user interfaces, documentation, and access-control behaviors in the Requirements section (notably 3.1 Functional features, 3.6 Online user documentation and help, and 3.8 Interfaces).

- User task completeness (cluster user)
  - Scope: Ability to perform each user task via Linux CLI and/or SGE interface as specified in 3.8.1.1 and 3.1, including:
    - submit job with deadline, cost, and execution time,
    - query current cost per unit time,
    - monitor status of submitted jobs,
    - cancel own jobs,
    - check credit balance,
    - check usage history.
  - Method: Scenario-based task execution on a Linux system with SGE by representative users; confirm the existence of commands and successful end-to-end task execution using the documented parameters (including budget and deadline).
  - Evidence: Test scripts, command transcripts, and observed outcomes matching specified behaviors.

- Administrator task completeness (cluster administrator)
  - Scope: Ability to perform each administrator task via Linux CLI and/or SGE interface as specified in 3.8.1.2, including:
    - check status of each node,
    - view cluster usage history and all submitted jobs,
    - check load per node,
    - alter cost structure,
    - alter scheduling policy,
    - cancel, suspend, resume any job.
  - Method: Role-based task execution with administrative credentials; verify commands exist and function as described.
  - Evidence: Test logs, configuration diffs where applicable, and operation outcomes.

- Role separation and access control for usability-critical operations
  - Scope: Enforcement of authentication and authorization for viewing job status and deleting/changing jobs as stated in 3.1.2.2 and 3.1.3.2, and administrative control as stated in 3.8.1.2 and 3.2.4.
  - Method: Positive and negative tests:
    - authenticated user can view only their job status and cancel their own jobs,
    - unauthenticated/other users cannot access or modify another user’s jobs,
    - non-admin users cannot perform administrator-only actions (e.g., alter cost structure or scheduling policy).
  - Evidence: Access attempts with varied credentials and resulting system responses.

- Submission parameter support and propagation
  - Scope: SGE interface adaptation to accept QoS parameters (budget, deadline, execution time) and pass them to Libra as stated in 3.1.1.1 and 3.1.4.
  - Method: Form and CLI submission tests providing the additional parameters; tracing to confirm parameters are stored and used in initialization and scheduling steps.
  - Evidence: Parameter presence in job metadata, logs, and subsequent scheduling decisions.

- Documentation and help system availability
  - Scope: Availability of Linux man pages and compliance with documentation requirements in 3.6.
  - Method: Installation verification that man pages are present for all user and admin commands; content review to confirm inclusion of purpose, syntax, parameters (including budget/deadline), and examples consistent with implemented behavior.
  - Evidence: Man page listings and content snapshots; cross-check report against command behavior.

- Interface modality and environment
  - Scope: Usability in the stated contexts of use (Linux CLI and SGE interface) per 3.8.1.
  - Method: Execute all user and admin task scenarios within a standard Linux environment running SGE; confirm no additional UI dependencies are required.
  - Evidence: Environment configuration records and task execution logs.

- GUI
  - Scope: The GUI is identified as desirable but not required in the current version (2.2, 3.8.1).
  - Verification: [N/A]

- Measurable effectiveness criteria
  - [N/A]

- Measurable efficiency criteria (e.g., time-on-task)
  - [N/A]

- User satisfaction criteria (e.g., surveys, SUS)
  - [N/A]

- Avoidance of harm in use (usability-specific)
  - [N/A]

## 4.5 Logical database requirements

a) Types of information used by various functions
- Verification approach:
  - Review and traceability: Map each data item referenced in 3.1 Functions (e.g., User Information, Job details, Cluster Information, Scheduling Information, Execution Host/Queue, Accounting/Cost/Usage data) to the logical data model or central information store used by SGE/Libra.
  - Functional data checks: For a representative job lifecycle (Submit → Initialize → Accept/Reject → Calculate Scheduling Information → Determine Execution Host → Dispatch → Update Cluster Status → Execute), verify that records are created/updated with the fields specified in the SRS:
    - User Information: name, authentication id.
    - Job details: Job Id (from SGE), Job type (sequential/embarrassingly parallel), standalone execution time, executable/input locations, system type, budget, deadline, output directory (if set).
    - Scheduling Information: tickets, stride, pass.
    - Cluster Information: CPU load, node status, remaining time of pending jobs, available memory.
    - Execution placement: chosen execution host and queue.
    - Accounting/Cost/Usage: current cost structure, credit balance, usage history.
  - Cross-check against SGE-provided logs/central store to confirm Libra writes/reads the expected fields.

b) Frequency of use
- Verification approach:
  - Event-driven validation: Instrument Update Cluster Status to verify it triggers on every job schedule/dispatch and on job completion, with no missed updates under continuous execution (Execute Job loop).
  - Operational burst tests: Submit/cancel/query jobs in bursts and sustain frequent View Job Status queries; verify no data loss or stale reads in the central information store and that updates reflect the latest state.
  - Long-run execution: Run queues continuously and confirm periodic updates remain consistent over time.

c) Accessing capabilities
- Verification approach:
  - Role-based access tests via the Linux/SGE interfaces:
    - Cluster user can: submit jobs with deadline, cost, execution time; query current cost per unit time; monitor own job status; cancel own jobs; check credit balance; check usage history.
    - Cluster administrator can: check node status and load; check all jobs; check usage patterns; alter cost structure; alter scheduling policy; cancel/suspend/resume any job.
  - Authorization negative tests: Ensure users cannot access other users’ job status or perform administrative actions; ensure only administrators can change cost structure/scheduling policy.
  - Data access validation: Each operation retrieves/updates only the documented fields and persists changes as specified.

d) Data entities and their relationships
- Verification approach:
  - Entity-relational consistency checks using functional workflows:
    - Job must reference its submitting User.
    - Accepted Job must be associated with an Execution Host and Queue (from Determine Execution Host) and with Scheduling Information (tickets/stride/pass).
    - Cluster Status aggregates per-node and per-queue state; updates must reflect dispatch and completion events.
    - Accounting/usage records link to Jobs and Users and reflect the active cost structure at submission/charging time.
  - Referential integrity tests: Deleting/canceling a Job updates Cluster Status and leaves no dangling references (e.g., scheduling info, host/queue assignments).
  - Trace tests: For each job, verify end-to-end linkage from submission through completion across all related entities.

e) Integrity constraints
- Verification approach:
  - Job Id uniqueness: Confirm SGE-assigned Job Ids are unique in stored records across the system.
  - Budget cap enforcement: Post-run audit that recorded charge for each job never exceeds the user-submitted maximum cost (3.3.4).
  - Acceptance feasibility: For accepted jobs, verify stored acceptance rationale aligns with inputs (budget, deadline, execution time) and that the subsequent schedule honors the computed share; use stored scheduling parameters for evidence.
  - Deadline/error allowance check: Using stored start/finish timestamps, verify that completed jobs meet the 10% error allowance criterion stated in 3.3.3.
  - Status consistency: Verify that every dispatch/completion event results in a corresponding Cluster Status update; no orphaned running jobs or stale queue entries.
  - No migration guarantee: Verify that the stored execution host for a job does not change during execution (3.2.1).

f) Security
- Verification approach:
  - Authentication: Validate that access to job/accounting/usage data requires valid User Id and Password.
  - Authorization: Test that only administrators can alter scheduling criteria, resource allocations, cost structure, and scheduling policy (3.2.4, 3.8.1.2).
  - Privacy: Attempt cross-user access to job status/history and confirm denial; verify that user-visible views exclude other users’ data (3.2.4).
  - Auditability: Confirm that administrative changes to cost/scheduling policy are logged with user, timestamp, and before/after values.

g) Data retention requirements
- [N/A]

## 4.6 Design constraints

This section defines the planned verification approaches to demonstrate compliance with the design constraints specified in Requirements 3.6 (Design constraints).

- Parent component: Sun Grid Engine (SGE)
  - Verification objective: Libra operates as an SGE sub-component (SGE v5.3), uses only SGE-exposed interfaces, and requires no Linux kernel modifications.
  - Methods:
    - Integration testing in an SGE 5.3 environment: submit, schedule, dispatch, and monitor jobs exclusively via SGE commands/APIs.
    - Interface/API review against SGE 5.3 documentation to confirm no direct OS kernel hooks or unsupported interfaces are used.
    - Packaging/deployment inspection to confirm Libra is built and installed as an SGE module/extension without kernel patches.
  - Evidence:
    - Test reports for end-to-end job lifecycle via SGE.
    - Interface compliance checklist signed off by reviewers.
    - Build/deployment artifacts and installation instructions demonstrating SGE-only integration.
  - Acceptance criteria:
    - All functional flows (submit, accept/reject, schedule, dispatch, execute, update status) execute through SGE without kernel changes.
    - No use of non-SGE privileged interfaces detected in code review.

- Software language: Standard C
  - Verification objective: All production source code is written in standard C and builds with a C toolchain.
  - Methods:
    - Build pipeline compiles with a C compiler (e.g., gcc with a specified -std flag) and fails if C++ compiler/linker is invoked.
    - Static analysis/linting configured for C (e.g., clang-tidy, cppcheck in C mode) to flag non-C constructs.
    - Repository audit to ensure only .c/.h source files (or generated C) are present for runtime components.
    - Code review checklist item for language compliance.
  - Evidence:
    - CI logs showing successful C-only builds and static analysis results.
    - Repository report of file types and build scripts.
    - Review records confirming no C++ usage.
  - Acceptance criteria:
    - 100% of runtime code compiles with a C compiler per chosen C standard without requiring a C++ toolchain.
    - No C++ keywords, templates, or linkage detected by static analysis or review.

- Scheduling constraints: Heuristics only (no exhaustive search of all job combinations)
  - Verification objective: Scheduling decisions are made using heuristic algorithms; the implementation does not perform combinatorial/exhaustive enumeration of job combinations.
  - Methods:
    - Design review of scheduling algorithms (including stride-based enforcement and host/queue selection) to confirm heuristic approach and absence of exhaustive combinatorial search.
    - Code inspection to detect enumeration over combinatorial subsets or exponential-time decision routines.
    - Performance tests under increasing numbers of jobs/nodes to confirm scheduling latency scales in line with heuristic expectations (e.g., approximately linearithmic/polynomial behavior) and within stated response-time limits for submission (see Requirements 3.2).
  - Evidence:
    - Approved design documents describing the heuristic selection and proportional resource enforcement.
    - Code review findings with no instances of combinatorial enumeration.
    - Empirical results showing scheduler decision times remain bounded and practical for target scales.
  - Acceptance criteria:
    - No functions implementing exhaustive search over job combinations identified in code.
    - Scheduling decision latency meets the system’s operational response expectations across tested scales, indicating a heuristic (non-exhaustive) approach.

## 4.7 Software system attributes

This section defines the verification approaches and methods to qualify the software system attributes, aligned with the corresponding requirement items.

- Reliability
  - Defect density threshold (≤ 1 bug/KLOC): verify via defect tracking after unit, integration, and system testing; compute KLOC from source and confirm defect density does not exceed the threshold.
  - Maximum time to repair (< 5 minutes): perform controlled outage/reboot tests on the master and execution hosts; measure time from outage to restored scheduling service; pass if measured time consistently remains under 5 minutes.
  - No job migration for fragmentation: verify by design/code inspection (absence of migration routines for fragmentation reduction) and runtime observation under load; confirm scheduler never initiates migration for this purpose.

- Availability
  - Restart/recovery: execute planned OS reboot and SGE restart scenarios; verify Libra resumes normal operation without manual reconfiguration and within the defined repair time; confirm no Linux kernel modifications are required for recovery.
  - Checkpoint/restart capability: [N/A].

- Security
  - Authentication and authorization: test that View Job Status and Delete/Change Job require valid user ID and password; attempt cross-user access to verify denial of unauthorized reads/changes.
  - Job status privacy: attempt to retrieve job status of other users; verify access is denied and only owners (or administrators) can view.
  - Administrator-only control: attempt to alter scheduling criteria or resource allocation as a non-admin user; verify denial and that only administrators can perform such actions.
  - Cryptographic techniques: [N/A].
  - Security logging/history requirements: [N/A].
  - Function/module segregation for security: [N/A].
  - Communications restrictions between components: [N/A].
  - Data integrity checks for critical variables: [N/A].
  - Data privacy beyond job status: [N/A].

- Maintainability
  - Naming convention (Hungarian): run static analysis/linting to check identifier and file naming rules; sample reviews to confirm adherence or documented exceptions.
  - Coding standards/licensing (GNU GPL compliance): perform repository and source header review to confirm GPL licensing notices and distribution artifacts meet GPL requirements.
  - No kernel modification: confirm by build/deployment review and environment inspection that no Linux kernel patches or changes are required.
  - Modularity/complexity limitations: [N/A].

- Portability
  - Portable language (standard C): compile with a standard C compiler on the target Linux environment without using non-standard extensions; build must succeed with no non-portable dependencies.
  - Target environment compatibility: install and run with Sun Grid Engine 5.3 on a homogeneous Linux cluster; verify correct operation with PVM/MPI where applicable.
  - Percentage of host-dependent elements: [N/A].
  - Percentage of host-dependent code: [N/A].
  - Required compiler or language subset: [N/A].
  - Required operating systems beyond Linux: [N/A].

## 5.1 Assumptions and dependencies

- Availability and correct operation of the Sun Grid Engine (SGE) cluster management system (version 5.3), including its queuing, scheduling, resource management, communications, and related modules (e.g., process migration) that must interoperate with Libra’s policies.
- Deployment on a homogeneous Linux cluster; all execution hosts run Linux with uniform characteristics as defined for a homogeneous cluster.
- Availability of PVM and MPI libraries for executing embarrassingly parallel jobs.
- Users provide QoS parameters (budget and deadline) with each job submission.
- Users provide a fair/accurate estimate of standalone execution time with each job submission.
- A basic job accounting and payment facility is available to support credit tracking, charging, and usage history (detailed pricing front-end to be specified later).
- User access is via the Linux command line or the SGE interface; a GUI is out of scope for the current version.
- The operational model excludes user-to-user bargaining/negotiation; QoS is provided within a single administrative domain without inter-user market interactions.
- Authentication and authorization mechanisms (e.g., user ID and password) provided by the underlying system/SGE are available to restrict access to job information and control operations.
- Accurate and timely cluster state information (e.g., CPU load, node status, remaining time of pending jobs, available memory) is provided by SGE for Libra’s scheduling decisions.

## 5.2 Acronyms and abbreviations

- SRS — Software Requirements Specification
- QoS — Quality of Service
- SGE — Sun Grid Engine
- GUI — Graphical User Interface
- CPU — Central Processing Unit
- GPL — GNU General Purpose License
- GNU — GNU’s Not Unix
- MPI — Message Passing Interface
- PVM — Parallel Virtual Machine
- FIFO — First-In, First-Out
- ID — Identifier
- KLOC — Thousand Lines of Code
- RAM — Random Access Memory
- Mb — Megabyte
- HPC — High Performance Computing
- IEEE — Institute of Electrical and Electronics Engineers
- CS — Computer Society
- HCW — Heterogeneous Computing Workshop
- IPDPS — International Parallel and Distributed Processing Symposium
- PDPTA — Parallel and Distributed Processing Techniques and Applications