Previous Projects

Fast Routing Table Recovery

This work is part of the NSF BBGP project. Our paper is here.

In this study, we propose a scalable mechanism, Fast Routing Table Recovery (FRTR), for detecting and correcting route inconsistencies between neighboring BGP routers. A periodic update approach, used by most routing protocols, is considered infeasible due to the large size of today's global routing table. In FRTR neighboring routers periodically exchange Bloom filter digests of the routing state to detect any potential routing inconsistency. The digests can also facilitate efficient recovery after a BGP session reset. FRTR achieves a low bandwidth overhead by using small digests, and achieves strong consistency by ``salting" the digests with random seeds to overcome Bloom filter's false-positive drawback. Our analysis and simulation results show that, with one round of message exchange, FRTR can detect and recover over 91% of random errors that the current BGP would have missed and the overhead can be as low as 1.3% of a full routing table exchange. With salted digests FRTR can detect all the errors with a probability close to 100% after a few rounds of exchanges.

BGP Routing Stability

This work is part of the DARPA FNIISC project. Our paper is here.

The Internet infrastructure relies on BGP to provide essential routing information. In this study, we examine BGP's behavior during one stressful period, the CodeRed/Nimda attack on September 18, 2001. The attack was correlated with a 30-fold increase in the BGP update messages at a monitoring point which peers with a number of Internet service providers. Our examination of BGP's behavior during the event concludes that BGP exhibited no significant abnormality, and that over 40% of the observed updates can be attributed to the monitoring artifact in current BGP measurement settings. Our analysis, however, does reveal several weak points in both the protocol and its implementation, such as BGP's sensitivity to the transport session reliability, its inability to avoid the global propagation of small local changes, and its certain implementation features whose otherwise benign effects only get amplified under stressful conditions. We also identify areas for improvement in the current network measurement and monitoring effort.

DNS Service Protection

This work is part of the DARPA FNIISC project. Our paper is here .

The Domain Name System (DNS) translates host names into IP addresses for Internet communication. The DNS is vulnerable to a number of potential faults and attacks. In particular, false routing announcements can deny access to the DNS service or redirect DNS queries to a malicious impostor. Due to the hierarchical DNS design, a single fault or attack against the routes to any of the top level DNS servers can disrupt Internet services to millions of users. In this paper we propose a path-filtering approach to protect the routes to the critical top level DNS servers. Our approach exploits the high degree of redundancy in top level DNS servers and also exploits the observation that popular destinations, including top level DNS servers, are well connected via stable routes. Our path-filter restricts the potential top level DNS server route changes to be within a set of established paths. Heuristics derived from routing operations are used to adjust the potential routes over time. We tested our path-filtering design against BGP routing logs and the results show that the design can effectively ensure correct routes to top level DNS servers without impacting DNS service availability.

RSVP Refresh Overhead Reduction

RSVP is a signaling protocol designed by Lixia Zhang for resource reservation. It has been standardized by IETF (RFC 2205) and implemented by major router and host vendors such as Cisco, 3Com, Bay Networks, Microsoft and Sun Microsystems (here is a survey of the implementation status).

RSVP employs a soft-state approach to maintain the reservation states. Routers periodically send refresh messages to neighbors for all of their reservation states, so that they can automatically adapt to changes in routing and reservations. However, people are concerned about the transmission and processing overhead of the refresh messages when there is a large number of states. We believe that the soft-state paradigm is the right choice for RSVP and therefore our approach is to minimize the overhead by using message digests. Instead of sending full refresh messages, routers can send digests (a signature of the reservation states). When a router detects that its digest does not match its neighbor's, it requests the neighbor to send full refresh messages. The neighbor will refresh only the states that have been changed since the last time they had a matched digest. See our paper for more details.

Two-tier Resource Management

Two-tier resource management was proposed by Lixia Zhang, et al. [reference] to provide scalable resource management for the global Internet. Its design follows the two-level routing hierarchy in the current Internet, namely, each administrative domain sets up service agreements with its neighbors and it is allowed to choose any scheme to satisfy internal and external resource requirements. We have done some experiments that showed the promising prospects of this scheme.

QBone Implementation

QBone is the Internet 2 testbed for differentiated services. Its first step is to deploy the Premium Service proposed by Van Jacobson. We participated in the design and implementation of a Bandwidth Broker prototype (click here for more info on the BB working group).


Design of Mobile Adaptive Networks Using Simulation & Agent Technology

This DARPA project is a collaboration effort of three research groups (PCL, NRL, IRL) in our department. The main goal of the project is to develop a simulation package (GlomoSim) for large scale mobile wireless network simulation. GlomoSim modules are written in a C-based simulation language Parsec developed by PCL. I ported TCP in FreeBSD to Parsec and wrote some traffic generators for GlomoSimusing TcpLib.

back to home