Posts: 2,051
Threads: 1,405
Joined: Jun 2011
[attachment=15102]
ROUTING PROTOCOLS WITH EFFICIENT FLOODING MECHANISMS
Routing Protocol With Efficient Flooding Mechanisms
Existing routing protocols employ efficient
flooding mechanisms to counter the
requirement of flooding.
– Preferred link-based routing (PLBR): On demand
– Optimized page link state routing (OLSR): Table-driven
These protocols require a minimum number
of retransmissions in order to flood the entire
network.
Preferred Link-Based Routing Protocol (PLBR)
• Neighbor List (NL)
• Preferred List (PL): a subset of NL
– Only the neighbors in PL forward the RouteRequest further.
• Neighbor’s Neighbor Table (NNT)
• RouteRequest:
– Contains SrcID, DestID, SeqNum, TP(Traversed Path), TTL, NoDelay
• Three phases
– Route establishment
– Route selection
– Route maintenance
Route establishment:
– If Dest is in Src’s NNT, the route is established directly.
– Otherwise, Src transmits RouteRequest. And the RouteRequest is forwarded only
• The node ID is in the PL (K entries) of received RouteRequest.
• The RouteRequest must not have been forwarded by the node.
• TTL is greater than zero.
– Before forwarding, the node updates the PL of RouteRequest by its preference list table (PLT).
– If Dest is in node’s NNT, the node forwards RouteRequest as a unicast packet to the neighbor.
Route selection for Dest:
– Waiting RouteSelectWait period
– The path has Max(Wimin) is selected, where i is the
number of RouteRequest.
– If NoDelay is set, the TP of the first RouteRequest
reaching the Dest is selected as the route.
Route Maintenance:
– Bypassing the down page link node form the broken
path with the information in NNT.
• Preferred Links Computation:
– Neighbor Degree-Based Preferred Link Algorithm
(NDPL)
• As higher degree neighbors cover more nodes, only a
few of them are required to cover all the nodes of the
NNT.
• This reduces the number of broadcasts.
– Weight-Based Preferred Link Algorithm (WBPL)
• The notion of stability is based on the weight given to
links.
Neighbor Degree-Based Preferred Link Algorithm (NPDL)
N(i): neighbor of node i and itself. INL: a set of NB reachable by
transmitting the RouteRequest packet. EXL: a set of NB unreachable by
transmitting the RouteRequest packet. TP: the list of nodes the packet
has traversed so far
Node d adds N(i) to include list (INL).
• A node i of TP is a neighbor of node d.
• A node i of OLDPL is a neighbor of node d, and i < d.
• A node i is a neighbor of node d and has a neighbor n in TP.
• A node i is a neighbor of node d and has a neighbor n in OLDPL\and n < d
B. If neighbor i of node d is not in INL, puts i in PLT and marks neighbors of i as reachable. If neighbor i is in INL, marks the neighbors of i as unreachable by adding them to exclude list (EXL).
C. If neighbor i of node d has neighbor n in EXL,
put i in PLT. Mark all neighbors of i as
reachable and delete them from EXL.
• After this step, all the nodes in NNT are
d reachable.
D. Reduction steps
• Removing each neighbor i from PLT if N(i) is
covered by remaining neighbors of PLT.
• Removing neighbor i from PLT whose N(i) is
covered by node d itself.
Weight-Based Preferred Link Algorithm (WBPL)
• WBPL
– Wi = WTitime + Wtispatial
– WTitime = 1 if BCnti > Thbcon
= BCnti / Thbcon otherwise
– WTispatial = R-Dest/R
– The neighbors are put into the PLT if they are in a nonincreasing
order of their weights.
– If a page link is overloaded, delete the associated neighbor from PLT.
Advantages:
Minimizes the broadcast storm occurred in On-Demand routing protocol.
High scalability.
Reduction in control overhead results decrease in the no.of collisions and improvement in the efficiency of protocol.
Disadvantage:
Both PLBR and WBPL are much more computationally complex than the other reactive protocols.
Optimized Link State Routing (OLSR)
• Multipoint relays:
– MPRset:
• MPRset processes and forwards every page link state packet that
node P originates.
• The member of MPRset is selected in the manner that every
node in the node’s two-hop neighborhood has bidirectional
link with the node.
– MPR selectors:
• A node only forwards the packet received from its
MPRselector set.
– Hello message:
• The list of neighbor with which the node has bidirectional
links.
• The list of neighbor whose transmissions were received in the
recent past but with whom bidirectional links have not yet
been confirmed.
• Topology Control (TC) packet
– is periodically originated
– contains MPRselector of every node
– Floods throughout the network with multipoint relaying mechanism.
• Selection of the optimal MPRset is NP-complete.
MPR(x)Φ
MPR(x){Those nodes that belong to N1(x) and which are the only
neighbors of nodes in N2(x) }
While there exists some node in N2(x) which is not covered by MPR(x)
Each node in N1(x) ,which is not in MPR(x) ,compute the max
number of nodes that it covers among the uncovered nodes in
N2(x) .
Add to MPR(x) the node belonging to N1(x) , for which this
number is max.
Advantages:
Reduces the routing overhead associated with table driven routing in addition to reducing the no.of broadcasts done.
Low connection setup time.
Reduced control overhead.
Posts: 2,051
Threads: 1,405
Joined: Jun 2011
[attachment=15260]
ROUTING PROTOCOLS WITH EFFICIENT FLOODING MECHANISMS
Routing Protocol With Efficient Flooding Mechanisms
Existing routing protocols employ efficient
flooding mechanisms to counter the
requirement of flooding.
– Preferred link-based routing (PLBR): On demand
– Optimized page link state routing (OLSR): Table-driven
These protocols require a minimum number
of retransmissions in order to flood the entire
network.
Preferred Link-Based Routing Protocol (PLBR)
• Neighbor List (NL)
• Preferred List (PL): a subset of NL
– Only the neighbors in PL forward the RouteRequest further.
• Neighbor’s Neighbor Table (NNT)
• RouteRequest:
– Contains SrcID, DestID, SeqNum, TP(Traversed Path), TTL, NoDelay
• Three phases
– Route establishment
– Route selection
– Route maintenance
Route establishment:
– If Dest is in Src’s NNT, the route is established directly.
– Otherwise, Src transmits RouteRequest. And the RouteRequest is forwarded only
• The node ID is in the PL (K entries) of received RouteRequest.
• The RouteRequest must not have been forwarded by the node.
• TTL is greater than zero.
– Before forwarding, the node updates the PL of RouteRequest by its preference list table (PLT).
– If Dest is in node’s NNT, the node forwards RouteRequest as a unicast packet to the neighbor.
Route selection for Dest:
– Waiting RouteSelectWait period
– The path has Max(Wimin) is selected, where i is the
number of RouteRequest.
– If NoDelay is set, the TP of the first RouteRequest
reaching the Dest is selected as the route.
Route Maintenance:
– Bypassing the down page link node form the broken
path with the information in NNT.
• Preferred Links Computation:
– Neighbor Degree-Based Preferred Link Algorithm
(NDPL)
• As higher degree neighbors cover more nodes, only a
few of them are required to cover all the nodes of the
NNT.
• This reduces the number of broadcasts.
– Weight-Based Preferred Link Algorithm (WBPL)
• The notion of stability is based on the weight given to
links.
Neighbor Degree-Based Preferred Link Algorithm (NPDL)
N(i): neighbor of node i and itself. INL: a set of NB reachable by
transmitting the RouteRequest packet. EXL: a set of NB unreachable by
transmitting the RouteRequest packet. TP: the list of nodes the packet
has traversed so far
Node d adds N(i) to include list (INL).
• A node i of TP is a neighbor of node d.
• A node i of OLDPL is a neighbor of node d, and i < d.
• A node i is a neighbor of node d and has a neighbor n in TP.
• A node i is a neighbor of node d and has a neighbor n in OLDPL\and n < d
B. If neighbor i of node d is not in INL, puts i in PLT and marks neighbors of i as reachable. If neighbor i is in INL, marks the neighbors of i as unreachable by adding them to exclude list (EXL).
C. If neighbor i of node d has neighbor n in EXL,
put i in PLT. Mark all neighbors of i as
reachable and delete them from EXL.
• After this step, all the nodes in NNT are
d reachable.
D. Reduction steps
• Removing each neighbor i from PLT if N(i) is
covered by remaining neighbors of PLT.
• Removing neighbor i from PLT whose N(i) is
covered by node d itself.
Weight-Based Preferred Link Algorithm (WBPL)
• WBPL
– Wi = WTitime + Wtispatial
– WTitime = 1 if BCnti > Thbcon
= BCnti / Thbcon otherwise
– WTispatial = R-Dest/R
– The neighbors are put into the PLT if they are in a nonincreasing
order of their weights.
– If a page link is overloaded, delete the associated neighbor from PLT.
Advantages:
Minimizes the broadcast storm occurred in On-Demand routing protocol.
High scalability.
Reduction in control overhead results decrease in the no.of collisions and improvement in the efficiency of protocol.
Disadvantage:
Both PLBR and WBPL are much more computationally complex than the other reactive protocols.
Optimized Link State Routing (OLSR)
• Multipoint relays:
– MPRset:
• MPRset processes and forwards every page link state packet that
node P originates.
• The member of MPRset is selected in the manner that every
node in the node’s two-hop neighborhood has bidirectional
link with the node.
– MPR selectors:
• A node only forwards the packet received from its
MPRselector set.
– Hello message:
• The list of neighbor with which the node has bidirectional
links.
• The list of neighbor whose transmissions were received in the
recent past but with whom bidirectional links have not yet
been confirmed.
• Topology Control (TC) packet
– is periodically originated
– contains MPRselector of every node
– Floods throughout the network with multipoint relaying mechanism.
• Selection of the optimal MPRset is NP-complete.
MPR(x)Φ
MPR(x){Those nodes that belong to N1(x) and which are the only
neighbors of nodes in N2(x) }
While there exists some node in N2(x) which is not covered by MPR(x)
Each node in N1(x) ,which is not in MPR(x) ,compute the max
number of nodes that it covers among the uncovered nodes in
N(x) .
Add to MPR(x) the node belonging to N1(x) , for which this
number is max.
Advantages:
Reduces the routing overhead associated with table driven routing in addition to reducing the no.of broadcasts done.
Low connection setup time.
Reduced control overhead.
