24 August 2012 in Bell Labs Technical Journal
DMME is a distributed architecture that implements mobility management for next-generation cellular systems. It has been designed to serve as a scalable and cost-effective drop-in replacement for the Long Term Evolution (LTE) mobility management enti...
9 December 2011 in IEEE Transactions on Vehicular Technology
WiFi-enabled buses and stops may form the backbone of a metropolitan delay-tolerant network, which exploits nearby communications, temporary storage at stops, and predictable bus mobility to deliver non-real-time information. This paper studies the routing problem in such a network. Assuming that the bus schedule is known, we maximize the delivery probability by a given deadline for each packet. Our approach takes the randomness into account, which stems from road traffic conditions, passengers boarding and alighting, and other factors that affect bus mobility. In this sense, this paper is one of the first to tackle quasi-deterministic mobility scenarios. We propose a simple stochastic model for bus arrivals at stops, supported by a study of real-life traces collected in a large urban network. A succinct graph representation of this model allows us to devise an optimal (under our model) single-copy routing algorithm and then extend it to cases where several copies of the same data are permitted. Through an extensive simulation study, we compare the optimal routing algorithm with three other approaches: 1) minimizing the expected traversal time over our graph; 2) maximizing the delivery probability over an infinite time-horizon; and 3) a recently proposed heuristic based on bus frequencies. We show that our optimal algorithm shows the best performance, but it essentially reduces to minimizing the expected traversal time. When transmissions frequently fail (more than half of the times), the algorithm behaves similarly to a heuristic that maximizes the delivery probability over an infinite time horizon. For reliable transmissions and values of deadlines close to the expected delivery time, the multicopy extension requires only ten copies to almost reach the performance of the costly flooding approach.
15 March 2010 in IEEE/ACM Transactions on Networking
Forwarding decisions in routing protocols rely on information about the destination nodes provided by routing table states. When paths to a destination change, corresponding states become invalid and need to be refreshed with control messages for resilient routing. In large and highly dynamic networks, this overhead can crowd out the capacity for data traffic. For such networks, we propose the concept of weak state, which is interpreted as a probabilistic hint, not as absolute truth. Weak state can remain valid without explicit messages by systematically reducing the confidence in its accuracy. Weak State Routing (WSR) is a novel routing protocol that uses weak state along with random directional walks for forwarding packets. When a packet reaches a node that contains a weak state about the destination with higher confidence than that held by the packet, the walk direction is biased. The packet reaches the destination via a sequence of directional walks, punctuated by biasing decisions. WSR also uses random directional walks for disseminating routing state and provides mechanisms for aggregating weak state. Our simulation results show that WSR offers a very high packet delivery ratio ( ≥ 98%). Control traffic overhead scales as O(N), and the state complexity is Θ(N3/2), where N is the number of nodes. Packets follow longer paths compared to prior protocols (OLSR , GLS-GPSR , ), but the average path length is asymptotically efficient and scales as O(√N). Despite longer paths, WSR's end-to-end packet delivery delay is much smaller due to the dramatic reduction in protocol overhead.