Search

The network link speed is growing at an ever-increasing rate, which requires all network functions on routers/switches to keep pace. Bloom filter is a widely-used membership check data structure in networking applications. Correspondingly, it also faces the urgent demand of improving the performance in membership check speed. To this end, this paper proposes a new Bloom filter variant called Ultra-Fast Bloom Filters (UFBF), by leveraging the Single Instruction Multiple Data (SIMD) techniques. We make three improvements for UFBF to accelerate the membership check speed. First, we develop a novel hash computation algorithm which can compute multiple hash functions in parallel with the use of SIMD instructions. Second, we elaborate a Bloom filter’s bit-test process from sequential to parallel, enabling more bit-tests per unit time. Third, we improve the cache efficiency of membership check by encoding an element’s information to a small block so that it can fit into a cache-line. We further generalize UFBF, called c-UFBF, to make UFBF supporting large number of hash functions. Both theoretical analysis and extensive evaluations show that the UFBF greatly outperforms the state-of-the-art Bloom filter variants on membership check speed. [ABSTRACT FROM AUTHOR]

Nowadays, by integrating the cloud radio access network (C-RAN) with the mobile edge cloud computing (MEC) technology, mobile service provider (MSP) can efficiently handle the increasing mobile traffic and enhance the capabilities of mobile devices. But the power consumption has become skyrocketing for MSP and it gravely affects the profit of MSP. Previous work often studied the power consumption in C-RAN and MEC separately while less work had considered the integration of C-RAN with MEC. In this paper, we present an unifying framework for the power-performance tradeoff of MSP by jointly scheduling network resources in C-RAN and computation resources in MEC to maximize the profit of MSP. To achieve this objective, we formulate the resource scheduling issue as a stochastic problem and design a new optimization framework by using an extended Lyapunov technique. Specially, because the standard Lyapunov technique critically assumes that job requests have fixed lengths and can be finished within each decision making interval, it is not suitable for the dynamic situation where the mobile job requests have variable lengths. To solve this problem, we extend the standard Lyapunov technique and design the VariedLen algorithm to make online decisions in consecutive time for job requests with variable lengths. Our proposed algorithm can reach time average profit that is close to the optimum with a diminishing gap (1/V) for the MSP while still maintaining strong system stability and low congestion. With extensive simulations based on a real world trace, we demonstrate the efficacy and optimality of our proposed algorithm. [ABSTRACT FROM AUTHOR]

Light-trail is proposed as a candidate to carry IP traffic over wavelength-division multiplexing optical networks given its capability of enabling high-speed provisioning and accommodating multigranularity traffic. In a light-trail, the optical shutters at the start node and the end node are configured to be in OFF state and the optical shutters at the intermediate nodes are configured to be in ON state. Thus, an optical bus is formed, allowing traffic multiplexing without the state change of any optical shutter. This, however, limits the system throughput and also makes it impossible to implement a fully distributed medium access control (MAC) protocol to assure quality of service (QoS) in a light-trail. With the recent development on ultrafast optical shutter, we propose an improved light-trail architecture, called opportunistic hyperchannel in this paper. In an opportunistic hyperchannel, an intermediate node can dynamically control its optical shutter which makes it possible to design a fully distributed QoS assuring MAC protocol. We then present a QoS assuring distributed dynamic scheduling protocol, namely, minimum source round robin (minSrcRR) protocol, for opportunistic hyperchannels. Theoretical analysis on the effectiveness of the proposed QoS assuring protocol and the worst-case delay bound are also derived in this paper. The simulation results quantitatively demonstrate the advantage of opportunistic hyperchannels and the effectiveness of minSrcRR protocol. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the supernode-shape selection problem, which has been widely discussed in the bibliography. In general, the selection of the supernode transformation greatly affects the parallel execution time of the transformed algorithm. Since the minimization of the overall parallel execution time via an appropriate supernode transformation is very difficult to accomplish, researchers have focused on scheduling-aware supernode transformations that maximize parallelism during the execution. In this paper, we argue that the communication volume of the transformed algorithm is an important criterion, and its minimization should be given high priority. For this reason, we define the metric of the per-process communication volume and propose a method to minimize this metric by selecting a communication-aware supernode shape. Our approach is equivalent to defining a proper Cartesian process grid with MPI_Cart_Create, which means that it can be incorporated in applications in a straightforward manner. Our experimental results illustrate that by selecting the tile shape with the proposed method, the total parallel execution time is significantly reduced due to the minimization of the communication volume, despite the fact that a few more parallel execution steps are required. [ABSTRACT FROM AUTHOR]

Cloud computing economically enables customers with limited computational resources to outsource large-scale computations to the cloud. However, how to protect customers' confidential data involved in the computations then becomes a major security concern. In this paper, we present a secure outsourcing mechanism for solving large-scale systems of linear equations (LE) in cloud. Because applying traditional approaches like Gaussian elimination or LU decomposition (aka. direct method) to such large-scale LEs would be prohibitively expensive, we build the secure LE outsourcing mechanism via a completely different approach—iterative method, which is much easier to implement in practice and only demands relatively simpler matrix-vector operations. Specifically, our mechanism enables a customer to securely harness the cloud for iteratively finding successive approximations to the LE solution, while keeping both the sensitive input and output of the computation private. For robust cheating detection, we further explore the algebraic property of matrix-vector operations and propose an efficient result verification mechanism, which allows the customer to verify all answers received from previous iterative approximations in one batch with high probability. Thorough security analysis and prototype experiments on Amazon EC2 demonstrate the validity and practicality of our proposed design. [ABSTRACT FROM AUTHOR]

Abstract-Global-scale grids provide a massive source of processing power, providing the `means to support processor intensive parallel applications. The strong burstiness and unpredictability of the available processing and network resources raise the strong need to make applications robust against the dynamics of grid environments. The two main techniques that are most suitable to cope with the dynamic nature of the grid are Dynamic Load Balancing (DLB) and job replication (JR). In this paper, we analyze and compare the effectiveness of these two approaches by means of trace-driven simulations. We observe that there exists an easy-to-measure statistic Y and a corresponding threshold value Y[sup*], such that DLB consistently outperforms JR when Y > Y[sup*], whereas the reverse is true for Y < Y[sup*]. Based on this observation, we propose a simple and easy-to-implement approach, throughout referred to as the DLB/JR method, that can make dynamic decisions about whether to use DLB or JR. Extensive simulations based on a large set of real data monitored in a global-scale grid show that our DLB/JR method consistently performs at least as good as both DLB and JR in all circumstances, which makes our DLB/JR method highly robust against the unpredictable nature of global-scale grids. [ABSTRACT FROM AUTHOR]

Policies play an important role in network configuration and therefore in offering secure and high performance services especially over multi-tenant Cloud Data Center (DC) environments. At the same time, elastic resource provisioning through virtualization often disregards policy requirements, assuming that the policy implementation is handled by the underlying network infrastructure. This can result in policy violations, performance degradation and security vulnerabilities. In this paper, we define PLAN, a PoLicy-Aware and Network-aware VM management scheme to jointly consider DC communication cost reduction through Virtual Machine (VM) migration while meeting network policy requirements. We show that the problem is NP-hard and derive an efficient approximate algorithm to reduce communication cost while adhering to policy constraints. Through extensive evaluation, we show that PLAN can reduce topology-wide communication cost by 38 percent over diverse aggregate traffic and configuration policies. [ABSTRACT FROM PUBLISHER]

Reducing the cost of memory accesses, both in terms of performance and energy consumption, is a major challenge in shared-memory architectures. Modern systems have deep and complex memory hierarchies with multiple cache levels and memory controllers, leading to a Non-Uniform Memory Access (NUMA) behavior. In such systems, there are two ways to improve the memory affinity: First, by mapping threads that share data to cores with a shared cache, cache usage and communication performance are optimized. Second, by mapping memory pages to memory controllers that perform the most accesses to them and are not overloaded, the average cost of accesses is reduced. We call these two techniques thread mapping and data mapping, respectively. Thread and data mapping should be performed in an integrated way to achieve a compounding effect that results in higher improvements overall. Previous work in this area requires expensive tracing operations to perform the mapping, or require changes to the hardware or to the parallel application. In this paper, we propose kMAF, a mechanism that performs integrated thread and data mapping in the kernel. kMAF uses the page faults of parallel applications to characterize their memory access behavior and performs the mapping during the execution of the application based on the detected behavior. In an evaluation with a large set of parallel benchmarks executing on three NUMA architectures, kMAF achieved substantial performance and energy efficiency improvements, close to an Oracle-based mechanism and significantly higher than previous proposals. [ABSTRACT FROM PUBLISHER]

Statistics counters are essential in network measurement on tracking various network statistics and implementing various network counting sketches. For such applications it is crucial to maintain a large number of statistics counters at very high speeds. On the Internet with millions of flows, potentially millions of counters are required to be updated at wirespeed of 40 Gb/s and beyond. It is widely accepted that SRAM is too costly to store such large counter arrays entirely, and DRAM is too slow to catch up with the line rate. In this paper, we propose a DRAM-based architecture that takes advantage of the performance of modern commodity DRAM by interleaving counter updates to multiple memory banks. Our architecture is based on the observation that most flows on the Internet consist of multiple packets that are transmitted during a relatively short period of time, which are referred to as traffic bursts. Our proposed architecture makes use of a simple randomization scheme and a set of small fully associative request queues to statistically guarantee a near-perfect load balancing of counter updates to the memory banks. The architecture explores the benefit of traffic bursts to greatly reduce the maximum size of the request queues while providing a diminishing overflow probability guarantee. We also develop queuing models to show that as long as the flow sizes are heavy-tailed distributed due to traffic bursts, the maximum request queue length is always bounded by a small constant. The simulation results confirm the effectiveness of our queuing models. The proposed statistics counter arrays can effectively maintain line rate updates to a large number of counters while guaranteeing a diminishing overflow probability in the system. [ABSTRACT FROM AUTHOR]

We study the problem of skeleton extraction for large-scale sensor networks with reliance purely on connectivity information. Existing efforts in this line highly depend on the boundary detection algorithms, which are used to extract accurate boundary nodes. One challenge is that in practical this could limit the applicability of the boundary detection algorithms. For instance, in low node density networks where boundary detection algorithms do not work well, the extracted boundary nodes are often incomplete. This paper brings a new view to skeleton extraction from a distance transform perspective, bridging the distance transform of the network and the incomplete boundaries. As such, we propose a distributed and scalable algorithm for skeleton extraction, called DIST, based on DIStance$(T)$ransform, while incurring low communication overhead. The proposed algorithm does not require that the boundaries are complete or accurate, which makes the proposed algorithm more practical in applications. First, we compute the distance transform of the network. Specifically, the distance (hop count) of each node to the boundaries of a sensor network is estimated. The node map consisting of the distance values is considered as the distance transform (the distance map). The distance map is then used to identify skeleton nodes. Next, skeleton arcs are generated by controlled flooding within the identified skeleton nodes, thereby connecting these skeleton arcs, to extract a coarse skeleton. Finally, we refine the coarse skeleton by building shortest path trees followed by a prune phase. The obtained skeleton is robust to boundary noise or shape variations. Besides, we present two specific applications that benefit from the extracted skeleton: identifying complete boundaries and shape segmentation. First, with the extracted skeleton using DIST, we propose to identify more boundary nodes to form a meaningful boundary curve. Second, the utilization of the derived skeleton to segment the network into approximately convex pieces has been shown to be effective. [ABSTRACT FROM AUTHOR]

The cloud represents a computing paradigm where shared configurable resources are provided as a service over the Internet. Adding intra- or intercloud communication resources to the resource mix leads to a networked cloud computing environment. Following the cloud infrastructure as a Service paradigm and in order to create a flexible management framework, it is of paramount importance to address efficiently the resource mapping problem within this context. To deal with the inherent complexity and scalability issue of the resource mapping problem across different administrative domains, in this paper a hierarchical framework is described. First, a novel request partitioning approach based on Iterated Local Search is introduced that facilitates the cost-efficient and online splitting of user requests among eligible cloud service providers (CPs) within a networked cloud environment. Following and capitalizing on the outcome of the request partitioning phase, the embedding phase—where the actual mapping of requested virtual to physical resources is performed can be realized through the use of a distributed intracloud resource mapping approach that allows for efficient and balanced allocation of cloud resources. Finally, a thorough evaluation of the proposed overall framework on a simulated networked cloud environment is provided and critically compared against an exact request partitioning solution as well as another common intradomain virtual resource embedding solution. [ABSTRACT FROM AUTHOR]

This paper addresses the schedulability problem of periodic and sporadic real-time task sets with constrained deadlines preemptively scheduled on a multiprocessor platform composed by identical processors. We assume that a global work-conserving scheduler is used and migration from one processor to another is allowed during a task lifetime. First, a general method to derive schedulability conditions for multiprocessor real-time systems will be presented. The analysis will be applied to two typical scheduling algorithms: Earliest Deadline First (EDF) and Fixed Priority (FP). Then, the derived schedulability conditions will be tightened, refining the analysis with a simple and effective technique that significantly improves the percentage of accepted task sets. The effectiveness of the proposed test is shown through an extensive set of synthetic experiments. [ABSTRACT FROM AUTHOR]

Internet Protocol (IP) traceback is the enabling technology to control Internet crime. In this paper, we present a novel and practical IP traceback system called Flexible Deterministic Packet Marking (FDPM) which provides a defense system with the ability to find out the real sources of attacking packets that traverse through the network. While a number of other traceback schemes exist, FDPM provides innovative features to trace the source of IP packets and can obtain bettor tracing capability than others. In particular, FDPM adopts a flexible mark length strategy to make it compatible to different network environments; it also adaptively changes its marking rate according to the load of the participating router by a flexible flow-based marking scheme. Evaluations on both simulation and real system implementation demonstrate that FDPM requires a moderately small number of packets to complete the traceback process; add little additional load to routers and can trace a large number of sources in one traceback process with low false positive rates. The built-in overload prevention mechanism makes this system capable of achieving a satisfactory traceback result even when the router is heavily loaded. The motivation of this traceback system is from DDoS defense. It has been used to not only trace DDoS attacking packets but also enhance filtering attacking traffic. It has a wide array of applications for other security systems. [ABSTRACT FROM AUTHOR]

Serverless distributed computing has received significant attention from both the industry and the research community. Among the most popular applications are the wide-area network file systems, exemplified by CFS, Farsite, and OceanStore. These file systems store files on a large collection of untrusted nodes that form an overlay network. They use cryptographic techniques to maintain file confidentiality and integrity from malicious nodes. Unfortunately, cryptographic techniques cannot protect a file holder from a denial-of-service (DoS) attack or a host compromise attack. Hence, most of these distributed file systems are vulnerable to targeted file attacks, wherein an adversary attempts to attack a small (chosen) set of files by attacking the nodes that host them. This paper presents LocationGuard--a location hiding technique for securing overlay file storage systems from targeted file attacks. LocationGuard has three essential components: 1) location key, consisting of a random bit string (e.g., 128 bits) that serves as the key to the location of a file, 2) routing guard, a secure algorithm that protects accesses to a file in the overlay network given its location key such that neither its key nor its location is revealed to an adversary, and 3) a set of location inference guards, which refer to an extensible component of the LocationGuard. Our experimental results quantify the overhead of employing LocationGuard and demonstrate its effectiveness against DoS attacks, host compromise attacks, and various location inference attacks. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of searching a network for intruders. We propose a strategy for capturing the intruder in the popular interconnection topology, the star network. According to the proposed strategy, a team of collaborative software agents are responsible for capturing a hostile intruder (e.g., a virus). These agents asynchronously move along the network links, and the intruder has the capability of escaping arbitrarily fast. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of destination anonymity for applications in mobile ad hoc networks where geographic information is ready for use in both ad hoc routing and Internet services. Geographic forwarding becomes a lightweight routing protocol in favor of the scenarios. Traditionally, the anonymity of an entity of interest can be achieved by hiding it among a group of other entities with similar characteristics, i.e., an anonymity set. In mobile ad hoc networks, generating and maintaining an anonymity set for any ad hoc node is challenging because of the node mobility and, consequently, the dynamic network topology. We propose protocols that use the destination position to generate a geographic area called an anonymity zone (AZ). A packet for a destination is delivered to all the nodes in the AZ, which make up the anonymity set. The size of the anonymity set may decrease, because nodes are mobile, yet the corresponding anonymity set management is simple. We design techniques to further improve node anonymity and reduce communication overhead. We use analysis and extensive simulation to study the node anonymity and routing performance and to determine the parameters that most impact the anonymity level that can be achieved by our protocol. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel approach for reducing the download time of large files over the Internet. Our approach, known as Parallelized File Transport Protocol (P-FTP), proposes simultaneous downloads of disjoint file portions from multiple file servers. P-FTP server selects file servers for the requesting client on the basis of a variety of QoS parameters, such as available bandwidth and server utilization. The sensitivity analysis of our file server selection technique shows that it performs significantly better than random selection. During the file transfer, P-FTP client monitors the file transfer flows to detect slow servers and congested links and adjusts the file distributions accordingly. P-FTP is evaluated with simulations and real-world implementation. The results show at least 50 percent reduction in download time when compared to the traditional file-transfer approach. Moreover, we have also carried out a simulation-based study to investigate the issues related to large scale deployment of our approach on the Internet. Our results demonstrate that a large number of P-FTP users has no adverse effect on the performance perceived by non-P-FTP users. In addition, the file servers and network are not significantly affected by large scale deployment of P-FTP. [ABSTRACT FROM AUTHOR]

A number of structured peer-to-peer (P2P) lookup protocols have been proposed recently. A P2P lookup protocol routes a lookup request to its target node in a P2P distributed system. Existing protocols achieve balanced routing traffic among nodes by assuming that lookup requests are evenly targeted at every node. However, when lookup requests concentrate on a few nodes simultaneously, these nodes become hot spots. Due to uneven routing patterns in existing protocols, hot spots cause unbalanced routing traffic which leads to routing bottlenecks. In this paper, we present a novel structured P2P lookup protocol called SCALLOP that delivers balanced routing and avoids routing bottlenecks at occurrences of hot spots. Among existing protocols, SCALLOP is the first one to accomplish this goal at the fundamental nature of a routing protocol. SCALLOP achieves balanced routing by uniquely constructing a balanced lookup tree for each node. The balanced tree evenly distributes routing traffic among sibling nodes and, therefore, avoids or reduces routing bottlenecks. In addition, as a load-balanced protocol, SCALLOP delivers asymptotically optimal lookup performance at the tradeoff between routing path and routing table size. We conducted a set of simulations to demonstrate the effectiveness of SCALLOP. The results show that, compared with a most-referenced and representative structured P2P lookup protocol and a graph-based extension of this protocol, SCALLOP significantly reduces routing bottlenecks while all three protocols deliver comparable lookup performance. [ABSTRACT FROM AUTHOR]

RPS is a publicly available toolkit that allows a practitioner to straightforwardly create flexible online and offline resource prediction systems in which resources are represented by independent, periodically sampled, scalar-valued measurement streams. The systems predict the future values of such streams from past values and are composed at runtime out of a large and extensible set of communicating components that are in turn constructed using RPS's extensible sensor, prediction, wavelet, and communication libraries. This paper describes the design, implementation, and performance of RPS. We have used RPS extensively to evaluate predictive models and build online prediction systems for host load, Windows performance data, and network bandwidth. The computation and communication overheads involved in such systems are quite low. [ABSTRACT FROM AUTHOR]

Peer-to-peer (P2P) system is an overlay network of peer computers without centralized servers, and many applications have been developed for such networks such as file sharing systems. Because a set of peers dynamically changes, design and verification of efficient protocols is a challenging task. In this paper, we consider an object searching problem under a resource model such that there are some replicas in a system and the lower bound of the ratio p = n'/n is known in advance, Where n' is a lower bound of the number of peers that hold original or replica for any object type and n is the total number of peers. In addition, we consider object searching with probabilistic success, i.e., for each object search, object must be found with at least probability 0 < σ < 1. To solve such a problem efficiently, we propose a new communication structure, named probabilistic weak quorum systems (PWQS), which is an extension of coterie. Then, we propose a fault-tolerant protocol for searching for objects in a P2P system. lb our method, each peer does not maintain global information such as the set of all peers and a logical topology with global consistency. In our protocol, each peer communicates only a small part of a peer set and, thus, our protocol is adaptive for huge scale P2P network. [ABSTRACT FROM AUTHOR]

The development and deployment of distributed network-aware applications and services require the ability to compile and maintain a model of the underlying network resources with respect to one or more characteristic properties of interest. To be manageable, such models must be compact; and to be general-purpose, should enable a representation of properties along temporal, spatial, and measurement resolution dimensions. In this paper, we propose MINT—a general framework for the construction of such metric-induced models using end-to-end measurements. We present the basic theoretical underpinnings of MINT for a broad class of performance metrics, and describe PERISCOPE, a Linux embodiment of MINT constructions. We instantiate MINT and PERISCOPE for a specific metric of interest—namely, packet loss rates—and present results of simulations and Internet measurements that confirm the effectiveness and robustness of our constructions over a wide range of network conditions. [ABSTRACT FROM AUTHOR]

Efficient and reliable communication is essential for achieving high performance in a networked computing environment. Finite network resources bring about unavoidable competition among in-flight network packets, resulting in network congestion and, possibly, deadlock. Many techniques have been proposed to improve network performance by efficiently handling network congestion and potential deadlock. However, none of them provide an efficient way of accelerating the movement of network packets in congestion toward their destinations. In this paper, we propose a new mechanism for detecting and resolving network congestion and potential deadlocks. The proposed mechanism is based on efficiently tracking paths of congestion and increasing the scheduling priority of packets along those paths. This acts to throttle other packets trying to enter those congested regions-in effect, locking out packets from congested regions until congestion has had the opportunity to disperse. Simulation results show that the proposed technique effectively disperses network congestion and is also applicable in helping to resolve potential deadlock. [ABSTRACT FROM AUTHOR]

Distributed denial of service (DDoS) is a major threat to the availability of Internet services. The anonymity allowed by lP networking, together with the distributed, large scale nature of the Internet, makes DDoS attacks stealthy and difficult to counter. To make the problem worse, attack traffic is often indistinguishable from normal traffic. As various attack tools become widely available and require minimum knowledge to operate, automated, anti-DDoS systems become increasingly important. Many current solutions are either excessively expensive or require universal deployment across many administrative domains. This paper proposes two perimeter-based defense mechanisms for Internet service providers (lSPs) to provide the anti-DDoS service to their customers. These mechanisms rely completely on the edge routers to cooperatively identify the flooding sources and establish rate-limit filters to block the attack traffic. The system does not require any support from routers outside or inside of the ISP, which not only makes it locally deployable, but also avoids the stress on the ISP core routers. We also study a new problem of perimeter-based IP traceback and provide three solutions. We demonstrate analytically and by simulations that the proposed defense mechanisms react quickly in blocking attack traffic while achieving high survival ratio for legitimate traffic. Even when 40 percent of all customer networks attack, the survival ratio for traffic from the other customer networks Is still close to 100 percent. [ABSTRACT FROM AUTHOR]

We perform a large-scale topology mapping and geolocation study for China's Internet. To overcome the limited number of Chinese PlanetLab nodes and looking glass servers, we leverage unique features in China's Internet, including the hierarchical structure of the major ISPs and the abundance of IDC data centers. Using only 15 vantage points, we design a traceroute scheme that finds significantly more interfaces and links than iPlane with significantly fewer traceroute probes. We then consider the problem of geolocating router interfaces and end hosts in China. When examining three well-known Chinese geoIP databases, we observe frequent occurrences of null replies and erroneous entries, suggesting that there is significant room for improvement. We develop a heuristic for clustering the interface topology of a hierarchical ISP, and then apply the heuristic to the major Chinese ISPs. We show that the clustering heuristic can geolocate router interfaces with significantly more detail and consistency than can the existing geoIP databases in isolation. We show that the resulting clusters expose several characteristics of the Chinese Internet, including the major ISPs' provincial structure and the centralized interconnections among the ISPs. Finally, using the clustering heuristic, we propose a methodology for improving commercial geoIP databases and evaluate using IDC data center landmarks. [ABSTRACT FROM AUTHOR]

As part of the security within distributed systems, various services and resources need protection from unauthorized use. Remote authentication is the most commonly used method to determine the identity of a remote client. This paper investigates a systematic approach for authenticating clients by three factors, namely password, smart card, and biometrics. A generic and secure framework is proposed to upgrade two-factor authentication to three-factor authentication. The conversion not only significantly improves the information assurance at low cost but also protects client privacy in distributed systems. In addition, our framework retains several practice-friendly properties of the underlying two-factor authentication, which we believe is of independent interest. [ABSTRACT FROM AUTHOR]

A distinct trend has emerged that the Internet is used to transport data on a more and more massive scale. Capacity shortage in the backbone networks has become a genuine possibility, which will be more serious with fiber-based access. The problem addressed in this paper is how to conduct massive content distribution efficiently in the future network environment, where the capacity limitation can equally be at the core or the edge. We propose a novel technique as a main content transport mechanism to achieve efficient network resource utilization. The technique uses multiple trees for distributing different file pieces, which at the heart is a version of swarming. In this paper, we formulate an optimization problem for determining an optimal set of distribution trees as well as the rate of distribution on each tree under bandwidth limitation at arbitrary places in the network. The optimal solution can be found by a distributed algorithm. The results of the paper not only provide stand-alone solutions to the massive content distribution problem, but should also help the understanding of existing distribution techniques such as BitTorrent or FastReplica. [ABSTRACT FROM AUTHOR]

Abstract-Consistency maintenance mechanism is necessary for the emerging peer-to-peer (P2P) applications due to their frequent data updates. Centralized approaches suffer from single point of failures, while previous decentralized approaches consume too many network resources because of locality-ignorant structures. To address this issue, we propose a scalable and efficient consistency maintenance scheme for heterogeneous P2P systems. Our scheme takes the heterogeneity nature into account and forms the replica nodes of a key into a locality-aware hierarchical structure, in which the upper layer is Distributed Hash Table (DHT)-based and consists of powerful and stable replica nodes, while a replica node at the lower layer attaches to a physically close upper layer node. A d-ary update message propagation tree (UMPT) is dynamically built upon the upper layer for propagating the updated contents. As a result, the tree structure does not need to be maintained all the time, saving a lot of cost. Through theoretical analyses and comprehensive simulations, we examine the efficiency and scalability of this design. The results show that, compared with previous designs, especially locality-ignorant ones, our approach is able to reduce the cost by about 25-67 percent. [ABSTRACT FROM AUTHOR]

Presents information pertaining to the real-time communication in the distributed computing systems. Importance of the timely delivery intertask messages called real-time communication; Definition of the real-time channel; Inadequacy of the failure-handling techniques.

Wireless sensor networks (WSNs) have been widely used in many areas for critical infrastructure monitoring and information collection. While confidentiality of the message can be ensured through content encryption, it is much more difficult to adequately address source-location privacy (SLP). For WSNs, SLP service is further complicated by the nature that the sensor nodes generally consist of low-cost and low-power radio devices. Computationally intensive cryptographic algorithms (such as public-key cryptosystems), and large scale broadcasting-based protocols may not be suitable. In this paper, we first propose criteria to quantitatively measure source-location information leakage in routing-based SLP protection schemes for WSNs. Through this model, we identify vulnerabilities of some well-known SLP protection schemes. We then propose a scheme to provide SLP through routing to a randomly selected intermediate node (RSIN) and a network mixing ring (NMR). Our security analysis, based on the proposed criteria, shows that the proposed scheme can provide excellent SLP. The comprehensive simulation results demonstrate that the proposed scheme is very efficient and can achieve a high message delivery ratio. We believe it can be used in many practical applications. [ABSTRACT FROM AUTHOR]

Congestion management is likely to become a critical issue in interconnection networks, as increasing power consumption and cost concerns lead to improvements in the efficiency of network resources. In previous configurations, networks were usually oversized and underutilized. In a smaller network, however, contention is more likely to occur and blocked packets cause head-of-line (HoL) blocking among the rest of the packets, spreading congestion quickly. The best-known solution to HoL blocking is Virtual Output Queues (VOQs). However, the cost of implementing VOQs increases quadratically with the number of output ports in the network, making it unpractical. The situation is aggravated when several priorities and/or Quality of Service (QoS) levels must be supported. Therefore, a more scalable and cost-effective solution is required to reduce or eliminate HoL blocking. In this paper, we present a family of methodologies, referred to as Destination-Based Buffer Management (DBBM), to reduce/eliminate the HoL blocking effect on interconnection networks. DBBM efficiently uses the resources (mainly memory queues) of the network. These methodologies are comprehensively evaluated in terms of throughput, scalability, and fairness. Results show that using the DBBM strategy, with a reduced number of queues at each switch, it is possible to achieve roughly the same throughput as the VOQ mechanism. Moreover, all of the proposed strategies are designed in such a way that they can be used in any switch architecture. We compare DBBM with RECN, a sophisticated mechanism that eliminates HoL blocking in congestion situations. Our mechanism is able to achieve almost the same performance with very low logic requirements (in contrast with RECN). [ABSTRACT FROM AUTHOR]

Large peer-to-peer systems exhibit the presence of communities based on user interests. Resources commonly shared within individual communities are in general relatively less popular and inconspicuous in the system-wide behavior. Hence, such communities are unable to benefit significantly from caching and replication that focus only on the most dominant queries. A community-based caching (CBC) solution that enhances both community-wide and system-wide lookup performance is proposed. CBC consists of a suboverlay formation scheme and a local-knowledge-based distributed caching (LKDC) algorithm. Suboverlays enable communities to forward queries through their members. While queries are forwarded, the LKDC algorithm causes members to identify and cache resources of interests to them, resulting in faster resolution of queries for popular resources within each community. Distributed local caching requires global information (e.g., hop count and popularity of contents) that is difficult and costly to obtain. However, by means of an analysis of globally optimal behavior and structural properties of the overlay, we developed the heuristic-based LKDC algorithm that not only relies on purely local information but also provides close-to-optimal caching performance. CBC is adaptive to changing popularity and user interests, works with any skewed distribution of queries, and introduces minimal modifications and overhead to the overlay network. [ABSTRACT FROM AUTHOR]

Scheduling multisource divisible loads is a challenging task as different sources should cooperate and share their computing power with others to balance their loads and minimize total computational time. In this study, we attempt to address a generalized divisible load scheduling problem for handling loads from multiple sources on arbitrary networks. This problem is all the more challenging as 1) the topology is arbitrary, 2) in such networks, it is difficult to decide from which source and which route a processing node should receive loads, and 3) processing nodes must be allocated to different sources when they become available. We study two distinct cases of interest, static case and dynamic case, and propose two novel strategies, referred to as Static Scheduling Strategy (SSS) and Dynamic Scheduling Strategy (DSS), respectively. Both strategies work in an iterative fashion. In each iteration, they will use a novel Graph Partitioning (GP) scheme to partition the network such that each source in the network gains a portion of network resources and then these sources cooperate to process their loads. We analyze the performance of DSS using queuing theory and derive upper bounds on a load's average waiting time and a source's average queue length. We use simulation to verify the usefulness and effectiveness of SSS and DSS. Our findings reveal an interesting "load insensitive" property of SSS and also verify the theoretical upper bound of average queue length at each source in the dynamic case. [ABSTRACT FROM AUTHOR]

Most P2P Video-on-Demand (VOD) schemes focus more on mending service architectures and optimizing overlays but do not carefully consider the user behavior and the benefit of prefetching strategies. As a result, they cannot better support VCR-oriented services in terms of substantive asynchronous clients or free VCR controls for P2P VODs. To address this issue, we propose VOVO, a VCR-oriented VOD for large-scale P2P networks. By mining associations inside each video, the segments requested in VCR interactivities are predicted based on the information collected through gossips. Together with a hybrid caching strategy, a collaborative prefetching scheme is designed to optimize resource distribution among neighboring peers. We evaluate VOVO through extensive experiments. Results show that VOVO is scalable and effective, providing short start-up latencies and good performance in VCR interactivities. [ABSTRACT FROM AUTHOR]

We propose a novel payment-based incentive scheme for peer-to-peer (P2P) live media streaming. Using this approach, peers earn points by forwarding data to others. The data streaming is divided into fixed-length periods; during each of these periods, peers compete with each other for good parents (data suppliers) for the next period in a first-price-auction-like procedure using their points. We design a distributed algorithm to regulate peer competitions and consider various individual strategies for parent selection from a game-theoretic perspective. We then discuss possible strategies that can be used to maximize a peer's expected media quality by planning different bids for its substreams. Finally, in order to encourage off-session users to remain online and continue contributing to the network, we develop an optimal data forwarding strategy that allows peers to accumulate points that can be used in future services. Simulation results show that the proposed methods effectively differentiate the media qualities received by peers making different contributions (which originate from, for example, different forwarding bandwidths or servicing times) and at the same time maintain high overall system performance. [ABSTRACT FROM AUTHOR]

A commonly employed abstraction for studying the object placement problem for the purpose of Internet content distribution is that of a distributed replication group. In this work, the initial model of the distributed replication group of Left et al. [1] is extended to the case that individual nodes act selfishly, i.e., cater to the optimization of their individual local utilities. Our main contribution is the derivation of equilibrium object placement strategies that 1) can guarantee improved local utilities for all nodes concurrently as compared to the corresponding local utilities under greedy local object placement, 2) do not suffer from potential mistreatment problems, inherent to centralized strategies that aim at optimizing the social utility, and 3) do not require the existence of complete information at all nodes. We develop a baseline computationally efficient algorithm for obtaining the aforementioned equilibrium strategies and then extend it to improve its performance with respect to fairness. Both algorithms are realizable, in practice, through a distributed protocol that requires only a limited exchange of information. [ABSTRACT FROM AUTHOR]

We consider the problem of providing per-customer service guarantees in a high-speed packet switch typically situated at the edge between a set of customers and a service provider network. As basic requirements, the switch should be scalable to high speeds per port, a large number of ports, and a large number of customers (macroflows) with independent guarantees. Existing scalable solutions are based on virtual output queuing, which is computationally complex when required to provide service guarantees for a large number of macroflows. We present a novel architecture for packet switching that provides support for such service guarantees. A cost-effective fabric with small external speedup is combined with a feedback mechanism that enables the fabric to be virtually lossless, thus avoiding packet drops indiscriminate of macroflows' behavior. Through analysis and simulation, we show that this architecture provides accurate support for service guarantees, has low computational complexity, and is scalable to very high port speeds. [ABSTRACT FROM AUTHOR]

Tracing DoS attacks that employ source address spoofing is an important and challenging problem. Traditional traceback schemes provide spoofed packets traceback capability either by augmenting the packets with partial path information (i.e., packet marking) or by storing packet digests or signatures at intermediate routers (i.e., packet logging). Such approaches require either a large number of attack packets to be collected by the victim to infer the paths (packet marking) or a significant amount of resources to be reserved at intermediate routers (packet logging). We adopt a hybrid traceback approach in which packet marking and packet logging are integrated in a novel manner, so as to achieve the best of both worlds, that is, to achieve a small number of attack packets to conduct the traceback process and a small amount of resources to be allocated at intermediate routers for packet logging purposes. Based on this notion, two novel traceback schemes are presented. The first scheme, called Distributed Link-List Traceback (DLLT), is based on the idea of preserving the marking information at intermediate routers in such a way that it can be collected using a link list-based approach. The second scheme, called Probabilistic Pipelined Packet Marking (PPPM), employs the concept of a "pipeline" for propagating marking information from one marking router to another so that it eventually reaches the destination. We evaluate the effectiveness of the proposed schemes against various performance metrics through a combination of analytical and simulation studies. Our studies show that the proposed schemes offer a drastic reduction in the number of packets required to conduct the traceback process and a reasonable saving in the storage requirement. [ABSTRACT FROM AUTHOR]

We study the connection capacity of a class of rearrangeable nonblocking (RNB) and strictly nonblocking (SNB) networks with/without crosstalk-free constraint, model their routing problems as weak or strong edge-colorings of bipartite graphs, and propose efficient routing algorithms for these networks using parallel processing techniques. This class of networks includes networks constructed from Banyan networks by horizontal concatenation of extra stages and/or vertical stacking of multiple planes. We present a parallel algorithm that runs in O(lg² N) time for the RNB networks of complexities ranging from O(N lg N) to O(N1.5 lg N) crosspoints and parallel algorithms that run in O(min{d* Ig N, √N}) time for the SNB networks of O(N1.5 lg N) crosspoints, using a completely connected multiprocessor system of N processing elements. Our algorithms can be translated into algorithms with an O(lg N lg lg N) slowdown factor for the class of N-processor hypercubic networks, whose structures are no more complex than a single plane in the RNB and SNB networks considered. [ABSTRACT FROM AUTHOR]

Peer-to-Peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatch between the P2P overlay network and the physical underlying network. The topology mismatch problem brings great stress in the Internet infrastructure. It greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary, traffic, we propose a location-aware topology matching (LTM) technique. LTM builds an efficient overlay by disconnecting slow connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network. The effectiveness of LTM is demonstrated through simulation studies. [ABSTRACT FROM AUTHOR]

Presents a slowdown model for applications executing on time-shared clusters of computer workstations. Retardation of application execution through competition of shared computer network resources; Focus of model on types of slowdown; Provision of accurate estimate of application performance.