Host-Bypass: Approximating Node-Weighted Connectivity Problems in Two-Tier Networks
The authors focus on network design problems in those networks which have two distinct sets or tiers of network nodes: hosts and infrastructure nodes. For instance, wireless mesh networks are often composed of the infrastructure nodes which relay the data between the client nodes. Similarly, the switches (infrastructure) in data center networks sit between the servers (hosts) to route the information flow. In such two-tier networks, a network designer typically requires paths between hosts in the host-tier through nodes in the infrastructure-tier while minimizing the cost in building the network. A subtle constraint, which they call as the host-tier constraint, in choosing such paths requires that no host in host-tier is an intermediate node on any path.