Transport Layer Flashcards
(35 cards)
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