Size-Based Routing Policies: Non-Asymptotic Analysis and Design of Decentralized Systems

Area of Science:

• Computer Science
• Operations Research
• Performance Analysis

Background:

• Size-based routing policies are effective for high job size variance.
• Task Assignment with Guessing Size (TAGS) and Size Interval Task Assignment (SITA) are two such policies.
• SITA assumes job sizes are known, while TAGS does not.

Purpose of the Study:

• To analyze the performance ratio between TAGS and SITA in non-asymptotic regimes.
• To compare TAGS with a variant of SITA (SITA-E) across arbitrary numbers of servers.
• To provide insights for designing decentralized systems with quality of service constraints.

Main Methods:

• Analysis of mean waiting times for TAGS and SITA.
• Mathematical modeling of job size distributions (Bounded Pareto).
• Comparison of performance ratios under varying server counts and traffic conditions.

Main Results:

• For two servers and Bounded Pareto (α=1) job sizes, the TAGS/SITA waiting time ratio is unbounded.
• In light traffic, the performance ratio is unbounded for Bounded Pareto (α=1) with any number of servers.
• The ratio is also unbounded for Bounded Pareto (α∈(0,2)\{1}) as the number of servers approaches infinity.

Conclusions:

• The performance gap between TAGS and SITA can be significantly larger than previously thought.
• These findings are crucial for optimizing load balancing and resource allocation in distributed systems.
• Results inform the design of decentralized systems prioritizing quality of service.