Lösungsvorschlag Computer Networks Reexamination 2009

Aus VISki
Wechseln zu: Navigation, Suche

Exam: http://www.systems.ethz.ch/education/courses/fs10/operating-systems-and-networks/exercises/vs-sep-09-exam.pdf

Solutions provided without any guarantees.

1 Network architecture and performance

1 Layering

The transport and Application layer determine what data is transferred and which application handles the data. The lower layers determine how the data is transferred and where the data goes through (routing).

2 Network performance


Transfer time = 0.01 s (delay) + 16mb/10mbps (transmission time) = 1.61s


For each 2kB you have: 0.01s (delay) + 16kb/10mbps (transmission time) + 0.01s (ack delay) + 80b/10mbps (ack transmission time) = 
0.02 s + 1.6ms + 8/1000ms = approx. 0.021 s

So to send the entire file:

1000 * 0.021 s = 21s

2 Socket programming

1 Events and Threads

Threadbased networking: create for each connection a new thread, and do the work within that thread.
+ Easier to understand program flow
+ Scales well with number of cores
- Overhead due to context switches
- Must switch into a thread, even if the thread is blocked, just to see that => ineffiecent and slows things down

Eventbased networking: just react to events with a select() call, to select on which connection you can work.
+ Efficient, as you always select what is ready
+ Scales well with number of connections
- Does not scale with number of cores
- Complicated program flow

3 Application layer protocols


The DNS root server is responsible to give the DNS information about where to search for DNS entries. If you want to access ethz.ch the root server would give you the IP of the .ch server, and this one would give you the IP of ethz.ch. In reality that's not what happens, you rely on heavy caching, meaning most of the time you don't have to go ask the root server, but you will get the IP of ethz.ch a lot earlier.


You have two connections, one is for the control, that means on this connection you exchange commands and queries. The second one is for data exchange.


As HTTP uses the TCP protocol to communicate between server and client, this means you have the connection setup, and slow start overhead. Having non-persistent connections, each HTTP request must be sent in its own TCP connection. So if a client wants to access a website (a typical use case in HTTP) which has 10 images, the client needs to create 11 TCP connections to get the website. This is slow and can easily be improved with persistent connections, which means you can sequentially send several HTTP requests on one connection. The performance of non-persistent HTTP is quite bad, as you unnecessarly open a lot of connections between the same server and client.

4 Transport protocols

1 Reliability


See rdt2.0


Because the sender does not know what happened at receiver, it can't just retransmit the package (could be duplicate) or go on (maybe last package was not received). So this problem is not solved by this approach.


See rdt2.1

2 Go-Back-N

The Go-Back-N protocol is between a sender and a receiver. The sender has a sliding window, but the receiver does not(!). The sender can send up to all slots of his window, storing the packets at the same time in those slots of the window. As the receiver has no window, this means there is no buffering at receiver side, he only accepts the packet with the sequence number which is the next he expects. If the packet which arrives is the expected one, he sends back the ACK for that number. If the package is out of order, he ACK's the last packet which arrived in order. Always when the sender receives an ACK for a packet which is in his frame, he moves the window forth to the number after the just ACKed packet(cumulative ACKs). Other ACKed packets (outside his window) are ignored. The sender has one timer, always for the leftmost packet in his window. When this timer runs out, he resends all packets starting with this packet ("go-back-N").


1 Congestion window

The congestion_window will be set to 1500 Bytes, and the threshold to 13kB.

1 successful ;; congestion_window = 3000 Bytes -- because smaller than threshold
2 successful ;; congestion_window = 6000 Bytes -- because smaller than threshold
3 successful ;; congestion_window = 12000 Bytes -- because smaller than threshold
4 successful ;; congestion_window = 13500 Bytes -- because in exponential phase it's congestion_window = min ( 2* congestion_window, threshold)

2 Setting timeouts

Timeout too low: resend packets even if everything runs correct => leads to congestion.

Timeout too high: wait even if you could resend it => slows connection down

EstimatedRTT = (1-a) * EstimatedRTT + a * MeasuredRTT

Where MeasuredRTT is Time(ACK arrives) - Time(Packet sent).

Deviation = (1-b)* Deviation + b * |(EstimatedRTT - MeasuredRTT)|

So the final formula for the Timeout is:

Timeout = EstimatedRTT + 4 * Deviation

3 Connection setup

6 Network layer protocols


CIDR is a way to distribute IPv4 addresses. To a given IP address you also need the length of the network part. So this part determines the network a machine is in, and the rest of the IP determines in this network where the machine is. It was invented because static length of the network part (e.g. 8bit) led to a lot unused addresses in the networks (who uses 2^24 IP addresses within one network). With the new approach it is possible to allocate smaller chunks, so more networks can be created at different places. (This approach is necessary because the IP scheme is hierarchical).

2 Dijkstra’s algorithm

(D,0,-) ;; (B,6,B), (C,3,C) -- search for next node
(D,0,-), (C,3,C) ;; (B,6,B) -- adding C
(D,0,-), (C,3,C) ;; (B,6,B), (A,9,C) -- search for next node, found A
(D,0,-), (C,3,C), (B,6,B) ;; (A,9,C) -- adding B
(D,0,-), (C,3,C), (B,6,B) ;; (A,8,C) -- found shorter path to A
(D,0,-), (C,3,C), (B,6,B), (A,8,C) -- adding A, finished

7 Link layer protocols

1 Preamble

The preamble is a 7-byte sequence of 101010... followed by the byte 1010'1011. This sequence is used to give the machines listening on the wire the possibility to synchronize with the link. It is so long that all machines have enough time to synchronize with the link.

2 Cyclic Redundancy Checks

3 Framing and coding

(the _ indicates where a 's' or a '@' is introduced)