Transcript Microsoft PowerPoint Presentation: Lecture9.1

Mobile and Wireless Computing
Lecture 9: The Source Tree Adaptive Routing Protocol

Lecture 9.1 : The Least Overhead Routing
Approach and exchanging source trees for semiproactive routing

Lecture 9.2 : Routing Details and Performance
of the STAR protocol.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Table-Driven Protocols



Almost all table-driven protocols aim to do
shortest-path routing.
If a source node wants to send a message to a
destination node, the source node looks up its
routing table and forwards the message to a
neighbour that leads to a shortest path to the
destination.
The neighbour in turn follows the same
approach to forward the packet to its best
neighbour.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Maintaining Routing Table



The maintenance of correct routing tables at
each node is of utmost importance for this
approach. For example DSDV follows this
approach.
However, maintaining correct routing tables
require frequent and regular exchange of
complete or partial routing tables among the
nodes.
In particular, a node needs to broadcast any
changes in its routing table due to mobility.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Proactive and Reactive Routing



The main advantage of a proactive and tabledriven protocol is its low-latency in finding new
routes, since all routes are already present in
the local routing tables.
However, the routing overhead in terms of
control messages is usually quite high.
On the other hand, a reactive protocol like DSR
finds routes only on-demand at the cost of
higher latency in route finding. However, the
volume of control messages is low.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Polling

The approach of a reactive protocol like DSR
can be viewed as polling of a destination by a
source.

The approach of a proactive protocol like DSDV
can be viewed as polling of a source by a
destination.

Both approaches require flooding the network in
the following sense.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Flooding



In DSDV, any update of the routing table of a
node causes that node to send update
messages throughout the network. This causes
flooding. This flooding happens at regular
intervals.
In DSR, a node sends a route request message
through flooding as a route request message is
forwarded by any node that receives it.
However, this flooding is infrequent and occurs
only on-demand.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
The STAR Approach




The approach used in the STAR protocol is
inbetween these two approaches.
The idea is to maintain a source tree at each
node which connects the node to all the
destinations through loop-free tree branches.
The aim is not to emphasize the determination of
shortest paths, rather find paths which are
reasonable with respect to some metric.
This is called the Least Overhead Routing
Approach (LORA).
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
ORA and LORA



DSDV uses the Optimum Routing Approach
(ORA) which requires frequent exchange of
routing table updates.
In the LORA approach, route optimality is
sacrificed in favour of lower number of overhead
messages.
In the STAR protocol, the LORA approach is
used and the exchange of source trees among
the nodes is infrequent. Also, a source tree
much lighter compared to a routing table.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
STAR Description



In STAR, the topology of a network is modelled
as a directed graph G=(V,E), where V is the set
of nodes and E is the set of edges connecting
the nodes.
A link level protocol is assumed that keeps track
of neighbourhood information through exchange
of hello messages.
We will call a node as a router in accordance
with the terminology used in the textbook.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
STAR Description




Each router maintains a source tree that is a tree
connecting the router to all destinations that are
known to the router.
A router knows its adjacent links, i.e., the nexthop neighbours in its source tree.
A router also knows the source trees reported by
its neighbours.
The collection of a router´s own source tree and
the source trees reported by its neighbours
forms a partial topology graph for the router.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Maintaining Source Trees



A router computes its source tree by running
Dijkstra´s shortest path algorithm on its partial
topology graph.
A router updates its source tree whenever there
are significant changes in the partial topology
graph when a neighbour moves away (link
failure), or a neighbour communicates a new
source tree.
The updates are done according to the order the
communications are received.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
What Needs to be Communicated



Link deletions need not be communicated as the
deletion of a link to reach a given destination is
implicit with the addition of a new link to reach
the same destination.
The only case a router needs to explicitly inform
its neighbours about link deletion is when a
deletion causes the router to lose paths to one
or more destinations.
The basic update unit used to communicate
changes to source trees is the link state update
(LSU).
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Link State Update (LSU)

An LSU reports the characteristics of a link and
an update message contains one or more LSUs.

For a link between a router u and destination v,
the router u is called the head node of the link in
the u to v direction.

STAR uses sequence numbers (like DSDV) to
keep track of recent routes.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Sequence Numbers


When a router receives an LSU, it can determine
whether the LSU contains more recent link-state
information by comparing the sequence number
of the new LSU with the sequence number of
the link stored locally.
Each router erases a link from its partial
topology graph if the link is not adjacent to the
router and is not present in the source trees
reported by any of its neighbours.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Validating Updates




LSUs are validated through sequence numbers.
A sequence number associated with a link
consists of a counter that can be incremented
only by the head node of the link.
A router needs to keep only a single counter for
all the links for which it is a head node.
Each time the router sends an LSU for a link, it
increments this counter by 1. Hence, different
LSUs for the same link may not have cosecutive
numbers, but the numbers are monotonically
increasing.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Exchanging Update Messages



We only discuss how STAR protocol can be
implemented for supporting the Least Overhead
Routing Approach (LORA). It is possible to
implement STAR to support Optimal Routing
Approach (ORA).
The LORA approach is more important since it
reduces overheads considerably.
The ORA approach can be supported simply by
exchanging source trees whenever a router
detects a change in its source tree.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
When to Exchange Update Messages

A router running STAR protocol to support LORA
reports updates to its source tree in the event of
:
–
–
–
–

Unreachable destinations
New destinations
The possiblity of permanent routing loops
Cost of paths exceeding a given threshold
Router i checks these possible conditions by
updating its local source tree after an input event
due to the receipt of an LSU from a neighbour.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
New Destination

Router i sends a source-tree update to its
neighbours when it finds a new destination or
any of its neighbours reports a new destination.

A router can learn about a new neighbour
through link level support and this triggers a
source-tree update.
This update message is also necessary when a
node joins the network for the first time.

Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Unreachable destination or High Cost of a Link




Router i sends an LSU when the cost of a path
to a destination exceeds a threshold.
In the special case, a link failure to a destination
may be denoted by a cost of infinity.
A failure of a link to the head node of a subtree
implies failure of links to all nodes in that
subtree.
However, it is not necessary to inform the failure
of links to all the nodes in that subtree.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Unreachable Destination
u
LSU message
m
Link failure
v
It
is suficient only to report the
failure of the link from u to v.
w
Since
m has a copy of u´s source tree, m can infer
that a failure of the link from u to v implies a failure of
the link from u to any node in the subtree rooted at v,
like w.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Unreachable Destination

However, if any of the destinations in the subtree
rooted at v is reachable in u´s source tree, it is
necessary to include in the LSU the paths to
those destinations.

When a destination becomes unreachable to
any of the router i´s neighbours and i has a path
to that destination in its source tree, it is
necessary for i to send an LSU.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)