Network multimedia applications require certain performance guarantees that can be provided through proper resource allocation. Allocation techniques are needed to provide these guarantees as efficiently as possible since resources are limited. This paper presents an allocation method called Dynamic Search Algorithm (DSA+). DSA+ is an on-line algorithm that dynamically adjusts the resource allocation based upon the measured quality of service. Advantages of DSA+ include efficient use of resources, reasonable implementation cost and stringent quality of service control. In this paper we demonstrate how DSA+ dynamically allocates bandwidth to achieve a given loss rate for actual variable bit rate MPEG videos. Performance and cost advantages over other allocation methods are presented, as well as allocation for multiple hop connections.