Brainscape's Knowledge GenomeTM

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


See full index

CS 6250 - OMSCS > Midterm 2 > Flashcards

Midterm 2 Flashcards

1
Q

What is congestion control?

A

Goal: ‘Fill the internet pipes without overflowing them’

‘Watch the sink, slow down the water flow if it begins to overlow’

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

What is congestion collapse?

A

Increase in load -> decrease in useful work done: throughput is less than the bottleneck link.

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

What are the causes of congestion collapse?

A

Spurios Retransmission: Senders don’t receive ACK in reasonable time, they retransmit the packet. The results in many copies of the same packet being outstanding.

Undelivered Packets: Packets consume resoursces and are dropped elsewhere in the network

Solution: TCP Congestion control to all traffic!

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

What are the goals of congestion control?

A
  • Use network resources efficiently
  • Preserve fair allocation of resources
  • Avoid congestion collapse
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the two approaches to congestion control?

A

End to End (What TCP uses)

  • No feedback from network
  • Congestion inferred from loss and delay

Network-Assisted

  • Routers provide Feedback
    • set a single Bit indicating congestion (ECN)
    • tell sender explicit rate they should send at
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How does TCP congestion occur?

A
  • Senders increase rate until packets are dropped

* TCP interprets packet loss as congestion and slows down

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

What is the window-based approach to adjusting transmission rates?

A
  • Send up to WINDOW_SIZE packets
  • Stop sending until you get an ACK back
  • Each time you get an ACK, increase window size by 1 and send packets until window is full
  • If you fail to receive an ACK for a packet, cut the window size in half
  • TCP is Additive Increase, Multiplicative Decrease (AIMD)
  • This is the common method to use
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is Rate Based congestion control (as opposed to window based congestion control)?

A
  • Monitor loss rate

* Uses timer to modulate transmission rate

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

Calculate the Sending Rate for the following:

RTT = 100ms
Packet: 1kB
Window Size: 10 Packets

A
  • 10 packets / 100ms = 100 packets / second
  • 1000B * 8 b/B = 8000b
  • 8000 b/packet * 100 packets / sec = 800kbps
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is fairness and efficiency in congestion control?

A

Fairness:
* everyone gets their fair share of resources

Efficiency:

  • network resources are used well.
  • No spare capacity in network
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How does AIMD converge to optimal fairness and efficiency?

A
  • Efficiency: x1 + x2 = C (network capacity, Constant)
  • Fairness: x1 = x2
  • Left of the x1 + x2 = C -> Underutilization
  • Right of the x1 + x2 = c -> Overutilization
  • Optimal Point is where network is neither under or over-utilized and you are on the x1 = x2 fairness line
  • Additive increased moves parallel to the fairness line. This continues until network becomes overloaded (Increases efficiency)
  • multiplicative decrease moves you toward the origin which makes it more fair.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Describe TCP Incast

A

Drastic reduction in application network throughput when large number of servers using TCP all make simultaneous requests.

Results b/c of:

  • High Fan In
  • High bandwidth, low latency
  • lots of parallel requests each w/ small amount of data

Results in bursty, retransmission
When TCP timeout occurs, have to wait hundreds of ms for timeout to occur, but RTT inside DC network is < 1ms, or even us, so throughput is reduced by up to 90% because of link idle time (waiting for TCP timeout to occur)

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

How do you calculate average AIMD throughput?

A

(3/4) * (Wm/RTT)

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

What are solutions to TCP incast?

A
  • us granularity of retransmission timers (reducing retransmission timeout)
    • Timers need to operate on granularity close to the RTT time.
  • ACKS for every other packet
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are some challenges of streaming data?

A
  • Large volume of data
  • Data volume varies over time
  • Low tolerance for delay variation (don’t like buffering)
  • Low tolerance for delay, period
    • Some loss is acceptable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How is video compression performed?

A
  • Image Compression -> Spatial Redundancy

* Compression across images -> temporal redundancy

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

Why is TCP not a good fit for congestion control for streaming data?

A
  • Reliable Delivery (could resend packets, waisting time and causing buffering)
  • Slowing down upon loss (could slow down too much and starve buffer)
  • Protocol overhead (extra bytes to send)

UDP:
+ No Retransmission
+ No Sending rate adaption

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

How are youtube and skype implemented?

A

Youtube: Decided to keep it simple and still use HTTP/TCP

Skype: Peer to Peer (P2P)
* Individual users route voice traffic through one another

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

How does QOS Work?

A

Marking and Policing
* Marking and Scheduling - mark packet with higher priority then they can be put into a higher priority queue. Schedule that queue so it’s serviced more often than lower priority queues.

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

Describe the different traffic classifications

A

CBR - Constant bit rate (audio)

VBR - variable bit rate (video, data)

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

What is leaky bucket traffic shaping?

A

(Isochronous)
Beta = size of bucket
rho = drain rate from bucket (average rate)

Sender can send bursty traffic as long as it doesn’t overfill the bucket

Larger bucket = larger burst
larger drain rate = enable faster packet rate

Example Audio Stream

  • 16KB Bucket
  • Packet size = 1KB
  • Rho = 8 packets / s

So could possible accept a burst up to 16 packets, but will constantly deliver 8 packets/s out of the bucket.

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

What is (r, T) traffic shaping?

A

Typically limited to fixed rate flows.

  • can send max r bits during a T-bit frame
  • can send a certain number of bits every time unit

If flow exceeds rate, those bits are assigned a lower priority and may be dropped.

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

What is a token bucket?

A

Shapes bursty traffic patterns - bounded by the rate, rho.

  • arrive in bucket at rate rho
  • bucket size is beta

If ‘b’ is packet size, < beta:

  • if bucket is full - packet sent, b tokens removed
  • if bucket is empty, must wait for b tokens before sending

In general, you must wait for packet size bits to be present in the bucket at which point they will be sent.

difficult to police traffic sent by token buckets.

bound in token bucket is:
Over any interval T, rate < Beta + T*rho

You can always send at rate Rho - if you want to send a burst of > rho, you use the bucket size. So if rho = 6Mbps and you want to send at 10Mbps for 0.5s, you need: (10 - 6)*0.5 = 2Mb = 250KB = beta.

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

How do you police a token bucket shaper?

A

To use a composite shaper: Combined token bucket shaper + leaky bucket shaper. Token feeds the leaky.

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

What is a power boost?

A

Allows subscriber to send at higher rate for short period of time. Spare capacity for users who do not put a sustained load on the network.

Time allowed for power boost = Beta / (r_boost - r_sustained)

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

What is buffer bloat?

A

When there is too much buffering and thus the latency (RTT) can significantly increase.

Solutions:

1) smaller buffers (not realistic - lot of stuff currently deployed)
2) traffic shaping - prevent sending at a rate higher than the upload link provided by your ISP.

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

Why measure network traffic?

A
  • Security - looking for rogue behavior (botnets, DOS)

- Billing - something like the 95th percentile

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

How do you passively measure data?

A

SNMP - simple network management protocol
– Interface byte and packet counts
+ Ubiquitous
- Course

29
Q

What is packet monitoring?

A

Can see full packet contents (tcpdump, ethereal, wireshark)
+ lots of detail (timing, header info)
- high overhead - hard to keep up w/ high speed links (often requires additional hardware)

30
Q

What is flow monitoring?

A

Monitors statistics per flow:
– a flow consists of packets that share common: src/dest IP, src/dest PORT, protocol type, TOS byte, interface
– sometimes also grouped if they are ‘close’ together in time
+ Less overhead
- Much more course, no packets/payloads

Could also just do ‘sampling’ instead of measuring all packets.

31
Q

What are the contents of an HTTP Request?

A

Request line:

  • Method (GET, POST, HEAD)
  • URL (relative, /index.html)
  • HTTP Version number

Headers (not usually required):

  • Referer - what caused page to be requested
  • User Agent - client software used to fetch page
  • Accept: client will accept these types
  • Host: host location is being made to
32
Q

What does an HTTP Response look like?

A

Status Line:

  • HTTP Version
  • Response Code:
    • 100’s - info
    • 200’s - success
    • 300’s - redirection
    • 400’s - errors
    • 500’s - server error
  • Location: could be used for redirection
  • server: server software (apache/2.2.16)
  • allow: http methods that are allowed
  • content-encoded: how content is encoded
  • content-length: length in bytes
  • expires: how long content cant be cached
  • modified: last time page was modified
33
Q

What are persistent connections and why do they exist?

A

multiple http requests/responses on a single TCP connection

  • delimiters indicate ends of requests
  • content-length

Can be combined with ‘pipelineing’
- client sends requests as soon as it encounters a referenced object

34
Q

How can you configure how to use a cache?

A
  1. Browser Config

2. Origin sends a special reply telling the client to go to a cache to get the data

35
Q

What is a CDN?

A

Content Delivery Network

Overlay network of web caches designed to deliver content to client from the optimal location

36
Q

What are the major challenges of running a CDN?

A 
Goal: Replicate content on many servers
How?
Where?
How do you find it?
How to choose server replicas?
how to direct clients?
37
Q

Describe server selection (CDNs) (what metrics would use to select which server to send a client to)

A

Could be:

  • lowest load
  • any ‘alive’ server
  • lowest latency (typically chosen)
38
Q

Describe content routing (CDN)

A
  1. Routing (eg, anycas) - simple but service providers have little control over which server client actually gets sent to
  2. Application-Based - (http redirect) - effective but client must first go to origin to get redirect location
  3. Naming-based (DNS) - when DNS lookup done, it returns a location that is best suited for client
39
Q

Why do CDNs and ISPs like eachother?

A

CDNs with ISPs:
+ better throughput (lower latency)
+ redundancy
+burtiness - lower transit costs

ISPs with CDNs:
+ good performance for customers
+ lower transit costs

40
Q

What is a distributed hash table?

A

Example, a Chord - scaleable, distributed lookup service. A key - value map (DNS, directory service)

+ Scalability
+ Proven Correctness
+

41
Q

What is consistent hashing?

A

Keys and nodes are mapped to the same ID Space.

Think of a ring with node ids distributed around it. The key ids are also distributed around the ring.

In Chord, you key to the owning node by looking up the next higher node in the id space.

So if there are nodes 1, 10, 32, and 43, then keys 33-42 are owned by node 43. 2 - 9 are owned by node 10, etc.

+ Load balancing
+ Flexibility - when node is added/removed, it’s pretty simple to re-balance

42
Q

How do you implement consistent hashing?

A 
Two options:
* Every node knows location of every other node:
  \+ lookups = O(1)
  - Tables= O(n)
* Node only knows about it's successor:
  - lookups = O(n)
  \+ tables = O(1)
43
Q

What are Finger Tables?

A
  • Every node knows M other nodes in Ring
  • Distance of nodes that it knows increases exponentially
So in ring w/ nodes: 1, 10, 32, 43 (out of 0-63 key space):
* Node 10 maintains mappings from:
** 10+2^0, 10+2^1 ... 10+2^i
Where Finger i points to the successor of 10 + 2^i, so:
* 10+2^0 = 11 -> 32
...
* 10+2^4 = 23 ->32
*10+2^5 = 42 -> 43, etc

So it walks around the ring trying to find the predecessor of the data it’s looking for and

+ Tables = O(log n)
+ Lookup = O(log n)

Each node knows about the node half way around the ring, then half way to that node, and again half way to that node … until it gets to it’s successor. It’s like a binary search. 1/2 -> 1/4 -> 1/8 … etc.

44
Q

What are the benefits of CUBIC over BIC?

A
  • Much more simple algorithm
  • BIC can be too aggressive for short RTT systems and was designed for larger bandwidth/longer RTTs, making it unfriendly to other TCP competing flows
  • Based on Time b/t congestion events instead of doing something at each RTT.
  • Keeps BICS stability utilization strengths, but simpler algorithm with less to keep track of.
45
Q

When would you use UDP over TCP?

A
  • Latency is critical
  • You don’t mind dropped packets
  • Congestion Control can cause unacceptable delays
46
Q

Why does linear growth of TCP Reno perform poorly for short lived flows? (1/RTT)

A

It takes a long time for the congestion window to reach its maximum. Short lived flows may never reach a congestion event and thus transmit unnecessarily slow.

47
Q

How does BIC-TCP work?

A
  • Starts out by linearly going toward Wmax (additive increase)
  • after meets specific threshold, transitions to binary search
  • Cuts distance b/t Wmax and Wmin in half, repeatedly for each RTT. This becomes new Wmin.
  • Keep doing this until increment is < Smin, then set to Wmax
  • Transitions to max probing which is symmetric view of the first half
  • When congestion event occurs, decrease by beta
48
Q

Describe the three regions of TCP CUBIC

A

Concave - Rapid growth back toward Wmax at the previous congestion event for quick recovery

Plateau - AKA, TCP Friendly region. very slow, near linear growth as it approaches Wmax

Convex - Max Probing - Grow quickly to find a new Wmax

49
Q

What is CUBICs fast convergence?

A

If successive congestion events are encountered prior to Wmax, the window is further reduced [(2-Beta)/2] to free up additional bandwidth.

50
Q

What kind of flows are good for TCP fast-open?

A

Short lived TCP connections - small data size on links with long RTTs. Performance of these flows is dominated by RTT so reducing one RTT can really help.

51
Q

How does TCP Fast Open prevent source spoof attacks that would allow the server to respond to all HTTP GET requests and just send data?

A

by using an encrypted cookie that must be requested by the requestor before initiating requests. Server uses this cookie to verify the requestor address is not a forgery.

52
Q

What role do middle boxes play in MPTCP?

A
  • Strip out unrecognized TCP options/flags
    • Endpoints could both support MPTCP, but if middle box doesn’t and strips the flags, it doesn’t matter.
  • MPTCP will fallback to TCP if it doesn’t get an ack containing the MPTCP flag.
53
Q

Why does MPTCP require larger buffers? What controls does MPTCP use to maximize efficiency.

A
  • Buffer size is dictated by the largest RTT of the flow. so it’s Link_Size*max(RTT).
  • Occurs because MPTCP allows out of order packets and allows other links to keep sending
  • Worst case is packet dropped early and must wait for it to be sent on slowest link, while faster link keeps sending data

Controls:

  • Opportunistic Retransmission - retransmit un-ack’d data that was already sent on a slower flow (but now we send on the faster flow).
  • Subflows that induce opp. retransmission can be penalized and have their cwnd reduced.
  • Buffer itself dynamically grows over time as needed, so doesn’t use worst case unless it must
54
Q

How does the youtube application flow control work and describe how it interacts with TCP

A
  • Connection starts normally, sending data until the application buffer is deemed full
  • Then data is sent in ‘blocks’ or bursts as the video is watched
  • The receive/send buffers are emptied during the pauses when no data is being sent, then when the large burst of data comes through, it is seen as congestion on the line and packet loss occurs reducing throughput
55
Q

How does TFO defend against a SYN FLOOD attack?

A
  • Requiring the security cookie
  • Maintaining # of active new TFO requests and if threshold is hit, falls back to regular 3WHS while continuing to process existing ones. RSTs still count against this quota.
56
Q

How does TFO defend against an Amplified Reflection attack?

A
  • The TFO cookie is basically enough. They would need cookies from multiple hosts and have to use them before they expire. In order to get the cookie the host may already be compromised so this is ultimately of little value.
57
Q

What is active measurement?

A

Inject additional traffic into network to measure additional characteristics of the network.

ping - delay to server,
traceroute - network or ip level path b/t two hosts on the network.

58
Q

Under what conditions was the RTT*C rule of thumb developed?

A
  • Assumed a single long lived flow
  • Currently there are thousands of flows in a backbone router, have varying RTTs and congestion windows are not synchronized.
59
Q

Why do short flows not significantly impact buffer queue sizing?

A

Average queue length is only affected by the length of the TCP flows and the load on the link. It does not depend on:

  • Bandwidth
  • Propagation Delay of the flows
  • Number of flows
60
Q

Describe CoDel - what are the three innovations it brings to the table?

A

Controlled Delay Management

  • Assumes standing queue of target size is acceptable
  • At least one MTU worth of data must be in buffer before dropping packets
  • If min time in queue exceeds target value for at least a set interval, drop packets according to a control law until queue delay is back on target or data in buffer drops below one MTU.
  • Uses minimum rather than average as the queue measure
  • simplified single-state variable tracking of minimum
  • Use of queue-sojourn time
61
Q

What is a standing queue and how does it develop?

A

When there is a constant number of packets in the queue.

Difference in the bottleneck link speed and link RTT result in some # of packets constantly occupying the queue. As queue is processed, the receiver sends ACKS back which are turned into more data by the sender.

62
Q

What is the last modified field if the header?

A

Datetime of when document was last modified

63
Q

What is the HOST field in the header?

A

The domain name - eg, www.w3.org/pub/WWW –> www.w3.org is domain

64
Q

What is the cookie field in the header?

A

If set-cookie was set in a response field, future requests to the same domain would send the cookie in this field.

65
Q

What are the methods of CDN redirection and which is the most preferred?

A

Routing (anycast) - give all replicas same IP and allow routing to take the user to the proper location
- simple, but course at the mercy of routing - no control

Application Based (HTTP redirect) 
- simple, but long delays. slow because you have to visit the original page/location first
DNS routing (Preferred) - Response when DNS lookup gives response of optimal cache. 
\+ fine grained control and fast
66
Q

How does Bit torrent tit for tat work?

A
  • Send to top N Peers (unchoked) + 1 optimistically unchoked peer
  • If optimistically unchoked peer sends fast enough to get into top N, then client boots slowest of top 5 and adds this one, and then will send back in return
  • If not, drops that peer and tries another
67
Q

What is the bit torrent solution to freeloading/freeriding?

A

Choking! I won’t send to you if you don’t send to me

68
Q

How is the AIMD throughput (lambda) related to the loss rate (p)?

A

Lambda = k / (RTT * sqrt(p))

k = some constant
Where p = loss rate
RTT = round trip time
Lamda = 3/4 * (Wmax/RTT)

Loss Rate (1/2)(Wmax)(Wmax/2+1)k

CS 6250 - OMSCS (3 decks)

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