OSPF and BGP Flashcards
Routing algorithm classification (Centralised)
- all routers have complete topology, link cost info
- “link state” algorithms
Routing algorithm classification
decentralized: iterative process of computation, exchange of info with neighbors
* routers initially only know link costs to attached neighbors
* “distance vector” algorithms
Link State Routing
- Each node knows its neighbors and cost to direct neighbors
- Each node broadcasts every other node this information (i.e., flooding)
- Each node learns complete network topology (i.e., graph)
- Use Dijkstra’s algorithm (see next slide) to compute shortest path
Dijkstra’s algorithm
- centralized: network topology, link costs known to all nodes
- accomplished via “link state broadcast”
- all nodes have same information
- computes least cost paths from one node (“source”) to all other nodes
- gives forwarding table for that node
- Iterative: after k iterations, know least cost path to k destinations
Dijkstra’s algorithm: an example
Dijkstra’s algorithm: discussion
algorithm complexity
algorithm complexity: n nodes
- each of n iteration: need to check all nodes, w, not in N’
- n(n+1)/2 comparisons: O(n2) complexity
- more efficient implementations possible: O(nlogn)
Dijkstra’s algorithm: discussion
- message complexity
message complexity:
- each router must broadcast its link state information to other n routers
- efficient (and interesting!) broadcast algorithms: O(n) link crossings to disseminate a broadcast message from one source
- each router’s message crosses O(n) links: overall message complexity: O(n2)
Comparison of LS and DV algorithms
- message complexity
LS: n routers, O(n2) messages sent
DV: exchange between neighbors;
convergence time varies - speed of convergence
LS: O(n2) algorithm, O(n2) messages- may have oscillations
DV: convergence time varies
- may have oscillations
- robustness: what happens if router
malfunctions?
LS:- router can advertise incorrect link cost
- each router computes only its own table
DV: - DV router can advertise incorrect path cost (“I have a really low-cost path to everywhere”): black-holing
- each router’s table used by others: errors propagate through network
Making routing work at Internet scale
our routing study thus far - idealized
- all routers identical
- network “flat”
… not true in practice
scale: billions of destinations:
- can’t store all destinations in routing tables!
- routing table exchange would swamp links!
administrative autonomy:
- Internet: a network of networks
- each network admin may want to control routing in its own network
Making routing work at Internet scale 2
aggregate routers into regions known as “autonomous systems” (AS) (a.k.a. “domains”)
intra-AS (aka “intra-domain”): routing among within same AS (“network”)
- all routers in AS must run same intradomain protocol
- routers in different AS can run different
intra-domain routing protocols
- gateway router: at “edge” of its own AS, has link(s) to router(s) in other AS’es
inter-AS (aka “inter-domain”): routing among AS’es
- gateways perform inter-domain routing (as well as intra-domain routing)
Making routing work at Internet scale:
Interconnected ASes
forwarding table configured by intraand inter-AS routing algorithms
- intra-AS routing determine entries for
destinations within AS
- inter-AS & intra-AS determine entries
for external destinations
Inter-AS routing: a role in intradomain forwarding
§ suppose router in AS1 receives
datagram destined outside of AS1:
* router should forward packet to gateway router in AS1, but which one?
AS1 inter-domain routing must:
1. learn which destinations reachable through AS2, which through AS3
2. propagate this reachability info to all routers in AS1
OSPF (Open Shortest Path First) routing
- “open”: publicly available
- classic link-state
- each router floods OSPF link-state advertisements (directly over IP rather than using TCP/UDP) to all other routers in entire AS
- multiple link costs metrics possible: bandwidth, delay
- Each router then locally runs Dijkstra’s shortest-path algorithm to determine a shortest-path tree to all subnets, with itself as the root node.
OSPF routing scalability
- Scaling routing within a single AS (i.e., domain) can be challenging as well!
- A single ISP can be very large
- Challenging to run LS or DV routing at such scale
Making OSPF routing more scalable: Hierarchy
- two-level hierarchy: local area, backbone.
- link-state advertisements flooded only in area, or backbone
- each node has detailed area topology; only knows direction to reach other destinations