. 80
( 87 .)


packets (i.e., RREQ, RREP, RERR) are all taken into account to compute the average de-
lay and loss rate (percentage of packets dropped). See Bikki [2] for detailed trace files.

15.4.5 Solving the Linear Programming Formulation
CPLEX is a software product from ILOG, Inc. [27] that solves linear, mixed-integer, and
quadratic programming problems. We use this software to solve the linear programming
formulation of our ISP problem. For each nonzero time interval in the route cache trace,
the route used, the average packet delay, and the average packet loss rate for all the links
are used as input for the linear program. This program is fed into CPLEX and it produces
an output file that contains values of and for that time interval. To obtain the value for
and for a simulation run, we average the values over the nonzero time intervals in the
route cache trace.
Figures 15.5 and 15.6 show the values of and , respectively, for each of the 200 sim-
ulation runs of our experiment.

15.4.6 Interpretation of and
It is evident from Figures 15.5 and 15.6 that there are three distinct regions of values for
the coefficients. The first region (simulation runs 1 to 40) corresponds to simulations in









0 20 40 60 80 100 120 140 160 180 200
Simulation ID

Figure 15.5. Delay coefficients ( ).

which the two shortest routes between the observed source and destination have the same
length in hop count. The second region (runs 41 to 100) corresponds to simulations with a
one hop count difference between the two shortest routes. Finally, the third region (runs
161 to 200) corresponds to simulations with a two hop count difference between the two
shortest routes. (Note that there may also be other, higher hop count routes present be-
tween the source and destination.)
For the first region, there are some time periods in the route cache trace in which the
difference in the length of the observed path and the next-best path is equal to zero. In this
case, any small values for and satisfy the requirement of Equation (15.1). These val-
ues of and keep the overall average and values for the entire simulation low. For
the simulations in the second region, route trace contains time periods in which the differ-
ence in the length of the observed path and the next-best path is equal to one. Now, in or-
der to satisfy the requirement of Equation (15.1), the inverse shortest-path problem needs
to assign larger values for and , and similarly for the third region of simulations.
Thus, for increasing distance between the shortest hop count path between a source
and destination and the path actually used by the routing protocol, we see increasing coef-
ficients on the congestion parameters in the link metric.
One way that the and values may be used is as follows. Network designers can com-
pute the values of average packet delay and average packet loss rate by the use of targeted








0 20 40 60 80 100 120 140 160 180 200
Simulation ID

Figure 15.6. Packet loss coefficients ( ).

traffic patterns and node configurations. Using the equations in Section 15.3.3, we can ob-
tain threshold values for the delay and loss rate below which DSR uses the weight solely of
hop count when routing the traffic. When the delay and loss rates in the current path exceed
the threshold values, DSR tries to select a longer path with low delay and loss rates.
In certain task-specific MANETs, it may be desirable to have the traffic take a mini-
mum hop count path to minimize the overall traffic delay. In such cases, the above equa-
tion can be used to obtain the maximum fluctuations of the delay and loss rates that would
still satisfy the desired constraint.


The Dynamic Source Routing (DSR) protocol [13, 14] is a reactive protocol that uses
source routing to route traffic in the network. Source routing is a mechanism in which the
source of a packet determines the complete sequence of nodes the packet needs to follow
in order to reach the destination. This sequence of nodes is placed in the packet header, so
that all the intermediate nodes can determine the next hop to which it should forward the
packet directly.

In DSR, each mobile node in the MANET maintains a route cache. This cache is used
to store the source routes learned by the node. When a source node wants to send a packet
to a destination, the source checks its cache to see if it has a source route to that destina-
tion. If a route is found, then the packet is transmitted after inserting the source route into
the packet header. If no route is found for that destination, then the source initiates the
route discovery mechanism. The packet is buffered while the route discovery mechanism
is underway.
A host initiates the route discovery by broadcasting a route request (RREQ) packet.
This packet includes information such as the initiator of this RREQ, the destination that
is the target of this RREQ, and a route sequence list that contains the list of node iden-
tifiers traversed by the route request. It also contains a request identifier (id), set by the
initiator. This is a sequence number that is unique to each route request initiated at this
node. Initially, the route sequence list is set to the source id at the initiator of the route
Each node in the network maintains a list of initiator id, request id pairs from the most
recent route request. All intermediate nodes that receive a RREQ forward it if: (1) the pair
initiator id, request id from the RREQ packet does not match any entry from the list it is
maintaining, and (2) its node id is not already present in the route sequence list of the
The rebroadcast explosion of duplicate route requests is suppressed by discarding a
route request if the node has recently seen another route request belonging to the same
route discovery. By not forwarding a route request when the node id is already present in
the node list, DSR ensures that no loop is present in the route realized by the route discov-
ery mechanism.
When the RREQ reaches the target destination, the route reply (RREP) is sent back to
the initiator of the route discovery. The RREP contains the route sequence list from the
corresponding RREQ appended with the destination node id.
The route maintenance mechanism performs the job of validating the routes. While the
route is in use, this mechanism monitors the operation of the route and informs the sender
of any routing errors by sending a route error (RERR) packet to the original sender of the
packet. The route error packet contains the ids of the endpoints of the link that is no
longer available. Upon receiving a route error, a node purges the route entries with this
link from its route cache.
The packets in the cache and in the buffer are periodically validated. A packet is
purged from the buffer when it has been buffered for longer than the expiration period.
Similarly, each entry in the route cache has an expiration time period after which it is re-
moved from the cache.
For further details and optimizations of DSR, the interested reader should consult ref-
erences [13, 14].


In this chapter, we have proposed the use of the inverse shortest paths problem as a
method to characterize the effect of congestion on routing protocols in MANETs, and
demonstrated solutions of the resulting linear programming problem that are compatible
with observations in the simulated network. In general, inverse optimization may provide

a promising formal framework for understanding cross-layer and inter-layer protocol in-


We are grateful to Professor A. Faragó for helpful discussions as this work evolved.


1. C. Barrett, M. Drozda, A. Marathe, and M. V. Marathe, “Characterizing the Interaction Between
Routing and MAC Protocols in Ad Hoc Networks,” in Proceedings of the Third ACM Interna-
tional Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc™02), pp. 92“103,
Lausanne, Switzerland, 2002.
2. A. Bikki, “Using Inverse Optimization to Model the Effect of Congestion on Routing Protocols
in MANETs,” M. S. Thesis, University of Texas at Dallas, August 2002.
3. G. Holland and N. Vaidya, “Analysis of TCP Performance over Mobile Ad Hoc Networks,” in
Proceedings of the Fifth ACM Conference on Mobile Networking and Computing (Mobi-
Com™99), pp. 219“230, Seattle, 1999.
4. E. M. Royer, S.-J. Lee, and C. E. Perkins, “The Effects of MAC Protocols on Ad hoc Network
Communication,” in Proceedings of the IEEE Wireless Communications and Networking Con-
ference (WCNC™00), Volume 2, pp. 543“548, Chicago, 2000.
5. S. R. Das, C. E. Perkins, and E. M. Royer, “Performance Comparison of Two On-Demand Rout-
ing Protocols for Ad Hoc Networks,” in Proceedings of the Nineteenth Annual Joint Conference
of the IEEE Computer and Communications Societies (Infocom™00), pp. 3“12, Tel Aviv, Israel,
6. C. E. Perkins, E. M. Royer, S. R. Das, and M. K. Marina, “Performance Comparison of Two
On-Demand Routing Protocols for Ad Hoc Networks,” IEEE Personal Communications
Systems (PCS) Magazine, special issue on Mobile Ad Hoc Networks, 8, 1, 16“29, February
7. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE
802. 11 Standard, IEEE, New York, 1996.
8. K. Tang, M. Correa, and M. Gerla, “Effects of Ad Hoc MAC Layer Medium Access Mecha-
nisms Under TCP,” ACM/Kluwer Mobile Networks and Applications (MONET), 6, 4, 317“329,
August 2001.
9. C. E. Koksal, H. Kassab, and H. Balakrishnan, “An Analysis of Short-Term Fairness in Wireless
Media Access Protocols,” in Proceedings of the ACM International Conference on Measurement
and Modeling of Computer Systems (SIGMETRICS™00), 118“119, Santa Clara, California,
10. A. Ahuja, S. Agarwal, J. P. Singh, and R. Shorey, “Performance of TCP over Different Routing
Protocols in Mobile Ad-Hoc Networks,” in Proceedings of the IEEE Vehicular Technology Con-
ference (VTC™00), Vol. 3, pp. 2315“2319, Tokyo, Japan, 2000.
11. G. Holland and N. Vaidya, “Impact of Routing and Link Layers on TCP Performance in Mobile
Ad Hoc Networks,” in Proceedings of the IEEE Wireless Communications and Networking Con-
ference (WCNC™99), Vol. 3, pp. 1323“1327, New Orleans, Louisiana, 1999.
12. K. Chandran, S. Raghunathan, S. Venkatesan, and R. Prakash, “A Feedback-Based Scheme for
Improving TCP Performance in Ad Hoc Networks,” IEEE Personal Communications Systems
(PCS) Magazine, special issue on Ad Hoc Networks, 8, 1, 34“39, February 2001.

13. D. Johnson and D. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” in T.
Imielinski and H. Korth (Eds.), Mobile Computing, pp. 153“181, Kluwer Academic Publishers,
14. D. Johnson, D. Maltz, Y. Hu, and J. Jetcheva, “The Dynamic Source Routing Protocol for Mo-
bile Ad Hoc Networks,” IETF Internet Draft, work in progress. http://www.ietf.org/internet-
15. T. D. Dyer and R. V. Boppana, “Comparison of TCP Performance over Three Routing Protocols
for Mobile Ad Hoc Networks,” in Proceedings of the 2001 ACM International Symposium on
Mobile Ad Hoc Networking and Computing (MobiHoc™01), pp. 56“64, Long Beach, California,
16. A. Scaglione and S. Servetto, “On the Interdependence of Routing and Data Compression in
Multi-Hop Sensor Networks,” in Proceedings of the Eighth ACM International Conference on
Mobile Computing and Networking (MobiCom™02), pp. 140“147, Atlanta, Georgia, 2002.
17. Network Simulator, ns-2. The VINT Project. http://www.isi.edu/nsnam/ns/
18. C. Heuberger, “Inverse Combinatorial Optimization: A Survey on Problems, Methods and Re-
sults,” to appear in Journal of Combinatorial Optimization.


. 80
( 87 .)