Topic 9 - Routing

Router

Network device that forwards packets based on the best available routing information (if not intended for itself)

Border Routers

advertise it’s internal routes outwards and shares information about outer routes to its inner routers

Network Operator

Central Authority responsible for managing, operating, and maintaining a network (collection of hosts and routers)

Autonomous System (AS)

A set of IP networks and routers under the control of a single network operator and identified with a unique Autonomous System Number

How do AS’s operate

they use a consistent, internally defined routing policy

AS Path

Ordered list of ASNs that routing information has traversed to reach a particular network, helps prevent loops and finds the best route

EGP (Exterior Gateway Protocol)

Routes between Autonomous Systems using BGP (between networks)

IGP (Interior Gateway Protocols)

Connects routers inside on Autonomous System using OSPF, IS-IS, Legacy, or RIP (Inside a network)

BGP (Border Gateway Protocol)

Helps different AS’s send data between to eachother

How Does BGP determine the best path?

It uses a 12 step algorithm (6-12 aren’t important)

What Are BGP’s Top 5 factors?

1.) Next-hop reachability – can I actually reach it?

2.) Highest weight – the router’s own preference.

3.) Highest local preference – what the network policy prefers.

4.) Locally originated routes – prefers directly connected routes.

5.) Shortest (AS) Path

What’s it called when two Customers talk to each other within the same AS with no cost to Internal networks

Settlement Free Peering

Net Neutrality

all internet traffic should be treated equally, no matter the source.

How does Dijkstra’s Algorithm help find the shortest path? (SSSP)

It produces a Shortest Path Tree representing the shortest path cost wise from a single source node to every other node

How does Dijkstra’s Algorithm work? (Best First Search)

Using a Priority Queue and an Array,

-You start at the source node and branch out to every connected node, putting them in the priority queue sorted from least to greatest.

-Then you choose the node with the least cost, pop it from the queue, and note that path in the array,

-Traverse to the selected Node, keeping track of the accrued cost, and branch out to every connected node

-Repeat the process, updating the tables accordingly and ignoring paths to already accounted for nodes in the array table

-For previously recorded paths who’s node has already been accounted for, discard them

-When you arrive at a Node that already has every path accounted for, just go back to the priority queue and evaluate from there

What are the Link-State Routing Concepts

Dynamic Graphs, LSA, LSDB

Dynamic Graph

Routers share information about which networks they’re connected to, If a link goes down or new one appears, routers update each other. This keeps routing as a distributed proble

LSA (Link-State Advertisement)

A message a router sends to share what it’s connected to. Broadcasted to all routers (via 224.0.0.5), Used by OSPF to share topology info.

LSDB (Link-State Database)

A representation of the AS topology, Routers use LSDB to:

-Calculate shortest paths

-Build their routing table

-If a link or router goes down, an LSA update is shared to reflect changes.

How does the Process work as a whole?

-Routers share LSA messages with neighbors.

-Each router builds a LSDB (a map of the network).

-Routers run Dijkstra’s Algorithm to find the shortest paths.

-They use that info to create their routing table.

-When something changes (like a link failure), they send a new LSA update to everyone.