стр. 79 |

An important вЂњforwardвЂќ problem in graph theory (networks) is that of finding shortest

paths (routes) between one or more pairs of vertices (nodes) in a graph. A shortest path is

a path that is better than all other paths available between the same source and destination

pairs. A path is considered better if it is optimized on some predetermined weight, such as

the sum of costs of edges that form the path. There are various algorithms to solve the

shortest-path problem, such as those proposed by Dijkstra [20], Bellman [21], Ford [22],

and Moore [23].

In the inverse shortest-path (ISP) problem, we are given a weighted graph and a set of

paths. The task is to modify the edge weights as little as possible such that the given paths

become optimal paths between the corresponding source and destination.

For example, consider the graph in Figure 15.2 with the edge weights equal to one, and

the path P1,7 = 1, 2, 3, 4, 6, 7 between source node 1 and destination node 7 as optimal.

If all edge weights remain one, P1,7 cannot be an optimal path, as a path 1, 2, 5, 6, 7 of

length four exists. In order to make P1,7 optimal, we must modify edge weights. It can be

easily seen that by setting the weights of edges of (2,5) and (5, 6) each to 1.5, the given

path becomes optimal. (Note that the solution is not unique in this case.)

More formally, the inverse shortest-path problem takes, as input, a weighted, undirect-

ed graph G = (V, E, W) and a set P = {Ps,d} of paths in the graph between certain (but not

necessarily all) pairs s and d of nodes. The task is to find w , the modified weights of the

edges, such that

min || w вЂ“ w ||

Each given path in P arises as a minimum weight path between its endpoints.

We consider the use of the 1 norm, that is, the absolute value, in the objective function.

The inverse shortest-path problem was first studied in detail by Burton [24]. He pro-

posed various methods to solve the inverse shortest-path problem. One method introduces

the concept of an island to characterize the violation of the shortest-path constraint by the

given optimal paths. Then it uses the method of Goldfarb et al. [25] to solve the resulting

quadratic programming formulation.

We use an approach similar to the one presented in [26] to solve our inverse shortest-

path problem. This approach formulates the problem as a linear program. We then use

the interactive optimizer software CPLEX [27] to solve the resulting linear program-

ming problem. Since the inverse shortest-path problem that occurs in our work has the

characteristic that w w, we can ignore the absolute value function in the objective

function.

3 4

6

2 7

1

5

Figure 15.2. Instance of inverse shortest-path problem.

417

15.3 CHARACTERIZING INTERACTION USING INVERSE OPTIMIZATION

The linear programming [28] formulation of our inverse shortest paths problem is:

Objective function:

min (w i,j вЂ“ wi,j) (15.3)

(i,j) E

Constraints:

Si,j 0 i, j (15.4)

w i, j wi, j (i, j) E (15.5)

Si,k + w k, j Si, j i, j, k; (k, j) E (15.6)

P

wu,u Si, j i, j; Pi, j (15.7)

(u,u ) Pi, j

Since the task is to modify the edge weights as little as possible, we need to minimize

the difference between the old edge weights (wi,j) and the new edge weights (w i,j). This is

indicated by the objective function [Equation (15.3)]. All the weights of edges are positive

resulting in shortest paths (Si,j) of positive length. This constraint is reflected by Equation

(15.4). In our work, the modified edge weights are always greater than the original values,

as shown in Equation (15.5). The cost of the shortest path between a source s and a desti-

nation d is less than or equal to the sum of the cost of the shortest path between s, a neigh-

bor of d, and the cost of the edge between this neighbor and d. This principle of path opti-

mality is captured in Equation (15.6). The Equation (15.7) reflects the fact that the given

optimal paths have a cost less than the shortest path between the same vertices.

Note that we are not directly interested in computing the value of the modified link

weights. We are instead interested in computing the values of and in the modified link

weights. From Equation (15.1), we see that the modified link weights are a linear function

of and . Note that the delay and the loss rate parameters of this equation are not vari-

ables. Their values are computed through simulation. By substituting the modified link

weights (w i, j) as defined in Equation (15.1), we obtain a new linear programming formu-

lation that has and as the variables:

Objective function:

min (w i, j вЂ“ wi, j)

(i,j) E

= min (1 + В· di,j + В· i, j) вЂ“1

(i,j) E

= ( В· di,j + В· i, j) (15.8)

(i,j) E

Constraints:

Si, j 1 i, j (15.9)

0 (15.10)

418 MODELING CROSS-LAYER INTERACTION USING INVERSE OPTIMIZATION

0 (15.11)

Si,k + 1 + В· di, j + В· Si, j i, j, k; (k, j) E (15.12)

i, j

(1 + В· du,u + В· ) Si, j (15.13)

u,u

(u,u ) P

We now describe our simulation study and demonstrate that the solutions obtained for

this linear programming formulation are compatible with observations in the simulated

network.

15.4 SIMULATION STUDY

We describe how we set up the experiments in our simulation study by describing in detail

one scenario. Then, we show the results of the study and interpret the resulting values of

and for the link metrics.

15.4.1 Simulation Environment

For this work, we use ns-2 (version ns-2.1b8) [17], a discrete-event simulator developed at

Lawrence Berkeley National Laboratory. The wireless extensions added to ns-2, which in-

clude support for MANETs, were implemented by the Monarch Project at CMU [29].

In order to isolate the effect of congestion mechanisms on routing, we consider ten

manually generated static network topologies. Each network contains 30 nodes in a 500 Г—

500 m2 area. Each node in the network has omnidirectional transmission range of 100 m.

Two types of traffic are introduced into the network. One type is established between a

source and destination and is used to observe the effects of congestion on routing, and the

other type is used to create the congestion itself. Congestion is introduced by strategically

injecting traffic between node pairs with the aim of creating an interference with potential

routes taken by traffic between a source and destination. The traffic between a source and

destination is less aggressive so that it does not create congestion in the network by itself.

For our simulations, TCP traffic is used between a source and destination. To create

different levels of congestion in the links of the network, we use ten traffic patterns (in-

cluding both UDP with CBR, and TCP traffic) for the traffic between the other nodes. In

total, we run 10 Г— 2 Г— 10 = 200 simulations, with ten static topologies, two kinds of traffic

between a source and destination, and ten traffic patterns for the other nodes.

Each simulation is run for 50 seconds of real time. The traffic in the simulation starts

randomly between 0.5 s and 1.0 s and continues until the end of the simulation. All of the

nodes in the network are configured with a drop-tail priority interface queue with a buffer

length of 50, DSR as the routing protocol, and IEEE 802.11 as the MAC protocol.

The source in the network traces its route cache periodically with a time interval of 0.1

s. The MAC trace and routing trace are enabled on all nodes to enable calculation of the

average packet delay and loss rate across each link.

15.4.2 Example Scenario

One of the ten static topologies used is a 5 Г— 6 grid of nodes, as shown in Figure 15.3. The

source and destination nodes are nodes 1 and 22, respectively. The traffic flowing between

them is continuous TCP/Reno traffic with a window size of 32 and a packet size of 64

419

15.4 SIMULATION STUDY

4

2

1 5

3 6

s

8 9 10 12

11

7

15

14 16

13 17 18

19 20 21 23

22 24

d

25 26 29 30

27 28

Figure 15.3. Static 5 Г— 6 grid network topology. s and d denote the source and destination nodes.

Traffic between the three indicated pairs of nodes is used to induce congestion.

bytes. To induce congestion in the network, CBR traffic over UDP is introduced between

node pairs 9 and 19, 10 and 26, and 11 and 27, with a packet arrival interval time of 0.006

s, 0.006 s, and 0.1 s, respectively, to create dynamic levels of congestion. The packet size

of all of the CBR traffic is 64 bytes.

15.4.3 The Route Cache Trace

The route cache trace file at the source node contains entries consisting of a timestamp

followed by routes from the primary and secondary route cache at that time. In DSR, the

primary route cache contains the routes found using the route-discovery mechanism. The

secondary route cache contains the routes learned from promiscuous listening. When a

packet is sent to a destination, both the primary and the secondary cache entries are

searched for the minimum hop-count path. If the route found is from the secondary cache,

it is promoted to the primary cache.

The route cache trace file is processed to produce a sequence of the paths observed to

route packets for the duration of the simulation. Figure 15.4 shows the length of each path

in the sequence for the duration of the simulation. In this run, the length of the shortest

path in the cache varies between six and eight. From time to time, the cache is empty, in-

dicated by a path of length zero. This may happen when a route error purges routes in the

cache due to a link failure, or when the cache entries time out.

The figure shows that, for most of the time in the simulation, the traffic between the

source and destination follows a path of length eight. This corresponds to the route 1, 2,

3, 4, 5, 11, 17, 23, 22 . The paths of length six intersect the links on which congestion is

being induced, hence DSR avoids using the shorter paths and instead uses the longer path

having lower average packet delay and loss rates.

15.4.4 Computing the Packet Delay and Loss Rate

In order to compute the delay and loss rate for each link in the network, the MAC and

routing trace entries are analyzed. Data packets (i.e., TCP, CBR), ARP packets, and DSR

420 MODELING CROSS-LAYER INTERACTION USING INVERSE OPTIMIZATION

8

7

6

5

Path Hop Count

4

3

2

1

0

0 5 10 15 20 25 30 35 40 45 50

Time

Figure 15.4. Length of routes in a route cache trace.

стр. 79 |