Lösungsvorschlag Operating Systems And Computer Networks FS10

Aus VISki
Wechseln zu: Navigation, Suche

1 Application-level protocols

Question 1.1

  • «stateless»: Server maintains no information about past client requests
  • disadvantages of stateful protocols:
    • stateful protocols are way more complicated (keep state in sync, transitions, ...)
    • past history must be maintained (more memory/disk space needed, cpu time, ...)
    • caching is not possible, because the server can send different replies for the same query

Question 1.2

HTTP is stateless, but states can be accomplished by cookies

2 Centralizing DNS

Question 2.1

centralized DNS would not need:

  • NS Resource Record
  • TTL (Time To Live) not needed anymore

Question 2.2

reasons why centralizing DNS would not be a good idea:

  • single point of failure
  • traffic volume
  • performance (high RTT)
  • maintenance
  • bad scalability
  • bad security

3 Network programming

Question 3.1

blocking I/O with threads:

  • advantages
    • easier to program & understand (read code from top to bottom per connection)
  • disadvantages
    • does not scale well (a lot of connections mean a lot of threads)

event-driven I/O:

  • advantages
    • works with only one thread
    • scales very well
  • disadvantages
    • harder to program & understand (callbacks)
    • hard to deal with long running operations

Question 3.2

difference in the operating system kernels I/O subsystem:

blocking I/O with threads:

  • needs blocking system-calls

event-driven I/O:

  • needs non-blocking system-calls

4 Transport protocols and performance

Question 4.1

If an ACK is corrupted, the receiver considers the transmission as completed, but the sender will wait forever, since he only considers ACKs or NACKs. If a NACK is corrupted, the receiver waits for the retransmission forever, because the sender will wait forever to detect a ACK or NACK

Question 4.2

Sender side:

If the sender receives a corrupt answer, he has to retransmit the packet. But the receiver needs to be able to detect, whether the packet is a retransmission or a new packet. Therefore, we need sequence numbers (1 bit is enough for this purpose). The sender now retransmits the packet with the same sequence number as before. This leads to four states: "Wait for call from above 0", "wait for answer 0", "wait for call from above 1", "wait for answer 1"

Receiver side:

If the receiver has now two states, "wait for 0" and "wait for 1" The receiver only delivers data to the application on a transition from "wait for 0" to "wait for 1". The ACKs or NACKs are always handled the same way.

For all transitions see: Slide on page 15/16

Question 4.3

  • Bandwidth: 10 Gbps
  • Propagation delay: 1 ms
  • Packet size: 1 kb (this is stange, why not kB? typing error?)

Utilization = (packet size / (2 * propagation delay)) / bandwidth = (1 kb / 2 ms) / 10 Gbps = 0.5 Mbps / 10 Gbps = 1/20'000

5 Protocol overheads

Question 5.1

Process:

Client A creates a TCP connection to client B

  1. SYN with sequence number a, sent to B
  2. SYN + ACK with sequence number b, acknowledgement a + 1
  3. ACK with acknowledgement b + 1

Example:

  1. A sends: SYN, Sequence = 100
  2. B sends: SYN + ACK, Sequence = 500, Acknowledgement = 101
  3. A sends: ACK, Acknowledgement = 501

Why is it necessary to exchange such information?

If a packet is corrupted, such that it becomes a SYN-packet, if we have only a two way handshake, B accepts this unwanted connection. If we have a one-way handshake, A doesn't know, whether B accepted the connection. Three-way handshake solves this problem. Accidental SYN do not lead to connections on any side, both parties know when a connection is established.

We use sequence numbers for both nodes, because the nodes need to know, in which order the packets should be. We use a random sequence number, because a old connection could otherwise interfere with a new connection on the same port. We increase the sequence numbers in the handshake, because it is easier to implement.

Question 5.2

  • Bandwidth: 10 Gbps
  • Propagation delay: 1ms
  • Initialization packet size: 100 B

Time to establish connection =

6 Flow control

Question 6.1

Problem of flow control:

  • Sender and receiver don't know how much resources the communication partner can use for this connection, therefore they need to regulate the communication speed.

Mechanisms:

  • Receiver informs sender about the amount of free buffer space (receive window)
  • Sender keeps the transmitted unacked data less than the most recently received receiver Window

Data structures:

  • Receiver buffer: buffer for received packets
  • Receiver window: unused space in receiver buffer
  • Send queue: Queue of packets to send
  • Send window: part of the send queue (sent, but unACKed + unsent, but ready)

7 Delay and bandwidth

Question 7.1

  • Data size: 10 TB
  • Distance: 10 km
  • Bandwidth: 10 Mbps
  • Speed: 20 km/h
  • time to copy to 5*2TB harddisks = n

Transfer over the network:

  • Time_1 = Data size / Bandwidth = 10 TB / 10 Mbps = 8'000'000 s = 92 days 14 hours 13 minutes 20 seconds

Transfer by bicycle:

  • Time_2 = n + Distance / Speed = n + 10 km / 20 km/h = n + 0.5 h
  • Time_2 < Time_1 if n < 92 days 13 hours 43 minutes 20 seconds

Question 7.2

Bicycle bandwidth = 10 TB / (n + 0.5 h) = ? => if n = 0 then 20 TB/h

8 Count to infinity

Example:

A <==1==> B <==1==> C

  • B has a connection to A with weight 1
  • C has a connection to A with weight 2 via B

A <==X==> B <==1==> C

  • Link from B to A is broken
  1. B needs a new connection to A and asks C => new connection for B with Cs value + 1
  2. B notifies C that its connection has changed
  3. C updates its connection weight
  4. C notifies B
  5. B updates its connection weight
  6. goto 2

It happens, because there are cycles in the network graph and no one detects updates in cycles.

 But your topology does not contain any cycle.. What do you mean by cycle? (Jan Veen 02.07.15)

Outline of the solution by BGP

  • save the path to the target along with the other routing information
  • if a router asks for updates, paths containing his name are ignored

9 Slow convergence

See Slides on page 104

When a link breaks, some nodes start to consider alternative routes over nodes which haven't propagated the dead link yet. => leads to slow convergence

It happens because the nodes only consider their neighbours and not the whole path.

10 NAT

Problem it solves:

  • Make it easy to change the provider
  • Make it easier to add new computers to the network
  • Security
  • Shortage of IPv4 addresses

Problem it tries to solve: unknown

Disadvantages:

  • Additional overhead
  • Computers in the network cannot be servers (unless some port-forwarding technique is used)
  • Overhead to rewrite packet headers to address correct host behind NAT (external_ip:port to internal_ip:port)

How it works?

  • Connections, initiated by computer of the local network are tracked
  • Multiplex, based on the stored information of the sessions
  • => Modification of IP-Headers and Ports

11 Link layer

Question 11.1

The preamble is used to synchronize the clocks of the network participants. Its always 0x55555555555555 and at the beginning of each ethernet-frame.

Wrong: It's actually 0x55 0x55 0x55 0x55 0x55 0x55 0x55 0xD5. On the wire the bit pattern looks like this: 10101010 <- 7 times and then 10101011

Question 11.2

When we have n nodes in a hubbed network, the probability of a collision grows linearly dependent on n. With more collisions, the network utilization converges to zero.

12 Spanning Tree

Question 12.1

problems witch cycles in switched networks

Question 12.2

See Slides Page 54

  • create graph
  • calculate minimum spanning tree
  • deactivate all links that are not in the minimum spanning tree

13 Scheduling

Question 13.1

I/O-bound:

  • Use a lot of blocking I/O-systemcalls => often switch back to the scheduler before their quantum has ended
  • The bottleneck is the I/O device

CPU-bound:

  • Do not use a lot of blocking I/O-systemcalls => often use their whole quantum
  • The bottleneck is the CPU

Question 13.2

The I/O-bound tasks do not use much time to block again => another task is scheduled. Because the I/O is slow, the CPU-bound task wont starve (all I/O devices are busy) => only CPU-bound tasks can be scheduled.

14 Virtual Memory

Question 14.1

40 ns

  • 20 ns for page table access
  • 20 ns for memory access

Question 14.2

0.25 * 20 ns + 20 ns = 25 ns

15 Page replacement

Question 15.1

  • More page frames do not necessary lead to less or equal page faults.
  • FIFO shows this anomaly

Question 15.2

1 2 3 4 2 1 5 6 2 1 2 3 7

frame 1 frame 2 frame 3 frame 4
1
2
3
4
2
1
5
6
2
1
2
3
7

8 page faults

16 Working set

Working set: Set of page references a process has used in the last k instructions

Useful to minimize thrashing and optimize parallelism

17 Buffer management

Question 17.1

Concept: mbufs form together a linked list of linked lists of messages and message parts.

Problems:

  • Unified format for half-defined packets
  • Easily add/remove headers
  • Avoid copying lots of payload
  • Fragment large datasets

Question 17.2

  1. Variable packet size
  2. Linked List of different packets

18 Disk access

  1. RAM-disk
  2. Special file
  3. Network share
  4. Virtual file systems (they are not necessarily on the disk)
  5. Disk removed while computer is running
  6. Data in the cache

19 File representation

Question 19.1

An inode is a data structure that contains metadata, probably some data and block references.

Metadata

  1. Creation date
  2. Modification date
  3. Archive-bit
  4. System-file-bit
  5. Compression-metainformation
  6. Rights
  7. Size
  8. Other metadata

Question 19.2

Filename: because there can be multiple names to one inode

The file names are saved in the data-blocks of the directories inode.

20 Links

20.1

In the context of the folder that contains the hard link, the name of the hard link is mapped to the inode which the target of the link pointed to when the hard link was created.

A symbolic link is a file, that contains a name, which is probably the name of another file.

20.2

The question is probably wrong.

Interpretation 1: There exists already a file in a folder, with a hard-link and a soft-link to it in another folder. This interpretation ignores, that we could create a new soft-link to the hard-link.

  • After changing the access-rights to the first folder, the hard-link can access, and the soft-link can't.
  • After a rename of the file, the hard-link is still valid, and the soft-link isn't


Interpretation 2: We can create new soft-links or hard-links.

  • This has no solutions, because we can always create a soft-link to the hard-link.


Interpretation 3: There exists a file, to which either a hard or a softlink has to be made, but only the former is possible

  • An open file whose hard links have all been deleted should meet the requirements. Before creating a new hard link, no soft link can access the file.


Interpretation 4: No restriction.

  • It's possible if there is a security hole

Interpretation 5: Two hard links. And one hard link might be in a directory we do not have access rights to.