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
Internet inter-AS routing: BGP
- BGP (Border Gateway Protocol): the de facto inter-domain routing protocol
- “glue that holds the Internet together”
- allows subnet to advertise its existence, and the destinations it can reach, to rest of Internet: “I am here, here is who I can reach, and how”
- BGP provides each AS a means to:
- eBGP: obtain subnet reachability information from neighboring ASes
- iBGP: propagate reachability information to all AS-internal routers.
- determine “good” routes to other networks based on reachability information and policy
eBGP, iBGP connections
BGP basics: a path vector protocol
- BGP session: two BGP routers (“peers”) exchange BGP messages over semi-permanent TCP connection:
- advertising paths to different destination network prefixes (BGP is a “path vector” protocol)
- when AS3 gateway 3a advertises path AS3, IP prefix to AS2 gateway 2c:
- AS3 promises to AS2 that it will forward datagrams towards that IP prefix
Path attributes and BGP routes
- BGP advertised route: prefix + attributes
- prefix: destination being advertised
- two important attributes:
- AS-PATH: list of ASes through which prefix advertisement has passed
- NEXT-HOP: indicates specific internal-AS router to next-hop AS
- policy-based routing:
- gateway receiving route advertisement uses import policy to accept/decline path (e.g., never route through AS Y).
- AS policy also determines whether to advertise path to other other neighboring ASes
BGP path advertisement
- AS2 router 2c receives path advertisement AS3, IP prefix X (via eBGP) from AS3 router
3a - based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates (via iBGP) to all
AS2 routers - based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2, AS3, X to AS1
router 1c
BGP path advertisement (more)
- gateway router may learn about multiple paths to destination:
§ AS1 gateway router 1c learns path AS2,AS3,X from 2a
§ AS1 gateway router 1c learns path AS3,X from 3a
§ based on policy, AS1 gateway router 1c chooses path AS3,X and advertises path within AS1 via iBGP
Why different Intra-, Inter-AS routing ?
policy:
- inter-AS: admin wants control over how its traffic routed, who routes through its network
- intra-AS: single admin, so policy less of an issue
scale:
- hierarchical routing saves table size, reduced update traffic
performance:
- intra-AS: can focus on performance
- inter-AS: policy dominates over performance
Hot potato routing
- 2d learns (via iBGP) it can route to X via 2a or 2c
- hot potato routing: choose local gateway that has least intra-domain cost (e.g., 2d chooses 2a, even though more AS hops to X): don’t worry
about inter-domain cost!
BGP: achieving policy via advertisements
ISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs – a typical “real world” policy)
- A advertises path Aw to B and to C
- B chooses not to advertise BAw to C!
- B gets no “revenue” for routing CBAw, since none of C, A, w are B’s customers
- C does not learn about CBAw path
- C will route CAw (not using B) to get to w
BGP: achieving policy via advertisements (more)
ISP only wants to route traffic to/from its customer networks (does not want to carry transit traffic between other ISPs – a typical “real world” policy)
§ A,B,C are provider networks
§ x,w,y are customer (of provider networks)
§ x is multi-homed: attached to two networks
§ policy to enforce: x does not want to route from B to C via x
§ .. so x will not advertise to B a route to C
BGP route selection
- router may learn about more than one route to destination AS, selects route based on:
1. local preference value attribute: policy decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria
