Scribd
Upload
14 views18 pages

Hierarchical and Mobile Routing Techniques

This document discusses different routing techniques including hierarchical routing, routing for mobile hosts, broadcast routing, and multicasting. It provides examples and explanations of the following key points: 1) Hierarchical routing divides a large network into regions and uses routing tables to direct traffic between regions in a more efficient manner than flat routing tables. 2) Routing for mobile hosts requires techniques like home and foreign agents to track user locations and tunnel packets to mobile users roaming across different network areas. 3) Broadcast routing techniques aim to deliver packets to all destinations simultaneously in an optimized way, such as using spanning trees, reverse path forwarding, or multi-destination routing. 4) Multicasting delivers messages to well-

Uploaded by

Amit Gupta
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
14 views18 pages

Hierarchical and Mobile Routing Techniques

This document discusses different routing techniques including hierarchical routing, routing for mobile hosts, broadcast routing, and multicasting. It provides examples and explanations of the following key points: 1) Hierarchical routing divides a large network into regions and uses routing tables to direct traffic between regions in a more efficient manner than flat routing tables. 2) Routing for mobile hosts requires techniques like home and foreign agents to track user locations and tunnel packets to mobile users roaming across different network areas. 3) Broadcast routing techniques aim to deliver packets to all destinations simultaneously in an optimized way, such as using spanning trees, reverse path forwarding, or multi-destination routing. 4) Multicasting delivers messages to well-

Uploaded by

Amit Gupta
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Hierarchical Routing

Region 1
1B 1A 1C 2C 2A

Region 2
2B
2D

5B

4A
3A 5A 3B 4B 4C 5E

5C

5D

Region 3

Region 5
Region 4

2/8/2013

Hierarchical Routing

Full table for 1A


Dest line hops
1A 1B 1C 2A 2B 2C 2D 3A 1B 1C 1B 1B 1B 1B 1C 1 1 2 3 3 4 3

Hierarchical table for 1A

Dest Line hops

1A 1B 1C 2 3 4 5

1B 1C 1B 1C 1C 1C

1 1 2 2 3 4

3B
4A 4B 4C 5A 5B 5C 5D 5E
2/8/2013

1C
1C IC 1C 1C 1C 1B 1C 1C

2
3 4 4 4 5 5 6 5
Hierarchical Routing

Routing For Mobile Hosts


Users

Stationary Users

Migratory Users

Roaming Users

Mobile Users

2/8/2013

Routing for Mobile Hosts

Network designers View of the world

Wireless Cell
Home Agent

Mobile Host

Home LAN

Foreign Agent

WAN

Foreign LAN

MAN

2/8/2013

Routing for Mobile Hosts

Terminology
Areas: Small geographical units typically LANS or WIRELESS Foreign Agent: Keeps track of all the mobile users visiting the area. Home Agent: Keeps track of users whose home is in the area but currently visiting another area.
2/8/2013

Routing for Mobile Hosts

Registration Process of a Mobile User


Mobile Host Foreign Agent Home Agent

Asks for FA
Register
1 2

Contacts Examines timestamp present the in the security information

Registered/ Not

Ack to proceed/stop

Home address, current DLL address & security information Foreign Agents Network address & security information
Routing for Mobile Hosts
6

2 2/8/2013

Packet Routing for Mobile Users


Mobile User 3 4 Users Home Address Home Agent 2 1

Foreign Agent

1. Packet is sent to the mobile hosts home address.

2. Packet is tunneled to the foreign agent.


3. Sender is given the foreign agents address. 4. Subsequent packets are tunneled to the foreign agent.
2/8/2013

Routing for Mobile Hosts

Broadcast Routing
Sending packets to all destinations simultaneously. Various methods for broadcasting: 1. Separately addressed packets. 2. Flooding 3. Multidimensional routing. 4. Spanning tree. 5. Reverse path forwarding.
2/8/2013

Broadcast Routing

1. Separately Addressed Packets


Source sends a packet to each of the destination. Disadvantage:

Wastage of bandwidth. Source needs to know the complete list of destinations.

2/8/2013

Broadcast Routing

2. Flooding
In this technique, source sends packets on all its outgoing lines. Disadvantage:

Generates too many packets Bandwidth consumption is more.

2/8/2013

Broadcast Routing

10

3. Multi-destination routing
In this method each packet contains either a list of destinations or a bit map indicating the desired destination.

Packet arrives

Out going lines

2/8/2013

Broadcast Routing

11

4. Spanning Tree
A spanning tree is a subset of the subnet that includes all the routers but contains no loops.

2/8/2013

Broadcast Routing

12

12

7-8 4-5 4-3 2-1 4-7 1-3 7-6 8-6 2-4 5-6 3-5 2 3 6 8 12 12 15 16 16 19 21
3 21

16 4

3 5 15 8

12

12 6 3 3 5

19
6

2 4 12 15

7 2

16

Weighted Graph

7 2

Spanning Tree
13

2/8/2013

Broadcast Routing

Spanning Tree
Advantage: 1. Makes excellent use of bandwidth 2. Minimum number of packets are generated Disadvantage: Each router must have some knowledge of the spanning tree.

2/8/2013

Broadcast Routing

14

5. Reverse Path Forwarding


In this method, the router forwards only the packets that have traveled the shortest path from source to router, all other copies are [Link] Path
Packet is discarded
Arrival R Departure Departure Arrival Departure
2/8/2013

Packet is Forwarded

Not the shortest path

Broadcast Routing

15

Multicasting
A technique in which messages are sent to well defined groups which are numerically large in size but small compare to the network as a whole.

2/8/2013

Multicast Routing

16

A Subnet

1
2 1,2 2 2

Spanning tree for the leftmost 1 router 2 1,2 2 2

1,2

1,2

1 1 2 2 2 2

Multicast tree for group 1


2 1 1

Multicast tree for group 2 1

1
2/8/2013

1
Multicast Routing

1
17

Pruning of spanning tree


The following 2 ways can be used:

Link State Routing. Distance Vector Routing.

2/8/2013

Multicast Routing

18

You might also like