Capturing Approximated Data Delivery Tradeoffs

TitleCapturing Approximated Data Delivery Tradeoffs
Publication TypeConference Papers
Year of Publication2008
AuthorsRoitman H, Gal A, Raschid L
Conference NameData Engineering, 2008. ICDE 2008. IEEE 24th International Conference on
Date Published2008/04//
Keywordsapproximation scheme, approximation theory, biobjective optimization problem, Middleware, middleware data delivery tradeoffs, mobile networks, Pareto optimisation, Pareto set, proxy dilemma problem, sensor networks

This paper presents a middleware data delivery setting with a proxy that is required to maximize the completeness of captured updates, specified in its clients' profiles, while minimizing at the same time the delay in delivering the updates to clients. The two objectives may conflict when the monitoring budget is limited. Therefore, any solution should consider this tradeoff in satisfying both objectives. We term this problem the "proxy dilemma" and formalize it as a biobjective optimization problem. Such problem occurs in many contemporary applications, such as mobile and sensor networks, and poses scalability challenges in delivering up-to-date data from remote resources to meet client specifications. We present a Pareto set as a formal solution to the proxy dilemma. We discuss the complexity of generating a Pareto set for the proxy dilemma and suggest an approximation scheme to this problem.