Provisioning a virtual private network

摘要: Consider a setting in which group of nodes, situated large underlying network, wishes to reserve bandwidth on support communication. Virtual private networks (VPNs) are services that such construct; rather than building new physical network the nodes must be connected, is reserved for communication within group, forming virtual “sub-network.”Provisioning over set off terminals gives rise following general design problem. We have bounds cumulative amount traffic each terminal can send and receive; we choose path pair terminals, allocation edge so any matrix consistent with given upper feasibly routed. Thus, seeking continuum possible scenarios.We provide optimal approximate algorithms several variants this problem, depending whether required symmetric, designed tree (a natural constraint number basic applications). also establish relation between collection problems variant facility location problem introduced by Karger Minkoff; extend their results providing stronger approximation algorithm latter