Computernetwerken en gedistribueerde systemen

Oplossingen Engelse boek te vinden op: [1]

• Gebruik het gedistribueerde algoritme voor mutuele exclusie op een voor-

beeld 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 trans-

actie. 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 beÄeindigd is.

• 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.

• 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 2 ² 8 en 8 ² 15 en 8 ² 8 en 1 ² 15 en 15

• 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.

• 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

• 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.

• Routingtabellen opstellen met transparante bridges + tekeningske gegeven

• distance vector routing met split horizon hack, voer uit + tekeningske

gegeven

• 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?

• Coda

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

• 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 e±cient gebruikt? (zoiets als in de voormiddag met die satellietverbinding).

• BGP routing uitleggen aan de hand van een tekening.

• distributed mutex algoritme uitleggen aan de hand van beschreven ge-

beurtenissen. (Dus niet zelf een vb verzinnen).

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

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

• AFS: 2 programmas gegeven + bestandje. Programmas doen bewerkin-

gen 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 wor- den). Zeg voor elke mogelijkheid of ze kan, en waarom/waarom niet.

• ethernet aan ¶e¶en 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 verbin- den, kies er ¶e¶en 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)

• protocol 6 voor data link, wat als de venstergrootte verandert (1-1, 1-8,

8-1, etc.)

• distance-based routing met split horizon hack voor een klein systeem van

routers toepassen

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

met een onbetrouwbare send en receive operatie.

• 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

• transactie met subtransacties, teken de tabellen uit, ongeveer zoals in de

slides p.139-141 staat

• 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

• 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 Mbps en een pakketgrootte van 8000 bits (het kan zijn dat de waarden iets anders waren, maar 't zal wel ongeveer juist zijn)

• beschouw CSMA/CD : wat is de minimale framegrootte bij 10 Gbps, 1km?

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

bytes gebruiken. welke resultaten kan je krijgen en hoe?

• mutual exclusion met multicasting en logische klokken. Geef de toestanden

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

• 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.

• 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 e±ciÄent. Verbetering ? Bespreek kritisch.

• satellietnetwerk met aantal gegevens, met stop and wait, p5 en p6. Wat

is de e±cientie van het kanaal?

• BGP: hoe geraakt een router aan zijn routeringstabel, welke info krijgt hij

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

• Broadcast met reverse forwarding, hoe verloopt dat? Pas toe op voor-

beeldje. Welke messages worden gestuurd?

• 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)

• Berekeningetje hoeveel pakketten kun je zenden in 1 minuut over een

satelietverbinding van: 100Kbps, 60.000km, pakket=10.000 bits met een sliding window protocol met 4-bit vensters kies andere nodige gegevens zelf.

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

len/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 token- ring in plaats van de zender? Beschrijf zo volledig mogelijk!

• 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. 9

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

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

• IPv6: je hebt voor je bedrijf computersystemen gekocht en zet een net-

werkje op, je gaat gebruik maken van IPv6, bespreek problemen en oplos- singen in deze gevallen: ² wat als je als enig netwerk IPv6 gebruikt? ² wat als je enkel communiceert met andere netwerken die ook IPv6 gebruiken? ² wat als er mogelijk andere IPv6 netwerken zijn, maar communicatie enkel met IPv4 netwerken gebeurt?

• Glijdende vensters, 4 bits (0-15), bespreek als zender/ontvanger vensters =

1/1, 1/8, 8/1, 8/8, 15/8, 8/15 in elk van deze gevallen, als goed: bespreek e±ciÄentie, indien slecht: geef voorbeeld waar het mis gaat.

• 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.

• 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?

• Schema: \z" wli 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?

• 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 else start ack timer() in protocol 6 weglaten? Werkt het

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

• 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")

• 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).

• Bully election algo. 5 processen. 3 niet beschikbaar. Der wordt ¶e¶en terug

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

• 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)

• 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

• protocol 6 aangepast naar variabele venstergroottes (zonder code gegeven,

gewoon aannemen dat het kan). Is het volgende geldig + waarom wel/niet ? <venstergrootte zender, venstergrootte ontvanger> <1,1> <1,5> <5,5> <5,1> <5,9> <9,9>

• vraag over gedistribueerde transactie, staat in blaadjes WINA???

• je moet een server maken met veel functionaliteit, bv naamserver, voor de

communicatie met de server heb je keus uit volgende alternatieven: (a) proces (b) mailbox (c) poort

• tokenring: proces komt erbij in promiscue mode. Geef alle pakketten +

type die dat proces ziet + afzender + bestemmeling

• 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.

• Protocol 6 bevat speci¯eke 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 . . .

• 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.

• NFS

write(ufid1, 2, 1111) write(ufid2, 6, 22) Wat zijn de verschillende resultaten ?

• MobileIP (leg uit)

• over zoiets dat net op 1li-list is gevraagd, nl. bereken de maximale ge-

bruiksgraad 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.

• 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.

• at-least-once semantiek bij RPC over onbetrouwbaar kanaal

• over ordening bij multicast (FIFO-ordering, causal ordering, total orde-

ring). 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

• 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).

• De verschillende grootes voor vensters (1-1, 1-8, 8-1, 8-8, 15-8, 8-15) voor

selectief repeat. Geef aan welke fout/juist zijn met vb en zeg iets over hoe goed ze zijn.

• 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.

• AFS en gelijktijdige writes (gemakkelijk, die vraag staat ier al een paar

keer, ga hem nie herhalen).

• 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 objec- ten te tonen. (a) C en D willen allebei gelijktijdig toegang tot kritieke code (b) A geeft lock vrij.

• 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)

• zeg voor de 4 algoritmes voor gedistribueerde mutual exclusion of ze vol-

doen aan ME3 of niet + informeel bewijs of tegenvoorbeeld

• vraag met 10 volgnr sliding window met selectieve herhaling. Gegeven 6

situaties, leg uit of ze werken en hoe e±cient ze zijn. 1-1 1-5 5-1 5-5 9-5 5-9

• vraag over 802.5 en token op ring. Wat als de ontvanger het pakket van

de lijn haalt ipv doorstuurt? Geef de consequences.

• vb van reverse path forwarding toepassen

• vraag met AFS en gelijktijdig schrijven, zijn de gegeven mogelijkheden

juist?

• moeilijke vraag over global states. toepassen op een raarrrr voorbeeld

• Het algoritme van Ricart en Agrawala is niet e±ciÄent 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.

• 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.

• 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 u¯d1=open(..) . . . u¯d2=open(..) write(u¯d2,2,"22") . . . write(u¯d1,1,"1111") . . . write(u¯d2,4,"44") . . . Je krijgt volgende resultaten: ² (a122)(44gh) ² (a111)(44gh) 20 Zijn deze resultaten mogelijk? Leg uit.

• 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)

• 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?

• Je hebt een onbetrouwbare send en receive; dit wil zeggen:

22 ² 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.

• 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.

• 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?

• 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.

• Voor de verbinding tussen de campus van Leuven en de campus van Kort-

rijk (200 km) wordt gebruik gemaakt van een kanaal met een transmissie- snelheid 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 trans-

portverbinding waarbij gebruik gemaakt wordt van een 8 bit glijdend ven- ster 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.

• 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 u¯d1=open(. . . , Äex-¯le", . . . ) . . . u¯d2=open(. . . , Äex-¯le", . . . ) . . . read(u¯d2, . . . , . . . ) . . . . . . write(u¯d1, 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?

• 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.

• 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?

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

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

• 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.

• Gedistribueerde Mutual Exclusion oefening: 4 processen die met logical

clock 0 beginnen en dan verschillende stappen doorlopen; voer het algo- ritme uit.

• Satelliet verbinding

• 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 onprak-

tische veronderstellingen. Kan je hier iets aan doen? Hint: Wanneer kunnen pakketjes weggegooid worden?

• 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 ¯g 2.74.

• 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 data-

structuur zoals op transparant 149 op verschillende momenten tijdens de uitvoering en het commit-protocol.

• (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 ¯ber-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?

• AFS met reads en writes. Programma's worden op 2 werkstations uit-

gevoerd en in de tijd kunnen de opeenvolgende bewerkingen in het pro- gramma alle mogelijke volgordes aannemen. Het kan bv. ook zijn dat programma 1 volledig voor programma 2 wordt uitgevoerd. Client 1 Client 2 u¯d1=open(. . . , Äex-¯le", . . . ) . . . u¯d2=open(. . . , Äex-¯le", . . . ) . . . read(u¯d2, 0, 8) . . . . . . write(u¯d1, 2, "1111") . . . . . . write(u¯d2, 2, "22") . . . close(. . . ., Äex-¯le", . . . ) . . . . . . close(. . . ., Äex-¯le", . . . ) . . . 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

• 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 (..,..,..), (..,..,..) en (..,..,..). 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) 31