Truthful Padding-Based Auction Mechanisms for Cross-Cloud Link Bandwidth Allocation and Pricing

More and more application providers (APs) start to deploy their geo-distributed services in multiple cloud environments, such as JointCloud, federated clouds and InterCloud. Thus, massive cross-cloud traffic is generated from the services of APs, who need to pay Internet service providers (ISPs) for using their bandwidth. As such, an effective cross-cloud link bandwidth allocation and pricing mechanism is needed between APs and ISPs. Existing fixed-price scheme lacks market efficiency. Thus, we propose a truthful padding-based auction mechanism (TPAM) for cross-cloud bandwidth, which introduces the padding method and well-designed pricing strategy to ensure desirable properties. This mechanism is flexible enough to allow each AP to win the whole request, or win the specified proportional request, or lose and get nothing. Specifically, we first devise a linear-program-based method to calculate the padding vector for each candidate AP. Next, we design a padding-based method to determine the winning APs and match them with ISPs who offer the cheapest bandwidth. Finally, we design a critical-value-based pricing strategy and a marginal-cost-based pricing strategy for APs and ISPs to achieve truthfulness and budget balance. Theoretical analyses prove that TPAM achieves truthfulness, budget balance, individual rationality, asymptotic efficiency and computational tractability. Trace-driven simulation results also validate the effectiveness and efficiency of TPAM.