diff options
Diffstat (limited to 'sem5/net/eksamnen/noter_spgs.md')
| -rw-r--r-- | sem5/net/eksamnen/noter_spgs.md | 779 |
1 files changed, 779 insertions, 0 deletions
diff --git a/sem5/net/eksamnen/noter_spgs.md b/sem5/net/eksamnen/noter_spgs.md new file mode 100644 index 0000000..ee89462 --- /dev/null +++ b/sem5/net/eksamnen/noter_spgs.md @@ -0,0 +1,779 @@ +# Topic 1 Time order + +## Distributed system + +N nodes working together on a overall task. +Interacting via communication network. + +Challenges include. + +- Bad communication channel +- Global state is hard +- Local clocks may not be in sync +- Ordering of subtasks +- Handling faults or malicous behavior + +Ways to implement ordering. + +- Clock synchronisation +- Use of logical clocks +- Algorithms that do not rely on order of events + +## Time and clocks + +Monotonicity +: Når et ur ikke kan gå tilbage i tiden. Altså hvis `t1 > t2`, så er t1 senere end t2. + +Local clocks have drift. +To make them usefull, they must have bounded precision and accuracy. + +## Notions of time + +- UTC +- Internal clocks + Often implemented with a counter function, which counts at a given frequency. +- "Time-stamping" + Event ordering + +## Clock synchronization + +Uses measured round trip time to calculate the delay of the received time. + +Clients can either pull a server, or the other way around. + +### NTP + +Clients can pull times from another server. +Builds a tree of servers. + +Represents time using number of seconds since 1900-01-01. +Timestamps all messages, and timestamps of recent events. + +Accuracy is ~1ms for LAN and ~tens of ms for Internet. + +## Ordering + +Total order is if for all times `a` and `b`: `a > b or b > a`. +So all times can be compared. + +Transisive relation +: If `a, b` can `b, c` can be compared then `a, c` can too. + +Irreflexive +: That `a, b` cannot be compared. + +If precise physical clocks are posible, total order can be achieved. + +Partial order implies that concurrent events can occur. + +## Partial order + +Important to be able to say a happened before b, as a could affect the result of b. + +Consistent clock +: If a happened after b then `C(a) < C(b)`. Where C translates event to time. *Strictly consistent* if the reverse is also true. + +Local logical clocks can do this internally in precesses and between processes. + +Causal order +: Her kigger man på om et event A kan have forårsaget B. + +## Scalar logical clocks + +Have a counter which is incremented before each event. +Include this counter in each message sent. + +When a recipeint receives a message set its counter to either its own or the senders depending on which is largest. + +Scaler clocks are not strictly consistent, but can be used to define total order. + +### Vector based + +Each node keeps a vector of the logical clocks of all other nodes. + +# Topic 2 Algorithms and Consistency + +## Mutex locking + +Different solutions. + +Simple: A node can request a lock by sending a request, and locking nodes can object. +Requires: + +- FIFO: message order between processes is preserved +- Every messages is received +- Each process can communicate with all other + +## Leader election + +Contralized control is useful in some algorithms. +If done distributedly all nodes must be able to take this role. + +Requires a algorithm to elect leader. +Can be done with mutex locking, but better methods exist. + +Nodes broadcast their role id(random) at a random time. +If a node hasn't received at higher id, it broadcasts its own. + +## Transaction and consistency + +Transaction properties: + +- Atomicity (result is either commit og abort, not a half failure state) +- Durability (persistent results) +- Isolation (current transactions do not influence other transactions) +- Consistency (transactions go from a consistent state to another) + +Global state cut +: Taking a snapshot of consistent state, not including transactions. + +Different cuts/snapshots. + +- Strongly consistent: No messages in transit +- Consistent cut: Messages in transit not included +- Inconsistent cut: Messages in transit are included + +## Computational model + +Includes read and write, FIFO queues, stacks etc. + +Can be implemented as: + +- Central storage +- Master storage and copies +- Fully symmetric distributed storage + +Consistency criteria +: correctness of result of distributed sequence of operations. + +### Linearizability + +A sequence of events are linearizable consistent if: + +- If a sequential order can give same result +- This sequential order is consistent with the real order of events + +Requires global time, and limits concurrentcy. + +### Serializability + +- If the sequential order is consistent with the real order of operations on each node. + +# Topic 3 OSI + +Layered protocol to ease implementation of layers and adding new layers. +As layers only talks to the layers above and under. + +1. Physical layer: + Defines physical things like voltage, frequency etc. + Different services which next layer relies on. +2. Data link layer: + Breaks data from physical layer into packets, and handling error at the physical link. + Includes ethernet. +3. Network layer: + Handles routing of packets across the network. + Where things go from single hop to many hops. + Implements the Internet with IP addresses. +4. Transport layer: + Handles end to end connections, where ports live. + Where connections are implemented, such as in TCP. +5. Session layer: + Handles session :-). + Things like *authorization* and *authentication*. +6. Presentation layer: + Formatting of data, such as MIME, ASCII or PGP. +7. Application layer: + Applications such as web browsers, ssh or email. + +## Connection oriented + +Simple communication can just send a packet with a destination on it. +If the packet is lost it is just lost. + +A connection can be setup, packets can be sent and it cna be torn down. +This allows for re-transmission and re-ordering of packets. + +# Topic 5 Mac and link layer + +Started with telephone switching where two are connected using a continues connection. +When computers came packet switching was created for internet packets. + +These where combined when packet switching became fast enough. + +## Link layer + +Often comes in short burst + +Use *error correction* when retransmission or feedback channel is not available. + +### ARQ + +ARQ (Automatic Repeat Request) handles errors and retransmission. + +Uses different retransmission strategies: + +- Stop and wait: + Vent på ACK før den næste packet skal sendes. +- Go back N: + Sender will keep a window of sent windows and will keep track of which sequence number has been received. + It will go back if missing. +- Selective repeat/selective reject: + Receiver selectively says which frames are missing. + +#### Hybrid ARQ + +Combination of error control schemes. + +Type-1 +: Error detection and correction. + +Type-2 +: On a good channel use pure ARQ, if not add more parity bits. + +## MAC + +Multiaccess media instead of point to point. +Requires Media Access Control sublayer. + +Different way to have multiple devices talk on one line. + +### Static allocation + +Devide channel in portions and allocate these to devices. +This can be done in different ways: + +- SDMA (space devision): + Segment using space, as with different directed antennas or wires. +- TDMA (time devision): + Have devices transmission time slots. +- FDMA (Frequency devision): + +Static allocation can be good with a small number of devices. +But not to good if many devices or bursty traffic. + +#### Frequency hopping + +Combination of FDMA and TDMA. +Can be done with fast hopping (for every symbol) or slow hopping (for every message). + +Can withstand interference, as multiple frequencies are used. + +Synchronization and discovery can be a challenge. + +This can be done by first sending a seed and offset. +And then a new clock reference is sent with every packet. + +This requires that slaves can't got to sleep for too long. + +### Dynamic schemes + +#### Random schemes + +Direct transmission without contention phase, so collision are very possible. +Suitable for short messages, which can afford to be retransmitted. + +##### Aloha + +Transmit immediadly, incase of collision retransmit after random time. + +Special case of stop and wait. + +**Slotted aloha** created slots where transmission is allowed. +Not as many collisions, as only start can go wrong. + +##### CSMA + +Listen before talk, as listening is not super demanding. +Does not relieve of collisions, because sending takes time. + +1-persistent +: Send if the channel is idle. + +Non-persistent +: Send if idle, if idle send. If not idle then wait for random period of time. + +Can deploy collision detection to stop the transmission if a collision happens. + +*Consensus reenforcement* what? + +#### Slotted systems + +Assign allowed transmission times to slots. + +Can use base station as reference, but distributed is much harder. + +#### Reservation schemes + +Devices signal they want to sent in a contention phase. +The winning device will get to send a message collision free. + +Nice for long messages. + +#### Collision detection in radio + +Harder as with wire, as the signal is weaker throughout the range. +Often not implemented in wireless systems. + +ACK is often required. + +#### Wireless problems + +*Hidden terminal* is when a collision happend between two temrinals which can't see each other. + +*Exposed terminal* is when a station can't transmit because the channel looks busy, but really transmission is possible. + +#### MACA + +Uses signalling packets for collision avoidance. +Terminal sends RTS (Request) and receiver can answer with CTS if the channel is ready. + +Avoid hidden terminal, but not exposed terminal. +As requests will collide at B. + +# Topic 6 WLAN + +Architecture in networks: + +- Station (STA): + Terminal with radio which communicates with access point. +- Basic Service Set (BSS): + Group of stations using the access point +- Access point: +- Portal: + Bridge to other wires network +- Distribution system: + Interconnected network to form one logical network. + +*Adhoc* network are only between stations directly. +Important word is IBSS (Independend Basic Service Set), which is a group of stations using the same frequency. + +*Direct communication* is when a station functions as a access point. + +TODO der står en del om PCF i slides. + +## MAC + +Two different schemes: + +- Distributed Coordination Function (DCF): + Implementation of adhoc networks and all users contend to accessing the channel. +- Point Coordination Function (PCF): + Is based on polling, performed by a AP. + +These want to achieve two *traffic services*. + +- Asynchronous Data Service (mandatory): + - Support for multicast and broadcast. + - Priority networks. +- Time bounded service (optional) + - Implemented using PCF. + +## Carrier sensing + +Can be done in two different ways. + +- Physical carrier sensing: + Detects activity on the channel via signal strength. +- Virtual carrier sensing: + Detects from received header information, where packets say how long they utilize the channel. + +The channel is marked busy if one of them indicate a busy channel. + +## NAV + +Network Allocation Vector is used by stations to predict the duration of the current transmission. + +## Performance + +Theoretical throughput calculates throughput deterministic analysis. +Does not take collisions and channel errors into consideration. + +Multihopping in networks can give problems as it blocks many connections. + +TCP also gives poorer performance as it quickly breaks. + +A good solution would be multi-radio per station so forwarding can be done on another channel. + +## Transmission range + +Limited by 3 different things. + +- Transmission range: + Limited by the transmission power and radio propagation. +- Physical carrier sensing range: + Is the range where another station. + This is larget than the transmission range. +- Interference range: + Range which the transmission will cause interferenence on a receiver. + +## Access methods + +- DFWMAC-DCF CSMA/CA (mandatory): + - Collision avoidance with back-off mechanism. + - Using ACK for non broadcast packages. +- DFWMAC-DCF w/ RTS/CTS (optional) +- DFWMAC-PCF (optional): + Access point polls terminals according to a list. + + Pull data in a superframe, which is started with a beacon from AP. + +# Topic 7 Bluetooth + +Bluetooth uses frequency hopping. + + +Alternates RX and TX meaning master always transmit on odd time slots, and a slave transmit on even time slots. +A slave can therefore not initilize a conversation itself. + +## Discovery + +Complex in bluetooth classic and takes some time. + +Bluetooth low energy has 3 advertisement channels where devices discover each other. + +## Different link types + +- Synchronous Connection Oriented for voice: + - Circuit switched with preallocated bandwidth. + - No retransmission + - Symmetric +- Asynchronous Connection Less for data: + - Variable time slots + - Uses ARQ protocol + - Symmetric +- eSCO for streaming: + - Retransmissions immediately after received slot. + - Symmetric or asymmetric + +Symmetric means that RX packets are the same type as TX. + +## Errors + +Can use different error correction schemes: + +- 1/3 FEC where each bit is 3 times. + Uses majority voting. +- 2/3 FEC uses math to encode 10 bit code to 15 bit code. So 1 parity per 2 bits. + +But can also use ARQ schemes. + +## Energy states + +Active +: Channel is active and slave and master are kept in sync. + +Sniff +: Slave only listens for synchronization beacons at specific times, this entering low power mode. + +Hold +: Can be used if other actions must be performed such as participating in other networks. +: Here it will only listen for specific messages. + +Park +: Master parks slaves to support many devices is piconets. + +## Interference + +Bluetooth utilizes AFH (Adaptive frequency hopping) where is tries to avoid frequencies where many collision happen. + +# Topic 8 CAN + +Why use a fieldbus instead of dedicated wires: + +- Cost savings +- Reduction of weight +- Reliability +- Easier fault diagnosis +- Redundancy + +Fieldbusses often implement multiple OSI layers, and the layers 3 to 6 are non existent. + +## CAN + +CAN is good for noisy environments. + +CAN uses an single set of wires where everything is broadcast transmissions. + +Synchronization is required and resyncrhonization is done by looking at edges of signal. +Because of this, long silent sequences should be avoided. +This is done with bit shuffling of bits. + +Requires the idea of *dominant bits* which are explained in the question section together with addressing and priority. + +### Messages types + +- Data frame: a frame containing node data +- Remote frame: a request for a specific ID +- Error frame: transmitted by a node on error +- Overload frame: used to create a delay if more time is needed + +# Spørgsmål + +If we answer a question nicely and quickly, we just get another question. +We should not work hard to scretch time. + +## Time, synchronization and order + +1. **Explain the need for clock synchronisation by giving an example scenario. Provide an example synchronisation approach for 2 nodes and discuss its advantages/disadvantages** + +**Ide 1:** + +A distributed chat system requires must be able to preserve order of messages and their received times. +Conversations often have questions which other can answer, which can be confusing if the order is skrewed up. + +It is also important for users to see when messages where sent. + +1. Alice sends a message to Bob. +2. Bob will respond with a ACK. +3. Alice sends the measured round-time to Bob. +4. Bob sends the measured round-time to Alice. +5. Alice and Bob independedly calculate the average delay between the two round times. +6. The one behind sets it's clock to the most forward one. + +The has the advantage that it works without a central time server, however comes with many problems. + +- Alice and Bobs clocks will quickly come out of sync with the rest of world, making the timestamps useless for users. +- This requires alot of extra traffic + +**Ide 2:** + +Many websites often have authenticated user interaction, where users log in to a session. +This is often implemented with a server recording sessions and their expire time. + +If this is to be done distributed between multiple server, all servers must have + +2. **Explain the concept of causal partial order using an example event diagram.** + +Svaret i notesbog. + +3. **Explain the motivation and realization of a logical clock using an example.** + +Multiple users add and remove text to a distributed document sharing program. + +When a users adds text it sends only the addition and where it happened to other clients. +It is therefore important which order changes arive in as they depend of the previous state of the document. + +However it does not matter which time edits happen on so a real clock is not needed. +Therefore a logical clock can be used to insure additions are applied in the right order. + +Shown in notebook. + +4. **Explain vector clocks and scalar logical clocks using an example and discuss their differences** + +Scalar clocks are implemented as a simple counter, counting up for each action. +On receiving a message which a clock value a client takes the biggest. + +If two events have et same scalar clock value, its not possible to determine their order. +Scalar clocks have eventual consistent time. + +Vector clocks have a counter for each node, which gives more insight into the order of messages. +This has the advantage that one can see if one event caused another as it is causaly consistent. + +Se sammenligning notesbog. + +## Distributed exclusion, consistency + +5. **Explain the'distributed mutual exclusion' problem and compare it to a centralized approach.** + +When sharing resources like memory or devices between multiple nodes, it is often unwanted to have multiple nodes access it. +For example if multiple nodes want to add 3 to a shared variable. + +Adding often consist of multiple operations: + +1. Retrieve +2. Add locally +3. Store + +This is an issue with multiple nodes wanting to add 3. +Mutual exclusion is therefore needed, where a node locks the resource while operating on it. + +A centralized method is by having a locking variable which can be read and set atomicly, facilitated by an operating system. +However this is not possible in a distributed system, as a centralized lock server is unwanted. + +Instead notes broadcast a lock request, which all other nodes must grant. +A node can then only get the lock if all other nodes permit it. + +This comes at a much larger performance cost as the centralized approach. + +TODO here a contralized approach may refer to in distributed systems. + +6. **Give an example of a distributed read and write operation sequence and explain two different consistency criteria.** + +The example can be seen in notebook. + +Linearizability, order of events must be preversed on all nodes. +So the example is not linearizable as no valid order can be found. + +`r_1` must read a `d` before `r_2` can an `a`, meaning `w_1` must happen after `r_1` which is not allowed. + +With sequantial order, time order at each node must be preserved (`w_1` must happen before `r_2`). +So a valid order is. + +`w_1(a), r_2(a), w_2(d), r_1(d), w_3(e), r_3(e)`. + +## OSI model + +7. **What are the advantages of a layered architecture? Explain functionalities of different layers of OSI model.** + +Se det der er skrevet oppe i noterne. + +## Techniques used at Data Link Layer: ARQ and MAC concepts + +8. **Explain the three types of ARQ protocols.** + +Stop and wait is when the next packet can't be sent without a ACK from the previus. + +Go back N will implement a window of packets available to be sent, and will keep track of the latest ACKED packet. + +This allows for the receiver to sent multiple packets thus utilizing bandwidth. + +In selective repeat the sender will send many packets and will check which are received. When it will only retransmit the ones that where not ACKED. + +9. **Explain the difference between error correction and error detection. Give examples when it is preferable to use one or another, or a combination of them.** + +Error correction is when parity data is used to correct errors. +This requires alot of extra parity data, used to reconstruct the original signal. + +Error detection is when terminals check for error but cant fix them. +This is often done with CRC, and then not sending an ACK if a invalid packet was sent. + +Error detection can be done with much smaller overhead, but requires to a channel to send NACK or ACK. + +If this is not available error detection is a bit useless as a retransmission cant be signalled. + +Therefore error correction is better. +Error correction is also better for channels with high latency as retransmission are expensive. + +10. **Give examples of MAC protocols with static channel allocation. Discuss their advantages anddisadvantages.** + +TODO + +Focus on FDMA and TDMA. +Obvius advantage is that every thing is nice static and periodic. + +If dynamic requires a central entity which makes allocations. + +11. **Explain the principle behind a Random Access class of MAC protocols. Give an example of a such a protocol.** +TODO +12. **Explain main features of Carrier Sense Multiple Access (CSMA) protocol, including the differencebetween non-persistent and 1-persistent versions.** +TODO + +## WLAN IEEE 802.11 standard + +13. **Explain the Random backoff time mechanism used in the standard. Explain how prioritizationof different messages is realized.** + +If the medium is busy multiple devices can wait to send efter. +A random backoff period is introduced to break this summetry. + +This is also called a *contention window* where devices fight to be able to send. +Each devices chooses a random count number and counts down. +The first one to reach 0 can start sending. + +Priority is implemented with the delay from end busy time to backoff window. +Devices with a smaller delay will have an advantage in the contention window. + +The delays are as follows in order of smallest first: + +- SIFS (Short Inter Frame Spacing): for high priority such as ACK, CTS or polling responses. +- PIFS (PCF IFS): For timebounded services implemented in PCF. +- DIFS: Lowest priority, for asynchronous data. + +14. **Explainthe “handshaking” mode of operation (with RTS/CTS messages) and basic mode (without RTS/ CTS) and the associated trade-offs.** + +Handshake done before sending between A and B. + +A sends a request (RTS) to send to B, and B will respond (CTS) as soon as it is ready to receive. + +This enables other stations close to A or B to see that something is going to happen. +This also solves the hidden terminal problem. + +However comes at a bandwidth reduction, and does not work well with multicast and broadcast. + +Good to use with large frames or when collisions are likely. + +## Bluetooth + +15. **Explain the principle of frequency hopping as well as its advantages and challenges in terms of channel sharing and coordination.** + +Frequency hopping is the combination of TDMA and FDMA. +It has the timeslots of TDMA, but with each new time slot a new frequency is chosen. + +These frequencies are chosen a random meaning different networks can communicate in the same frequency range if they use a different random seed or offset. + +Frequency hopping has the advantage of being very resilient to interference, and the timeslots give it predictable behavior. + +However initial configuration is challenging as all nodes must agree on a clock offset and seed. +Also clocks must be kept up to date as drifting can cause nodes to get out of sync. + +16. **Explain what is a piconet and how data is exchanged between a master and slaves (polling; time synchronization; slot structure; packet types).** + +Piconet is a small bluetooth network which allows multiple slaves to connect to the same master device. +Each piconet may contain up to 7 simultaneous nodes, and many more parked slaves. + +The master controls all communication in the piconet, so no slave-to-slave communication is possible. +Communication is done using polling where the master will poll a slave with a null packet and it can answer with data. + +Polling happens in time TDD (time division duplex) with 625 us size slots. +Time slots are in the range 0 to 227-1, so each node does the same frequency hopping. + +Master sends at odd time slots and slaves at even, and because all traffic is controlled by master contention between nodes is avoided. + +Packet types: + +- ID packet +- NULL, so only contains access code+header +- POLL: used by master to force a response from a slave +- FHS: Used for synchronization to exchange clock and ID information +- DM1: Can carry payload + +## Field busses - CAN bus + +17. **Explain the role of the frame ID in the priority arbitration scheme used in CAN. Explain what is a dominant and a recessive bit. Show an example of bit sequencesof two frames with different IDs that are transmitted at the same time.** + +Many devices can share a single CAN bus, and priority is therefore beneficial. + +In a CAN bus each message is sent with a frame ID, which also functions as a priority. + +For example all messages belonging to brakes can have a low ID=2 (low is higher priority) while speedometer can have a higher ID=20. + +Other nodes can then listen in on a specific message ID they are interested. + +This is implemented with the idea of a *dominant bit*, where a line has a default state (recessive) until someone actively does something. +So if one devices writes OFF and another writes ON the dominant bit decides what is read on the line. + +When a nodes wants to transmit a frame it will start by transmitting the frame ID. +Other devices can then chime in with their own ID. +If a node measures that its write dominated by another node it will stop. +Nodes with lower ID will therefore win over ones with higher ID. + +``` +FRAME 23: 00000010111 +FRAME 3 : 00000000011 +``` + +Here frame id=3 will win. + +## Network layer and routing + +18. **You regulate a flow of packets using a token bucket, feeding into a leaky bucket.** + Assume that the token bucket has a rate of 5 packets per second, and a capacity of 60 tokens. + The leaky bucket has a rate of 20 packets per second. Assume that the token bucket isempty. + 200 packets has arrived. How long will it take before all packets have left? +19. **Explain flooding and broadcast storm problem in ad hoc networks.** +20. **Explain the difference between proactive and reactive routing approaches.** +21. **Explain the main principles of Dynamic Source Routing protocol.** + +## Transport layer + +22. **Explain how TCP achieves reliable in-order delivery of TCP segments. What is the role of a receiver buffer and how is receiver buffer overflow prevented?** +23. **Explain the congestion control mechanismof TCP (slow-start phase and congestion avoidance).** +24. **What are the possible problems of executing TCP over a wireless technology? How can these be mitigated?** + +## Introduction to Fault Tolerance + +25. **A server node shows has a down-time of 20 hours per year. Show how to calculate the resulting availability Pr(Server operational). ** + Extend your derivation to the case of aredundant structure of 3 servers. + Show how to calculate its availability assuming independent faults. + + +26. **Discuss advantages and disadvantages of cluster structures (that hide the redundancy to accessing nodes) as opposed to an architecture where failover is done via the Clients (such as RSerPool)** |