Opportunistic Scheduling in Bus and Kiosk Networks

This project deals with the problem of scheduling bundles to and from kiosks in bus-and-kiosk networks. A first statement of the problem and a simplified solution can be found in [1]. This page has a more refined statement of the problem.

The setting

The setting of the problem is a bus-and-kiosk network. In such a network, kiosks use buses to communicate with the Internet. Buses opportunistically transfer data to and from the kiosks and 'Internet gateways' using WiFi. Buses run according to a bus schedule, which defines arrivals and departures at each kiosk and gateway. In general, a bus route may go past multiple kiosks and gateways. Symmetrically, kiosks and gateways may be served by multiple bus routes. This opens up the possibility of using a kiosk or gateway as a relay to transfer data from one bus to another, even if they do not meet each other directly (a similar problem is being explored by the DieselNet project at UMass. Amherst).

Some facts

During each connection opportunity, it is possible to tranfer at least 20MB of data, and perhaps even more, depending on the bus speed, the antenna configuration, the access point power, and the distance between a bus stop and a kiosk. Moreover, a bus AP can easily hold 40 GB of data. So, to a first approximation, we can think of the bus's data holding and information transfer capacity as being infinite.

In contrast, it turns out that the bandwidth at a gateway is a bottleneck resource. Gateways are connected to the internet using a dialup or DSL link. Such links transfer about 100kbps, or about 1GB/day. So, a bus that accidentally (or naively) dumps all 40 GB of data on a single gateway is going to create 40 days worth of queueing delay. Clearly, in order to keep delays to reasonable values, it is necessary to keep the gateway queues short.

A symmetric problem is encountered at a 'proxy' that relays data from the Internet to the gateways. The proxy can potentially choose among a number of gateways, each of which can reach a given kiosk. If the 'wrong' gateway is chosen, then there can be a huge amount of queueing delay on the link from the proxy to the gateway.

To sum up, given typical configurations and rates, we believe that the capacity of the bus network is fairly high, and the bottleneck resources are the links from the proxy to the gateways. We should try to use these links are efficiently as possible, even if this causes other resources to be wasted.

Data transfer in the kiosk to proxy direction

Given the discussion above, data transfer in this direction is easy. A kiosk floods bundles to all buses that it encounters, which flood it to all kiosks and gateways. Of course, this causes duplicates to arrive at gateways and kiosks. When a gateway gets a potentially duplicate bundle, it contacts the proxy and checks if the bundle has already been transmitted to the proxy by some other gateway. If so, the gateway drops the bundle; otherwise, it forwards it to the proxy. This solution is easy to implement. Moreover, we can enhance it to limit the scope of flooding (say with a hop count), to balance redundancy and worst-case delay.

The Proxy to Kiosk direction

Things are far more complex in this direction. Essentially, the proxy has to choose one or more gateways to balance three competing objectives:

• the expected delay of a bundle if it is sent on this gateway
• the number of gateways that have to be chosen in order to achieve sufficient reliability
• making the allocation of the bottleneck bandwidth as fair as possible

This makes the problem complex!

A formal statement of the problem

We consider only the proxy-to-kiosk direction. Let the proxy communicate to one of m gateways, which talk to one of n kiosks. For simplicity, we model the path from a gateway to a kiosk, which could be more than one hop, as a single virtual link. We can therefore represent this by a bipartite graph, where the weight on edge ij corresponds to the delay in going from the ith gateway to the jth kiosk at time t (i.e this is a temporal bipartite graph). The time-dependant Dijkstra algorithm (see Jain and Fall's paper in Sigcomm 2004) allows us to compute the weight on this link at any given time t.

We associate each kiosk with a virtual queue at the proxy. The proxy selects head-of-line bundles from these queues and assigns them to a link from the proxy to one of the m gateways. Specifically, every time the link from the proxy to one of the gateways is free, the proxy uses a decision process to choose one of the head-of-line bundles and assign it to this link. Our interest is in designing a decision process such that:

1. The overall delay (i.e queueing + transfer delay) of the first bundle (of a set of replicas) is minimized
2. The probability that at least one copy of a bundle is delivered is maximized
3. The allocation of bottleneck bandwidths to the kiosks is max-min (or proportional) fair

Some complications

The problem above has four additional significant complications.

1. We do not know the schedules precisely. Buses may come a little bit earlier or later than scheduled.
2. We do not know how reliable buses are, or, for that matter, how to even quantify the reliability of a bus.
3. Buses and routes are not mapped one-one. Many buses may run on the same route. Buses may run on different routes on different days, and in fact, may serve more than one route the same day.
4. Buffers in the bus and the kiosks are not infinite.
5. Virtual links may represent non-disjoint paths. Hence, if a real link goes down (i.e due to bus failure), more than one virtual link may fail

Given these complications, we believe that the opportunistic scheduling problem is bothh hard, and yet very practical in its applications. Please feel free to contact us by email if you would like to help us in solving it!

[1] S. Guo, M. Ghaderi, A. Seth, S.Keshav,Opportunistic Scheduling in Ferry-Based Networks  (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/06/wnept.pdf),Proc. WNEPT 2006, August 2006.