Transcript Fundamentals of Computer Networks ECE 478/578

Fundamentals of Computer Networks
ECE 478/578
Lecture #17: Routing 2
Instructor: Loukas Lazos
Dept of Electrical and Computer Engineering
University of Arizona
Broadcast Routing
Broadcast Communication: All nodes of the network must receive the same
message
TV, radio are by default broadcast operations
Unicasting to each node
Source needs transmit message N times
Addresses of all recipients must be known
A total of N messages must traverse the network
Flooding
Inefficient use of bandwidth – Nodes receive the same message multiple times
Does not scale with network size N
Spanning Tree Routing
Build a (minimum) spanning tree from source to all nodes
Source need send the message only once
Message is relayed a total of (N - 1) times
2
Building a Spanning Tree
Kruskal’s Algorithm: Greedy approach
Add the edge with the smallest weight that adds connects one or two new nodes together
Repeat until all nodes are added
Broadcasting
All edges have the same weight
Any spanning tree is a minimum spanning tree
Spanning tree is the same regardless of the source of the message
3
Reverse Path Forwarding
If packet arrives from a “preferred router” forward, otherwise discard
Preferred router: router on the reverse shortest path to the source
Source
4
Broadcasting in Wireless Multi-hop Nets
Must take into account energy
The Broadcast advantage
SBn > SAn + ABn, broadcast to A and A will forward to B
Else use one transmission to B
B
BIP: Broadcast Incremental Power
S
S
A
B
C
D
A
• T={S}
• Add node j, which minimally increases the
power required to reach new node
• Repeat until all nodes are added to T
• Greedy algorithm, that leads to a nonoptimal solution
E
5
Routing for Mobile Hosts
Host moves from one network to another
If IP is changed, certain services may not work
6
Optimizing Routing for Mobile Hosts
7
Routing in Ad Hoc Networks
Ad Hoc Distance Vector Routing (AODV)
Source node floods a RREQ message
Every receiving hosts keeps a reverse path to where the packet came from
Once the message reaches the destination, it replies with a RREP
RREP is forwarded on a unicast path back to the source
8
Message Format
Route Request Message
Destination Sequence Number: Freshness of route to dest.
Source Sequence Number: Freshness of RREQ
Route Reply Message
9
Route Maintenance
Active neighbors: Neighbors that maintain active paths
10
Dynamic Source Routing (DSR)
The source determines the sequence of nodes that the packet must follow based
on
Cashed Information
A route discovery phase
Advantages of DSR
No periodic route updates as in DV, saves energy resources
No need for bidirectional links as in AODV
Can quickly adapt to changes
Disadvantages of DSR
Route is specified on the packet header that can grow fairly long
Uses flooding for routing discovery as well
11
Route Discovery in DSR
Sender broadcasts a route request (RREQ) packet
Similar format to AODV packet
Each Intermediate node
<Source address, request id>
If same, discard
The address of the intermediate node is already in the route record
This is a loop - discard
This node is the target
Send a route reply (RREP)
Else
Append node’s address to the route record, and re-broadcast
12
Example: Routing with DSR
A
A
B
A
C
A, B
A, D
A, B, C
D
E
A, D
F
A, D, F
A, B
A, B, D, G G
H
A, D, F, H
A, B, C, E
A, D, G
I
13
Geographical Routing
Route based on geographical location
Send packet to the neighbor closest to the destination, based on geographic
coordinates
No need for route discovery, or routing tables
A
B
C
D
E
F
G
H
I
14
Geographical Routing May Get Stuck
A node is closest to the destination, yet there is no transition to the
destination
15
Avoid local Minima
Create a planar graph of the network
Route in the perimeter until you hit the straight line
16