Dan Rubenstein's Resilient Routing Research

My work on resilient routing can further be divided into three areas: multipath connections, data persistence in collapsing networks, and distributed debugging:

• Multipath Connections: Unicast communication usually utilizes a single route. Attacking any link or node on the communication path will stop the communication. In [LMR05], we constructed distributed algorithms and protocols to find the best set of paths to achieve a target throughput or to maximize aggregate throughput such that loss of throughput would be minimized under a single link attack. Our distributed solution was also shown to be remarkably robust to multiple link attacks as well.
  
  
  
  • [LMR05] Patrick P. C. Lee, Vishal Misra, and Dan Rubenstein. Distributed algorithms for secure multipath routing. In Proceedings of IEEE Infocom, Miami, FL, March 2005.
  
  
  
• Data Persistence Routing in Collapsing Networks: A collapsing network is a network whose nodes are failing rapidly, perhaps due to an ongoing disaster or rapid loss of power. If a sensor network is collapsing, there is a risk of losing data collected by the network as its waits its turn to be forwarded to the collection points. In [KFMR06], we designed a novel coding technique that we call a growth code, whose distribution changes with time (unlike traditional coding techniques where the code distribution is constant over time). Combined with resilient (pretty much random) routing, we show that growth codes do very well at maximizing the amount of information that can be extracted from a sensor network over time.
  
  
  
  • [KFMR06] Abhinav Kamra, Jon Feldman, Vishal Misra, and Dan Rubenstein. Growth Codes: Maximizing Sensor Network Data Persistence. In Proceedings of ACM Sigcomm, Pisa, Italy, September 2006. A preliminary version is currently available as a Tech Report.
  
  
  
• Distributed Debugging: Strong Detection: Distributed routing protocols generally assume that the distributed components that implement the protocol perform their tasks correctly. Malicious users or simply oversights in design or coding can significantly impede routing performance. Can the presence of a misbehaving node be detected by correctly behaving nodes? Previous work has shown that a node can look at its state for inconsistencies in specific properties (e.g., triangle inequality) to reveal potential problems. However, how does one know if they are checking the right property?

  In [KMR05], we derived the notion of strong detection methods. A method implements strong detection if, given an inconsistency, the method identifies it, or there is no method that can identify it without changing/enhancing the routing protocol and state information collected. In [KMR06], we derived low-complexity strong detection methods for distance-vector, path-vector, and link-state routing protocols, and used them to explore the likelihood of detecting inconsistencies in these various classes of protocols.

  
  
  
  • [KMR05] Raj Kumar Rajendran, Vishal Misra, and Dan Rubenstein. Brief announcement::strong detection of misconfigurations. In Principles of Distributed Computing (PODC), Las Vegas, NV, July 2005.
    
    
  • [KMR06] Raj Kumar Rajendran, Vishal Misra, and Dan Rubenstein. Theoretical bounds on control-plane self-monitoring in routing protocol. Technical report, Columbia University, February 2006.