Scholars.muet.edu.pk

Dependable Embedded Wired/Wireless Networks  In most cases packet requires multiple hops to make  The algorithms that chooses the routes is major area of Properties for desirable Routing Algorithms  Correctness Simplicity Robustness Stability Fairness Optimality  used for selection of route simplest is “minimum hop” can be generalized as “least cost”  packet or virtual circuit basis fixed or dynamically changing  distributed - made by each node centralized source Network Information Source and Update Timing routing decisions usually based on knowledge of • using local knowledge, info from adjacent nodes, info from  when is network info held by nodes updated fixed - never updated adaptive - regular updates • Not based on measurement or estimate of current traffic and topology.
• The choice of route is computed in advance.
• called as Static Routing/Fixed Routing.
• Change routing decisions to reflect change in topology, and traffic as well.
• They differ in where they get their information, and what metric is used  Direct delivery Indirect delivery Static routing Default routing  Distance vector routing  Link state routing • Where each node rep: router and each arc communication link.
 There are many ways of measuring path length • Number of hops.
• Geographical distance.
• Transmission delay.
• Mean queuing.
Note: In general, the label on arcs could be computed as function of distance,
average traffic, measured delay and other factors.
C(,-)
E (,-)
F (,-)
D (,-)
H (,-)
F (,-)
D (,-)
H (,-)
D (,-)
H (,-)
D (,-)
D (,-)
packet sent by node to every neighboreventually multiple copies arrive at destinationno network info requiredeach packet is uniquely numbered so duplicates need some way to limit incessant retransmission  nodes can remember packets already forwarded to  at least one packet will have taken minimum hop count  can be used to set up virtual circuit  useful to distribute information (eg. routing)  disadvantage is high traffic load generated  The previous algorithms do not consider load.
Flow Based Routing (cont…)
 In some networks the mean data flow b/w pair of nodes  Under these conditions, where average traffic b/w i and j is known in advance, and constant in time, it is Flow Based Routing (cont…)
– Capacity– And average flow are known – It is possible to compute mean packet delay on that line  The routing problem than reduces to finding the routing algorithm that produces minimum average delay for Flow Based Routing (cont…)
 Certain info must be known in advance.
• Subnet topology.
• Traffic matrix Fi,j • Tentative Routing algorithm must be chosen. simplicity of flooding with much less loadnode selects one outgoing path for selection can be random or round robina refinement is to select outgoing path based no network info neededbut a random route is typically neither least  Distance Vector Routing Link State Routing • Distributed Bellman
Bellman--Ford
Ford Algorithm.
Ford--Fulkerson
Fulkerson Algorithm.
It operates by maintaining a table(vector),  Giving best known distance to destination.
 Which line to use to get there.
These vectors are updated by exchanging  Each router maintain the routing table indexed by, and containing one entry for each router in  The preferred outgoing line.
 The estimate of metric to that destination.
 The router is assumed to know the “distance” to  Distance Vector routing works in theory.
 It has serious drawbacks.
 It reacts rapidly to good news.
 But leisurely to bad news.

Source: http://scholars.muet.edu.pk/~shaikh/08esCCN/11CCN_RoutingAlgorithms.pdf