Content

1. Routing
   1. Link State Routing Algorithm
      1. Flooding
      2. Dijkstra's Algorithm
      3. Forwarding Table
   2. Distance Vector Routing Algorithm
      1. Bellman-Ford Algoritm
      2. Forwarding Table
      3. Counting-to-Infinity Problem
      4. Loop-Breaking Heuristics
2. Routing in the Internet
   1. Hierarchical Routing
      1. Intra-AS Protocols
         1. OSPF
      2. Inter-AS Protocols
         1. Border Gateway Protocol

Routing

• Network graph
  • Nodes: routers
  • Edges: physical/logical linkages
  • Labels: costs
    • Delay, money, congestion, distance, political factors
  • Best route?
    • Min delay/money/hop? Max bandwidth/reliability?
• Attributes
  • Dynamic
    • Routing algorithm changes as network traffic loads or topology changes
  • Distributed
    • Routing computation takes place at routers
  • Global info
    • Complete info about link connectivity & link costs of the network
  • Decentralized info
    • No node has complet info

Link State Routing Algorithm

Dynamic, distributed, global info. e.g. OSPF, IS-IS.

1. Routers discover their immediate neighbors & cost
2. Link state broadcast: construct a LSP (link state packet/link state advertisement) telling everyone what they know (neighbors, cost)
   • LSP
     • id of router
     • List of neighbors & costs
     • SEQNO
     • TTL
   • Based on reliable controlled flooding
3. Get LSPs from other routers & build topology of the network
4. Compute shortest paths to every other routers -> forwarding table

Flooding

When router receives packets, forward to neighbor nodes except the source one. Based on reliable transmission - ack & retransmission.

• Controlled flooding: avoid exponentially increased number of packets
  • SEQNO
    • Stamped on newly generated LSPs
    • Router stores most recently recieved LSPs; discards already seen ones
  • TTL
    • Discard packets after decrementing TTL to 0
    • Decrement TTL in database periodically
      • If other routers reboot, SEQNO may get duplicated, but those should not be discarded!

Dijkstra's Algorithm

N' = {u}, D(u) = 0
for all v != u:
    D(v) = c(u, v) if v neighbor of u else inf
while (N != N'):
    let w = min D in {N - N'}
    for edge w->v:
        if v !in N and D(v) > D(w) + c(w, v):
            D(v) = D(w) + c(w, v)
    N' |= w

Forwarding Table

Dest | Cost | Nexthop

Distance Vector Routing Algorithm

Dynamic, distributed, decentralized info.
Each node sends its distance vector to its neighbors upon change in its view of network asynchronously (at its own schedule)

Bellman-Ford Algorithm

Init:
    Dii = 0
    Dij = c(i, j), Nexthop = j for neighbors
    Dik = inf, Nexthop = -1 for non-neighbors
Loop:
    OnEvent:
        - Receive DV from neighbor j, keep in db
        - Detect link change to some neighbors
    Update:
        For each dest d, find min dist via any neighbor k:
            Did' = min_k_in_neighbors(c(i, k) + Dkd)
            Replace old entry by (k, Did')
        If any entry updated:
            Send new DV to all neighbors

Forwarding Table

Dest | Nexthop | Distance

Counting-to-Infinity Problem

• Good news (shorter route info) delivers fast
• Bad news (broken linkage) delivers slowly & routers cannot know whether it is on somebody else's path

Loop-Breaking Heuristics

• Set infinity to small value
• Split horizon with poison reverse
  • If some distance is based on some node, tell that node it's infinity

Routing in the Internet

• Challenges so far
  • Scale: storing all information in a forwarding table
    • CIDR aggregation important
    • Routing table exchange swamps links
  • Administrative autonomy: each network administrator may want to control routing in its network

Hierarchical Routing

• Autonomous Systems (AS)
  • Intra-AS routers run the same routing protocol
• Gateway router
  • Run intra-AS routing protocol as a member in AS
  • Run inter-AS routing protocol to exchange reachability information with peer router of neighborhood AS
  • Distribute reachability info to internal routers
• Forwarding table
  • Intra-AS for internal dest
  • Intra-AS & inter-AS for external dest

Intra-AS Protocols

Or Interior Gateway Protocol (IGP)s.

• Routing Information Protocol (RIP) DV
• Open Shortest Path First (OSPF) LS
• Interior Gateway Routing Protocol (IGRP) DV

OSPF

• Link-state approach
• Transmitted directly on IP datagrams
• Support a variety of cost metrics
• Support load-balancing across equal-cost routes
• Support separate paths for each IP type-of-service
• Support authentication scheme
• Support CIDR aggregation
• Multicast for LSPs to reduce traffic
• Network
  • Backbone
    • Connected to all areas
    • Route traffic between areas
  • Area
    • Nodes within get complete area topology
      • Reduced LSP traffic, LS db size & processing overhead
    • Knows route to destination outside area, not topology
  • Area border routers
    • Overlapping backbone & area
    • Topology info for both
  • AS boundary router
    • Links to other AS

Inter-AS Protocols

Border Gateway Protocol

Routes to subnets, not hosts. Allows subnets to advertise its existence to rest of internet.

• AS can:
  • Obtain reachability info of neighboring ASs
    • When AS advertises an IP prefix to others, it promises to forward datagrams toward that IP prefix
  • Propagate reachability info to internal routers
  • Determine good routes based on reachability info & policy
• BGP session: semi-permanent TCP connection
  • iBGP: BGP peers within the same AS
  • eBGP: BGP peers of different ASs
  • BGP peers may not be directly/physically connected; all network details hidden
  • When router learns new prefix, create entry or that prefix
• Advertised prefix: prefix + attribute = route
  • Attribute
    • AS-PATH: passing ASs
    • Path vector protocol: reveal exact sequence of ASs used for a destination subnet; avoids count-to-infinity problem
• BGP policy: nodes can control traffic (accept/reject route advertisement) e.g. not routing to non-customers; not telling connection info to avoid traffic passing through