Auction-Based Algorithms for Routing and Task Scheduling in Federated Networks
Tóm tắt
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.
Tài liệu tham khảo
Johnson, S.: Star Trek: The Worlds of the Federation. Pocket Books, New York (1989)
Joseph, P., Carton, S.: The law of the federation: images of law, lawyers, and the legal system in Star Trek, the next generation. Univ. Toledo Law Rev. 24, 43 (1992)
Maier, M.W.: Architecting principles for systems-of-systems. Syst. Eng. 1(4), 267–284 (1998). https://doi.org/10.1002/(SICI)1520-6858(1998)1:4<267::AID-SYS3>3.0.CO;2-D
Selva, D., Golkar, A., Korobova, O., Cruz, ILi, Collopy, P., de Weck, O.L.: Distributed earth satellite systems: what is needed to move forward? J. Aerosp. Inf. Syst. 14(8), 412–438 (2017). https://doi.org/10.2514/1.I010497
Azevedo, J.L., Cunha, B., Almeida, L.: Hierarchical distributed architectures for autonomous mobile robots: a case study. In: Proc. 2007 IEEE Conf. Emerg. Technol. Fact. Autom. (EFTA), pp. 973–980. IEEE, New York (2007). https://doi.org/10.1109/EFTA.2007.4416889
Petri, I., Beach, T., Zou, M., Montes, J.D., Rana, O., Parashar, M.: Exploring models and mechanisms for exchanging resources in a federated cloud. In: 2014 IEEE Int. Conf. Cloud Eng. (IC2E), pp. 215–224. IEEE, New York (2014). https://doi.org/10.1109/IC2E.2014.9
Koponen, T., Casado, M., Thakkar, P., Zhang, R., Wendlandt, D.J.: Packet processing in federated network (2015). U.S. Patent 8,964,767
Sun, J., Modiano, E., Zheng, L.: Wireless channel allocation using an auction algorithm. IEEE J. Sel. Areas Commun. 24(5), 1085–1096 (2006). https://doi.org/10.1109/JSAC.2006.872890
Kutanoglu, E., David Wu, S.: On combinatorial auction and Lagrangean relaxation for distributed resource scheduling. IIE Trans. 31(9), 813–826 (1999). https://doi.org/10.1080/07408179908969883
Zhang, H., Jiang, H., Li, B., Liu, F., Vasilakos, A.V., Liu, J.: A framework for truthful online auctions in cloud computing with heterogeneous user demands. IEEE Trans. Comput. 65(3), 805–818 (2016). https://doi.org/10.1109/TC.2015.2435784
Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P., Kleywegt, A.: Robot exploration with combinatorial auctions. In: 2003 IEEE/RSJ Int. Conf. Intell. Robots and Syst. (IROS), vol. 2, pp. 1957–1962. IEEE, New York (2003). https://doi.org/10.1109/IROS.2003.1248932
Pica, U., Golkar, A.: Sealed-bid reverse auction pricing mechanisms for federated satellite systems. Syst. Eng. 20(5), 432–446 (2017). https://doi.org/10.1002/sys.21395
Morgan, J.: Efficiency in auctions: theory and practice. J. Int. Money Financ. 20(6), 809–838 (2001). https://doi.org/10.1016/S0261-5606(01)00024-9
Yi, C., Cai, J.: Ascending-price progressive spectrum auction for cognitive radio networks with power-constrained multiradio secondary users. IEEE Trans. Veh. Technol. 67(1), 781–794 (2017). https://doi.org/10.1109/TVT.2017.2744560
Yi, C., Cai, J., Zhang, G.: Spectrum auction for differential secondary wireless service provisioning with time-dependent valuation information. IEEE Trans. Wireless Commun. 16(1), 206–220 (2016). https://doi.org/10.1109/TWC.2016.2621765
Schaeffer-Filho, A., Lupu, E., Sloman, M.: Federating policy-driven autonomous systems: interaction specification and management patterns. J. Netw. Syst. Manag. 23(3), 753–793 (2015). https://doi.org/10.1007/s10922-014-9317-5
Famaey, J., Latré, S., Wauters, T., De Turck, F.: End-to-end resource management for federated delivery of multimedia services. J. Netw. Syst. Manag. 22(3), 396–433 (2014). https://doi.org/10.1007/s10922-013-9288-y
Jennings, B., Feeney, K., Fleck, J.J.: Managing federations and cooperative management. J. Netw. Syst. Manag. 22(3), 297–301 (2014). https://doi.org/10.1007/s10922-014-9308-6
Umrao, S., Roy, A., Saxena, N., Singh, S., Jung, Ji: Mobile network operator and mobile user cooperation for customized d2d data services. J. Netw. Syst. Manag. 26(4), 878–903 (2018). https://doi.org/10.1007/s10922-018-9447-2
Yi, C., Huang, S., Cai, J.: An incentive mechanism integrating joint power, channel and link management for social-aware D2D content sharing and proactive caching. IEEE Trans. Mobile Comput. 17(4), 789–802 (2017). https://doi.org/10.1109/TMC.2017.2741481
Mo, J., Kim, W., Park, H.: Internet service pricing: flat or volume? J. Netw. Syst. Manag. 21(2), 298–325 (2013). https://doi.org/10.1007/s10922-012-9234-4
Pastirčák, J., Friga, L., Kováč, V., Gazda, J., Gazda, V.: An agent-based economy model of real-time secondary market for the cognitive radio networks. J. Netw. Syst. Manag. 24(2), 427–443 (2016). https://doi.org/10.1007/s10922-015-9355-7
Ehsanfar, A., Grogan, P.T.: Mechanism design for exchanging resources in federated networks. J. Netw. Syst. Manag. 1–25 (2019). https://doi.org/10.1007/s10922-019-09498-9
Cong, L., Yang, H., Wang, Y., Di, X.: An auction-gaming based routing model for LEO satellite networks. In: Int. Conf. Mach. Learn. Intell. Commun., pp. 498–508. Springer, Berlin (2017). https://doi.org/10.1007/978-3-319-73447-7_54
Kiran, Y.V., Giaffreda, R.: A dynamic pricing method for efficient radio resource management in wireless access networks. In: IEEE Int. Conf. Commun. (ICC), pp. 1–5. IEEE, New York (2011). https://doi.org/10.1109/icc.2011.5962681
Jayaweera, S.K., Bkassiny, M., Avery, K.A.: Asymmetric cooperative communications based spectrum leasing via auctions in cognitive radio networks. IEEE Trans. Wireless Commun. 10(8), 2716–2724 (2011). https://doi.org/10.1109/TWC.2011.061311.102044
Grosu, D., Chronopoulos, A.T.: Algorithmic mechanism design for load balancing in distributed systems. IEEE Trans. Syst. Man Cybern. Part B 34(1), 77–84 (2004). https://doi.org/10.1109/TSMCB.2002.805812
Son, S., Sim, K.M.: A price-and-time-slot-negotiation mechanism for cloud service reservations. IEEE Trans. Syst. Man Cybern. Part B 42(3), 713–728 (2012). https://doi.org/10.1109/TSMCB.2011.2174355
An, B., Lesser, V.: Characterizing contract-based multiagent resource allocation in networks. IEEE Trans. Syst. Man Cybern. Part B 40(3), 575–586 (2010). https://doi.org/10.1109/TSMCB.2009.2035100
Zhang, Y., Lee, C., Niyato, D., Wang, P.: Auction approaches for resource allocation in wireless systems: a survey. IEEE Commun. Surv. Tutor. 15(3), 1020–1041 (2013). https://doi.org/10.1109/SURV.2012.110112.00125
Zou, S., Ma, Z., Liu, X.: Auction-based mechanism for dynamic and efficient resource allocation. IEEE Trans. Syst. Man Cybern. Syst. 48(1), 34–49 (2018). https://doi.org/10.1109/TSMC.2016.2581025
De Vries, S., Vohra, R.V.: Combinatorial auctions: a survey. INFORMS J. Comput. 15(3), 284–309 (2003). https://doi.org/10.1287/ijoc.15.3.284.16077
Shafiq, M., Choi, J.G.: Adaptive auction framework for spectrum market in cognitive radio networks. J. Netw. Syst. Manag. 26(2), 518–546 (2018). https://doi.org/10.1007/s10922-017-9429-9
Pekeč, A., Rothkopf, M.H.: Combinatorial auction design. Manag. Sci. 49(11), 1485–1503 (2003). https://doi.org/10.1287/mnsc.49.11.1485.20585
Zaman, S., Grosu, D.: Combinatorial auction-based allocation of virtual machine instances in clouds. J. Parallel Distrib. Comput. 73(4), 495–508 (2013). https://doi.org/10.1016/j.jpdc.2012.12.006
Archer, A., Papadimitriou, C., Talwar, K., Tardos, É.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. Internet Math. 1(2), 129–150 (2004). https://doi.org/10.1080/15427951.2004.10129086
Lehmann, D., Oćallaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5), 577–602 (2002). https://doi.org/10.1145/585265.585266
Hajiesmaili, M.H., Deng, L., Chen, M., Li, Z.: Incentivizing device-to-device load balancing for cellular networks: an online auction design. IEEE J. Sel. Areas Commun. 35(2), 265–279 (2017). https://doi.org/10.1109/JSAC.2017.2659558
Yi, C., Cai, J., Zhang, G.: Online spectrum auction in cognitive radio networks with uncertain activities of primary users. In: 2015 IEEE Int. Conf. Commun. (ICC), pp. 7576–7581. IEEE, New York (2015). https://doi.org/10.1109/ICC.2015.7249538
Li, Z., Li, B., Zhu, Y.: Designing truthful spectrum auctions for multi-hop secondary networks. IEEE Trans. Mob. Comput. 14(2), 316–327 (2015). https://doi.org/10.1109/TMC.2013.64
Mondal, A., Madria, S.K., Kitsuregawa, M.: ABIDE: a bid-based economic incentive model for enticing non-cooperative peers in mobile-P2P networks. In: Int. Conf. Database Syst. Adv. Appl., pp. 703–714. Springer, Berlin (2007). https://doi.org/10.1007/978-3-540-71703-4_59
del Portillo, I., Cameron, B.G., Crawley, E.F.: A technical comparison of three low earth orbit satellite constellation systems to provide global broadband. Acta Astronautica 159, 123–135 (2019). https://doi.org/10.1016/j.actaastro.2019.03.040
Brooks, D., Eddy, W.M., Clark III, G.J., Johnson, S.K.: In-space networking on NASA’s SCaN testbed. In: Proc. 34th AIAA Int. Commun. Satell. Syst. Conf., AIAA 2016-5754, pp. 445–449. AIAA (2016). https://doi.org/10.2514/6.2016-5754
Anderegg, L., Eidenbenz, S.: Ad hoc-vcg: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents. In: Proc. 9th Ann. Int. Conf. Mobile Comput. Netw., pp. 245–259. ACM (2003). https://doi.org/10.1145/938985.939011
Han, X., Mandal, S., Pattipati, K.R., Kleinman, D.L., Mishra, M.: An optimization-based distributed planning algorithm: a blackboard-based collaborative framework. IEEE Trans. Syst. Man Cybern. Syst. 44(6), 673–686 (2014). https://doi.org/10.1109/TSMC.2013.2276392
Wang, Y., Dai, W., Jin, Q., Ma, J.: BciNet: a biased contest-based crowdsourcing incentive mechanism through exploiting social networks. IEEE Trans. Syst. Man Cybern. Syst. 56, 56 (2018). https://doi.org/10.1109/TSMC.2018.2837165. (Early access)