Scribd Logo
Upload

Welcome to Scribd!

  • 398 views

    Cedar

    Uploaded by

    Azeem Khan
    This document discusses several hybrid routing protocols including CEDAR, ZRP, ZHLS, and OLSR. It focuses on describing the CEDAR protocol. CEDAR extracts core nodes that approximate a minimum dominating set. Core nodes broadcast packets throughout the network and find paths between other core nodes to route packets. The protocol establishes routes in two phases: finding a core path and then a QoS feasible path over the core path. It provides advantages of reducing overhead through core nodes but relies heavily on the core nodes, whose movements can impact performance.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Cedar

    Uploaded by

    Azeem Khan
    398 views13 pages
    This document discusses several hybrid routing protocols including CEDAR, ZRP, ZHLS, and OLSR. It focuses on describing the CEDAR protocol. CEDAR extracts core nodes that approximate a minimum dominating set. Core nodes broadcast packets throughout the network and find paths between other core nodes to route packets. The protocol establishes routes in two phases: finding a core path and then a QoS feasible path over the core path. It provides advantages of reducing overhead through core nodes but relies heavily on the core nodes, whose movements can impact performance.

    Original Description:

    pjvklvbkldfbpjpovkl

    Original Title

    cedar ppt

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses several hybrid routing protocols including CEDAR, ZRP, ZHLS, and OLSR. It focuses on describing the CEDAR protocol. CEDAR extracts core nodes that approximate a minimum dominating set. Core nodes broadcast packets throughout the network and find paths between other core nodes to route packets. The protocol establishes routes in two phases: finding a core path and then a QoS feasible path over the core path. It provides advantages of reducing overhead through core nodes but relies heavily on the core nodes, whose movements can impact performance.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    398 views13 pages

    Cedar

    Uploaded by

    Azeem Khan
    This document discusses several hybrid routing protocols including CEDAR, ZRP, ZHLS, and OLSR. It focuses on describing the CEDAR protocol. CEDAR extracts core nodes that approximate a minimum dominating set. Core nodes broadcast packets throughout the network and find paths between other core nodes to route packets. The protocol establishes routes in two phases: finding a core path and then a QoS feasible path over the core path. It provides advantages of reducing overhead through core nodes but relies heavily on the core nodes, whose movements can impact performance.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 13

    Hybrid Routing Protocols

     Core Extraction Distributed Ad Hoc Routing(CEDAR)


    protocol
     Zone Routing Protocol (ZRP)
     Zone-based Hierarchical Link State (ZHLS) Routing
    Protocol
     Routing Protocols with Efficient Flooding Mechanisms
     Preferred link–based rooting(PLBR) protocols
     Neighbor Degree-based Preferred Link Algorithm
     Weight-based Preferred Link algorithm
     Optimized link state routing(OSLR) protocol
    Basic concept of core extraction
    • There is at least on core node every three hops.
    • Every node picks up a node within a distance
    not greater than one hop from it, as its dominator.
    • The core consists of the dominators and tunnels.
    • Tunnels consist of at most two intermediate non-core
    nodes .
    • Core nodes advertise their presence in the three-hop
    Neighborhood
    CEDAR
     CEDAR is based on extracting core
    nodes,which together approximate
    the minimum dominating set
     A dominating set (DS) of a graph is
    defined as a set of nodes that every node
    in the graph is either in the DS or
    a neighbor of some node in the DS.
     There exists at least one core node
    within three hops
    • Core broadcast: core nodes transmit any
    packet throughout the network in the unicast
    – Virtual link: the path between two core nodes
    • QoS Path:
    – First phase: Finding a core path from the source
    node to the destination
    – Second phase: Finding a QoS feasible path over
    the core path
    Route Establishment in CEDAR

    Phase1:
    Finding core nodes
     Establishing virtual
    links
    Phase2:
     Check local topology
     Initiate a
    RouteRequest
     Core broadcast
     RouteReply
     Core path
    First phase

    • A node initiates a RouteRequest if the destination is


    not in the local topology table of its core node.
    • Source core node uses core broadcast to send
    RouteRequest to neighboring core nodes.
    • The recipient core node forwards the RouteRequest to
    its neighboring core nodes if the destination is not its
    core member.
    • A core node which has the destination as its core
    member replies to the source core.
    Second phase

    • MidCore: the farthest core node in the core path with


    required bandwidth found by the source core.
    • When the source finds a MidCore, MidCore becomes
    the new source core and finds another MidCore in the
    next iteration until a path to the destination with the
    required bandwidth is found
     Link break:
     The node after which the break occurred
    • sends a notification of failure
    • begins to find a new path from it to
    the destination.
    • rejects every received packet till the moment
    it finds a new path to the
    destination.
     Meanwhile, as the source receives
    the notification message
    • it stops to transmit
    • tries to find a new route to the destination.
    G A CEDAR: routing example
    H B C D Core Node
    E
    F Links that node B aware of
    S J K

    G A

    H B C D
    E
    F
    Links that node E aware of
    S J K Partial Route constructed by B

    G A

    Disadvantages of CEDAR: H B C D
    E
    ― Sub-optimal route
    ― Core nodes being bottleneck F
    S J K

    Complete, with last 2 nodes determined by E


    Li Cheng, ELG5125
     Advantage:

    • utilization of core nodes reduces the traffic overhead.


    • It performs both routing and QoS
    path computation very efficiently with the
    help of core nodes.
     Disadvantage:

    • The route establishment and computation is relied on


    core nodes
    • Core nodes’ movement affects the performance of
    the protocol core
    • The movement of the core nodes affects the
    performance of the protocol.
    • The update information of core nodes could cause
    a significant of control overhead
    Thank you

    You might also like