Obstacle Avoidance Algorithms in Wireless Sensor Networks
- PDF / 2,937,598 Bytes
- 25 Pages / 547.087 x 737.008 pts Page_size
- 67 Downloads / 201 Views
O
O
Oblivious Routing 2002; Räcke N IKHIL BANSAL IBM Research, IBM, Yorktown Heights, NY, USA Keywords and Synonyms Fixed path routing Problem Definition Consider a communication network, for example, the network of cities across the country connected by communication links. There are several sender-receiver pairs on this network that wish to communicate by sending traffic across the network. The problem deals with routing all the traffic across the network such that no link in the network is overly congested. That is, no link in the network should carry too much traffic relative to its capacity. The obliviousness refers to the requirement that the routes in the network must be designed without the knowledge of the actual traffic demands that arise in the network, i. e. the route for every sender-receiver pair stays fixed irrespective of how much traffic any pair chooses to send. Designing a good oblivious routing strategy is useful since it ensures that the network is robust to changes in the traffic pattern. Notations Let G = (V; E) be an undirected graph with non-negative capacities c(e) on edges e 2 E. Suppose there are k sourcedestination pairs (s i ; t i ) for i = 1; : : : ; k and let d i denote the amount of flow (or demand) that pair i wishes to send from si to ti . Given a routing of these flows on G, the congestion of an edge e is defined as u(e)/c(e), the ratio of the total flow crossing edge e divided by its capacity. The congestion of the overall routing is defined as the maximum congestion over all edges. The congestion minimization problem is to find the routing that minimizes the maximum congestion. Observe that specifying a flow from si
to ti is equivalent to finding a probability distribution (not necessarily unique) on a collection of paths from si to ti . The congestion minimization problem can be studied in many settings. In the offline setting, the instance of the flow problem is provided in advance and the goal is to find the optimum routing. In the on line setting, the demands arrive in an arbitrary adversarial order and a flow must be specified for a demand immediately upon arrival; this flow is fixed forever and cannot be rerouted later when new demands arrive. Several distributed approaches have also been studied where each pair routes its flow in a distributed manner based on some global information such as the current congestion on the edges. In this note, the oblivious setting is considered. Here a routing scheme is specified for each pair of vertices in advance without any knowledge of which demands will actually arrive. Note that an algorithm in the oblivious setting is severely restricted. In particular, if di units of demand arrive for pair (s i ; t i ), the algorithm must necessarily route this demand according to the pre-specified paths irrespective of the other demands or any other information such as congestion of other edges. Thus given a network graph G, the oblivious flows need to be computed just once. After this is done, the job of the routing algorithm is trivial; whenever a demand arrives, it simply
Data Loading...
