Optimizing callout in unified ad markets

In the past, online ad networks owned their supply of impressions for ads with publishers and matched it to their own demand (advertisers). However, in the past few years, with programmatic ad selling becoming common place, these ad networks are now appealing to demand from multitude of demand side platforms (DSPs). The general approach is to partition the demand into pools (based on type of ads or the demand party). An inevitable challenge is the impedance mismatch between the marketplace and the demand pools. Thus, a central problem is to figure out how to handle each supply request and selectively send requests to demand pool so as to optimize the performance of entire supply. This is the Callout Problem. We present a large scale data analysis and control system that (a) continually learns changing traffic patterns, capacities, bids, revenue etc, and (b) picks the best slice of traffic to send to each demand pool, subject to their capacity constraints. The optimization is based on a greedy solution to the underlying knapsack problem which easily adapts as capacities change over time. We have implemented and deployed this solution for the callout problem in one of the largest mobile ad marketplaces(InMobi) and has been operational for several months. In this paper, we will describe the scale of the problem, our solution and our observations from operational experience with it. We believe a well-engineered solution to the Callout problem is essential for many ad networks in the online ad world.