| Kamal Jain, Jitendra Padhye, Venkata N. Padmanabhan, Lili Qiu
This paper addresses the question of determining the maximum throughput that can be supported by a multi-hop wireless network given a specific placement of nodes and traffic workload. Unlike previous work that focused on asymptotic performance bounds under assumptions of homogeneity or randomness, this study considers any given network and workload as inputs. A key challenge is wireless interference between neighboring nodes, which is modeled using a conflict graph. This graph indicates which links mutually interfere and cannot be active simultaneously. The paper formulates a multi-commodity flow problem augmented with constraints from the conflict graph to compute the optimal throughput. It shows that finding optimal throughput is NP-hard and presents methods for computing upper and lower bounds. The analysis suggests that interference-aware routing can achieve better throughput than default shortest path routing, even in the presence of uncoordinated transmissions and MAC contention. The paper also discusses various network characteristics, such as multiple channels, multiple radios, and directional antennas, and how they can be incorporated into the model. It evaluates how per-node throughput varies with the number of nodes and shows that adding new nodes can improve throughput by providing more routing opportunities around interference "hotspots." The paper also discusses related work, including studies on asymptotic bounds, mobility, and network coding. It presents results from simulations showing that the routes derived from the analysis often yield better throughput than default routes. The paper concludes that the conflict graph model is a key contribution, enabling the computation of upper and lower bounds on optimal throughput for a given network and workload.This paper addresses the question of determining the maximum throughput that can be supported by a multi-hop wireless network given a specific placement of nodes and traffic workload. Unlike previous work that focused on asymptotic performance bounds under assumptions of homogeneity or randomness, this study considers any given network and workload as inputs. A key challenge is wireless interference between neighboring nodes, which is modeled using a conflict graph. This graph indicates which links mutually interfere and cannot be active simultaneously. The paper formulates a multi-commodity flow problem augmented with constraints from the conflict graph to compute the optimal throughput. It shows that finding optimal throughput is NP-hard and presents methods for computing upper and lower bounds. The analysis suggests that interference-aware routing can achieve better throughput than default shortest path routing, even in the presence of uncoordinated transmissions and MAC contention. The paper also discusses various network characteristics, such as multiple channels, multiple radios, and directional antennas, and how they can be incorporated into the model. It evaluates how per-node throughput varies with the number of nodes and shows that adding new nodes can improve throughput by providing more routing opportunities around interference "hotspots." The paper also discusses related work, including studies on asymptotic bounds, mobility, and network coding. It presents results from simulations showing that the routes derived from the analysis often yield better throughput than default routes. The paper concludes that the conflict graph model is a key contribution, enabling the computation of upper and lower bounds on optimal throughput for a given network and workload.