Distributed Systems PDF

Rechnernetze und Kommunikationssysteme Chapter 1 Introduction Dr.-Ing. Torben Weis University Duisburg-Essen Uses of Computer Networks ∙ Business Applications ∙ Home Applications ∙ Mobile Users Distributed Systems Torben Weis 2 University Duisburg-Essen Bus...

Rechnernetze und Kommunikationssysteme Chapter 1 Introduction Dr.-Ing. Torben Weis University Duisburg-Essen Uses of Computer Networks ∙ Business Applications ∙ Home Applications ∙ Mobile Users Distributed Systems Torben Weis 2 University Duisburg-Essen Business Applications of Networks A network with two clients and one server. Distributed Systems Torben Weis 3 University Duisburg-Essen  Business Applications of Networks (2) The client-server model involves requests and replies. Distributed Systems Torben Weis 4 University Duisburg-Essen Uses of Computer Networks ∙ Business Applications ∙ Home Applications ∙ Mobile Users ∙ Broadcast Distributed Systems Torben Weis 5 University Duisburg-Essen Home Network Applications ∙ Person-to-person communication ∙ Interactive entertainment ∙ Smart Home ∙ Internet-of-Things Distributed Systems Torben Weis 6 University Duisburg-Essen Home Network Devices ∙ Computers ∘ Desktop PC, PDA, shared peripherals ∙ Entertainment ∘ TV, DVD, VCR, camera, stereo, MP3 ∙ Telecomm ∘ Telephone, cell phone, intercom, fax ∙ Appliances ∘ Microwave, fridge, clock, furnace, airco ∙ Telemetry ∘ Utility meter, burglar alarm, babycam Distributed Systems Torben Weis 7 University Duisburg-Essen Peer-to-Peer Networks In peer-to-peer system there are no fixed clients and servers. Distributed Systems Torben Weis 8 University Duisburg-Essen Uses of Computer Networks ∙ Business Applications ∙ Home Applications ∙ Mobile Users Distributed Systems Torben Weis 9 University Duisburg-Essen Mobile Network Users ∙ Combinations of wireless networks and mobile computing Distributed Systems Torben Weis 10 University Duisburg-Essen Broadcast Networks ∙ Types of transmission technology ∘ Broadcast links ∘ Point-to-point links Distributed Systems Torben Weis 11 University Duisburg-Essen Network Hardware ∙ Local Area Networks ∙ Metropolitan Area Networks ∙ Wide Area Networks ∙ Wireless Networks ∙ Home Networks ∙ Internetworks Distributed Systems Torben Weis 12 University Duisburg-Essen Local Area Networks Two broadcast networks (a) Bus (b) Ring Distributed Systems Torben Weis 13 University Duisburg-Essen Metropolitan Area Networks A metropolitan area network based on cable TV. Distributed Systems Torben Weis 14 University Duisburg-Essen Wide Area Networks Relation between hosts on LANs and the subnet. Distributed Systems Torben Weis 15 University Duisburg-Essen Wide Area Networks (2) A stream of packets from sender to receiver. Distributed Systems Torben Weis 16 University Duisburg-Essen Networks Dimensions Classification of interconnected processors by scale. Distributed Systems Torben Weis 17 University Duisburg-Essen Wireless Networks ∙ Categories of wireless networks: ∘ Wireless LANs ∘ Wireless WANs ∘ System interconnection Distributed Systems Torben Weis 18 University Duisburg-Essen Wireless Networks (2) (a) Bluetooth configuration (b) Wireless LAN Distributed Systems Torben Weis 19 University Duisburg-Essen Wireless Networks (3) ∙ (a) Individual mobile computers ∙ (b) A flying LAN Distributed Systems Torben Weis 20 University Duisburg-Essen Network Software ∙ Network software is complex ∘ Therefore it is split into Layers ∙ Each layer communicates according to a protocol (IP, TCP, UDP) … ∙ Each layer provides a service to the upper layer ∘ This service can be accessed via an interface ∙ The layered protocols form a protocol hierarchy Distributed Systems Torben Weis 21 University Duisburg-Essen Protocol Hierarchies Layers, protocols, and interfaces Distributed Systems Torben Weis 22 University Duisburg-Essen Protocol Hierarchies (2) The relationship between a service and a protocol Distributed Systems Torben Weis 23 University Duisburg-Essen Protocol Hierarchies (3) The philosopher-translator-secretary architecture. Distributed Systems Torben Weis 24 University Duisburg-Essen Protocol Hierarchies (4) Example information flow supporting virtual communication in layer 5. Distributed Systems Torben Weis 25 University Duisburg-Essen Design Issues for the Layers ∙ Connection-oriented or Connection-Less ∙ Addressing ∙ Error Control ∙ Flow Control ∙ Multiplexing ∙ Routing Distributed Systems Torben Weis 26 University Duisburg-Essen Connection-Oriented and Connectionless Services ∙ Connection-oriented ∘ A connection is opened (handshake) ∘ A sequence of data is being sent ∘ The connection is closed (handshake) ∘ The network knows to which connection the data belongs ∘ In addition: Error correction, flow control, ordering, etc. ∙ Connectionless ∘ Each datagram travels independently of the others ∘ The network does not know about the relationship of the datagrams ∘ Typically no flow control or datagram ordering Distributed Systems Torben Weis 27 University Duisburg-Essen Service Primitives Five service primitives for implementing a simple connection-oriented service Distributed Systems Torben Weis 28 University Duisburg-Essen Service Primitives (2) Packets sent in a simple client-server interaction on a connection-oriented network Distributed Systems Torben Weis 29 University Duisburg-Essen Reference Models ∙ The OSI Reference Model ∙ The TCP/IP Reference Model ∙ A Comparison of OSI and TCP/IP ∙ A Critique of the OSI Model and Protocols ∙ A Critique of the TCP/IP Reference Model Distributed Systems Torben Weis 30 University Duisburg-Essen Reference Models The OSI reference model Distributed Systems Torben Weis 31 University Duisburg-Essen Reference Models (2) The TCP/IP reference model Distributed Systems Torben Weis 32 University Duisburg-Essen Reference Models (3) Protocols and networks in the TCP/IP model Distributed Systems Torben Weis 33 University Duisburg-Essen Comparing OSI and TCP/IP Models ∙ OSI provided ∘ … a model first ∘ … multiple implementations later ∙ Internet provided ∘ … the working implementation first ∘ … a model later ∙ OSI is very clear with respect to concepts ∘ Services ∘ Interfaces ∘ Protocols ∙ OSI allows (in theory) to replace layers Distributed Systems Torben Weis 34 University Duisburg-Essen A Critique of the OSI Model and Protocols ∙ Why OSI did not take over the world ∘ Bad timing ∘ Bad technology ∘ Bad implementations ∘ Bad politics Distributed Systems Torben Weis 35 University Duisburg-Essen Bad Timing The apocalypse of the two elephants Distributed Systems Torben Weis 36 University Duisburg-Essen A Critique of the TCP/IP Reference Model ∙ Problems: ∘ Service, interface, and protocol not distinguished ∘ Not a general model ∘ Host-to-network “layer” not really a layer ∘ No mention of physical and data link layers ∘ Minor protocols deeply entrenched, hard to replace Distributed Systems Torben Weis 37 University Duisburg-Essen Hybrid Model The hybrid reference model to be used in this lecture Distributed Systems Torben Weis 38 University Duisburg-Essen Example Networks ∙ The Internet ∘ i.e. a collection of different networks ∘ internetworking: connect different networks together ∙ Connection-Oriented Networks ∘ X.25, Frame Relay, and ATM ∙ Ethernet ∘ 10 Mbit/s, 100 Mbit/s, 1 Gbit/s, 10 Gbit/s ∙ Wireless LAN ∘ 802.11 Distributed Systems Torben Weis 39 University Duisburg-Essen The ARPANET (a) Structure of the telephone system (b) Distributed switching system Distributed Systems Torben Weis 40 University Duisburg-Essen The ARPANET (2) The original ARPANET design. Distributed Systems Torben Weis 41 University Duisburg-Essen  The ARPANET (3) Growth of the ARPANET (a) December 1969. (b) July 1970. (c) March 1971. (d) April 1972. (e) September 1972. Distributed Systems Torben Weis 42 University Duisburg-Essen German DFN G-WiN Distributed Systems Torben Weis 43 University Duisburg-Essen German DFN G-WiN (2) Distributed Systems Torben Weis 44 University Duisburg-Essen German DFN G-WiN (3) Distributed Systems Torben Weis 45 University Duisburg-Essen  German DFN G-WiN (4) $ tracert www.su.se (University of Stockholm) 1 2 ms 3 ms 2 ms 130.149.63.129 2 7 ms 5 ms 2 ms ssr8-EN.gate.TU-Berlin.DE 3 8 ms 2 ms 3 ms ssr8pos-EN.gate.TU-Berlin.DE 4 * 7 ms 2 ms ar-tuberlin1.g-win.dfn.de 5 7 ms 3 ms 2 ms cr-berlin1-po4-1.g-win.dfn.de 6 22 ms 11 ms 11 ms cr-frankfurt1-po13-0.g-win.dfn.de 7 19 ms 11 ms 12 ms dfn.de1.de.geant.net 8 17 ms 11 ms 44 ms de1-1.de2.de.geant.net 9 38 ms 36 ms 38 ms de.se1.se.geant.net 10 34 ms 33 ms 33 ms sw-gw.nordu.net 11 34 ms 34 ms 34 ms stockholm2-POS6-0.sunet.se 12 34 ms 33 ms 34 ms stockholm4-POS0.sunet.se 13 39 ms 34 ms 34 ms giga-su2-gw-srp1-1.su.se 14 40 ms 36 ms 34 ms shall-gw1-ge1-0-25.su.se 15 * 40 ms 34 ms ccc.it.su.se Distributed Systems Torben Weis 46 University Duisburg-Essen  German DFN G-WiN (4) $ tracert www.uio.no (University of Oslo) 1 7 ms 2 ms 2 ms 130.149.63.129 2 2 ms 5 ms 3 ms ssr8-EN.gate.TU-Berlin.DE 3 7 ms 2 ms 2 ms ssr8pos-EN.gate.TU-Berlin.DE 4 8 ms 2 ms 2 ms ar-tuberlin1.g-win.dfn.de 5 * 8 ms 3 ms cr-berlin1-po4-1.g-win.dfn.de 6 16 ms 11 ms 11 ms cr-frankfurt1-po13-0.g-win.dfn.de 7 17 ms 12 ms 12 ms dfn.de1.de.geant.net 8 18 ms 11 ms 12 ms de1-2.de2.de.geant.net 9 39 ms 33 ms 34 ms de.se1.se.geant.net 10 39 ms 33 ms 34 ms sw-gw.nordu.net 11 46 ms 48 ms 41 ms no-gw.nordu.net 12 46 ms 41 ms 41 ms oslo-gw1.uninett.no 13 47 ms 41 ms 41 ms uio-gw7.uio.no 14 46 ms 41 ms 41 ms www.uio.no Distributed Systems Torben Weis 47 University Duisburg-Essen Architecture of the Internet Overview of the Internet Distributed Systems Torben Weis 48 University Duisburg-Essen ATM Virtual Circuits A virtual circuit Distributed Systems Torben Weis 49 University Duisburg-Essen ATM Virtual Circuits (2) An ATM cell Distributed Systems Torben Weis 50 University Duisburg-Essen The ATM Reference Model The ATM reference model Distributed Systems Torben Weis 51 University Duisburg-Essen The ATM Reference Model (2) The ATM layers and sublayers and their functions Distributed Systems Torben Weis 52 University Duisburg-Essen Ethernet Architecture of the original Ethernet Distributed Systems Torben Weis 53 University Duisburg-Essen Wireless LAN (a) Wireless networking with a base station. (b) Ad hoc networking. Distributed Systems Torben Weis 54 University Duisburg-Essen Wireless LAN (2) The range of a single radio may not cover the entire system. Distributed Systems Torben Weis 55 University Duisburg-Essen Wireless LAN (3) A multicell 802.11 network Distributed Systems Torben Weis 56 University Duisburg-Essen Network Standardization ∙ The Who’s Who ∘ In the Telecommunications World ∘ In the International Standards World ∘ In the Internet Standards World Distributed Systems Torben Weis 57 University Duisburg-Essen International Telecommunication Union (ITU) ∙ Main sectors ∘ Radiocommunications ∘ Telecommunications Standardization ∘ Development ∙ Classes of Members ∘ National governments ∘ Sector members ∘ Associate members ∘ Regulatory agencies Distributed Systems Torben Weis 58 University Duisburg-Essen IEEE 802 Standards The 802 working groups. The important ones are marked with *. The ones marked with  are hibernating. The one marked with † gave up. Distributed Systems Torben Weis 59 University Duisburg-Essen Appendix ∙ Metric Units ∙ Additional Bibliography ∙ Acknowledgements Distributed Systems Torben Weis 60 University Duisburg-Essen Metric Units Distributed Systems Torben Weis 61 University Duisburg-Essen Bibliography /1/ P. Gerdsen Kommunikationstechnik 1 P. Kröger Springer-Verlag, 1994 /2/ D. Conrads Datenkommunikation Vieweg, 1996 /3/ F. Kaderali Digitale Kommunikationstechnik II Viehweg, 1995 /4/ O. Kyas ATM-Netzwerke Datacom, 1996 (43 YCT 2897) /5/ D. Lochmann Digitale Nachrichtentechnik Verlag Technik Berlin, 1995 (42 YCB 4158) /6/ G. Küveler Arbeitsbuch Informatik D. Schwoch Vieweg, 1996 /7/ J. L. Hennessy Computer Architecture, A Quantitative Approach D. A. Patterson Morgan Kaufmann, 1996 /8/ R.Kiefer Digitale Übertragung in SDH- und PDH-Netzen expert Verlag, 1996 (43 YCT 3097) Distributed Systems Torben Weis 62 University Duisburg-Essen Bibliography (2) /9/ G. Siegmund ATM - Die Technik des Breitband - ISDN R. v. Decker, 1994 /10/ R. Händel ATM Networks M. N. Huber Addison-Wesley, 1995 (43YCT2952) S. Schröder /11/ R. O. Onvural Asynchronous Transfer Mode Networks Artech House, 1995 /12/ M. de Prycker Asynchronous Transfer Mode Prentice Hall, 1995 /13/ M. Lübbers Datenverkehr in ATM-Netzen Generierung und Bewertung Diplomarbeit, GMU-Duisburg, FB E- technik, FG DV, 1997 /14/ A. Badach Integrierte Unternehmensnetze Hüthig, 1997 /15/ R. Kiefer Messung in Digitalen Netzen Hüthig, 1997 Distributed Systems Torben Weis 63 University Duisburg-Essen Bibliography (3) /16/ L. Lewis Managing Computer Networks Artech House, 1995 /17/ R. Ananthanpillai Managing Messaging Networks Artech House, 1995 /18/ M. Ritter Mechanismen zur Steuerung und Verw. von ATM-Netzen Ph. Tran-Gia Teil1: Grundlegende Prinzipien Informatik-Spektrum 20(1997)H.4, S.216-224 /19/ F. Kaderali Graphen Algorithmen Netze W. Poguntke Grundlagen und Anwendungen in der Nachrichtentechnik Vieweg Verlag, 1995 (43 YCB 4433) /20/ A. S. Tanenbaum Computer Networks Prentice Hall, 1996; in German 1998 /21/ B. Lee, M. Kang Broadband Telecommunications Technology J. Lee Artech House, Boston ,London, 1993 /22/ W. Stallings ISDN and Broadband ISDN with Frame Relay and ATM PrenticeHall, Enlewood Cliffs, New Jersey, 1995 /23/ W. P. Kowalk Rechnernetze M. Burke Teubner, 1994 Distributed Systems Torben Weis 64 University Duisburg-Essen Bibliography (4) /24/ W.-D. Haaß Handbuch der Kommunikationsnetze Springer, 1997 /25/ J. Manchester, et al. IP over SONET ('Scrambling') IEEE Comm. Magaz. Vol.36, 1998, may, pp.136-151 /26/ W. Stallings High-Speed Networks Prentice Hall, 1998 /27/ G.N.Higginbottom Performance Evaluation of Communication Networks Artech House, 1998 /28/ D. Bertsekas Data Networks R. Gallager Prentice Hall, 1992 /29/ G. Held Ethernet Networks Wiley, 1998 /30/ G. Held Data Communications Networking Devices Wiley, 1998 /31/ D. Kosiur Building and Managing Virtual Private Networks Wiley, 1998 Distributed Systems Torben Weis 65 University Duisburg-Essen Bibliography (5) /32/ G. Held Enhancing LAN Performance Wiley, 1999 /33/ S.G. Wilson Digital Modulation and Coding Prentice Hall, 1996 /34/ J. G. Proakis Digital Communications McGraw-Hill, 1995 /35/ ITU-T Standards http://ubntint.uni-duisburg.de/itu-t/Menu.PDF Distributed Systems Torben Weis 66 University Duisburg-Essen Acknowledgements ∙ The slides of this lecture are partly based on the slides of Andrew Tanenbaum ∙ The original slides can be obtained at http://authors.phptr.com/tanenbaumcn4/ Distributed Systems Torben Weis 67 University Duisburg-Essen Rechnernetze und Kommunikationssysteme Chapter 2 Physical Layer Dr.-Ing. Torben Weis University Duisburg-Essen The Theoretical Basis for Data Communication ∙ Fourier Analysis ∙ Bandwidth-Limited Signals ∙ Maximum Data Rate of a Channel Distributed Systems Torben Weis 2 University Duisburg-Essen Putting Bits on the Wire Waves can be used to approximate the above curve Distributed Systems Torben Weis 3 University Duisburg-Essen Fourier Analysis (1) ∙ The signal on the wire is a periodic function (sinus, cosinus) ∙ Every periodic function can be approximated by a sum of waves of different frequencies ∙ Why is that important to us? ∘ Cables cannot transport waves of very high frequency ∘ → Cables act like a low-pass filter Low frequencies pass the cable High frequencies are filtered, i.e. they drop out ∙ What happens if we send 10101010… too fast ? ∘ The signal is damaged ∘ The receiver cannot decode it  Distributed Systems Torben Weis 4 University Duisburg-Essen Fourier Analysis (2) A binary signal and its root-mean-square Fourier amplitudes. (b) – (c) Successive approximations to the original signal. Distributed Systems Torben Weis 5 University Duisburg-Essen Fourier Analysis (3) (d) – (e) Successive approximations to the original signal. Distributed Systems Torben Weis 6 University Duisburg-Essen Fourier Analysis (4) ∙ The “famous” formula 𝑁 𝑁 1 𝑔 𝑡 ≈ 𝑐 + ෍ 𝑎𝑛 sin 2𝜋𝑛𝑓𝑡 + ෍ 𝑏𝑛 cos 2𝜋𝑛𝑓𝑡 2 𝑛=1 𝑛=1 ∙ Let 𝑇 be the period of 𝑔 1 ∙ 𝑓 is the frequency of 𝑔 → 𝑓 = 𝑇 ∙ Our task ∘ We know 𝑔: e.g., the bit sequence on slide 5 (a) ∘ We want to see which wave functions are required to approximate 𝑔 ∘ → We must determine 𝑎𝑛, 𝑏𝑛 and c ∘ 𝑎𝑛, 𝑏𝑛 are the amplitudes of the 𝑛-th harmonics Distributed Systems Torben Weis 7 University Duisburg-Essen Fourier Analysis (5) ∙ We need some helpful formulas first 2𝜋 න sin 𝑎𝑥 cos 𝑏𝑥 𝑑𝑥 = 0, 𝑎, 𝑏 ∈ ℕ 0 2𝜋 න sin 𝑎𝑥 sin 𝑏𝑥 𝑑𝑥 = 0, 𝑎 ≠ 𝑏. 0 2𝜋 2𝜋 න sin 𝑎𝑥 𝑠𝑖𝑛 𝑎𝑥 𝑑𝑥 = , 𝑎 = 𝑏. 2 0 Distributed Systems Torben Weis 8 University Duisburg-Essen Fourier Analysis (5.1) 1 ∙ Remember: 𝑓 = 𝑇 𝑇 න sin 2𝜋𝑓𝑎𝑥 cos 2𝜋𝑓𝑏𝑥 𝑑𝑥 = 0, 𝑎, 𝑏 ∈ ℕ 0 𝑇 න sin 2𝜋𝑓𝑎𝑥 sin 2𝜋𝑓𝑏𝑥 𝑑𝑥 = 0, 𝑎 ≠ 𝑏. 0 𝑇 𝑇 න sin 2𝜋𝑓𝑎𝑥 𝑠𝑖𝑛 2𝜋𝑓𝑎𝑥 𝑑𝑥 = , 𝑎 = 𝑏. 2 0 Distributed Systems Torben Weis 9 University Duisburg-Essen Fourier Analysis (6) 𝑁 𝑁 1 𝑔 𝑡 ≈ 𝑐 + ෍ 𝑎𝑛 sin 2𝜋𝑛𝑓𝑡 + ෍ 𝑏𝑛 cos 2𝜋𝑛𝑓𝑡 2 𝑛=1 𝑛=1 ∙ Idea to get a specific 𝑎𝑘 ∘ Multiply with sin 2𝜋𝑘𝑓𝑡 ∘ Integrate from 0 to 𝑇 𝑇 1 ∙ න 𝑐 sin 2𝜋𝑘𝑓𝑡 𝑑𝑡 = 0 0 2 ∙ The cos & sin mixed terms disappear 𝑇 ∙ න sin 2𝜋𝑛𝑓𝑡 sin 2𝜋𝑘𝑓𝑡 𝑑𝑡 = 0, 𝑛≠𝑘 0 Distributed Systems Torben Weis 10 University Duisburg-Essen  Fourier Analysis (7) ∙ What remains? 𝑇 𝑇 𝑇 න 𝑔(𝑡) sin 2𝜋𝑘𝑓𝑡 𝑑𝑡 = න 𝑎𝑘 sin 2𝜋𝑘𝑓𝑡 sin 2𝜋𝑘𝑓𝑡 𝑑𝑡 = 𝑎𝑘 0 0 2 ∙ We can compute any 𝑎𝑛 using the known 𝑔 (e.g., slide 5 (a)) 2 𝑇 𝑎𝑛 = න 𝑔(𝑡) sin 2𝜋𝑛𝑓𝑡 𝑑𝑡 𝑇 0 ∙ We can do the same for 𝑏𝑛 2 𝑇 𝑏𝑛 = න 𝑔(𝑡) 𝑐𝑜𝑠 2𝜋𝑛𝑓𝑡 𝑑𝑡 𝑇 0 Distributed Systems Torben Weis 11 University Duisburg-Essen Fourier Analysis (8) 𝑁 𝑁 1 𝑔 𝑡 ≈ 𝑐 + ෍ 𝑎𝑛 sin 2𝜋𝑛𝑓𝑡 + ෍ 𝑏𝑛 cos 2𝜋𝑛𝑓𝑡 2 𝑛=1 𝑛=1 ∙ We can compute 𝑐 by just integrating 𝑇 1 න 𝑎𝑛 sin 2𝜋𝑛𝑓𝑡 𝑑𝑡 = 0, 𝑓 = ,𝑛 ∈ ℕ 0 𝑇 ∙ It follows that 𝑇 𝑇 1 1 2 𝑇 න 𝑔(𝑡) 𝑑𝑡 = න 𝑐 𝑑𝑡 = 𝑐 𝑇 → 𝑐 = න 𝑔 𝑡 𝑑𝑡 0 0 2 2 𝑇 0 Distributed Systems Torben Weis 12 University Duisburg-Essen Fourier Analysis (9) ∙ For 𝑔 𝑡 we compute 𝑎𝑛, 𝑏𝑛 and c for 1 ≤ 𝑛 ≤ 𝑁 ∙ Investigate how the signal looks like when we reduce 𝑁 (i.e. the number of harmonics) Distributed Systems Torben Weis 13 University Duisburg-Essen Bandwidth-Limited Signals (1) ∙ Maximum frequency is limited ∙ How fast can we transmit? ∙ Example: we want to transmit 19200 bit/sec ∙ 1st harmonic oscillates once per 8 bit ∙ 1st harmonic has frequency ∙ 2nd harmonic has frequency 4800 Hz, and so on… Distributed Systems Torben Weis 14 University Duisburg-Essen Bandwidth-Limited Signals (2) ∙ Typical telephone line has a 3000 Hz low-pass filter ∙ At 19200 bit/sec we could only transmit the 1st harmonic (2400Hz) → 19200 bit/sec will not work (at least not without further tweaking) Distributed Systems Torben Weis 15 University Duisburg-Essen Bandwidth-Limited Signals (3) Relation between data rate and harmonics. Bit rates and associated harmonics for a 3000 Hz telephone line Distributed Systems Torben Weis 16 University Duisburg-Essen Maximum Data Rate of a Channel (1) ∙ Theorem of Mr. Nyquist ∘ Channel with H low-pass filter ∘ Sampling at 2H is necessary and sufficient ∙ Maximum data rate = 2⋅H⋅log2(V) ∙ Example: telephone line (H=3000 Hz) ∘ We transfer binary data → V=2 ∘ Maximum data rate = 6000 bit/sec ∙ Idea: Increase V ☺ ∙ Attention: Noise not considered yet! Distributed Systems Torben Weis 17 University Duisburg-Essen Maximum Data Rate of a Channel (2) ∙ Theorem of Mr. Shannon ∘ S/N = signal to noise ratio ∘ Maximum data rate= ∙ S/N is usually expressed in decibels ∘ 10 log10 S/N [db] ∙ Example: 3000 Hz and 30db (i.e. S/N =1000) ∙ Shannon tells us: ∘ 3000 ⋅ log2(1 + 1000) ≈ 3000 ⋅ 9,967 ∘ Approx. no more than 30.000 bit/sec ∙ Increasing V has limits  Distributed Systems Torben Weis 18 University Duisburg-Essen Guided Transmission Data ∙ Magnetic Media ∙ Twisted Pair ∙ Coaxial Cable ∙ Fiber Optics Distributed Systems Torben Weis 19 University Duisburg-Essen Magnetic Media ∙ We construct a network using ∘ A car ∘ A 1m3 box including 1000 tapes of each 200 GByte → 1.6 Petabit (1600 Terabit) ∙ 24 hours (=86400 sec) to go from A to B ∙ 1600 Terabit/86400 sec = 18 Gbit/sec ∙ 4 € per tape → 4000 € ∙ 1000 € shipping ∙ In total: 5000 € for 200 TByte ∙ → GByte costs 2.5 cent !!! Distributed Systems Torben Weis 20 University Duisburg-Essen Twisted Pair (a) Category 3 Unshielded TP. (b) Category 5 Unshielded TP. Distributed Systems Torben Weis 21 University Duisburg-Essen Coaxial Cable A coaxial cable Distributed Systems Torben Weis 22 University Duisburg-Essen Fiber Optics (1) (a) Three examples of a light ray from inside a silica fiber impinging on the air/silica boundary at different angles. (b) Light trapped by total internal reflection. Distributed Systems Torben Weis 23 University Duisburg-Essen Fiber Optics (2) ∙ Rays with different angle cause total reflection ∙ Each such ray has a mode ∙ If a fiber can transport rays of different modes, it is called multi-mode fiber ∙ Fibers with a small diameter (few wavelengths) propagate light only in a straight line, i.e. they transport only one mode ∙ Such fibers are called single-mode fiber Distributed Systems Torben Weis 24 University Duisburg-Essen Fiber Optics (3) ∙ Communication advanced faster than CPU speed ∙ Original IBM PC 1981 ∘ 4.77 MHz ∙ State of the art PC ∘ 3.8 GHz ∙ Factor of 1000 in 24 years ∙ ARPANET ∘ 56 Kbit/sec ∙ Optical Communication, Gigabit Ethernet ∘ 1 Gbit/sec ∙ Factor 20.000 in 35 years ∙ Error Rate: From 10-5 errors/bit to almost zero Distributed Systems Torben Weis 25 University Duisburg-Essen Fiber Optics (4) ∙ Fiber Optics have a theoretical limit of 50 Tbit/sec ∙ Practical limitation ∘ Conversion between light and electronic devices ∘ Photodiode response time: picosecs to 1 nanosec → Maximum: 100 Gbit/s Ethernet (IEEE 802.3ba) ∙ Routing in Fiber Optic Networks is problematic ∘ Computers not fast enough to process each packet ∘ Hardware routers without any software ∘ Outlook: optical routers without light/electronic conversion Distributed Systems Torben Weis 26 University Duisburg-Essen Attenuation of Light ∙ Light looses intensity while traveling ∙ Attenuation depends on ∘ The wavelength ∘ Physical properties of the glass used Distributed Systems Torben Weis 27 University Duisburg-Essen Transmission of Light through Fiber Attenuation of light through fiber in the infrared region. Distributed Systems Torben Weis 28 University Duisburg-Essen Dispersion (1) ∙ Light pulses are sent through the wire ∙ Pulses spread out in length ∘ This can destroy the encoded information Distributed Systems Torben Weis 29 University Duisburg-Essen Dispersion (2) ∙ Solution: Solitons ∘ A soliton is a pulse of a special shape ∘ Nearly all dispersion effects cancel out →Pulses can travel a long distance Up to 1000km and more Distributed Systems Torben Weis 30 University Duisburg-Essen Fiber Cables (1) (a) Side view of a single fiber. (b) End view of a sheath with three fibers. Distributed Systems Torben Weis 31 University Duisburg-Essen Fiber Cables (2) ∙ Connecting fiber cables is difficult ∙ 1) Connectors and fiber sockets ∘ Easy to use, easy to reconfigure the system ∘ Fiber looses 10 – 20% of the light ∙ 2) Mechanical splices ∘ Fiber ends must be carefully cut ∘ Fibers must be well aligned ∘ Fiber looses 10% of the light ∙ 3) Melting ∘ Two ends can be melted ∘ Almost perfect, but still some attenuation Distributed Systems Torben Weis 32 University Duisburg-Essen Fiber Cables (3) A comparison of semiconductor diodes and LEDs as light sources. Distributed Systems Torben Weis 33 University Duisburg-Essen Fiber Optic Networks A fiber optic ring with active repeaters. Distributed Systems Torben Weis 34 University Duisburg-Essen Fiber Optic Networks (2) A passive star connection in a fiber optics network. Distributed Systems Torben Weis 35 University Duisburg-Essen Wireless Transmission ∙ The Electromagnetic Spectrum ∘ Radio Transmission ∘ Microwave Transmission ∘ Infrared and Millimeter Waves ∘ Light Wave Transmission Distributed Systems Torben Weis 36 University Duisburg-Essen The Electromagnetic Spectrum The electromagnetic spectrum and its uses for communication Distributed Systems Torben Weis 37 University Duisburg-Essen Radio Transmission (a) In the VLF, LF, and MF bands, radio waves follow the curvature of the earth. (b) In the HF band, they bounce off the ionosphere. Distributed Systems Torben Weis 38 University Duisburg-Essen Light Wave Transmission Convection currents can interfere with laser communication systems. Distributed Systems Torben Weis 39 University Duisburg-Essen Communication Satellites (2) Distributed Systems Torben Weis 40 University Duisburg-Essen Low-Earth Orbit Satellites Iridium ∙ (a) The Iridium satellites form six necklaces around the earth. ∙ (b) 1628 moving cells cover the earth. Distributed Systems Torben Weis 41 University Duisburg-Essen Satellite Switches and Ground Switches (a) Relaying in space. (b) Relaying on the ground. Distributed Systems Torben Weis 42 University Duisburg-Essen Rechnernetze und Kommunikationssysteme Chapter 3 Medium Access Control Sublayer Prof. Dr.-Ing. Torben Weis University Duisburg-Essen Channel Allocation Problem (1) Multiple stations access one channel How to avoid collisions? Two different approaches Static Channel Allocation Dynamic Channel Allocation What do we expect? Static à Simple Dynamic à Efficient Distributed Systems Torben Weis 2 University Duisburg-Essen Channel Allocation Problem (2) ∙ Example: ∘ Cocktail party – many people gather in a large room ∘ Broadcast medium = air ∙ Human protocols: ∘ “Give everyone a chance to speak” ∘ “Don’t speak until you are spoken to” ∘ “Don’t monopolize the conversation” ∘ “Raise your hand if you have a question” ∘ “Don’t interrupt when someone is speaking” ∘ “Don’t fall asleep when someone else is talking” Distributed Systems Torben Weis 3 University Duisburg-Essen Channel Allocation Problem (3) ∙ If more than 2 users send at the same time à collision ∙ All collided packets are lost à waste of bandwidth ∙ Ideally, the MAC protocol for a broadcast channel with R bit/sec should satisfy: ∘ If only 1 node is sending then the throughput is R ∘ When M nodes have data to send then the throughput is R/M ∘ Decentralized protocol, i.e. no master ∘ Simple & inexpensive to implement Distributed Systems Torben Weis 4 University Duisburg-Essen Protocol Layer Layer 5 Application Layer Layer 5 Layer 4 Transport Layer Layer 4 Layer 3 Network Layer Layer 3 Layer 3 Network Layer Layer 3 Layer 2 Data Link Layer Layer 2 Layer 2 Data Link Layer Layer 2 Layer 1 Physical Layer Layer 1 Layer 1 Physical Layer Layer 1 ∙ Data Link Layer puts frames on the wire ∙ What happens if multiple stations want to put frames on the medium (wire) at the same time? è Medium Access Control (MAC) is required Distributed Systems Torben Weis 5 University Duisburg-Essen Medium Access Control Sublayer Layer 5 Application Layer Layer 5 Layer 4 Transport Layer Layer 4 Layer 3 Network Layer Layer 3 Layer 3 Network Layer Layer 3 Layer 2 Data Link Layer Layer 2 Layer 2 Data Link Layer Layer 2 MAC MAC MAC MAC Layer 1 Physical Layer Layer 1 Layer 1 Physical Layer Layer 1 ∙ MAC is not part of the OSI Model ∙ MAC is a sublayer of the Data Link Layer Distributed Systems Torben Weis 6 University Duisburg-Essen Static Channel Allocation ∙ Frequency Division Multiplexing (FDM) ∙ Time Division Multiplexing (TDM) Distributed Systems Torben Weis 7 University Duisburg-Essen Frequency Division Multiplexing (1) ∙ Uses static allocation ∙ Channel has a bandwidth of H ∙ n stations are connected to the cable ∙ Idea ∘ Divide the bandwidth in H/n frequency bands ∘ Assign one band to one station ∙ Result ∘ No collisions possible J ∘ Bandwidth for single user decreased by factor n L Distributed Systems Torben Weis 8 University Duisburg-Essen Frequency Division Multiplexing (2) (a) The original bandwidths (b) The bandwidths raised in frequency (b) The multiplexed channel Distributed Systems Torben Weis 9 University Duisburg-Essen Time Division Multiplexing (1) ∙ Uses static allocation ∙ Channel transfers B bit/sec ∙ n stations are connected to the cable ∙ Idea ∘ Allocate n time slots of length t ∘ Round robin ∘ Each station transfers B*t bits per slot ∙ Result ∘ No collisions possible J ∘ Bandwidth for single user decreased by factor n L Distributed Systems Torben Weis 10 University Duisburg-Essen Time Division Multiplexing (2) Distributed Systems Torben Weis 11 University Duisburg-Essen Dynamic Channel Allocation (1) ∙ Station Model ∘ n independent stations ∘ Each station wants to send frames ∘ l is the constant arrival rate ∘ Probability of sending a frame in time Dt is l Dt Distributed Systems Torben Weis 12 University Duisburg-Essen Dynamic Channel Allocation (2) ∙ Single Channel Assumption ∘ All stations connected to the same channel ∘ All stations are equivalent ∘ Every station can send/receive ∘ Optional Priorities can be assigned to stations Distributed Systems Torben Weis 13 University Duisburg-Essen Dynamic Channel Allocation (3) ∙ Collision Assumption ∘ Two stations sending at overlapping time intervals à collision à the transmitted data is garbled ∘ After a collision, data must be sent again ∘ Stations can detect collisions ∘ No other errors, only collisions Distributed Systems Torben Weis 14 University Duisburg-Essen Dynamic Channel Allocation (4) ∙ Continuous Time ∘ Time is not slotted ∘ Station can attempt to send any time ∙ Slotted Time ∘ Time is slotted (divided in discrete intervals) ∘ Frame transmission starts at the beginning of a slot Distributed Systems Torben Weis 15 University Duisburg-Essen Dynamic Channel Allocation (5) ∙ Carrier Sense ∘ Channels are either busy or idle ∘ Station can sense whether the channel is busy ∘ Before sending, the station checks the channel ∙ No Carrier Sense ∘ Station cannot sense the channel ∘ Stations just transmit ∘ After sending the station knows whether it was successful or not ∘ Problem: A transmission has been destroyed Distributed Systems Torben Weis 16 University Duisburg-Essen Dynamic Channel Allocation (6) ∙ Station Model ∙ Single Channel Assumption ∙ Collision Assumption ∙ (a) Continuous Time (b) Slotted Time ∙ (a) Carrier Sense (b) No Carrier Sense Distributed Systems Torben Weis 17 University Duisburg-Essen Multiple Access Protocols ∙ ALOHA ∙ Carrier Sense Multiple Access Protocols ∙ Collision-Free Protocols ∙ Limited-Contention Protocols ∙ Also ∘ Wavelength Division Multiple Access Protocols ∘ Wireless LAN Protocols Distributed Systems Torben Weis 18 University Duisburg-Essen ALOHA (1) ∙ Norm Abramson at the Univ. of Hawaii ∙ mountainous islands à land network difficult to install ACK ACK ACK ACK Distributed Systems Torben Weis 19 University Duisburg-Essen ALOHA (2) ∙ M nodes can create new frames at any time ∙ The node immediately transmits its frame completely on a shared frequency ∘ (Different in slotted ALOHA) ∙ Base station acknowledges frames on a dedicated frequency ∙ If the frame collides à No ACK is received ∙ Retransmission with probability p à avoids efficiency to become 0 Distributed Systems Torben Weis 20 University Duisburg-Essen Pure ALOHA ∙ In pure ALOHA, frames are transmitted at completely arbitrary times. Distributed Systems Torben Weis 21 University Duisburg-Essen Pure ALOHA (2) ∙ Vulnerable period for the shaded frame = 2t. Distributed Systems Torben Weis 22 University Duisburg-Essen Slotted ALOHA ∙ Idea ∘ Create time slots of length t ∘ Transmission only at beginning of each time slot ∙ Result ∘ Vulnerability reduced from 2t to t ∘ We doubled the throughput ∙ Problem ∘ How does everybody agree on time slots? Distributed Systems Torben Weis 23 University Duisburg-Essen Pure and Slotted ALOHA ∙ Throughput versus offered traffic for ALOHA systems Distributed Systems Torben Weis 24 University Duisburg-Essen Evaluating Slotted Aloha Assumption: Channel can transmit R bit/sec Checklist: ü If only 1 node is sending than the throughput is R - When M nodes have data to send than the throughput is R/M ü Decentralized protocol ü Simple & inexpensive to implement Distributed Systems Torben Weis 25 University Duisburg-Essen Carrier Sense Multiple Access (1) ∙ CSMA = Carrier Sense Multiple Access ∙ Invented to minimize collisions and increase the performance ∙ A station now “follows” the activity of other stations ∘ à Carrier Sense ∙ Simple rules for polite human conversation ∘ Listen before speaking ∘ If someone else begins talking at the same time as you, stop talking Distributed Systems Torben Weis 26 University Duisburg-Essen Carrier Sense Multiple Access (2) ∙ If everyone is sensing the medium, how can collisions still occur? channel propagation delay Distributed Systems Torben Weis 27 University Duisburg-Essen 1-persistent CSMA ∙ The protocol ∘ Listen before transmitting ∘ If channel busy, wait until channel is idle ∘ If channel idle, transmit ∘ If collision occurs, wait a random amount of time and start all over again ∙ It is called 1-persistent because the station transmits with a probability of 1 whenever it finds the channel idle. Distributed Systems Torben Weis 28 University Duisburg-Essen Nonpersistent CSMA ∙ The protocol ∘ Listen before transmitting ∘ If busy, wait a random amount of time and sense the channel again ∘ If idle, transmit a packet immediately ∘ If collision occurs, wait a random amount of time and start all over again ∙ What is special? ∘ The station does not sense all the time à less greedy than 1-persistent CSMA Distributed Systems Torben Weis 29 University Duisburg-Essen p-persistent CSMA ∙ Applies to slotted channels ∙ The protocol ∘ Listen before transmitting ∘ If channel busy, wait until channel is idle ∘ If channel idle Transmit with probability p Wait for next slot with probability q=1-p ∘ If collision occurs, repeat the above procedure Distributed Systems Torben Weis 30 University Duisburg-Essen Persistent and Nonpersistent CSMA ∙ Comparison of the channel utilization versus load for various random access protocols Distributed Systems Torben Weis 31 University Duisburg-Essen Collision Detection (1) 1. Waiting for an acknowledge (ACK) ∙ ACK is sent after the frame has been transmitted à Frames with collisions are transmitted completely ∙ Waiting for ACK wastes time and bandwidth 2. Sending and receiving ∙ Check, whether you receive what you have sent à Collisions can be detected early ∙ This is called “Collision Detection” or just “CD” Distributed Systems Torben Weis 32 University Duisburg-Essen Collision Detection (2) ∙ When is a collision detected ? ∙ Station A sends at time t0 ∙ Signal needs t to the most distant station X ∙ At t0+t-e station X sends, too ∘ X sensed that the channel is idle ∙ The signal of X needs t to station A ∙ Result: A must wait 2t-e before it can detect a collision ∙ Problem: Maximum value of t depends on the maximum distance between stations Distributed Systems Torben Weis 33 University Duisburg-Essen CSMA with Collision Detection ∙ Senders can detect collisions while sending à “Collision Detection” Distributed Systems Torben Weis 34 University Duisburg-Essen Collision-Free Protocols (1) The basic bit-map protocol Distributed Systems Torben Weis 35 University Duisburg-Essen Collision-Free Protocols (2) ∙ The bitmap protocol is a reservation protocol ∙ Overhead calculation for the reservation ∘ Every station (N in total) wants to send a frame à Overhead = 1 contention slot per N frames = 1 bit ∘ Only one station wants to send a frame à Overhead = 1 contention slot for 1 frame = N bits Distributed Systems Torben Weis 36 University Duisburg-Essen Collision-Free Protocols (3) ∙ The binary countdown protocol ∙ A dash indicates silence Distributed Systems Torben Weis 37 University Duisburg-Essen Collision-Free Protocols (4) ∙ Binary countdown is a reservation protocol, too ∙ Overhead calculation for the reservation ∘ N stations in total ∘ At least one wants to send ∘ Contention slot has length log2 N ∙ Optimization ∘ Many frames carry the sender address à Efficiency can become 100% Distributed Systems Torben Weis 38 University Duisburg-Essen Collision-Free Protocols (5) ∙ Binary countdown uses priorities ∙ High addresses always win ∙ Low addresses can starve to death ∙ Possible fix ∘ Address numbers circulate ∘ After sending a frame, address numbers are shifted ∘ The sending station gets a low address Distributed Systems Torben Weis 39 University Duisburg-Essen Limited-Contention Protocols Acquisition probability for a symmetric contention channel Distributed Systems Torben Weis 40 University Duisburg-Essen Adaptive Tree Walk Protocol (1) The tree for eight stations Distributed Systems Torben Weis 41 University Duisburg-Essen Adaptive Tree Walk Protocol (2) ∙ Idea ∘ Limit the number of participants in the contention ∘ First, everybody may try to send ∘ Collision à halve the participants ∙ Best of both worlds ∘ Low delay when there are few collisions As good as slotted ALOHA ∘ Low delay when many station bid for the channel Almost as good as reservation protocols Distributed Systems Torben Weis 42 University Duisburg-Essen Wireless LAN Protocols (1) ∙ We have learned about protocols for cables ∘ CSMA ∘ CSMA/CD ∙ Wireless LANs require special protocols ∘ MACA = Multiple Access Collision Avoidance ∘ MACAW = MACA for Wireless ∙ … and concrete technologies ∘ IEEE 802.11 Distributed Systems Torben Weis 44 University Duisburg-Essen Wireless LAN Protocols (2) ∙ Why not use CSMA? ∘ The problem is sensing the carrier (i.e. air) ∘ Using cables, every signal eventually reaches every station ∘ Using radio, signals have a limited radius à no way to sense signals of far away stations ∙ Why care about signals that I cannot see? ∘ The sender may not see the other station ∘ However, the receiver can (perhaps) à the receiver experiences a collision à CSMA does not work as expected Distributed Systems Torben Weis 45 University Duisburg-Essen Hidden Station Problem ∙ A is sending to B ∙ Imagine C is sending to B, too ∘ A cannot hear C and vice versa à carrier sense says: ok. ∙ However, the collision would appear at B ∘ Neither A nor C will sense the collision Distributed Systems Torben Weis 46 University Duisburg-Essen Exposed Station Problem ∙ B is sending to A ∙ Imagine C wants to send to D ∘ C assumes that it cannot send because of B ∙ However, A will not experience a collision à C waits for no good reason Distributed Systems Torben Weis 47 University Duisburg-Essen The Central Problem of CSMA ∙ Problem statement ∘ We would like to know about activity at the receiver ∘ But, we sense whether there is activity at the sender ∙ Solution Idea ∘ Before sending a large data frame, force the receiver in sending a short frame (CTS) ∘ Stations close to the receiver detect the CTS ∘ These nearby stations will be silent until the data frame is sent & received ∙ Idea realized in MACA Distributed Systems Torben Weis 48 University Duisburg-Essen Multiple Access Collision Avoidance (1) ∙ A wants to send to B ∘ A first sends “Request to Send” (RTS) to B ∘ RTS contains the size of the real data ∘ B receives RTS ∘ B responds with “Clear to Send” (CTS) ∘ CTS contains the size of the real data, too ∘ A receives CTS ∘ A sends real data Distributed Systems Torben Weis 49 University Duisburg-Essen Multiple Access Collision Avoidance (2) ∙ RTS ∘ Stations hearing RTS could cause collisions at the sender à The sender could miss the CTS ∘ Solution: Stations hearing RTS will be silent until they hear CTS (or long enough for the receiver to respond with a CTS) ∙ CTS ∘ Stations hearing CTS can cause collisions at the receiver à The receiver could miss the real data ∘ Stations hearing the CTS will be silent until the data is transmitted ∘ The data length is known from RTS or CTS Distributed Systems Torben Weis 50 University Duisburg-Essen Multiple Access Collision Avoidance (3) ∙ The MACA protocol (a) A sending an RTS to B. (b) B responding with a CTS to A. Distributed Systems Torben Weis 51 University Duisburg-Essen Multiple Access Collision Avoidance (4) ∙ Collisions can still occur ∘ RTS frames can collide ∙ Solution ∘ Exponential back-off ∘ As in Ethernet ∙ MACAW ∘ Improved version of MACA ∘ Uses CSMA to avoid most RTS collisions Distributed Systems Torben Weis 52 University Duisburg-Essen Manchester Code (1) ∙ How to represent 0 and 1 on the wire? ∙ Idea 1 ∘ 1 = +5 Volt, 0 = 0 Volt ∘ Problem: How to differentiate 00000000 from an idle sender ? ∙ Idea 2 ∘ 1 = +5 Volt, 0 = -5 Volt ∘ Problem: We cannot be sure that all receivers sample the signal at the same rate (clock drift) ∙ We need a self-clocking encoding Distributed Systems Torben Weis 53 University Duisburg-Essen Manchester Code (2) ∙ Encode 1 bit as 2 bits ∘ 1 = 10 ∘ 0 = 01 ∘ Good news: the signal oscillates in the “middle” of every bit ∘ Bad news: We waste half of the bandwidth ∙ This is called Manchester Code ∘ It is used by Ethernet (we will come to that later) Distributed Systems Torben Weis 54 University Duisburg-Essen Manchester Code (3) Distributed Systems Torben Weis 55 University Duisburg-Essen Differential Manchester Code ∙ Encode 1 bit as 2 bits ∙ The encoding of bit n depends on the encoding of bit n-1 ∘ If n = 1 n-1 encoded as 10 ? à n = 01 n-1 encoded as 01 ? à n = 10 ∘ If n = 0 n-1 encoded as 10 ? à n = 10 n-1 encoded as 01 ? à n = 01 ∙ Advantage: Better noise immunity ∙ Disadvantage: Requires more complex equipment Distributed Systems Torben Weis 56 University Duisburg-Essen IEEE Standard 802 for LANs ∙ Ethernet: IEEE 802.3 ∙ Token Bus: IEEE 802.4 ∙ Token Ring: IEEE 802.5 ∙ Wireless: IEEE 802.11 Distributed Systems Torben Weis 57 University Duisburg-Essen IEEE 802.5 Token Ring Distributed Systems Torben Weis 58 University Duisburg-Essen Token Ring – Physical Length (1) ∙ A 3 byte token circulates on the ring ∙ Sender must not receive its own token data before it sends the last token bit à How many bits fit on the ring? Distributed Systems Torben Weis 59 University Duisburg-Essen Token Ring – Physical Length (2) ∙ Each station buffers 1 bit ∘ Problem: station can be taken off the net ∙ The cable carries some bits ∘ Data rate of R Mbit/sec à A bit is emitted every 1/R µsec ∘ Signal propagation speed 200 m/µsec à Each bit occupies 200/R m ∘ Example: R=1 Mbit/sec, length = 1000m à Each bit occupies 200m à 5 bits on the ring cable ∙ Additional buffers are required Distributed Systems Torben Weis 60 University Duisburg-Essen Token Passing (1) TK PKT T T PK PK TK The Token Station A Station A Staton A waits Station A rotates around captures the transmits the for the Packet releases the the ring Token and packet Token converts it to a Packet Release After Reception (RAR) Distributed Systems Torben Weis 61 University Duisburg-Essen Token Passing (2) TK T TK PK T PK Station A Station A transmits The Token captures the rotates around the Packet and Token and immediately releases the ring converts it to a the Token Packet Release After Transmission (RAT) Distributed Systems Torben Weis 62 University Duisburg-Essen Token Passing (3) ∙ The ring can contain: ∘ A token ∘ A data frame ∘ (or both in “release after transmission”) ∙ The token must fit on the ring ∙ The size of a data frame is not limited ∘ à A data frame is not entirely on the ring ∘ The sender can receive its own frame while still sending ∘ Can be used for error detection Distributed Systems Torben Weis 63 University Duisburg-Essen Token Passing (4) ∙ Is starvation possible? ∘ i.e. a station wants to send but never gets the token ? ∘ Answer: No ∙ Stations s1, s2, … sn ∙ Station si fetches the token and transmits data ∙ Then, si issues a new token à si+1 can get the token ∙ Full load à round robin ∙ Token ring is “fair” ∘ … as long as only one priority is used Distributed Systems Torben Weis 64 University Duisburg-Essen Token Ring Wiring Wire center bypass relays Distributed Systems Torben Weis 65 University Duisburg-Essen Token Ring – Multistation Access Unit (MSAU) Distributed Systems Torben Weis 66 University Duisburg-Essen Token Ring - Active Monitor ∙ Some station must … ∘ inject the token ∘ detect circulating frames ∘ send a continuous signal (e.g. Differential Manchester encoded 0) to synchronize all stations ∙ This station is the active monitor (AM) ∙ All other stations are standby monitors (SM) ∙ The active monitor is elected ∘ The station with the largest MAC wins Distributed Systems Torben Weis 67 University Duisburg-Essen Joining a Token Ring 1. (Lobe Check) - Performs a lobe media check to see whether frames are received without error. 2. (Physical Insertion) - A station then sends a 5 volt signal to the MSAU to open the relay. 3. (Address Verification) - A station then sends a message to is own MAC If the “Copied” flag is set à The MAC is already used 4. (Participation in Ring Poll) - The station must participate in the periodic (every 7 seconds) ring poll process. 5. (Request Initialization) - Finally a station sends out a special request to a parameter server to obtain configuration information. Distributed Systems Torben Weis 68 University Duisburg-Essen Token Structure (1) SD = Starting Delimiter SD AC ED AC = Access Control ED = Ending Delimiter 1 1 1 SD J - Phase Violation J JK0JK000 K - Phase Violation K 0 - Binary Zero PPP - Priority Bits AC T - Token Bit PPPTMrrr M - Monitor Bit rrr - Reservation Bit J - Phase Violation J K - Phase Violation K ED 1 - Binary One JK1JK1IE I - Intermediate Bit E - Error Bit Distributed Systems Torben Weis 69 University Duisburg-Essen Token Structure (2) SD = Starting Delimiter SD AC ED AC = Access Control ED = Ending Delimiter 1 1 1 ∙ The manchester code SD J - Phase Violation J violation enables a JK0JK000 K - Phase Violation K 0 - Binary Zero receiver to detect the start of a token ∙ Violation is achieved by not switching in the “middle” of a bit ∙ J ≠ K assures that the signal is still oscillating Distributed Systems Torben Weis 70 University Duisburg-Essen  Data Frame Structure SD AC FC DA SA DATA ED FS 1 1 1 6 6 n 1 1 SD = Starting Delimiter AC = Access Control FC = Frame Control DA = Destination Address FC SA = Source Address FF - Frame Type ED = Ending Delimiter FFZZZZZZ ZZZZZZ - Control Bits FS = Frame Status FS A = Address AC00AC00 Recognized C = Frame Copied Distributed Systems Torben Weis 71 University Duisburg-Essen Token Ring Priority Distributed Systems Torben Weis 72 University Duisburg-Essen IEEE Standard 802 for LANs ∙ Ethernet: IEEE 802.3 ∙ Token Bus: IEEE 802.4 ∙ Token Ring: IEEE 802.5 ∙ Wireless: IEEE 802.11 Distributed Systems Torben Weis 73 University Duisburg-Essen IEEE 802.4 Token Bus ∙ Physical: Bus (solid line) ∙ Logical: Ring (dashed line) Distributed Systems Torben Weis 74 University Duisburg-Essen Why Token Bus ? ∙ Combines: ∘ Cabling of Ethernet (single wire) ∘ Determinism (QoS) of Token Ring ∙ Different application domains ∘ Token Ring / Ethernet: Office ∘ Token Bus: Industrial automation Pushed by General Motors Real-time important Distributed Systems Torben Weis 75 University Duisburg-Essen Token Bus – Frame Format ∙ Comparable to IEEE 802.5 format, but unfortunately different Distributed Systems Torben Weis 76 University Duisburg-Essen Token Bus - Messages Distributed Systems Torben Weis 77 University Duisburg-Essen Token Bus – MAC Protocol (1) ∙ Initializing a ring 90 ∙ Station 90 wants to join ∘ Station 90 detects that there is no traffic ∘ Station 90 sends claim_token(90) ∘ The station with the highest MAC wins Distributed Systems Torben Weis 78 University Duisburg-Essen Token Bus – MAC Protocol (2) ∙ Joining a ring 90 80 70 60 ∙ Station 80 wants to join ∘ 90 periodically sends solicit_successor(90,70) ∘ Station between 90 and 70 may respond ∘ 80 sends set_successor(90,80) Distributed Systems Torben Weis 79 University Duisburg-Essen Token Bus – MAC Protocol (3) ∙ Joining a ring, part 2 90 80 70 60 ∙ Stations 80 and 70 want to join ∘ 90 periodically sends solicit_successor(90,60) ∘ Station between 90 and 60 may respond ∘ 80 and 70 send set_successor(90,xx) à collision ∘ 90 sends resolve_contention ∘ The winner sends set_successor(90,xx) Distributed Systems Torben Weis 80 University Duisburg-Essen Token Bus – MAC Protocol (4) ∙ Contention Resolution Station A two random bits  address bits Station B  ∙ Use the address bits, two bits at a time, starting from the most significant bit (MSB) ∙ To avoid that larger number nodes always win: ∘ Add two random bits before the MSB ∘ Regenerate random bits periodically Distributed Systems Torben Weis 81 University Duisburg-Essen Token Bus – MAC Protocol (5) ∙ Leaving a ring 90 80 70 60 ∙ Stations 80 wants to leave ∘ 80 waits for the token ∘ 80 sends set_successor(90,70) à 90 has new successor à 70 has new predecessor Distributed Systems Torben Weis 82 University Duisburg-Essen Token Bus – MAC Protocol (6) ∙ Station failure 90 80 70 60 ∙ Station 80 fails ∘ 90 sends token. If 80 does not reply, 90 sends again ∘ Still no response à 90 sends who_follows(90,80) ∘ 70 sends set_successor(90,70) Distributed Systems Torben Weis 83 University Duisburg-Essen Token Bus – MAC Protocol (7) ∙ Station failure, part 2 90 80 70 60 ∙ Stations 80 and 70 fail ∘ 90 sends token. If 80 does not reply, 90 sends again ∘ No response à 90 sends who_follows(90,80) ∘ No response à 90 sends solicit_successor_2(90) ∘ Any alive station sends set_successor(90,xx) Distributed Systems Torben Weis 84 University Duisburg-Essen IEEE Standard 802 for LANs ∙ Ethernet: IEEE 802.3 ∙ Token Bus: IEEE 802.4 ∙ Token Ring: IEEE 802.5 ∙ Wireless: IEEE 802.11 Distributed Systems Torben Weis 85 University Duisburg-Essen Ethernet ∙ Cabling ∙ Frame Format ∙ Binary Exponential Back-off Algorithm ∙ Ethernet Performance ∙ Switched Ethernet ∙ Fast Ethernet ∙ Gigabit Ethernet Distributed Systems Torben Weis 86 University Duisburg-Essen Ethernet Cabling (1) The most common kinds of Ethernet cabling 10 = Speed in MBit/sec Base 2 {Base, Broad} 5,2 = Distance in 100m -T/F = Kind of cable used Distributed Systems Torben Weis 87 University Duisburg-Essen Ethernet Cabling (2) Three kinds of Ethernet cabling. (a) 10Base5, (b) 10Base2, (c) 10Base-T. Distributed Systems Torben Weis 88 University Duisburg-Essen Ethernet Cabling (3) ∙ Locating errors with coax cables ∘ Many stations connected to one cable ∘ If the cable breaks à multiple machines are offline ∘ “Where” did the cable break? ∘ Did a vampire tap destroy the cable? ∘ Hard to say … ∙ Locating errors with 10Base-T ∘ All computers offline à Hub is broken ∘ One computer offline à Its patch cable is broken ∘ Patch cables are not very long à Error can easily be found and removed Distributed Systems Torben Weis 89 University Duisburg-Essen Ethernet Cabling (4) Cable topologies (a) Linear, (b) Spine, (c) Tree, (d) Segmented. Distributed Systems Torben Weis 90 University Duisburg-Essen Repeaters and Hubs ∙ Repeaters can connect multiple cables ∘ Repeaters regenerate the signal à This introduces delay ∘ From the software point of view, the entire network acts like one large cable ∙ Hubs ∘ Special kind of repeater ∙ Limitations ∘ Maximum distance between two stations is 2.5 km ∘ No path between two stations may visit more than 4 repeaters ∘ Reason: 2t to detect a collision Distributed Systems Torben Weis 91 University Duisburg-Essen Ethernet Frame Format (1) Ethernet Frame formats (a) DIX Ethernet, (b) IEEE 802.3. Distributed Systems Torben Weis 92 University Duisburg-Essen Ethernet Frame Format (2) ∙ Preamble ∘ 8 bytes with bit pattern 10101010 ∘ In Manchester code à 10 MHz wave for 6.4 µsec ∘ Used for clock synchronization ∙ Addresses ∘ High-order bit 0 = Single cast 1 = Multi cast ∘ Address =111…1 à Broadcast address ∘ Bit 46 (see MAC Address slides) 0 = Local address 1 = Global address Distributed Systems Torben Weis 93 University Duisburg-Essen Ethernet Frame Format (3) ∙ Type / Length ∘ Type tells to which Network-Layer stack the frame belongs ∘ Thus, multiple stacks on top of Ethernet possible ∘ Type was used in DIX Ethernet ∘ IEEE 802.3 stores the data length instead à Incompatibilities ∘ Unification of DIX and IEEE 802.3 Values > 1500 represent a type Values < 1500 represent the data length Distributed Systems Torben Weis 94 University Duisburg-Essen Ethernet Frame Format (4) ∙ Data ∘ Up to 1500 bytes ∙ Pad ∘ Used if data section is too short ∘ Ensures minimum frame size of 64 byte (Remember the 2t problem) ∙ Checksum ∘ Used for error detection Distributed Systems Torben Weis 95 University Duisburg-Essen Ethernet ∙ Cabling ∘ A broadcast medium ∙ Uses CSMA/CD ∘ Carrier Sense ∘ Collision detection ∙ If the cable is currently in use ∘ 1-persistent ∙ In case of a collision ∘ Binary Exponential Back-off Algorithm Distributed Systems Torben Weis 96 University Duisburg-Essen Detecting Collisions (1) Collision detection can take as long as 2t. Distributed Systems Torben Weis 97 University Duisburg-Essen Detecting Collisions (2) ∙ What is the minimum frame size ? ∘ Bits sent during time period of length 2t ∙ Computing 2t ∘ Network has maximum length 2.5 km ∘ Maximum 4 repeaters ∘ Signal travels maximum 50 µsec ∙ How many bits sent during 50 µsec ? ∘ 10 MBit/sec à 1 bit requires 100 nsec ∘ 500 bit require 50 µsec ∘ Round it up: 512 bit = 64 byte ∙ Gigabit Ethernet ∘ Minimum frame size would become 6400 byte Distributed Systems Torben Weis 98 University Duisburg-Essen Binary Exponential Back-off Algorithm ∙ What to do after a collision? ∘ Wait, i.e. back-off ∘ If both wait for the same time à collision ∘ If both wait too long à inefficient ∙ Binary Exponential Back-off Algorithm ∘ 1st collision: Select waiting time 2 {0,1} ∘ 2nd collision: Select waiting time 2 {0,1,2,3} ∘ i-th collision: Select waiting time 2 {0,1,…2i-1} ∘ After 16 collisions Give up Send error to software layer Distributed Systems Torben Weis 99 University Duisburg-Essen Ethernet Performance (1) ∙ During a contention slot, each station sends with probability p ∘ This is a strong simplification!! ∙ Probability that some station wins ∙ Probability that contention interval has j slots Distributed Systems Torben Weis 100 University Duisburg-Essen Ethernet Performance (2) ∙ One slot lasts 2t à Contention interval lasts 2t/A ∙ Channel efficiency ∘ Transmitting a single frame takes P ∙ A rigorous analysis is much more difficult Distributed Systems Torben Weis 101 University Duisburg-Essen Ethernet Performance (3) Efficiency of Ethernet at 10 Mbps with 512-bit slot times. Distributed Systems Torben Weis 102 University Duisburg-Essen Ethernet Performance (4) ∙ Be careful with performance analysis ∘ They assume a certain “distribution” ∘ i.e. a model of when new frames are sent ∙ Almost up-to-date assumption ∘ Frames follow a Poisson distribution ∘ i.e. whether a new frame is sent does not depend on when the last frame has been sent ∙ Latest research results ∘ Real world traffic is not a Poisson distribution ∘ Real world traffic is self-similar Distributed Systems Torben Weis 103 University Duisburg-Essen Switched Ethernet (1) ∙ A talks to B A ∙ E talks to C & D ∙ They must share the available bandwidth E B ∙ Idea ∘ Why should A & B see the traffic of C & D & E ? ∙ Solution ∘ Do not use a hub C D ∘ Use a switch Distributed Systems Torben Weis 104 University Duisburg-Essen Switched Ethernet (2) A simple example of switched Ethernet Distributed Systems Torben Weis 105 University Duisburg-Essen Switched Ethernet (3) Distributed Systems Torben Weis 106 University Duisburg-Essen Fast Ethernet Fast Ethernet cabling ∙ Fast Ethernet uses switches and hubs ∘ No vampire taps etc. allowed ∙ 100Base-T4 exists for old buildings only ∙ 100Base-TX is very common ∙ Many Fast Ethernet switches support 10Base-T Distributed Systems Torben Weis 107 University Duisburg-Essen Gigabit Ethernet (a) A two-station Ethernet (b) A multistation Ethernet Distributed Systems Torben Weis 108 University Duisburg-Essen Gigabit Ethernet (2) Gigabit Ethernet cabling Distributed Systems Torben Weis 109 University Duisburg-Essen Gigabit Ethernet & Hubs ∙ Carrier extension ∘ Cables of only 25 meters are too short ∘ What is the problem? Collision detection of short frames with 64 byte ∘ Solution Extend the frame (i.e. padding) to 512 byte ∙ Frame burst ∘ If a station has multiple frames in the queue Concatenate them ∘ If the concatenated frames are still < 512 byte Apply padding again ∙ Optimal solution ∘ Don’t use hubs with Gigabit Ethernet. Use a switch. Distributed Systems Torben Weis 110 University Duisburg-Essen MAC Address (1) ∙ MAC Address = Media Access Control Address ∙ Every networking card must have a unique ID ∘ This allows us to address a recipient of a message ∙ IEEE standard for MAC addresses ∘ MAC-48 ∘ Part of IEEE 802 ∙ Putting the MAC address on the card ∘ Burned in Address They are globally unique Managed by the IEEE ∘ Locally administrated addresses (LAA) Distributed Systems Torben Weis 111 University Duisburg-Essen MAC Address (2) ∙ You can change the MAC of your card ∙ Linux ∘ ifconfig eth0 hw ether 00:01:02:03:04:05 ∘ ip link set eth0 address 00:01:02:03:04:05 ∙ Windows ∘ Change the registry key ∘ Use regedit.exe ∘ Look for: HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\ Control\Class\{4D36E972-E325-11CE-BFC1- 08002BE10318} Distributed Systems Torben Weis 112 University Duisburg-Essen IEEE Standard 802 for LANs ∙ Ethernet: IEEE 802.3 ∙ Token Bus: IEEE 802.4 ∙ Token Ring: IEEE 802.5 ∙ Wireless: IEEE 802.11 Distributed Systems Torben Weis 113 University Duisburg-Essen IEEE 802.11 Overview ∙ The 802.11 Protocol Stack ∙ The 802.11 Physical Layer ∙ The 802.11 MAC Sublayer Protocol ∙ The 802.11 Frame Structure ∙ Services Distributed Systems Torben Weis 114 University Duisburg-Essen The 802.11 Protocol Stack Part of the 802.11 protocol stack Distributed Systems Torben Weis 115 University Duisburg-Essen IEEE 802.11 Slow Version (1) ∙ Slow protocols operate on 1 or 2 MBit/sec ∙ 802.11 Infrared ∘ Uses Gray Code, 16 bit for 4 bit ∘ Not very popular ∙ 802.11 FHSS ∘ Frequency Hopping Spread Spectrum ∘ Uses the 2.4 GHz band ∘ 79 channels, each 1 MHz wide ∘ Random number generator tells which channel to choose ∘ Security: You must know the frequency sequence Distributed Systems Torben Weis 116 University Duisburg-Essen IEEE 802.11 Slow Version (2) ∙ 802.11 DSSS ∘ Direct Sequence Spread Spectrum ∘ The data is modulated on a noise signal (chips) ∘ The noise signal has a higher frequency than the data ∘ One data bit per chip ∘ Example: 8 bit chip Signal: 1 | 0 Chip-S: 11000111|11000111 XOR: 00111000|11000111 Distributed Systems Torben Weis 117 University Duisburg-Essen IEEE 802.11 a ∙ 802.11a uses OFDM ∘ Orthogonal Frequency Division Multiplexing ∘ Up to 54 Mbit/sec ∘ Uses the wider 5 GHz band ∘ Many carriers used in parallel at different frequencies ∘ Advantage: Fast and can deal better with reflections ∙ OFDM is used in other areas, too ∘ IEEE 802.11 a/g ∘ Digital Audio Broadcast (DAB) ∘ Digital Video Broadcast – Terrestrial (DVB-T) Distributed Systems Torben Weis 118 University Duisburg-Essen IEEE 802.11 b ∙ 802.11b uses HR-DSSS ∘ High Rate - Direct Sequence Spread Spectrum ∘ Operates on 2.4 GHz band ∘ Possible speed: 11, 5.5, 2, 1 MBit/sec ∘ Slower than 802.11 a ∘ Range is up to 7-times wider than 802.11 a ∘ Very popular currently Distributed Systems Torben Weis 119 University Duisburg-Essen IEEE 802.11 g ∙ 802.11g uses OFDM ∘ Offers up to 54 MBit/sec ∘ Uses the 2.4 GHz band (802.11a uses 5 GHz) ∘ 802.11g and 802.11b are compatible ∘ However, 802.11b devices slow down 802.11g devices ∘ Becomes more and more popular ∘ New notebooks offer 802.11b/g ∙ Additional specifications in IEEE 802.11 ∘ See http://en.wikipedia.org/wiki/802.11 Distributed Systems Torben Weis 120 University Duisburg-Essen The 802.11 MAC Sublayer Protocol (1) ∙ CSMA with Collision Avoidance (CSMA/CA) ∘ CD does not work on wireless networks ∘ CA is best effort à Collisions still possible ∙ CSMA/CA builds on MACAW ∘ It uses RTS / CTS à “Virtual channel sensing” ∘ It uses CS (Carrier Sensing) to avoid colliding RTS ∘ CSMA/CA tries to minimize collisions However, collisions are still possible ∘ Collision à Exponential back-off as in Ethernet Distributed Systems Torben Weis 121 University Duisburg-Essen The 802.11 MAC Sublayer Protocol (2) Virtual channel sensing using CSMA/CA Distributed Systems Torben Weis 123 University Duisburg-Essen The 802.11 MAC Sublayer Protocol (3) ∙ How likely is a frame subject to a bit error ? ∘ p = Probability of any bit error ∘ Frame of n-bit length ∘ Probability of correct frame is (1-p)n ∙ Examples ∘ Ethernet frame has 12.144 bits ∘ pf = probability of a correct Ethernet frame ∘ p = 10-4 à pf ¼ 30% ∘ p = 10-5 à pf ¼ 90% ∘ p = 10-6 à pf ¼ 99% ∙ Conclusion: Frame is too long Distributed Systems Torben Weis 124 University Duisburg-Essen The 802.11 MAC Sublayer Protocol (4) A fragment burst Distributed Systems Torben Weis 125 University Duisburg-Essen The 802.11 MAC Sublayer Protocol (5) ∙ Virtual Channel Reservation & Fragment Burst ∘ Reservation lasts only until the next ACK à No reservation for further fragments ∙ Idea ∘ Use the waiting time between frames in a clever way ∘ Assign priorities 1. Additional frames 2. Contention 3. Error reporting ∘ Low priorities must wait longer Distributed Systems Torben Weis 126 University Duisburg-Essen The 802.11 MAC Sublayer Protocol (6) ∙ DCF = Distributed Coordination Function ∘ Uses CSMA/CA as discussed ∘ DCF is mandatory for every IEEE 802.11 hardware ∙ PCF = Point Coordination Function ∘ A central point coordinates channel access ∘ Central point (i.e. base station) polls other stations ∘ Stations send only if asked (i.e. polled by the base station) ∘ Thus, no collisions at all ∘ PCF is optional ∙ DCF and PCF can coexist in one cell ∘ Due to the Inter-Frame Spacing Distributed Systems Torben Weis 127 University Duisburg-Essen The 802.11 MAC Sublayer Protocol (7) Inter-Frame Spacing in 802.11 Distributed Systems Torben Weis 128 University Duisburg-Essen The 802.11 Frame Structure The 802.11 data frame Distributed Systems Torben Weis 129 University Duisburg-Essen Data Link Layer Switching Distributed Systems Torben Weis 132 University Duisburg-Essen Data Link Layer Switching ∙ Bridges from 802.x to 802.y ∙ Local Internetworking ∙ Spanning Tree Bridges ∙ Remote Bridges ∙ Repeaters, Hubs, Bridges, Switches, Routers, Gateways ∙ Virtual LANs Distributed Systems Torben Weis 133 University Duisburg-Essen Connecting LANs ∙ Attention ∘ We talk about the data link layer here ∘ Not about the network layer (i.e. routing etc.) ∙ What is the difference ? ∘ Connecting LANs on the data link layer Inside a building Inside a company ∘ Connecting LANs on the network layer This is the idea of the inter-net Each LAN is a network The Inter-net inter-connects different networks Across buildings, oceans, continents Across all companies, homes, universities, … Distributed Systems Torben Weis 134 University Duisburg-Essen Reasons for Connecting LANs ∙ Size ∘ Too many nodes for one LAN All nodes must share the bandwidth Too many nodes for one switch ∘ Too large distances (remember the 2.5 km rule) ∙ Reliability ∘ If one LAN is broken, others still work ∙ Security ∘ Ethernet uses a broadcast cable Everybody can eavesdrop on your communication ∙ History ∘ Every department started its own LAN Distributed Systems Torben Weis 135 University Duisburg-Essen Data Link Layer Switching Multiple LANs connected by a backbone to handle a total load higher than the capacity of a single LAN Distributed Systems Torben Weis 136 University Duisburg-Essen Bridges from 802.x to 802.y (1) Operation of a LAN bridge from 802.11 to 802.3 Distributed Systems Torben Weis 137 University Duisburg-Essen Bridges from 802.x to 802.y (2) ∙ Bridging from 802.x to 802.y is difficult ∙ Different network speed ∘ A sends on a 1000BaseT-Ethernet to B ∘ B is located on a 10Base-T Ethernet ∘ The bridge tries to buffer data ∘ If the buffer is full à we loose frames ∙ Different pay-load size ∘ A sends via 802.4 à 8191 byte payload ∘ B receives via a 802.3 à 1500 byte payload ∘ Splitting frames is not an option ∙ Different frame format Distributed Systems Torben Weis 138 University Duisburg-Essen Bridges from 802.x to 802.y (2) Three IEEE 802 frame formats Distributed Systems Torben Weis 139 University Duisburg-Essen Bridges from 802.x to 802.y (3) Distributed Systems Torben Weis 140 University Duisburg-Essen Local Internetworking A configuration with four LANs and two bridges. Distributed Systems Torben Weis 141 University Duisburg-Essen Bridging Algorithm (1) ∙ A frame arrives at a bridge ∙ The frame has a sender X and receiver Y ∙ The frame came from some LAN L1 ∙ If Y is in LAN L1 ∙ Discard the frame ∙ The frame is already on the correct LAN ∙ à Y already received it ∙ If Y is in a different LAN L2 ¹ L1 ∙ Forward the frame on another LAN. Which one? ∙ If the bridge is connected to L2 ∙ Forward the frame to L2 ∙ Else ∙ Find a LAN Lk that is connected with L2 ∙ Forward the frame to Lk Distributed Systems Torben Weis 142 University Duisburg-Essen Bridging Algorithm (2) ∙ Given a node Y how to find the LAN of Y? ∘ A big hash table is required ∘ Every bridge has such a table ∘ n nodes on all LANs à n entries in the table ∙ Two problems ∘ Tables become very large No solution for the internet with its million of nodes ∘ Table configuration Who updates these tables? What happens if a mobile computer moves from one WLAN to another WLAN? We would have to adapt the table Distributed Systems Torben Weis 143 University Duisburg-Essen Bridging Algorithm (3) ∙ Adaptation is required ∘ The topology of the network can change ∘ à The table must adapt ∙ Second-chance algorithm ∘ Attach a flag to every table entry: (Node,Lan,Flag) ∘ Initially the flag is 0 ∘ If a frame from C is received via LAN L (C,L,1) à (C,L,0) i.e. clear the flag ∘ Periodically do the following (C,L,1) à delete this entry from the table (C,L,0) à (C,L,1) ∙ Extra memory for the algorithm ∘ Only 1 bit per table entry Distributed Systems Torben Weis 144 University Duisburg-Essen Bridging Algorithm – Backward Learning ∙ Initial behavior ∘ A frame with destination D arrives at the bridge ∘ It originates in LAN Lx ∘ Search in the table for (D, Ld) ∘ If such an entry exists Forward to Ld ∘ Else Forward it to all other LANs connected to this bridge Do not forward it to Lx ∙ Backward Learning ∘ A frame sent by C arrives at the bridge via LAN Lk ∘ Write in the table (C, Lk) Distributed Systems Torben Weis 145 University Duisburg-Essen Spanning Tree Bridges (1) ∙ Arbitrarily connected LANs ∘ They form an arbitrarily shaped graph ∘ Can form cycles ∘ Can feature multiple paths between two nodes ∙ This can lead to frames that never die ∘ Instead, they are copied, and copied, and copied … ∙ Basic idea: a spanning tree ∘ For every graph you can construct a spanning tree ∘ Trees Cannot form cycles Feature exactly one path between two nodes Distributed Systems Torben Weis 146 University Duisburg-Essen Spanning Tree Bridges (2) Two parallel transparent bridges Distributed Systems Torben Weis 147 University Duisburg-Essen Spanning Tree Algorithm (1) ∙ First the bridges have to elect the root bridge ∘ Each bridge broadcast its serial number ∘ The serial number is installed by the manufacturer and is guaranteed to be unique worldwide ∘ The bridge with the lowest serial number becomes the root ∙ Next, a tree of shortest paths from the root to every bridge and LAN is constructed ∙ Updates ∘ The algorithm updates the tree from time to time ∘ à adaptation to changes in the network topology Distributed Systems Torben Weis 148 University Duisburg-Essen Spanning Tree Algorithm (2) (a) Interconnected LANs. (b) A spanning tree covering the LANs. The dotted lines are not part of the spanning tree. Distributed Systems Torben Weis 149 University Duisburg-Essen Remote Bridges Remote bridges can be used to interconnect distant LANs Distributed Systems Torben Weis 150 University Duisburg-Essen High-Speed Networks Distributed Systems Torben Weis 151 University Duisburg-Essen Repeaters, Hubs, Bridges, Switches, Routers and Gateways (1) (a) Which device is in which layer (b) Frames, packets, and headers Distributed Systems Torben Weis 152 University Duisburg-Essen Repeaters, Hubs, Bridges, Switches, Routers and Gateways (2) (a) A hub. (b) A bridge. (c) a switch. Distributed Systems Torben Weis 153 University Duisburg-Essen Virtual LANs A building with centralized wiring using hubs and a switch Distributed Systems Torben Weis 154 University Duisburg-Essen Virtual LANs (2) (a) Four physical LANs organized into two VLANs, gray and white, by two bridges. (b) The same 15 machines organized into two VLANs by switches Distributed Systems Torben Weis 155 University Duisburg-Essen Bluetooth ∙ Bluetooth Architecture ∙ Bluetooth Applications ∙ The Bluetooth Protocol Stack ∙ The Bluetooth Radio Layer ∙ The Bluetooth Baseband Layer ∙ The Bluetooth L2CAP Layer ∙ The Bluetooth Frame Structure Distributed Systems Torben Weis 156 University Duisburg-Essen Bluetooth Piconet ∙ A piconet consists of ∘ One master node ∘ Up to seven slave nodes ∘ Up to 255 parked nodes Consume less power Wait for the master to wake them up ∘ All nodes within a range of 10 meters ∙ Scatternet ∘ A combination of piconets ∘ Piconets can overlap ∘ Nodes, which are in two piconets, can be used as bridges Distributed Systems Torben Weis 157 University Duisburg-Essen Bluetooth Architecture Two piconets can be connected to form a scatternet Distributed Systems Torben Weis 158 University Duisburg-Essen Bluetooth Communication ∙ Slaves only talk to the master ∘ Direct slave-to-slave communication not possible ∘ Slaves must communicate via the master ∙ Reasons ∘ Slave chips should be inexpensive ( 0 ∘ The cost of sending data from v1 to v2 ∘ Different ways of defining “cost” Bandwidth of the link Queue length Delay Cost in EUR or $ Distributed Systems Torben Weis 10 University Duisburg-Essen Dijkstra’s Algorithm (2) 01 Foreach v ∈ V 02 Distance(v) := , Predecessor(v) := none 03 Distance(s) := 0, Predecessor(s) := s, U := V 04 05 While U  ∅ 06 select u ∈ U with Distance(u) minimal 07 U := U ∖ {u} 08 If u = z then STOP # optional 09 Foreach (u,v) ∈ E with v ∈ U 10 If Distance(u) + Cost(u,v) < Distance(v) then 11 Distance(v) := Distance(u) + Cost(u,v) 12 Predecessor(v) := u Distributed Systems Torben Weis 11 University Duisburg-Essen Dijkstra’s Algorithm (3) Distributed Systems Torben Weis 12 University Duisburg-Essen Flooding (1) ∙ Shortest Path Routing requires global knowledge ∘ The path can be inaccurate ∙ Flooding is much simpler ∘ No global knowledge ∘ Very robust ∙ Idea: Propagate each message to all neighbors ∘ Every message reaches every node ∘ A message can reach one node several times ∙ Problem: How to avoid infinite circulation? ∘ Use maximum hop count ∘ Use sequence numbers Distributed Systems Torben Weis 14 University Duisburg-Essen Flooding (2) ∙ Maximum Hop Count ∘ Let l be the maximum distance between two routers ∘ Each message has a hop count ∘ Initial m.hop_count = 0 ∘ For each propagation of message m: m.hop_count++ ∘ If m.hop_count = l then discard(m) Distributed Systems Torben Weis 15 University Duisburg-Essen Flooding (3) ∙ Sequence Numbers ∘ Each message m has: A sequence number: m.seq The name of the source router: m.source ∘ Each router maintains a table Rows contain (source router, sequence number) ∘ Each router maintains a counter k ∘ When a message is created: m.seq = k; m.source = router name k++ ∘ When a message m is received If table contains (m.seq, m.source) → discard(m) Else add (m.seq, m.source) to table and propagate Distributed Systems Torben Weis 16 University Duisburg-Essen Flooding (4) ∙ Sequence Numbers (continued) ∘ The table can become too long ∘ Idea 1: throw away old entries Can cause retransmissions ∘ Idea 2: throw away old entries and keep minimum sequence number per source router: minsource router If m.seq < minsource router then discard(m) Can cause “very slow” messages to be discarded Distributed Systems Torben Weis 17 University Duisburg-Essen Dynamic Routing Algorithms (1) ∙ So far we have seen two extremes: ∙ Shortest Path Routing (Dijkstra) ∘ Good: Optimal, because of shortest path ∘ Bad: Static, i.e. does not adapt to topology changes ∙ Flooding ∘ Good: Very robust. Works with every topology. ∘ Bad: Far from optimal. Too many messages sent ∙ How can we improve? ∘ Use a routing table (as with shortest path routing) ∘ Dynamically adapt routing table Distributed Systems Torben Weis 18 University Duisburg-Essen Dynamic Routing Algorithms (2) ∙ Distance Vector Routing ∘ Routers exchange their routing tables regularly with their neighbors ∘ Good: Only communication between neighbors ∘ Bad: Adapts slowly to new topologies ∙ Link State Routing ∘ Routers flood their view of the world ∘ Every router gains global knowledge ∘ Every router calculates shortest path ∘ Good: Adapts fast ∘ Bad: More overhead due to flooding Distributed Systems Torben Weis 19 University Duisburg-Essen Distance Vector Routing (1) ∙ Used in ARPANET, the early internet ∙ Each router maintains a routing table ∘ Table contains one row for every router (destination router, distance, outgoing line) ∙ Example for some router A: (D, 20, H) ∘ Means: router A can reach D at distance 20. To reach D, A sends the message to H A → H → X1 → … → Xn → D Distance = 20 Distributed Systems Torben Weis 20 University Duisburg-Essen Distance Vector Routing (2) ∙ Routers know distance to direct neighbors ∘ This can be measured ∙ The routing table is updated regularly ∘ Send routing table to every neighbor ∙ Assume A receives routing table of X ∘ A knows its distance to X is AX ∘ X says it can reach Y at a distance of XY → A can reach Y at a distance of A X + XY ∘ If this is the best route → insert it in the routing table Distributed Systems Torben Weis 21 University Duisburg-Essen Distance Vector Routing (3) Distributed Systems Torben Weis 22 University Duisburg-Essen Distance Vector Routing (4) ∙ Adapts fast to new nodes in the network ∘ Assume we have n nodes ∘ After 1 step the direct neighbors know it ∘ After 2 steps, routers in distance 2 know it ∘ … and so on ∘ After n steps, all routers know it ∙ Adapts slow to dead nodes in the network ∘ Distances will be increased until they reach “infinity” (see next slide) ∘ Solution: Set “infinity” ¸ Maximum distance + 1 ∘ Problem: How can we know the maximum distance? Distributed Systems Torben Weis 23 University Duisburg-Essen Distance Vector Routing (5) The count-to-infinity problem Distributed Systems Torben Weis 24 University Duisburg-Essen Link State Routing (1) ∙ Widely used today in the internet: OSPF ∙ Each router must do the following: ∘ Discover its neighbors, learn their network address ∘ Measure the delay or cost to each of its neighbors ∘ Construct a packet telling all it has just learned ∘ Send this packet to all other routers ∘ Compute the shortest path to every other router ∙ Each router gains global knowledge ∘ Routers can locally compute shortest paths ∙ Routers must have globally unique addresses ∘ Required for global knowledge Distributed Systems Torben Weis 25 University Duisburg-Essen Link State