Approximate Nearest Neighbor Search (ANNS) is a fundamental algorithmic problem, with numerous applications in many areas of computer science. Locality-Sensitive Hashing (LSH) is one of the most popular solution approaches for ANNS. A common shortcoming of many LSH schemes is that since they probe only a single bucket in a hash table, they need to use a large number of hash tables to achieve a high query accuracy. For ANNS- L 2 , a multi-probe scheme was proposed to overcome this drawback by strategically probing multiple buckets in a hash table. In this work, we propose MP-RW-LSH, the first and so far only multi-probe LSH solution to ANNS in L 1 distance, and show that it achieves a better tradeoff between scalability and query efficiency than all existing LSH-based solutions. We also explain why a state-of-the-art ANNS -L 1 solution called Cauchy projection LSH (CP-LSH) is fundamentally not suitable for multi-probe extension. Finally, as a use case, we construct, using MP-RW-LSH as the underlying "ANNS- L 1 engine", a new ANNS-E (E for edit distance) solution that beats the state of the art.

Most of today's high-speed switches and routers adopt an input-queued crossbar switch architecture. Such a switch needs to compute a matching (crossbar schedule) between the input ports and output ports during each switching cycle (time slot). A key research challenge in designing large (in number of input/output ports N) input-queued crossbar switches is to develop crossbar scheduling algorithms that can compute “high quality” matchings - i.e., those that result in high switch throughput (ideally 100%) and low queueing delays for packets - at line rates. SERENA is one such algorithm: it outputs excellent matching decisions that result in 100% switch throughput and reasonably good queueing delays. However, since SERENA is a centralized algorithm with O(N) time complexity, it cannot support switches that both are large and have a very high line rate per port. In this work, we propose SERENADE (SERENA, the Distributed Edition), a parallel iterative algorithm that provably precisely emulates SERENA in only O(logN) iterations between input ports and output ports, and hence has a time complexity of only O(logN) per port.

Set reconciliation is a fundamental algorithmic problem that arises in many networking, system, and database applications. In this problem, two large sets A and B of objects (bitcoins, files, records, etc.) are stored respectively at two different network-connected hosts, which we name Alice and Bob respectively. Alice and Bob communicate with each other to learn A Δ B , the difference between A and B , and as a result the reconciled set A ∪ B. Current set reconciliation schemes are based on either invertible Bloom filters (IBF) or error-correction codes (ECC). The former has a low computational complexity of O(d) , where d is the cardinality of A Δ B , but has a high communication overhead that is several times larger than the theoretical minimum. The latter has a low communication overhead close to the theoretical minimum, but has a much higher computational complexity of O(d 2 ). In this work, we propose Parity Bitmap Sketch (PBS), an ECC-based set reconciliation scheme that gets the better of both worlds: PBS has both a low computational complexity of O(d) just like IBF-based solutions and a low communication overhead of roughly twice the theoretical minimum. A separate contribution of this work is a novel rigorous analytical framework that can be used for the precise calculation of various performance metrics and for the near-optimal parameter tuning of PBS.

Approximate Nearest Neighbor (ANN) search is a fundamental algorithmic problem, with numerous applications in many areas of computer science. In this work, we propose indexable distance estimating codes (iDEC) , a new solution framework to ANN that extends and improves the locality sensitive hashing (LSH) framework in a fundamental and systematic way. Empirically, an iDEC-based solution has a low index space complexity of O ( n ) and can achieve a low average query time complexity of approximately O (log n ). We show that our iDEC-based solutions for ANN in Hamming and edit distances outperform the respective state-of-the-art LSH-based solutions for both in-memory and external-memory processing. We also show that our iDEC-based in-memory ANN-H solution is more scalable than all existing solutions. We also discover deep connections between Error-Estimating Codes (EEC), LSH, and iDEC.

Hybrid switching for data center networks (DCN) has received considerable research attention recently. A hybrid-switched DCN employs a much faster circuit switch that is reconfigurable with a nontrivial cost, and a much slower packet switch, to interconnect its racks of servers. The research problem is, given a traffic demand (between the racks), how to properly schedule the circuit switch so that it removes most of the traffic demand, leaving little for the slower packet switch to handle. All existing solutions make a convenient but unnecessarily restrictive assumption that when the circuit switch changes from one configuration to another, all input ports have to stop data transmission during the reconfiguration period. However, the circuit switch can usually readily support partial reconfiguration in the following sense: Only the input ports affected by the reconfiguration need to pay a reconfiguration delay, while unaffected input ports can continue to transmit data during the reconfiguration. In this work, we propose BFF (best first fit), the first solution to exploit this partial reconfigurability in hybrid-switched DCNs. BFF not only significantly outperforms but also has much lower computational complexity than the state of the art solutions that do not exploit this partial reconfigurability.

Various Online Social Network (OSN) based applications depend on the interactions between users to disseminate information and recruit more users. The temporal evolution of adoption or cascade process of new products, applications or ideas is important to advertisers, OSN operators and application developers. Interactions between users are represented by massive directed graphs, so graph sampling methods were proposed to capture their properties. Existing graph sampling methods, such as a simple random walk, however, are ill- suited for capturing this and other dynamic properties of the graph. We propose ForestStream, a measurement method that relies on a combination of sampling and streaming with the goal of capturing the statistical properties of cascades in OSN graphs. We demonstrate our method's accuracy over existing methods in inferring the cascade statistics, with a low memory usage.

It is known that multicast provisioning is important for supporting cloud-based applications, and as the traffics from these applications are increasing quickly, we may rely on optical networks to realize high-throughput multicast. Meanwhile, the flexible-grid elastic optical networks (EONs) achieve agile access to the massive bandwidth in optical fibers, and hence can provision variable bandwidths to adapt to the dynamic demands from the cloud-based applications. In this paper, we consider all-optical multicast in EONs in a practical manner and focus on designing impairment- and splitting-aware multicast provisioning schemes. We first study the procedure of adaptive modulation selection for a light-tree, and point out that the multicast scheme in EONs is fundamentally different from that in the fixed-grid wavelength-division multiplexing networks. Then, we formulate the problem of impairment- and splitting-aware routing, modulation and spectrum assignment (ISa-RMSA) for all-optical multicast in EONs and analyze its hardness. Next, we analyze the advantages brought by the flexibility of routing structures and discuss the ISa-RMSA schemes based on light-trees and light-forests. This paper suggests that for ISa-RMSA, the light-forest-based approach can use less bandwidth than the light-tree-based one, while still satisfying the quality of transmission requirement. Therefore, we establish the minimum light-forest problem for optimizing a light-forest in ISa-RMSA. Finally, we design several time-efficient ISa-RMSA algorithms, and prove that one of them can solve the minimum light-forest problem with a fixed approximation ratio.

This paper tries to solve the location-constrained virtual network embedding (LC-VNE) problem efficiently. We first investigate the complexity of LC-VNE, and by leveraging the graph bisection problem, we provide the first formal proof of the NP-completeness and inapproximability result of LC-VNE. Then, we propose two novel LC-VNE algorithms based on a compatibility graph (CG) to achieve integrated node and link mapping. In particular, in the CG, each node represents a candidate substrate path for a virtual link, and each link indicates the compatible relation between its two endnodes. Our theoretical analysis proves that the maximal clique in the CG is also the maximum one when the substrate network has sufficient resources. With CG, we reduce LC-VNE to the minimumcost maximum clique problem, which inspires us to propose two efficient LC-VNE heuristics. Extensive numerical simulations demonstrate that compared with the existing ones, our proposed LC-VNE algorithms have significantly reduced time complexity and can provide smaller gaps to the optimal solutions, lower blocking probabilities, and higher time-average revenue as well.

Software defined networking (SDN) makes networks programmable and application-aware by decoupling network control and management (NC&M) from data forwarding and leveraging centralized NC&M to facilitate user-customized routing and switching. Inspired by these, this paper investigates how to realize the OpenFlow-controlled (OF-controlled) network orchestration that can facilitate efficient scalable video coding (SVC) streaming to heterogeneous clients. Specifically, we consider real-time SVC streaming and address the situation in which video sources reside in geographically- distributed servers and clients can join and leave the streaming services dynamically. We formulate this as a multi-source multi-destination manycast problem and realize the networking system with an OF-controlled SDN architecture. We first design the OF controller to enable efficient network operations. Then, we focus on solving the multi-source multi-destination SVC video manycast problem and design several algorithms. Initially, an integer linear programming (ILP) model is formulated to obtain the optimal solutions for small-scale problems. Next, we try to make the manycast algorithm suitable for practical implementation, and design two time-efficient heuristics. Simulation results indicate that the heuristics can provide close-to-optimal solutions. Finally, we build an OF network testbed that consists of OF switches, SVC video servers and clients, and perform SVC streaming experiments to demonstrate our design. Experimental results verify that the proposed scheme can allocate bandwidth intelligently and ensure high-quality video streaming. To the best of our knowledge, this is the first work that accomplishes experimental demonstration of OF-controlled network orchestration for adaptive SVC video manycast.

With the development of datacenter networks and network virtualization, facility-failure-proof survivable virtual network embedding (SVNE) has recently gained notable attention. In this work, we design novel location-constrained SVNE (LC-SVNE) approaches that consider the working and backup embeddings jointly and protect virtual networks against single-facility-failures efficiently. We first transform the survivable node mapping to a bipartite graph matching problem and solve it for effective resource sharing among working and backup facilities. Then, two survivable link mapping schemes are designed to minimize the bandwidth consumption of virtual links, by leveraging anycast- and multicast-based substrate routing scenarios. Simulation results show that the proposed approaches outperform two existing ones on blocking probability and time-average revenue.

In this paper, after proposing a novel metric, i.e., global resource capacity (GRC), to quantify the embedding potential of each substrate node, we propose an efficient heuristic virtual network embedding (VNE) algorithm, called as GRC-VNE. The proposed algorithm aims to maximize the revenue and to minimize the cost of the infrastructure provider (InP). Based on GRC, the proposed algorithm applies a greedy load-balance manner to embed each virtual node sequentially, and then adopts the shortest path routing to embed each virtual link. Simulation results demonstrate that our proposed GRC-VNE algorithm achieves lower request blocking probability and higher revenue due to the more appropriate consideration of the resource distribution of the entire network, when compared to the two lastest VNE algorithms that also consider the resources of entire substrate network. Then, we introduce a classical reserved cloud revenue model, which consists of fixed revenue and variable one. Based on this revenue model, we design a novel admission control policy selectively accepting the VNR with high revenue-to-cost ratio to maximize the InP's profit based on an empirical threshold. Through extensive simulations, we observe that the optimal empirical threshold is proportional to the ratio of variable revenue to the fixed one.

Virtual network embedding (VNE), working as a key step for network virtualization, has recently gained intensive attentions from the research community. In this paper, we propose a novel VNE algorithm that aims to maximize the infrastructure provider's revenue from serving virtual network (VN) requests, with the help of the global resource information. The proposed algorithm, named as revenue-driven VNE (RD-VNE), adopts a node-ranking approach that takes the global resource information into account in a recursive manner to assist the greedy node mapping, and leverages the shortest-path routing for link mapping. Our simulation results suggest that the proposed VNE algorithm outperforms two existing VNE algorithms that also take global resource information into consideration, in terms of request blocking probability, and brings higher time-average revenue to the infrastructure provider (InP).

In this paper, we incorporate a layered approach to design integrated multicast-capable routing and spectrum assignment (MC-RSA) algorithms for achieving efficient all-optical multicasting in spectrum-sliced elastic optical networks (EONs), which are based on the optical orthogonal frequency-division multiplexing (O-OFDM) technology. For each multicast request, the proposed algorithms decompose the physical topology into several layered auxiliary graphs according to the network spectrum utilization. Then, based on the request's bandwidth requirement, we select a proper layer and calculate a multicast light-tree within it. With these procedures, the routing and spectrum assignment (RSA) for each multicast request is done in an integrated way. We evaluate the proposed algorithms in simulations of static network planning and dynamic network provisioning. The simulation results demonstrate that compared to the existing MC-RSA algorithms, our approaches achieve more efficient network planning in terms of spectrum utilization, and provide lower blocking probabilities in network provisioning.

We propose a novel dynamic transparent virtual network embedding (VNE) algorithm, which considers node mapping and link mapping jointly, for network virtualization over optical orthogonal frequency-division multiplexing (O-OFDM) based elastic optical infrastructures. For each virtual optical network (VON) request, the algorithm first transfers the substrate optical network into a layered-auxiliary-graph according to the spectrum usage of each fiber link, then applies a node mapping approach that considers the local information of all substrate nodes, and accomplishes the link mapping, in a single layer of the auxiliary graph. The simulation results verify that the proposed algorithm considers the uniqueness of O-OFDM networks and outperforms two reference algorithms that directly apply the VNE schemes developed for Layer 2/3 or WDM network virtualization, by providing lower VON blocking probability. The simulations with a realistic topology also demonstrate that the average lengths of embedded substrate paths are well-controlled within the typical transmission reaches of O-OFDM signals. To the best of our knowledge, this is the first proposal that includes both link mapping and node mapping to address dynamic transparent VNE over elastic optical infrastructures.

Bandwidth defragmentation, i.e., the operation to reconfigure existing connections for making the spectrum usage less fragmented and less misaligned, has recently been recognized as one of the most important features for elastic optical networks (EONs). In this paper, we propose a novel comprehensive bandwidth defragmentation algorithm that considers the problems of 1) When to defragment? 2) What for defragment? and 3) How to defragment? jointly. The proposed algorithm accomplishes defragmentation through proactive network reconfiguration that only reroutes a portion of existing connections. In each defragmentation operation, we first choose the connections to reroute using a selection strategy, then determine how to reroute them with the defragmentation based routing and spectrum assignment (DF-RSA), and finally perform rerouting with best-effort traffic migration to minimize traffic disruptions. Simulation results indicate that in order to make the bandwidth blocking probability (BBP) comparable with that from the Greenfield scenario (100% rerouting all the time), the proposed algorithm only needs to reroute ~30% existing connections. The simulations also demonstrate that the traffic disruption percentages are less than 1% for defragmentations with 30% rerouting and can be further reduced to within 0.25% by adding a move-to-vacancy (MTV) approach in the traffic migration.

We develop an adaptive and efficient genetic algorithm (GA) to solve the dynamic routing, modulation and spectrum assignments (RMSA) for elastic O-OFDM networks. The algorithm offers an efficient way of serving the dynamic lightpath requests based on the current network status at each service provision time. The GA is designed for multi-objective optimization. For low traffic cases when there is no blocking, the GA minimizes the maximum number of slots required on any fiber in the network; otherwise, it minimizes the blocking probability. The performance of the proposed GA is evaluated in dynamic RMSA simulations with the 14-node NSFNET and the 28-node US Backbone topologies, and the results show that it converges within 25 generations. The simulation results also verify that the GA-RMSA outperforms several existing algorithms by providing more load-balanced network provisioning solutions with lower blocking probabilities. Specifically, when the traffic load is same, the GA can achieve more than one order-of-magnitude reduction on blocking probability. To the best of our knowledge, this is the first attempt to solve dynamic RMSA in elastic O-OFDM networks with a GA.