Routing Flashcards by Deleted Deleted

What is an Autonomous System?

Internet Service Providers (ISPs) offering transit services, such as Deutsche Telekom, Vodafone, DFN
Organisations at one or more locations, e.g. Universities, companies
Hosting providers, e.g., Amazon
Content Delivery Networks, e.g., Akamai, Google

How well did you know this?

Not at all

Perfectly

What types of AS exist?

Transit AS: fwd traffic from one AS to others
Stub AS: AS connected to only one other
Multi-Homed AS: AS connected to multiple ASes without offering transit services

How well did you know this?

Not at all

Perfectly

What are inter-domain routing protocols and name some

Exchange routing information between ASes (Exterior Gateway Protocols)

Practice only BGP

How well did you know this?

Not at all

Perfectly

What is a intra-domain routing protocol and name some

Interior gateway protocols inside an AS

OSPFv2/3, IS-IS, RIP

How well did you know this?

Not at all

Perfectly

Eselsbrücke für EGP & IGP?

EGP: Which AS to transfer the packet to?
IGP: Which intra-AS route to use to reach this neighboring AS?

How well did you know this?

Not at all

Perfectly

What is a routing information base?

All routing information a router can gather from updates of neighboringrouters
(may contain multiple routes to target)

How well did you know this?

Not at all

Perfectly

What is the Forwarding Information Base?

Mapping from a destination IP network address (prefix) to outgoinginterface or next hop router IP address

Unique for each destination
Longest prefix matching

How well did you know this?

Not at all

Perfectly

What is a Forwarding Decision?

Algorithm uses the FIB to decide how to forward individual packets

How well did you know this?

Not at all

Perfectly

Explain how BGP works

Each AS has a unique AS Number (ASN)
BGP router exchange their routing table entries
Which next AS to choose is a policy (business) decision
Path-Vector: updates contain all ASes on the path towards a destination network (prefix)

How well did you know this?

Not at all

Perfectly

What is the difference between iBGP and eBGP

iBGP: Both routers have the same ASN
eBGP: Routers have different ASNs

How well did you know this?

Not at all

Perfectly

What message types exist in BGP?

OPEN: Opens a connection between two routers
TEARDOWN: Close the connection
NOTIFICATION: Send error codes
UPDATE: Announce a new route, or un-reachability of an old one

How well did you know this?

Not at all

Perfectly

What does an BGP update message contain?

Destination prefix (a.b.c.d/x)
AS path - list of ASes
Next Hop - IP address of the router sending the update
Origin - Learned via IGP/EGP/other

How well did you know this?

Not at all

Perfectly

What is hot potato routing?

Always hand it over as fast as possible
Choosing the “nearest” connection site minimizes the cost
-> Leads to asymetric routing

How well did you know this?

Not at all

Perfectly

What types of peering do exist in BGP?

Private: Direct connection to (frequently large) AS

* Public: Exchanging traffic with other ASes at an Internet Exchange Point (IXP)

How well did you know this?

Not at all

Perfectly

How is peering in BPG defined?

Two ASes peer with each other, if they have some kind of BGP relationship, i.e., two ASes are directlyconnected
Protocol viewpoint: It is irrelevant if one party pays the other party
Policy viewpoint: It is very relevant if one party pays the other par

How well did you know this?

Not at all

Perfectly

How can private peering be established?

direct network connections between locations
Peering possible at colocation center operated by a carrier
Peering possible at colocation center operated by a carrier-neutral data center provider

Which use cases do exist for private peering?

Exchange a large amount of traffic with a single AS
Attractive setup for upstream providers
Interconnection of, within, and inbetween data centers

Which type of routing has which financial effects?

Route via a customer (financial gain)
Route via a peer (no financial gain or loss)
Route via a provider (financial loss)

Which routes should one AS announce and which not?

Announce routes that incur financial gain if others use them•Others = costumers
Announce routes that reduce costs if others use them•Others = peers
Do not announce routes that incur financial loss(… as long as alternative paths exist)

What are Tier 1 , Tier 2 and Tier 1.5 providers?

Tier-1 / Default-Free-Zone: only peerings, no providers
Tier-2: only peerings, and one or more Tier-1 providers
“Tier-1.5”: almost a Tier-1, but pays money for some links

What is the k-core algorithm?

Remove all nodes of degree k or < k recursively

What are link-state and distance vector algorithms and how do they differentiate?

Distance Vector (RIP, IS-IS): Routers only know the next hop &amp; cost; no global topology; routers exchange cumulative costs
Link-State (OSPF): Routers also exchange topology information (complete or partial) -> Shortest path (Djikstra)

What are Area Border Routers?

Routers which are member of area 0 (the backbone) and one or more other areas

> Can fwd packets from one area to another
> Each area must have a connection to area 0

What are AS Boundary Routers?

Routers that inject routes learned from another routing protocol into OSPF
Those routes may be from a BGP process on the same router, another routing protocol, or even stativroutes redistributed into OSPF
The term “Autonomous System” in that context does not demand that those routes must lead to anotherAS

What OSPF packet types do exist?

Hello: Router is up and wants to participate (also keep-alive every 10s and after 3 missing -> link down) Database Description: Router announce its Link-State-Advertisements Link State Request: Router describes another router sends over an LSA contained in its DB Link State Update: Originate a new LSA Link State Acknowledgement: Router acks the reception of an LSA

What is a Desginated Router in OSPF?

* All routers send their LSAs to the DRs on all their links * Therefore, the DRs always have the most up-to-date information * The DRs flood the LSAs to all other routers on the links * Sends network-LSAs on behalf of the OSPF routers on this link

Which router becomes the Designated Router?

On each link, the router with the unique higherst Router-ID becomes the DR (second highest is backup)

What would happen if no DR exist?

Routers would send their LSAs and other routers would resend them. Result: LSA would be sent multiple times on the same link, resulting in lots of redundant packets

is there more about OSPF?

yes, much more

What is the interface of an routing protocol?

- Routing protocols know all routers (from RIB) - Routing protocols choose best route (writes it to the FIB/Routing Table) - > Routing protocols do not care about individual packes - > They create the RIB; RIB -> FIB (less frequent, not that time critical) Router then uses the FIB to forward individual packets. This is time critical.

How does the strict longest prefix matching algorithm work?

- It sorts the FIB prefixes by length - Scans for a matching prefix - The first matching prefix is the longest prefix

How does the longest prefix matching algorithm actually evaluates if a prefix matches?

1. take the IP of the FIB entry 2. apply the prefix mask 3. AND the result with the ip to be looked up. 4. Verify that result is 0

What is a trie structure?

It is a tree with additional invariants used for prefix searching. For each leaf level, the prefixes of the parent nodes are ommitted.

How can you create a trie?

1. write all next hops to table and add unique ID (NH-ID) 2. write FIB entry prefixes at corresponding position in trie. Root is default gateway. - Each level n is the Nth bit in the prefix. Insert the NH-IDs accordingly.

How does the Trie lookup algorithm work?

- iterate for each subnet-bit of the ip address over the trie: if it is 0 go left, otherwise go right. Update the NH-ID for each step to the current id. If the current node is null: return last NH-ID

What are problems with basic tries and what 2 alternatives do exist?

Problem: basic tries are wasteful and sparsely used. Path compressed trie: aggregate chains of empty nodes -> less memory and less computation Level compressed trie: Pull children's children into parent -> fewer, bigger nodes to save -> less cpu and better cache use

What is the DIR 24-8 structure?

It is a routing table lookup structure which allows to find a prefix in 1 or 2 lookups. It consists of 2 parts: a "TBL24" part (24bit; includes most prefix lengths) and a "TBLlong" part with the remaining 8 bit.

What is the advantage of DXR over DIR-24-8?

It allows flexible address separation. | It works a bit like a set associative cache.

How can you construct a DIR 24-8 structure?

Associate Routes with their next hops and store next hops in array. If next hop exists for entire /24 prefix -> direct mapping otherwise: add all next hops for the /24 prefix into TBLLong and do set-associatve things.