We consider rate-distortion (RD) optimized multi-flow video delivery in unstructured overlay networks. We show that this problem can be studied as a distributed rate allocation. To solve the problem over the participating peers in the overlay, we apply classical decomposition techniques such that the network-wide utility of video distortion is minimized. Media packets are assumed to be piggy-backed with RD preambles that contain information regarding their impact on decoder video distortion and their size. This allows for converting the calculated optimal rate allocation at every node into simple forwarding or dropping actions. Furthermore, the proposed distributed media streaming framework employs a network inference algorithm for minimizing the flow of duplicate packets over the network and utilizing thus more efficiently the available resources. Our simulation results indicate that significant quality benefits can be achieved when the precise RD characteristics of a media presentation are taken into account.