In an input-queued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed for each switching cycle, or time slot. It is a challenging research problem to design switching algorithms that produce high-quality matchings yet have a very low computational complexity when the switch has a large number of ports. Indeed, there appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the quality of the computed matchings.
Parallel maximal matching algorithms (adapted for switching) appear to be a sweet tradeoff point in this regard. On one hand, they provide the following performance guarantees: Using maxi- mal matchings as crossbar schedules results in at least 50% switch throughput and order-optimal (i.e., independent of the switch size 𝑁 ) average delay bounds for various traffic arrival processes. On the other hand, their computational complexities can be as low as 𝑂 (log_2 𝑁) per port/processor, which is much lower than those of the algorithms for finding matchings of higher qualities such as maximum weighted matching.
In this work, we propose QPS-r, a parallel iterative switching
algorithm that has the lowest possible computational complexity:
𝑂(1) per port. Yet, the matchings that QPS-r computes have the
same quality as maximal matchings in the following sense: Using
such matchings as crossbar schedules results in exactly the same
aforementioned provable throughput and delay guarantees as using
maximal matchings, as we show using Lyapunov stability analysis.
Although QPS-r builds upon an existing add-on technique called
Queue-Proportional Sampling (QPS), we are the first to discover
and prove this nice property of such matchings. We also demon-
strate that QPS-3 (running 3 iterations) has comparable empirical
throughput and delay performances as iSLIP (running log 𝑁 itera- 2
tions), a refined and optimized representative maximal matching algorithm adapted for switching.
more »
« less
SERENADE: A Parallel Iterative Algorithm for Crossbar Scheduling in Input-Queued Switches
In an input-queued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed for each switching cycle, or time slot. It is a challenging research problem to design switching algorithms that produce high-quality matchings yet have a very low computational complexity when the switch has a large number of ports. Indeed, there appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the quality of the computed matchings.
Parallel maximal matching algorithms (adapted for switching) appear to be a sweet tradeoff point in this regard. On one hand, they provide the following performance guarantees: Using maxi- mal matchings as crossbar schedules results in at least 50% switch throughput and order-optimal (i.e., independent of the switch size 𝑁 ) average delay bounds for various traffic arrival processes. On the other hand, their computational complexities can be as low as 𝑂 (log2 𝑁 ) per port/processor, which is much lower than those of the algorithms for finding matchings of higher qualities such as maximum weighted matching.
In this work, we propose QPS-r, a parallel iterative switching
algorithm that has the lowest possible computational complexity:
𝑂(1) per port. Yet, the matchings that QPS-r computes have the
same quality as maximal matchings in the following sense: Using
such matchings as crossbar schedules results in exactly the same
aforementioned provable throughput and delay guarantees as using
maximal matchings, as we show using Lyapunov stability analysis.
Although QPS-r builds upon an existing add-on technique called
Queue-Proportional Sampling (QPS), we are the first to discover
and prove this nice property of such matchings. We also demon-
strate that QPS-3 (running 3 iterations) has comparable empirical
throughput and delay performances as iSLIP (running log 𝑁 itera- 2
tions), a refined and optimized representative maximal matching algorithm adapted for switching.
more »
« less
- Award ID(s):
- 1909048
- NSF-PAR ID:
- 10167952
- Date Published:
- Journal Name:
- 2020 IEEE 21st International Conference on High Performance Switching and Routing (HPSR)
- Page Range / eLocation ID:
- 1 to 6
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)In this work, we first propose a parallel batch switching algorithm called Small-Batch Queue-Proportional Sampling (SB-QPS). Compared to other batch switching algorithms, SB-QPS significantly reduces the batch size without sacrificing the throughput performance and hence has much lower delay when traffic load is light to moderate. It also achieves the lowest possible time complexity of O(1) per matching computation per port, via parallelization. We then propose another algorithm called Sliding-Window QPS (SW-QPS). SW-QPS retains and enhances all benefits of SB-QPS, and reduces the batching delay to zero via a novel switching framework called sliding-window switching. In addition, SW-QPS computes matchings of much higher qualities, as measured by the resulting throughput and delay performances, than QPS-1, the state-of-the-art regular switching algorithm that builds upon the same underlying bipartite matching algorithm.more » « less
-
We propose distributed scheduling algorithms that guarantee a constant fraction of the maximum throughput for typical wireless topologies, and have O(1) delay and complexity in the network size. Our algorithms resolve collisions among pairs of conflicting nodes by assigning a master-slave hierarchy. When the master-slave hierarchy is chosen randomly, our algorithm matches the throughput performance of the maximal scheduling policies, with a complexity and delay that do not scale with network size. When the master-slave hierarchy is chosen based on the network topology, the throughput performance of our algorithm is characterized by a parameter of the conflict graph called the master-interference degree. For commonly-used conflict-graph topologies, our results lead to the best known throughput guarantees among the algorithms that have O(1) delay and complexity. Numerical results indicate that our algorithms outperform the existing O(1) complexity algorithms like Q-CSMA.more » « less
-
We study the problem of scheduling VMs (Virtual Machines) in a distributed server platform, motivated by cloud computing applications. The VMs arrive dynamically over time to the system, and require a certain amount of resources (e.g. memory, CPU, etc) for the duration of their service. To avoid costly preemptions, we consider non-preemptive scheduling: Each VM has to be assigned to a server which has enough residual capacity to accommodate it, and once a VM is assigned to a server, its service cannot be disrupted (preempted). Prior approaches to this problem either have high complexity, require synchronization among the servers, or yield queue sizes/delays which are excessively large. We propose a non-preemptive scheduling algorithm that resolves these issues. In general, given an approximation algorithm to Knapsack with approximation ratio r , our scheduling algorithm can provide rβ fraction of the throughput region for β < r. In the special case of a greedy approximation algorithm to Knapsack, we further show that this condition can be relaxed to β<1. The parameters β and r can be tuned to provide a tradeoff between achievable throughput, delay, and computational complexity of the scheduling algorithm. Finally extensive simulation results using both synthetic and real traffic traces are presented to verify the performance of our algorithm.more » « less
-
Finding from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems that attempt to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker for subgraph finding algorithms, which adopts a task-based computation model, and which also provides a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph finding algorithms that can be easily adapted from existing serial algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the idle time of CPU cores. To further improve load balancing on graphs where the workloads of individual tasks can be drastically different due to biased graph density distribution, we propose to prioritize the scheduling of those tasks that tend to be long running for processing and decomposition, plus a timeout mechanism for task decomposition to prevent long-running straggler tasks. The idea has been integrated into a novelty algorithm for maximum clique finding (MCF) that adopts a hybrid task decomposition strategy, which significantly improves the running time of MCF on dense and large graphs: The algorithm finds a maximum clique of size 1,109 on a large and dense WikiLinks graph dataset in 70 minutes. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/HPSR48589.2020.9098995
