User-specified Adaptive Scheduling in a StreamingMedia NetworkMichael Hicks, Adithya Nagarajan Robbert van RenesseDepartment of Computer Science Department of Computer ScienceUniv. of Maryland, College Park, MD Cornell Univ., Ithaca, [email protected], [email protected] [email protected]—In disaster and combat situations, mobile camerasand other sensors transmit real-time data, used by many op-erators or analysis tools. Unfortunately, in the face of limited,unreliable resources, and varying demands, not all users maybe able to get the fidelity they require. This paper describesMediaNet, a distributed stream processing system designed withthe above scenarios in mind. Unlike past approaches, MediaNet’susers can intuitively specify how the system should adapt basedon their individual needs. MediaNet uses both local and on-line global resource scheduling to improve user performanceand network utilization, and adapts without requiring underlyingsupport for resourcereservations.Performance experiments showthat our scheduling algorithm is reasonably fast, and thatuser performance and network utilization are both significantlyimproved.I. INTRODUCTIONConsider a dangerous setting, such as collapsed buildingscaused by an earthquake or terrorist attack. Novel recordingdevices, such as cameras carried by Uninhabited Aerial Ve-hicles (UAVs) or by robots that crawl through rubble, maybe deployed to explore the area. The output of these devicescan be of interest to many operators. Operators may includerescue workers working in the rubble itself, people overseeingthe work in a station somewhere, the press, or software thatcreates, say, a 3-dimensional model of the scene.Different operators may require different views of the area,and may have different fidelity requirements or user priorities.Although the operators may work independently of one an-other, they share many resources, such as the recording devicesthemselves, compute servers, and networks. These resourceshave limited capacity, and so they must be allocated carefully.Without resource reservation, adaptivity is essential.The conditions present in this disaster situation are notunique. That is, many applications consist of multiple oper-ators interested in streaming data from multiple sources thatmust adapt to limited resources, potentially in application-specific ways. Examples include the exchange and aggregationof sensor reports [1], the distribution of media on a homenetwork [2], the performing of reconnaissance and deploymentin a military setting [3], and so on.A number of projects have explored how to provide im-proved quality of service (QoS) for streaming media inThis work was funded in part by DARPA grant F30620-98-2-0198,DARPA/AFRL-IFGA grant F30602-99-1-0532, a grant under NASA’s REEprogram administered by JPL, NSF-CISE grant 9703470,and the AFRL-IFGAInformation Assurance Institute under grant AFOSR F49620-01-1-0312.resource-limited conditions. These systems place computationsin the network, either within routers themselves (e.g., [4], [5],[6]) or at the application-level using an overlay network (e.g.,[7], [8]), and employ system-determined, local adaptations,such as priority-based video frame dropping. While suchadaptations impose little overhead, they can be inefficientbecause they do not take into account global information. Also,existing schemes typically do not consider user preferences inmaking QoS decisions.To study whether these problems can be overcome, we aredeveloping a system called MediaNet that takes a compre-hensive view of streaming data delivery. MediaNet mainlydiffers from past approaches in two ways. First, rather thanmake QoS adaptation system-determined, MediaNet allowsusers to specify how it should adapt under overload conditions.Each user contributes a list of alternative specifications, andassociates a utility value with each specification. To someusers, color depth may be more important than frame rate,while for other users the preference may be the other wayaround. The primary goal of MediaNet is to maximize eachuser’s utility.Second, in addition to using local scheduling, MediaNetemploys a global scheduling service to divide tasks andflows among network components. This global point of viewhas benefits to both fairness and performance, because theservice can consider specifications from multiple users whileaccounting for priority and overall network efficiency; thechallenge is to do this in a scalable manner. Different fromother projects that use global schedulers (e.g., [5], [9], [2]),MediaNet’s global scheduling service is continuously lookingfor improvements based on monitoring feedback. MediaNetemploys a completely adaptive overlay network; it does notrely on resource reservations, and adapts to loads not underits control.Experimental measurements with our prototype implemen-tation are promising: users achieve better performance andthe network is more efficiently utilized than without any orwith only local adaptations. On the other hand, our systemdoes exact a higher cost for its global adaptations, in termsof overhead and implementation complexity. We consider ourwork as a step to exploring how to synergistically applyadaptations from various levels in a scheduling hierarchy.In this paper, we describe the MediaNet architecture (Sec-tion II) and our prototype implementation (Section III).We focus on the challenges of implementing a globally-Scheduling ServiceCompute Serversand Wireless User DevicesCameras, SensorsWorkstationsFig. 1. MediaNet architecture.reconfigurable stream processing system, and show experimen-tal evidence of its costs and benefits (Section IV). We finishup with related work (Section V) and conclusions and futurework (Section VI).II. MEDIANET ARCHITECTUREMediaNet’s architecture defines a computational network,consisting of compute nodes and network links. These elementsare responsible for receiving streaming data from varioussources, computing on that data, and delivering it to the end-applications. As shown in Figure 1, compute nodes are highlyheterogeneous, consisting of cameras, sensors, workstations,and compute servers; as such they have different computationalpower, available memory, hardware support for video opera-tions, etc. Network links between nodes could be either wiredor wireless; as such, the underlying network topology maychange at run-time as components physically move around ornew parts of the infrastructure are deployed.The user’s