We consider the load-balancing design for forwarding incoming flows to access points (APs) in high-density wireless networks with both channel fading and flow-level dynamics, where each incoming flow has a certain amount of service demand and leaves the system once its service request is complete. The efficient load-balancing design is strongly needed for supporting high-quality wireless connections in high-density areas. In this work, we propose a Joint Load-Balancing and Scheduling (JLBS) Algorithm that always forwards the incoming flows to the AP with the smallest workload in the presence of flow-level dynamics and each AP always serves the flow with the best channel quality. Our analysis reveals that our proposed JLBS Algorithm not only achieves maximum system throughput, but also minimizes the total system workload in the heavy-traffic regime. Moreover, we observe from both our theoretical and simulation results that the mean total workload performance under the proposed JLBS Algorithm does not degrade as the number of APs increases, which is strongly desirable in high-density wireless networks.
more »
« less
Throughput bound minimization for random access channel assignment
Throughput extremization is an important facet of performance modeling for low-power wide-area network (LP-WAN) wireless networks (e.g., LoRaWAN) as it provides insight into the best and worst case behavior of the network. Our previous work on throughput extremization established lower and upper bounds on throughput for random access channel assignment over a collision erasure channel in which the lower bound is expressed in terms of the number of radios and sum load on each channel. In this paper the lower bound is further characterized by identifying two local minimizers (a load balanced assignment and an imbalanced assignment) where the decision variables are the number of radios assigned to each channel and the total load on each channel. A primary focus is to characterize how macro-parameters of the optimization, i.e., the total number of radios, their total load, and the minimum load per radio, determine the regions under which each of the local minimizers is in fact the global minimizer.
more »
« less
- Award ID(s):
- 1816387
- NSF-PAR ID:
- 10355782
- Date Published:
- Journal Name:
- 2021 19th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)
- Page Range / eLocation ID:
- 1 to 8
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract Motivation The minimizers technique is a method to sample k-mers that is used in many bioinformatics software to reduce computation, memory usage and run time. The number of applications using minimizers keeps on growing steadily. Despite its many uses, the theoretical understanding of minimizers is still very limited. In many applications, selecting as few k-mers as possible (i.e. having a low density) is beneficial. The density is highly dependent on the choice of the order on the k-mers. Different applications use different orders, but none of these orders are optimal. A better understanding of minimizers schemes, and the related local and forward schemes, will allow designing schemes with lower density and thereby making existing and future bioinformatics tools even more efficient.
Results From the analysis of the asymptotic behavior of minimizers, forward and local schemes, we show that the previously believed lower bound on minimizers schemes does not hold, and that schemes with density lower than thought possible actually exist. The proof is constructive and leads to an efficient algorithm to compare k-mers. These orders are the first known orders that are asymptotically optimal. Additionally, we give improved bounds on the density achievable by the three type of schemes.
-
more » « less
As the demand for wireless capacity continues to grow, highly directional wireless communication technologies have the potential to provide massive gains in area spectral efficiency. However, novel challenges arise when considering bidirectional connectivity and multi-cell/multi-user systems with highly directional links. Some of these challenges can be alleviated with the introduction of asymmetric connectivity where the highly directional links are used solely for downlink transmission. As an example, we consider asymmetric links with an optical wireless communication (OWC) downlink and sub-6 GHz RF uplink. More specifically, we consider visible light communication as an instance of OWC, although the presented analysis and validation are applicable to alternative OWC technologies and other simplex downlink transmission technologies. While asymmetric connectivity has been previously demonstrated in scenarios like this, the impact of control-plane asymmetry has not been explored, to our knowledge. In this paper, we first introduce the novel challenges related to local handshaking in wireless networks with control-plane asymmetry. We then develop a theoretical framework for throughput analysis in a network where the sub-6 GHz RF channel is shared between a conventional RF link and an asymmetric RF/OWC link. This analysis is validated via simulation and verified in a testbed system using Mango WARP3 software defined radios and a commercially available RF access point. Finally, we use the derived throughput equations to analyze the impact of various protocol parameters and demonstrate one potential use of the derived equations to evaluate sum throughput in the presence of an unreliable OWC link.
-
Oblivious routing has a long history in both the theory and practice of networking. In this work we initiate the formal study of oblivious routing in the context of reconfigurable networks, a new architecture that has recently come to the fore in datacenter networking. These networks allow a rapidly changing bounded-degree pattern of interconnections between nodes, but the network topology and the selection of routing paths must both be oblivious to the traffic demand matrix. Our focus is on the trade-off between maximizing throughput and minimizing latency in these networks. For every constant throughput rate, we characterize (up to a constant factor) the minimum latency achievable by an oblivious reconfigurable network design that satisfies the given throughput guarantee. The trade-off between these two objectives turns out to be surprisingly subtle: the curve depicting it has an unexpected scalloped shape reflecting the fact that load-balancing becomes more difficult when the average length of routing paths is not an integer because equalizing all the path lengths is not possible. The proof of our lower bound uses LP duality to verify that Valiant load balancing is the most efficient oblivious routing scheme when used in combination with an optimally-designed reconfigurable network topology. The proof of our upper bound uses an algebraic construction in which the network nodes are identified with vectors over a finite field, the network topology is described by either the elementary basis or a sequence of Vandermonde matrices, and routing paths are constructed by selecting columns of these matrices to yield the appropriate mixture of path lengths within the shortest possible time interval.more » « less
-
Jurdziński, T ; Schmid, S (Ed.)In the multiparty equality problem, each of the n nodes starts with a k-bit input. If there is a mismatch between the inputs, then at least one node must be able to detect it. The cost of a multiparty equality protocol is the total number of bits sent in the protocol. We consider the problem of minimizing this communication cost under the local broadcast model for the case where the underlying communication graph is undirected. In the local broadcast model of communication, a message sent by a node is received identically by all of its neighbors. This is in contrast to the classical point-to-point communication model, where a message sent by a node to one of its neighbors is received only by its intended recipient. Under point-to-point communication, there exists a simple protocol which is competitive within a factor 2 of the lower bound [1]. In this protocol, a rooted spanning tree is fixed and each node sends its entire input to its parent in the tree. On receiving a value from its child, a node compares it against its own input to check if the two values match. Ignoring lower order additive terms, a more complicated protocol comes within a factor 4/3 of the lower bound and is tight for certain classes of graphs [1]. Tight results, ignoring lower order terms, are also known for complete graphs [2, 9]. We study the multiparty equality problem under the local broadcast model. Recently, our work has shown that the connectivity requirements for Byzantine consensus are lower in the local broadcast model as compared to the classical model [7, 8]. In this work, 1. we identify a lower bound for the multiparty equality problem in this model. 2. we first identify simple protocols, wherein nodes are restricted to either transmit their entire input or not transmit anything at all, and find that these can cost Ω(logn) times the lower bound using existing example for the set cover problem [12]. 3. we then design a protocol to solve the problem within a constant factor of the lower bound.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.23919/WiOpt52861.2021.9589241
