ITA Workshop : networks

There were some talks on dynamic spectrum access as well as waterfilling and other resource allocation problems.

  • Robust routing for dynamic ad hoc wireless networks based on embeddings (D. Tschopp, EPFL, S.N. Diggavi, EPFL and M. Grossglauser, EPFL)

    In fading, multiple unicast networks with mobility and point-to-point links, how can we do route discovery withi limited control overhead? This is a question of topology versus geometry and so they use a graph embedding of the communication graph (taking fading into account) into Rn to minimize the worst-case stretch. By using beacons to coordinate partial graph distances they can decentralize the approach a bit.

  • Coding achieves the optimal delay-capacity trade-off in mobile ad hoc networks (Lei Ying, Sichao Yang and R. Srikant, University of Illinois at Urbana-Champaign)

    For networks in which packets have a hard delay deadline, it’s bad news if a packet just dies onces its deadline expires — you might hope to code over packets so that if a packet dies from delay its contents can be recovered from other packets that made it in time (writing this makes it sound like Watership Down). This work tries to look at a mobility model in which nodes choose a fresh new location every time slot and uses coding across packets to help maximize a link rate.

  • On the throughput-region of a random wireless ad hoc network with geographic routing (Sundar Subramanian, Sanjay Shakkottai, University of Texas at Austin, Piyush Gupta, Bell Labs)

    Geographic routing is bad for network congestion and doesn’t deal well with holes in the networks (although there are hacks for this). By splitting a route into multiple paths, the authors can bound away the congestions. To deal with holes, you can erasure-code across the routes and drop a packet if you hit a hole. These two algorithms are shown to be order-optimal up to log factors in the network size.

  • On the wireless communication architecture for consensus problems (Anna Scaglione, Cornell)

    This work tried to incorporate quantization error into gossip algorithms as well as other physical-layer considerations. I wasn’t able to parse out the results (the talk was notation-heavy), but I suppose I will get to see the paper soon.

  • The law second class customers obey (James Martin, Oxford University, Balaji Prabhakar, Stanford University)

    The best thing about this talk was that it was given on a whiteboard (no slides) and was one of the clearest talks I went to at the whole workshop. Maybe technology is getting in the way. Suppose that we have an exponential service time queue with two Poisson arrival processes (first and second class customers). The first class customers queue up as if the second class customers were not there. Clearly the departure process for the first class customers is also Poisson. What about the second class customers? They use Weber’s result on the
    interchangeability of exponential-server queues to get an alternate derivation of the departure law.

  • On the broadcast capacity of wireless networks (Birsen Sirkeci-Mergen and Michael Gastpar, UC Berkeley)

    Suppose we have a central broadcaster in a network that wants to flood one message across all the nodes. This paper addresses how do to this for dense and extended networks, under iid and “spatially continuous” fading. For dense networks a two-phase protocol involving cooperation works. For an extended network, a cooperative multistage broadcase protocol is proposed. The key is that multihop protocols perform very badly on the broadcast problem and cooperative protocols are needed to get reasonable results.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.