Return to Dan's main page

My main research interest has been improving the resilience of network systems. While networks have a long history of being engineered to maximize performance under expected operating conditions where loss, failure and delay occur, these architectures are not prepared to hold up under more extreme conditions that can occur because of a malicious attack or because of some unexpected event, such as a flash crowd, natural disaster, or incorrect implementation of a protocol.

NEW for '07/'08: If I had to quickly summarize my more recent interests, the focus would be on:

• Distributed Debugging [A]: When can a node implementing some distributed routing protocol detect a misconfiguration (misbehaving node) elsewhere in the network by using its own current state? In [A], We devise a method called strong detection that can provably detect any misconfiguration that is detectable within the state information.
  
  
• Accurate Distributive Queries [B]: In [B], we construct a technique, called CountTorrent, that can compute accurate distributive queries (SUM, AVG, COUNT, MAX, MIN) even in networks whose nodes move, join, and leave.
  
  
• SCANs [C]: A Spreadable Connected Autonomic Network (SCAN) is a network whose nodes are mobile, yet constrain their movements in order to maintain connectivity. In [C], we present a distributed algorithm that mobile nodes can implement that only controls their movements when their movements are at risk of disconnecting the network.
  
  
• Robust Economic Theory for ISP Connectivity [D], [E]: Today's ISPs make bilateral agreements that encourage selfish routing strategies and do not enable certain desirable peerings. In [D] and [E], we show that if profit-sharing mechanisms derived from the coalition games concept of Shapley value and its extensions are applied, this will encourage these selfish ISPs who seek to maximize their own profits to con- verge to a Nash equilibrium that maximizes global profitability.
  
  
  
  • [A] Raj Kumar Rajendran, Vishal Misra and Dan Rubenstein, Theoretical Bounds on Control-Plane Self-Monitoring in Routing Protocols, Proceedings of ACM Sigmetrics, San Diego, CA, June, 2007.
    
    
  • [B] Abhinav Kamra, Vishal Misra and Dan Rubenstein, CountTorrent: Ubiquitous Access to Query Aggregates in Dynamic and Mobile Sensor Networks, ACM SenSys, Sydney, Australia, November, 2007.
    
    
  • [C] Joshua Reich, Vishal Misra, Dan Rubenstein and Gil Zussman, Spreadable Connected Autonomic Networks (SCAN), Columbia University, Number CUCS-016-08, 2008.
    
    
  • [D] Richard T.B. Ma, Dah-Ming Chiu, John C.S. Lui, Vishal Misra and Dan Rubenstein, Internet Economics: The use of Shapley value for ISP settlement, Proceedings of 2007 ACM Conference on Emerging network experiment and technology (CoNEXT 2007), Columbia University, New York, December, 2007.
    
    
  • [E] Richard T.B. Ma, Dah-Ming Chiu, John C.S. Lui, Vishal Misra and Dan Rubenstein, Interconnecting Eyeballs to Content: A Shapley Value Perspective on ISP Peering and Settlement, Columbia Electrical Engineering Technical Report, March, 2008.

  Earlier, I focused mainly on P2P and Overlays, some of which dealt with resilience.

  Style of Research
  
  I generally like working on problems that

  • have some (mathematical) modeling component.
  • can be (and often are) easily implemented, deployed, experimented with.
  • have purely distributed solutions. No central points of failure is important for resilience.
  For a small representative set of my publications in resilience of networks, I would recommend [1], [4], [10] (or [16]), and [14] (or [20]).
  There's also the shared-point-of-congestion work from my grad school days
  
  
  

  Specific Network Resilience Topics
  

  • Flash Crowds (initiated Fall 2001) [7], [9], [15], [18], [19]
    Sometimes called the "Slash-Dot Effect", a flash crowd is a sudden jump in demand for a particular piece of content. Traditional client-server systems that delivered content did not do a good job at handling the sudden increase in load. Our research looked at 3 solutions: methods for predicting upcoming flash crowds, peer-to-peer (P2P) protocols that could efficiently exchange the highly sought-after content, and incentive mechanisms for server collectives.
    Read more about our research into flash crowds here.
    
    
  • Distributed Scalable Replica/Task Placement (initiated Fall 2001) [5], [10], [16]
    Content distribution systems increase their resilience and efficiency in delivering content by replicating the content at multiple points in the network. Wireless 802.11 ad-hoc networks can utilize multiple channels to reduce interference among neighbor's competing transmissions. We viewed the challenge of replicated task placement as a non-traditional graph coloring problem, and constructed distributed, self-configuring algorithms that assign colors to nodes such that the coloring is provably within a constant factor of an optimal assignment.
    Read more about our research into distributed scalable replica/task placement here.
    
    
  • Protection from DDoS Attacks (initiated Fall 2001) [6], [13], [14], [17], [20]
    Distributed Denial of Service (DDoS) Attacks are mounted by a malicious user or set of users who seek to block access to a particular target site by sending packets from multiple compromised network locations at the target. Our Secure Overlay Services (SOS) work investigated how to use overlay networks to proactively protect target sites, such as web servers, from direct attack.
    Read more about our research into DDoS Attack Protection here.
    
    
  • Soft State for Resilience (initiated Spring 2003) [12]
    Soft state has long been argued to be an important facet of good network protocol design. While often utilized, the benefits were difficult to explain formally. Prior work that tried to explain the benefits of soft state attempted to motivate its benefit via traditional performance costs, like maximizing throughput and delay. Our work demonstrated that another more important benefit of soft state was that it increased network resilience: instead of optimizing performance under ideal network conditions, soft state mechanisms extended the range of "good" performance across a much broader range of network conditions, including those that would be considered anomalous.
    
    
  • Resilient Routing (initiated Fall 2004) [1], [4], [8], [11]
    The focus of routing is generally to use the minimal resources to get the data from the sources to the desired destinations in minimal time, using the minimal amount of resources. There are two underlying assumptions: nodes used for forwarding are properly implementing their tasks, and network (link and node) failures are infrequent. Our work looks at what can be done when these assumptions no longer hold. Topics covered include distributed allocation across multiple paths, coding and routing for persistence in collapsing networks, and distributed debugging of distributed routing protocols.
    Read more about our research into resilient routing here .
    
    
  • Dealing with P2P Pollution (initiated Spring 2005) [3]
    A recent challenge for peer-to-peer (P2P) networking systems is the advent of polluters who seek to obfuscate access to legitimate content by introducing corrupted copies into the network. Our work models these systems mathematically to quantify, for a variety of pollution and pollution avoidance strategies, the fraction of users with time who can receive legitimate copies of the sought after content.
    
    
  • ALOHA in selfish environments (initiated Spring 2005) [2]
    We have explored how two-state generalizations of the traditional ALOHA MAC-layer protocol will behave in competitive network environments where connections competing for bandwidth over the same wireless medium greedily try to maximize their own additional bandwidth.

  Publications on Network Resilience

  This is a partial list of my publications that includes only those papers that address network resilience in some form. Click here for full publications list.
  
  
  • 2006
    • [1] 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.
      
      
    • [2] Richard T.B. Ma, Vishal Misra, and Dan Rubenstein. Modeling and analysis of generalized slotted-aloha mac protocols in cooperative, competetive and adversarial environments. In Proceedings of IEEE ICDCS, Lisbon, Portugal, July 2006.
      
      
    • [3] Rakesh Kumar, David Yao, Amitabha Bagchi, Keith Ross, and Dan Rubenstein. Fluid modeling of pollution proliferation in p2p networks. In Proceedings of ACM Sigmetrics, St. Malo, France, June 2006.
      
      
    • [4] Raj Kumar Rajendran, Vishal Misra, and Dan Rubenstein. Theoretical bounds on control-plane self-monitoring in routing protocol. Technical report, Columbia University, February 2006.
    
    
    
  • 2005
    • [5] Bong Jun Ko, Jitendra Padhye, Vishal Misra, and Dan Rubenstein. Distributed channel assignment in multi-radio 802.11 mesh networks. Technical report, Columbia University, November 2005.
      
      
    • [6] Angelos Stavrou, Debra L. Cook, William G. Morein, Angelos D. Keromytis, Vishal Misra, and Dan Rubenstein. Websos: An overlay-based system for protecting web servers from denial of service attacks. Journal of Communication Networks, 48(5), August 2005.
      
      
    • [7] Yuliy Baryshnikov, Ed G. Coffman, Guillaume Pierre, Dan Rubenstein, Mark Squillante, and Teddy Yimwadsana. Predictability of web-server traffic congestion. In 10th International Workshop on Web Content Caching and Distribution (WCW 2005), Sophia Antipolis, France, September 2005.
      
      
    • [8] 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.
      
      
    • [9] Dan Rubenstein and Sambit Sahu. Can unstructured p2p protocols survive flash crowds? IEEE/ACM Transactions on Networking, 13(3), June 2005.
      
      
    • [10] Bong-Jun Ko and Dan Rubenstein. A distributed, self-stabilizing protocol for placement of replicated resources in emerging networks. IEEE/ACM Transactions on Networking, 13(3), June 2005.
      
      
    • [11] Patrick P. C. Lee, Vishal Misra, and Dan Rubenstein. Distributed algorithms for secure multipath routing. In Proceedings of IEEE Infocom, Miami, FL, March 2005.
    
    
    
  • 2004
    • [12] John Lui, Vishal Misra, and Dan Rubenstein. On the robustness of soft state protocols. In 12th IEEE International Conference on Network Protocols (ICNP), Berlin, Germany, October 2004.
      
      
    • [13] Angelos Stavrou, John Ioannidis, Angelos D. Keromytis, Vishal Misra, and Dan Rubenstein. A pay- per-use dos protection mechanism for the web. In In Proceedings of the 2nd Applied Cryptography and Network Security (ACNS) Conference, Yellow Mountain, China, June 2004.
      
      
    • [14] Angelos Keromytis, Vishal Misra, and Dan Rubenstein. Sos: An architecture for mitigating ddos attacks. IEEE Journal on Selected Areas in Communications (JSAC), special issue on Service Overlay Networks, 22(1), January 2004.
      
      
    • [15] Angelos Stavrou, Dan Rubenstein, and Sambit Sahu. A lightweight, robust, p2p system to handle flash crowds. IEEE Journal on Selected Areas in Communications (JSAC), special issue on Service Overlay Networks, 22(1), January 2004.
    
    
    
  • 2003
    • [16] Bong-Jun Ko and Dan Rubenstein. A distributed, self-stabilizing protocol for placement of replicated resources in emerging networks. In Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP), Atlanta, GA, November 2003. Best Paper Award Recipient.
      
      
    • [17] William G. Morein, Angelos Stavrou, Debra L. Cook, Angelos D. Keromytis, Vishal Misra, and Dan Rubenstein. Using graphic turing tests to counter automated ddos attacks against web servers. In Proceedings of the 10th ACM International Conference on Computer and Communications Security (CCS), Washington D.C., October 2003.
      
      
    • [18] Daniel Villela and Dan Rubenstein. A queueing analysis of server sharing collectives for content distribution. In Proceedings of the Eleventh IEEE International Workshop on Quality of Service (IWQoS 2003), June 2003.
    
    
    
  • 2002
    • [19] A. Stavrou, D. Rubenstein, and S. Sahu. A Lightweight, Robust P2P System to Handle Flash Crowds. In Proceedings of ICNP'02, Paris, France, November 2002.
      
      
    • [20] Angelos Keromytis, Vishal Misra, and Dan Rubenstein. SOS: Secure overlay services. In Proceedings of ACM Sigcomm, Pittsburgh, PA, September 2002.

  Full publications list

  Return to Dan's main page