Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Advanced Computer Networks > Routing > Flashcards

Routing Flashcards

1
Q

What is an Autonomous System?

A
  • 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?
1
Not at all
2
3
4
5
Perfectly
2
Q

What types of AS exist?

A
  • 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?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are inter-domain routing protocols and name some

A

Exchange routing information between ASes (Exterior Gateway Protocols)

Practice only BGP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a intra-domain routing protocol and name some

A

Interior gateway protocols inside an AS

OSPFv2/3, IS-IS, RIP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Eselsbrücke für EGP & IGP?

A

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?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a routing information base?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the Forwarding Information Base?

A

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?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a Forwarding Decision?

A

Algorithm uses the FIB to decide how to forward individual packets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Explain how BGP works

A
  • 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?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the difference between iBGP and eBGP

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What message types exist in BGP?

A

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?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does an BGP update message contain?

A
  • 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?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is hot potato routing?

A

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?
1
Not at all
2
3
4
5
Perfectly
14
Q

What types of peering do exist in BGP?

A
  • 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?
1
Not at all
2
3
4
5
Perfectly
15
Q

How is peering in BPG defined?

A
  • 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?
1
Not at all
2
3
4
5
Perfectly
16
Q

How can private peering be established?

A

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

17
Q

Which use cases do exist for private peering?

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

Which type of routing has which financial effects?

A
  1. Route via a customer (financial gain)
  2. Route via a peer (no financial gain or loss)
  3. Route via a provider (financial loss)
19
Q

Which routes should one AS announce and which not?

A
  • 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)
20
Q

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

A

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

21
Q

What is the k-core algorithm?

A

Remove all nodes of degree k or < k recursively

22
Q

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

A 
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)
23
Q

What are Area Border Routers?

A

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
24
Q

What are AS Boundary Routers?

A
  • 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
25
Q

What OSPF packet types do exist?

A

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

26
Q

What is a Desginated Router in OSPF?

A
  • 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
27
Q

Which router becomes the Designated Router?

A

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

28
Q

What would happen if no DR exist?

A

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

29
Q

is there more about OSPF?

A

yes, much more

30
Q

What is the interface of an routing protocol?

A
  • 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.

31
Q

How does the strict longest prefix matching algorithm work?

A
  • It sorts the FIB prefixes by length
  • Scans for a matching prefix
  • The first matching prefix is the longest prefix
32
Q

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

A
  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
33
Q

What is a trie structure?

A

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

34
Q

How can you create a trie?

A
  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.
35
Q

How does the Trie lookup algorithm work?

A
  • 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
36
Q

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

A

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

37
Q

What is the DIR 24-8 structure?

A

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.

38
Q

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

A

It allows flexible address separation.

It works a bit like a set associative cache.

39
Q

How can you construct a DIR 24-8 structure?

A

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.

Advanced Computer Networks (12 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions