Powered by extensive curated training data, the Segment Anything Model (SAM) demonstrates impressive generalization capabilities in open-world scenarios, effectively guided by user-provided prompts. However, the classagnostic characteristic of SAM renders its segmentation accuracy highly dependent on prompt quality. In this paper, we propose a novel plug-and-play dual-space Point Prompt Optimizer (PPO) designed to enhance prompt distribution through deep reinforcement learning (DRL)-based heterogeneous graph optimization. PPO optimizes initial prompts for any task without requiring additional training, thereby improving SAM’s downstream segmentation performance. Specifically, PPO constructs a dual-space heterogeneous graph, leveraging the robust feature-matching capabilities of a foundational pre-trained model to create internal feature and physical distance matrices. A DRL policy network iteratively refines the distribution of prompt points, optimizing segmentation predictions. We conducted experiments on four public datasets. The ablation study explores the necessity and balance of optimizing prompts in both feature and physical spaces. The comparative study shows that PPO enables SAM to surpass recent one-shot methods. Additionally, experiments with different initial prompts demonstrate PPO’s generality across prompts generated by various methods. In conclusion, PPO redefines the prompt optimization problem as a heterogeneous graph optimization task, using DRL to construct an effective, plugand-play prompt optimizer. This approach holds potential for broader applications across diverse segmentation tasks and provides a promising solution for point prompt optimization. The source code and demo are available at https://github.com/XueyuLiu/PPO.

The stage prediction of kidney renal clear cell carcinoma (KIRC) is important for the diagnosis, personalized treatment, and prognosis of patients. Many prediction methods have been proposed, but most of them are based on unimodal gene data, and their accuracy is difficult to further improve. Therefore, we propose a novel multi-weighted dynamic cascade forest based on the bilinear feature extraction (MLW-BFECF) model for stage prediction of KIRC using multimodal gene data (RNA-seq, CNA, and methylation). The proposed model utilizes a dynamic cascade framework with shuffle layers to prevent early degradation of the model. In each cascade layer, a voting technique based on three gene selection algorithms is first employed to effectively retain gene features more relevant to KIRC and eliminate redundant information in gene features. Then, two new bilinear models based on the gated attention mechanism are proposed to better extract new intra-modal and inter-modal gene features; Finally, based on the idea of the bagging, a multi-weighted ensemble forest classifiers module is proposed to extract and fuse probabilistic features of the three-modal gene data. A series of experiments demonstrate that the MLW-BFECF model based on the three-modal KIRC dataset achieves the highest prediction performance with an accuracy of 88.9 %.

In the new industrial Internet, a wide variety of industrial applications are expected to rely on high-performance data communication between a multitude of sensors and actuators that are deployed on a large scale. Publish-subscribe-based communication model is well-suited to handle such large-scale data gathering and dissemination among data sources and sinks. To support publish-subscribe-based data delivery, the newly standardized Segmented Routing over IPv6 (SRv6) can provide non-disruptive network programming primitives for building and maintaining network-efficient, shareable data distribution trees within the network. We study optimal algorithms for setting up different types of multicasting in the SRv6-capable network. In particular, we show, both theoretically and experimentally, that splitting multicast streams into multiple sub-streams, as well as using end-to-end application-layer coding without any network participation can provide significant benefits in terms of multicast throughput compared to traditional single stream multicasting.

Multiplexing resources is the core savings principle upon which the economic model of the Cloud is built. Cloud customers can flexibly purchase additional resources when needed, and trim these down when the need has past, while Cloud providers can direct resources when and where customers might require. One aspect which poses a challenge to this capability is the allocation process itself, which can be costly in terms of time and energy. Indeed, both provider and customer would prefer if resource allocation would be continuous, fast and with low energy overhead. Since this is not the case, there is an inherent tension between limiting the number of allocation events and efficient resource utilization.This paper considers this tension using several different models, and proposes a history-based dynamic allocation scheme that minimizes the number of resource allocation transition points for both average and adversarial use cases. We prove performance bounds and use extensive simulation to study the performance of our scheme.

Having an efficient onboarding process is a pivotal step to utilize and provision the IoT devices for accessing the network infrastructure. However, the current process to onboard IoT devices is time-consuming and labor-intensive, which makes the process vulnerable to human errors and security risks. In order to have a streamlined onboarding process, we need a mechanism to reliably associate each digital identity with each physical device. We design an onboarding mechanism called MAIDE to fill this technical gap. MAIDE is an Augmented Reality (AR)-facilitated app that systematically selects multiple measurement locations, calculates measurement time for each location and guides the user through the measurement process. The app also uses an optimized voting-based algorithm to derive the device-to-ID mapping based on measurement data. This method does not require any modification to existing IoT devices or the infrastructure and can be applied to all major wireless protocols such as BLE, and WiFi. Our extensive experiments show that MAIDE achieves high device-to-ID mapping accuracy. For example, to distinguish two devices on a ceiling in a typical enterprise environment, MAIDE achieves ~95% accuracy by measuring 5 seconds of Received Signal Strength (RSS) data for each measurement location when the devices are 4 feet apart.

Since the outbreak of the COVID-19 pandemic, videoconferencing has become the default mode of communication in our daily lives at homes, workplaces and schools, and it is likely to remain an important part of our lives in the post-pandemic world. Despite its significance, there has not been any systematic study characterizing the user-perceived performance of existing videoconferencing systems other than anecdotal reports. In this paper, we present a detailed measurement study that compares three major videoconferencing systems: Zoom, Webex and Google Meet. Our study is based on 62 hours’ worth of more than 1.1K videoconferencing sessions, which were created with a mix of emulated videoconferencing clients deployed in the cloud, as well as real mobile devices running from a residential network over two separate periods with nine months apart. We find that the existing videoconferencing systems vary in terms of geographic scope and resource provisioning strategies, which in turns determine streaming lag experienced by users. We also observe that streaming rate can change under different conditions (e.g., available bandwidth, number of users in a session, mobile device status), which affects user-perceived streaming quality. Beyond these findings, our measurement methodology enables reproducible benchmark analysis for any types of comparative or longitudinal study on available videoconferencing systems.

Since the outbreak of the COVID-19 pandemic, videoconferencing has become the default mode of communication in our daily lives at homes, workplaces and schools, and it is likely to remain an important part of our lives in the post-pandemic world. Despite its significance, there has not been any systematic study characterizing the user-perceived performance of existing videoconferencing systems other than anecdotal reports. In this paper, we present a detailed measurement study that compares three major videoconferencing systems: Zoom, Webex and Google Meet. Our study is based on 48 hours' worth of more than 700 videoconferencing sessions, which were created with a mix of emulated videoconferencing clients deployed in the cloud, as well as real mobile devices running from a residential network. We find that the existing videoconferencing systems vary in terms of geographic scope, which in turns determines streaming lag experienced by users. We also observe that streaming rate can change under different conditions (e.g., number of users in a session, mobile device status, etc), which affects user-perceived streaming quality. Beyond these findings, our measurement methodology can enable reproducible benchmark analysis for any types of comparative or longitudinal study on available videoconferencing systems.

In order to create services using IoT devices, the underlying network infrastructure must support large number of such devices with different underlying protocols, and diverse requirements from the service applications (privacy, reliability and QoS guarantee, etc.). Many of these requirements can be realized by implementing an in-network packet forwarding policy in the infrastructure supporting direct device-to-device communications. However, with large number of devices deployed in the IoT network, the number of rules required for policy enforcement grows very rapidly, and it becomes an infrastructural challenge to installing and managing the rules in switches/routers. We argue that attaching service and role-based labels to address IoT devices can significantly reduce the number of rules by using wild-cards. We formulate a scheme that can produce the optimum length labels for representing the service attributes of the communicating IoT devices. Due to non-convex nature of the optimization, we develop two heuristic solutions for the label generating scheme. Through evaluation using a simulated but practical IoT network environment with large number of devices, we demonstrate the benefits of the scheme that can reduce the number of rules by several orders of multitude.

While being critical to the network management, the current state of the art in network measurement is inadequate, providing surprisingly little visibility into detailed network behaviors and often requiring high level of manual intervention to operate. Such a practice becomes increasingly ineffective as the networks grow both in size and complexity. In this paper, we propose vPROM, a vSwitch enhanced SDN programmable measurement framework that automates the measurement process, minimizes the measurement resource usage, and addresses several significant technical challenges faced by early works. vPROM leverages the SDN programmability and extends the Pyretic runtime system and OpenFlow network interface to achieve the measurement automation. The required measurement resources are minimized by only acquiring the necessary statistics, made possible with instrumented Open vSwitches1with user defined monitoring capability. By decoupling monitoring from routing, vPROM reduces the interference between the measurement applications and other applications, and eliminates the frequent involvement of the controller. A vPROM prototype is implemented with DDoS and port-scan detection applications. The performance of vPROM is evaluated and the comparison results with other existing programmable measurement approaches are also presented.

Software Defined Networking (SDN) can benefit a Network Function Virtualization solution by chaining a set of network functions (NF) to create a network service. Currently, control on NFs is isolated from the SDN, which creates routing inflexibility, flow imbalance and choke points in the network as the controller remains oblivious to the number, capacity and placement of NFs. Moreover, a NF may modify packets in the middle, which makes flow identification at a SDN switch challenging. In this paper, we postulate native NFs within the SDN data plane, where the same logical controller controls both network services and routing. This is enabled by extending SDN to support stateful flow handling based on higher layers in the packet beyond layers 2-4. As a result, NF instances can be chained on demand, directly on the data plane. We present an implementation of this architecture based on Open vSwitch, and show that it enables popular NFs effectively using detailed evaluation and comparison with other alternative solutions.

One of the primary functions of a cloud service provider is to allocate cloud resources to users upon request. Requests arrive in real-time and resource placement decisions must be made as and when a request arrives, without any prior knowledge of future arrivals. In addition, when a cloud service provider operates a geographically diversified cloud that consists of a large number of small data centers, the resource allocation problem becomes even more complex. This is due to the fact that resource request can have additional constraints on data center location, service delay guarantee, and so on, which is especially true for the emerging network function virtualization application. In this paper, we propose a generalized resource placement methodology that can work across different cloud architectures, resource request constraints, with real-time request arrivals and departures. The proposed algorithms are online in the sense that allocations are made without any knowledge of resource requests that arrive in the future, and the current resource allocations are made in such a manner as to permit the acceptance of as many future arrivals as possible. We derive worst case competitive ratio for the algorithms. We show through experiments and case studies the superior performance of the algorithms in practice.

Segment routing is a new proposed routing mechanism for simplified and flexible path control in IP/MPLS networks. It builds on existing network routing and connection management protocols and one of its important features is the automatic rerouting of connections upon failure. Re-routing can be done with available restoration mechanisms including IGP-based rerouting and fast reroute with loop-free alternates. This is particularly attractive for use in Software Defined Networks (SDN) because the central controller need only be involved at connection set-up time and failures are handled automatically in a distributed manner. A significant challenge in restoration optimization in segment routed networks is the centralized determination of connections primary paths so as to enable the best sharing of restoration bandwidth over non-simultaneous network failures. We formulate this problem as a linear programming problem and develop an efficient primal-dual algorithm for the solution. We also develop a simple randomized rounding scheme for cases when there are additional constraints on segment routing. We demonstrate the significant capacity benefits achievable from this optimized restoration with segment routing.

Multipath TCP (MPTCP) is a promising technique for boosting application throughput while using well-known and versatile network socket interfaces. Recently, many interesting applications of MPTCP in various environments such as wireless networks and data centers have been proposed, but little work has been done to investigate the impact of this protocol on conventional network devices. For example, MPTCP throughput advantage can be better achieved if all MPTCP subflows are routed on disjoint paths, but this is currently not feasible since routers are not designed to recognize the membership of MPTCP subflows. In this paper, we take a first step to address this issue by proposing SAMPO, an online algorithm to detect and associate MPTCP subflows in network. The main challenge is that sampling techniques and network dynamics may cause a network device to only obtain partial flow records. SAMPO takes advantage of both protocol information and statistical characteristics of MPTCP data sequence number to overcome the challenge in network. Through analysis and experimentation, we show that SAMPO is able to detect and associate MPTCP subflows with high accuracy even when a small portion of the entire flow records are available.

We study how to provide fine-grained, flexible traffic monitoring in the Open vSwitch (OVS). We argue that the existing OVS monitoring tools are neither flexible nor sufficient for supporting many monitoring applications. We propose UMON, a mechanism that decouples monitoring from forwarding, and offers flexible and fine-grained traffic stats. We describe a prototype implementation of UMON that integrates well with the OVS architecture. Finally, we evaluate the performance using the prototype, and illustrate UMON's efficiency with the example use cases such as detecting port scans.

Segment Routing is a proposed IETF protocol to improve traffic engineering and online route selection in IP networks. The key idea in segment routing is to break up the routing path into segments in order to enable better network utilization. Segment routing also enables finer control of the routing paths and can be used to route traffic through middle boxes. This paper considers the problem of determining the optimal parameters for segment routing in the offline and online cases. We develop a traffic matrix oblivious algorithm for robust segment routing in the offline case and a competitive algorithm for online segment routing. We also show that both these algorithms work well in practice.

Netflix and Hulu are leading Over-the-Top (OTT) content service providers in the US and Canada. Netflix alone accounts for 29.7% of the peak downstream traffic in the US in 2011. Understanding the system architectures and performance of Netflix and Hulu can shed light on the design of such large-scale video streaming platforms, and help improving the design of future systems. In this paper, we perform extensive measurement study to uncover their architectures and service strategies. Netflix and Hulu bear many similarities. Both Netflix and Hulu video streaming platforms rely heavily on the third-party infrastructures, with Netflix migrating that majority of its functions to the Amazon cloud, while Hulu hosts its services out of Akamai. Both service providers employ the same set of three content distribution networks (CDNs) in delivering the video contents. Using active measurement study, we dissect several key aspects of OTT streaming platforms of Netflix and Hulu, e.g., employed streaming protocols, CDN selection strategy, user experience reporting, etc. We discover that both platforms assign the CDN to a video request without considering the network conditions and optimizing the user-perceived video quality. We further conduct the performance measurement studies of the three CDNs employed by Netflix and Hulu. We show that the available bandwidths on all three CDNs vary significantly over the time and over the geographic locations. We propose a measurement-based adaptive CDN selection strategy and a multiple-CDN-based video delivery strategy that can significantly increase users' average available bandwidth.

Software Defined Networking (SDN) has become a popular paradigm for centralized control in many modern networking scenarios such as data centers and cloud. For large data centers hosting many hundreds of thousands of servers, there are few thousands of switches that need to be managed in a centralized fashion, which cannot be done using a single controller node. Previous works have proposed distributed controller architectures to address scalability issues. A key limitation of these works, however, is that the mapping between a switch and a controller is statically configured, which may result in uneven load distribution among the controllers as traffic conditions change dynamically. To address this problem, we propose ElastiCon, an elastic distributed controller architecture in which the controller pool is dynamically grown or shrunk according to traffic conditions. To address the load imbalance caused due to spatial and temporal variations in the traffic conditions, ElastiCon automatically balances the load across controllers thus ensuring good performance at all times irrespective of the traffic dynamics. We propose a novel switch migration protocol for enabling such load shifting, which conforms with the Openflow standard. We further design the algorithms for controller load balancing and elasticity. We also build a prototype of ElastiCon and evaluate it extensively to demonstrate the efficacy of our design.

Software Defined Networks use logically centralized control due to its benefits in maintaining a global network view and in simplifying programmability. However, the use of centralized controllers can affect network performance if the control path between the switches and their associated controllers becomes a bottleneck. We find from measurements that the software control agents on some of the switches have very limited throughput. This can cause performance degradation if the switch has to handle a high traffic load, as for instance due to flash crowds or DDoS attacks. This degradation can occur even when the data plane capacity is under-utilized. The goal of our paper is to design new mechanisms to enable the network to scale up its ability to handle high control traffic loads. For this purpose, we design, implement, and experimentally evaluate Scotch, a solution that elastically scales up the control plane capacity by using a vSwitch based overlay. Scotch takes advantage of both the high control plane capacity of a large number of vSwitches and the high data plane capacity of commodity physical switches to increase the SDN network scalability and resiliency under normal (e.g., flash crowds) or abnormal (e.g., DDoS attacks) traffic surge.

One of the primary functions of a cloud service provider is to allocate cloud resources to users upon request. Requests arrive in real-time and resource placement decisions must be made as and when a request arrives, without any prior knowledge of future arrivals. In addition, when a cloud service provider operates a geographically diversified cloud that consists of large number of small data centers, the resource allocation problem becomes even more complex. This is due to the fact that resource request can have additional constraints on data center location, service delay guarantee, etc. In this paper, we propose a generalized resource placement methodology that can work across different cloud architectures, resource request constraints, with real-time request arrivals and departures. The proposed algorithms are online in the sense that allocations are made without any knowledge of resource requests that arrive in the future, and the current resource allocations are made in such a manner as to permit the acceptance of as many future arrivals as possible. We derive worst case competitive ratio for the algorithms. We show through experiments and case studies the superior performance of the algorithms in practice.

Preventing flow of confidential data out of a network is a fundamental problem faced by network operators. This problem gets even more complex in the context of Cloud Computing, where multiple distrusting customers share the same underlying infrastructure, and data is often replicated and moved across regions. Despite the significance of this problem, existing solutions are based on generic search for keywords in outgoing data, and hence severely lack the ability to control data flow at a fine granularity with low false positives. In this paper, we advocate a fine-grained approach to prevent confidential data from leaking out of the cloud. We propose a solution using document-level fingerprint checks. We show via analysis and experiments that our algorithm for checking the fingerprints on-the-fly scale to a large amount of documents at very low cost. For example, for one TB of documents, our solution only requires 340 MB memory to achieve worst case expected detection lag (i.e. leakage length) of 1000 bytes.

Netflix is the leading provider of on-demand Internet video streaming in the US and Canada, accounting for 29.7% of the peak downstream traffic in US. Understanding the Netflix architecture and its performance can shed light on how to best optimize its design as well as on the design of similar on-demand streaming services. In this paper, we perform a measurement study of Netflix to uncover its architecture and service strategy. We find that Netflix employs a blend of data centers and Content Delivery Networks (CDNs) for content distribution. We also perform active measurements of the three CDNs employed by Netflix to quantify the video delivery bandwidth available to users across the US. Finally, as improvements to Netflix's current CDN assignment strategy, we propose a measurement-based adaptive CDN selection strategy and a multiple-CDN-based video delivery strategy, and demonstrate their potentials in significantly increasing user's average bandwidth.

In this paper, we consider the problem of designing a data structure that can perform fast multiple-set membership testing in deterministic time. Our primary goal is to develop a hardware implementation of the data structure that uses only embedded memory blocks. Prior efforts to solve this problem involve hashing into multiple Bloom filters. Such approach needs a priori knowledge of the number of elements in each set in order to size the Bloom filter. We use a single-Bloom-filter-based approach and use multiple sets of hash functions to code for the set (group) id. Since a single Bloom filter is used, it does not need a priori knowledge of the distribution of the elements across the different sets. We show how to improve the performance of the data structure by using constant-weight error-correcting codes for coding the group id. Using error-correcting codes improves the performance of these data structures especially when there are a large number of sets. We also outline an efficient hardware-based approach to generate the large number of hash functions that we need for this data structure. The resulting data structure, COMB, is amenable to a variety of time-critical network applications.

Many popular algorithms for fast packet forwarding and filtering rely on the tree data structure. Examples are the trie-based IP lookup and packet classification algorithms. With the recent interest in network virtualization, the ability to run multiple virtual router instances on a common physical router platform is essential. An important scaling issue is the number of virtual router instances that can run on the platform. One limiting factor is the amount of high-speed memory and caches available for storing the packet forwarding and filtering data structures. An ideal goal is to achieve good scaling while maintaining total isolation among the virtual routers. However, total isolation requires maintaining separate data structures in high-speed memory for each virtual router. In this paper, we study the case where some sharing of the forwarding and filtering data structures is permissible and develop algorithms for combining tries used for IP lookup and packet classification. Specifically, we develop a mechanism called trie braiding that allows us to combine tries from the data structures of different virtual routers into just one compact trie. Two optimal braiding algorithms and a faster heuristic algorithm are presented, and the effectiveness is demonstrated using the real-world data sets.

Many popular algorithms for fast packet forwarding and filtering rely on the tree data structure. Examples are the trie-based IP lookup and packet classification algorithms. With the recent interest in network virtualization, the ability to run multiple virtual router instances on a common physical router platform is essential. An important scaling issue is the number of virtual router instances that can run on the platform. One limiting factor is the amount of high-speed memory and caches available for storing the packet forwarding and filtering data structures. An ideal goal is to achieve good scaling while maintaining total isolation amongst the virtual routers. However, total isolation requires maintaining separate data structures in high-speed memory for each virtual router. In this paper, we study the case where some sharing of the forwarding and filtering data structures is permissible and develop algorithms for combining tries used for IP lookup and packet classification. Specifically, we develop a mechanism called trie-braiding that allows us to combine tries from the data structures of different virtual routers into just one compact trie. Two optimal braiding algorithms are presented and the effectiveness is demonstrated using the real world data sets.

With the increasing volume of VoIP, IPTV, and other real-time traffic on the Internet in recent years, service providers and operators demand tools to effectively detect and manage such traffic in their networks. However, many such applications are not easy to detect by using conventional approaches based on packet header and payload inspections since they may use random ports and data encryption. In this paper, we propose a simple yet effective approach that can detect constant or near constant rate traffic based on statistical inference on packet timing behaviors. Through experiments with traffic collected from both lab controlled environment and actual field networks, we show that this approach is easier to implement and has much better performance compared to existing approaches.

Recently, there has been much renewed interest in developing compact data structures for packet processing functions such as longest prefix-match for IP lookups. This has been motivated by several factors: (1) The advent of 100 Gbps interfaces necessitating correspondingly fast packet processing algorithms with a compact memory footprint; (2) network virtualization leading to virtualization of physical router platforms making it critical to reduce high-speed memory needs per virtual router; (3) software routers built on multi-core processors requiring the use of compact data-structures that fit in on-chip caches for good performance. In this paper, we revisit this issue of developing compact data structures for key packet-processing functions. We develop a new data structure, called the shape graph, that significantly compacts the trie data-structure used for IP lookups. We accomplish this by identifying considerable structural similarities in IP lookup tries that have not previously been used in the literature for scalable IP lookups. We use these similarities to store lookup tries in a new graph data structure that has a significantly lower memory-footprint. Using real IP forwarding tables, we compare the memory usage of this new data structure to that of multi-bit tries and of Bloom filters used for IP lookups. The shape graph requires significantly less memory and allows the far more effective use of on-chip memory. This effective use of on-chip memory combined with multi-threading on a multi-core processor makes shape-graph-based IP lookups well suited for 100 Gbps lookups. The small footprint also makes it well suited for use in router platforms that host a large number of virtual routers.

In this paper we consider the problem of designing a data structure that can perform fast multiset membership testing in deterministic time. Our primary goal is to develop a hardware implementation of the data structure which uses only embedded memory blocks. Prior efforts to solve this problem involve hashing into multiple bloom filters. Such approach needs a priori knowledge of the number of elements in each set in order to size the bloom filter. We use a single bloom filter based approach and use multiple sets of hash functions to code for the set (group) id. Since a single bloom filter is used, it does not need a priori knowledge of the distribution of the elements across the different sets. We show how to improve the performance of the data structure by using constant weight error correcting codes for coding the group id. Using error correcting codes improves the performance of these data structures especially when there are large number of sets. We also outline an efficient hardware based approach to generate the the large number of hash functions that we need for this data structure. The resulting data structure, COMB, is amenable to a variety of time-critical network applications.

Internet line speeds are expected to reach 100 Gbps in a few years. To match these line rates, a single router line card needs to forward more than 150 million packets per second. This requires a corresponding amount of longest prefix match operations. Furthermore, the increased use of IPv6 requires core routers to perform the longest prefix match on several hundred thousand prefixes varying in length up to 64 bits. It is a challenge to scale existing algorithms simultaneously in the three dimensions of increased throughput, table size and prefix length. Recently, Bloom filter-based IP lookup algorithms have been proposed. While these algorithms can take advantage of hardware parallelism and fast on-chip memory to achieve high performance, they have significant drawbacks (discussed in the paper) that impede their use in practice. In this paper, we present the distributed and load balanced bloom filters to address these drawbacks. We develop the practical IP lookup algorithm for use in 100 Gbps line cards. The regular and modular hardware architecture of our scheme directly maps to the state-of-art ASICs and FPGAs with reasonable resource consumption. Also, our scheme outperforms TCAMs on most metrics including cost, power dissipation, and board footprint.

In this paper the problem of path following control of autonomous vehicles subject to sliding is addressed. First a kinematic model is built which takes sliding effects into account by introducing two additional tire sliding angles. Since the tire sliding angles cannot be directly measured by sensors, an adaptive robust Luenberger observer is designed. With this observer, the tire cornering stiffness instead of the sliding angles is identified in presence of time-varying lateral disturbance. The Lyapunov stability theory guarantees that the estimated cornering stiffness would converge to a neighborhood of the real value when control inputs excitated the system persistently. But due to the existence of the lateral disturbance which causes loss of accuracy of the sliding angle reconstruction, the previously designed anti-sliding controller whose effectiveness completely depends on the estimation of the sliding angles cannot yield satisfactory results. To overcome this problem a tire-oriented kinematic model is built in which the inaccuracy of the sliding angle reconstruction is modeled in form of additive disturbances to the kinematic model. By transforming the tire-oriented kinematic model into a perturbed chained system, a sliding mode controller, which is robust to both the sliding effects and the negative effects of the lateral disturbance is designed with the help of the natural algebraic structure of the chained systems. Simulation results show that the proposed methods can provide accurate estimation of the sliding angles and guarantee high anti-sliding control accuracy even in presence of time-varying lateral disturbance.

A bloom filter is a randomized data structure for performing approximate membership queries. It is being increasingly used in networking applications ranging from security to routing in peer to peer networks. In order to meet a given false positive rate, the amount of memory required by a bloom filter is a function of the number of elements in the set. We consider the problem of minimizing the memory requirements in cases where the number of elements in the set is not known in advance but the distribution or moment information of the number of elements is known. We show how to exploit such information to minimize the expected amount of memory required for the filter. We also show how this approach can significantly reduce memory requirement when bloom filters are constructed for multiple sets in parallel. We show analytically as well as experiments on synthetic and trace data that our approach leads to one to three orders of magnitude reduction in memory compared to a standard bloom filter.

The growing importance of operations such as packet-content inspection, packet classification based on non-IP headers, maintaining flow-state, etc. has led to increased interest in the networking applications of Bloom filters. This is because Bloom filters provide a relatively easy method for hardware implementation of set-membership queries. However, the tradeoff is that Bloom filters only provide a probabilistic test and membership queries can result in false positives. Ideally, we would like this false positive probability to be very low. The main contribution of this paper is a method for significantly reducing this false positive probability in comparison to existing schemes. This is done by developing a partitioned hashing method which results in a choice of hash functions that set far fewer bits in the Bloom filter bit vector than would be the case otherwise. This lower fill factor of the bit vector translates to a much lower false positive probability. We show experimentally that this improved choice can result in as much as a ten-fold increase in accuracy over standard Bloom filters. We also show that the scheme performs much better than other proposed schemes for improving Bloom filters.

Fast IP flow rate estimation has many potential applications in network management, monitoring, security, and traffic engineering. Recently, low cost and memory efficient techniques to accurately estimate flow-rates in real-time have been developed. These techniques rely on flow definitions being constrained to being subsets of the fields in the packet header making flow-membership tests relatively inexpensive. In this paper, we consider a more general flow-rate estimation problem where flow membership testing is non-trivial and may involve more complex processing such as packet-payload based tests. An example is to estimate the amount of traffic that contains a given set of patterns (e.g., virus or worm signatures). We design new flow estimation techniques to reduce the number of membership tests. These techniques track pairs of arrivals that have the given property of interest and use lazy membership testing to avoid complex property testing unless absolutely necessary. The efficiency of the new schemes is evaluated by both analysis and simulation. I.

Real-time IP flow estimation has many potential applications in network management, monitoring, security, and traffic engineering. Existing techniques typically rely on flow definitions being constrained as subsets of the fields in packet headers. This makes flow-membership tests relatively inexpensive. In this paper, we consider a more general flow estimation problem that needs complex packet-payload based tests for flow-membership. An example is to estimate traffic with common strings in the payload and detect potential virus signatures for early alarm generation. We develop a fast, memory efficient algorithm for solving this problem as a variant of the longest common subsequence problem. This is done via an application of Rabin fingerprinting in combination with bloom filters. Both analysis and simulation show the effectiveness of the developed method.

We consider the problem of fast, estimation of flow rates in backbone network links with possibly millions of flows. Accurate flow rate estimation is necessary for network traffic management, network planning, measuring compliance to service level agreements, and network security. Ideally, a rate estimation scheme should have short estimation times with provable bounds on estimation error, be low in memory usage, and be easily implementable in hardware for operation at high speeds. We develop such a scheme, and achieve up to two orders of magnitude speed-up in estimation time over the previously proposed two-runs-based RATE scheme [Kodialam, M et al., 2004]. The speedups are achieved without a significant increase in memory usage, by using coincidences instead of runs. Counting coincidences has a higher processing overhead than detecting two-runs, but this higher overhead is not significant for a hardware implementation. We show that the proposed scheme is faster and more accurate than other recently proposed schemes such as ACCEL-RATE [Hao, F et al., 2004] and smart sampling [Duffield, N et al., 2004]. The faster estimation time of the new scheme has many benefits including quicker detection of incipient denial of service attacks. We prove bounds on the scheme's accuracy, memory needs, and also show that it performs well by simulations that use both synthetic and real traffic traces.

We address the problem of fast automatic identification of traffic patterns in core networks with high speed links carrying large numbers of flows. This problem has applications in detecting DoS attacks, traffic management, and network security. The typical measurement and identification objective is to determine flows that use up a disproportionate fraction of network resources. Several schemes have been devised to measure large flows efficiently assuming that the notion of what constitutes a flow is well defined a priori. However, there are many scenarios where traffic patterns are hidden in the sense that there is no clear knowledge of what exactly to look for and there is no natural a priori definition of flow. In This work, we develop an effective scheme to identify and measure hidden traffic patterns. The approach is flexible enough to automatically identify interesting traffic patterns for further evaluation. The basic idea is to extend the runs based approach proposed in (Kodialam, M. et al., 2004) to the case where flow definitions are not known a priori. A straightforward extension is both memory and processing intensive. We develop an efficient scheme that has good theoretical properties and does extremely well in practice.

Per-flow network traffic measurement is an important component of network traffic management, network performance assessment, and detection of anomalous network events such as incipient DoS attacks. In [1], the authors developed a mechanism called RATE where the focus was on developing a memory efficient scheme for estimating per-flow traffic rates to a specified level of accuracy. The time taken by RATE to estimate the per-flow rates is a function of the specified estimation accuracy and this time is acceptable for several applications. However some applications, such as quickly detecting worm related activity or the tracking of transient traffic, demand faster estimation times. The main contribution of this paper is a new scheme called ACCEL-RATE that, for a specified level of accuracy, can achieve orders of magnitude decrease in per-flow rate estimation times. It achieves this by using a hashing scheme to split the incoming traffic into several sub-streams, estimating the per-flow traffic rates in each of the substreams and then relating it back to the original per-flow traffic rates. We show both theoretically and experimentally that the estimation time of ACCEL-RATE is at least one to two orders of magnitude lower than RATE without any significant increase in the memory size.

Quality-of-service (QoS) techniques and server replication are two complementary approaches that can improve the performance observed by users. QoS techniques provide differentiated service to meet the diverse needs of applications; server replication enables load balancing across a set of servers. To combine the two approaches, we need to address one important question: how to select a server among a replicated set that satisfies the user QoS requirement. We propose a probing-based protocol to discover network resources and make reservations for requests in differentiated service networks. This approach optimizes network resource utilization with reasonable signaling overhead. Furthermore, we compare five heuristics that can be used for server selection. We also investigate two methods that can reduce probing overhead, namely caching and the technique of probing from a subset of servers.

As the Internet has grown in size and diversity of applications, two trends have emerged to provide good end-user perceived performance. First, servers are often replicated for better scalability of the service. Second, QoS approaches, such as the differentiated services framework, have been proposed as enhancement to the best-effort IP service. We are interested in the combination of these two trends; that is, replicated servers in QoS-based networks. We focus on the problem of selecting amongst replicated servers in the context of differentiated service networks. Our contributions are twofold. First, we design a QoS-based server-selection architecture. The architecture is scalable in the sense that server selection and resource reservation are done in an aggregated fashion and operate in the background, rather than being driven by individual client demand. At the same time, the architecture offers a fast response time to client requests for server selection. Second, we explore the design space implied by the architecture and evaluate various design options including signalling protocols, server selection/sorting algorithms and resource reservation granularity.

A number of important questions remain concerning the scalability of networks with quality of service guarantees. We consider one of these questions: can QoS routing protocols scale to large networks? To address this question, we evaluate the performance of techniques that can reduce the QoS routing protocol overhead. We specifically focus on topology aggregation, which can reduce overhead by orders of magnitude. We also investigate the interaction of topology aggregation with other important factors that contribute to performance, such as routing update frequency, routing algorithms, and network configuration. Our experiments are based on simulations of relatively large, structured networks. Among our observations, we find-contrary to intuition-that topology aggregation does not always have a negative impact on routing performance. Aggregation can reduce the routing information fluctuation, increase stability, and thus benefit routing performance. We also propose two new methods of aggregating routing information. Our hybrid aggregation method performs much better than conventional star aggregation and approaches unaggregated performance. Our weighted aggregation method, while intuitively appealing, offers mixed performance across topologies.

We present a technique to enable the efficient simulation of large scale ATM networks, while preserving the accuracy of the end-to-end delay statistics. Our approach uses on-the-fly aggregation by observing traffic at monitoring points, then substituting an aggregate model, when appropriate. We focus in particular on the end-to-end delay distribution, given the importance of this distribution for continuous media. We find that our methods are able to achieve speedup of one order of magnitude, while maintaining accuracy within 5% of the unaggregated simulation. These results are observed in both a series of multiplexers and a 100-switch wide-area ATM topology.