Intradomain and Interdomain Routing Algorithms

• Intradomain routing involves routers in the same administrative domain.
• Interdomain routing involves routers in different administrative domains.
• Intradomain routing algorithms are also known as Interior Gateway Protocols (IGPs).
• Two major classes of algorithms include link-state and distance-vector algorithms.
• In these algorithms, routers are represented as nodes, and links between routers are edges with associated costs.
• The goal is to find the least-cost path between two nodes.

Representing Edge Weights

• Length of the cable
• Time delay to traverse the link
• Monetary cost
• Link capacity
• Current load on the link

Linkstate Routing Algorithm

• In the linkstate routing protocol, all nodes know the link costs and network topology via broadcasting.
• u represents the source node.
• v represents every other node in the network.
• D(v) represents the cost of the current least-cost path from u to v.
• p(v) represents the previous node along the current least-cost path from u to v.
• N' represents the subset of nodes along the current least-cost path from u to v.
• The algorithm initializes all known least-cost paths from u to its directly attached neighbors.
• Costs for nodes not directly attached to u are initialized to infinity.
• The set N' initially includes only the source node u.
• The algorithm iterates, finding the node w not in N' with the minimum D(w), adding w to N', and updating D(v) for each neighbor v of w not in N'.

Linkstate Routing Algorithm - Computational Complexity

• The computational complexity is determined by the number of computations needed to find the least-cost paths.
• In the first iteration, all nodes are searched to find the node with the minimum path cost.
• The number of nodes searched decreases with each iteration.
• The complexity of the algorithm is in the order of O(n^2).
• Node x executes the same number of iterations as node u, regardless of the number of immediate neighbors.

Distance Vector Routing

• The Distance Vector (DV) routing algorithm is iterative, asynchronous, and distributed.
• Each node receives information from its direct neighbors and distributes the results back after calculation.
• It is based on the Bellman-Ford Algorithm.
• The least-cost path from x to y is defined as dx(y) = min{c(x,v) + dv(y)}, where the minimum is computed over all neighbors v of x.

DV Algorithm Details

• Each node maintains its own distance vector with costs to reach every other node.
• Nodes periodically send their distance vectors to neighbor nodes.
• Neighbor nodes use these distance vectors to update their own views of the network by exchanging distance vectors.

Node Responsibilities

• Dx(y) is the least cost from x to y.
• Node x calculates the cost to each of its neighbor v: c(x,v).
• Dx = [Dx(y): y in N] is node x's distance vector, estimating costs to all destinations y in N. -Dv = [Dv(y): y ∈ N] is maintained for each neighbor v.

Vector Updates

• Each node x updates its distance vector using the Bellman-Ford equation: Dx(y) = minv{c(x,v) + Dv(y)} for each destination node y.
• Node x computes the least cost to reach destination y by considering costs to reach neighbor v and then the least cost from v to y.

Distance Vector Routing Example

• du(z)=min{ c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) }
• du(z) = min{2+5, 1+3, 5+3} = min {7,4,8} = 4

Distance Vector Routing Algorithm Formal Definition

• Initialization

  • for all destinations y in N:
    • Dx(y) = c(x,y) /* if y is not a neighbor then c(x,y) = ∞ */
  • for each neighbor w -Dv(y) = ? for all destinations y in N
  • for each neighbor w:
    • send distance vector Dw = [Dw(y): y in N] to w

• Algorithm Loop

  • wait (until I see a link cost change to some neighbor w or until I receive a distance vector from some neighbor w) -for each y in N: -Dx(y) = min{c(x,v) + Dv(y)} -if D(y) changed for any destination y
    • send distance vector Dx = [Dx(y): y in N] to all neighbors -forever

Link Cost Changes and Failures in DV

Scenario 1: Link cost decreases and advertises faster amoung nodes. Scenario 2: Link cost increases, which takes longer to propagate amount nodes. It is known as Count-to-infinity problem.

Poison Reverse

• Poison reverse is a solution for the count-to-infinity problem.
• If z reaches x through y, z advertises to y that Dz(x) = infinity, even though z knows Dz(x) = 5.
• This prevents y from routing to x via z and vice versa by poisoning the path from z to y.
• Things change when the cost from X to y changes to 60. y will update its table and send packet to x directly with cost Dy (x)=60
• It will inform z about its new cost to x, after this update is received.

Distance Vector Protocol - RIP

• Routing Information Protocol (RIP) is based on the Distance Vector protocol.
• The first version, released with BSD Unix, uses hop count as a metric assuming link cost as 1.
• Routing updates are exchanged periodically between neighbors using RIP response messages, which contain sender's distances to destination subnets.
• Each router maintains a routing table with destination subnets, the next router on the shortest path, and the number of hops to the destination.
• Routers merge advertisements received with their old routing table.

Link State Protocol - OSPF

• An OSPF autonomous system can be configured hierarchically into areas.
• Every OSPF area is assigned a 32 bit number
• One of these areas has to be the backbone are.
• The main role of back bone is to route traffic between other areas
• Each area runs its own
• OSPF link-state routing algorithm.
• Each router in an area broadcasts its link state to all other routers in that area.
• Area border routers manage routing packets outside their areas.
• OSPF costs can be set proportionally to link capacity or set to one. OSPF includes the authentication of the messages exchanged to confirm the identity.

How does OSPF send its messages?

• Uses Link State Advertisements (LSAs).
• LSA communicates the router's local routing topology to all other local routers in the same OSPF area.
• Flooded to every router in the domain
• 30 minute default refresh rate.
• First LSA change is stored, subsequent are stored as duplicates.
• Each node maintains a RIP Table (Routing Table), which will have one row for each subnet in the AS.
• RIP version 2 allows subnet entries to be aggregated using route aggregation techniques.
• If a router does not hear from its neighbor at least once every 180 seconds, that neighbor is considered to be no longer reachable (broken link). In this case, the local routing table is modified and changes are propagated.

OSPF and Link State Advertisements (LSAs)

• Routers send request and response messages over UDP, using port number 520, which is layered on top of network-layer IP protocol. RIP is actually implemented as an application-level process.

OSPF Flowchart Explained

• Processing tasks begin at receipt of an LS update packet (T1). For every LSA unpacked from the update packet -The OSPF protocol checks whether it is a new or a duplicate LSA. -If it is new: -the database is updated -an SPF calculation is scheduled (T2).
• After, the the LSA is flooded out (T3).
• LSAs are prepared and flooded out as an LS Update packet to the next router (T4).
• SPF calculation within the router (T5 and T6).

How To Process Packets Fast

• OSPF processing consists of: - Receive LS Update packet which contain LSA - SPF caclulations - FIB
• CPU uses the OSPF updates from neighbouring routers
• Consistency is maintained through the link-state database.
• shortest path first (SPF) algorithm

Hot Potato Routing

• In large networks, routers rely both on interdomain and intradomain routing protocols to route the traffic.

Operation

• Routers use intradomain routing protocols to find the best path for the traffic within the local network.
• When the destination is outside of the local network: -The traffic will travel towards the networks exit (egress points)

Traffic Engineering Framework

The three main components that are involved are:

• measure, model, and control.

The Model Includes:

• Predicting the traffic flow through the network based on the IGP configuration
• Calculating the shortest path between two routers.
• Splitting the traffic almost evenly over these paths when there are multiple shortest paths between two routers.

Measure

• The efficient assignment of link weights depends on the real time view of the network state which: -The operational routers and links -The link capacity and IGP parameters configuration

Simple Network Management Protocol (SNMP)

• Is what collects the data regarding network elements.
• A software router could act as an IGP route monitor by participating in OSPF/IS-IS with operational routers and reporting real time topology information.

Estimate of The Traffic In The Network

• SNMP Management Information Bases (MIBs)
• Combining packet-level measurements at the network edge using the information in routing tables
• Observing the aggregate load on the links along with the routing data
• Direct observation of the traffic using new packet sampling techniques