BGP-ANYCAST SIMULATIONS
PEOPLE
Faculty:
  • Dr. George Riley

  • Current Students:
  • Veena Raghavan

  • Past participants:
  • Talal M. Jaafar

  • Sunitha Beeram

  • Xenofontas Dimitropoulos

  • LATEST NEWS
    03/01/06:
    CAIDA workshop to discuss Anycast simulations. For slides presenting early work on Anycast simulations
    [Click Here]
    About BGP-Anycast


    DNS is critical for the survival of the Internet. DNS root server operators are using Anycast to ensure availability, load balancing and to reduce latency perceived by the end user. The Anycast mechanism used is IP level Anycasting, which is naturally supported by the existing BGP infrastructure.

    In this project, we use simulations to study the effectiveness of using Anycast for DNS root servers. We are using GTNetS BGP++ implementation to achieve a fine-grained BGP simulation. We employ topology data available from RouteViews project and from CAIDA data sets to build realistic topologies to simulate the supporting Internet backbone topology. We seek to answer questions related to the impact of BGP on Anycast deployment and possible effects of Anycast deployment on BGP. Some of the metrics of interest are:

    * BGP Convergence
    * BGP Churn
    * End-to-End User Latency
    * Anycast Load Balancing


    This project is funded by CAIDA.


    Experimental Setup



    In our experiments, we aim to simulate a realistic AS level topology of the Internet. The AS level topology is derived from CAIDA data sets and the RouteViews project. We use BGP++ configuration generator to convert the inferred AS relationships to configuration files that the simulation can use.

    In the simulations, we have represented each AS as a single node/ BGP speakers. The interconnecting links as inferred from Routeviews have been preserved.

    In our experiments, we are interested in studying the following:
    • Impact of BGP idiosyncrasies on Anycast setup. For example, study the impact of BGP Path Exploration problem and Flap Dampening on Anycast stability.

    • Impact of Anycast on BGP. For example, study impact of large number of Global Anycast nodes on BGP stability.

    • Placement of new Anycast nodes that can minimize downtime and BGP churn in case of network failures.

    Failures:

    Currently, we simulate 2 kinds of failures.
    • Explicit withdraw of Anycast prefix from an advertising AS: This failure would mean that the server is unreachable and hence the prefix is withdrawn by the advertising AS. The Anycast client would switch to a different server in this failure case. Explicit withdraw is expected to have lesser downtime but involves potentially more network churn as a lot of updates can be exchanged.

    • Silent link failure: Link failures could be on any segment of the chosen best AS path. Currently, we restrict the simulated failure to a single failure in the last hop AS link. Silent link failures would rely on BGP holdtime timers to get triggered to be detected. In this failure mode, the client would still communicate with the same server (if it is up) through a different path. Such failures are expected to have a longer donwtime but lesser network churn as fewer updates about the failure are exchanged.


    Setup:

    We divided our experiments into two stages. In the first stage, we used a small topology (44 nodes, Tier-1 ASes) to verify the functionality of our simulator. In the second stage, we used a much larger topology (5476 nodes, Tier-1 & Tier-2 ASes) to deduce realistic results.

    Stage 1:
    We have extracted information about ASes that provide connectivity to the F-root sites. In all, we have 44 ASes and 467 interconnecting links. The F-root AS is AS3557 and the following ASes included in the topology provide service to the F-root in our setup : 6461, 174, 2914, 3549, 3356, 701, 2828, 5511 and 6453. For a GeoPlot visualization of the topology [Click Here].

    Stage 2:
    We have extracted information about ASes that provide connectivity to the F-root, J-root, K-root, and M-root sites. In all, we have 5,476 ASes and 14,468 interconnecting links. We have found in the topology 10 ASes to provide service to the F-root, 6 ASes to provide service to the J-root, 17 ASes to provide service to the K-root, and 4 ASes to provide service to the M-root. We used distributed simulations (16 federates) for this setup.

    Measurement methodology:

    Stage 1:
    The simulation of the topology is started and BGP is allowed to converge. Multiple Anycast servers are started in the ASes which advertise the Anycast prefix. Multiple clients are started at different ASes. The clients send an UDP packet to the server every second, which is timestamped and returned to the client by the server. After convergence, failure is induced into the system using one of the failure modes discussed above. The simulation stops at a pre-determined time. The number of missed client responses gives us a measure of the downtime of the prefix with respect to the particular client.
    Click Here for a discussion of the results obtained with this setup.

    Stage 2:
    The methodology is very similar to that used in stage 1 except to inducing multiple points of failures, and DNS clients sending UDP packets to the root-servers at a realistic rate. In other words, we used the DNS statistics provided by CAIDA data sets to drive our DNS clients.
    We are almost through with our experiments, and we will be posting the results very soon (few weeks).