Lösungsvorschlag Operating Systems And Computer Networks FS10
- 1 1 Application-level protocols
- 2 2 Centralizing DNS
- 3 3 Network programming
- 4 4 Transport protocols and performance
- 5 5 Protocol overheads
- 6 6 Flow control
- 7 7 Delay and bandwidth
- 8 8 Count to infinity
- 9 9 Slow convergence
- 10 10 NAT
- 11 11 Link layer
- 12 12 Spanning Tree
- 13 13 Scheduling
- 14 14 Virtual Memory
- 15 15 Page replacement
- 16 16 Working set
- 17 17 Buffer management
- 18 18 Disk access
- 19 19 File representation
- 20 20 Links
1 Application-level protocols
- «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
HTTP is stateless, but states can be accomplished by cookies
2 Centralizing DNS
centralized DNS would not need:
- NS Resource Record
- TTL (Time To Live) not needed anymore
reasons why centralizing DNS would not be a good idea:
- single point of failure
- traffic volume
- performance (high RTT)
- bad scalability
- bad security
3 Network programming
blocking I/O with threads:
- easier to program & understand (read code from top to bottom per connection)
- does not scale well (a lot of connections mean a lot of threads)
- works with only one thread
- scales very well
- harder to program & understand (callbacks)
- hard to deal with long running operations
difference in the operating system kernels I/O subsystem:
blocking I/O with threads:
- needs blocking system-calls
- needs non-blocking system-calls
4 Transport protocols and performance
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
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"
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
- 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
Client A creates a TCP connection to client B
- SYN with sequence number a, sent to B
- SYN + ACK with sequence number b, acknowledgement a + 1
- ACK with acknowledgement b + 1
- A sends: SYN, Sequence = 100
- B sends: SYN + ACK, Sequence = 500, Acknowledgement = 101
- 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.
- Bandwidth: 10 Gbps
- Propagation delay: 1ms
- Initialization packet size: 100 B
Time to establish connection =
6 Flow control
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.
- 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
- 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
- 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
Bicycle bandwidth = 10 TB / (n + 0.5 h) = ? => if n = 0 then 20 TB/h
8 Count to infinity
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
- B needs a new connection to A and asks C => new connection for B with Cs value + 1
- B notifies C that its connection has changed
- C updates its connection weight
- C notifies B
- B updates its connection weight
- 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.
Problem it solves:
- Make it easy to change the provider
- Make it easier to add new computers to the network
- Shortage of IPv4 addresses
Problem it tries to solve: unknown
- 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
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
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
problems witch cycles in switched networks
See Slides Page 54
- create graph
- calculate minimum spanning tree
- deactivate all links that are not in the minimum spanning tree
- 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
- Do not use a lot of blocking I/O-systemcalls => often use their whole quantum
- The bottleneck is the CPU
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
- 20 ns for page table access
- 20 ns for memory access
0.25 * 20 ns + 20 ns = 25 ns
15 Page replacement
- More page frames do not necessary lead to less or equal page faults.
- FIFO shows this anomaly
1 2 3 4 2 1 5 6 2 1 2 3 7
|frame 1||frame 2||frame 3||frame 4|
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
Concept: mbufs form together a linked list of linked lists of messages and message parts.
- Unified format for half-defined packets
- Easily add/remove headers
- Avoid copying lots of payload
- Fragment large datasets
- Variable packet size
- Linked List of different packets
18 Disk access
- Special file
- Network share
- Virtual file systems (they are not necessarily on the disk)
- Disk removed while computer is running
- Data in the cache
19 File representation
An inode is a data structure that contains metadata, probably some data and block references.
- Creation date
- Modification date
- Other metadata
Filename: because there can be multiple names to one inode
The file names are saved in the data-blocks of the directories inode.
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.
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.