. 79
( 87 .)


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

3 4
2 7

Figure 15.2. Instance of inverse shortest-path problem.

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


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)

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


Si, j 1 i, j (15.9)

0 (15.10)

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 ) 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


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

1 5
3 6

8 9 10 12

14 16
13 17 18

19 20 21 23
22 24

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




Path Hop Count





0 5 10 15 20 25 30 35 40 45 50

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


. 79
( 87 .)