Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Subject: search.filters.subject.Routing

Search Results

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    DIAGNOSING AND IMPROVING THE PERFORMANCE OF INTERNET ANYCAST
    (2019) Li, Zhihao; Spring, Neil; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    IP anycast is widely used in Internet infrastructure, including many of the root and top-level DNS servers, major open DNS resolvers, and content delivery networks (CDNs). Increasing popularity of anycast in DNS resolvers involves it in most activities of Internet users. As a result, the performance of anycast deployments is critical to all the Internet users. What makes IP anycast such an attractive option for these globally replicated services are the desired properties that anycast would appear to achieve: reduced overall access latency for clients, improved scalability by distributing traffic across servers, and enhanced resilience to DDoS attacks. These desired properties, however, are not guaranteed. In anycast, a packet is directed to certain anycast site through inter-domain routing, which can fail to pick a route with better performance in terms of latency or load balance. Prior work has studied anycast deployments and painted a mixed picture of anycast performance: many clients of anycast are not served by their nearby anycast servers and experience large latency overheads; anycast sometimes does not balance load across sites effectively; the catchment of an anycast site is mostly stable, but it is very sensitive to routing changes. Although it was observed over a decade ago that anycast deployments can be inefficient, there exist surprisingly few explanations on the causes or solutions. In addition, most prior work evaluated only one or several deployments with measurement snapshots. I extended previous studies by large-scale and longitudinal measurements towards distinct anycast deployments, which can provide more complete insights on identifying performance bottlenecks and providing potential improvements. More importantly, I develop novel measurement techniques to identify the major causes for inefficiency in anycast, and propose a fix to it. In this dissertation, I defend the following thesis: Performance-unawareness of BGP routing leads to larger path inflation in anycast than in unicast; and with current topology and protocol support, a policy that selects routes based on geographic information could significantly reduce anycast inflation. In the first part of the dissertation, I use longitudinal measurements collected from a large Internet measurement platform towards distinct anycast deployments to quantitatively demonstrate the inefficiency in performance of anycast. I measured most root DNS servers, popular open DNS resolvers, and one of the major CDNs. With the passive and active measurements across multiple years, I illustrate that anycast performs poorly for most deployments that I measured: anycast is neither effective at directing queries to nearby sites, nor does it distribute traffic in a balanced manner. Furthermore, this longitudinal study over distinct anycast deployments shows that the performance has little correlation with number of sites. In the second part of the dissertation, I focus on identifying the root causes for the performance deficits in anycast. I develop novel measurement techniques to compare AS-level routes from client to multiple anycast sites. These techniques allow me to reaffirm that the major cause of the inefficiency in anycast is the performance- unawareness of inter-domain routing. With measurements from two anycast deployments, I illustrate how much latency inflation among clients can be attributed to the policy-based performance-unaware decisions made by BGP routing. In addition, I design BGP control plane experiments to directly reveal relative preference among routes, and how much such preference affects anycast performance. The newly discovered relative preferences shed light on improving state-of-art models of inter-domain routing for researchers. In the last part of the dissertation, I describe an incrementally deployable fix to the inefficiency of IP anycast. Prior work has proposed a particular deployment scheme for anycast to improve its performance: anycast servers should be deployed such that they all share the same upstream provider. However, this solution would require re-negotiating services that are not working under such a deployment. Moreover, to put the entire anycast service behind a single upstream provider introduces a single point of failure. In the last chapter, I show that a static hint with embedded geographic information in BGP announcements fixes most of the inefficiency in anycast. I evaluate the improvements from such static hints in BGP route selection mechanisms through simulation with real network traces. The simulation results show that the fix is promising: in the anycast deployments I evaluated, the fix reduces latency inflation for almost all clients, and reduces latency by 50ms for 23% to 33% of the clients. I further conduct control plane experiments to evaluate the effectiveness of the static hints in BGP announcements with real-world anycast deployments. This dissertation provides broad and longitudinal performance evaluation of distinct anycast deployments for different services, and identifies an at-fault weakness of BGP routing which is particularly amplified in anycast, i.e., route selection is based on policies and is unaware of performance. While applying the model of BGP routing to diagnose anycast, anycast itself serves as a magnifying glass to reveal new insights on the route selection process of the BGP in general. This work can help refine the model of route selection process that can be applied to various BGP- related studies. Finally, this dissertation provides suggestions to the community on improving anycast performance, which thus improves performance and reliability for many critical Internet infrastructure and ultimately benefits global Internet users.
  • Thumbnail Image
    Item
    Solving, Generating, and Modeling Arc Routing Problems
    (2017) Lum, Oliver; Golden, Bruce; Wasil, Edward; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Arc routing problems are an important class of network optimization problems. In this dissertation, we develop an open source library with solvers that can be applied to several uncapacitated arc routing problems. The library has a flexible architecture and the ability to visualize real-world street networks. We also develop a software tool that allows users to generate arc routing instances directly from an open source map database. Our tool has a visualization capability that can produce images of routes overlaid on a specific instance. We model and solve two variants of the standard arc routing problem: (1) the windy rural postman problem with zigzag time windows and (2) the min-max K windy rural postman problem. In the first variant, we allow servicing of both sides of some streets in a network, that is, a vehicle can service a street by zigzagging. We combine insertion and local search techniques to produce high-quality solutions to a set of test instances. In the second variant, we design a cluster-first, route-second heuristic that compares favorably to an existing heuristic and produces routes that are intuitively appealing. Finally, we show how to partition a street network into routes that are compact, balanced, and visually appealing.
  • Thumbnail Image
    Item
    Sensitivity of Peak Discharge Calculation to GIS-Derived Hydrologic Routing Parameters in the TR-20 Rainfall-Runoff Model
    (2006-08-15) Stack, Ian Malone; Moglen, Glenn; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Hydrologic routing of runoff from upstream locations is a central element in rainfall-runoff modeling. Channel cross-section geometry is used to develop routing parameters for this process. The sensitivity of the routed peak discharge to cross-section location along the routing reach is examined using two methods in this thesis. First, an enumeration method was used to analyze the sensitivity of overall peak discharge to the channel routing process by executing the TR-20 model for all possible cross-section locations evaluated within the GIS. Second, a regression equation as a function of the modified att-kin method routing coefficient, reach length, and channel slope shows promise as a planning and decision making tool when implementing the rainfall-runoff model. Finally, case study analyses support the usefulness that a possible future expert system would provide for guidance on developing routing reach cross-section characteristics to engineers and other professionals that use GIS to perform hydrologic rainfall-runoff modeling.
  • Thumbnail Image
    Item
    Efficient Cross Layer Designs for IEEE 802.11 Wireless Networks
    (2006-04-24) Nadeem, Tamer; Agrawala, Ashok; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Various properties of wireless networks, such as mobility, frequent disconnections and varying channel conditions, have made it a challenging task to design networking protocols for wireless communications. In this dissertation, we address several problems related to both the routing layer and medium access control (MAC) layer in wireless networks aiming to enhance the network performance. First, we study the effect of the channel noise on the network performance. We present mechanisms to compute energy-efficient paths in noisy environments for ad hoc networks by exploiting the IEEE 802.11 fragmentation mechanism. These mechanisms enhance the network performance up to orders of magnitude in terms of energy and throughput. We also enhance the IEEE 802.11 infrastructure networks with a capability to differentiate between different types of unsuccessful transmissions to enhance the network performance. Second, we study the effects of the physical layer capture phenomena on network performance. We modify the IEEE 802.11 protocol in a way to increase the concurrent transmissions by exploiting the capture phenomena. We analytically study the potential performance enhancement of our mechanism over the original IEEE 802.11. The analysis shows that up to 35% of the IEEE 802.11 blocking decisions are unnecessary. The results are verified by simulation in which we show that our enhanced mechanism can achieve up to 22% more throughput. Finally, we exploit the spatial reuse of the directional antenna in the IEEE 802.11 standards by developing two novel opportunistic enhancement mechanisms. The first mechanism augments the IEEE 802.11 protocol with additional information that gives a node the flexibility to transmit data while other transmissions are in its vicinity. The second mechanism changes the access routines of the IEEE 802.11 data queue. We show analytically how the IEEE 802.11 protocol using directional antenna is conservative in terms of assessing channel availability, with as much as 60% of unnecessary blocking assessments and up to 90% when we alter the accessing mechanism of the data queue. By simulation, we show an improvement in network throughput of 40% in the case of applying the first mechanism, and up to 60% in the case of applying the second mechanism.
  • Thumbnail Image
    Item
    MAXIMIZING DATA DOWNLOAD CAPABILITIES FOR FUTURE CONSTELLATION SPACE MISSIONS
    (2004-07-27) Chen, Yingyong; Baras, John S; Hadjitheodosiou, Michael; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    We outline the first step toward the development of a unified space communication network approach, offering more flexibility, robustness, expandability and compatibility with terrestrial networks. The aim is to maximize the data download capabilities of future missions while reducing the development and operational costs. We introduce the current State-of-the-Art in space communications, present the benefits of a unified approach and discuss some challenges that need to be addressed to enable this transition. We focus on developing a suitable dynamic routing algorithm and a reconfigurable simulation framework. A case study on the Magnetospheric Multi-Scale constellation mission shows that both NASAs Deep Space Network and some commercial ground facilities can provide sufficient coverage for this mission and demonstrates the benefits of a unified space network. We also demonstrate the usefulness of a modular simulation framework as a low-cost but powerful tool for evaluating the performance of protocols and architectures in this environment.
  • Thumbnail Image
    Item
    Profile Based Topology Control and Routing in Wireless Optical Networks
    (2004-05-04) Kashyap, Abhishek; Shayman, Mark A; Electrical Engineering
    The problem of topology control and routing of bandwidth-guaranteed flows over wireless optical backbone networks is addressed. The input is a potential topology and a traffic profile. The constraints are that of limited interfaces at each node and the limited link bandwidth, and the objective is to maximize the throughput. The problem turns out to be NP-Hard. A new framework for integrated topology control and routing is proposed. A simple heuristic is proposed, and efficient rollout algorithms are proposed which enhance the heuristic. The routing problem is formulated as a multi-commodity flow problem, and is used to enhance the rollout algorithms to achieve a higher throughput. Another set of heuristics is proposed which use matching theory and multi-commodity flow formulation of routing to achieve the desired results. We enhance the heuristics to provide fairness to the ingress-egress pairs in terms of how much traffic we route for each of them.