Transport Layer

Question 1

How does the internet decide on the bandwith you get?

e.g. You live in flat with multiple people who use multiple programs

Answer 1

Via flows

Write down the flow equations

Question 2

What is the flow rate

Answer 2

The net flow leaving s

Question 3

What is a commodity? What is a multicommodity flow? Write down the equations

Answer 3

A commodity is a source-target pair. A multicommodity flow is a collection of multiple si-ti flows Fi

Question 4

How to find augmenting paths to increase flow for commodities

Answer 4

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)

Question 5

Describe the simplex algorithm

Answer 5

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

Question 6

Describe simplex as LP

Answer 6

Write down equations

Question 7

Which networks do actually use a central authority assigning each commodity a certain flow (via LP for instance)

Answer 7

Software Defined Network (SDN)
BUT: the internet is a large network with quickly changing data flows -> centralized allocation procedures are not efficient

Question 8

What is an unsplittable flow

Answer 8

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)

Question 9

What is a splittable flow

Answer 9

We can have multiple paths taking us from s to t

Question 10

Can we use LP for maximizing an UNSPLITTABLE MUlTIcommodity flow?

Answer 10

NO. This problem is NP hard

Question 11

Decribe the term demand in the context of flows

Answer 11

The demand di is the rate at which Fi wants to transmit

For the actual flow rate we have: Fi <= di

Question 12

Why do we need fairness protocols when allocating bandwith?

Answer 12

If we simply maximize total throughput, this might mean that certain flows starve

Question 13

What is Max-Min Fairness

Answer 13

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)

Question 14

If you just want the max throughput

Answer 14

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

Question 15

Describe UDPs

Answer 15

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

Question 16

What is a port?

Answer 16

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

Question 17

Structure of UDPs

Answer 17

UDPs consist of a header which contains: the source and destination ports, a checksum (for error detection) and the length of the packet

Question 18

What are UDPs used for?

Answer 18

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.

Question 19

Structure of TCP

Answer 19

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

Question 20

Contrast to UDP

Answer 20

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

Question 21

Three-way handshake

Answer 21

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

Question 22

Flow Control

Answer 22

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

Question 23

Congestion Control

Answer 23

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

Question 24

Explain RTT

Answer 24

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

Question 25

Smooth RTT

Answer 25

Used by TCP. Initially set to RTT of first ACK packet.

Smoot RTT: weighted mean of itself and RTT of last ACK packet

Question 26

How can RTT change

Answer 26

Packet takes a different path, congestion at router, …

Question 27

Slow Start

Answer 27

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

Question 28

NAT

Answer 28

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

Question 29

Can the rate of a flow F(e) on some edge e be greater than its rate F?

Answer 29

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

Question 30

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

Answer 30

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

Question 31

Implement Voice over IP, would you use UDP or TCP? Why?

Answer 31

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

Question 32

In slow-start, how long does it take to double the size of the congestion window?

Answer 32

Takes one RTT (time it takes for an ACK packet to travel from sender to receiver and back)

Question 33

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

Answer 33

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

Question 34

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?

Answer 34

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!

Question 35

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?

Answer 35

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.