Quarterly Technical Report, January 2001
- Analysis of strong adversary models: We continue to investigate an adversary that
can fail and recover edges in an arbitrary manner, in contrast to
traditional adversary models which leave the network stable for time
long enough for the protocols to accomplish global communication.
- New routing and dissemination protocols: We devised initial routing
protocols that accomplish the task of routing facing the above strong
adversary model. Our protocols operate without using the concept of
a global path, which is standard in the common "weak adversary" models.
Moreover, the operation of these protocols is based solely on locally
available knowledge, eliminating the need to build a global picture of
the network state.
- New replication protocol: We have developed a general replication engine
that allows consistent ordering of actions in a network that is prone to
partitions and crashes.
The main idea has several instances of the engine (several tens) strategically
positioned in the network. The replicas maintain consistent state and recover
from a wide range of possible faults.
We are now in the process of connecting our engine with the Postgress database software.
We have built some of the infrastructure that will allow us to test the
replication engine, inducing faults into practical network settings.
Currently, our tests are still configned to our lab.
- Overlay networks architecture: We started developing the basic building
blocks for our overlay networks architecture. The first step was to develop
Hop - a link level modified selective-repeat protocol that is TCP-fair, uses less CPU, and allows us full control over the forwarding of messages on
the overlay network.
We designed two alternative global flow control schemes. The first scheme is
a cost benefit approach to buffer utilization in the overlay network routers. The second Scheme is a cost benefit approach to capacity utilization of the
overlay links. We have implemented the buffer utilization cost-benefit scheme in the ns2 simulation toolkit and in the Spread group communication system. Preliminary results are promissing.
It seems that keeping track of buffers is more successful compared with keeping track of link utilization since the link utilization is very hard to measure on the overlay network, it changes rapidly, and hard to assess.
Plans for Next Quarter:
- Network level resiliency: We plan to analyze specific techniques
for single-source single-destination routing, and develop efficient
routing methods for the weak adversary model. We expect that the final
protocol will achieve performance comparable to algoritms that operate
with global knowledge of current and future adversarial behavior.
- 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 Postgress database.
- Cost benefit decision making: We have developed a cost
benefit framework to support global flow control on our overlay network
architecture. A report about this work will appear shortly.
We plan to investigate extending the cost benefit framework to support
overlay network routing, but this will take some time to mature.
- Overlay network infrastructure: We have completed the first global flow
control mechanisms in our overlay network architecture, and are now looking to complete a basic congestion control for Hop. The combination of global flow control and "local" - link level - congestion control will result in a complete practcial method. Currently we maintain fair link level congestion control using TCP/IP.
Questions or comments to:
webmaster (at) dsn.jhu.edu
TEL: (410) 516-5562
FAX: (410) 516-6134
Distributed Systems and Networks Lab|
Computer Science Department
Johns Hopkins University
3400 N. Charles Street
Baltimore, MD 21218-2686