Routing Flashcards
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
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
What are inter-domain routing protocols and name some
Exchange routing information between ASes (Exterior Gateway Protocols)
Practice only BGP
What is a intra-domain routing protocol and name some
Interior gateway protocols inside an AS
OSPFv2/3, IS-IS, RIP
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?
What is a routing information base?
All routing information a router can gather from updates of neighboringrouters
(may contain multiple routes to target)
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
What is a Forwarding Decision?
Algorithm uses the FIB to decide how to forward individual packets
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)
What is the difference between iBGP and eBGP
iBGP: Both routers have the same ASN
eBGP: Routers have different ASNs
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
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
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
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 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 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 & 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?
- take the IP of the FIB entry
- apply the prefix mask
- AND the result with the ip to be looked up.
- 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?
- write all next hops to table and add unique ID (NH-ID)
- 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.
