Computernetwerken en gedistribueerde systemen

Ga naar: navigatie, zoeken
PierreVerbaeten.jpg

Samenvattingen

Klik hier om de samenvattingen te bekijken

=Inleiding

Het vak Computernetwerken en gedistribueerde systemen bestaat niet meer vanaf 2006. Het nieuwe vak Gedistribueerde Systemen zal door een andere prof worden gegeven vanaf 2006-07, het deel van Computernetwerken zal vanaf 2007 of 2008 door een andere prof worden gegeven. Opgelet: Gedistribueerde Systemen is een GESLOTEN BOEK examen, in tegenstelling tot wat on line te vinden is. Mensen die hier niet van op de hoogte waren worden gevraagd dit aan de ombuds te melden.

Extra materiaal

Oplossingen Engelse Distributed Systems boek te vinden op: [1]

De (nederlandse) CWIS pagina met alle informatie omtrend het examen, te kennen leerstof en de slides kan je vinden op: [2]


Q & A

Stel hier uw vragen. Indien je het antwoord weet op een gestelde vraag gelieve die dan te beantwoorden.

  • Wat mag je meenemen op het examen?
    • Dit staat op het winaforum.[3]
Antwoord van Prof Verbaeten :

"Alles mag gebruikt worden.
Succes,
P. Verbaeten"


Greetz

Examens

Recente examens: Netwerken

Zie Computernetwerken.

Recente examens: Distributed

Zie Gedistribueerde Systemen.

Voorbeeldexamen

Deze vragen komen van het winaforum [4]. Ik laat ze samen staan inclusief feedback zodat ze een beter idee geven over het volledige examen. --Beau

Verbaeten is keirelax tijdens mondeling. Die houdt echt een babbelke me u. En hij stopt ook ni me kletsen. Toon interesse en kennis en tkomt in orde. Eerste vraag had ik zijn clue totaal gemist maar hij vond het niet erg omdat ik toonde dat ik er goed over had nagedacht Razz

1) mondeling : wat is transparantie van locatie. stel dat we een transportprotocol willen definieren, hoe kunnen we locatietransparantie hier dan in gebruiken? Welke problemen zouden zich voordoen en hoe lossen we deze op.

Transparantie van locatie is dat het voor het proces niet uit maakt waar de gegevens staan.  
Deze merkt geen verschil tussen locatie data en remote data.

Oplossen in transport protocol: Stabiel TSAP address (duidelijk NIET want dan is er geen transparantie!!)
Een Name Service gebruiken.

Zie slides: Map service name to TSAP Address. (Transport layer slides 20 & 22)

Dit is wat ik van de vraag denk dus niet aannemen dat het correct is.  Tom.

Een andere mogelijkheid is misschien een routing overlay zoals de distributed hash tables gezien bij p2p.
MobileIP zorgt ook nog voor locatietransparantie. --Beau

2) mondeling : leg PGP (pretty good privacy) uit. zeg wat elk van de stappen doen en wat er zou gebeuren als we ze weglaten

Zie Computernetwerken pg 806.  Pretty basic question :)

3) mondeling : Elections : kan als waarde voor een proces ook <1/load, i> gebruikt worden om het minst beladen proces te laten winnen? Want in de voorbeelden wordt altijd i gebruikt. (antwoord ja da kan want moet uniek en totaal rangschikbaar zijn. Wordt niet gebruikt omdat het niet zou gaan bij die technieken. Ring -> zou ni perse stoppen want load verandert, Bully moet op voorhand de waarden weten wat voor load ni zo is)

4) schriftelijk : Protocol 6 van datalinklaag, hier is een case voor als er een checksum error is. Stel dat we dit stukje code zouden weglaten (dat is het stukje dat de NAK send) zou het protocol dan nog werken (antwoord JA maar veel trager want wachten op timeout)

5) schriftelijk : gegeven een netwerkje (twee switches ondeling verbondenm eerste switch pcs A B C D tweede switch pcs E en F) Pcs D en F staan ingesteld o; af te luisteren. Dan geeft hij een lijstje van berichten (bvb A naar B) en ge moet zeggen welke D en F kunnen horen

6) schriftelijk : Ring election : geef de situatie (groep van processen die election starten) die zoveel mogelijk messages genereert, en die die zo weinig mogelijk messages genereert

Zo veel mogelijk messages: Er start een proces de election.  Het laatste proces in de ring heeft het hoogste nummer.
(Moet twee maal rondegaan worden om een elected message te kunnen versturen.  Deze moet ook weer rond dus 3 maal)

Zo weinig mogelijk: Het startend proces heeft het hoogste nummer.  1 maal rond voor te kiezen + 1 maal rond voor te zeggen wie het is.

Ik kan natuurlijk mis zijn.  Tom.

7) schriftelijk : CODA : hij geeft twee sets CVVS, en ge moet zeggen hoe die kunnen ontstaan (door netwerkpartitie etc) en hoe CODA ze zal oplossen (of confilct of niet blabla)

Oude Examenvragen

Vragen Computernetwerken


  • Een vraag ivm protocol 6 (glijdende vensters met selectieve herhaling): we beschouwen volgnummers van 4 bits. Stel dat de volgende venstergroottes gebruikt worden voor zend- en ontvangstvenster. Werkt het algoritme? Wat zijn de gevolgen?
    • 1 en 1
    • 1 en 8
    • 8 en 8
    • 15 en 8
    • 8 en 1
    • 15 en 15
Het venster van de ontvanger mag niet groter zijn dan 8 (MAX_SEC+1)/2. Anders krijgt men overlapping.
15/15 is dus niet in orde. 
1/1 = stop and wait, 
8/1 = go back n
de rest lijkt mij ok. Maar ben er niet zeker van :)  
Aanvulling: 1/8 is ook stop and wait, er zijn daar 7 overbodige buffers bij de ontvanger --Beau

  • Er was een tekening gegeven met 2 transparante bridges en een aantal

LAN's met enkele computers. Verder was de volgende tabel gegeven:

Bron Doel
1 A E
2 B C
3 C F
4 B E


Gevraagd: bepaal de inhoud van de routeringstabellen na zenden van de bovenstaande boodschappen. In het begin zijn de tabellen leeg.

  • Bespreek de werking van het externe gateway-routeringsprotocol BGP. Doe dit aan de hand van de volgende tekening (tekening met een aantal verbonden routers). Als afstand tussen twee aanliggende routers moet je 1 nemen.
  • dataverbindingsprotocol met satelietverbinding (100Kbps , 60.000 km).

Hoeveel pakketten van 8000 bits kan je verzenden in 1 minuut in een 3-bit sliding window protocol? Zijn er ontbrekende gegevens? Zo ja, geef ze en zeg waarom ze nodig zijn, doe een voorstel voor waarden.

1 pakket verzenden duurt 80ms, de transmissie duurt 200ms dus na 280ms is het eerste pakket aangekomen. 
Na 480ms komt de eerste bevestiging (onder ideale omstandigheden) terug aan. Bij een 3bit sliding protocol kunnen er 7 pakketten verzonden worden. 
7*80=560ms > 480ms, er komt een bevestiging binnen voordat de volgnummers opraken en men zal bijgevolg niet moeten wachten op bevestigingen.  
60.000ms / 80ms per pakket = 750 paketten. Iemand die dit kan bevestigen?
Aanvulling: ik veronderstel go back n, bij selectieve herhaling kunnen er slechts 4 pakketten tegelijk verzonden worden. 


  • hoe groot moet het venster van een zender zijn als hij continu pakketten wil blijven sturen naar een ontvanger, over een afstand van 60000 km, met een bandbreedte van 100 Kbps en een pakketgrootte van 8000 bits (het kan zijn dat de waarden iets anders waren, maar 't zal wel ongeveer juist zijn)
Wc = 1 + (2xIxC)/F
Wc = 1 + (2 x 270 x 100) / 8000     (270 komt uit de slides.  Als afstand groter is dan 3000 Km is I = 270msec)
Wc = 1 + 6.75
Wc = 7.75  (waarschijnlijk naarboven afronden)
(Iemand die dit kan bevestigen of weerleggen please)

Kun je de formules uitleggen? Wat is I, C, F ?
Analoog met de vorige vraag: 480ms eer dat eerste bevestiging aankomt, je moet dus 480 ms lang pakketten kunnen sturen
100Kbps = 100 bpms (bit per ms) => 48.000 / 8000 = 6 pakketten
Ik neem c = 300.000km/sec --Beau

C = channel capacity.  in dit geval 100
I = Propagation Delay + Interrupt & service time.  Hier de waarde uit de slides gehaald dus wrs fout ?!?! (slide 43 datalink layer)
F = Number of databits in Frame + number of databits in header.  Hier zou dat dan 8000 + 320 moeten zijn.
En de formule komt uit de slides voor de datalink layer.  Slide 41.

hmmmm, ik heb idd geen rekening gehouden met de header, 8000 in mijn berekening moet dan 8320 zijn. Verder klopt het wel imho.
I heb ik 200 genomen. Volgens de formule uit de slide zou het dan
Wc = 1+ 4000/8300 = moeten zijn. 
En volgens mijn redenering 48320 / 8320 (80ms moet 83.2 zijn door de header die erbij komt)
Dat is dus hetzelfde. Je berekening klopt dus, op de foute waarde van I na. --Beau


  • over zoiets dat net op 1li-list is gevraagd, nl. bereken de maximale gebruiksgraad van een satellietkanaal bij
    • stop-and-wait protocol
    • protocol 5 (van deel over datalinklaag)
    • protocol 6

Gegeven: satelliet op 36000km hoogte, pakketgrootte 10000 bits, kanaal 100kbps.

  • Beschouw een Lan CMCD/CA met bandbreedte van 1Gbps en een prop

van 200000km/s. Bereken de minimale pakket lengte en toon aan hoe je eraan komt.

  • Voor de verbinding tussen de campus van Leuven en de campus van Kortrijk (200 km) wordt gebruik gemaakt van een kanaal met een transmissiesnelheid van 1 Mbps en een 2 bit glijdend venster protocol. De maximale framegrootte bedraagt 5000 bits. Wordt het kanaal e±ciÄent gebruikt? Indien u meent dat er gegevens ontbreken, geef dan aan welke dat zijn, waarvoor die nodig zijn en maak een logische veronderstelling voor de waarden van die gegevens.
  • Bereken de maximale transmissiesnelheid (in KByte/sec) voor een transportverbinding waarbij gebruik gemaakt wordt van een 8 bit glijdend venster protocol, een maximale pakketgrootte van 128 bytes, en waarbij de maximale levensduur van de pakketten beperkt is tot 30 sec. Indien u meent dat er gegevens ontbreken, geef dan aan welke dat zijn, waarvoor die nodig zijn en maak een logische veronderstelling voor de waarden van die gegevens.
  • QoS: GCR bij ATM aangesloten aan 155Mbps, afspraak: 200.000 cellen/sec en max 5 paketten na elkaar. Bereken CDVT. en teken tabel gelijk 5.74 in boek 5. Wat loopt er allemaal mis indien ontvanger het pakket wegneemt uit tokenring in plaats van de zender? Beschrijf zo volledig mogelijk!
  • Routingtabellen opstellen met transparante bridges + tekeningske gegeven
  • Distance vector routing met split horizon hack, voer uit + tekeningske gegeven
  • LAN op ATM-netwerk. Hoe, beschijft het ATM-forum de oplossing en wat zijn de berichten die gestuurd worden. Zijn 2 logische LAN's op 1 ATM mogelijk? Geef uitleg.
  • Kabelvebinding tussen Leuven en Kortrijk, met een aantal gegevens over de lijn en gebruikt protocol. Wordt de lijn efficient gebruikt? (zoiets als in de voormiddag met die satellietverbinding).
  • BGP: hoe geraakt een router aan zijn routeringstabel, welke info krijgt hij

van zijn buren? Bespreek. Leg uit met een voorbeeldje.

  • ethernet aan één kant, token ring aan andere kant, A wil naar B zenden, ertussen zitten twee 'boxes' met een seriële lijn tussen... Bespreek wat de mogelijkheden zijn om die twee netwerken (en A en B er op) te verbinden, kies er één en bespreek die uitgebreider, geef tenslotte aan hoe de netwerklaag van A met de netwerklaag van B communiceert (tonen hoe paketten door de lagen gaan en adressen weten)
  • distance-based routing met split horizon hack voor een klein systeem van routers toepassen
  • mobiele hosts : hoe zendt een niet-mobiele host X een bericht naar een mobiele host M die zich verplaatst van een LAN A naar een LAN B
  • beschouw CSMA/CD : wat is de minimale framegrootte bij 10 Gbps, 1km?
Een frame moet zo groot zijn dat het niet verzonden is wanneer de eerste bit aankomt. 
1km = 0.00333 s vertraging. 10.000.000 bps * 0.00333 s = 33,333 bits
(edit)Ge zijt een paar nullen vergeten. het moet 1km = 0.00000333s zijn en 10Gbps is 10.000.000.000 bps. De uiteindelijke waarde is
wel hetzelfde. Andrew
  • satellietnetwerk met aantal gegevens, met stop and wait, p5 en p6. Wat is de efficientie van het kanaal?
  • Broadcast met reverse forwarding, hoe verloopt dat? Pas toe op voorbeeldje. Welke messages worden gestuurd?
  • IPv6: je hebt voor je bedrijf computersystemen gekocht en zet een netwerkje op, je gaat gebruik maken van IPv6, bespreek problemen en oplossingen in deze gevallen:
  1. wat als je als enig netwerk IPv6 gebruikt?
  2. wat als je enkel communiceert met andere netwerken die ook IPv6 gebruiken?
  3. wat als er mogelijk andere IPv6 netwerken zijn, maar communicatie enkel met IPv4 netwerken gebeurt?
1.Software moet mogelijk een beetje aangepast worden voor de grotere adressen
2.Geen probleem?
3.tunnels
  • Schema met 4 LAN's, verbonden met bridges, host Z is verbonden met elk van deze LAN's en in promiscue mode. (met bijvoorbeeld [netX=Y,Z] bedoel ik "een LAN X met daarop hosts Y en Z")

[net1=A,E,Z] Ã! bridge1 bridge1 Ã! [net2=B,Z] Ã! bridge2 bridge2 Ã! [net3=C,Z] bridge2 Ã! [net4=D,Z] (Note: iemand zin om hier een tekeningske in .eps van te maken? Ik zie het niet goed zitten...) Het hele systeem wordt gelijktijdig opgestart en dan worden 4 pakketten verstuurd:

    • B
    • E;D
    • B;E
    • D;A
    • E.

Bespreek welke pakketten Z ontvangt en vanwaar die kwamen.

  • gegeven is een schema van 4 netwerkjes (2 ethernet, 2 tokenring) verbon-

den door 2 routers. Je moet ip adressen toekennen en (statische) rou- teringstabellen opstellen en voor 3 bron-bestemming gevallen beschrijven hoe het pakketje gaat.

  • wat als we start_ack_timer() in protocol 6 weglaten? Werkt het

protocol dan nog correct? Geef een scenario om uw bewering te verduide- lijken.

Ack's kunnen dan enkel dmv piggybacking verstuurd worden. 
Indien er geen data terug te sturen is zal het protocol stilvallen.
  • transparante bridges: 4 LAN's verbonden door 2 bridges. We sturen ach-

tereenvolgens pakketten van een host naar een andere (4 bron-bestemming dinges gegeven). Schrijf na elke stap de tabellen van de bridges op (tabel bevat rijen van de vorm "host-naam netwerk-nr")

  • Ethernet en token ring LAN elk met onbekend apparaat ertussen die zijn

in serie geschakeld. Vraag: wat kunnen die dingen zijn? (opl: bridges of routers) + hoe pakket van host a op ether naar host b op ring sturen (protocol stapel + pakket met headers)

  • je moet een server maken met veel functionaliteit, bv naamserver, voor de communicatie met de server heb je keus uit volgende alternatieven:
    • proces
    • mailbox
    • poort
  • tokenring: proces komt erbij in promiscue mode. Geef alle pakketten +

type die dat proces ziet + afzender + bestemmeling

  • Protocol 6 bevat specifeke instructies voor de behandeling van een pakket

waarin een fout in de controlesom wordt vastgesteld (case chsum err of case ctlsom fout). Neem aan dat deze instructies verwijderd worden; is het protocol nog steeds correct? Omschrijf de gevolgen zo nauwkeurig mogelijk. Illustreer uw antwoord met enkele scenario's; maak deze zo con- creet mogelijk en zorg er voor dat het e®ect van de verwijdering duidelijk geijllustreerd wordt.

  • Geef de routeringstabellen van beide bruggen telkens na de verwerking

van een boodschap.

  • Geef de hopcounter een waarde ...
  • MobileIP (leg uit)
  • over transparante bridges en het achterwaarts leren. Gegeven 4 LAN's

met 2 bridges, en 1 machine die op alle LAN's zit. Welke pakketten ontvangt deze ene machine als er een boodschap van A in LAN1 naar E in LAN2 wordt gestuurd? En zo nog 3 andere boodschappen. Bij de laatste ontvangt de machine die op alle LAN's luistert niet meer op alle LAN's het bericht.

  • vraagje over protocol stacks en dergelijke.

Ge hebt een architectuur met een ² A op Lan Ethernet ² apparaat 1 op Lan Ethernet en via seriÄele lijn verbonden met appa- raat 2 ² apparaat 2 op Lan Token Ring ² B op Lan Token Ring Geef bondig de verschillende alternatieven voor die apparaten (komt erop neer da het router en bridge is). Toon hoe een pakket van A naar B wordt gestuurd. Teken de protocol stacks, al de headers met daarin de adressen in de vorm van IA (internet adres voor A) en EA (ethernet adres voor A).

  • vraag over 802.5 en token op ring. Wat als de ontvanger het pakket van de lijn haalt ipv doorstuurt? Geef de consequenties
  • vb van reverse path forwarding toepassen
  • dataverbindingsprotocol met satelietverbinding (100Kbps , 36.000 km).

Pakketten zijn 5000 bits lang. Hoe groot is de minimale framegrootte voor continue transmissie? Als er dingen niet gegeven zijn, geef dit dan aan en kies redelijke waarden ervoor.

  • QoS: GCR bij ATM aangesloten aan 155Mbps, afspraak: 200.000cel-

len/sec en max 5 pakketten na elkaar. bereken CDVT. en teken tabel gelijk 5.74a in boek waarin je duidelijk de 5 pakketten na elkaar aangeeft. Als er dingen niet gegeven zijn, geef dit dan aan en kies redelijke waarden ervoor.

  • TCP-transmissie: Het venster voor de ontvanger is 20 KBytes. De maxi-

male grootte van het segment is 1 KByte. Hoe lang duurt het eer het eerste venster helemaal verstuurd is bij de zender? Als er dingen niet gegeven zijn, geef dit dan aan en kies redelijke waarden ervoor.

  • Host A rechtstreeks op ATM-schakelaar

ATM subnet Router rechtstreeks op (andere) ATM-schakelaar Router tevens op Ethernet Host B op datzelfde Ethernet Ken (redelijke) IP adressen toe aan A, B en Router. Welke informatie bevat de routertabel minimaal? Hoe verloopt het zenden van een IP pak- ket van A naar B? Geef relevante hoofdingen in pakketten; welke adressen komen er in voor? Hoe verloopt het zenden van een IP pakket van B naar A? Geef vooral de verschillen.

  • De KULeuven huurt een verbinding van Leuven naar Kortrijk. De lengte

van die kabel is 200km. De transmissiesnelheid is 1Mbps. De gemiddelde pakket-grootte wordt geraamd op 5000 bits. We willen gebruik maken van een 2-bit sliding-window protocol. Wordt de kabel op die manier voldoen- de e±cint gebruikt? Welke fractie van de transmissiesnelheid wordt nuttig gebruikt (voor het verzenden)? Eindapparatuur op beide locaties hebben 1ms nodig voor de verwerking van een pakket. Welke gegevens ontbreken. Geef duidelijk aan en maak een geschikte keuze.

  • 4 netwerken:

Host A en E op netwerk 1 Bridge1 van netwerk 1 naar netwerk 2 Host B op netwerk 2 Host C op netwerk 3 Host D op netwerk 4 Bridge2 tussen netwerk3, netwerk4 en netwerk2 Host Z in 'a°uistermodus' aangesloten op alle netwerken Alles wordt gelijktijdig opgestart, en eerste dat verstuurd wordt is (in die volgorde:) (a) B ! E (b) D ! B (c) E ! D (d) A ! E Welke pakketjes krijgt Z, en vanwaar komen die?

  • Beschouw een machine A op een Ethernet netwerk en een machine B op

een Token ring netwerk. Verder bevindt zich op het Ethernet netwerk en het Token ring netwerk telkens een onbekende machine. De onbekende machines zijn verbonden via een serile lijn. Veronderstel dat machine A communiceert met machine B. Welke alternatieven zijn er dan voor de onbekende machines? Geef deze alternatieven en bespreek voor een van deze gevallen in detail (met protocolstapels) hoe de communicatie verloopt.

  • Token-ring LAN: Als ipv de zender de ontvanger een frame van de ring

zou halen bij het ontvangen van een frame, welke aanpassingen moeten er dan gebeuren aan het protocol? Zo volledig mogelijk.

  • Afstandsroutering met split-horizon hack: E verbonden met D, D met A

en C, en B ook met A en C. Bespreek de routeringstabellen voor E in alle routers en leg uit wat er gebeurt als E uitvalt.

  • Een aantal combinaties tussen zender- en ontvanger-vensters. Je mag er

vanuit gaan dat er geen volgnummers herbruikt moeten worden. Bepaal welke combinaties mogelijk zijn. Geef eventueel scenario's met verloren gegane en aangekomen pakketjes en leg uit waarom de onmogelijke com- binaties niet kunnen. voor de zender: ----- | | = zender heeft het bericht gestuurd, maar nog geen bevestiging | | gekregen ----- ----- |xxx| = zender heeft het bericht gestuurd, en een bevestiging |xxx| gekregen ----- voor de ontvanger: ----- | | = nog geen bericht gekregen | | ----- ----- |xxx| = bericht geregen en bevestiging verstuurd |xxx| ----- De vensters zagen er ongeveer zo uit (waarschijnlijk is dit niet letterlijk, maar alle moeilijkheden zitten er wel in denk ik, toch diegenen die ik gevonden had): 27 zender: ----------------------------- | | |xxx|xxx|xxx| | | | | |xxx|xxx|xxx| | | ----------------------------- ontvanger: ----------------------------- | | | |xxx|xxx| | | | | | |xxx|xxx| | | ----------------------------- zender: ----------------------------- | | |xxx|xxx|xxx| |xxx| | | |xxx|xxx|xxx| |xxx| ----------------------------- ontvanger: ----------------------------- |xxx| |xxx|xxx| | | | |xxx| |xxx|xxx| | | | ----------------------------- zender: ----------------------------- |xxx| |xxx|xxx|xxx| |xxx| |xxx| |xxx|xxx|xxx| |xxx| ----------------------------- ontvanger: ----------------------------- |xxx| |xxx|xxx|xxx| | | |xxx| |xxx|xxx|xxx| | | -----------------------------

  • Je krijgt een tekening van netwerken met transparante routers en hun

routertabellen. Zijn de waarden in de tabellen mogelijk? Indien niet, leg uit waarom niet. Dan krijg je een aantal pakketjes die van zender naar ontvanger moeten. Doe dat op basis van de gegeven routeringstabellen en vul desnoods de tabellen aan. Geef duidelijk aan wanneer °ooding nodig is.

  • Een QOS op ATM. 200000 cellen per seconde, 155 Mbps, en je wil een

burst van maximaal 5 cellen na elkaar toelaten. Wat moet L zijn? Maak 28 ook de tekeningen van fig 2.74.

  • (mondeling) Waarom kan BGP routing gebruik maken van TCP verbin-

dingen en OSPF niet? (vraag was iets langer geformuleerd dan dit, maar kwam hierop neer... het was iets wat em in de les uitgelegd had en volgens mij moeilijk te vinden is via hetgeen in de cursus staat)

  • Stel dat we een nieuwe netwerk-standaard willen op de markt brengen: we

nemen token-bus en voorzien die van een monitor. Welke functies moet deze monitor zoal hebben. Vergelijk met Token Ring.

  • Je wil 2 computers laten communiceren met een fiber-channel lijn. Je

gebruikt hiervoor TCP en de RTT voor boodschappen, onafhankelijk van hun grootte, mag je 20ms veronderstellen. De snelheid van de lijn is 500Mbps. Leg uit hoe je dit doet, welke venstergrootte en maximale segmentgrootte etc... je neemt. Hoeveel data kan je maximum van 1 computer naar de andere verzenden? Hoe e±ciÄent wordt de lijn gebruikt?

Vragen Distributed Systems


Time services

  • NTP: B ontvangt op 10:12:57,810 boodschap van A met tijdstempel 10:12:57,500.

A ontvangt op 10:13:03,400 boodschap van B met tijdstempel 10:12:59,210. Bereken de benadering voor het verschil tussen de 2 klokken + de nauw- keurigheid van dat verschil.

  • De NTP tijdserver B ontvangt van tijdserver A een boodschap op tijdstip

10:12:57,810; de boodschap bevat de tijdstempel 10:12:57,500; B stuurt een antwoord en A ontvangt deze boodschap op tijdstip 10:13:03,400; de boodschap bevat de tijdstempel 10:12:59,210. Bereken een benadering voor het verschil tussen de klokken in A en B en voor de nauwkeurigheid van dit verschil.

  • Gegeven een bericht van NTP tijdserver A naar tijdserver B en een be-

richt terug. Beide berichten bevatten een timestamp en de tijden waarop de berichten aankomen zijn gegeven. Bereken een schatting van het tijds- verschil tussen de 2 server en een schatting van accuraatheid van deze schatting.

  • Een master-server in het Berkerly algoritme start op tijdstip 10:12:10,500 (door een broadcast naar de andere computers) en krijgt volgende replies van zijn client computers:
    • 10:12:10,690
    • 10:12:10,600
    • 10:12:10,450
    • 10:12:10,570

Wat zijn de volgende stappen in het algoritme: werk uit. Indien je extra waarden nodig hebt kies je zelf zinvolle waarden.

Distributed file systems

  • vraag met AFS en gelijktijdig schrijven, zijn de gegeven mogelijkheden juist?
  • AFS en gelijktijdige writes (gemakkelijk, die vraag staat ier al een paar keer, ga hem nie herhalen).
  • NFS
    • write(ufid1, 2, 1111)
    • write(ufid2, 6, 22)

Wat zijn de verschillende resultaten ?

  • NFS: bestand (abcd)(efgh) van 8bytes, 2blokken (van 4bytes) prog1 en

prog2 gebruiken gelijktijdig dat bestand. (Note: write (bestands-u¯d, positie in bestand, "nieuwe tekst") => positie begint bij 0 1 2 ufid1=open(..) . . . ufid2=open(..) write(ufid2,2,"22") . . . write(ufid1,1,"1111") . . . write(ufid2,4,"44") . . . Je krijgt volgende resultaten: ² (a122)(44gh) ² (a111)(44gh) 20 Zijn deze resultaten mogelijk? Leg uit.

  • AFS met reads en writes. Programma's worden op 2 werkstations uitgevoerd en in de tijd kunnen de opeenvolgende bewerkingen in het programma alle mogelijke volgordes aannemen. Het kan bv. ook zijn dat programma 1 volledig voor programma 2 wordt uitgevoerd.

Client 1 Client 2 ufid1=open(. . . , Äex-file", . . . ) . . . ufid2=open(. . . , Äex-file", . . . ) . . . read(ufid2, 0, 8) . . . . . . write(ufid1, 2, "1111") . . . . . . write(ufid2, 2, "22") . . . close(. . . ., Äex-file", . . . ) . . . . . . close(. . . ., Äex-file", . . . ) . . . 4 uitkomst-mogelijkheden gegeven, geef aan of ze mogelijk zijn of niet. Indien mogelijk, zeg hoe. Indien niet mogelijk, zeg waarom niet. ² ab22efgh 30 ² ab2211gh ² ab11efgh ² ab1111gh

  • Beschouw het NFS bestanden systeem en een bestand dat bestaat uit

2 blokken (a b c d)(e f g h). Elk blok bestaat uit 4 karakters van 1 byte. Het bestand bestaat dus slechts uit 8 bytes. Beschouw verder de operaties open, close, read en write. De operaties read en write hebben als eerste argument de UFID van een bestand, als tweede argument de positie binnen het bestand waar de operatie begint, en als derde argument het aantal opeenvolgende bytes waarop de operatie een bewerking uitvoert. Bytes worden genummerd vanaf 0. Beschouw dan twee clients 1 en 2, die operaties uitvoeren als volgt: 24 Client 1 Client 2 ufid1=open(. . . , Äex-file", . . . ) . . . ufid2=open(. . . , Äex-file", . . . ) . . . read(u¯d2, . . . , . . . ) . . . . . . write(ufid1, 2, "1111") . . . . . . write(u¯d2, 2, "22") . . . close(. . . ., Äex-¯le", . . . ) . . . . . . close(. . . ., Äex-¯le", . . . ) . . . Veronderstel dat het bestand zich bevindt op een server en clients 1 en 2 toegang hebben tot het bestand vanop 2 werkstations (verschillend van de server waarop het bestand staat). Wat zijn dan de mogelijke resultaten? Wat is het resultaat indien clients 1 en 2 processen zijn op de server?

  • AFS: bestand (abcd)(efgh) van 8bytes, 2 blokken (van 4bytes) prog1 en

prog2 gebruiken gelijktijdig da bestand 1 2 ufid1=open(..) ... ufid2=open(..) data=read(ufid2,....) ... write(ufid1,2,"1111") ... write(u¯d2,2,"22") ... Geef mogelijke resultaten!

  • NFS: 2 programma's die tegelijkertijd een bestand van 2 blokken van 4

bytes gebruiken. welke resultaten kan je krijgen en hoe?

  • AFS: 2 programmas gegeven + bestandje. Programmas doen bewerkingen op bestand. Gegeven zijn aantal mogelijkheden als resultaat van de bewerkingen van de programmas. Uitvoering van de programmas is niet tijdsgebonden (dus kunnen tegelijk, voor of achter elkaar uitgevoerd worden). Zeg voor elke mogelijkheid of ze kan, en waarom/waarom niet.

Election

  • ring-election algortime, ring van 4 processen:

5 14 2 16 Het aantal messages hangt af van wie en hoeveel beginnen zenden! Geef de groep/proces die moet beginnen zenden voor minimaal en voor maximaal aantal election messages.

  • ring-based electoin algoritme:

11 5 14 2 16 Stel dat ze alle 4 op hetzelfde moment het algoritme starten, hoeveel election-berichten worden er dan verstuurd?

  • Beschouw het ring election algoritme dat wordt toegepast op de ring 7-16-

2-21-29-7. Een proces dat een verkiezing start, zendt een election bood- schap naar het volgende proces uit de ring. Bereken het maximum aantal election boodschappen dat kan voorkomen als een proces of groep van processen een verkiezing start. Zelfde vraag voor het minimum aantal boodschappen.

  • Ring-gebaseerde verkiezingsalgoritme: Verklaar waarom het zeker is dat

alle election-berichten uitgestorven zijn voor het elected-bericht wordt ver- zonden

  • ring based election, alle leden van de ring starten tegelijk een verkiezing: bereken het totaal aantal messages voor iemand verkozen is + toon hoe dit gebeurt
  • Ringbased Election: zijn volgende situaties mogelijk? Zo ja, welke proces-

sen zijn participant. Zo nee, leg duidelijk uit waarom de situatie onmoge- lijk is. De ring was: 7-16-2-12-29-7-... (a) token met waarde 2 op (2-12) // token met waarde 16 op (12-29) (b) token met waarde 12 op (12-29) // token met waarde 29 op (7-16) (c) token met waarde 16 op (7-16)

  • het ringalgoritme voor mutual exclusion (de gemakkelijksten, die 2 namen, weet ze niet meer) illustreren (4 objecten).

De toestanden:

    • A: HELD
    • B: WANTED
    • C en D: RELEASED

illustreer volgende events door alle berichten en toestanden van de objecten te tonen.

  • (a) C en D willen allebei gelijktijdig toegang tot kritieke code
  • (b) A geeft lock vrij.


(distributed) Mutex

  • Gedistribueerde Mutual Exclusion oefening: 4 processen die met logical clock 0 beginnen en dan verschillende stappen doorlopen; voer het algoritme uit.
  • zeg voor de 4 algoritmes voor gedistribueerde mutual exclusion of ze voldoen aan ME3 of niet + informeel bewijs of tegenvoorbeeld
  • mutual exclusion met multicasting en logische klokken. Geef de toestanden

(staat, klok en queue) van 4 processen doorheen een bepaalde situatie

  • mutual exclusion algoritme (dat waar iedereen moet toestemming geven):

als een proces meerdere keren na elkaar de CS binnen moet, zonder dat een ander proces dat ook wil, is het algoritme niet efficiÄent. Verbetering ? Bespreek kritisch.

  • Gebruik het gedistribueerde algoritme voor mutuele exclusie op een voorbeeld dat niet in de cursus/slides staat. Maak duidelijk dat de logische klokken belangrijk zijn. Zijn de logische klokken op een juiste manier gebruikt? (bijvraag: kan het ook met fysische?)
  • Gegeven een beschrijving/tekening van een gedistribueerde geneste transactie. Geef de datastructuur die door de servers wordt bijgehouden op volgende momenten:
    • vlak voor een bepaalde transactie start.
    • vlak voor het gedistribueerde commit protocol wordt gestart.
    • als het protocol volledig beeindigd is.
  • Mutual Exclusion, Central Server. Pas het algoritme aan zodat klantproces-falingen opgevangen worden. Je hebt een betrouwbare detector ter beschikking. Centrale server faalt niet. Bespreek kritisch
  • distributed mutex algoritme uitleggen aan de hand van beschreven gebeurtenissen. (Dus niet zelf een vb verzinnen).
  • Bully election algo. 5 processen. 3 niet beschikbaar. Der wordt een terug

opgestart, teken welke messages er verstuurd worden. Dan gaat er ene down, tekenen. En dan komt er nog ene terug op, tekenen.

  • gedistribueerde mutex: geef de gegevensstructuren van de 4 processen.

Initieel heeft p1 de lock, dan:

    • p2 vraagt lock
    • p1 geeft lock vrij
    • p3 en p4 willen tegelijk lock
    • p2 geeft lock vrij
  • We beschouwen een systeem waarin de processen het algoritme van Ricard

en Agrawala volgen voor het realiseren van wederzijdse uitsluiting. Ieder proces in dit systeem vertoont volgend gedrag: de kritische sectie wordt herhaaldelijk betreden en verlaten, vooraleer een ander proces toegang tot de kritische sectie vraagt. Het algoritme van die twee gasten is one±ciÄent in deze situatie; hoe kan het aangepast worden? Bespreek kritisch het aangepaste algoritme.

Overige vragen

  • Beschouw een transactie T die start op een server A (genoteerd als T

@ A). Vervolgens starten subtransacties van T, namelijk T1 en T2, op B en C (T1 @ B en T2 @ C). Hierop volgen de subtransacties T11 @ D, T12 @ C, T21 @ D en T22 @ E. Is het mogelijk dat een subtransactie die voorwaardelijk gecommit heeft, niet betrokken wordt bij het 2-phase commit algoritme? Illustreer dit aan de hand van een voorbeeld waarbij je de gegevensstructuren die de verschillende servers bijhouden vermeldt. Moet het algoritme uitgebreid worden, en zo ja, hoe?

  • 2fase-commit. Het is mogelijk dat de knoop waarop een subtransactie wordt uitgevoerd niet betrokken wordt in het commit-proces. Wanneer is dit? Geef tekening. Moet het protocol aangepast/uitgebreid worden, hoe?
  • transactie met subtransacties, teken de tabellen uit, ongeveer zoals in de slides p.139-141 staat
  • Coda

Er zijn een aantal versievectoren gegeven: hoe bekomen, hoe behandeld?

  • Gossip: timestamps van Replica Servers gegeven + timestamp van Front

End. Mag query gebeuren en op welke servers? Zelfde vraag voor updates.

  • implementatie van een remote procedure call met at-most-once semantiek

met een onbetrouwbare send en receive operatie.

  • transaction diagram (gelijk die hele hoop slides daar)
  • RM gegeven: 3 RM met timestamps, timestamp van FE. Welk ¶e¶en kan

direct een query beantwoorden? Welk ¶e¶en kan direct een update beant- woorden?

  • Wissel in het algoritme voor R-multicast mbv B-multicast de regels R-

deliver m en if (p!=q) ..... . Wordt nog voldaan aan uniform agreement? Hoe zit het met die variant bij R-multicast over IP-multicast? (Note: dit is vraag 11.12 uit het boek)

  • Schema: \z" wil zeggen \een boodschap die verstuurd wordt", \Z" wil

zeggen \diezelfde boodschap die ontvangen wordt". P1 ---------a----b----A-----B----C---- P2 ------------------B-----C----A----- P3 ----------------A---c----B----C---- met ---tijd--> (Note: iemand zin om hier een duidelijk tekeningske van te maken? Ik zag het niet zitten. . . ) Enige ordening hierin? Wat moeten we doen om totale ordening te ver- krijgen? Je mag enkel ontvangen berichten later zetten in de tijd (naar rechts verschuiven dus)

  • Commit algoritme:

transactie T (op A) start de boel

    • T ! transactie T1 (op B)
    • T ! transactie T2 (op C)
    • T1 ! transactie T11 (op D)
    • T1 ! transactie T12 (ook op C)
    • T2 ! transactie T21 (op E)
    • T2 ! transactie T22 (op F)

(Note: iemand zin om een tekeningske te maken?) 12 Kan het voorkomen dat een knoop waarop een transactie gebeurd is niet betrokken is bij commit? Zo ja, geef vb? Hoe kan algoritme verbeterd worden?

  • Coda: 4 servers met een bestand X. Gegeven 2 situaties van CVV's:

[2; 1; 1; 1]; [1; 1; 1; 1]; [2; 1; 1; 1]; [1; 1; 1; 1] en [1; 1; 1; 1]; [1; 2; 1; 1]; [1; 1; 2; 1]; [1; 1; 1; 1] Leg voor elke situatie uit hoe ge daar aan kunt geraken doordat er par- tities zijn in uw netwerk. En zeg wat er gebeurt als de partities terug samenkomen

  • Gegeven een niet blokkerende send en een blokkerende receive operatie,

niet betrouwbaar (pakketjes kunnen verloren gaan). Schets de implemen- tatie van een at-least-once RPC met deze operaties (enkel het communi- catie gedeelte).

  • at-least-once semantiek bij RPC over onbetrouwbaar kanaal
  • over ordening bij multicast (FIFO-ordering, causal ordering, total ordering). Gegeven een voorbeeld, is dit in een bepaalde ordening en hoe zou je er een totale ordening van kunnen maken als je enkel deliveries in tijd naar achter mag verplaatsen.
  • iets over nested transactions en commit
  • Gossip: er zijn 3 RM bij een gossip architectuur met timestamps [8,,],

[8,5,4], [6,,] (de rest van de waarden weet ik niet meer) en een FE met timestamp [7,5,3]. Geef aan welke direct kan antwoorden bij een query van die FE en hoe de timestamps evalueren! Doe hetzelfde voor een update. (=ongeveer, zo precies weet ik het niet meer, heb de opgave niet echt mee)

  • moeilijke vraag over global states. toepassen op een raarrrr voorbeeld
  • Het algoritme van Ricart en Agrawala is niet efficient als een proces meer-

dere keren de kritische sectie wil betreden, terwijl er geen andere processen zijn die ook willen. Pas het algoritme aan, zodat het e±ciÄenter wordt. Be- spreek je nieuwe algoritme kritisch.

  • Je hebt een onbetrouwbare send en receive; dit wil zeggen:
    • uitgezonden pakketen koment niet noodzakelijk aan, maar wanneer ze aankomen zijn ze foutloos
    • non-blocking send, blocking receive
    • Hoe kan at-most-once RPC gemplementeerd worden?
    • Vergelijk met maybe-semantiek.
    • Verklaar waarom iedere boodschap verzonden wordt.
  • Gedistribueerde transacties:

(eigenlijk geneste)

    • Host A transactie T
    • Host B transactie T1
    • Host C transactie T2 en T12
    • Host D transactie T11
    • Host E transactie T21
    • Host F transactie T3 en T22

T1 voorlopige commit gedaan, T2 ook. (volgorde is als volgt: T @ A, T1@ B, T11 @ D, T12 @ C ! T1 voorlopige commit;T2 @ C, T21 @ E, T22 @ F ! T2 voorlopige commit; T3 @ F)

    • Is het mogelijk dat een knoop, waarop een subtransactie is uitgevoerd, niet betrokken is bij het commit-protocol? Wanneer doet een dergelijke situatie zich voor? Illustreer met bovenstaand voorbeeld, waarbij je de gegevensstructuren (nodig voor het commit protocol) op de verschillende knopen toont. Moet het protocol worden aangepast of uitgebreid? Hoe eventueel?
  • Oefening op Coda: 2 processen die gelijktijdig in bestand schrijven, 4 resultaten gegeven, welke zijn mogelijk? waarom? waarom niet?
  • Het algoritme voor multicast op basis van IP heeft een aantal erg onpraktische veronderstellingen. Kan je hier iets aan doen? Hint: Wanneer kunnen pakketjes weggegooid worden?
  • Een proces stuurt op 14:12:10,500 een klokrequest naar enkele processen die in een Berkeley algoritme samenwerken. De reply's zijn gegeven. Voer het algoritme uit en leg uit. Ontbrekende gegevens mag je indien nodig zelf aanvullen met realistische waarden.
  • Een heel schema met subtransacties en commit/aborts. Geef de datastructuur zoals op transparant 149 op verschillende momenten tijdens de uitvoering en het commit-protocol.
  • Global states: beschouw onderstaand systeem met unidirectionele verbin-

dingen. P R Q X Y Een bericht x wordt voortdurend heen en weer gestuurd van P naar Q naar P naar R naar P naar Q enz... Een bericht y wordt voortdurend heen en weer gestuurd van P naar X naar P naar Y naar P naar X enz.. Elke entiteit houdt haar state bij als het aantal keer dat een bericht is gepasseerd. P heeft uiteraard twee tellers: th en tv. Initieel zijn alle tellers 0 en op een gegeven ogenblik staan de tellers van P op (10,11). Nadat P bericht x en y heeft uitgestuurd wordt het snapshot algoritme gestart. Geef aan hoe het algoritme verder verloopt en met welke global states. Zijn er verschillende opeenvolgingen mogelijk? Verklaar.

  • Gossip: in een gossip systeem heeft de front end vector timestamp (3, 5, 7)

en de replica managers respectievelijke vector timestamps (5,2,8), (4,5,6) en (4,5,8). Welke replica manager(s) kunnen onmiddellijk een query van de front end beantwoorden en wat is de resulterende timestamp? Zelfde vraag voor een update (Deze oefening is dus totaal analoog als oefening 14.13 in het boek, doch met andere cijferwaarden)

Ik heb de waardes aangepast naar die van de boek zodat onderstaande oplossing overeenkomt. --Beau

Uit de oplossingen van de boek:
The only replica manager that can satisfy a query from this front end is the third, with (value) timestamp
(4,5,8). The others have not yet processed at least one update seen by the front end. The resultant time stamp
of the front end will be (4,5,8).
Similarly, only the third replica manager could incorporate an update from the front-end immediately.