4-Routing

Question 1

ISP, Content Provider, Campus network or any independently operated network

Answer 1

Autonomous Systems (AS) or ASes

Question 2

Routing within an AS

Answer 2

Intradomain Routing

Question 3

Routing traffic between ASes

Answer 3

Interdomain Routing

Question 4

A high-performance backbone network created by the Internet2 community in the late 1990s. In 2007 it was retired and the upgraded network became known as the “Internet2 Network”.

Answer 4

Abeline network (A Single AS research network in US)

Question 5

There are 2 types of Intradomain routing

Answer 5

1) Distance Vector

2) Link State

Question 6

Distance Vector Routing

Answer 6

1) Each node sends multiple distance vectors to each of its neighbors (copies of own routing table)
2) Routers compute costs to each destination based on shortest available path

Question 7

Distance Vector Routing is based on

Answer 7

Bellman-Ford algorithm

dx(y) = minv(c(x1v)+dv(y))

Question 8

What is the solutiopn to the “Count to infinity problem?”

Answer 8

Poison Reverse

Question 9

• Circa 1982
• edges have unit cost
• “infinity” = 16
• table refresh: 30 seconds (or when updates occur)

Answer 9

Routing Information Protocol (RIP)

Question 10

More on RIP

Answer 10

When an entry changes, it sends the copy of that update to all of it’s neighbors except the one that caused the update (also known as the “split Horizon” rule)

Question 11

Alternative to RIP

Answer 11

Link-State routing

Question 12

Link-State Routing (scale is an issue though)

Answer 12

• Each node distributes a network map to every other node in the network
• Each node performs a shortest path computation between itself and all other nodes in the network

Question 13

Shortest path computation

Answer 13

Dijkstra algorithm

D(v) = min(c(v,w)*D(w), D(v))

Question 14

2 common link-state routing protocols

Answer 14

1) Open Shortest Paths First (OSPF) ->Areas
2) Intermediate System- Intermediate System (IS-IS) -large ISP and most commonly used in large transit networks today ->Levels

Question 15

Coping with Scale

Answer 15

Hierarchy

Question 16

ASes advertise reach-ability to some destination by sending announcements or route advertisements. the protocol used to advertise these announcements is called

Answer 16

Border Gateway Protocol (BGP)

Question 17

Sequence of AS numbers that describe the route to the destination (Sequence of ASes that the route traversed to reach the recipient AS)

Answer 17

AS Path (1 BGP route attributes)

Question 18

The last AS

Answer 18

The origin AS

Question 19

Responsible for transmitting routing information between border routers of adjacent ASes about external destinations

Answer 19

external BGP or eBGP

Question 20

Responsible for disseminating BGP route advertisements about external destinations to routers inside any particular AS

Answer 20

internal BGP or iBGP

Question 21

Routes inside an AS to internal destinations

Answer 21

Intradomain routing protocol or IGP

Question 22

BGP Route Selection Process

Answer 22

1) Prefer a route with the higher “local preference” value
2) Shortest AS path length
3) Multi-exit discriminator (MED)
- Lower values
- Only comparable among routes from same AS
4) Shortest IGP path (“hot potato” routing)
5) Tiebreak -> “most stable” or advertised the longest -> lowest router ID typically

Question 23

Local Preference (Local Pref)

Answer 23

Allows operator to configure the router to assign different preference values to each of the routes that it learns

Question 24

Local Preference (Local Pref)

Answer 24

Sometimes used to control OUTBOUND traffic

Question 25

Local Preference (Local Pref)

Answer 25

Extremely useful for configuring Primary and Backup route

Question 26

Tag on a route

Answer 26

“Community”

Question 27

Multiple Exit Discriminator (MED)

Answer 27

To override “hot potato” routing behavior - ASes may use MED values (remember NY and SF example)

Question 28

Interdomain Routing Business Models

Answer 28

3 types and their rankings:
1) Customer, > 2) Peering (settlement free peering) , > 3) Provider

Money is flowing in the direction of the provider

Question 29

Interdomain Routing Business Models

Answer 29

From Customer: Everyone
Provider: only Customers
Peer: other customers

Question 30

Interdomain Routing Can Oscillate

Answer 30

BGP corrective property called “Saftey” by Griffin

But regional and paid peering can violate - so BGP is not guaranteed to be stable… due to Oscillation.