1
Q
Why is packet classification needed?
A
The internet has become more complex, meaning that networks want better quality of service and security guarantees for traffic. Packet forwarding with longest prefix matching of destination IP isn’t enough. Instead, we need to handle packets based on other things like TCP flags, source addresses, and more.
2
Q
What are three established variants of packet classification?
A
- Firewalls: They stop traffic at the beginning and end of a network to stop unwanted traffic or other security policies
- Resource reservation protocols: (e.g., DiffServ used to reserve bandwidth between src and destination)
- Routing based on traffic type
3
Q
What are simple solutions to pattern classification problems?
A
Linear Search: Looks through a rules database to keep track of best match (Firewalls do this)
Caching: Do a linear search, but cache the results. Issues involve linear search on missed hits and the initial linear search still stinks
Passing Labels: Add labels to traffic at entry points to categorize traffic (used by DiffServ and Multiprotocol Label Switching MPLS)
4
Q
How does fast searching using set-pruning tries work?
A
It’s a trie of tries structure used for multi-field lookups. You set up your first rule (e.g., destination rules) as a trie and traverse through that first. Then you hang any matching other field lookups (e.g., source rule tries) from the end of each ends of the destination tries. The idea is that every time you move forward you prune the search space (e.g., a source tree or more).
5
Q
What is the main problem with set-pruning tries?
A
Memory explosion because a source prefix tree can occur in multiple destination trees.
6
Q
What is the difference between the pruning approach and the backtracking approach for classification with a trie?
A
Backtracking is high cost in terms of time, but pruning is high cost in terms of memory. The backtracking does this by having each destination prefix D point to an exact-match source tree, it then goes backwards up the ancestors.
7
Q
What are the advantages and disadvantages of a layered architecture?
A
ADVANTAGES:
1. Scalability
2. Modularity
3. Cost-effective because it’s easy to add or delete components
DISADVANTAGES:
- Some layers require info from other layers, which blurs their lines (missing the point)
- A layer can duplicate lower-layer functionality
- There is overhead from abstracting other layers
8
Q
What are the differences and similarities between the OSI model and the five-layered Internet
model
A
OSI is 7 layers, internet is 5
OSI separates out the application layer into 3 layers:
- Application layer:
Protocols = HTTP, SMTP, FTP, DNS
Packet of info is a message - Presentation layer
Formats info (formatting video or translating ints from big to little endian) - Session layer
Manages transport streams from same session b/w end-user application processes (e.g., tie-in audio + video)
9
Q
What are sockets?
A
The interface b/w the application and transport layer
10
Q
What is the application layer in OSI?
A
End-user applications
Protocols include HTTP (internet), SMTP (e-mail), FTP (file transfer), DNS (domain–>IP address)
Packet of info = message
11
Q
What is the presentation layer?
A
Formats info for application layer that it receives from layer below, for example formatting video or moving ints from big to little endian
12
Q
What is the session layer?
A
Layer that manages concurrent transport streams b/w end-user application processes like tying together video and audio
13
Q
Transport Layer
A
Responsible for end-to-end communication between hosts
Protocols: TCP (transmission control protocol) and UDP (User datagram protocol)
Packet of info is a segment
14
Q
TCP vs UDP
A
TCP offers:
1. connection-oriented service
2. Guaranteed delivery of messages
3. Flow control (match sender/receiver speeds)
4. Congestion control (sender will slow transmission rate when congested network)
UDP offers:
1. Connectionless, best-effort service
15
Q
What is the network layer
A
Moves datagrams from one internet host to another. Determines routes!
Packet of info is a datagram
Protocol = IP (the glue that binds the internet together)
16
Q
What is the data link layer
A
Moves frames from one node (host or router) to the next node. While the network layer routes things, at each node, the data link layer delivers the datagram to the next node
Packet of info = frame
Protocols = 1. Ethernet 2. PPP (point to point) and 3. Wifi
17
Q
What is the physical layer
A
the hardware that lets it all happen
packet of info = bits
Protocol = twisted-pair copper wire, coaxial cable, single-mode fiber optics
18
Q
What is encapsulation and how is it used in the layered model
A
Encapsulation is when a layer adds a header to a given bit of info for the next level down to read/add to. This allows the layers to communicate with each other
19
Q
What is end-to-end (e2e) principle
A
All complexity should move to the ends of the network. We should not build application layer stuff into the core of the network so that the middle of the network can be simple and minimal and GENERIC. Besides, most stuff can’t be done properly unless it’s at the end.
20
Q
What are examples of a violatoin of e2e principle?
A
Firewalls: they are intermediate devices operated between two end hosts and can drop their communication
NAT boxes: The end-users can’t directly talk
21
Q
What is the EvoArch model?
A
A model that explains how and why layered networks become hourglass shape
22
Q
Explain a round in the evoarch model
A
A round in EvoArch consists of these steps:
Introduce new nodes → Place randomly across layers.
Connect nodes → For each layer (top → bottom):
Link new nodes to substrates below (based on generality probability of layer l−1).
Link new nodes to products in the current layer (based on generality probability of l).
Update node values → Adjust values in each layer to account for new nodes.
Remove nodes → Sort nodes in each layer by value (highest → lowest) and delete those marked to die.
Check stop condition → End simulation if the network has reached the target number of nodes.
Takeaway: After many rounds, the layer widths form a “bow-tie” shape: wide at bottom, narrowing toward middle, then widening again toward top.
23
Q
What are the ramifications of the hourglass shape of the internet?
A
A. Many technologies that were not originally designed for the internet have been modified so that they have versions that can communicate over the internet (such as Radio over IP).
B. It has been a difficult and slow process to transition to IPv6, despite the shortage of public IPv4 addresses.
24
Q
Repeaters, hubs, bridges, and routers operate on which layers?
A
Repeaters and Hubs (Physical layer): receive and forward digital signals to connect ethernet segments.
Bridges ad switches (Datalink layer): Enable communication between hosts that are not directly connected. They receive and forward packets. Note that packet drops can happen if bandwidth is too high.
Routers: Network layer: Router traffic through internet
25
What is a bridge, and how does it “learn”?
Bridget is a device with multiple inputs and outputs that transfers frames (in datalink layer) from an input to one or more outputs.
Note: it doesn't HAVE to forward everything
It can learn because it has a forwarding table so that it only forwards frames on specific ports rather than all of them. It learns because it keeps track of which hosts are reachable through which ports. It can even stop loops with the spanning tree algorithm.
26
Define distributed algorithms
An algorithm that runs across multiple independent nodes in a network. They coordinate via messages to solve problems. Very often asynchronous.
27
Explain the spanning tree algorithm
Every bridge has an ID. Each round a node sends a configuration message with three fields: the sending node's ID, the ID of the root as perceived by the sending node, the number of hops it thinks it takes to get to the root
Every round, the node processes messages and tries to see if there's a better route (smaller ID for root, there's a shorter path to the root, smallest ID if there is a tie). It stops sending messages if there's a neighbor with a shorter distance to the root or the same distance with lower ID.
28
What is the point of the STA
To stop loops from happening. The spanning tree algorithm stops loops by selecting which links to use for forwarding eliminating loops.
29
What does the transport layer provide?
The transport layer provides an end-to-end connection between two applications running on different hosts.
30
What is a packet for the transport layer called?
A segment
31
What are the two main protocols within the transport layer?
The two most common transport layer protocols are User Datagram Protocol (UDP) and Transmission Control Protocol (TCP).
32
What is multiplexing, and why is it necessary?
Multiplexing is the ability for a host to run multiple applications to use the network simultaneously. It's necessary because we want to be able to run spotify and Chrome at the same time.
33
What is multiplexing/demultiplexing.
The job of delivering the data included in the transport-layer segment to the appropriate socket, as defined in the segment fields, is called demultiplexing.
Similarly, the sending host will need to gather data from different sockets and encapsulate each data chunk with header information to create segments, and then forward the segments to the network layer. We refer to this job as multiplexing.
34
What are the two types of multiplexing/demultiplexing?
Connectionless: UDP best-effort delivery. In this case, it will forward the segments to the same destination process via the same destination socket, even if the segments come from different source hosts or source port numbers.
Connected: TCP establishes a connection before ever sending anything! That allows us to have guarantees.
35
What are the differences between UDP and TCP?
UDP: Connectionless, unreliable, but fewer delays and better control over sending data because no congestion control or connection management overhead.
TCP: Connection-oriented, reliable, has guarantees like ordered delivery, transmission control, flow control, congestion control,
36
When would an application layer protocol choose UDP over TCP?
UDP is better for real-time applications that are sensitive to delays. Some examples include:
DNS (name translation), NFS (remote file server), network management (SNMP), routing protocols (RIP)
Streaming video (can really be either)
37
What typically uses TCP?
Email (SMTP)
Remote terminal access (telnet)
Web (HTTP)
File transfer (FTP)
38
Explain the TCP Three-way Handshake.
Step 1: no data segment with SYN bit set to 1 with a client-specific initial sequence number
Step 2: The server gets the packet, prepares the connection, then says "Connection granted" called SYNACK (SYN = 1, seq = server_isn, ack= client_isn + 1)
Step 3: Gets the acknowledgement, allocates a buffer/resources for connection, sends acknowledgement with SYN bit set to 0, client_isn + 1, and server_isn + 1
39
Explain the TCP connection tear down.
4 parts:
1) client sends server segment with FIN bit set to 1
2) Server acknowledges it
3) Server sends segment with Fin bit set to 1 to show it's closed
4) Client send ACK to the server (may also resend it in case it gets lost)
40
What is automatic repeat request or ARQ
A way to help the sender know if their packet was lost. The sender keeps sending stuff if they did not receive and ack within a given period of time.
41
What is Stop and Wait ARQ?
Simplest automatic repeat request form. The sender sends a packet and simply waits for acknowledgement from the receiver. The timeout is tricky to get right and is often a function of the estimated round trip time (RTT)
Has pretty low performance. Sending N unacknowledged packets (a window size) helps.
42
What is Go-back-N?
A way for TCP to have reliable transmission. The receiver only acknowledges the last in-order packet and forces the sender to re-send all things.
This causes a lot of unnecessary retransmission.
43
What is selective ACKing?
The sender retransmits only those packets that it thinks were erroneous. This helps to fix the go-back-n ack for reliable transmission in TCP.
the receiver, in this case, acks a correctly recieved packet, even if not in order. The OOO packets get bufferedd until missing packets are received.
44
What is fast retransmit?
Timeouts stinks, so we need a way to detect packet loss without them (or minimized). In this case, the sender knows something was lost when it received 3 duplicate ACKs for a pakaet.
45
What is transmission control, and why do we need to control it?
What is it?
How does a TCP connection know how fast or slow to send things on a network?
We need to control it for fairness and to avoid possible packet loss.
46
What is flow control, and why do we need to control it?
A type of transmission control where we are protecting the receiver buffer from overflowing.
TCP controls the sender by provind it with a receive window to give it an idea how much the receiver can handle at the moment. This is:
rwnd (receive window) = RcvRuffer - LastByteReceived - LastByteRead
The receiver advertises this in every ACK it sends back to the sende.r
sender also keeps UnAcked Data Sent = LastByteSent - LastByteAcked
47
What is congestion control?
Congestion control allows the transport layer to control the transmission rate of the sender to avoid the whole network getting congested.
48
What are the goals of congestion control?
Efficiency: High throughput/utilization
Fairness: Each user has to have equal opportunity (every flow gets = bandwidth)
Low delay: Don't want high buffer times
Fast convergence: we should get to high utilization fast
49
What is network-assisted congestion control?
A congestion control implantation (one of two) where the network layer gives the sender feedback about congestion control in the network.
E.g., routers can use an ICMP source quench to notify the source that the network is congestion.
Is this effective, though? packets can still get lost.
Less favorable, and not e2e principle approved
50
What is end-to-end congestion control?
One of 2 congestion control implementations. Here, hosts infer congestion from network behavior and adapt the transmission rate.
TCP uses this.
Aligns with the e2e principle
Certain routers can still do both, though. So be aware that the line is kinda blurry.
51
How does a host infer congestion?
Two main signals:
1) Packet delay: You can see increases in round trip time, which can be estimated by ACKs
2) Packet loss: dropped packets can be for other reasons, but probably this.
52
How does a TCP sender limit the sending rate?
TCP congestion control was first invented to determine capacity and send only what was possible to avoid congestion.
A congestion window (cwnd) is used to say how many unacked data packets can be in transit.
TCP uses probe-and-adapt approach in determining the window.
LastbyteSent - LastByteAcked <= min{cwnd, rwind}.
53
Explain Additive Increase/Multiplicative Decrease (AIMD) in the context of TCP
Start with an initial window, then add one packet every RTT, so slow). This is the probe. If the host sends a CongestionWindow number of packets, we add a small increment.
Once we detect congestion, we half the cwnd.
54
What is a slow start in TCP?
TCP Slow Start
• What it is: Exponential increase of the congestion window (cwnd) at the start of a TCP connection.
• How it works:
◦ Starts with cwnd = 1 packet.
◦ Doubles cwnd after each Round Trip Time (RTT) upon receiving ACKs.
◦ Continues until cwnd reaches the "slow start threshold."
◦ Then switches to Additive Increase Multiplicative Decrease (AIMD).
• Why it's "slow": It starts with only one packet, making initial growth slower than if it began with a larger window.
• Other uses: Also used when a connection recovers after a timeout, using the last known cwnd as a target.
55
What is TCP Reno
It's a way of handling congestion, but one to maximize bandwidth use.
Uses two types of loss to signal congestion
1) triple duplicate ACKS (mild congestion), where we half the cwnd
2) Timeout (no ack for a specific amt of time). This is severe and we reset the initial window size.
56
What is a slow start in TCP?
TCP reno has a slow-start phase where the congestion window is increased exponentially instead of linearly. It does this to a threshold then moves to AIMD. this helps us get to congestion window much faster.
57
Is TCP fair in the case where connections have the same RTT? Explain
Yes. Because TCP reno uses an ACK-based adaptation of the congestion window, ACKs would come in at the same rate for both, so they would presumably both increase the congestion window at the same rate.
58
Is TCP fair in the case where two connections have different RTTs? Explain.
No. Because smaller RTT would allow for more ACKs, which would mean the slow start phase goes faster for those than the connections with larger RTTs
59
Explain how TCP CUBIC works.
Modern way to do congestion control that addresses TCP Reno's inefficiency as a high bandwidth delay product network.
CUBIC was implemented in the linux kernel and uses a CUBIC polynomial as the growth function.
Like AIMD, when it has a triple duplicate ACK, it halves the congestion window. After doing so, it remembers where the loss occurred and grows aggressively to about there. At the loss area, it goes really slowly. So if we don't see another packet loss (anomaly), we again grow aggressively.
RTT fair because it measures from last loss event instead of the usual ack-based timer. Growth depends on time between congestion events.
60
What is a high bandwidth delay product network
TCP Reno is an example: TCP Reno has low network utilization, especially when bandwidth is high (AIMD's fault) or delay is large (ack-based). This is not very efficient.
61
Explain TCP throughput calculation.
BW = data per cycle / time per cycle = Max segment size (MSS) * 3/8W2 / RTT * W/2
BW < MSS/RTT * 1/sq(p) where p is the probability of loss
62
What is the difference between forwarding and routing?
Forwarding is transferring a packet from an incoming link to an outgoing link within a single router. This is when the router consults its forwarding table and sends it onto the correct output.
Routing is when routers work together using routing protocols to determine good paths where packets can get to their destination.
63
What is the main idea behind a link-state routing algorithm?
Link-state algorithms are a type of routing protocol. In them, the link costs and network topology are known by all nodes.
An example of this is Dijkstra's algorithm.
64
What is an example of a link-state routing algorithm?
Dijsktra's
65
Walk through an example of the link-state routing algorithm.
Dijskstra's algorithm involves first initializing a set of all known paths to neighbors. Everyone else is infinity, then we do a loop:
For every destination node in the network, we look at the set of nodes not in N' and we identify the node wiht the least cost path from the previous iteration. That node (w) gets added to N'. For each of the neighbors (v) of that node, we update the distance vector with the new cost, which is the min of the known D(v) (u to v) and the D(w) + cost(w->v).
66
What is the computational complexity of the link-state routing algorithm?
O(n^2)
67
What is the main idea behind the distance vector routing algorithm?
Based on bellman ford, iterative, asynchronous, and distributed.
The idea is that each node maintains their own map of the network rather than everybody passing around the whole topology.
Each node sends DVs around and we do a similar min of current DV and cost to neighbor + neighbor's DV to the destination
68
When does the count-to-infinity problem occur in the distance vector algorithm?
If there is a large increase to the link cost, it can cause confusion. BAD NEWS TRAVELS SLOW
69
How does poison reverse solve the count-to-infinity problem?
If a node routes to a destination through a neighbor, it tells that neighbor the distance to that destination is infinity.
This “poison” prevents the neighbor from trying to route back through it, stopping the two-node loop seen in the count-to-infinity problem.
🧠 Example:
If z reaches x via y, z advertises to y that its distance to x is ∞ — even though it’s not — so y won’t send packets to x through z.
⚠️ Limitation:
Poison reverse only works for two-node loops; it doesn’t fully prevent count-to-infinity in larger routing loops.
70
What is the Routing Information Protocol (RIP)?
Example of a distance vector. Released with Unix, uses hop count as a metric. Paths can be chosen by a number of ways (lowest cost, load balanced, shortest distance, etc...).
Updates exchanged periodically using a RIP response message (an advertisement with the forwarding table) instead of distance vectors, and contain information about sender's distances to destination subnets.
Routers maintain routing tables with one row per subnet in the AS. They also have a personal distance vector. Tables contain destination subnets, next routers, and hops to that destination.
If the periodicity ends (router isn't heard from every 180s), that is considered a broken link.
Requests and responses are on UDP on port 520. This is, though, an application-level process.
Challenges include updating routes, reducing convergence time, and avoiding loops/count-to-infinity problems.
71
What is the Open Shortest Path First (OSPF) protocol?
Linkstate routing example. Introduced as advancement of the RIP protocol in high-tier ISPs. Advances include authentication of messages, can use multiple same-cost paths, and support for hierarchy within a single routing domain.
Hierarchy: can have routers in areas with individual linkstate algorithms. Border routers route in/out. But one AS is the backbone, which routes traffic to other ASs. Required to go through backbone to get to another area.
Operation: Each router runs Dijkstra locally. If there's a change, they broadcast it to EVERYONE in the AS. Sometimes just does it periodically.
Link State Advertisements: All routers use. Used to build a link state database containing all link states.
The refresh rate for LSAs: default 30 min. Periodic updates, but can also be dynamic if things change.
72
What is so good about linkstate algorithms?
Dynamic
Every router shares knowledge of its neighbors with every other router in the network.
73
How does a router process advertisements?
Routers have route processors (main CPU) and interface cards that receive/forward data packets via a switching fabric.
1. LS updates get to the OSPF (route processor), which triggers it. As updates comes, the OSPF updates the link state database. Can tell if new or duplicate.
2. Router calculates shortest path first algorithm and forwards it to the Forwarding Information Base (FIB).
3. FIB used when data packet arrives at interface card to forward to outgoing card.
4. If LSA is changed after processing, flood it out to other routers
74
What is hot potato routing?
A way to choose a path within the network by choosing the closest egress point based on intradomain path cost (Interior Gateway Protocol/IGP cost).
Simplifies computations for the routers. Gets traffic consumption out as soon as possible.
75
How did Licklider and his team in the early 1960s experiment with a precursor to the Internet?
Connecting two computers over a dial-up telephone line
76
What is the Domain Name System (DNS) designed to do primarily?
Translate domain names into IP addresses
77
What is the architectural design of the Internet protocol stack based on?
Layers
78
Both the data link and transports layer protocols may provide error correction.
(T/F)
True
79
What allows for communication between the application layer and transport layer?
Sockets
80
DNS belongs to which layer?
Application
81
When an application sends a packet of information across the network, this packet travels down the IP stack and undergoes what process?
Encapsulation
82
What is the difference between hubs, bridges, and routers?
They operate on different layers of the IP stack
83
The transport layer protocols offer a logical connection between processes only if the hosts reside in the same network. (T/F?)
False
84
T/F: A sending host receives a message from the application layer and encapsulates it with the transport layer header before passing it down to the network layer.
True
85
T/F: An application running on a host can bind to multiple sockets simultaneously.
True (session layer does this)
86
T/F: The identifier of a UDP socket is a tuple of destination IP address and port.
True
87
The identifier of a TCP socket is a tuple of source IP address and port.
False. It's a four-tuple that consists of source IP, source port, destination IP, and destination port.
88
T/F: UDP offers basic error checking.
True
The UDP packet structure: UDP has a 64-bit header consisting of the following fields:
Source port number
Destination port number
Length of the UDP segment (header and data).
Checksum (an error checking mechanism).
89
What is the UDP packet structure
The UDP packet structure: UDP has a 64-bit header consisting of the following fields:
1) Source port number
2) Destination port number
3) Length of the UDP segment (header and data).
4) Checksum (an error checking mechanism).
90
Why do people use UDP
fewer delays and better control over sending because we don't have overhead of congestion control or connection management overhead.
91
T/F: Assume Hosts A, B, and C. Host A has a UDP socket with port 123. Hosts B and C each send their own UDP segment to Host A. Hosts B and C cannot use the same destination port 123 for sending their UDP segment.
False
92
T/F: Flow control is a rate control mechanism to protect the receiver’s buffer from overflowing.
True
93
T/F: Congestion control is a rate control mechanism to protect the network from congestion.
True
94
In TCP, the number of unacknowledged segments that a sender can have is the minimum of the congestion window and the receive window.
True
95
T/F: Consider the TCP Reno, congestion window is cut in half in both of the following events: a) a timeout occurs, b) a triple duplicate acknowledgement occurs.
False: triple dup. ack is bad and TIMEOUT of VERY bad (go to minimum)
96
Consider a TCP connection and a diagram showing the congestion as it progresses. From the diagram, when we observe the congestion window drop to its initial value, we infer that a packet loss occurred.
True
97
Consider a TCP connection, and a diagram that shows how the congestion window progresses over time. From the diagram we can identify the time periods of slow start when the congestion window increases by 1 every RTT.
False
98
T/F: TCP Cubic was designed for better network utilization.
True
99
TCP Cubic congestion window growth function is designed to not overflow the receiver’s buffer.
False
100
T/F: TCP Cubic increases the congestion window in every RTT.
False
101
What is known to all nodes for link-state routing?
Link cost and network topology
102
What are three types of ISPS
access (tier-3), regional (tier-2), and global (tier-1).
Tier 1: AT&T, NTT, Sprint
103
What is an AS?
Group of routers and links that operate under the same admin authority.
104
Describe the relationships between ISPs, IXPs, and CDNs
ISPs are the backbone network over which smaller networks can connect.
IXPs are interconnection infrastructures that provide the physical infra where multiple networks like ISPs and CDNs can interconnect and exchange traffic.
CDNs are networks that content providers create to have better control over how their content is delivered to end-users while reducing connectivity costs.
Dominant presence of IXPs and CDNs has caused the structure to move from hierarchical to flat
105
What kind of relationship does AS have with other parties?
Types of relationships:
1. Provider-Customer (or transit) based on financials. Provider forwards customer's traffic to destinations found in the provider's routing table.
2. Peering: two AS have access to subset of each other's routing tables. Common with Tier-1. Holds if traffic is not highly asymmetric (must be similar size and types of traffic). They save money they'd pay to providers by directly forwarding traffic between them.
106
what is BGP/IGP
Use Border Gateway Protocol (BGP) to exchange routing info with one another (ASs)
Interior Gateway Protocols (IGPs) operate within an AS.
107
T/F: For two ASes to form a peering agreement, they need to find common ground regarding the internal policies and traffic engineering approaches that each AS implements.
False
108
A Content Distribution Network (CDN) or an ISP can operate over multiple Autonomous Systems.
True
109
iBGP vs eBGP vs IGP
The first two are for interdomain. iBGP tells intradomain routers about interdomain things. eBGP is all interdomain, and IGP is for intradomain routing like DV and link-state
110
T/F: Since the BGP path selection process is fixed, an AS has no control over which routes are selected.
False
111
How do we show preferences to external routes?
Higher LocalPref
112
How would an AS show another As the it prefers a specific entrypoint?
Lower MED values
113
T/F: An AS can use LocalPref to control which routers are used as exit points (for the outgoing traffic), and it can use the MED attribute to control which routers are used as entry points (for the incoming traffic).
True, but higher LocalPref and Lower MED
114
One of the services provided by IXPs is additional security protections such as mitigation of DDoS (Distributed Denial of Service) attacks.
True
115
There are no costs involved for an AS to participate at an IXP.
False. Entry fee usually
116
Since local traffic stays local at IXPs, the IXP infrastructures deal with limited volumes of traffic.
False
117
When a large provider or Content Delivery Network joins an IXP, this can act as an incentive for other networks to join as well.
True
118
At an IXP, the members have the choice to peer privately or publicly.
True
119
IXPs leading incentive to establish route servers was to charge the participants for using it.
False
120
An IXP route server does not need to run the BGP protocol to facilitate the establishment of multi-lateral peering sessions.
False
121
For multi-lateral BGP peering sessions at an IXP, the participants have the choice to advertise routes, either directly to other participants, or to the route server.
False
122
The data plane functions of a traditional router are implemented in hardware.
True
123
The control plane functions of a traditional router are implemented in software.
True
124
The forwarding plane operations take place in shorter time scales than the control plane operations.
True
125
The forwarding functions of a traditional router refer to transferring packets from the input ports to the appropriate output ports.
True
126
The control plane functions can either be implemented in the router's processor or they can be “outsourced” for implementation at a remote controller.
True
127
In traditional routers, traffic forwarding is performed based on:
Destination IP address only
128
By stride we refer to the number of bits that we check at every step when traversing a trie.
True
129
Using packet classification techniques we can perform packet forwarding based on multiple criteria, and not just based on destination IP address.
True
130
The backtracking approach has a higher cost in terms of time, whereas the set-pruning approach has a higher cost in terms of memory.
True
131
The grid of tries technique offers a “middle ground” approach, merging the backtracking and the set-pruning techniques.
True
132
The head-of-line blocking refers to the problem when an entire queue remains blocked because the head of the queue is blocked.
True
133
One technique to avoid head of line blocking is with parallel iterative matching.
True
134
With parallel iterative matching the input links are “matched” with output links in a fixed manner that stays the same as the rounds are progressing.
False
135
With the token bucket traffic approach, we can still have bursts of traffic entering the network, but these bursts are capped.
True
136
With the leaky bucket approach, we only allow the traffic to enter the network in a configured rate.
True
137
With the leaky bucket we can still have discarded packets.
True
137
Traffic policers target to limit traffic bursts to a configured max, whereas traffic shapers target to smooth out the overall rate.
True
138
How does an AS determine what rules to import/export?
Export (which routes to advertise)
We want to export customer-learned routes b/c it's financially beneficial. It doesn't make sense to route from providers because we are paying you! Same for peers
Import:
Customer first, then peer, then provider. We want to be sure we route things towards customers.
139
What were the original design goals of BGP? What was considered later?
Scalability: internet is only growing
Express routing policies: defined route attributes that allow ASes to implement policies through route filtering and ranking.
Allow AS cooperation: Each can make local decisions and keep those confidential
Security: Not original, but now a thing that is being researched.
140
BGP peers
A pair of routers in a BGP session.
141
Where does BGP happen?
Semi-permanent TCP port connection called a BGP session
142
How to begin BGP
Router sends an OPEN message to another router. They then exchange announcements from their routing tables
143
iBGP vs eBGP
i = internal (in the same AS)
e = external
144
Types of BGP messages
2 types:
UPDATE: contain info about routes that have changed. 2 kinds: announcements advertise new routes/updates. Withdrawals do the obvious
KEEPALIVE: Keeps things going
145
How are destinations represented in BGP
IP Prefixes. They represent the subnet/subnets an AS can reach
146
Advertised BGP routes consist of what
BGP attributes: 2
ASPATH: Each AS ID'd by a number (ASN). As you go through a router, that ID is added
NEXT HOP: Attribute refers to the next hop router's IP address.
147
IGP vs iBGP
One is for establishing paths between internal routers. iBGP is only used to disseminate external routes.
148
How does a router use the BGP decision process to choose which routes to import?
Compares routes by looking at attributes.
LocalPref and MED are important
High localpref = more likely to route here. Helps to prefer routes learned thorugh a specific AS over other Ases
Low MED = preferred link for inbound traffic.
149
* What are the 2 main challenges with BGP? Why?
Misconfiguration and faults: this can cause large numbers of ubdates and therefore route instability. Fix is to keep route tables small. Can also config default routes. Flap dampening also limits propagating unstable routes. Repress bad routes.
150
* What is an IXP?
Infra that helps Ases interconnect and directly exchange traffic with one another.
Typically Ases must have physical presence since IXP is a network of switches.Can be global though.
151
* What are four reasons for IXP's increased popularity?
They keep local traffic local
Lower costs
Network performance improved due to reduced delay
Incentives if big boy content providers are there
152
* Which services do IXPs provide?
1) Public peering with good QOS and better network performance. Big boys like Google also incentivize being here
2) Private peering with a dedicated link for high traffic
3) Route servers and service-level agreements
4) remote peering through resellers
5) Mobile peering thorugh 3g
6) DDoS blackholing
7) Free value-added services like Internet Routing Registry, broadband tetss, etc...
153
* How does a route server work?
Generally two Ases exchange traffic through bilateral BGP
Route server does the following
1) Collects and shares routing info from its peers or participants of the IXP that connects to the RS
2) Executes its own BGP decision process and re-advertises the resulting info (best route selection) to all RS's peer routers
They maintain two types of route filters: import (AS only advertises routes that it should advertise) and export (restrict the set of other IXP member Ases that receive their routes.
154
What are the basic components of a router?
Control plane: The routing processor (software)
Data plane (hardware) input ports, switch fabric, and output ports
155
Explain the forwarding (or switching) function of a router
Hardware:
transfers packet from input link to appropriate output link interface.
Typically very very fast
156
The switching fabric moves the packets from input to output ports. What are the functionalities
performed by the input and output ports?
Input: Physically terminate the incoming links to the router, decapsulates packets, and perform lookup function by consulting the forwarding table
Output: Receive and queue packets from switching fabric and send them over the outgoing link
157
What is the purpose of the router’s control plane?
Software and processing
Implements routing protocols, maintains routing tables computing the forwarding table.
158
What tasks occur in a router?
Lookup (input link): Done through longest prefix matching algorithms
Switching: Moves data from input to output link
Queuing:
Header validation and checksum
Route processing
Protocol Processing
159
List and briefly describe each type of switching. Which, if any, can send multiple packets across
the fabric in parallel?
Switching fabric is brain of the router as it switches from input to output
1) Switching via memory: Check the table in the routing processor
2) Switching via bus: No routing processor. Inputs give an internal header. All output ports get the packet, but only the designated one keeps it and removes header. This can be slow since only one packet can cross the bus at a time.
3) Switching vis interconnection network: Crossbar switch connects N inputs to N outputs using 2N busses. Very fast b/c parallelizable
160
What are two fundamental problems involving routers, and what causes these problems?
1) Bandwidth and internet population scaling: more devices and volumes from new apps. Also new links that have more volumes
2) Services at high speeds: Hard to offer protections against delays and congestion or security at high speeds
161
What are the bottlenecks that routers face, and why do they occur?
1) Longest prefix matching: Harder with more options
2) Service differentation: have to consider packet classification
3) Switching limitations
4) Bottlenecks about services: performance guarantees at high QOS and security hard!
162
Convert between different prefix notations (dot-decimal, slash, and masking).
1. Dot decimal
Example of the 16-bit prefix: 132.234
The binary form of the first octet: 10000100
Binary of the second octet: 11101010
The binary prefix of 132.234: 1000010011101010*
2. Slash notation
Standard notation: A/L (where A=Address, L=Length)
Example: 132.238.0.0/16
Here, 16 denotes that only the first 16 bits are relevant for prefixing.
3. Masking
We can use a mask instead of the prefix length.
Example: The prefix 123.234.0.0/16 is written as 123.234.0.0 with a mask 255.255.0.0
The mask 255.255.0.0 denotes that only the first 16 bits are importan
163
What is CIDR, and why was it introduced?
Classless Internet Domain Routing (CIDR) came into effect because there was rapid exhaustion of IP addresses. Decreased router table size, but also added longest-matching-prefix lookup bottleneck.
164
Name 4 takeaway observations around network traffic characteristics. Explain their consequences.
1) Measurement studies on network traffic had shown a large number of concurrent flows of short duration. This already large number has only been increasing, and as a consequence, caching solutions will not work efficiently.
2) The important element of any lookup operation is how fast it is done (lookup speed). A large part of the cost of computation for lookup is accessing memory.
3) An unstable routing protocol may adversely impact the update time in the table: add, delete or replace a prefix. Inefficient routing protocols increase this value up to additional milliseconds.
4) A vital trade-off is memory usage. We can use expensive fast memory (cache in software, SRAM in hardware) or cheaper but slower memory (e.g., DRAM, SDRAM).
165
Why do we need multibit tries?
While a unibit trie is very efficient and offers advantages such as fast lookup and easier updates, its most significant problem is the number of memory accesses required to perform a lookup. For 32 bit addresses, we can see that looking up the address in a unibit trie might require 32 memory accesses, in the worst case. Assuming a 60 nsec latency, the worst-case search time is 1.92 microseconds. This could be very inefficient in high-speed links.
166
What is prefix expansion, and why is it needed?
Consider a prefix such as 101* (length 3) and a stride length of 2 bits. If we search in 2-bit lengths, we will miss out on prefixes like 101*. To combat this, we use a strategy called controlled prefix expansion, where we expand a given prefix to more prefixes. We ensure that the expanded prefix is a multiple of the chosen stride length. At the same time, we remove all lengths that are not multiples of the chosen stride length. We end up with a new database of prefixes, which may be larger (in terms of the actual number of prefixes) but with fewer lengths. So, the expansion gives us more speed with an increased cost of the database size.
167
What are the benefits of variable-stride versus fixed-stride multibit tries?
Fixed stride means every node has the same number of bits. If collisions, you drop one
Variable optimizes for memory.
Some key points about variable stride:
1) Every node can have a different number of bits to be explored.
2) The optimizations to the stride length for each node are all done to save trie memory and the least memory accesses.
3 )An optimum variable stride is selected by using dynamic programming
168
What’s the benefit of a grid of tries approach?
With the grid of tries approach, we can reduce the wasted time in the backtracking search by using precomputation. When there is a failure point in a source trie, we precompute a switch pointer. Switch pointers take us directly to the next possible source trie containing a matching rule
It's a middleground between set pruning and backtracking.
169
Describe the “Take the Ticket” algorithm.
A simple scheduling algorithm. Each output maintains a queue of interested inputs. To get interested, inputs take a ticket and wait to be served.
This does create a problem called Head of Line Blocking because the entire queue is blocked by the progress of the head of the queue.
170
* What is the head-of-line problem?
In take a ticket approach, the head of the line blocks all other processes from happening.
171
How is the head-of-line problem avoided using the knockout scheme?
Assuming an N-by-N crossbar switch, it breaks up packets into fixed sizes. We assume the same output rarely receives N cells, and the expected number is K. The fabric then runs K times as fast as the input link. To avoid likely collisions.
We still have switches that choose outputs in the case of collisions randomly called concentrators. The larger number of possible collisions, the more complicated choosing random values is.
172
How is the head-of-line problem avoided using parallel iterative matching?
We schedule both the queue and more packets so that the queue makes progress in case the head is blocked
173
Computer Networks
flashcards
Decks in class (2)
# Cards
