We consider the problem of distributed admission control without knowledge of the capacity region in single-hop wireless networks, for flows that require a pre-specified bandwidth from the network. We present an optimization framework that allows us to design a scheduler and resource allocator, and by properly choosing a suitable utility function in the resource allocator, we prove that existing flows can be served with a pre-specified bandwidth, while the link requesting admission can determine the largest rate that it can get such that it does not interfere with the allocation to the existing flows.
Under the assumption that requests can be split, @cite_26 proposes a solution for multi-hop multichannel networks. If the requests cannot be split, a heuristic is presented using the least-congested, minimum-hop path to route requests.
@cite_26
1970554468
Modern cloud infrastructure providers allow customers to rent computing capability in the form of a network of virtual machines (VMs) with bandwidth guarantees between pairs of VMs. Typical requests are in the form of a chain of VMs with an uplink bandwidth to the gateway node of the network (rooted path requests), and most data center architectures route network packets along a spanning tree of the physical network. VMs are instantiated inside servers which reside at the leaves of this network, leading to the following optimization problem: given a rooted tree network T and a set of rooted path requests, find an embedding of the requests that minimizes link congestion. Our main result is an algorithm that, given a rooted tree network T with n leaves and set of weighted rooted path requests, embeds a 1e fraction of the requests with congestion at most poly(logn, log,e1)OPT (approximation is necessary since the problem is NP-hard). Here OPT is the congestion of the optimal embedding and  is the ratio of the maximum to minimum weights of the path requests. We also obtain an O(Hlogn e2) approximation if node capacities can be augmented by a (1+e) factor (here H is the height of the tree). Our algorithm applies a randomized rounding scheme based on Group Steiner Tree rounding to a novel LP relaxation of the set of subtrees of T with a given number of leaves that may be of independent interest.