Scribd Logo
Upload

Welcome to Scribd!

  • 23 views

    Routing Algorithms

    Uploaded by

    Lav Vijayvargiya
    Routing algorithms determine the best paths between nodes in a network. They use a graph abstraction where nodes represent routers and edges represent links between them. Global routing algorithms have a complete view of the topology while decentralized algorithms iteratively exchange information with neighbors. Dijkstra's algorithm is an example link-state routing algorithm that computes the shortest path from one node to all others. Hierarchical routing divides large networks into autonomous systems (AS) that each run intra-AS routing internally and interconnect through gateway routers using inter-AS routing.

    Copyright:

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

    Routing Algorithms

    Uploaded by

    Lav Vijayvargiya
    23 views13 pages
    Routing algorithms determine the best paths between nodes in a network. They use a graph abstraction where nodes represent routers and edges represent links between them. Global routing algorithms have a complete view of the topology while decentralized algorithms iteratively exchange information with neighbors. Dijkstra's algorithm is an example link-state routing algorithm that computes the shortest path from one node to all others. Hierarchical routing divides large networks into autonomous systems (AS) that each run intra-AS routing internally and interconnect through gateway routers using inter-AS routing.

    Original Description:

    Routing Protocols

    Original Title

    Routing

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Routing algorithms determine the best paths between nodes in a network. They use a graph abstraction where nodes represent routers and edges represent links between them. Global routing algorithms have a complete view of the topology while decentralized algorithms iteratively exchange information with neighbors. Dijkstra's algorithm is an example link-state routing algorithm that computes the shortest path from one node to all others. Hierarchical routing divides large networks into autonomous systems (AS) that each run intra-AS routing internally and interconnect through gateway routers using inter-AS routing.

    Copyright:

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

    Routing Algorithms

    Uploaded by

    Lav Vijayvargiya
    Routing algorithms determine the best paths between nodes in a network. They use a graph abstraction where nodes represent routers and edges represent links between them. Global routing algorithms have a complete view of the topology while decentralized algorithms iteratively exchange information with neighbors. Dijkstra's algorithm is an example link-state routing algorithm that computes the shortest path from one node to all others. Hierarchical routing divides large networks into autonomous systems (AS) that each run intra-AS routing internally and interconnect through gateway routers using inter-AS routing.

    Copyright:

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

    Routing algorithms

    Interplay between routing


    and forwarding
    routing algorithm

    local forwarding table


    header value output link
    0100 3
    0101 2
    0111 2
    1001 1

    value in arriving
    packet’s header
    0111 1

    3 2
    Graph abstraction
    5
    3
    v w 5
    2
    u 2 1 z
    3
    1 2
    Graph: G = (N,E)
    x 1
    y

    N = set of routers = { u, v, w, x, y, z }

    E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z), (u,w)}

    Remark: Graph abstraction is useful in other network contexts

    Example: P2P, where N is set of peers and E is set of TCP connections


    Graph abstraction: costs
    5 • c(x,x’) = cost of link (x,x’)
    3
    v w 5
    2 - e.g., c(w,z) = 5
    u 2 1 z
    3 • cost could always be 1, or
    1 2
    x 1
    y inversely related to bandwidth,

    Cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

    Question: What’s the least-cost path between u and z ?

    Routing algorithm: algorithm that finds least-cost path


    Routing Algorithm
    classification
    Global or decentralized  Static or dynamic?
    information?
    Static:
    Global:

    all routers have complete 

    routes change slowly over 
    topology, link cost info time
    • “link state” algorithms Dynamic: 
    Decentralized: 

    router knows physically­

    routes change more 
    connected neighbors, link costs to  quickly
    neighbors 
    periodic update

    iterative process of computation,
    exchange of info with neighbors

    in response to link 
    • “distance vector” algorithms cost changes
    Link state Routing algorithm
    A Link-State Routing Algorithm

    Dijkstra’s algorithm Notation:

    net topology, link costs known to  • c(x,y): link cost from node x to 
    all nodes y;  = ∞ if not direct neighbors

    accomplished via “link state  • D(v): current value of cost of 
    broadcast”  path from source to dest. v

    all nodes have same info
    • p(v): predecessor node along 

    computes least cost paths from  path from source to v
    one node (‘source”) to all other 
    nodes • N': set of nodes whose least cost 

    gives forwarding table for  path definitively known
    that node

    iterative: after k iterations, know 
    least cost path to k dest.’s
    Dijsktra’s Algorithm
    1 Initialization:
    2 N' = {u}
    3 for all nodes v
    4 if v adjacent to u
    5 then D(v) = c(u,v)
    6 else D(v) = ∞
    7
    8 Loop
    9 find w not in N' such that D(w) is a minimum
    10 add w to N'
    11 update D(v) for all v adjacent to w and not in N' :
    12 D(v) = min( D(v), D(w) + c(w,v) )
    13 /* new cost to v is either old cost to v or known
    14 shortest path cost to w plus cost from w to v */
    15 until all nodes in N'
    Dijkstra’s algorithm: example
    Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
    0 u 2,u 5,u 1,u ∞ ∞
    1 ux 2,u 4,x 2,x ∞
    2 uxy 2,u 3,y 4,y
    3 uxyv 3,y 4,y
    4 uxyvw 4,y
    5 uxyvwz

    5
    3
    v w 5
    2
    u 2 1 z
    3
    1 2
    x 1
    y
    1 C
    A 1
    2
    5
    1 F E
    1 3 2
    2
    B D

    1 C
    A 1

    E 3 F
    1 1
    2
    2
    B D
    Hierarchical Routing
    Our routing study thus far - idealization
    • all routers identical
    • network “flat”
    … not true in practice
    scale: with 200 million destinations:
     can’t store all dest’s in routing tables! administrative autonomy
     routing table exchange would swamp links!  
    internet = network of 
    networks

    each network admin may 
    want to control routing in 
    its own network
    Hierarchical Routing


    aggregate routers into  Gateway router
    regions, “autonomous  
    Direct link to router in 
    systems” (AS)
    another AS

    routers in same AS run 
    same routing protocol
    – “intra­AS” routing protocol

    routers in different AS can 
    run different intra­AS 
    routing protocol
    Interconnected AS’s
    Gate Way
    Routers
    3c
    3a 2c
    3b 2a
    AS3 2b
    1c AS2
    1a 1b AS1
    1d

    Forwarding table is 
    configured by both intra­ 
    and inter­AS routing 
    Intra-AS
    Routing
    Inter-AS
    Routing
    algorithm
    algorithm algorithm 
    Intra ­AS sets entries for 
    Forwarding internal dests
    table 
    Inter­AS & Intra­As sets 
    entries for external dests 

    You might also like