The All-or-Nothing Multicommodity Flow Problem

Date Added: Nov 2009
Format: PDF

A pervasive problem in communication networks is that of allocating bandwidth to satisfy a given collection of service requests. In situations where there is limited network capacity but an abundance of requests, one must optimize over the choice of which requests to satisfy. Such maximization problems arise for instance in the area of bandwidth trading, or when operators carve out subnets (so called VPNs) within their network, for sale to interested enterprise customers. Constraints on how bandwidth may be allocated vary according to the type of requesting service, as well as the technology in the underlying network.