Dynamic Scheduling of Update and Query Workloads in Agent Service Discovery Nodes

Abstract

Agent service discovery nodes may need to process two classes of workloads concurrently: Agent registration and dynamic state updates, and discovery queries issued by other Agents. These workloads compete for shared processing resources but have different performance objectives. Delayed state updates can cause a service discovery node to rely on stale workload, availability, or QoS information, while delayed queries can increase Agent-selection latency and the completion time of multi-Agent tasks.¶

This document describes a scheduling framework for coordinating update and query processing in a multi-Worker Agent service discovery node. To estimate the demand of each workload, the framework considers total queued work, waiting time, deadline pressure, recent load, state freshness, and, for updates, the expected freshness gain from processing a pending update. These estimates determine how Worker capacity is divided between the two queues, which remain active in parallel.¶

The framework also incorporates update merging and deduplication, freshness-aware dependencies between state updates and discovery queries, hysteresis-based resource reallocation, minimum resource holding time, and intra-queue task prioritization. Different deployment conditions can be accommodated by adjusting the corresponding weights and thresholds without changing the scheduling structure itself.¶

2. Terminology

This section defines the terms used throughout this document.¶

Agent: For the purposes of this document, an Agent is a software or physical entity capable of performing tasks or providing services and whose information may be registered with an Agent service discovery node.¶

Agent Service Discovery Node: A logical node that maintains information about registered Agents and processes discovery requests used to identify Agents that satisfy specified task requirements.¶

Dynamic Agent State: Information describing an Agent that may change during operation and may affect subsequent Agent-selection decisions. Examples include current workload, remaining computing capacity, availability status, QoS conditions, and location.¶

Update Task: A processing task generated by Agent registration or by an update to Agent information maintained by the service discovery node. In this document, update tasks primarily refer to dynamic state updates unless otherwise specified.¶

Query Task: A processing task generated by a discovery request that searches for or selects one or more Agents according to specified task requirements.¶

Update Queue : The queue containing update tasks that have been received by the service discovery node but have not yet completed processing.¶

Query Queue : The queue containing discovery query tasks that have been received by the service discovery node but have not yet completed processing.¶

Worker: A logical processing unit within the service discovery node that can be allocated to update processing or query processing. A Worker may correspond to a processing thread, process, execution slot, or another implementation-specific unit of parallel processing capacity.¶

Age of Information (AoI): The elapsed time since the generation of the freshest state information currently available at the service discovery node.AoI is used in this document to characterize the freshness of dynamic Agent state.¶

Maximum Acceptable Information Age: A state-specific freshness bound that represents how old a dynamic Agent state may become before it is considered insufficiently fresh for the relevant service-discovery operation.¶

Deadline Pressure: A relative measure of how much of a task's acceptable response-time budget has already been consumed. It is used to compare tasks with different latency requirements.¶

Update Benefit: The estimated improvement in information freshness that can be obtained by processing a particular update task.¶

Resource Reallocation: A change in the numbers or proportions of Workers assigned to the update and query workloads.¶

3. Scheduling Framework Overview

4. Update Task Merging and Deduplication

To shorten the update queue, the node retains only the latest unprocessed update for a state when newer values fully supersede older ones.¶

This rule is particularly useful for highly time-sensitive dynamic state. Examples include the current workload, remaining computing capacity, online/offline status, QoS condition, and current location. For these types of states, a newer state generally supersedes an older state.¶

For example, suppose that three consecutive updates are generated for the same state i¶

Equation (2): u_i^1, u_i^2, u_i^3¶

If u_i^3 has already been generated and represents the latest Agent state, processing u_i^1 and u_i^2 afterward provides little practical value. Even if one of the older states is written into the service directory, it will soon be overwritten by u_i^3.¶

When updates arrive frequently or the node is heavily loaded, obsolete entries can consume queue space, Worker capacity, and database-write resources, delaying fresher state information.¶

Updates that have already begun execution are generally allowed to complete because cancellation may require transaction rollback, state recovery, or resource cleanup.¶

The rule applies only to replaceable state. For event logs, cumulative counters, or state transitions that require complete history, older records cannot simply be discarded.¶

5. Representing Queue Pressure by Total Workload

In the Joint-(M, N) policy considered in “Towards the Tradeoff Between Service Performance and Information Freshness”, queue-length thresholds M and N are used as the switching triggers for the update and query queues. This mechanism is based on the number of tasks waiting in each queue and does not distinguish among tasks with different processing costs. In an Agent service discovery node, however, different tasks may require substantially different processing times. Queue length alone may therefore misrepresent the amount of remaining processing work.¶

For example, suppose that the update queue contains 10 tasks, each requiring approximately 10 ms of processing, whereas the query queue contains only 3 tasks, each requiring approximately 100 ms. If only the number of tasks is considered, the update queue appears to be more heavily loaded. In reality, however, the update queue contains approximately 100 ms of remaining work, whereas the query queue contains approximately 300 ms.¶

A simple online-status update may require significantly less processing than an update involving multiple fields of an Agent capability profile. Similarly, a direct Agent-ID lookup may require much less processing than a query that jointly considers capability, workload, QoS, and other filtering conditions.¶

Therefore, the sum of the estimated processing times of all tasks in a queue is used to represent the total workload¶

Equation (3): W = ∑_{j} ŝ_j¶

where W denotes the total workload of the queue and ^sj denotes the estimated processing time of task j.¶

Since the actual processing time of a task cannot be known precisely before completion, ^sj can be estimated using the historical average processing time of tasks of the same type.¶

The workloads of the update queue and the query queue are calculated separately as¶

Equation (4): W_U = ∑_{j∈U} ŝ_j¶

and¶

Equation (5): W_Q = ∑_{j∈Q} ŝ_j¶

where U and Q denote the sets of tasks currently contained in the update queue and the query queue, respectively.¶

The scheduler therefore compares remaining work rather than task count alone.¶

Under a multi-Worker architecture, workload should also be interpreted together with the currently allocated processing capacity. A queue with a large WU may not be critically overloaded if many Workers are already assigned to it. Conversely, even a moderate workload may accumulate rapidly if only a small amount of processing capacity is allocated to the queue.¶

Total workload measures the amount of remaining work, while the subsequent load and resource-allocation mechanisms determine whether the currently assigned capacity is sufficient.¶

This design prevents queue pressure from being overestimated because of a large number of short tasks and prevents it from being underestimated because of a small number of long tasks. It is therefore more suitable than simple task counts for heterogeneous Agent service discovery workloads.¶

6. Urgency Score of the Update Queue

The primary function of the update queue is to maintain dynamic Agent states in the service discovery node. Therefore, the urgency of the update queue should not depend solely on its length or workload. It should also reflect whether the currently stored Agent states have become stale and how much information freshness can be improved by processing particular updates.¶

For state i, let Δ_i(t) denote the current AoI of the state maintained by the service discovery node, and let di denote the maximum acceptable information age of that state. The freshness urgency of state i is defined as¶

Equation (6): A_i(t) = Δ_i(t) / d_i¶

When¶

Equation (7): A_i(t) < 1¶

the state is still within its acceptable freshness range.¶

When¶

Equation (8): A_i(t) ≥ 1¶

the state has reached or exceeded its acceptable information age, indicating that the urgency of the corresponding update should increase.¶

Absolute AoI values are not compared directly because different Agent states may have substantially different freshness requirements. For example, the current workload of an Agent may need to be refreshed on a timescale of seconds or less, whereas a slowly changing capability attribute may tolerate a significantly larger information age.¶

Suppose one state has an AoI of 2 s but a maximum acceptable age of only 1 s, while another state has an AoI of 5 s but can tolerate an age of 30 s. Although the second state has a larger absolute AoI, the first state has already violated its own freshness requirement and should therefore be considered more urgent.¶

By using Δ_i(t) / d_i, heterogeneous states are mapped onto a relatively unified scale. Dynamic states that strongly affect Agent selection can be assigned smaller di, while slowly changing or less time-sensitive states can be assigned larger di. Consequently, under the same absolute AoI, a more time-sensitive state naturally receives a higher urgency score.¶

This also avoids a separate importance term when state criticality is already reflected in d_i.¶

However, the current AoI alone is still insufficient. A highly stale state does not necessarily imply that every pending update for that state is worth processing immediately.¶

For example, the Agent workload currently stored by the discovery node may already be 10 s old, but a pending workload update may itself have been generated 9 s ago. Even if this update is processed immediately, the resulting state will still be relatively stale.¶

Therefore, the actual reduction in AoI produced by an update should also be considered.¶

Let g_j denote the generation time of the state information carried by update task j, and let ^c_j denote the estimated completion time of that task. The expected AoI after completing the task is¶

Equation (9): Δ̂_j^{after} = ĉ_j − g_j¶

Based on this value, the update benefit can be defined as¶

Equation (10): B_j = max(0, (Δ_i(t) − Δ̂_j^{after}) / d_i)¶

A_i(t) measures the severity of current staleness, whereas B_j estimates the freshness gain obtained by processing update j. The two quantities therefore represent different signals.¶

A high current AoI alone does not make every pending update valuable. The scheduler instead favors updates that address stale state and can materially reduce its AoI.¶

Based on these factors, the overall urgency score of the update queue can be expressed as¶

Equation (11): P_U ≈ a_1 W_U + a_2 T_U^{max} + a_3 T_U^{avg} + a_4 A_U + a_5 D_U + a_6 ρ_U + a_7 B_U¶

where P_U denotes the overall urgency of the update queue; W_U denotes the total update workload; T_U^max denotes the maximum waiting time in the update queue; T_U^avg denotes the average waiting time; A_U represents a high AoI urgency value within the queue; D_U represents a high deadline pressure value; ρ_U denotes the recent update load; B_U represents a high update benefit; and a_1,…,a_7 are the corresponding weights.¶

If a particular class of updates has no explicit deadline, the weight associated with DU can be reduced or set to zero. For state updates with explicit SLA or real-time requirements, this weight can be increased.¶

Since these metrics have different units and numerical ranges, they should be normalized before being combined into a weighted score. Equation (11) specifies the relationship among these factors but leaves normalization and weight selection to the implementation.¶

For factors such as AoI urgency, deadline pressure, and update benefit, using the average over the entire queue may be inappropriate. A single highly urgent task may otherwise be diluted by a large number of ordinary tasks. Therefore, the maximum value or the average of the top-k most urgent tasks can be used.¶

The resulting update-queue score therefore reflects the consequences of under-serving the update queue, including backlog growth, deadline pressure, and loss of state freshness.¶

7. Urgency Score of the Query Queue

Query processing primarily needs to deliver discovery results within an acceptable response time. Accordingly, PQ gives greater weight to workload, waiting time, and deadline pressure than to update-specific freshness factors.¶

For query task q, let wq denote its current waiting time and lq denote its maximum acceptable response time. Its deadline pressure can be expressed as¶

Equation (12): D_q = w_q / l_q¶

The ratio between current waiting time and maximum acceptable response time is used instead of the absolute waiting time because different discovery requests may tolerate different delays.¶

For example, suppose one query has already waited 100 ms and has a maximum acceptable response time of 150 ms, while another query has waited 300 ms but can tolerate up to 2 s. Although the second query has waited longer in absolute terms, the first query has already consumed a much larger fraction of its allowable response time and is therefore more urgent.¶

When D_q approaches 1, the query is approaching its maximum acceptable response time. When D_q > 1, the original latency requirement has already been violated.¶

The overall urgency score of the query queue can be expressed as¶

Equation (13): P_Q ≈ b_1 W_Q + b_2 T_Q^{max} + b_3 T_Q^{avg} + b_4 D_Q + b_5 ρ_Q¶

where P_Q denotes the overall urgency of the query queue; W_Q denotes the total query workload; T_Q^max denotes the maximum waiting time; T_Q^avg denotes the average waiting time; D_Q represents a high deadline pressure value among query tasks; ρ_Q denotes the recent query load; and b_1,…,b_5 are the corresponding weights.¶

As with the update-queue score, different metrics should be normalized before weighted aggregation.¶

Agent service discovery introduces an additional issue: a query can be processed quickly but still produce a poor result if the dynamic information on which it relies is stale. For example, if workload, availability, or QoS information has become outdated, the service discovery node may quickly select an Agent that is no longer an appropriate target.¶

However, this freshness problem should not be directly incorporated into P_Q to increase query-side processing capacity. If a query depends on stale information, the corresponding update generally needs acceleration rather than the query itself.¶

Therefore, a separate freshness-risk metric is introduced for query task q. Let S_q denote the set of dynamic states required by the query. Its information freshness risk is defined as¶

Equation (14): F_q = max_{i∈S_q}(Δ_i(t) / d_i)¶

Under¶

Equation (15): F_q < 1¶

the key dynamic states required by the query are still sufficiently fresh, and the query can be processed normally.¶

Under¶

Equation (16): F_q ≥ 1¶

at least one critical state required by the query has reached or exceeded its acceptable information age.¶

If a newer update for the corresponding state is waiting in the update queue, the internal priority of that update should be increased. If necessary, additional processing resources should also be assigned to the update queue.¶

For queries that require sufficiently fresh state information to make a valid Agent-selection decision, the following dependency can be established:¶

Equation (17): Update the required state → Execute the query¶

This distinction maps each cause of urgency to the appropriate resource: excessive query delay calls for query capacity, whereas stale query input calls for update capacity. It also avoids accelerating a query only to return a result based on outdated state.¶

8. Dynamic Adjustment of Processing-Resource Allocation

When the joint update-query scheduling idea of Joint(M, N) is adapted to a multi-Worker Agent service discovery node, the original threshold-triggered server-switching mechanism is no longer used directly. Instead, the framework derives target Worker shares from P_U and P_Q, allowing update and query workloads to be processed concurrently while their relative resource shares change over time.¶

A fixed allocation, such as assigning half of the Workers to updates and half to queries at all times, cannot adapt effectively to dynamic workloads.¶

For example, if almost no Agent state updates are arriving while a large burst of discovery requests occurs, some update-side Workers may remain idle while the query queue grows rapidly. Conversely, if many Agents simultaneously report workload, availability, and QoS changes while only a few queries arrive, a fixed allocation may cause update tasks to accumulate and the states maintained by the discovery node to become increasingly stale.¶

Therefore, when all score components have been normalized and P_U and P_Q are non-negative, a simple target resource ratio can be defined as¶

Equation (18): Equation (18): r_U(t) = P_U(t) / (P_U(t) + P_Q(t))¶

and¶

Equation (19): r_Q(t) = P_Q(t) / (P_U(t) + P_Q(t))¶

where r_U(t) and r_Q(t) denote the target resource proportions for the update and query queues, respectively. They satisfy¶

Equation (20): r_U(t) + r_Q(t) = 1¶

Equations (18) and (19) are applicable when P_U(t) + P_Q(t) > 0. If both queues are idle and both urgency scores are zero, no active resource allocation decision is required.¶

Given K Workers, the approximate target numbers of Workers can be calculated as¶

Equation (21): K_U(t) ≈ K r_U(t)¶

and¶

Equation (22): K_Q(t) ≈ K r_Q(t)¶

The above equations are intended to express the general principle that a more urgent queue should receive a larger proportion of processing resources. The actual mapping between urgency scores and Worker allocation does not have to be strictly linear and can be further refined experimentally.¶

If both queues are non-empty, minimum resource guarantees can also be introduced. For example, at least a small number of Workers can be reserved for each queue so that a temporarily low urgency score does not completely suspend that type of service.¶

Recent load should also account for the task arrival rate, average task-processing time, and the number of Workers currently assigned to the queue.¶

For the update queue, when K_U(t) > 0, the recent load can be approximated by¶

Equation (23): ρ_U(t) ≈ (λ_U(t) s̄_U) / K_U(t)¶

Similarly, for the query queue,¶

Equation (24): ρ_Q(t) ≈ (λ_Q(t) s̄_Q) / K_Q(t)¶

where λ_U(t) and λ_Q(t) denote the recent average arrival rates of update and query tasks, respectively; ˉs_U and ˉs_Q denote their average processing times; and K_U(t) and K_Q(t) denote the currently allocated numbers of Workers.¶

When the load of a queue satisfies¶

Equation (25): ρ > 1¶

the average incoming workload exceeds the average processing capacity currently allocated to that queue. If this condition persists, the queue will continue to accumulate tasks, indicating that additional processing resources may be required.¶

Compared with the simple approximation ρ ≈ λˉs, explicitly incorporating the number of allocated Workers is more appropriate for a multi-Worker Agent service discovery node because the same task arrival rate can impose substantially different pressure when two Workers are allocated than when ten Workers are allocated.¶

Under this allocation rule, a burst of discovery traffic shifts capacity toward queries, whereas rapid state aging or a burst of Agent state reports shifts capacity toward updates.¶

9. Resource Reallocation Conditions

Although the target resource ratios can be recalculated from P_U and P_Q, reallocating Workers whenever the urgency scores change slightly may itself introduce substantial overhead.¶

For example, the current Worker allocation may be 4:6 between the update and query queues. After several update tasks arrive, the target allocation may become 5:5. Shortly afterward, several query tasks may arrive and the target allocation may return to 4:6. If every small change immediately triggers Worker reallocation, the system may incur frequent Worker reassignment, task migration, cache disturbance, and database-connection adjustment.¶

Here, hysteresis governs changes to the Worker split rather than switching a single server between queues.¶

Let r_U^new denote the newly calculated target resource proportion of the update queue and r_U^cur denote its current actual resource proportion. Normal resource reallocation is performed only when¶

Equation (26): |r_U^{new} − r_U^{cur}| > H¶

where H is the resource-allocation hysteresis threshold.¶

If the difference between the new target allocation and the current allocation is small, the existing Worker allocation is retained. Reallocation occurs only after queue conditions have changed enough to justify it.¶

The resource reallocation conditions can include the following cases.¶

(1) If one queue becomes empty, some of its idle Workers may be temporarily reassigned to the other non-empty queue. (2) If the difference between the target resource ratio and the current ratio exceeds H, and the minimum resource holding time has been satisfied, normal reallocation is performed. (3) If the workload or maximum waiting time of a queue increases rapidly and indicates clear backlog risk, resource adjustment may be triggered earlier. (4) If the AoI of a critical Agent state significantly exceeds its acceptable limit, additional update Workers may be allocated temporarily. (5) If a high-priority discovery request is approaching a hard deadline, additional query Workers may be allocated temporarily. (6) If multiple queries depend on a severely stale state, additional update resources may be assigned so that the required state can be refreshed as quickly as possible.¶

An extremely urgent task does not necessarily require all Workers to be transferred to one queue. For example, if a node has 10 Workers with a current allocation of 3 update Workers and 7 query Workers, an urgent state update may cause a temporary adjustment to 5:5 rather than completely suspending query processing.¶

This preserves concurrent service and better reflects a multi-Worker node than full queue switching.¶

Hysteresis filters minor score fluctuations, while emergency overrides allow immediate responses to critically stale state or deadline-sensitive discovery requests. The two mechanisms trade allocation stability against responsiveness.¶

10. Minimum Resource Holding Time

A resource-allocation hysteresis threshold alone may still be insufficient to prevent frequent resource changes.¶

For example, suppose the service discovery node has just increased the number of update Workers from 3 to 6. After these Workers quickly process a group of pending updates, the urgency of the update queue may immediately decrease. If the Workers are immediately reassigned to the query queue, the resulting allocation may remain active for too little time to amortize its reconfiguration cost.¶

The model in Joint(M, N) assumes negligible overhead when the server switches back and forth between the update and query queues, and identifies the impact of switching cost as an open issue. In a practical multi-Worker Agent service discovery node, however, changes in Worker allocation may incur non-negligible overhead, including Worker reassignment, context migration, cache disruption, and database-connection adjustment. This document therefore introduces a minimum resource holding time to prevent short-lived reallocations from causing excessive reconfiguration overhead.¶

Let t_last denote the time of the most recent resource reallocation, t the current time, and T_min the minimum resource holding time. Under normal conditions, another resource reallocation is allowed only when¶

Equation (27): t − t_last ≥ T_min¶

Once a new allocation takes effect, it remains active for at least T_min under normal conditions, allowing its reconfiguration overhead to be amortized before another adjustment occurs.¶

The value of T_min can be determined according to the actual Worker reconfiguration cost. If Worker reassignment, context migration, cache disturbance, or database-connection adjustment is expensive, a larger T_min can be used. If Worker allocation can be modified with very low overhead, a smaller T_min can be selected to improve responsiveness.¶

The implementation need not rely solely on elapsed time. Equivalent alternatives include requiring the newly allocated resources to process a minimum number of tasks, complete a minimum amount of workload, or remain active for a minimum period. The underlying objective is to prevent rapid oscillation of processing resources between the two queues.¶

The minimum holding time should not, however, become an absolute constraint for extremely urgent tasks. If a critical Agent state becomes severely stale or a query is about to violate a hard deadline, the current holding period can be terminated early and the Workers can be immediately reallocated.¶

Even without an emergency, PU, PQ, and the target shares should be recomputed periodically so that the active allocation does not drift out of alignment with longer-term workload changes.¶

11. Intra-Queue Task Scheduling

The queue-level scores P_U and P_Q determine how Workers are divided between update and query processing, but a second decision remains: which task within each queue should run next. FIFO alone can leave a high-urgency task behind ordinary work, so each queue also applies an internal task priority.¶

For update task j, the internal priority can be expressed as¶

Equation (28): p_j^U ≈ c_1 A_i(t) + c_2 B_j + c_3 D_j + c_4 w_j¶

where p_j^U denotes the internal priority of update task j; A_i denotes the AoI urgency of its corresponding Agent state; B_j denotes the update benefit; D_j denotes the task deadline pressure; w_j denotes the time the task has already waited; and c_1,…,c_4 are the corresponding weights.¶

Higher priority is assigned to updates associated with stale state, substantial AoI reduction, approaching deadlines, or long waiting times.¶

For example, multiple Agent state updates may be waiting at the same service discovery node. One task may represent an ordinary capability-attribute change, whereas another may report that an Agent has changed from a low-load state to a high-load state and that many discovery requests may rely on this workload information. The latter update can receive a higher internal priority because it has a more direct effect on subsequent Agent-selection decisions.¶

If the importance of a state has already been reflected by a smaller di, an additional independent importance term is not required, thereby avoiding repeated weighting of the same factor.¶

For query task q, the internal priority can be expressed as¶

Equation (29): p_q^Q ≈ e_1 D_q + e_2 w_q¶

where p_q^Q denotes the internal priority of query task q; D_q denotes its deadline pressure; w_q denotes its current waiting time; and e_1 and e_2 are the corresponding weights.¶

The freshness of the states required by the query is deliberately not included directly in the query task priority.¶

Stale query input should normally increase the priority of the corresponding update rather than the query itself. Accelerating the query alone could produce an Agent-selection result more quickly without improving the freshness of its input.¶

Therefore, when Fq ≥ 1, the update-query dependency mechanism described above should be applied. The corresponding state update receives higher priority, and, if the update queue lacks sufficient resources, K_U(t) may also be increased. The priority of the query itself is increased directly only when the query has waited for a long time or is approaching its deadline.¶

If multiple tasks have the same internal priority, FIFO can be used as a secondary tie-breaking rule.¶

Waiting time remains in both priority functions to prevent starvation. Even a task with low initial AoI urgency, update benefit, or deadline pressure gradually gains priority as it waits.¶

The two levels therefore separate resource allocation between queues from task selection within each queue.¶

12. Deployment Considerations

The scheduling structure remains unchanged across deployments, but the relative importance of its inputs can vary. Interactive services tend to be latency-sensitive, rapidly changing state increases freshness pressure, and high-concurrency deployments place greater weight on backlog and allocation stability.¶

These differences can be expressed through the existing weights and thresholds, including d_i, l_q, H, and T_min, without introducing a separate scheduling algorithm for each deployment.¶

15. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.