Transport Layer Flashcards
How does the internet decide on the bandwith you get?
e.g. You live in flat with multiple people who use multiple programs
Via flows
Write down the flow equations
What is the flow rate
The net flow leaving s
What is a commodity? What is a multicommodity flow? Write down the equations
A commodity is a source-target pair. A multicommodity flow is a collection of multiple si-ti flows Fi
How to find augmenting paths to increase flow for commodities
In single commodity case: use Ford-Fulkerson
In multiple commodity case: Can’t apply Ford-Fulkerson, weil wir können nur unsere eigenen Flüsse verschieben, aber nicht die von anderen
Daher benutzen wir bei Multi-Commodity eine andere Methode: Linear Programmming (solved in polynomial time, hence fast)
Describe the simplex algorithm
Choose a vertex x of the polytope
While there is a neighbouring vertex y such that f(y) > f(x) do:
x:= y
return x
Describe simplex as LP
Write down equations
Which networks do actually use a central authority assigning each commodity a certain flow (via LP for instance)
Software Defined Network (SDN)
BUT: the internet is a large network with quickly changing data flows -> centralized allocation procedures are not efficient
What is an unsplittable flow
An s-t flow is unsplittable if the edges e \in E with F(e) form a PATH from s-t. (i.e. on our way from s to t there is a unique path with no repetition of nodes)
What is a splittable flow
We can have multiple paths taking us from s to t
Can we use LP for maximizing an UNSPLITTABLE MUlTIcommodity flow?
NO. This problem is NP hard
Decribe the term demand in the context of flows
The demand di is the rate at which Fi wants to transmit
For the actual flow rate we have: Fi <= di
Why do we need fairness protocols when allocating bandwith?
If we simply maximize total throughput, this might mean that certain flows starve
What is Max-Min Fairness
We increase all edges by the SAME amount, until one edge is saturated. If for that particular edge two flows have contributed to its saturation (i.e. we have an edge with capacity 8 and F1 and F2 both have a flow of 4) then both of them are taken out of the game and we increase the remaining edges. If we only have one edge left, we only increase it once and then we stop the algorithm (even if we actually could go further)
If you just want the max throughput
For each Fi look at the last edge that leads to ti, this is the amount that we want to push through
However, if along the path from si to ti there is an edge with even less capacity, that’s the one that poses our limits
So essentially look for the edge with smallest capacity on your si-ti path and then try to make sure that this limit is reached
Describe UDPs
Fire and forget
Doesn’t recognize when packets are lost, it simply keeps sending new ones, hence it doesn’t provide congestion control and it doesn’t guarantee any order of delivery of packets
What is a port?
A computer runs multiple programs and it receives multiple packets? How does it know which packet is for which program? This is cllarified by a port which is a numeric identifier.
It specifies which application send the packet and which application should receive it on the destination computer
Structure of UDPs
UDPs consist of a header which contains: the source and destination ports, a checksum (for error detection) and the length of the packet
What are UDPs used for?
Used for real-time applications like video streaming, online games, calls. Reason: These applications are time sensitive and can’t afford retransmission delays (resending of packets that have been damaged or lost)
These applications can suffer some data loss without adversely affecting perceived quality.
Structure of TCP
Like UDP it uses ports for addressing specific applications on a computer. Additionally, it the TCP header also includes a sequence and acknowledgment number, a window size for flow control and binary flags to indicate TCP states
Contrast to UDP
Instead of simply sending packets, TCP first establishes a connection between source and destination before sending the actual data -> three-way handshake. Now (due to the connection) if a packet gets lost, the client will know. The connection reamins alive as long as it is not terminated by setting the corresponding flag bit
Three-way handshake
Sequence number of a packet: number of first byte in the packet (in the first packet it is not set to zero, but to some random number -> security)
Acknowledgment number: number of last byte of received packet plus 1, hence it is also the sequence number of the next packet it expects to receive
1. Client send SYN (synchronization) packet to server (this only includes sequence number, no actual data)
2. Server sets it SYN and ACK flags (this way we know its responding to a connection request) and sends back a SYN/ACK packet
3. Client acknowledges received packet by sending an ACK packet
Only then the client starts sending data packets
Flow Control
Dem Client wird gesagt wieviel Byte der Receiver eigentlich verträgt,i.e. the receiver uses the flow window size field in the header to specify how many bytes it can receive before its buffer is full
Congestion Control
Beim Flow Control gehts darum, dass man den Empfänger nicht überlastet. Bei Congestion Control geht es darum, dass Internet (network) nicht zu überlasten
Achieved via AIMD: Additive Increase Multiplicative Decrease
As long as no packets have to be dropped (the client will know this from ACK messages), each flow increases its rate by 1 per RTT
If a package is dropped, the flow reduces its rate to half of the original value
Draw rate vs t diagram for AIMD
Explain RTT
Round trip time is the time needed for a packet to travel from its sender to the receiver and back.
Bis zu diesem Zeitpunkt warten wir auf das ACK, RTT is also unser timeout
Smooth RTT
Used by TCP. Initially set to RTT of first ACK packet.
Smoot RTT: weighted mean of itself and RTT of last ACK packet
How can RTT change
Packet takes a different path, congestion at router, …
Slow Start
Am Anfang ist es nervig immer nur 1 Paket mehr zu schicken, deswegen sagen wir 1s -> 1 Packet, 2s-> 2 Packete, 3s-> 4 Packete, i.e. verdopple die Anzahl pro RTT
NAT
Gerade bei IPv4 gibt es nicht genug Addressen, deswegen musste man sich anders zu helfen wissen -> private Addressen (10.0.0) sind im Gegensatz zu IP Addressen nicht unique, d.h. sie kommen mehrmals vor
Zu Hause brauchen wir also ein Gerät mit einer eindeutigen IP Addresse (Router, Modem, Gateway) das von aussen erreichbar ist
Alles internen Geräte im Haus hängen dann mit lokalen Addressen am Router
Wenn der Server jetzt aber ein request von so einem Paket kriegt, steht da eine lokale Adresse und er weiss nicht wohin er das Ergebnis zurückschicken soll
Deswegen:
Unser Router zu Hause macht folgendes:
Er erhält den request und ersetzt die lokale Addrresse durch seine eigene IP Addresse
Server schickt die Antwort an Router und der Router speichert Source IP, Source Port und eigenen Port um das Paket dann richtig an das lokale Gerät weiterzuleiten
Can the rate of a flow F(e) on some edge e be greater than its rate F?
Yes, if F uses the edge e twice because of a cycle in the flow.
If we require the flow to be cycle-free than F(e) <= F
Is it true that in a max-min-fair allocation, the different bandwidths allocated on an edge
differ at most by a factor of 2
No, you can have arbitrary factor between allocated bandwiths on an edge
No, e.g., you could have two flows on an edge e where one flow has a small rate because
it has to get through a low-capacity edge somewhere else and the other one can get all
the remaining bandwidth of e
Implement Voice over IP, would you use UDP or TCP? Why?
There are arguments you could make for TCP, e.g., the correct ordering of the packets, but
for realtime applications, the latency is more important in most cases. Thus, you rather
should choose UDP
In slow-start, how long does it take to double the size of the congestion window?
Takes one RTT (time it takes for an ACK packet to travel from sender to receiver and back)
Imagine that both UDP and TCP packets arrive at a router, but its buffers cannot accomodate all of them since they are already pretty full. Should the router rather drop UDP
packets or TCP packets? What arguments can you find for either approach
On the one hand, the UDP application might not adjust its rate, meaning that the congestion
will persist if TCP is not dropped. On the other hand, dropping TCP will incur a hefty
multiplicative decrease, while the UDP application might be able to handle some lost packets
(e.g., video streaming). There are more factors to this, but the real life answer is: It depends
In TCP, how does a sender establish if some router dropped one of its packets? What
would you gain if a router dropping packets informed the affected senders? Why, do you
think, is this not done in practice?
A sender finds out if a router dropped one of its packets due to the missing ACK from the
receiver after a timeout. If a router informs the sender directly when it drops its packet
then the sender would not have to wait for the timeout. This is not done in practice because
routers need to be fast, so we try to keep them simple. Also there might be a problem if the
direct message of the router got lost, so we need a timeout no matter what!
Should a router rather drop packets from a far-away client or from a close-by
client? And should it rather drop packets from a client sending with a large rate or from
one sending with a small rate?
Dropping packets from a close-by client is preferable since such
a client will realize faster that it lost packets and therefore the congestion will be remedied
faster. Dropping packets from a client sending with a large rate has the advantage that the
probability that the congestion is actually removed is larger since halving the rate of a larger
flow “removes more congestion”. Also, you do not want to utilize routers at their buffers’
limit since that would induce undesired latencies.
