Low-Earth-Orbit (LEO) satellite constellations provide Internet connectivity across the globe, but their network design poses significant challenges due to the large number of satellites and their fast movement. Named Data Networking (NDN) can bring many benefits to LEO satellite networks such as data-centric security, scalable content distribution, and intelligent data plane. A key enabler to these benefits is NDN's stateful forwarding, which unfortunately can be disrupted by the frequent handovers between the satellites and the ground terminals. In this paper, we investigate the impacts of these handovers on NDN's packet delivery and propose effective mitigation mechanisms. Using a newly developed packet-level simulator and in-depth analysis of packet forwarding behavior during handovers, we show that consumer handovers and producer handovers both lead to temporary packet losses but for different causes. To mitigate these problems, we design a new Interest retransmission strategy to handle consumer handovers, and a new forwarding strategy to handle producer handovers. Our evaluation shows that these solutions are effective in reducing packet losses and delivery time. This work sheds insights on how NDN can work in the presence of frequent satellite-ground handovers to enable data-centric communication in this new network environment.

Name lookup is a key technology for the forwarding plane of content router in Named Data Networking (NDN). To realize the efficient name lookup, what counts is deploying a high-performance index in content routers. So far, the proposed indexes have shown good performance, most of which are optimized for or evaluated with URLs collected from the current Internet, as the large-scale NDN names are not available yet. Unfortunately, the performance of these indexes is always impacted in terms of lookup speed, memory consumption and false positive probability, as the distributions of URLs retrieved in memory may differ from those of real NDN names independently generated by content-centric applications online. Focusing on this gap, a smart mapping model named Pyramid-NN via neural networks is proposed to build an index called LNI for NDN forwarding plane. Through learning the distributions of the names retrieved in the static memory, LNI that will be trained by real NDN names offline and preset in content routers in the future can not only reduce the memory consumption and the probability of false positive, but also ensure the performance of real NDN name lookup. Experimental results show that LNI-based FIB can reduce the memory consumption to 58.258 MB. Moreover, as it can be deployed on SRAMs, the throughput is about 177 MSPS, which well meets the current network requirement for fast packet processing.

IP networking deals with end-to-end communication where the network layer routing protocols maintain the reachability from one address to another. However, challenging environments, such as mobile ad-hoc networks or MANETs, lead to frequent path failures and changes between the sender and receiver, incurring higher packet loss. The obligatory route setup and maintenance of a device-to-device stable path in MANETs incur significant data retrieval delay and transmission overhead. Such overhead exaggerates the packet loss manifold. Named Data Networking (NDN) can avoid such delays and overhead and significantly improve the overall network performance. It does so with direct application-controlled named-data retrieval from any node in a network instead of reaching a specific IP address with protocol message exchange. However, existing works lack any explicit or systematic analysis to justify such claims. Our work analyzes the core NDN and IP architectures in a MANET at a baseline level. The extensive simulations show that NDN, when applied correctly, yields much lower data retrieval latency than IP and can lower the network transmission overhead in most cases. As a result, NDN’s stateful forwarder can significantly increase the retrieval rate, offering a better trade-off at the network layer. Such performance comes from its caching, built-in multicast, and request aggregation without requiring an IP-like separate routing control plane.

Vehicle to Vehicle (V2V) communication opens a new way to make vehicles directly communicate with each other, providing faster responses for time-sensitive tasks than cellular networks. Effective V2V routing protocols are essential yet challenging, as the high dynamic road environment makes communication easy to break. Many prediction methods proposed in the existing protocols to address this issue are either flawed or have a poor effect. In this paper, to cope with the two aspects of the problems that cause communication interrupt, i.e., link breaks and route quality degradation, we design an acceleration-based trajectory prediction algorithm to estimate the link lifetime, and a machine learning model to predict route quality. Based on the prediction algorithms, we propose PQR, a Prediction-supported Quality-aware Routing protocol, which can proactively switch to a better route before the current link breaks or the route quality degrades. Especially, considering the limitations of the current routing protocols, we elaborate a new hybrid routing protocol that integrates the topology-based method and location-based method to achieve instant communication. Simulation results show that PQR outperforms the existing protocols in Packet Delivery Ratio (PDR), Roundtrip Time (RTT), and Normalized Routing Overhead (NRO). Specifically, we have also implemented a vehicular testbed to demonstrate PQR’s real-world performance, and results show that PQR achieves almost no packet loss with latency less than 10ms during route handoff for topology change.

Adapting applications’ data rates in multi-hop wireless ad-hoc networks is inherently challenging. Packet collision, channel contention, and queue buildup contribute to packet loss but are difficult to manage in conventional TCP/IP architecture. This work explores a data-centric approach based on Name Data Networking (NDN) architecture, which is considered more suitable for wireless ad-hoc networks. We show that the default NDN transport offers better performance in linear topologies but struggles in more extensive networks due to high collision and contention caused by excessive Interests from out-of-order data retrieval and redundant data transmission from improper Interest lifetime setting as well as in-network caching. To fix these, we use round-trip hop count to limit Interest rate and Dynamic Interest Lifetime to minimize the negative effect of improper Interest lifetime. Finally, we analyze the effect of in-network caching on transport performance and which scenarios may benefit or suffer from it.

One unique architectural benefit of Named Data Networking (NDN) is adaptive forwarding, i.e., the forwarding plane is able to observe past data retrieval performance and use it to adjust forwarding decisions for future Interests. To be effective, adaptive forwarding assumes thatInterest Routing Localityis related to Interests’ common name prefix, meaning that Interests sharing the same prefix are likely to follow a similar forwarding path within a short period of time. Since Interests can have multiple common prefixes with different lengths, the real challenge is determining which prefix length should be used in adaptive forwarding to record path performance measurements - we refer to this as thePrefix Granularity Problem. The longer the common prefix is, the better the Interest Routing Locality, and the larger the forwarding table. Given the limited FIB size, route names are designed to be considerably shorter than Interest names. Existing adaptive forwarding designs use route names to record path performance measurements, which looses forwarding adaptability as it promises in the event of partial network failures. In this work, we propose to dynamically aggregate and de-aggregate name prefixes in the forwarding table in order to use the prefixes that are the most appropriate given current network situation. In addition, to reduce the overhead of adaptive forwarding, we propose mechanisms to minimize the use of the longest prefix matching in Data packet processing. Simulations demonstrate that the proposed techniques can result in better forwarding decisions in the event of partial network failures with significantly reduced overhead.

Information-Centric Networking (ICN) provides scalable and efficient content distribution at the Internet scale due to in-network caching and native multicast. To support these features, a content router needs high performance at its data plane, which consists of three forwarding steps: checking the Content Store (CS), then the Pending Interest Table (PIT), and finally the Forwarding Information Base (FIB). In this work, we build an analytical model of the router and identify that CS is the actual bottleneck. Then, we propose a novel mechanism called “NB-Cache” to address CS’s performance issue from a network-wide point of view. In NB-Cache, when packets arrive at a router whose CS is fully loaded, instead of being blocked and waiting for the CS, these packets are forwarded to the next-hop router, whose CS may not be fully loaded. This approach essentially utilizes Content Stores of all the routers along the forwarding path in parallel rather than checking each CS sequentially. NB-Cache follows a design pattern of on-demand load balancing and can be formulated into a non-trivial N-queue bypass model. We use the Markov chain to establish its theoretical base and find an algorithm for automated transition rate matrix generation. Experiments show significant improvement of data plane performance: 70% reduction in round-trip time (RTT) and 130% increase in throughput. NB-Cache decouples the fast packet forwarding from the slower content retrieval thus substantially reducing CS’s heavy dependency on fast but expensive memory.

The Internet can be made more efficient and robust with hop-by-hop multipath routing: Each router on the path can split packets between multiple nexthops in order to 1) avoid failed links and 2) reduce traffic on congested links. Before deciding how to split traffic, one first needs to decide which nexthops to allow at each step. In this paper, we investigate the requirements and trade-offs for making this choice.Most related work chooses the viable nexthops by applying the "Downward Criterion", i.e., only adding nexthops that lead closer to the destination; or more generally by creating a Directed Acyclic Graph (DAG) for each destination. We show that a DAG's nexthop options are necessarily limited, and that, by using certain links in both directions (per destination), we can add further nexthops while still avoiding loops. Our solution LFID (LoopFree Inport-Dependent) routing, though having a slightly higher time complexity, leads to both a higher number of and shorter potential paths than related work. LFID thus protects against a higher percentage of single and multiple failures (or congestions) and comes close to the performance of arbitrary source routing.

Information-Centric Networking (ICN) provides scalable and efficient content distribution at the Internet scale due to its in-network caching and native multicast capabilities. To support these features, a content router needs high performance at its data plane, which consists of three forwarding steps: checking the Content Store (CS), then the Pending Interest Table (PIT), and finally the Forwarding Information Base (FIB). While prior works focus on performance optimization of a single step, we build an analytical model of content router's entire data plane and identify that CS is the actual bottleneck in the pipeline. Compared with PIT and FIB, CS is more challenging because it has more data to read/write, may have more entries in its table to store and lookup, and needs to organize content objects to sustain frequent cache replacement. Then, we propose a novel mechanism called "NB-Cache" to address CS's performance issue from a network-wide point of view rather than a single router's. In NB-Cache, when packets arrive at a router whose CS is fully loaded, instead of being blocked and waiting for the CS, these packets are forwarded to the next-hop router, whose CS may not be fully loaded. This approach essentially utilizes Content Stores of all the routers along the forwarding path in parallel rather than checking each CS sequentially. Our experiments show significant improvement of data plane performance: 70% reduction in round-trip time (RTT) and 130% increase in throughput.

Name lookup is an essential function but a performance bottleneck in both today's and future network architectures. Trie is an excellent candidate data structure and has been widely used for looking up and updating names. However, the granularity of trie-at bit, byte (character), or component level-can dramatically affect the network performance in terms of memory usage and packet-processing speed, which has not yet been studied adequately. To fill this gap, we first show that the choice of trie's granularity for name lookups and updates (i.e., insertions and removals) is not a trivial problem due to the complex performance tradeoffs involved. We also introduce a new tool, called NameGen, which uses a Markov-based name learning model and generates pseudo-real datasets with different tunable name characteristics. We compare different trie granularities based on a collection of datasets and performance metrics, highlight the strengths and weaknesses of each granularity, and draw a conclusion on the choice of granularity. Surprisingly, our experimental evaluation finds that there are only two key rules to choose the proper trie's granularity for any kind of dataset: 1) bit-level trie is the choice when the memory requirement is a real concern and 2) character- and component-level tries are preferred for faster lookups and updates when dealing with names composed of short and long components, respectively.

Name lookup is an essential function, but a performance bottleneck in both today's and future network architectures. Variable-length and unbounded names rather than fixed-length addresses, as well as much larger and more dynamic forwarding tables call for a careful re-engineering of lookup structures for fast, memory-efficient, and scalable packet forwarding. We propose a novel data structure, called NameTrie, to store and index forwarding table entries efficiently and to support fast name lookups and updates. Its novelty lies in the optimized design and implementation of a character-trie structure. The nodes of NameTrie are stored compactly, improving cache efficiency and speeding up packet processing. Its edges are implemented using a hash table, facilitating fast name lookups and updates. A new scheme is used to encode control information without consuming additional memory. Running on conventional commodity hardware and using large-scale real-world name datasets, our implementation of NameTrie in software achieves 2.82~3.56, 3.48~3.72, and 2.73~3.25 million name insertions, lookups, and removals per second, respectively, for various datasets while requiring a small memory footprint. We have conducted a comprehensive performance evaluation against the state-of-the-art of named data networking (NDN) as a typical use-case. It is shown to require at least 35% less memory and runs at least 3x faster for name table lookups and updates than two well-known trie-based schemes in NDN.

A data-centric network architecture, Named Data Networking (NDN) has been developed to meet applications' growing demands of network effciency and resilience. Currently, the deployment of NDN in real network environments requires careful system design to not only enable NDN but also support IP traffc, considering IP network has been prevalent for decades and almost all the equipments and applications are IP-based. In this paper, we take the most popular local area network (LAN) technology, Ethernet, as an example to investigate incremental deployment of NDN. Assuming a local network with both NDN and IP traffc, we mainly layout three deployment scenarios: NDN-enabled hosts and all Ethernet switches, NDN-enabled hosts and all Dual-Stack switches (i.e., it can process both NDN and IP traffc), and a hybrid network with both Dual-Stack switches and Ethernet switches. We examine the technical issues involved in each scenario and present solutions. In particular, in the hybrid scenario, we propose heuristics to optimize the placement of Dual-Stack switches. Compared with traditional Ethernet, introducing Dual-Stack switches can improve network effciency and resiliency by utilizing more links, reducing each link's traffc load, and taking shorter paths, at the same time also maintaining the functionality of IP-based applications.

As a novel Internet architecture, Named Data Networking (NDN) shifts the communication model from address-centric to content-centric. An NDN router caches the data in its content store, greatly reducing network traffic. NDN adopts the hierarchical naming schema, which allows the name aggregation and enables high scalability. However, in a richly connected topology, the nearest data replica are often not on the path dictated by NDN's tree-like data fetching model. This might result in a lower data delivery efficiency compared with the flat self-certifying naming schema in other Information-Centric Networking (ICN) architectures. To address the low efficiency problem, we propose a CDN-like enhancement to the NDN design, called Fetching the Nearest Replica (FNR). In FNR, when a consumer sends an interest for a popular data, the data is fetched from the nearest replica in the network, regardless of whether it is on the best path from the producer to the consumer. We present the design details and theoretical overhead analysis for FNR. Our evaluation results using ndnSIM simulator show that on average FNR reduces the total (inter-domain, intra-domain) traffic by 25.6% (53.0%, 18.2%) on average, compared to the default NDN approach. In addition, the average latency is reduced by 37% and the average cost is reduced by 51.4%. To the best of our knowledge, this paper is the first NDN enhancement in the literature to support nearest replica fetching in NDN.

Routing in NDN networks must scale in terms of forwarding table size and routing protocol overhead. Hyperbolic routing (HR) presents a potential solution to address the routing scalability problem, because it does not use traditional forwarding tables or exchange routing updates upon changes in network topologies. Although HR has the drawbacks of producing sub-optimal routes or local minima for some destinations, these issues can be mitigated by NDN's intelligent data forwarding plane. However, HR's viability still depends on both the quality of the routes HR provides and the overhead incurred at the forwarding plane due to HR's sub-optimal behavior. We designed a new forwarding strategy called Adaptive Smoothed RTT-based Forwarding (ASF) to mitigate HR's sub-optimal path selection. This paper describes our experimental investigation into the packet delivery delay and overhead under HR as compared with Named-Data Link State Routing (NLSR), which calculates shortest paths. We run emulation experiments using various topologies with different failure scenarios, probing intervals, and maximum number of next hops for a name prefix. Our results show that HR's delay stretch has a median close to 1 and a 95th-percentile around or below 2, which does not grow with the network size. HR's message overhead in dynamic topologies is nearly independent of the network size, while NLSR's overhead grows polynomially at least. These results suggest that HR offers a more scalable routing solution with little impact on the optimality of routing paths.

IEEE 802.11-based wireless LAN, commonly referred to as Wi-Fi, has become a universal solution for the last-hop network access. In large and public assembly places, people may use their mobile devices to view the video of the same popular events via the same wireless access points (APs). However, current 802.11 APs transmit the same video stream multiple times via separate unicast sessions due to the well-known poor reliability and low data rate of the legacy Wi-Fi multicast. Besides, in traditional single-layer-coded video streams, all clients have to settle with the lowest video bitrate limited by the client with the worst channel quality. To address these problems, we propose M3, a practical and reliable multi-layer video multicast solution over multi-rate Wi-Fi networks. The aims of our system are, in the premise of no change to APs, not only to ensure that all clients can smoothly watch the video at least with the lowest quality, but also to maximize the overall video quality received by all clients. To meet these design goals, the video server selects certain clients as unicast receivers to transmit different SVC video layers, and other clients listen for the packets in the promiscuous mode. It is challenging to select specific unicast receivers and allocate different SVC layers to fully utilize the available bandwidth because of dynamic network conditions. To overcome this challenge, we use a periodical feedback mechanism to collect necessary statistics from clients, and use them to derive an optimal SVC-layer allocation strategy to maximize the video quality. We implemented a prototype in a real Wi-Fi testbed consisting of one AP and one M3server and 8 clients. Compared with the single-layer video multicast, our M3system can improve the total received video rate by up to 200%

Power saving in the network infrastructure has received great attention in recent years. Power-aware traffic management is proposed in many works, in which a subset of routers/links are preferentially used to carry traffic while other links are activated only when traffic load is high. However, it remains challenging how to minimize the overhead to both ISPs and applications, which is important to the successful deployment of power-aware traffic management in a real network. This paper presents PALS, a new Power-Aware Link State routing based traffic management protocol. Compared with previous solutions, PALS remarkably reduces the overheads to ISPs and applications by the following innovations. First, PALS minimizes the forwarding table expansion due to dynamic power-aware routing, by using destination based routing instead of pairwise routing (e.g., MPLS). Second, PALS limits packet reordering for applications, by never splitting traffic between an IE (ingress-egress) router pair to multiple paths. Third, PALS significantly reduces the computation complexity of the power-aware routing algorithm, by running a simple path selection algorithm at each ingress router with the knowledge of local traffic information as well as global link utilization, which are much easier to obtain than global traffic matrix required by the state-of-the-art solutions (e.g., Zhang , IEEE ICNP 2010). Extensive simulations and testbed experiments show that, although bearing the simplicities to minimize the overhead, PALS saves satisfactory network power, with quick response to traffic variance and negligible impact on the packet delivery performance for applications.

As the network infrastructure has been consuming more and more power, various schemes have been proposed to improve the power efficiency of network devices. Many schemes put links to sleep when idle and wake them up when needed. A presumption in these schemes, though, is that router's line cards can be waken up very quickly. However, through systematic measurement of a major vendor's high-end routers, we find that it takes minutes to get a line card ready under the current design. To address this issue, we propose a new line card design that 1) keeps the host processor in a line card standby, which only consumes a small fraction of power but will save considerable wakeup time, and 2) downloads a slim slot of popular prefixes with higher priority, so that the line card will be ready for forwarding most of the traffic much earlier. We design algorithms as well as architecture that ensure fast and correct longest prefix match during prioritized routing prefix download. Experiments on an FPGA-based prototype show that the customized hardware can be ready to forward packets in 127.27 ms, which is 0.3% of the time the original design takes. This can better support numerous power-saving schemes based on the sleep/wakeup mechanism.

Malicious attack and misconfiguration can cause unreachable websites, network outages, and other damages. Such incidents are usually observed together with anomalous AS paths which violate a “valley-free” policy. Existing techniques to infer routing policy cannot satisfy industrial demand of real-time route leak detection because they are very likely to trigger false positives. In this paper, we propose an online detection scheme dedicated to detect route leak AS paths. Based on long-lived routing paths, and route anomalous concurrency, we manage to filter possible false positives in online scenarios. Applying this scheme to Oregon's routing data from 2009 to 2013, we detect 136 route leak events. Our evaluation shows that our scheme triggers no false positives, and most of these events are previously unknown to the research and operation communities at large.

Named Data Networking (NDN) is a new Internet architecture that replaces today's focus on where - addresses and hosts - with what - the content that users and applications care about. One of NDN's prominent advantages is scalable and efficient content distribution due to its native support of caching and multicast in the network. However, at the last hop to wireless users, often the WiFi link, current NDN implementation still treats the communication as multiple unicast sessions, which will cause duplicate packets and waste of bandwidth when multiple users request for the same popular content. WiFi's built-in broadcast mechanism can alleviate this problem, but it suffers from packet loss since there is no MAC-layer acknowledgement as in unicast. In this paper, we develop a new NDN-based cross-layer approach called NLB for efficient and scalable live video streaming over wireless LAN. The idea is to use WiFi's broadcast channel to deliver content from the access point to the users, a leader-based mechanism to suppress duplicate requests from users, and receiver-driven rate control and loss recovery. The design is implemented and evaluated in a physical testbed comprised of a commodity residential access point and 20 WiFi clients. While NDN with multiple unicast sessions or plain broadcast can support no more than 7 concurrent viewers of a 1Mbps streaming video, NDN plus NLB supports all 20 viewers, and can likely support many more when present.

As the network infrastructure has been consuming more and more power, various schemes have been proposed to improve power efficiency of network devices. Many schemes put links to sleep when idle and wake them up when needed. A presumption in these schemes, though, is that router's line cards can be waken up quickly. However, through systematic measurement of a major vender's high-end router, we find that it takes minutes to get a line card ready under the current implementation. To address this issue, we propose a new line card design that (1) keeps the host processor in a line card always up, which only consumes a small fraction of power, and (2) downloads a slim slot of popular prefixes with higher priority, so that the line card will be ready for forwarding most of the traffic much earlier. We design algorithms that ensure fast and correct longest prefix match lookup during prioritized routing prefix download. Experiments on real hardware show that the wakeup time can be reduced to 127.27ms, which is 0.3% of the original line card wakeup time, well supporting many power-saving schemes.

Complex name constitution plus huge-sized name routing table makes wire speed name lookup a challenging task in Named Data Networking. To overcome this challenge, we propose two techniques to significantly speed up the lookup process. First, we look up name prefixes in an order based on the distribution of prefix length in the forwarding table, which can find the longest match much faster than the linear search of current prototype CCNx. The search order can be dynamically adjusted as the forwarding table changes. Second, we propose a new near-perfect hash table data structure that combines many small sparse perfect hash tables into a larger dense one while keeping the worst-case access time of O(1) and supporting fast update. Also the hash table stores the signature of a key instead of the key itself, which further improves lookup speed and reduces memory use.

The fast growth of global routing table size has been causing concerns that the Forwarding Information Base (FIB) will not be able to fit in existing routers' expensive line-card memory, and upgrades will lead to higher cost for network operators and customers. FIB Aggregation, a technique that merges multiple FIB entries into one, is probably the most practical solution since it is a software solution local to a router, and does not require any changes to routing protocols or network operations. While previous work on FIB aggregation mostly focuses on reducing table size, this work focuses on algorithms that can update compressed FIBs quickly and incrementally. Quick update is critical to routers because they have very limited time to process routing updates without impacting packet delivery performance. We have designed three algorithms: FIFA-S for smallest table size, FIFA-T for shortest running time, and FIFA-H for both small tables and short running time, and operators can use the one best suited to their needs. These algorithms significantly improve over existing work in terms of reducing routers' computation overhead and limiting impact on the forwarding plane while maintaining a good compression ratio.

A concurrent prefix hijack happens when an unauthorized network originates IP prefixes of multiple other networks. Its extreme case is leaking the entire routing table, i.e., hijacking all the prefixes in the table. This is a well-known problem and there exists a preventive measure in practice to safeguard against it. However, we investigated and uncovered many concurrent prefix hijacks that didn't involve a full-table leak. We report these events and their impact on Internet routing. y correlating suspicious routing announcements and comparing it with a network's past routing announcements, we develop a method to detect a network's abnormal behavior of offending multiple other networks simultaneously. Applying the detection algorithm to BGP routing updates from 2003 through 2010, we identify five to twenty concurrent prefix hijacks every year, most of which are previously unknown to the research and operation communities at large. They typically hijack prefixes owned by a few tens of networks, last from a few minutes to a few hours, and pollute routes at most vantage points.

Content Delivery Networks (CDN) are overlay network of servers being used to deliver growing traffic demands on the Internet. As a result, CDNs are facing ever-increasing operating costs. Internet Service Providers (ISP) charge CDNs on server traffic, computed using common usage-based charging models, e.g. 95th Percentile charging. We propose Network Cost Aware Request Routing, NetReq, that assign user requests to reduce server charging volume. We compare NetReq against nearest-available server request routing in large scale simulations for both Web and multicast traffic requests. NetReq reduces charging volume for both traffic request types, thereby reducing cost. NetReq provides comparable network performance for multicast traffic by introducing end-to-end delay as a constraint in the request-routing. NetReq marginally increases network performance for Web traffic, when content maybe available at every server.

Internet Service Providers (ISPs) route traffic at the IP layer with the preference of less inter-carrier payments while Content Distribution Networks (CDNs) route traffic at the application layer with the preference of better application performance. Such mismatch of routing preferences leads to conflicts that eventually result in higher operational cost for both ISPs and CDNs. In this paper, we propose to make CDN and ISP routing mutually beneficial through ISP's non-uniform bandwidth charging and CDN's bandwidth cost-aware request routing. More specifically, ISPs charge different prices for traffic that traverses different types of inter domain links and CDNs, in routing user requests to their servers, try to minimize their ISP payments by taking the pricing information into consideration. We evaluate the solution in large scale simulations. The greedy solution presents the lowest bandwidth cost for CDNs but at the expense of network performance for users. With end-to-end delay introduced as a constraint in the optimization process, the solution maintains good network performance for users while achieving significant savings in bandwidth cost. Compared with conventional nearest-available policy in CDN request routing, our solution moves significant amount of inter domain traffic from provider routes to peer or customer routes, reducing operational costs for ISPs and CDNs.

The global routing table size has been increasing rapidly, outpacing the upgrade cycle of router hardware. Recently aggregating the Forwarding Information Base (FIB) emerges as a promising solution since it reduces FIB size significantly in the short term and it is compatible with any long-term architectural solutions.Because FIB entries change dynamically with routing updates, an important component of any FIB aggregation scheme is to handle routing updates efficiently while shrinking FIB size as much as possible. In this paper, we first propose two incremental FIB aggregation algorithms based on the ORTC scheme. We then quantify the tradeoffs of the proposed algorithms, which will help operators choose the algorithms best suited for their networks.

Current network infrastructures exhibit poor power efficiency, running network devices at full capacity all the time regardless of the traffic demand and distribution over the network. Most research on router power management are at component level or link level, treating routers as isolated devices. A complementary approach is to facilitate power management at network level by routing traffic through different paths to adjust the workload on individual routers or links. Given the high path redundancy and low link utilization in today's large networks, this approach can potentially allow more network devices or components to go into power saving mode. This paper proposes an intra-domain traffic engineering mechanism, GreenTE, which maximizes the number of links that can be put into sleep under given performance constraints such as link utilization and packet delay. Using network topologies and traffic data from several wide-area networks, our evaluation shows that GreenTE can reduce line-cards' power consumption by 27% to 42% under constraints that the maximum link utilization is below 50% and the network diameter remains the same as in shortest path routing.

False routing announcements are a serious security problem, which can lead to widespread service disruptions in the Internet. A number of detection systems have been proposed and implemented recently, however, it takes time to detect attacks, notify operators, and stop false announcements. Thus detection systems should be complemented by a mitigation scheme that can protect data delivery before the attack is resolved. We propose such a mitigation scheme, QBGP, which decouples the propagation of a path and the adoption of a path for data forwarding. QBGP does not use suspicious paths to forward data traffic, but still propagates them in the routing system to facilitate attack detection. It can protect data delivery from routing announcements of false sub-prefixes, false origins, false nodes and false links. QBGP incurs overhead only when there are suspicious paths, which happen infrequently in real BGP traces. Results from large scale simulations and BGP trace analysis show that QBGP is light-weight yet effective, and it converges faster and incurs less overhead than Pretty Good BGP.

The rapid growth of global routing tables has raised concerns among many Internet Service Providers. The most immediate concern regarding routing scalability is the size of the Forwarding Information Base (FIB), which seems to be growing at a faster pace than router hardware can support. This paper focuses on one potential solution to this problem - FIB aggregation, i.e., aggregating FIB entries without affecting the forwarding paths taken by data traffic. Compared with alternative solutions to the routing scalability problem, FIB aggregation is particularly appealing because it is a purely local software optimization limited within a router, requiring no changes to routing protocols or router hardware. To understand the feasibility of using FIB aggregation to extend router lifetime, we present several FIB aggregation algorithms and evaluate their performance using routing tables and updates from tens of networks. We find that FIB aggregation can reduce the FIB table size by as much as 70% with small computational overhead. We also show that the computational overhead can be controlled through various mechanisms.

Internet routing tables have been growing rapidly due to factors such as edge-site multihoming, traffic engineering, and disjoint address allocations. To address the routing scalability problems caused by this rapid growth, we propose an evolutionary approach that is incrementally deployable and provides immediate benefits to any adopting ASes. The basic premise of the approach is that route aggregation removes from routing tables the unnecessary topological details about remote portions of the Internet. We demonstrate that aggregation can be applied incrementally starting from local scopes within individual routers and individual ASes, and gradually expanded to the global Internet scope. The evaluation studies show that route aggregation is effective in addressing FIB scalability problems within a router and within a network.

The common objective of network traffic engineering is to minimize the maximal link utilization in a network in order to accommodate more traffic and reduce the chance of congestion. Traditionally this is done by either optimizing OSPF link weights or using MPLS tunnels to direct traffic. However, they both have problems: OSPF weight optimization triggers network-wide convergence and significant traffic shift, while pure MPLS approach requires a full mesh of tunnels to be configured throughout the network. This paper formulates the traffic engineering problem as a Multi-Commodity Flow problem with hybrid MPLS/OSPF routing (MCFTE). As a result, the majority of traffic is routed by regular OSPF, while only a small number of MPLS tunnels are needed to fine-tune the traffic distribution. It keeps OSPF link weights unchanged to avoid triggering network convergence, and needs far fewer MPLS tunnels than the full-mesh to adjust traffic. Compared with existing hybrid routing approaches, MCFTE achieves the optimal link utilization, runs about two orders of magnitude faster, and is more robust against measurement inaccuracy in traffic demand.

Internet-scale dissemination of streaming contents (e.g., live sports games) can be achieved by infrastructure-based overlay multicast networks, where multicast service providers deliver the contents via dedicated servers strategically placed over the Internet. Given the huge amount of data traffic, one of the major operation costs is the ISP cost for network access. However, existing overlay multicast protocols only consider network performance metrics in building dissemination trees without taking into account the potentially high ISP cost they may incur. This paper presents a scheme, revenue-driven overlay multicast networks (ROMaN), to assign users to different servers in order to maximize the profit derived from providing multicast services. ROMaN exploits the fact that ISP charging functions are concave by assigning users to the cheapest available servers, and dynamically adjusts the assignment to accommodate the churns of group membership. The evaluation shows that ROMaN not only can reduce ISP cost substantially, but also has shorter end-to-end delay due to smaller overlay size, and the longer a user stays in the group the better the service it will receive.

Despite significant efforts to obtain an accurate picture of the Internet's actual connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper we assess the quality of the inferred Internet maps through case studies of a set of ASes. These case studies allow us to establish the ground truth of AS-level Internet connectivity between the set of ASes and their directly connected neighbors. They also enable a direct comparison between the ground truth and inferred topology maps and yield new insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, and which parts are missing and why. This information is critical in assessing for what kinds of real-world networking problems the use of currently inferred AS maps or proposed AS topology models are, or are not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.

A prefix hijack attack involves an attacker announcing victim networks' IP prefixes into the global routing system. As a result, data traffic from portions of the Internet can be diverted to attacker networks. Prefix hijack attacks are a serious security threat in the Internet and it is important to understand the factors that affect the resiliency of victim networks against these attacks. In this paper, we conducted a systematic study to gauge the effectiveness of prefix hijacks launched at different locations in the Internet topology. Our study shows that direct customers of multiple tier-1 networks are the most resilient, even more than the tier-1 networks themselves. Conversely, if these customer networks are used to launch prefix hijacks, they would also be the most effective launching pads for attacks. We verified our results through case studies using real prefix hijack incidents that had occurred in the Internet.

In this paper we propose a new routing protocol and address scheme, geographically informed inter-domain routing (GIRO). GIRO departs from previous geographic addressing proposals in that it uses geographic information to assist, not to replace, the provider-based IP address allocation and policy-based routing. We show that, by incorporating geographic information into the IP address structure, GIRO can significantly improve the scalability and performance of the global Internet routing system. Within the routing policy constraints, geographic information enables the selection of shortest available routing paths. We evaluate GIRO'S performance through simulations using a Rocketfuel-measured Internet topology. Our results show that, compared to the current practice, GIRO can reduce the geographic distance for 70% of the existing BGP paths, and the reduction is more than 40% for about 20% of the paths. Furthermore, encoding geographic information into IP addresses also enables GIRO to apply geographical route aggregation, and a combination of geographic and topological aggregation can lead to 75% reduction of the current BGP routing table size.

Characterizing the evolution of Internet topology is important to our understanding of the Internet architecture and its interplay with technical, economic and social forces. A major challenge in obtaining empirical data on topology evolution is to identify real topology changes from the observed topology changes, since the latter can be due to either topology changes or transient routing dynamics. In this paper, we formulate the topology liveness problem and propose a solution based on the analysis of BGP data. We find that the impact of transient routing dynamics on topology observation decreases exponentially over time, and that the real topology dynamics consist of a constant-rate birth process and a constant-rate death process. Our model enables us to infer real topology changes from observation data with a given confidence level. We demonstrate the usefulness of the model by applying it to three applications: providing more accurate views of the topology, evaluating theoretical evolution models, and empirically characterizing the trends of topology evolution. We find that customer networks and provider networks have distinct evolution trends, which can provide an important input to the design of future Internet routing architecture.

A number of previous measurement studies [10, 12, 17] have shown the existence of path exploration and slow convergence in the global Internet routing system, and a number of protocol enhancements have been proposed to remedy the problem [21, 15, 4, 20, 5]. However all the previous measurements were conducted over a small number of testing prefixes. There has been no systematic study to quantify the pervasiveness of BGP slow convergence in the operational Internet, nor there is any known effort to deploy any of the proposed solutions.In this paper we present our measurement results from identifying BGP slow convergence events across the entire global routing table. Our data shows that the severity of path exploration and slow convergence varies depending on where prefixes are originated and where the observations are made in the Internet routing hierarchy. In general, routers in tier-1 ISPs observe less path exploration, hence shorter convergence delays than routers in edge ASes, and prefixes originated from tier-1 ISPs also experience less path exploration than those originated from edge ASes. Our data also shows that the convergence time of route fail-over events is similar to that of new route announcements, and significantly shorter than that of route failures, which confirms our earlier analytical results [19]. In addition, we also developed a usage-time based path preference inference method which can be used by future studies of BGP dynamics.

We conduct a systematic study on the pervasiveness and persistency of one specific phenomenon in the global routing system: a small set of highly active prefixes accounts for a large number of routing updates. Our data analysis shows that this phenomenon is commonly observed from monitors in many different ISPs, and exists throughout our 3-year study period. The analysis further shows that the majority of these prefixes are highly active for only one or a few days, while a small number of them are persistently active over long period of time. Case studies demonstrate that the causes of these high routing activity include topological failures, BGP path exploration, protocol defects, and the failure of turning on protection mechanisms.

Route Flap Damping is a mechanism generally used in network routing protocols. Its goal is to limit the global impact of unstable routes by temporarily suppressing routes with rapid changes over short time periods. Although route damping is a clearly defined and simple procedure at each router, its effect in a large network setting is not well understood. We show that the current damping design leads to the intended behavior only under persistent route flapping. When the number of flaps is small, the global routing dynamics deviates significantly from the expected behavior with a longer convergence delay. Previous work observed that a single route flap can falsely trigger route suppression due to path exploration. However our simulations show that this false suppression only accounts for 30% of the convergence delay after a single route flap. Our study reveals previously unknown interactions between reuse timers at different routers. Route suppression and reuse at different routers are triggered at different times and thus affect the number of updates received by other routers. In turn, this impacts other routers’ damping behavior. We propose to use Root Cause Notification to eliminate both false suppression and undesirable timer interaction.

One important performance measure for routing protocols is packet delivery. An ideal routing protocol should quickly adapt to topological changes and deliver packets as long as any path to the destination exists. In this paper, we examine the packet delivery performance in a network running the BGP routing protocol when a destination may be disconnected from time to time. We develop two metrics, extra downtime and false uptime, to capture the time difference between actual loss of connectivity and perceived unreachability. Our results show that extra downtime closely matches T/sub up/ convergence delay, and false uptime closely matches T/sub down/ convergence delay. Furthermore, our results show that, for transient connectivity failures, a shorter T/sub down/ convergence time can have negative impact on packet delivery.

Overlay networks represent an emerging technology for rapid deployment of novel network services and applications. However, since public overlay networks are built out of loosely coupled end-hosts, individual nodes are less trustworthy than Internet routers in carrying out the data forwarding function. Here we describe a set of mechanisms designed to detect and repair errors in the data stream. Utilizing the highly redundant connectivity in overlay networks, our design splits each data stream to multiple sub-streams which are delivered over disjoint paths. Each sub-stream carries additional information that enables receivers to detect damaged or lost packets. Furthermore, each node can verify the validity of data by periodically exchanging Bloom filters, the digests of recently received packets, with other nodes in the overlay. We have evaluated our design through both simulations and experiments over a network testbed. The results show that most nodes can effectively detect corrupted data streams even in the presence of multiple tampering nodes.

The Internet distance map service (IDMaps) [P. Francis, S. Jamin, C. Jin, D. Raz, Y. Shavitt, and L. Zhang, 2001] provides distance estimates between any pair of hosts connected to the Internet. The IDMaps system comprises two component types: tracers that measure distance between IP address prefixes, and servers that collect measurement results and answer distance queries. The distance information protocol (DIP) is used for tracers to report measured distance data to servers. The dynamics on the Internet topology, the distributed nature of autonomous tracers and servers, and the vast size of the data set require that DIP provide highly adaptive and scalable data dissemination from tracers to servers. DIP is a soft-state announce/listen protocol and scales independently from the total amount of measurement data by all tracers. DIP achieves its scalability through combination of staged timers, positive feedback, and feedback suppression techniques, which enable DIP to disseminate only the most useful measurement data to servers in a dynamic way. Simulations verified DIP's scalability and adaptability under various network conditions.

While the advantages of multicast delivery over multiple unicast deliveries is undeniable, the deployment of the IP multicast protocol has been limited to "islands" of network domains under single administrative control. Deployment of inter-domain multicast delivery has been slow due to both technical and administrative reasons. In this paper we propose a Host Multicast Tree Protocol (HMTP) that (1) automates the interconnection of IP-multicast enabled islands and (2) provides multicast delivery to end hosts where IP multicast is not available. With HMTP, end-hosts and proxy gateways of IP multicast-enabled islands can dynamically create shared multicast trees across different islands. Members of an HMTP multicast group self-organize into an efficient, scalable and robust multicast tree. The tree structure is adjusted periodically to accommodate changes in group membership and network topology. Simulation results show that the multicast tree has low cost, and data delivered over it experiences moderately low latency.

Large homogeneous ad hoc wireless networks have a problem: the bandwidth available to a mobile user decreases as the number of nodes in the network increases. Using the embedded ad-hoc networking mechanism, nodes are able to transport packets across the network in a multihop fashion. An embedded mobile backbone is dynamically constructed to form a 2-level physical heterogeneous multihop wireless network. These backbone nodes provide two critical functions: (1) direct communication between neighboring cluster heads; and (2) efficient route discovery in HSR. With the broadcast feature of unmanned aerial vehicle (UAV), the link state can be broadcast to backbone nodes instead of "flooding" on the level 2. Thus, the routing overhead can be tremendously reduced, and the throughput will be improved. We modified hierarchical state routing (HSR) to have an intelligent selection algorithm to reduce the system latency caused by the long propagation delay of the UAV channel. The performance of the system is evaluated through simulation experiments.