Abstract:
Advances in wireless vehicular networks present us with opportunities for developing new distributed traffic control algorithms that avoid phenomena such as abrupt phase-transitions. Towards this end, we study the problem of distributed traffic control in a partitioned plane where the movement of all entities (vehicles) within each partition (or cell) is controlled by a single process. We present a distributed traffic control protocol that guarantees minimum separation between vehicles at all times, even when some cell-processes fail by crashing. Once failures cease, the protocol is guaranteed to stabilize and the packets with feasible paths to the target cell make progress towards it. The algorithm relies on two general principles: local geographical routing, and temporary blocking for maintenance of safety. Our proofs use mostly assertional reasoning and may serve as a template for analyzing other distributed traffic control protocols. We also present simulation results which provide estimates of throughput as a function of velocity, safety separation, and path complexity. Further, we present simulation results to estimate throughput as a function of failure and recovery rates.
Reference:
Taylor T. Johnson, Sayan Mitra, Karthik Manamcheri, "Safe and Stabilizing Distributed Cellular Flows", In 30th IEEE International Conference on Distributed Computing Systems (ICDCS 2010), Genoa, Italy, pp. 577–578, 2010, jun.
Bibtex Entry:
@inproceedings{johnson2010icdcs,
author = {Taylor T. Johnson and Sayan Mitra and Karthik Manamcheri},
booktitle = {30th IEEE International Conference on Distributed Computing Systems (<a href="http://icdcs2010.cnit.it/">ICDCS 2010</a>)},
title = {Safe and Stabilizing Distributed Cellular Flows},
year = {2010},
month = jun,
pages = {577--578},
keywords = {},
ISSN = {1063-6927 },
isbn = {978-1-4244-7261-1},
address = {Genoa, Italy},
gsid = {12377696546842138389},
abstract = {Advances in wireless vehicular networks present us with opportunities for developing new distributed traffic control algorithms that avoid phenomena such as abrupt phase-transitions. Towards this end, we study the problem of distributed traffic control in a partitioned plane where the movement of all entities (vehicles) within each partition (or cell) is controlled by a single process. We present a distributed traffic control protocol that guarantees minimum separation between vehicles at all times, even when some cell-processes fail by crashing. Once failures cease, the protocol is guaranteed to stabilize and the packets with feasible paths to the target cell make progress towards it. The algorithm relies on two general principles: local geographical routing, and temporary blocking for maintenance of safety. Our proofs use mostly assertional reasoning and may serve as a template for analyzing other distributed traffic control protocols. We also present simulation results which provide estimates of throughput as a function of velocity, safety separation, and path complexity. Further, we present simulation results to estimate throughput as a function of failure and recovery rates.},
doi = {10.1109/ICDCS.2010.49},
pdf = {http://www.taylortjohnson.com/research/johnson2010icdcs.pdf},
}