A Cost Benefit Approach to Fault Tolerant Communication and Information Access

Quarterly Technical Report, April 2001

Progress:

• We have implemented an initial version of gravitational flow technique for routing that can overcome strong adversary model. Our protocols operate without using the concept of a global path, which is standard in the common "weak adversary" models. Roughly, the operation of the gravitational flow protocol is based on the number of unacknowledged packets that were sent in each direction. Packets that reach the destination are acknowledged. Packets that are stuck create "back pressure" so that this link is not used for further packets. As the network connectivity change, pressure points may be released with links coming back up, and free paths may be clogged as links go down.

  We have built a preliminary test for the gravitational flow protocol that sends Mpeg video stream through an overlay network in our lab with controlled link-down and link-up events. This is still work in progress.

• Overlay network infrastructure: We have completed a basic congestion control for the Hop link-level protocol. The basic congestion control was implemented both in the ns2 simulator and in our overlay network implementation. We are still investigating tradeoffs regarding the different mechanisms in terms of our ability to control rate versus window, and in terms of cpu consumption.

• Cost benefit decision making: We have implemented the global flow control, both in ns2 and in our overlay network implementation inside the Spread group communication system. This is based on the Cost Benefit framework. A technical report is now released.

• New replication protocol: We came up with a method to create new replicas and eliminate replicas while the system is operational without compromising consistency and without requiring complete connectivity. This is a work in progress, but when completed, it will allow our cost-benefit algorithms to determine how many replicas to keep in the system and possibly where to situate them.

  Previously, we have developed a general replication engine that allows consistent ordering of actions in a network that is prone to partitions and crashes. We planned to complete the integration of our engine with the Postgres database software, but that turned out to be more complicated than we thought. We continue to work on this.

Papers:

• Flow Control for Many-to-Many Multicast: A Cost-Benefit Approach

  Technical Report CNDS-2001-1
  

  Yair Amir, Baruch Awerbuch Claudiu Danilov, Jonathan Stanton,

  We present a protocol that is analytically grounded, yet also achieves real world goals, such as simplicity, fairness and minimal resource usage. We base our flow control protocol on the Cost-Benefit algorithmic framework for resource management. We base decisions on the "opportunity" costs of network resources, comparing the cost of each individual resource to the benefit it provides. As opposed to existing window-based flow control schemes, we avoid end-to-end feedback by basing decisions on the state of the links between participating nodes. This produces control traffic proportional only to the number of overlay network links and independent of the number of groups.

Plans for Next Quarter:

• Network level resiliency: We plan to evaluate the performance of the gravitational flow implementation and contrast it with regular algorithms in "well-behaved" environments to assess the overhead.

• Data level resiliency: We plan to continue the validation of our general replication engine. We intend to use the CAIRN network to experiment with high latency wide area settings. Next, we are in the midst of integrating our replication engine to the Postgres database. We did not make much progress in this task this period and hope to do better this coming quarter.

• Overlay network infrastructure: We will clean our initial implementation for congestion control and flow control to make it more scalable and flexible. We expect our re-implementation in ns2 to be much cleaner this time around since we know exactly where we are going. This will potentially enable other researchers to use our new framework when developing their own protocols.

  We will complete our evaluation of the different congestion control schemes and enhance the scalability of our global flow control.

  During the coming period, we plan to release our extentions to ns2 that implement our framework.

• Replication protocol: We hope to finally complete our integration with Postgres.

• Cost benefit decision making: We will start investigating what parameters can be useful in the decision of where and whether to create new replicas in a replicated data(base) system.