Routing Algorithm
Routing Algorithm
Flooding: Every incoming packet is sent out on every outgoing line except the one it arrived on.
Broadcast Routing:
(a) Flooding
(b) Multidimensional routing
(c) Sink tree (spanning tree) and
(d) Reverse path forwarding
It sends the packets from a host to all other remaining hosts in the network simultaneously.
Multicast Routing: It sends the packets from a host to specific group.
(a) Shared tree
(b) Source based tree
(c) Least unit cost path tree
(d) Reverse path multi-casting (uses prune message)
Distance Vector Routing: Routing only to neighbours and knowledge about whole network. RIP , IGPF uses split horizon technique.
Link State Routing (OSPF) [Dijkstra's Algorithm]: It discovers the neighbour of each router and learn their network addresses,cost of reaching each neighbours , sends the packet to all other routers.
Path Vector Routing (BGP): It list all autonomous system visited inorder to reach the destination network by this route.
Hierarchical Routing (Intra region and Inter region routing): Routing is based on regions and it maintains two tables namely "Full Table (for all routers in all regions) and "Hierarchical Table" (for all routers within the region and knows about other regions but not routers of other regions).
CONGESTION CONTROL
If number of incoming packets are more than the packets which can be handled by the network , some packets are discarded or lost in a network.This phenomenon is called as 'congestion'.
Traffic Shaping is a technique which involves in making a BURSTY INCOMING TRAFFIC into an average output or a regulated output.
Two Approaches
- Leaky Bucket
- Token Bucket
M = Maximum regulated output rate
C = Capacity of bucket
ϼ = Token filling rate
t = Time period of incoming traffic
C = ( M - ϼ )t
Flooding: Every incoming packet is sent out on every outgoing line except the one it arrived on.
Broadcast Routing:
(a) Flooding
(b) Multidimensional routing
(c) Sink tree (spanning tree) and
(d) Reverse path forwarding
It sends the packets from a host to all other remaining hosts in the network simultaneously.
Multicast Routing: It sends the packets from a host to specific group.
(a) Shared tree
(b) Source based tree
(c) Least unit cost path tree
(d) Reverse path multi-casting (uses prune message)
Distance Vector Routing: Routing only to neighbours and knowledge about whole network. RIP , IGPF uses split horizon technique.
Link State Routing (OSPF) [Dijkstra's Algorithm]: It discovers the neighbour of each router and learn their network addresses,cost of reaching each neighbours , sends the packet to all other routers.
Path Vector Routing (BGP): It list all autonomous system visited inorder to reach the destination network by this route.
Hierarchical Routing (Intra region and Inter region routing): Routing is based on regions and it maintains two tables namely "Full Table (for all routers in all regions) and "Hierarchical Table" (for all routers within the region and knows about other regions but not routers of other regions).
CONGESTION CONTROL
If number of incoming packets are more than the packets which can be handled by the network , some packets are discarded or lost in a network.This phenomenon is called as 'congestion'.
Traffic Shaping is a technique which involves in making a BURSTY INCOMING TRAFFIC into an average output or a regulated output.
Two Approaches
- Leaky Bucket
- Token Bucket
M = Maximum regulated output rate
C = Capacity of bucket
ϼ = Token filling rate
t = Time period of incoming traffic
C = ( M - ϼ )t
No comments