Scribd
Upload
32 views

Details - Routing Algorithms

This document discusses various routing algorithms and concepts. It covers properties of routing algorithms, shortest path routing, flooding, distance vector routing, link state routing, hierarchical routing, broadcast routing, multicast routing, routing for mobile hosts, routing in ad hoc networks, and node lookup in peer-to-peer networks. Specific algorithms and concepts discussed in more depth include distance vector routing, link state routing, routing for mobile hosts using foreign agents and home agents, routing in ad hoc networks using an on-demand approach, and multicast routing using pruning.

Uploaded by

Ansh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views

Details - Routing Algorithms

This document discusses various routing algorithms and concepts. It covers properties of routing algorithms, shortest path routing, flooding, distance vector routing, link state routing, hierarchical routing, broadcast routing, multicast routing, routing for mobile hosts, routing in ad hoc networks, and node lookup in peer-to-peer networks. Specific algorithms and concepts discussed in more depth include distance vector routing, link state routing, routing for mobile hosts using foreign agents and home agents, routing in ad hoc networks using an on-demand approach, and multicast routing using pruning.

Uploaded by

Ansh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 24

Routing Algorithms

• Properties
• Shortest Path Routing
• Flooding
• Distance Vector Routing
• Link State routing
• Hierarchical routing
• Broadcast routing
• Multicast routing
• Routing for mobile hosts
• Routing in Ad Hoc Networks
• Node Lookup in Peer-to-Peer Networks
Routing algorithms
Routing: distance vector
Routing: distance vector
• Algorithm
• At each step within a router:
• Get routing tables from neighbours
• Compute distance to neighbours
• Compute new routing table
• Characteristics:
• Iterative
• Asynchronous
• Distributed
Routing: link state Overview of algorithm:

• Each router must


• Discover its neighbours and learn their network addresses
• Measure the delay or cost to each of its neighbours
• Construct a packet with these distances
• Send this packet to all other routers
• Compute the shortest path to every other router

Network layer -- May 2004 5


Routing: link state
• Learning about neighbours:
• Upon boot of router
• Send HELLO packet on each point-to-point line
• Routers are supposed to send reply with a globally unique name
• LAN
model
Routing: link state
Routing: link state
• Computing new routes:
• With a full set of link state packets, a router can:
• Construct the entire subnet graph
• Run Dijkstra’s algorithm to compute the shortest path to each destination
• Problems for large subnets
• Memory to store data
• Compute time
Network Layer
Routing for Mobile Hosts
• How does it work?
• Registration procedure with foreign agents
• Sending packets
• Leaving an area
• Registration procedure with foreign agent
• Announcing existence of foreign agent
• Broadcast by foreign agent
• Broadcast query by arriving mobile user
• Mobile user gives to foreign agent
• Home address
• Current data link address
• Security information
• Foreign agent contacts home agent of user

Network layer -- May 2004 10


Broadcast routing• Send message to all other hosts:
• Update distributed database
• Distribute weather reports
• Distribute live radio/TV programs
• Poor methods:
• Send a distinct packet to each destination
• List of addresses needed
• High usage of bandwidth
• Flooding
• Too many packets
• Multidestination routing
• Each packet contains a list of destination
• On each line a single packet

Network layer -- May 2004 12


Multicast routing

source

• Algorithm • Pruning:
• Source computes spanning • Link state routing
tree • Each router knows full topology
• Remove lines that do not • Distance vector routing
lead to hosts of group • Reverse path forwarding +
( = pruning) • PRUNE messages to remove
arcs

Network layer -- May 2004 13


Multicast routing
•

source

• Pruning:
• Link state routing
• Each router knows full topology
• Distance vector routing
• Reverse path forwarding +
• PRUNE messages to remove
arcs

Network layer -- May 2004 14


Routing for Mobile Hosts
o Move from time to time
• Model of world: WAN + LANs, wireless cells
o Use network when connected
• Migratory users
• Roaming users
o Compute on the run
o Maintain connections as they
move around

Network layer -- May 2004 15


Routing for Mobile Hosts
• Foreign agent: keeps track of users: • Home agent: keeps track of users
• who are currently visiting the area • whose home is in the area
• who are currently visiting another area

Permanent home location


Permanent home address

Network layer -- May 2004 16


Design: internal organisation
Routing for Mobile Hosts
• Registration procedure with foreign agent (cont.)
• Announcing existence of foreign agent
• Mobile user gives to foreign agent
• Foreign agent contacts home agent of user
• Identity of user
• Security info
• Network address of foreign agent
• Home agent
• Checks security info
• Sends ack to foreign agent
• Foreign agent
• Stores state
• Informs mobile user

Network layer -- May 2004 18


Routing for Mobile Hosts
• Sending a packet to a mobile user
• Home address is used packet routed to home LAN
• Packet intercepted by home agent
address of user ≠ address of home agent!
• Packet forwarded to the foreign agent
• Encapsulation – tunneling
• Foreign agent forwards packet to mobile user
• Which protocol, address used?
• Sender is given address of foreign agent
• Encapsulation – tunneling used, required?

Network layer -- May 2004 19


Routing for Mobile Hosts
• Sending a packet to a mobile user
• Home address is used packet routed to home LAN
• Packet intercepted by home agent
address of user ≠ address of home agent!
• Packet forwarded to the foreign agent
• Encapsulation – tunneling
• Foreign agent forwards packet to mobile user
• Which protocol, address used?
• Sender is given address of foreign agent
• Encapsulation – tunneling used, required?

Network layer -- May 2004 20


Routing for Mobile Hosts

Home agent

Foreign agent

Network layer -- May 2004 21


Routing Algorithms
• Properties
• Shortest Path Routing
• Flooding
• Distance Vector Routing
• Link State routing
• Hierarchical routing
• Broadcast routing
• Multicast routing
• Routing for mobile hosts
• Routing in Ad Hoc Networks
• Node Lookup in Peer-to-Peer Networks
Network layer -- May 2004 22
Routing in Ad Hoc Networks
• Ad Hoc Network = routers are mobile
• No fixed topologies
• No fixed or known neighbors
• Valid paths can disappear at any time
• Node = router + host
• Routing quite different from routing in wired networks
• Examples
• Military vehicles on a battlefield
• Fleet of ships at see
• People with notebooks (lacking 802.11)
• AODV = Ad hoc On-demand distance vector routing
• On-demand: route computed when needed
• Distance vector for mobile world
• Taking into account limited bandwidth + low battery life

Network layer -- May 2004 23

You might also like