Effective Delay Control for Online Network Coding
Joao Barros (University of Porto, PT); Rui Costa (Universidade do Porto / Instituto de Telecomunicações, PT); Daniele Munaretto (DoCoMo Euro-Labs, DE); Joerg Widmer (DoCoMo Euro-Labs, DE)
This talk tries to merge ARQ with network coding. The key idea is that a packet is “seen” if it only depends on XORs with future packets. The delay analysis is based then on analyzing the chains of dependent packets induced by erasures. This paper looks at the problem of multicast. Here the issue is managing the delays to multiple receivers and assessing which receiver is the “leader” and how the leader switches over time. For random erasures (different for each receiver) this means we are doing a biased random walk whose location shows who the leader is. A coding strategy is trying to control this random walk, and a strategy is proposed to maintain a “leader” by sending the XOR of the last unseen packet of all users when the leader loses a packet.

The Capacity Allocation Paradox
Asaf Baron (Technion – Israel Institute of Technology, IL); Isaac Keslassy (Technion, IL); Ran Ginosar (Technion, IL)
This talk was about a simple example of a network in which adding capacity can make a stable network unstable. To me it seemed to be because of the particular model adopted for the network, namely that if a link of capacity is available, then the transmitter will operate at rate . The simple example of the paradox is a 2-user multiaccess link. Suppose we have arrival process with rate 1 arriving at two users which have outgoing links of capacity 1 to a shared queue. This queue has output capacity 2, so the whole network is stable. However, if one user gets a capacity 2 link to the queue, then their traffic can hog the output link and cause increasing delay to the second user. The paradox was motivated by networks on a chip, which seem to be an interesting source of new problems with different emphases than traditional networking problems.

Power-Aware Speed Scaling In Processor Sharing Systems
Adam Wierman (California Institute of Technology, US); Lachlan Andrew (Swinburne University of Technology, AU); Kevin Tang (Cornell University, US)
This talk was about assigning speeds to processing jobs in a queue — if you do a job faster it takes more power but reduces delay. There are different ways of assigning speeds, either a fixed speed for all jobs (static), a square-wave for speed vs. time (gated static), or some arbitrary curve (dynamic). The metric they choose to look at it a sort of regularized energy , where . For a large number of jobs they get a kind of limiting form for the optimal speed and show that a gated static policy performs within a factor of 2 of the optimal dynamic, which is verified by simulation. In general we may not know the arrival process and so choosing the duty cycle for a gated static policy may be hard a priori. In this case a dynamic strategy may be much better to handle model variability. This was one of those problems I had never thought about before and I thought the results were pretty cute.