Ternary Content Addressable Memory (TCAM) is a specialized high-speed memory that enables fast parallel lookups for both exact-match rules and wildcard-match rules. TCAM has become a standard hardware component in Software-Defined Networking (SDN) switches to implement flow tables for packet classification. However, limited TCAM storage capacity poses a significant scalability challenge for SDN to enforce fine-grained policy-based forwarding. To this end, TCAM-based rule-caching systems are proposed by combining TCAM with Random Access Memory (RAM). Specifically, TCAM caches heavy-hitting rules to capture packets from hot flows, while RAM accommodates the complete ruleset for other cache-miss packets. However, previous rule-caching systems either failed to eliminate cross-rule dependencies or restricted their applications to prefix rules only. In this work, we propose AWEsome-Cache, a unifying framework to fundamentally eliminate cross-rule dependencies for wildcard rules with arbitrary matching patterns. The rationale behind AWEsome-Cache is to concretize a minimum number of wildcard bits in the best-match rule, thereby pruning its overlapping match fields with all direct dependent rules. AWEsome-Cache also develops replacement algorithms during TCAM updates to adapt to dynamic traffic locality. Experiments with prefix and non-prefix rules show that AWEsome-Cache outperforms baselines in achieving a comparable cache-hit rate but requiring 75.9% less TCAM occupancy.

Nowadays, the surge of Internet contents and the need for high Quality of Experience (QoE) put the backbone network under unprecedented pressure. The emerging edge caching solutions help ease the pressure by caching contents closer to users. However, these solutions suffer from two challenges: 1) a low hit ratio due to edges’ high density and small coverages. 2) unbalanced edges’ workloads caused by dynamic requests and heterogeneous edge capacities. In this paper, we formulate a typical cooperative edge caching problem and propose the MagNet, a decentralized and cooperative edge caching system to address these two challenges. The proposed MagNet system consists of two innovative mechanisms: 1) the Automatic Content Congregating (ACC), which utilizes a neural embedding algorithm to capture underlying patterns of historical traces to cluster contents into some types. The ACC then can guide requests to their optimal edges according to their types so that contents congregate automatically in different edges by type. This process forms a virtuous cycle between edges and requests, driving a high hit ratio. 2) the Mutual Assistance Group (MAG), which lets idle edges share overloaded edges’ workloads by forming temporary groups promptly. To evaluate the performance of MagNet, we conduct experiments to compare it with classical, Machine Learning (ML)-based and cooperative caching solutions using the real-world trace. The results show that the MagNet can improve the hit ratio from 40% and 60% to 75% for non-cooperative and cooperative solutions, respectively, and significantly improve the balance of edges’ workloads.

The previous surveys show that more than 90% of the flows in typical data center networks are smaller than 100KB in size, while most bytes transmitted are from a few large flows. The small flows are usually sensitive to their completion times while the large flows require a high throughput. The previous works usually either achieve low completion times for small flows or high throughput for large flows, but not both. In this paper, we propose PTT (Priority-based and Throughput-guaranteed Transport) to minimize the average completion time of small flows while guaranteeing the high throughput of large flows. We conduct comprehensive simulations to evaluate the performance of PTT. The simulation results show that PTT reduces the average completion time of small flows by up to 27.52% over DCTCP and 23.82% over L2DCT while the throughput of large flows is comparable to that in DCTCP, which is 170.46% better than that in L2DCT.

BGP measurement is important for monitoring and understanding the Internet anomalies. Most of the previous works on BGP measurement rely on aggregated statistics from BGP monitors, e.g., total updates. However, BGP events may have quite limited visibility. Therefore, merely investigating aggregated data may lead to misunderstanding Internet instability, e.g., overestimating the impact of monitor-local events. In this empirical study, we demonstrate how BGP data are distributed among a large number of monitors. We define eleven features as the analysis targets, and three metrics to quantify disparity. We apply the method to 1.14 TB data and find that the distribution of most of the features is quite uneven, and different types of feature illustrate different levels of disparity. We also observe long periods of persistent high disparity, and a small set of cross-feature highly active monitors. Our analysis highlights the necessity of per-monitor data analysis in future BGP measurement study.

Measuring the instability of IP prefixes in BGP is critical for network operation and management. In particular, identifying and investigating the most active prefixes assist in detecting, analyzing, and understanding network problems. The traditional metric to assess the activeness of a prefix is the quantity of BGP update. However, this metric may be strongly affected by monitor-local events: the large amount of updates for a highly active prefix may be caused by an event with rather limited impact area. To cope with the issue, we propose a two-dimensional method: in addition to the traditional metric, Update Quantity (UQ), we introduce Update Visibility (UV). The key idea is that we mark a prefix as a `Highly Active Prefix' only when the large number of updates for it are widely observable. We define five types of active prefixes and propose a measurement method. We apply the method to 947 GB updates; the measurement results show that the two-dimensional method provides a more comprehensive picture of the highly active prefixes in the Internet than traditional single-metric schemes, and provides insights into network operations.

Many attempts have been made to detect and analyze anomalous Internet events through dissecting BGP updates and tables, and substantial progress has been made in detecting and quantifying the impact of major Internet disruptions. However, we notice that most works in this realm either deploy/use a limited quantity of monitors or analyze aggregated statistics, and such practice may result in overestimating the impact of monitor-local events, which can be viewed only by a rather small portion of the Internet. To eliminate the impact of such local events on the detection of Internet-level anomalies, we raise the concept of Large-scale BGP Event (LBE), which affects a large amount of IP prefixes (high impact) and is widely observable (non-local). To detect LBE, we record update data in the Update Visibility Matrix (UVM) according to the prefix and monitor related to each update. At first, we formulate the problem of identifying LBE in UVM as a bi-clustering problem; after proving it is NP-hard, we describe our heuristic algorithm. Next, we apply our scheme to more than 2 TB of historical data. We find that LBE is highly correlated with many well-known disruptive incidents. Furthermore, we also identify some abnormal events that have never been investigated. We believe our work can assist in network operation tasks such as problem prevention, diagnosis, and recovery.

Anomalous BGP events can deteriorate Internet performance and connectivity thus have always been a research topic. However, most measurement works in this realm are prone to monitor-local events, namely, the events local to only few BGP monitors. Besides, events that are widely observed can also have negligible impact, e.g., prefix-local events. In contrast, a Large-scale BGP Event (LBE) makes a large quantity of prefixes be updated and can be observed by a large portion of monitors. Such events are anomalous even harmful. We formulate the problem of identifying LBEs from BGP updates, then propose the Iterative Cut-off Algorithm to solve it. We apply the method to some famous disruptive events and some `innocent' data, which are collected from more than 400 monitors. The measurement results validate the effectiveness of our method. Moreover, we detect a severe and persistent misconfiguration event that has remained unreported before.

In the current IP networks, content replication and inter-domain Traffic Engineering (TE) are manipulated by different entities with respective objectives, and work at different layers as well. In Information-Centric Networking (ICN), however, they can both be administered by Internet Service Providers (ISPs) and work at the same network layer. In this paper, we present our study of jointly optimizing content replication and inter-domain TE in ICN, which aims at maximizing the profit of inter-domain traffic for an ISP while constrained by the limits of link bandwidth and the availability of contents. Results show that our algorithms can increase the ISP's profit by 66% and reduce the link utilization by 23% on average, which are near-optimal and with much less running time.

The Internet global routing tables have been expanding at a dramatic and increasing rate. In this paper, we propose the next hop of strict partial order to construct and aggregate the Nexthop-Selectable FIB (NSFIB). We control the path stretch caused by NSFIB aggregation by setting an upper limit number of next hops. According to our simulation, our aggregation algorithms shrink the FIB to 5-15%, compared with 20-60% of single-nexthop FIB aggregation algorithms; our method works very well in controlling the path stretch.

The Internet is facing severe routing scalability problem. The Internet Service Providers cannot afford to upgrade their routers at the pace of routing table growth. Therefore, FIB aggregation has been proposed. However, current single-nexthop FIB aggregation solutions cannot provide a satisfactory performance. In this paper, we first propose the next hop of strict partial order (SPO next hop) to construct the Nexthop-Selectable FIB (NSFIB). The approach guarantees that NSFIB-based aggregation performs better than single-nexthop FIB aggregation, especially in larger and denser backbone networks. We then provide the NSFIB-based aggregation algorithms. According to our simulation, our algorithms can shrink the FIB to 5% and the aggregation performance does not degrade when the network density increases, both of which are a great improvement overhead single-nexthop FIB aggregation.