Auction-Based Algorithms for Routing and Task Scheduling in Federated Networks

摘要

This paper studies and develops multiple auction-based algorithms for resource exchange among decentralized systems in federated networks with distributed computational resources. Decentralized resource owners and users use processing, storage, and communication units to perform the available computational tasks at each time step while an auctioneer facilitates allocating resources. The auctioneer communicates with federates and receives bids for buying and selling resources, solves combinatorial problems, and proposes prices to federates. Multiple auction-based mechanisms are formulated and assessed using collective performance metrics in a networked federation. The auction-based algorithms include four reverse-bid and double-sided auctions: (1) first-price auction, (2) sequential non-linear pricing auction, (3) min-max closed-form pricing auction, and (4) balanced and maximizing closed-form pricing auction. For results, we assess algorithms for economic and computational efficiency using extensive simulation runs in hundreds of network topologies and initial conditions. The metrics introduced for our numerical validation include normalized bids and prices, collective values, and convergence rates.