Service-oriented architectures allow content providers to enable easy and transparent access to multimedia content for their clients as well as outsource non-strategic streaming services to thirdparty providers. We design a QoS framework and associated algorithms that can provide prioritized and fair media streaming based on service level agreements. We formulate the QoS support as a Multiple Choice Multiple Knapsack optimization and design several low-complexity algorithms to provide approximate solutions. We bound the performance of these algorithms, and evaluate them in terms of the number of clients supported and QoS provided over realistic simulation scenarios.