<<

. 78
( 87 .)



>>

62. A. Willig, “A New Class of Packet and Bit Level Models for Wireless Channels,” in Proceed-
ings of 13th IEEE International Symposium on Personal Indoor and Mobile Radio Communica-
tions, Lisbon, Portugal, 2002.
63. Wu, H. and R. Fujimoto, “Experiences Parallelizing a Commercial Network Simulator,” in Pro-
ceedings of the 2001 Winter Simulation Conference, pp. 1353“1360.
409
REFERENCES


64. J. Yoon, M. Liu, and B. Noble, “Random Waypoint Considered Harmful,” in Proceedings of
InfoCom, 2003.
65. X. Zeng and R. Bagrodia, “GloMoSim: A Library for the Parallel Simulation of Large Wireless
Networks,” in Proceedings of the 12th Workshop on Parallel and Distributed Simulation, Cal-
gary, Canada, June 1998.
66. M. M. Zonoozi and P. Dassanayake, “User Mobility Modeling and Characterization of Mobility
Patterns,” IEEE Journal on Selected Areas in Communication, 15, 7, September 1997.
CHAPTER 15




MODELING CROSS-LAYER INTERACTION
USING INVERSE OPTIMIZATION

VIOLET R. SYROTIUK and AMARESH BIKKI




15.1 INTRODUCTION

Traditionally, networks are organized as a series of layers, each one built on the one below
it. Although this simplifies the network design, the behavior of a protocol can vary signif-
icantly depending on the protocol above it or below it in the protocol stack. Many exam-
ples of cross-layer and inter-layer interaction are known. Although such interactions occur
locally within a node in the network, they have also been found to occur between nodes
that are not even adjacent [1]. Understanding how, and to what extent, protocols interact
with each other will ultimately yield improvements in network performance.
The layered network design philosophy has largely predominated, even in wireless net-
works such as mobile ad hoc networks (MANETs). A MANET is a self-organizing collec-
tion of mobile wireless nodes with no supporting infrastructure. These networks are envi-
sioned for situations such as emergency operations after a natural or environmental
disaster has destroyed existing infrastructure, special operations in support of law enforce-
ment activities, military missions in a hostile and/or unknown territory, commercial gath-
erings such as conferences, and the creation of interactive classrooms.
Recent research in MANETs has primarily focused on the optimization of protocols at
individual layers of the protocol stack. Although there is an increasing awareness that pro-
tocols do not act in isolation, very little formal characterization of their interaction has
been made. In Section 15.2, we overview the work related to protocol interaction in
MANETs.

*Both authors were affiliated with the University of Texas at Dallas for the duration of this work.

411
Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.
412 MODELING CROSS-LAYER INTERACTION USING INVERSE OPTIMIZATION


The problem motivating our work is the observation that routing protocols in MANETs
using hop count as the path metric do not always route packets along the shortest hop path
[2, 3]. For example, congestion in the network can cause the protocol to discover and
route through paths other than the shortest hop path. Here, the congestion control mecha-
nisms interact with the routing protocol to effectively change the link metrics into some
more complex function than hop count. We have an inadequate understanding of the im-
pact of congestion on the link metrics used in the shortest-path calculations. One way to
improve our understanding of the link metrics used is to consider the inverse problem.
Solving an inverse shortest-path problem consists of finding weights associated with the
links of a network that are as close as possible to the a priori estimated values, and that are
compatible with the observations of the shortest paths used for routing in the network.
In Section 15.3 we formulate an inverse shortest-path optimization problem to model
the effect of congestion on routing in MANETs. We model congestion by the delay and
the packet loss rate on each link in the network. Now, given actual routes computed by the
routing protocol in the network, the question is: What are the link weights that make these
routes the shortest paths? More specifically, we compute the contribution of each of the
parameters of the delay and the packet loss rate to the link metric. The solution to the in-
verse shortest-path problem is obtained by formulating and solving a linear program. Sec-
tion 15.4 describes our simulation study and demonstrates solutions that are compatible
with observations in the simulated network. Finally, Section 15.5 summarizes the chapter.


15.2 RELATED WORK IN MANETs

First, we describe the interaction of the medium access control (MAC) layer with high-
er-layer protocols, and higher-layer interactions as observed in simulation studies. We
then overview formal mechanisms to model protocol interaction.

15.2.1 MAC Protocol Interaction
Studies on the performance of MANET routing protocols run over different MAC proto-
cols [4, 5, 6] conclude that table driven routing protocols are not affected by the selection
of MAC protocol, whereas the amount of control traffic generated by a reactive routing
protocol is dependent on the underlying MAC protocol. Furthermore, if a routing protocol
generates more unicast packets than broadcast packets, this can affect throughput. This
depends on the implementation of the MAC layer primitives. In some MAC protocols,
such as IEEE 802.11 [7], there is more overhead in transmitting a unicast packet than a
broadcast packet because a broadcast packet is not transmitted reliably.
In [8], MAC-layer mechanisms are isolated to determine the effect of each on network
performance and to determine those most effective in supporting the User Datagram
Protocol (UDP) and the Transport Control Protocol (TCP). The mechanisms considered in-
clude carrier sensing, packet sensing, carrier sensing with collision avoidance, handshake-
control packets, and link-level acknowledgments (ACKs). The simulation study shows that
carrier sensing alone is preferable for UDP traffic with a constant bit rate (CBR), whereas
carrier sensing with collision avoidance is preferable for TCP running the file transfer pro-
tocol (FTP). In both cases, the handshake mechanism provides better sharing of the chan-
nel since it is a form of coordination among the nodes. Further, when ACKs are used,
throughput tends to increase since unnecessary retransmissions are avoided.
413
15.3 CHARACTERIZING INTERACTION USING INVERSE OPTIMIZATION


Koksal et al. [9] examine how short-term unfairness of a MAC protocol can degrade
the performance of transport and application protocols.

15.2.2 Routing Protocol Interaction
Several studies have examined the interaction of routing failures on TCP performance [3,
10, 11, 12]. In the Dynamic Source Routing (DSR) protocol [13, 14], routing failures can
be the result of the propagation of stale routes from the cache. In TCP, if the source is not
aware of a route failure it continues to transmit packets, leading to packet loss. Since
packet loss is interpreted as congestion, TCP invokes congestion-recovery algorithms
when the route is reestablished. This “slow start” mechanism throttles the transmission
and results in performance degradation in the network.
There are several feedback-based schemes proposed in which the failure point notifies
the source of route failures and/or reestablishments [12]. This allows a node to distinguish
route failures from congestion and apply a different solution for each problem. Fixing re-
transmission timeout intervals has also been applied to distinguish between failure and
congestion [15].

15.2.3 Formal Models for Protocol Interaction
To our knowledge, the first comprehensive study that attempts to characterize the interac-
tion between the MAC and routing protocols in MANETs using more rigorous techniques
is by Barrett et al. [1]. Extensive simulation-based experiments are performed and statisti-
cal analysis is used to study whether four factors R, v, M, and interact with each other in
a significant way. Here R is a routing protocol, v is node velocity, M is a MAC protocol,
and is a packet arrival rate. Statistically, interaction between two factors exists when the
effect of a factor on a response variable is modified by another factor in a significant way.
The response variables used are latency, number of packets received, and fairness.
Starting with a saturated model, backward elimination is applied. This method checks
each k-way factor interaction term for significance using analysis of variance techniques,
k = 4, . . . , 1, and eliminates it if it is found to be insignificant. In this way, the smallest
model that explains the simulation data is found.
The smallest model found when latency is the performance measure is the three-way [R,
v, M] term, whose interaction is due to the two-way interactions between [R, M] and [v, M].
Interestingly, there is no interaction between [R, v] on latency. For the measure number of
packets received, all four factors [R, v, M, ] interact significantly, whereas for fairness the
two-way interactions of [R, M] and [M, ] are found to be most significant.
In [16], an approach based on source codes, combined with suitable routing algorithms
and the reencoding of data at intermediate relays nodes, is used to capture the interdepen-
dencies between routing and data compression. This model is used to show that the
amount of data generated by a sensor network is below its transport capacity. This sup-
ports the feasibility of large-scale multihop sensor networks.


15.3 CHARACTERIZING INTERACTION USING INVERSE OPTIMIZATION

We first describe an experiment that shows how congestion mechanisms impact routing.
These observations motivate us to introduce a function of congestion in the link metric
414 MODELING CROSS-LAYER INTERACTION USING INVERSE OPTIMIZATION


used for routing, and to use inverse optimization to find the weights associated with the
links that are compatible with the actual observed shortest paths used for routing in the
network.

15.3.1 Motivating Example
In an effort to understand the effect of congestion mechanisms on routing, we set up the sta-
tic network topology shown in Figure 15.1 with each node running the Dynamic Source
Routing (DSR; see Section 15.6 for a brief overview of the DSR routing protocol) [13, 14]
protocol in the ns-2 [17] network simulator. We use a static network to conclusively show
that although DSR uses hop count as the path metric, the congestion mechanisms cause the
protocol to discover and use a longer path even though a shorter path exists in the network.
We use DSR for routing because it is proactive, and because of the convenience of the com-
plete source“destination paths stored locally in the source™s route cache.
Then we model a MANET by a weighted, undirected graph G = (V, E, W). The vertex
set V corresponds to the nodes in the network. An edge (i, j) exists in the edge set E when-
ever the vertices i and j are in the transmission range of each other. W is the set of edge
weights, that is, W = {wi, j} for (i, j) E. A path Ps,d of length k from a vertex s to a vertex
d in a graph G is a sequence v0, v1, v2, . . . , vk of vertices such that s = v0, d = vk, and
(vi“1, vi) E for i = 1, 2, . . . , k. The length of the path Ps,d, denoted as len(Ps,d), is the
number of edges in the path.
We induced a large volume of traffic between nodes 3 and 4 and, as a result, the link
between nodes 3 and 4 is heavily congested. Now consider what happens when node 1 ini-
tiates a route request (RREQ) packet to the destination node 7 once link (3, 4) is congest-
ed. There are two paths through which the RREQ packet can reach the destination.
The one path of length six is P1,7 = 1, 2, 3, 4, 5, 6, 7 and the other path of length sev-
en is P1,7 = 1, 2, 8, 9, 10, 11, 6, 7 . Since the link between nodes 3 and 4 is congested, the
route request may be dropped at node 3. Some reasons the RREQ packet may be dropped
include: buffer overflow at node 3, collision of the packet with data traffic in the opposite
direction, i.e., from node 4 to 3, and queueing delays at node 3.
If the route request is dropped at node 3, then node 7 may only receive one RREQ that
has traversed the longer path P1,7. As a result, node 1 receives a route reply (RREP) from
node 7 containing route P1,7. This route is then cached and used by node 1 to send traffic
to node 7.
If the route request is delayed at node 3 rather than dropped, then the RREQ along path
P1,7 reaches node 6 earlier than from along P1,7. In this case, node 6 discards the second
RREQ as it has the same request identifier as that of the RREQ from the longer, but less
congested, path. Therefore, even in the event of a delay along the shorter path, node 1 re-
ceives a RREP that contains the route P1,7.



4 5
3
2 6 7
1
11
9
8 10

Figure 15.1. Static MANET topology demonstrating effects of congestion.
415
15.3 CHARACTERIZING INTERACTION USING INVERSE OPTIMIZATION


Suppose that this time node 1 performs route discovery to node 6. Suppose that, as a
result, it found two routes to node 6, P1,6 = 1, 2, 3, 4, 5, 6 of length five, and P1,6 = 1, 2,
8, 9, 10, 11, 6 of length six. Since the first route is shorter than the second, node 1 sends
any packets destined to node 6 through path P1,6 (now, duplicate RREQs do not occur at
intermediate nodes).
Consider the scenario in which node 1 is routing packets to node 6 and link (3, 4) be-
comes congested. Now, a packet is dropped at node 2 because it exceeded the number of
retransmissions when node 2 tried to forward it to node 3. This might happen if node 3 is
too busy forwarding its own traffic to node 4. In such a case, node 2 sends a route error
(RERR) packet back to node 1, informing it that the link between nodes 2 and 3 is no
longer available. Upon reception of this packet, node 1 purges the route P1,6 from the
cache and starts using the route P1,6, which is already present in its route cache, to send a
packet to node 6. Despite the existence of a shorter path, node 1 starts to use a longer
path.
This example demonstrates that the presence of congestion may result in a node rout-
ing packets over a path other than the shortest-hop count path. Hence, congestion effec-
tively alters the link metrics in the network. This suggests that rather than wi, j = 1 for all
(i, j) E, its value should reflect the congestion on the links.


15.3.2 Modeling Congestion in the Link Metric
In order to reflect the effect of congestion on routing, we model the link weight as a linear
function of the hop count, the average packet delay (di, j), and the average packet loss rate
( i, j) across a link (i, j), that is,

wi, j = 1 + · di, j + · (15.1)
i, j


where the values of , > 0 represent the relative weights of the packet delay and loss
rate, respectively, in the cost of a link. Although, in reality, link weight may be a more
complex function of congestion (and other parameters) than we use in our model, we
choose these two parameters to validate our idea.
Now, the cost of a path Ps,d between a source node s and a destination node d (wPs,d) is
defined as follows:

wPs,d = wi, j = len(Ps,d) + di, j + (15.2)
i, j
(i,j) Ps,d (i,j) Ps,d (i,j) Ps,d


We are interested in finding the values of and in Equation (15.2) to determine how,
and to what extent, these elements of congestion affect the routing protocol. In order to
accomplish this, we formulate an inverse shortest-path problem.


15.3.3 Inverse Shortest-Path (ISP) Formulation
When solving an optimization problem, usually the parameters such as costs, capacities,
and so on are known and the interest is in finding an optimal solution. However, in prac-
tice, certain solutions might be known to be optimal from observations or experiments.
The idea of inverse optimization is to find values of the parameters that make the known
solutions optimum and that differ from the estimates as little as possible. Heuberger and
416 MODELING CROSS-LAYER INTERACTION USING INVERSE OPTIMIZATION


Ahuja et al. provide a good general introduction to inverse optimization [18, 19], with in-
teresting applications in geophysics, medical imaging, transportation, and communica-

<<

. 78
( 87 .)



>>