Modern storage-intensive server applications such as key-value stores and relational databases often rely on thread oversubscription to sustain high throughput in cloud environments. While effective at hiding I/O stalls, this practice introduces serious challenges, including unpredictable query behaviors, instruction-per-query (IPQ) inflation, and instability in dynamic power management (DPM). Existing quality-of-service (QoS)-centric or energy-centric techniques, developed in isolation at one of the service layers, fail to holistically optimize resource and energy efficiency under connection-level QoS constraints. This paper presents REEF (Resource- and Energy-Efficient user-space scheduling Framework), a non-intrusive, cross-layer approach that coordinates query processing across the network stack, application layer, and OS resource manager. REEF transforms self-serving threads into on-call threads activated by near-optimal, proactively batched scheduling, enabling deep CPU C-state residency and mitigating CPU and I/O contention. Our extensive evaluation on real server applications (MongoDB and MySQL) demonstrates that REEF can substantially improve the energy efficiency of server applications under different connection-level QoS schemes, by up to 53.45% for throughput per power, up to 2.18× and 5.33× for coefficient of P99 and P99.9 tail-latency per power respectively, and significantly reduce resource consumption, by up to 73.65% in CPU frequency.

A fundamental design principle of MultiPath TCP (MPTCP) congestion control algorithm (CCA) is that an MPTCP flow should be fair to and do not harm TCP flows. Unfortunately, to deal with cost heterogeneity among subflow interfaces, the existing cost-aware MPTCP CCAs often violate this design principle in an attempt to minimize the cost. Based on the network utility maximization (NUM) framework, we put forward UniMPTCP($\vec \omega $,n), a NUM-optimal, Unified MPTCP CCA with n subflow paths and a n-dimension weight vector $\vec \omega $ with n −1 independent elements. Uni-MPTCP($\vec \omega $,n) abides by this design principle for arbitrary $\vec \omega $ and can be customized to achieve specific cost design objectives with proper adaptation of $\vec \omega $. As such, UniMPTCP($\vec \omega $,n) provides a unified solution to enable cost-aware MPTCP CCAs, while adhering to the design principle. Finally, we put forward an adaptation algorithm for, ω, in Uni-MPTCP(ω,2), aiming at maintaining a target MPTCP flow rate with minimum cost for a cost-heterogeneity case with dual connectivity. The test results based on NS-3 simulation demonstrate that UniMPTCP(ω,2) can indeed effectively keep track of a given flow rate target with minimum cost, while adhering to the design principle.

A primary design objective for user-facing services for cloud and edge computing is to maximize query throughput, while meeting query tail latency Service Level Objectives (SLOs) for individual queries. Unfortunately, the existing solutions fall short of achieving this design objective, which we argue, is largely attributed to the fact that they fail to take the query fanout explicitly into account. In this paper, we propose TailGuard based on a Tail-latency-SLO-and-Fanout-aware Earliest-Deadline-First Queuing policy (TF-EDFQ) for task queuing at individual task servers the query tasks are fanned out to. With the task pre-dequeuing time deadline for each task being derived based on both query tail latency SLO and query fanout, TailGuard takes an important first step towards achieving the design objective. A query admission control scheme is also developed to provide tail latency SLO guarantee in the presence of resource shortages. TailGuard is evaluated against First-In-First-Out (FIFO) task queuing, task PRIority Queuing (PRIQ) and Tail-latency-SLO-aware EDFQ (T-EDFQ) policies by both simulation and testing in the Amazon EC2 cloud. It is driven by three types of applications in the Tailbench benchmark suite, featuring web search, in-memory key-value store, and transactional database applications. The results demonstrate that TailGuard can significantly improve resource utilization (e.g., up to 80% compared to FIFO), while also meeting the targeted tail latency SLOs, as compared with the other three policies. TailGuard is also implemented and tested in a highly heterogeneous Sensing-$a$s-a-Service (SaS) testbed for a data sensing service, demonstrating performance gains of up to 33% . These results are consistent with both the simulation and Amazon EC2 results.

Federated computing, including federated learning and federated analytics, needs to meet certain task Service Level Objective (SLO) in terms of various performance metrics, e.g., mean task response time and task tail latency. The lack of control and access to client activities requires a carefully crafted client selection process for each round of task processing to meet a designated task SLO. To achieve this, one must be able to predict task performance metrics for a given client selection per round of task execution. In this paper, we develop, FedSLO, a general framework that allows task performance in terms of a wide range of performance metrics of practical interest to be predicted for synchronous federated computing systems, in line with the Google federated learning system architecture. Specifically, with each task performance metric expressed as a cost function of the task response time, a relationship between the task performance measure - the mean cost and task/subtask response time distributions is established, allowing for unified task performance prediction algorithms to be developed. Practical issues concerning the computational complexity, measurement cost and implementation of FedSLO are also addressed. Finally, we propose preliminary ideas on how to apply FedSLO to the client selection process to enable task SLO guarantee.

Unexpected long query latency of a database system can cause domino effects on all the upstream services and severely degrade end users' experience with unpredicted long waits, resulting in an increasing number of users disengaged with the services and thus leading to a high user disengagement ratio (UDR). A high UDR usually translates to reduced revenue for service providers. This paper proposes UTSLO, a UDR-oriented SLO guaranteed system, which enables a database system to support multi-tenant UDR targets in a cost-effective fashion through UDR-oriented capacity planning and dynamic UDR target enforcement. The former aims to estimate the feasibility of UDR targets while the latter dynamically tracks and regulates per-connection query latency distribution needed for accurate UDR target guarantee. In UTSLO, the database service capacity can be fully exploited to efficiently accommodate tenants while minimizing resources required for UDR target guarantee.

A primary design objective for Data-intensive User-facing (DU) services for cloud and edge computing is to maximize query throughput, while meeting query tail latency Service Level Objectives (SLOs) for individual queries. Unfortunately, the existing solutions fall short of achieving this design objective, which we argue, is largely attributed to the fact that they fail to take the query fanout explicitly into account. In this paper, we propose TailGuard based on a Tail-latency-SLO-and-Fanout-aware Earliest-Deadline-First Queuing policy (TF-EDFQ) for task queuing at individual task servers the query tasks are fanned out to. With the task queuing deadline for each task being derived based on both query tail latency SLO and query fanout, TailGuard takes an important first step towards achieving the design objective. TailGuard is evaluated against First-In-First-Out (FIFO) task queuing, task PRIority Queuing (PRIQ) and Tail-latency-SLO-aware EDFQ (T-EDFQ) policies by simulation. It is driven by three types of applications in the Tailbench benchmark suite. The results demonstrate that TailGuard can improve resource utilization by up to 80%, while meeting the targeted tail latency SLOs, as compared with the other three policies. TailGuard is also implemented and tested in a highly heterogeneous Sensing-as-a-Service (SaS) testbed for a data sensing service, with test results in line with the other ones.

Modern database systems suffer from compromised throughput, persistent unfair I/O processing and unpredictable, high latency variability of user requests as a result of mismatches between highly scaled user parallel I/O and the I/O capacity afforded by the database and its underlying storage I/O stack. To address this problem, we introduce an efficient user-centric QoS-aware scheduling shim, called AppleS, for user-level fine-grained I/O regulation that delivers the right amount and pattern of user parallel I/O requests to the database system and supports user SLOs with high-level performance isolation and reduced I/O resource contention. It is designed to enable database systems to proactively regulate user request behaviors based on runtime conditions to reshape user access pattern to hide excessive user parallelism from the I/O stack that has a limited concurrent processing capability. This helps achieve scalable throughput for multi-user workloads in a fair and stable manner. AppleS is implemented as a user-space shim for transparent user-differentiated I/O scheduling, making it highly flexible and portable. Our extensive evaluation, run on real databases (MySQL and MongoDB), demonstrates that, by incorporating AppleS in the existing database systems, our solution can not only improve the throughput (up to 39.2%) in a fairer (3.2× to 40.6× fairness improvement) and more stable (up to 2× lower latency variability) manner, but also support user SLOs with less I/O provisioning.

Multiple Path Transmission Control Protocols (MPTCPs) allow flows to explore path diversity of datacenter networks and multihoming to improve throughput, reliability, and network resource utilization. However, the existing MPTCPs are largely empirical by design and fall short of achieving satisfactory tradeoffs among responsiveness, TCP fairness and throughput. By leveraging the TCP utility and a network-utility-maximization (NUM) solution for concave utilities, in this paper, we derive and implement in Linux kernels two distinct families of NUM-optimal MPTCP protocols, EUTCP ($\gamma$), a function of a rate-scaling vector of the sub-flow rate-scaling coefficients,$\gamma$, and WUTCP ($\omega$), a function of a utility weight vector of the sub-flow weights,$\omega$, respectively. While the former allows resource pooling, the latter does not. We then show that the Semicoupled algorithm and EWTCP are in fact EUTCP(1) and WUTCP$(1/m^{2})$, where$m$is the number of sub-flow paths, and hence, are NUM-optimal. The performance of the two families with equal weight and equal rate-scaling coefficient for all sub-flows when coexisting with TCP is also analyzed based on experiments in a testbed. In particular, the test results demonstrate that the family members of EUTCP ($\gamma$) with rate-scaling coefficient in the range of [1, 1.1] outperform three well-known MPTCPs with resource pooling capability, including LIA, OLIA and Balia, in terms of achieving satisfactory tradeoffs among responsiveness, fairness and throughput. Finally, the effectiveness of the proposed algorithms compared to the existing ones is further confirmed by simulation in a fat-tree datacenter network topology running both long and short flows.

The Fork-Join structure underlays many distributed computing applications in data centers. In this paper, we develop a technique, called ForkMV, to estimate the mean and variance of request response time for Fork-Join queuing networks (FJQNs) with both short-tailed and long-tailed service time distributions and arbitrary request fanout degrees (i.e., the number of Fork nodes). Specifically, for an FJQN with any given service time distribution of practical interests, ForkMV is able to estimate the mean and variance of request response time, accurate enough to facilitate effective resource allocation for data center applications. The test results indicate that in the entire range of the fanout degrees being tested (i.e., [1], [4000]), ForkMV is able to estimate the mean response time within 5 % and 15 % and variance response time within 15% and 10% of the simulation results for short-tailed exponential service distribution and long-tailed truncated Pareto distribution, respectively, at the 90 % load or higher.

TCAM is widely used for flow table lookup in Software-Defined Networking (SDN) switches for datacenter and enterprise networks. While its lookup throughput is unparalleled, TCAM updating, particularly for new rule insertions, can impair the overall system performance. A rule insertion entails two steps: 1) Computing the rule moving operations; and 2) Interrupting the TCAM lookups to apply the operations. In previous work, the performance gain on one step is always at the expense of the performance loss on the other. However, update throughput and latency depend on both. In this paper, we present a faster and more balanced TCAM update scheme, which not only achieves the shortest interrupt time so far but also significantly reduces the computation time. By using a novel sequential stack, FastUp reduces the time and space complexity of the state-of-the-art schemes from$O(m^{2})$and$O(m)$to$O(m\log h)$and$O(h)$, respectively, where$h << m$. Evaluations show that FastUp shortens the computation time and the interrupt time by$100\times$and$1.6\times$, respectively, which is equivalent to update delay${15\times}$reduction and$\mathbf{10\times}$update throughput gain against the state-of-the-art schemes. Moreover, we debunk a common mistake and show the dynamic programming based algorithm cannot be used to solve the reorder problem, and instead we use a bidirectional rule moving method to address the problem. In addition, we propose a practical method to find the theoretical lower bound of interrupt time in relatively large TCAM, which can be used to evaluate the optimality degree of TCAM update schemes. Evaluations show that FastUp achieves 90 % optimality.

Today s datacenters need to meet service level objectives (SLOs) for applications, which can be translated into deadlines for (co)flows running between job execution stages. As a result, meeting (co)flow deadlines with high probabilities is essential to attract and retain customers and hence, generate high revenue. To fill the lack of a transport protocol that can facilitate low (co)flow deadline miss rate, especially in the face of incast congestion, in this paper, we propose DCMRG, an incast-coflow-aware, ECN-based soft minimum-rate-guaranteed congestion control protocol for datacenter applications. DCMRG is composed of two major components, i.e., a congestion controller running on the send host and an incast congestion controller running on the receive host. DCMRG possesses three salient features. First, it is the first congestion control protocol that integrates congestion control with coflow-aware incast control while providing soft minimum flow rate guarantee. Second, DCMRG is readily deployable in datacenter networks. It only requires software upgrade in the hosts and minimum assistance (i.e., ECN) from in-network nodes. Third, DCMRG is backward compatible with and, by design, friendly to the widely deployed, standard-based transport protocols, such as DCTCP. The results from large-scale datacenter network simulation demonstrate that in the absence of incast congestion, DCMRG can reduce flow deadline miss rates by 3x and 1.6x compared to D2TCP and MRG, respectively. Moreover, DCMRG further reduces the coflow deadline miss rate by more than 40% and 60% and lowers the packet drop probability by 60% and 80%, in the face of incast congestion, compared to D2TCP with ICTCP and MRG with ICTCP, respectively.

While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40~100× and the interrupt time by 1.2~2.5×. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90%.

In this paper, we put forward a HOListic traffic control framework for datacenter NETworks (HOLNET). HOLNET reformulates the network utility maximization (NUM) framework into a HOLNET NUM framework that fully harnesses the potential of the existing NUM-based solutions to allow large families of traffic control protocols of various degrees of sophistication to be developed, i.e., host-based, single or multiple Class-of-Service (CoS) enabled, single or multi-path congestion control, with or without in-network load balancing. Unlike the existing solutions that are largely empirical and point by design, HOLNET is a principled, systematic framework. All the protocols in a family developed under HOLNET share a common, user-defined global optimization objective and fairness criterion. As a result, the protocols in a family can be fairly compared and carefully selected to fully explore the performance, scalability and design complexity tradeoffs. Case studies, based on both a single and a multi-path host-based solutions, demonstrate the viability and flexibility in HOLNET design space exploration. To further test the backward compatibility and performance with respect to some existing lightweight solutions, we develop HOLNET-UTA, an integrated congestion control and load balancing protocol, achieving TCP-fair resource allocation. HOLNET-UTA is found by simulation to improve the average flow completion time (FCT) by more than 20%, compared to DRILL with DCTCP.

In today's datacenters, job heterogeneity makes it difficult for schedulers to simultaneously meet latency requirements and maintain high resource utilization. The state-of-the-art datacenter schedulers, including centralized, distributed, and hybrid schedulers, fail to ensure low latency for short jobs in large-scale and highly loaded systems. The key issues are the scalability in centralized schedulers, ineffective and inefficient probing and resource sharing in both distributed and hybrid schedulers.

Video caching has gained significant attention due to its cost efficiency. In this paper, we propose an optimized cache replacement scheme based on the user request arrival pattern. The users are grouped among all possible request intervals, and the user density is calculated in each interval. The groups with highest user density are cached. Whenever a group with high user density arrives, the groups with lower density will be replaced. The simulation results show that the proposed schemes can double the hit ratio compared with the Least recently Used (LRU) scheme.

Longest Prefix Matching (LPM), Policy Filtering (PF), and Content Filtering (CF) are three important tasks for Internet nowadays. It is both technologically and economically important to develop integrated solutions to the effective execution of the three tasks. To this end, in this paper, we propose a distributed Ternary Content Addressable Memory (TCAM) coprocessor architecture. The integrated solution exploits the complementary lookup load and storage load requirements of the three tasks to balance the lookup load and storage load among the TCAMs. A prefix filtering-based CF algorithm is designed to reduce the lookup load and a novel cache system is developed to dynamically handle the lookups from overloaded TCAMs. Simulations based on real-world traffic traces show that the proposed solution can perform all three tasks given a 10 Gbps line rate using only the resources required to perform just the CF task given a 10 Gbps line rate.

In wireless sensor networks, a critical system service is the localization service that determines the locations of geographically distributed sensor nodes. The raw data used by this service are the distance measurements between neighboring nodes and the position knowledge of anchor nodes. However, these raw data may contain outliers that strongly deviate from their true values, which include both the outlier distances and the outlier anchors. These outliers can severely degrade the accuracy of the localization service. Therefore, we need a robust localization algorithm that can reject these outliers. Previous studies in this field mainly focus on enhancing multilateration with outlier rejection ability, since multilateration is a primitive operation used by localization service. But patch merging, a powerful operation for increasing the percentage of localizable nodes in sparse networks, is almost neglected. We thus propose a robust patch merging operation that can reject outliers for both multilateration and patch merging. Based on this operation, we further propose a robust network localization algorithm called RobustLoc . This algorithm makes two major contributions. (1) RobustLoc can achieve a high percentage of localizable nodes in both dense and sparse networks. In contrast, previous methods based on robust multilateration almost always fail in sparse networks with average degrees between 5 and 7. Our experiments show that RobustLoc can localize about 90% of nodes in a sparse network with 5.5 degrees. (2) As far as we know, RobustLoc is the first to uncover the differences between outlier distances and outlier anchors. Our simulations show that RobustLoc can reject colluding outlier anchors reliably in both convex and concave networks.

This paper puts forward an end-to-end traffic control solution, which we refer to as TCP-Elastic Real-time SErvice (TERSE). TERSE provides a unified end-to-end traffic control protocol that enables Non-Real-time Elastic (NRE) service (i.e., the same as the one under the TCP control), Real-time Delay Adaptive (RDA) service, and Real-time Rate Adaptive (RRA) service. A specific service is enabled by properly setting a single parameter in the protocol. TERSE is underpinned by a sound design methodology. While having its roots in a well-known utility-based optimization approach, this methodology successfully addresses its limitations. It leads to a unified traffic control protocol, which has several provable properties, including fairness, convergence, and stability. The protocol is implemented in LINUX-based systems. The cross-Pacific testing of this protocol shows that it can achieve more than 1.2Mbps throughput performance, 150% higher than TCP-reno and 50% higher than TCP cubic. Both analytical and simulation studies also show that it can provide soft minimum-rate guarantees for both RRA and RDA traffic flows. Moreover, simulation also demonstrates that it is resilient to network resource shortage. As part of the protocol design, an effective utility function of TCP and the corresponding control law are derived, which captures TCP behavior not only in a qualitative but also in a quantitative manner.

Policy Filtering (PF) and Content Filtering (CF) are two important tasks in packet forwarding of today's Internet. It is both technologically and economically important to develop integrated solutions for executing both tasks to reduce cost. In this paper, we propose a distributed Ternary Content Addressable Memory (TCAM) coprocessor architecture to allow fast and integrated PF and CF. Due to significant requirement diversities in both lookup load and storage load between PF and CF, the integrated solution exploits the complementary characteristics of the two tasks and well balances both the lookup load and storage load among TCAMs. A prefix filtering based CF algorithm is designed to reduce the lookup load and a novel cache mechanism is developed to dynamically handle the lookups from overloaded TCAMs. Simulations based on real-world traffic traces show that the proposed solution can match 10Gbps line rate for executing both PF and CF with the similar costs as CF task only.

In this paper, we identify the unique challenges in deploying parallelism on TCAM-based pattern matching for Network Intrusion Detection Systems (NIDSes). We resolve two critical issues when designing scalable parallelism specifically for pattern matching modules: 1) how to enable fine-grained parallelism in pursuit of effective load balancing and desirable speedup simultaneously; and 2) how to reconcile the tension between parallel processing speedup and prohibitive TCAM power consumption. To this end, we first propose the novel concept of Negative Pattern Matching to partition flows, by which the number of TCAM lookups can be significantly reduced, and the resulting (fine-grained) flow segments can be inspected in parallel without incurring false negatives. Then we propose the notion of Exclusive Pattern Matching to divide the entire pattern set into multiple subsets which can later be matched against selectively and independently without affecting the correctness. We show that Exclusive Pattern Matching enables the adoption of smaller and faster TCAM blocks and improves both the pattern matching speed and scalability. Finally, our theoretical and experimental results validate that the above two concepts are inherently complementary, enabling our integrated scheme to provide performance gain in any scenario (with either clean or dirty traffic).

The Datagram Congestion Control Protocol (DCCP) was designed to provide congestion control for unreliable applications, such as voice-over-IP and IPTV. But the current congestion control mechanisms of DCCP do not have the ability to support Quality of Service (QoS) features. This paper aims to design an end-to-end QoS-aware congestion control mechanism for DCCP based on theory. In particular, we design an end-to-end traffic control mechanism to support Real-time Delay Adaptive and Real-time Rate Adaptive applications. The mechanism possesses several provable properties, including friendliness to TCP, stability, and optimality. The experimental results show that the proposed mechanism can provide minimum rate guarantee for real-time applications and maintain a lower packet drop ratio.

Providing guaranteed end-to-end quality of service (QoS) is important for real-time applications such as Voice-over-IP. In this paper, a family of optimal, distributed, QoS- aware, end-to-end congestion control laws is derived. It enables a set of class of services (CoSs) including Assured Forwarding Service (AFS), Minimum Rate Guaranteed Service (MRGS), and Minimum Rate Guaranteed and Upper Bounded Rate Service (MRGUBS). These control laws maximize the same utility function as the TCP congestion control protocol does. As a result, they are by design TCP friendly. These control laws are implemented as window-based congestion control protocols, similar to the window-based TCP congestion control protocol. The performance of these protocols is tested based on ns-2 simulation. The results indicate that these protocols are indeed TCP friendly and can provide end-to-end service assurance as long as the percentage of network bandwidth consumed by the flows using these protocols is moderately small. Consequently, this family of QoS-aware control protocols has the potential to be used to provide end-to-end QoS guaranteed services for low- bandwidth applications, such as Voice-over-IP.

Easy management and maintenance and highly cost effective equipment make Ethernet an attractive technology for deploying metropolitan area networks (MANs). However, Ethernet has poor scalability due to use flat addressing scheme. To make metro-Ethernet more scalable, the provider edge (PE) nodes can use MAC-in-MAC (MiM) encapsulation scheme for frame forwarding. The MiM encapsulation scheme reduces the forwarding table size in the core nodes (CNs), but not in the PE nodes which need to maintain the entries of mapping end userpsilas MAC address to PEpsilas MAC address. In this paper, we propose an End user enabled MAC-in-MAC (EMiM) encapsulation scheme for Metro-Ethernet. In the proposed scheme, a userpsilas MAC address as well as its PE nodepsilas MAC address are associated with its address resolution protocol (ARP) entry. The modified ARP entry allows the end user to do MiM encapsulation. Hence a PE node does not need to maintain the entries of mapping end userpsilas MAC address to PE nodepsilas MAC address, thus significantly reducing the forwarding table size. The proposed scheme sustains Ethernetpsilas plug-and-play feature and provides high scalability. The simulation results show that the proposed scheme can reduce up to 65% maximum forwarding table size in PE nodes.

One of the most critical resource management issues in the use of ternary content addressable memory (TCAM) for packet classification/filtering is how to effectively support filtering rules with ranges, known as range matching. In this paper, a Dynamic Range Encoding Scheme (DRES) is proposed to significantly improve TCAM storage efficiency for range matching. Unlike the existing range encoding schemes requiring additional hardware support, DRES uses the TCAM coprocessor itself to assist range encoding. Hence, DRES can be readily programmed in a network processor using a TCAM coprocessor for packet classification. A salient feature of DRES is its ability to allow a subset of ranges to be encoded and hence to have full control over the range code size. This feature allows DRES to exploit the TCAM structure to maximize TCAM storage efficiency. DRES is a comprehensive solution, including a dynamic range selection algorithm, a search key encoding scheme, a range encoding scheme, and a dynamic encoded range update algorithm. While the dynamic range selection algorithm running in software allows optimal selection of ranges to be encoded to maximize the TCAM storage efficiency, the dynamic encoded range update algorithm allows the TCAM database to be updated lock-free without interrupting the TCAM database lookup process. DRES is evaluated based on real-world databases and the results show that DRES can reduce the TCAM storage expansion ratio from 6.20 to 1.23. The performance analysis of DRES based on a probabilistic model demonstrates that DRES significantly improves TCAM storage efficiency for a wide spectrum of range distributions.

Caching is an important technique to support pervasive Internet access. Cache consistency measures the deviation between the cached data and the source data. In mobile computing environments, especially with ad hoc networks, users are in great need of the flexibility in tuning their consistency requirements, in order to make tradeoffs between the specified cache consistency and the cost incurred. Existing works have used delta consistency (DC) and probabilistic consistency (PC) which, to some extent, provide the users with such flexibility. In this paper, we propose a general consistency model called probabilistic delta consistency (PDC). PDC covers all existing consistency models including DC and PC, and integrates the flexibility granted by both DC and PC. Thus, PDC enables the users to flexibly specify their consistency requirements in two orthogonal dimensions, namely the deviation in time/value and the ratio of queries gaining the specified consistency. We also propose a consistency maintenance algorithm, called flexible combination of push and pull (FCPP), which can meet users' consistency requirements specified under the PDC model. An analytical model is derived to achieve the optimized combination of push and pull, so as to ensure the user-specified consistency requirements, while minimizing the consistency maintenance overhead. Extensive simulations are conducted to evaluate the performance of the FCPP algorithm. Evaluation results show that, compared with the widely used dynamic TTR algorithm, FCPP can save up to 68% of the traffic overhead and reduce the query delay by up to 84%

As the tremendous growth in peer-to-peer (P2P) applications, the issues related to file consistency become critical. In this paper, an algorithm for file Consistency Maintenance through Virtual servers (CMV) is proposed for unstructured and decentralized P2P systems. In CMV, consistency of each dynamic file is maintained by a virtual server (VS). A file update can only be accepted through the VS to ensure the one-copy serializability. The VS of a file is a logical network composed of multiple replica peers (RPs) that have replicas of the file. Mathematical analysis is performed to determine the optimal parameter selections that achieve minimum overhead messages for maintaining file consistency. The numerical results indicate that CMV is well suited for efficient file consistency maintenance in P2P systems.

Packet classification has been a critical data path function for many emerging networking applications. An interesting approach is the use of ternary content addressable memory (TCAM) to achieve deterministic, high-speed packet classification performance. However, apart from high cost and power consumption, due to slow growing clock rate for memory technology, in general, the traditional single TCAM-based solution has difficulty to keep up with fast growing line rates. Moreover, the TCAM storage efficiency is largely affected by the need to support rules with ranges or range matching. In this paper, a distributed TCAM scheme that exploits chip-level-parallelism is proposed to greatly improve the throughput performance. This scheme seamlessly integrates with a range encoding scheme which not only solves the range matching problem, but also ensures a balanced high throughput performance. A thorough theoretical worst-case analysis of throughput, processing delay, and power consumption, as well as the experimental results show that the proposed solution can achieve scalable throughput performance matching up to OC768 line rate or higher. The added TCAM storage overhead is found to be reasonably small for the five real-world classifiers studied.

Caching frequently accessed data objects at the local buffer of a mobile user (MU) has been found to be very effective in improving information availability in mobile wireless environments. Several mechanisms have been proposed in the literature to address the challenging problem of cache consistency in cellular wireless networks. However, these mechanisms are limited to single cell systems. In this paper, we develop a novel Dynamic Scalable Asynchronous Cache Consistency Scheme (DSACCS) that can adaptively maintain mobile data objects globally or locally depending on the minimum consistency maintenance cost in multi-cell systems. The cost function is derived by taking into account each data object's update frequency, MUs' access pattern and roaming frequency, number of cells and number of MUs in the system. Extensive simulation studies demonstrate that DSACCS outperforms three existing cache strategies extended to multi-cell environments. The three cache consistency strategies are homogeneous invalidation reports (IRs), inhomogeneous IR without roaming check, and inhomogeneous IR with roaming check. Finally, an improvisation of DSACCS, called DSACCS-G, is proposed for grouping cells in order to facilitate effective cache consistency maintenance in multi-cell systems.

Packet classification (PC) has been a critical data path function for many emerging networking applications. An interesting approach is the use of TCAM to achieve deterministic, high speed PC However, apart from high cost and power consumption, due to slow growing clock rate for memory technology in general, PC based on the traditional single TCAM solution has difficulty to keep up with fast growing line rates. Moreover, the TCAM storage efficiency is largely affected by the need to support rules with ranges, or range matching. In this paper, a distributed TCAM scheme that exploits chip-level-parallelism is proposed to greatly improve the PC throughput. This scheme seamlessly integrates with a range encoding scheme, which not only solves the range matching problem but also ensures a balanced high throughput performance. Using commercially available TCAM chips, the proposed scheme achieves PC performance of more than 100 million packets per second (Mpps), matching OC768 (40 Gbps) line rate.

Summary form only given. In mobile distributed systems, vital resources like battery power and wireless channel bandwidth impose significant challenges in ubiquitous information access. We propose a novel energy and bandwidth efficient data caching mechanism, called greedydual least utility (GD-LU), that enhances dynamic data availability while maintaining consistency. The proposed utility-based caching mechanism considers several characteristics of mobile distributed systems, such as connection-disconnection, mobility handoff, data update and user request patterns to achieve significant energy savings in mobile devices. Based on the utility function derived from an analytical model, we propose a cache replacement algorithm and a passive prefetching algorithm to cache and prefetch data objects. Our comprehensive simulation experiments demonstrate that the proposed mechanism achieves more than 10% energy saving and near-optimal performance tradeoff between access latency and energy consumption.

We propose a novel algorithm, called update propagation through replica chain (UPTReC), to maintain file consistency in decentralized and unstructured peer-to-peer (P2P) systems. In UPTReC, each file has a logical replica chain composed of all replica peers (RPs) which are defined as peers that have replicas of the file. Each RP acquires partial knowledge of the bi-directional chain by keeping a list of information about k nearest RPs, called probe peers, in each direction. When an RP initiates an update, it pushes the update to all possible online (active) RPs through the replica chain. A reconnected RP pulls an online RP to synchronize the replica status and the information of the probe peers. An analytical model is derived to evaluate the performance of the UPTReC algorithm. The analytical results provide a better understanding of the system in choosing the system parameters for probabilistically guaranteed file consistency with minimum overheads. Simulation experiments are conducted to compare the performance with an existing update propagation algorithm based on the rumor spreading scheme. The experimental results show that the UPTReC can significantly reduce (up to 70%) overhead messages and also achieve smaller stale query ratio for files prone to frequent updates.

Due to deterministic and fast lookup performance, ternary content addressable memory (TCAM) has recently been gaining popularity in general policy filtering (PF) for packet classification in high-speed networks. However, the PF table update poses significant challenges for efficient use of TCAM. To avoid erroneous and inconsistent rule matching, the traditional approach is to lock the PF table during the rule update period, but table locking has a negative impact on data path processing. In this paper, we propose a novel scheme, called Consistent Policy Table Update Algorithm (CoPTUA), for TCAM. Instead of minimizing the number of rule moves to reduce the locking time, CoPTUA maintains a consistent PF table throughout the update process, thus eliminating the need for locking the PF table while-ensuring correctness of rule matching. Our analysis and simulation show that, even for a PF table with 100,000 rules, an arbitrary number of rules can be updated simultaneously within 1 second in the worst case, provided that 2 percent of the PF table entries are empty. Thus, CoPTUA enforces any new rule in less than 1 second for practical PF table size with high memory utilization and without impacting data path processing.

In the literature, there exit two types of cache consistency maintenance algorithms for mobile computing environments: stateless and stateful. In a stateless approach, the server is unaware of the cache contents at a mobile user (MU). Even though stateless approaches employ simple database management schemes, they lack scalability and ability to support user disconnectedness and mobility. On the other hand, a stateful approach is scalable for large database systems at the cost of nontrivial overhead due to server database management. We propose a novel algorithm, called Scalable Asynchronous Cache Consistency Scheme (SACCS), which inherits the positive features of both stateless and stateful approaches. SACCS provides a weak cache consistency for unreliable communication (e.g., wireless mobile) environments with small stale cache hit probability. It is also a highly scalable algorithm with minimum database management overhead. The properties are accomplished through the use of flag bits at the server cache (SC) and MU cache (MUC), an identifier (ID) in MUC for each entry after its invalidation, and estimated time-to-live (TTL) for each cached entry, as well as rendering of all valid entries of MUC to uncertain state when an MU wakes up. The stale cache hit probability is analyzed and also simulated under the Rayleigh fading model of error-prone wireless channels. Comprehensive simulation results show that the performance of SACCS is superior to those of other existing stateful and stateless algorithms in both single and multicell mobile environments.

This paper aims at finding fundamental design principles for hierarchical Web caching. An analytical modeling technique is developed to characterize an uncooperative two-level hierarchical caching system where the least recently used (LRU) algorithm is locally run at each cache. With this modeling technique, we are able to identify a characteristic time for each cache, which plays a fundamental role in understanding the caching processes. In particular, a cache can be viewed roughly as a low-pass filter with its cutoff frequency equal to the inverse of the characteristic time. Documents with access frequencies lower than this cutoff frequency have good chances to pass through the cache without cache hits. This viewpoint enables us to take any branch of the cache tree as a tandem of low-pass filters at different cutoff frequencies, which further results in the finding of two fundamental design principles. Finally, to demonstrate how to use the principles to guide the caching algorithm design, we propose a cooperative hierarchical Web caching architecture based on these principles. Both model-based and real trace simulation studies show that the proposed cooperative architecture results in more than 50% memory saving and substantial central processing unit (CPU) power saving for the management and update of cache entries compared with the traditional uncooperative hierarchical caching architecture.

This paper aims at finding fundamental design principles for hierarchical Web caching. An analytical modeling technique is developed to characterize an uncooperative two-level hierarchical caching system where the least recently used (LRU) algorithm is locally run at each cache. With this modeling technique, we are able to identify a characteristic time for each cache, which plays a fundamental role in understanding the caching processes. In particular, a cache can be viewed roughly as a lowpass filter with its cutoff frequency equal to the inverse of the characteristic time. Documents with access frequencies lower than this cutoff frequency will have good chances to pass through the cache without cache hits. This viewpoint enables us to take any branch of the cache tree as a tandem of lowpass filters at different cutoff frequencies, which further results in the finding of two fundamental design principles. Finally, to demonstrate how to use the principles to guide the caching algorithm design, we propose a cooperative hierarchical Web caching architecture based on these principles. The simulation study shows that the proposed cooperative architecture results in 50% saving of the cache resource compared with the traditional uncooperative hierarchical caching architecture.