Faculty of Engineering and Natural Sciences
Weak State Routing in Large Scale Dynamic Networks
Utku Günay Acer
Electrical, Computer and Systems Engineering Department
Rensselaer Polytechnic Institute
Random walks and related Markov Chain Monte Carlo method are predominant in many areas of Computer Science, Mathematics, Engineering, Physics, Biology and Economics. Random walks is a key algorithmic ingredient with highly sophisticated and profound impact in algorithms and complexity theory. This talk will provide an overview our efforts on random walk based routing in dynamic networks. In particular, the talk will present a routing mechanism, Weak State Routing (WSR). WSR's novelty is that it uses random directional walks biased occasionally by weak indirection state information in intermediate nodes. The indirection state information is weak, i.e. interpreted not as absolute truth, but as probabilistic hints. Nodes only have partial information about the region a destination node is likely to be. This method allows us to aggregate information about a number of remote locations in a geographic region. In other words, the state information maps a set-of-IDs to a geographical region. The intermediate nodes receiving the random walk use a method similar to longest-prefix-match in order to prioritize their mappings to decide how to bias and forward the random walk. WSR displays good rare-object recall with scalability properties similar to structured DHTs, albeit with more tolerance to dynamism and without constraining the degree distribution of the underlying network. Simulations demonstrate that the protocol achieves high delivery ratio with scalable overhead and stored states at the cost of increased path length.
Bio: Utku is a graduate student pursuing his Ph.D. degree in the Electrical, Computer and Systems Engineering Department of Rensselaer Polytechnic Institute (RPI). He received his B.S. degree from the Telecommunications program of Sabancı University in 2004. His research interests involve variable topology networks with an emphasis on routing in large scale ad-hoc and disruption tolerant networks.
August 20, 2007, 14:00, FENS G032