Adversarial training (AT) with projected gradient descent is most popular for improving model robustness under adversarial attacks. However, computational overheads become prohibitively large when AT is applied to large backbone models. It also suffers from robust overfitting that impairs model generalization. This paper contributes to solving both problems simultaneously towards building more trustworthy foundation models. We propose an adapter-based method to perform efficient AT directly in the feature space. The proposed approach improves the inner-loop convergence quality by eliminating robust overfitting, thus boosting robust generalization against unseen attacks and accelerating the training speed with fewer epochs. The proposed adapter can also enable adversarial detection by “plug-in” for testing at inference time. We evaluate the proposed approach on different backbone architectures and demonstrate its effectiveness for efficient AT at scale.

With cloud computing becoming increasingly popular, there has been a rapid increase in the number of data owners who outsource their data to the cloud while allowing users to retrieve the data. To preserve the privacy of data, data owners usually encrypt their data before outsourcing them to the cloud, and cloud servers can search across the ciphertext domain on behalf of users without learning any information about the data. However, existing work in the literature mostly supports only a single-user or single-keyword search which is not able to satisfy more desired expressive search. Thus, we propose a searchable encryption primitive with attribute-based access control for hybrid boolean keyword search over outsourced encrypted data. There exist several desirable features: (1) Data owners can set search permissions for outsourced encrypted data according to an access control policy. (2) Multiple users, whose attributes satisfy the access control policy, are allowed to perform a retrieval operation upon the encrypted data. (3) Authorized users are able to perform more expressive search, such as any required boolean keyword expression search. Additionally, this primitive is provably secure under our security model and we have also implemented the prototype to show the practicality of the primitive.

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today's large-scale data analytics. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job's lifetime, which makes it difficult to assign valuable tasks to well-performing machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

Approximation jobs that allow partial execution of their many tasks to achieve valuable results have played an important role in today’s large-scale data analytics [1], [2]. This fact can be utilized to maximize the system utility of a big data computing cluster by choosing proper tasks in scheduling for each approximation job. A fundamental challenge herein, however, is that the machine service capacity may fluctuate substantially during a job’s lifetime, which makes it difficult to assign valuable tasks to well-performed machines. In addition, the cluster scheduler needs to make online scheduling decisions without knowing future job arrivals according to machine availabilities. In this paper, we tackle this online resource allocation problem for approximation jobs in parallel computing clusters. In particular, we model a cluster with heterogeneous machines as a multi-armed bandit where each machine is treated as an arm. By making estimations on machine service rates while balancing the exploration-exploitation trade-off, we design an efficient online resource allocation algorithm from a bandit perspective. The proposed algorithm extends existing online convex optimization techniques and yields a sublinear regret bound. Moreover, we also examine the performance of the proposed algorithm via extensive trace-driven simulations and demonstrate that it outperforms the baselines substantially.

Similarity search is essential to many important applications and often involves searching at scale on high-dimensional data based on their similarity to a query. In biometric applications, recent vulnerability studies have shown that adversarial machine learning can compromise biometric recognition systems by exploiting the biometric similarity information. Existing methods for biometric privacy protection are in general based on pairwise matching of secured biometric templates and have inherent limitations in search efficiency and scalability. In this paper, we propose an inference-based framework for privacy-preserving similarity search in Hamming space. Our approach builds on an obfuscated distance measure that can conceal Hamming distance in a dynamic interval. Such a mechanism enables us to systematically design statistically reliable methods for retrieving most likely candidates without knowing the exact distance values. We further propose to apply Montgomery multiplication for generating search indexes that can withstand adversarial similarity analysis, and show that information leakage in randomized Montgomery domains can be made negligibly small. Our experiments on public biometric datasets demonstrate that the inference-based approach can achieve a search accuracy close to the best performance possible with secure computation methods, but the associated cost is reduced by orders of magnitude compared to cryptographic primitives.

This paper focuses on an important and fundamental problem of connecting two points by a cable, subject to a tradeoff between cost and earthquake survivability. In particular, we address the problem of selecting a route for laying a cable under arbitrary topography, based on earthquake data. First, we derive a semi-supervised probability density estimation model for the likelihood of earthquake disaster. Based on this probabilistic model, we generate a nearest neighbor graph. The graph represents each data point with a four-dimensional space formed by the three-dimensional undersea coordinates and the one-dimensional data of earthquake disaster level. It then forms the weight on graph between any positions. The data used in this study are all real data of undersea topography and earthquake information of the Taiwan Strait. As a result, both the undersea topology and the earthquake level can be transferred into a distance for shortest route finding. Finally, Dijkstra's algorithm is used for finding the optimal shortest route for cabling between the two given points on the graph. Extensive simulations based on a synthetic dataset and the Taiwan Strait real-world dataset corroborate the effectiveness of the proposed method.

We study the problem of job assignment in a large-scale realistically dimensioned server farm comprising multiple processor-sharing servers with different service rates, energy consumption rates, and buffer sizes. Our aim is to optimize the energy efficiency of such a server farm by effectively controlling carried load on networked servers. To this end, we propose a job assignment policy, called Most energy-efficient available server first Accounting for Idle Power (MAIP), which is both scalable and near optimal. MAIP focuses on reducing the productive power used to support the processing service rate. Using the framework of semi-Markov decision process, we show that, with exponentially distributed job sizes, MAIP is equivalent to the well-known Whittle's index policy. This equivalence and the methodology of Weber and Weiss enable us to prove that, in server farms where a loss of jobs happens if and only if all buffers are full, MAIP is asymptotically optimal, as the number of servers tends to infinity under certain conditions associated with the large number of servers, as we have in a real server farm. Through extensive numerical simulations, we demonstrate the effectiveness of MAIP and its robustness to different job-size distributions, and observe that significant improvement in energy efficiency can be achieved by utilizing the knowledge of energy consumption rate of idle servers.

Channel borrowing has been widely adopted in mobile cellular networks as a compromise between fixed channel assignment and dynamic channel assignment. Various channel borrowing schemes have been proposed in the literature with their performance, typically in terms of blocking probability, obtained by computer simulations. However, analytical approximation methods are much more computationally effective and practically useful for performance analysis of mobile cellular networks. In this paper, we model mobile cellular networks with channel borrowing as overflow loss systems. We present two methods for approximation of blocking probabilities in such systems, one based on the classical Erlang fixed point approximation (EFPA) approach, and the other derived from the recently established information exchange surrogate approximation (IESA) framework. Comprehensive results of both EFPA and IESA are provided and compared against simulation results. We demonstrate for a wide range of scenarios that IESA is more accurate in evaluating blocking probabilities than EFPA. To the best of our knowledge, our proposed approximation framework is the first workable approach in terms of accuracy and computational efficiency for cellular networks with consideration to mobility of calls and a channel borrowing mechanism.

Overflow loss systems have wide applications in telecommunications and multimedia systems. In this paper, we consider an overflow loss system consisting of a set of finite-buffer processor-sharing (PS) queues, and develop effective methods for evaluation of its blocking probability. For such a problem, an existing approximation of the blocking probability is based on decomposition of the system into independent PS queues. We provide a new approximation which instead performs decomposition on a surrogate model of the original system, and demonstrate via extensive numerical results that our new approximation is more accurate and robust than the existing approach. We also examine the sensitivity of the blocking probability to the service time distribution, and demonstrate that an exponential distribution is a good approximation for a wide range of service time distributions.

Energy efficiency of server farms is an important design consideration of data centers. One effective approach is to optimize energy consumption by controlling carried load on the networked servers. In this paper, we propose a robust heuristic policy for job assignment in a server farm, aiming to improve the energy efficiency by maximizing the ratio of the long-run average throughput to the expected energy consumption. Our model of the server farm considers parallel processor-sharing queues with finite buffer sizes, heterogeneous server speeds, and an arbitrary energy consumption function. We devise the new energy-efficient (EE) policy in a way that the state distribution of the system depends on the service requirement distribution only through the mean. We show that the state-of-the-art slowest server first (SSF) policy can be obtained as a special case of EE and both policies have the same computational complexity. We provide a rigorous analysis of EE and derive conditions under which EE is guaranteed to outperform SSF in terms of energy efficiency. Extensive numerical results are presented and demonstrate that, in comparison with SSF, EE yields a consistently better system throughput and yet improves the energy efficiency by up to 70%.

Energy efficiency of server farms is an important design consideration of the green datacenter initiative. One effective approach is to optimize power consumption of server farms by controlling the carried load on the networked servers. In this paper, we propose a robust heuristic policy called E* for stochastic job assignment in a server farm, aiming to improve the energy efficiency by maximizing the ratio of job throughput to power consumption. Our model of the server farm considers a parallel system of finite-buffer processor-sharing queues with heterogeneous server speeds and energy consumption rates. We devise E* as an insensitive policy so that the stationary distribution of the number of jobs in the system depends on the job size distribution only through its mean. We provide a rigorous analysis of E* and compare it with a baseline approach, known as most energy-efficient server first (MEESF), that greedily chooses the most energy-efficient servers for job assignment. We show that E* has always a higher job throughput than that of MEESF, and derive realistic conditions under which E* is guaranteed to outperform MEESF in energy efficiency. Extensive numerical results are presented and demonstrate that E* can improve the energy efficiency by up to 100%.

This paper presents a cross-layer approach for enabling high-throughput reliable multicast in multi-hop wireless mesh networks. The building block of our approach is a multicast routing metric, called the expected multicast transmission count (EMTX). EMTX is designed to capture the combined effects of MAC-layer retransmission-based reliability, wireless broadcast advantage, and link quality awareness. The EMTX of single-hop transmission of a multicast packet from a sender is the expected number of multicast transmissions (including retransmissions) required for its next-hop recipients to receive the packet successfully. We formulate the EMTX-based multicast problem with the objective of minimizing the sum of EMTX over all forwarding nodes in the multicast tree, aiming to reduce network bandwidth consumption while ensure high end-to-end packet delivery ratio for the multicast traffic. We provide rigorous mathematical formulations and methods to find near-optimal solutions of the problem computationally efficiently. We present centralized and distributed algorithms, and demonstrate their effectiveness in tackling the EMTX-based multicast problem with a combination of theoretical and numerical results. Simulation experiments show that, in comparison with two baseline approaches, EMTX-based multicast routing reduces the number of hop-by-hop transmissions per packet by up to 40 percent and yet improves the multicast throughput by up to 24 percent.

We study the problem of stochastic job assignment in a server farm comprising multiple processor-sharing servers with various speeds and finite buffer sizes. We consider two types of assignment policies: without jockeying, where an arriving job is assigned only once to an available server, and with jockeying, where a job may be reassigned at any time. We also require that the underlying Markov process under each policy is insensitive. Namely, the stationary distribution of the number of jobs in the system is independent of the job size distribution except for its mean. For the case without jockeying, we derive two insensitive heuristic policies: One aims at maximizing job throughput, and the other trades off job throughput for energy efficiency. For the case with jockeying, we formulate the optimal assignment problem as a semi-Markov decision process and derive optimal policies with respect to various optimization criteria. We further derive two simple insensitive heuristic policies with jockeying: One maximizes job throughput, and the other aims at maximizing energy efficiency. Numerical examples demonstrate that, under a wide range of system parameters, the latter policy performs very close to the optimal policy. Numerical examples also demonstrate energy/throughput tradeoffs for the various policies and, in the case with jockeying, they show a potential of substantial energy savings relative to a policy that optimizes throughput.

We present a cross-layer approach for enabling high-throughput routing in multi-hop wireless networks. This approach builds on a MAC-layer cooperative retransmission mechanism, which is explicitly designed to exploit the benefits of MAC-layer retransmission-based reliability, cooperative communications, and link-quality awareness. Based on this mechanism, we devise a routing metric, called the expected cooperative transmission count (ECTX), to capture the combined effects of MAC-layer cooperative retransmission and per-link estimates of packet delivery ratios. We show that, compared to conventional approaches using the well-known expected transmission count (ETX) metric, our approach has two advantages in principle: 1) with the cooperative retransmission mechanism, one can effectively reduce the expected total number of packet transmissions (including retransmissions) on the same path found by ETX; 2) with the ECTX metric, one may indeed identify a more effective path and further reduce the transmission count. We discuss modifications to IEEE 802.11 MAC to incorporate the cooperative retransmission mechanism, and implement ECTX-based routing using the DSR protocol. Extensive simulations on QualNet demonstrate that ECTX-based routing is significantly more efficient than ETX-based routing, in many instances reducing the transmission count by more than 30% and yet improving the network throughput by up to 80%.

We propose a routing metric for enabling high-throughput reliable multicast in multi-rate wireless mesh networks. This new multicast routing metric, called expected multicast transmission time (EMTT), captures the combined effects of 1) MAC-layer retransmission-based reliability, 2) transmission rate diversity, 3) wireless broadcast advantage, and 4) link quality awareness. The EMTT of one-hop transmission of a multicast packet minimizes the amount of expected transmission time (including that required for retransmissions). This is achieved by allowing the sender to adapt its bit-rate for each ongoing transmission/retransmission, optimized exclusively for its next-hop receivers that have not yet received the multicast packet. We model the rate adaptation process as a Markov decision process (MDP) and derive an efficient procedure for computing EMTT from the theory of MDP. We present receiver-initiated algorithms and describe protocol implementation for the EMTT-based multicast routing problem. Numerical results are presented to demonstrate the accuracy of the proposed algorithms against optimal solutions to the multicast routing problem. Simulation experiments confirm that, in comparison with single-rate multicast, multi-rate multicast using the EMTT metric effectively reduces the overall multicast transmission time while yielding higher packet delivery ratio and lower end-to-end latency.

To support large-scale Internet-based broadcast of live streaming video efficiently in content delivery networks (CDNs), it is essential to implement a cost-effective overlay multicast mechanism by exploiting peer-to-peer distribution capabilities among end hosts. This way, the access bandwidth demand on CDN servers in the multicast overlay backbone can be largely reduced. Such a streaming infrastructure gives rise to an interesting host-aware routing problem (HARP). For a live streaming video broadcast event, each participating CDN server is made aware of the largest delay from it to end hosts within its service area. The problem is to optimize routing among CDN servers in the multicast overlay backbone such that the de facto maximal end-to-end latency from the origin server to all end hosts is minimized subject to access bandwidth constraints on CDN servers. In this paper, we frame HARP as a constrained spanning tree problem which is shown to be NP-hard. We present a distributed algorithm for HARP. Simulation experiments confirm that our proposed algorithm converges to good quality solutions that are close to the optimum.

This paper studies probabilistically reliable multicast in wireless mesh networks (WMNs), utilizing MAC layer re-transmission and wireless broadcast advantage to improve both the multicast throughput and the delivery rate. We first present a new multicast routing metric which we call the expected multicast transmissions (EMT). EMT captures the effect of link packet delivery ratio, MAC layer retransmission and wireless broadcast advantage at the same time. The EMT of a MAC layer multicast transmission is the expected number of data transmissions (including retransmissions) required for a packet to reach all the recipients. The EMT of a multicast tree is the sum over the EMT of each forwarding node. Then, we propose a probabilistically reliable on-demand (PROD) multicast protocol with the objective of minimizing the EMT of the multicast tree. Simulation results show that, in comparison with existing approaches, PROD reduces the end-to-end packet loss ratio by up to 30% and improves the multicast throughput by up to 25%. In addition, it reduces the number of transmissions per packet by up to 40% and thus significantly reduces the network overhead of the multicast session.

We observe that an effect of ldquodisk resource sharingrdquo of multi-copy movie traffic has great impact on the blocking performance of a video-on-demand system. This observation leads us to establish a conjecture on how to balance the movie traffic load among ldquocombinationrdquo groups of disks to maximize the level of disk resource sharing. For a given file replication instance, the conjecture predicts in general an effective lower bound on the blocking performance of the system. It motivates the design of a numerical index that measures quantitatively the goodness of disk resource sharing on allocation of multi-copy movie files. It also motivates the design of a greedy file allocation method that decides a good quality heuristic solution for each feasible file replication instance. We further develop analytical formulas to obtain approximate results for the bound fast and accurately. These techniques can be utilized by an optimization program to find near-optimal file assignment solutions for the system computationally efficiently.

We present a genetic algorithm for tackling a file assignment problem for a large-scale video-on-demand system. The file assignment problem is to find the optimal replication and allocation of movie files to disks so that the request blocking probability is minimized subject to capacity constraints. We adopt a divide-and-conquer strategy, where the entire solution space of file assignments is divided into subspaces. Each subspace is an exclusive set of solutions sharing a common file replication instance. This allows us to utilize a greedy file allocation method for finding a good-quality heuristic solution within each subspace. We further design two performance indices to measure the quality of the heuristic solution on 1.) its assignment of multicopy movies and 2.) its assignment of single-copy movies. We demonstrate that these techniques, together with ad hoc population handling methods, enable genetic algorithms to operate in a significantly reduced search space and achieve good-quality file assignments in a computationally efficient way.

The designers of a large scale video-on-demand system face an optimization problem of deciding how to assign movies to multiple disks (servers) such that the request blocking probability is minimized subject to capacity constraints. To solve this problem, it is essential to develop scalable and accurate analytical means to evaluate the blocking performance of the system for a given file assignment. The performance analysis is made more complicated by the fact that the request blocking probability depends also on how disks are selected to serve user requests for multicopy movies. In this paper, we analyze several efficient resource selection schemes. Numerical results demonstrate that our analysis is scalable and sufficiently accurate to support the task of file assignment optimization in such a system.

Placing multicast proxies on the Internet can largely reduce the delivery delay of Internet live media streaming using overlay multicast mechanisms. In this paper, we propose a new approach to address the issue of proxy placement in an overlay multicast network. The task is to decide an optimal placement of multicast proxies in the overlay multicast network so as to minimize the average end-to-end delay of the overlay skeleton tree subject to out-degree balancing constraint and maximum delivery delay bound. We present two heuristic methods for this proxy placement problem. Experimental results demonstrate that proxy placement due to our proposed approach can greatly improve the overlay multicast routing performance. In comparison with an existing approach commonly used for replica placement in content distribution networks, our proposed approach significantly improves the end-to-end latency performance of overlay multicast networks, and is not much sensitive to network dynamics.

In this paper, we proposed a probabilistically reliable multicast routing (PRMR) which uses link packet delivery rate as the link-quality-based metric to find paths from source to destinations. In order to increase the reliability of the multicast session, we use a pair of disjoint paths to connect the source to each destination. We reduce the total number of forwarding nodes by exploiting the wireless broadcast advantage. Our experiment results show that PRMR can increase the average reliability by up to 25% and the node with the lowest reliability by up to 50% in comparison with ODMRP.

To support reliable multicast routing in wireless mesh networks, it is important to protect multicast sessions against link or node failures. The issue of protecting multicast sessions in wireless mesh networks is a new problem to the best of our knowledge. In this paper, we propose a resilient forwarding mesh approach for protecting a multicast session in wireless mesh networks. Utilizing the wireless broadcast advantage, a resilient forwarding mesh effectively establishes two node disjoint paths for each source-destination pair. This allows a multicast session to be immune from any single link or intermediate node failure. We introduce four heuristic algorithms to obtain approximate solutions that seek to minimize the number of required broadcast transmissions. We evaluate the performance of these heuristic algorithms against the optimal resilient forwarding mesh (ORFM) obtained by solving an integer linear programming (ILP) formulation of the problem. Experimental results demonstrate that one of these heuristic algorithms, which we call the minimal disjoint mesh algorithm (MDM), performs sufficiently close to ORFM. Besides, we find that the resilient forwarding mesh approach provides efficient 1+ 1 protection (Pioro and Medhi, 2004) to the multicast session without incurring much additional overhead on a single minimal cost multicast tree

This paper proposes a new optical burst switching (OBS) paradigm known as dynamic two-way reservation OBS (DTWR/OBS), in which the burst length is dynamically determined at an ingress router, according to the minimum length reservation period available on each wavelength channel within a lightpath, from the ingress router to the egress router. The dynamic nature of DTWR/OBS ensures the packet transmission rate is controlled at the ingress routers, based on the level of network congestion. This increases network utilization and eliminates burst blocking due to wavelength contention. An analytical model for a single isolated optical cross-connect (OXC) is derived to determine the waiting time distribution of an arbitrary IP packet at the ingress router using the proposed DTWR/OBS. The accuracy of the analytical model is confirmed by simulations.

We obtain detailed analytic formulas for the density and probability distribution of the waiting time in a time-division multiple-access (TDMA) model with a finite buffer and state-dependent service. On successive intervals of length equal to the duration of a slot, the density is expressed as a linear combination of beta densities with positive coefficients. A recursive scheme, obtained by a matrix-analytic derivation, allows for the highly efficient computations of the coefficient sequences. An expression for the mean waiting time is derived using the classical queueing formula L=/spl lambda/W. We also demonstrate that our methodology provides a concise treatment of various special cases that have been studied over the past half century.

Little and Venkatesh conjectured that, for an interactive VoD system with a single random trial resource selection scheme, the blocking probability of a user's request is minimized when the overall movie traffic load is spread uniformly on each disk in the system. In this paper, we generalize this conjecture to the situation where there can be repeated random trials or where a least busy fit resource selection scheme is used. We support our conjecture with a simulation of a realistic system, and propose a metric following the idea of our conjecture to assess the goodness of movie assignment in the system.

This paper provides and efficient for the derivation of the delay distribution for a TDMA system with a finite buffer. Assuming successive intervals of length equal to the duration of a slot, the density is expressed as (finite) linear combinations of gamma densities and beta densities with positive coefficients. The results are verified by simulations. Comparison with a previously proposed solution demonstrates that the solution presented here is more efficient.

We consider a video-on-demand system in which multiple copies of each movie file are kept in separate disks. Various schemes for file allocation and retrieval are considered and compared. We have introduced a certain easy-to-implement scheme that requires 15% more storage than another certain harder-to-implement scheme.

Detailed analytic formulas for the density and probability distribution of the waiting time in a TDMA model with a finite buffer is obtained. On successive intervals of length equal to the duration of a slot, the density is expressed as (infinite) linear combinations of beta densities with positive coefficients. A recursive scheme, obtained by a matrix-analytic derivation, allows for the highly efficient computations of the coefficient sequences.