Back to search

Boston University

Route coordination in brokered computing environments

Abstract

dc:description.abstract

The increased use of federated commodities to provide scalable, high quality services is fueling research in novel brokerage mechanisms and models for the management of resources under the control of rational agents. In such settings, the responsibility of a broker varies from coordinating the communication between agents to making decisions on their behalf. This thesis focuses on brokerage services that require routing of – as well as route coordination for – a set of commodities over a communication/mobility graph. Routing can either be explicit or implicit. In explicit routing, the location of the commodities, and hence the endpoints for the communication, are fixed and the problem reduces to the identification of a path subject to some objectives and constraints. In implicit routing, the routes are fixed, and the problem reduces to the assignment of endpoint locations to the commodities subject to some objectives and constraints. The first part of this thesis considers GeoPresence-as-a-Service (GPaaS) as a model of explicit route coordination in a brokered environment. In GPaaS, crowd-sourced mobile agents participate in the system by offering to fulfill geo-temporal service requests at locations along their journeys, requiring that their mobility be coordinated by the broker. The problem of route coordination is that of finding the optimal path for each participating agent that satisfies its geo-temporal journey constraints, with an objective to maximize the total revenue of the broker. This problem is shown to be as hard as the Vehicle Routing Problem; the classical NP-hard combinatorial optimization problem of deciding the routes to be taken by a fleet of vehicles to service customers. Moreover, as the agents are crowdsourced, i.e., they are presumed rational, selfish, and willing to deviate from their original journey paths only if given an incentive, any proposed heuristic for route coordination has to consider agent rationality. Thus, this thesis presents an incentive compatible, individually rational, and cash-positive route coordination mechanism that determines the routes to be taken by the agents, as well as Vickrey-Clarke-Groves (VCG) payments (Nisan and Ronen, 1999) as rewards for their participation. The second part of this thesis considers a brokerage environment that provides execution predictability guarantees for data-intensive workloads in a federated cloud setting as a model of implicit route coordination. The thesis provides a definition of the problem of packing virtual machines (VMs) in network-constrained physical hosts with an objective to minimize the cost of communication among the VMs. This problem is shown to be as hard as the Bin Packing problem (Johnson, 1973). Following the definition of a heuristic to solve the packing problem for a single workload, the thesis considers the problem of scheduling a batch of data-intensive workloads with time flexibility, and presents a batch scheduling algorithm that provides a packing solution that accounts for each workload’s flexibility and network demand. Moreover, the thesis presents a VCG-based pricing mechanism that fairly distributes the broker’s cost for offering the service over the different workloads. The thesis also expands this scheduling and pricing model to the management of data-intensive workloads in online (as opposed to batch) settings.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Naoum, Christin Bassem
Advisor dc:contributor.advisor
  • Bestavros, Azer

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53563

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Naoum, Christin Bassem. Route coordination in brokered computing environments. doctoral thesis, Boston University, 2015. https://hdl.handle.net/2144/53563