Lesson 4 - Routing

Question 1

Nuts and bolts that make routing possible

Answer 1

Naming, addressing, forwarding

Question 2

The internet is a collection of

Answer 2

10s of thousands of autonomous systems (AS’s)

Question 3

AS

Answer 3

• networks such as Comcast, Google, Georgia Tech

- ISP, content provider, campus network, any other independently operating network

Question 4

Internet routing involves 2 distinct types

Answer 4

• Intradomain (traffic routed inside any single AS)
• Interdomain (traffic routed between AS’s)
• Business relationships make interdomain routing so complicated

Question 5

Topology in AS consists of

Answer 5

• Nodes (“POPs”/points of presence). Typically located in dense population center to be close to POP’s of other providers for easier interconnection, and close to other customers for cheaper backhaul to customers
• Edges: connect nodes. Constrainted by fiber paths, which for the sake of convenience typically parallel major transportation routes such as railroads and highways.

Question 6

Abilene

Answer 6

Single AS topology - research network in the US

-GT is an AS that connects at the Atlanta POP of the Abilene network

Question 7

Southern Crossroads

Answer 7

Internet exchange point where Abilene connects to other universities in southeast near Atlanta

Question 8

Routing is

Answer 8

The process by which nodes discover where to forward traffic so that it reaches a certain node.

Question 9

2 types of intradomain routing

Answer 9

1. Distance vector
   - Routers compute paths based on shortest path available, using Bellman-Ford algorithm. When costs decrease, the network converges quickly, but one problem is when failures happen, bad news can travel slowly.
2. Link state
   - Prevailing alternative, used in most operational networks today
   - Each node distributes a network map to every other node in the network. Then, each node performs a shortest path computation between itself and all other nodes in the network.
   - Often called the Dijkstra shortest path routing algorithm

Question 10

Routing Information Protocol (RIP)

Answer 10

• Example of distance vector
• First version defined in 1982
• Infinity in count-to-infinity was 16
• Split horizon rule = tell all neighbors except for one that caused the update
• When a router or link fails in RIP, things can take minutes to stabilize
• Slow convergence and count to infinity = protocol designers look to alternatives

Question 11

2 common link state routing protocols

Answer 11

• Open shortest paths first (OSPF)
• Intermediate System - Intermediate System (IS-IS). In recent years, has gained increasing use in large ISP’s, more commonly used link state routing protocol in large transit networks today.

Question 12

1 problem with link state routing

Answer 12

Scale. Complexity of a link state routing protocol grows as n^3 where n is # of nodes in the network.

Question 13

Coping with scale using hierarchy

Answer 13

• OSPF has Areas (backbone is Area 0, and each area not in the backbone has an Area 0 router)
• IS-IS has Levels

Question 14

Each AS performs in

Answer 14

Its own best interest (economically, performance-objectives, etc.) and yet must cooperate to provide global connectivity

Question 15

BGP

Answer 15

• Border Gateway Protocol

- Each AS advertises reachability to some destination by sending route advertisements or announcements

Question 16

3 most important attributes of route advertisements

Answer 16

• Destination prefix (e.g. IP prefix for Georgia Tech)
• Next Hop (IP address of the router you need to send traffic to for that destination) - typically the IP address for the first router in the neighboring network
• AS path: sequence of AS #’s that describe the route to the destination. Nothing more than a sequence of AS’s that the route traversed to reach the recipient AS.

Question 17

Origin AS

Answer 17

The last AS along the AS path. Called this because it’s the AS that originated the advertisements for this IP prefix.

Question 18

EBGP

Answer 18

External BGP

BGP consisting of route advertisements solely between border routers of adjacent AS’s

Question 19

iBGP

Answer 19

Internal BGP
Used to transmit routes inside an AS for external destinations
Not to be confused with IGP

Question 20

IGP

Answer 20

Routes inside an AS to internal destinations

Question 21

BGP Route Selection Process

Answer 21

• Router in an AS might learn multiple routes to the same destination. It must select the single best route. This selection among multiple alternatives is BGP route selection process.
• Prefer router with higher “local preference” value

Question 22

Local preference

Answer 22

Numerical value that a network operator in local AS can assign to a particular route. It’s purely local, so it’s dropped in eBGP route advertisements, but allows local operator ability to explicitly state that one route should be preferred over the other

• If equally high local preference values, BGP prefers shortest AS path length
• Control how traffic leaves its AS en route to a destination
• Useful for configuring primary and backup routes

Question 23

Multi-Exit Discriminator

Answer 23

“MED”

• Value allows one AS to specify that one exit point in the network is more preferred than another
• Lower MED values are preferred
• Only applies when comparing routes advertised from same AS
• Not inherently comparable across routes advertised from different AS’s

Question 24

Hot potato routing

Answer 24

AS sends traffic to the neighboring AS via a path that traverses as little of its own network as possible
-Tie breaker in BGP route selection process is arbitrary, but typically operators prefer to use the route advertisement from the router with the lowest router ID, which is typically the neighboring router’s IP address

Question 25

BGP Community

Answer 25

Sometimes attached to a route by AS to affect how neighboring AS sets local preference. A community is nothing more than a fancy jargon word for a tag on a route. e.g. if AS 4 wants incoming traffic to route through AS 3 rather than 2, it can advertise BGP routes with “primary” and “backup”.
-Requires prior agreement typically

Question 26

All things being equal, routers in an AS will select the BGP route with the shortest ___ path cost to the next hop, resulting in hot potato routing

Answer 26

iGP

Question 27

MED _____ hot potato routing behavior

Answer 27

overrides

• typically not used in conventional business relationships
• sometimes used when a transit provider peers with a content provider. “Yes I’ll peer with you but it’s your responsibility to transport across the country.” Don’t want to provide free transit if both providers have routers on both coasts.

Question 28

Interdomain Routing Business Models - It’s all about

Answer 28

Routing money

Question 29

2 types of business relationships in the internet

Answer 29

• Customer/provider: money flows from customer to provider regardless of which direction traffic flows
• Peering: AS can exchange traffic with another AS free of charge. Sometimes also called Settlement-free Peering
• Most preferable route is through customer, 2nd through peer, 3rd through provider.

Question 30

Filtering/export decisions

Answer 30

1. Routes learned from customer - readvertise to everyone (otherwise only advertise to customers)
2. Routes learned from provider only advertised to customers, never other providers
3. Routes from peers only advertised to other customers.

If every AS in the internet followed the following rules exactly, then routing stability is guaranteed. Turns out, it’s not guaranteed

Question 31

Safety

Answer 31

BGP correctness property derived by Tim Griffin.
-If AS’s follow the ranking and export rules, safety is guaranteed, but there are various times where those rules are violated. Such examples include business relationships such as regional peering and paid peering – can occasionally cause these conditions to be violated.

Question 32

To this day, is BGP guaranteed to be stable in practice?

Answer 32

No. Many common practices result in the potential for oscillation to occur.

Question 33

Route selection

Answer 33

Where to forward packets

Question 34

Route propagation

Answer 34

Who to export routes to

Question 35

Usually you have ___ ISP per AS

Answer 35

1

Question 36

Why would an ISP choose to operate multiple As’s?

Answer 36

For business reasions – it would provide more autonomy to administrators of an ISP’s backbones in the United States and Europe

Question 37

BGP Decision Process

Answer 37

1. Highest LocalPref (controlled by local AS)
2. Lowest AS path length (controlled by neighbor AS)
3. Lowest origin type (controlled by neither)
4. Lowest MED (controlled by neighbor AS)
5. eBGP-learned over iBGP-learned (controlled by neither)
6. Lowest IGP cost to border router (controlled by local AS)
7. Lowest router ID (to break ties) (controlled by neither)

Question 38

RIP is which type of routing?

Answer 38

Intradomain

Question 39

Link State is which type of routing?

Answer 39

Intradomain

Question 40

Where is NAT implemented?

Answer 40

• Routers and Firewalls mostly. Switches operate at Layer 2 of the OSI (and TCP/IP) models. They work with MAC addresses and aren’t responsible for routing packets.
• Since NAT modifies at the very least the IP addresses (and in the case of the type of NAT studied in this course, TCP and UDP port numbers), it requires a device like a router or firewall capable of operating on those packets.
• The exception to this is a multilayer switch, but you can think of a multilayer switch as a switch that is also a router.