In recent years, auction theory has been extensively studied and many state-of-the-art solutions have been proposed aiming at allocating scarce resources. However, most of these studies assume that the auctioneer is a...In recent years, auction theory has been extensively studied and many state-of-the-art solutions have been proposed aiming at allocating scarce resources. However, most of these studies assume that the auctioneer is always trustworthy in the sealed-bid auctions, which is not always true in a more realistic scenario. Besides the privacy-preserving issue, the performance guarantee of social efficiency maximization is also crucial for auction mechanism design. In this paper, we study the auction mechanisms that consider the above two aspects. We discuss two multi-unit auction models: the identical multiple-items auction and the distinct multiple-items auction.Since the problem of determining a multi-unit auction mechanism that can maximize its social efficiency is NPhard, we design a series of nearly optimal multi-unit auction mechanisms for the proposed models. We prove that the proposed auction mechanisms are strategyproof. Moreover, we also prove that the privacy of bid value from each bidder can be preserved in the auction mechanisms. To the best of our knowledge, this is the first work on the strategyproof multi-unit auction mechanisms that simultaneously consider privacy preservation and social efficiency maximization. The extensive simulations show that the proposed mechanisms have low computation and communication overheads.展开更多
In recent years, Software-Defined Networks(SDNs) have become a promising technology to improve network utilization. However, limited flow table size and long deployment delays may result in low network performance in ...In recent years, Software-Defined Networks(SDNs) have become a promising technology to improve network utilization. However, limited flow table size and long deployment delays may result in low network performance in large-scale networks and a poor user experience. While a typical solution to this issue is routing aggregation(i.e., wildcard routing), the aggregation feasibility problem and reduced network performance may be encountered. To address this dilemma, we first design a novel wildcard routing scheme, called the Tag-based Rule Placement Scheme(TRPS). We then formulate a Hybrid Routing by Joint optimization of Per-flow routing and Tagbased routing(HR-JPT) problem, and prove its NP-hardness. An algorithm with a bounded approximation factor is designed for this problem, and the proposed methods are implemented on a Mininet platform. Extensive simulation results show that our methods are efficient for wildcard/hybrid routing. For example, our proposed tag-based wildcard rule placement scheme can reduce the number of required rules by about 65% on average compared with previous wildcard routing methods. Our proposed hybrid routing algorithm can increase network throughput by about 43% compared with existing hybrid routing solutions.展开更多
基金supported by the National Natural Science Foundation of China (Nos. 61572342 and 61672369)the Natural Science Foundation of Jiangsu Province (Nos. BK20151240 and BK20161258)China Postdoctoral Science Foundation (Nos. 2015M580470 and 2016M591920)
文摘In recent years, auction theory has been extensively studied and many state-of-the-art solutions have been proposed aiming at allocating scarce resources. However, most of these studies assume that the auctioneer is always trustworthy in the sealed-bid auctions, which is not always true in a more realistic scenario. Besides the privacy-preserving issue, the performance guarantee of social efficiency maximization is also crucial for auction mechanism design. In this paper, we study the auction mechanisms that consider the above two aspects. We discuss two multi-unit auction models: the identical multiple-items auction and the distinct multiple-items auction.Since the problem of determining a multi-unit auction mechanism that can maximize its social efficiency is NPhard, we design a series of nearly optimal multi-unit auction mechanisms for the proposed models. We prove that the proposed auction mechanisms are strategyproof. Moreover, we also prove that the privacy of bid value from each bidder can be preserved in the auction mechanisms. To the best of our knowledge, this is the first work on the strategyproof multi-unit auction mechanisms that simultaneously consider privacy preservation and social efficiency maximization. The extensive simulations show that the proposed mechanisms have low computation and communication overheads.
基金supported by the National Natural Science Foundation of China (Nos. 61472383, 61472385, and U1301256)the Natural Science Foundation of Jiangsu Province in China (No. BK20161257)
文摘In recent years, Software-Defined Networks(SDNs) have become a promising technology to improve network utilization. However, limited flow table size and long deployment delays may result in low network performance in large-scale networks and a poor user experience. While a typical solution to this issue is routing aggregation(i.e., wildcard routing), the aggregation feasibility problem and reduced network performance may be encountered. To address this dilemma, we first design a novel wildcard routing scheme, called the Tag-based Rule Placement Scheme(TRPS). We then formulate a Hybrid Routing by Joint optimization of Per-flow routing and Tagbased routing(HR-JPT) problem, and prove its NP-hardness. An algorithm with a bounded approximation factor is designed for this problem, and the proposed methods are implemented on a Mininet platform. Extensive simulation results show that our methods are efficient for wildcard/hybrid routing. For example, our proposed tag-based wildcard rule placement scheme can reduce the number of required rules by about 65% on average compared with previous wildcard routing methods. Our proposed hybrid routing algorithm can increase network throughput by about 43% compared with existing hybrid routing solutions.
