LAN LANs Computer Networking Our goals: Overview: ß understand principles ß multiple access protocols behind LANs: ß example LANs: ß sharing a broadcast ß Ethernet Local Area Networks channel: multiple ß 802.11 access ß token ring ß link layer addressing ß token bus ß LAN interconnection ß link layer addressing Prof. Andrzej Duda ß instantiation and ß LAN interconnection [email protected] implementation of ß hubs, bridges, switches various LAN technologies http://duda.imag.fr 1 2 Characteristics Data link layer in LANs ß Shared channel ß multiplexing (TDM, FDM, or CDM) ß fixed allocation: wasted badwidth if no active sources ß statistical multiplexing (multiple access) ß suitable for bursty traffic - channel used at the full capacity ß Most of LANs ß no retransmission (up to upper layers) Metcalfe’s Etheret ß WLANs ß Short distances (100 m - 1 km) sketch ß ACK of delivery ß High bit rate (10 Mb/s, 100 Mb/s, 1 Gb/s) ß Shared communication channel ß Used in a distributed environment ß shared equipment, shared data 3 4 Multiple Access protocols Multiple Access Protocols ß single shared communication channel ß two or more simultaneous transmissions Three broad classes: by nodes: interference ß Random Access (Ethernet, 802.11) ß only one node can send successfully at a time ß allow collisions ß multiple access protocol: ß “recover” from collisions ß distributed algorithm that determines how ß Tokens - “Taking turns” (Token Ring, FDDI) stations share channel, i.e., determine when station can transmit ß tightly coordinate shared access to avoid collisions ß communication about channel sharing must ß Distributed Queue (DQDB) use channel itself! ß use the channel in the arrival order ß what to look for in multiple access protocols: ß synchronous or asynchronous ß Goal: efficient, fair, simple, decentralized ß information needed about other stations ß robustness (e.g., to channel errors) ß performance 5 6 1 LAN LAN Reference model LAN technologies ß Data link layer: LLC 802.2 ß services, multiple access Data link ß LAN technologies MAC MAC MAC ß addressing Physical 802.3 802.4 802.5 ß Ethernet, 802.11 ß repeaters, hubs, bridges, switches ß virtual LANs ß LLC - Logical Link Control: IEEE 802.2 (ISO 8802.2) ß MAC - Medium Access Control ß IEEE 802.3 (ISO 8802.3): CSMA/CD ß IEEE 802.4 (ISO 8802.4): token bus ß IEEE 802.5 (ISO 8802.5): token ring ß IEEE 802.11: CSMA/CA 7 8 IEEE 802.3 - Ethernet Coding host 100 ns time transceiver ß Synchronous transmission ß receiving station locks on 10 MHz - preamble ß Manchester coding repeater terminator 9 10 Random Access protocols CSMA/CD (Collision Detection) ß CSMA/CD (Carrier Sense Multiple Access/ Collision ß When node has packet to send Detection) ß transmit at full channel data rate R. ß no a priori coordination among nodes ß carrier sensing, deferral if ongoing transmission ß two or more transmitting nodes -> “collision”, ß collisions detected within short time ß colliding transmissions aborted, reducing channel wastage ß random access protocol specifies: ß persistent transmission ß how to detect collisions ß collision detection: ß hreotwra ntos mreiscsoivoenrs )from collisions (e.g., via delayed ß easy in wired LANs: measure signal strengths, compare transmitted, received signals ß Examples of random access protocols: ß difficult in wireless LANs: receiver shut off while transmitting ß ALOHA, slotted ALOHA ß CSMA, CSMA/CD (Ethernet), CSMA/CA (802.11) 11 12 2 LAN CSMA/CD algorithm CSMA / CD Collision i = 1 while (i <= maxAttempts) do ß A senses idle listen until channel is idle channel, starts A B transmitting transmit and listen 0 wait until (end of transmission) or ß shortly before T, T B senses idle (collision detected) channel, starts if collision detected then transmitting stop transmitting, send jam bits (32 bits) else wait for interframe delay (9.6 ms) leave wait random time increment i end do 13 14 CSMA / CD Jam Signal Random retransmission interval ß B senses r = random (0, 2k -1) collision, k = min (10, AttemptNb) continues to A B transmit the jam signal (32-bit) 0 t =r¥51.2ms, rŒ[0, 2k -1] r ß A senses T collision, continues to ß slot time = 51.2 ms transmit the jam ß 1st collision, r = 0, 1 signal t2 ß 2nd collision, r = 0, 1, 2, 3 ß 10th, r = 0, 1, …, 1023 ß 15th, stop 15 16 CSMA / CD Retransmission CSMA/CD performance A B 0 ß Maximum utilization of Ethernet (approximation) ß A waits random T time t1 q ª 1 / ( 1 + C a ) ß B waits random time t2=slottime t2 < t1 =2*slottime where a = 2Db / L, ß B senses channel D = propagation delay, b = bit rate, idle and transmits L = frame size ß A senses channel C is a constant: busy and defers to B ß C = 3.1 is a pessimistic value; ß A now waits until ß C = 2.5 is an approximate value based on simulations channel is idle t1 17 18 3 LAN Frame format (Ethernet v.2) Frame format (802.3) preamble dest sourcelength data pad CRC preamble dest source type data CRC 8 bytes 6 bytes 6 bytes 2 bytes 46 - 1500 bytes 4 bytes 8 bytes 6 bytes 6 bytes 2 bytes 46 - 1500 bytes 4 bytes ß Preamble LLC frame DSAP SSAP control data • synchronization : 10101010….0101011 1 byte 1 byte 1 byte • Addresses (xAA) (xAA) (x03) • unique, unicast and multicast (starts with the first bit 1) • broadcast: 11111…11111 SNAP frame prot. id type data • Type 3 bytes 2 bytes • upper layer protocol (IP, IPX, ARP, etc.) (x00) ß SNAP (Subnet Access Protocol) used in bridge management (any length of data: 0 - 1492) 19 20 Addressing Addressing ß MAC address: 48 bits = adapter identifier ß Data on Ethernet is transmitted least significant bit of ß sender puts destination MAC address in the frame first byte first (a bug dictated by Intel processors) ß all stations read all frames; keep only if destination ß Canonical representation thus inverts the order of bits address matches inside a byte (the first bit of the address is the least ß all 1 address (FF:FF:FF:FF:FF:FF) = broadcast significant bit of the first byte) ß examples of addresses: ß 01:00:5e:02:a6:cf (a group address) ß 08:00:20:71:0d:d4 (a SUN machine) B C ß 00:00:c0:3f:6c:a4 (a PC ) ß 00:00:0c:02:78:36 (a CISCO router) ß FF:FF:FF:FF:FF:FF the broadcast address MAC address A D 08:00:20:71:0d:d4 00:00:c0:3f:6c:a4 01:00:5e:02:a6:cf (group address) 21 22 Interconnecting LANs Repeaters ß Function of a simple, 2 port Why not just one big LAN? repeater: ß Limited amount of supportable traffic: on single LAN, all stations ß repeat bits received on one port must share bandwidth to other port ß limited distance ß if collision sensed on one port, ß large “collision domain” (can collide with many stations) repeat random bits on other port ß processing broadcast frames ß One network with repeaters = Repeater LAN evolution one collision domain ß increase the bit rate: 10Mb/s, 100Mb/s, 1 Gb/s ß Repeaters perform only ß from hubs to switches physical layer functions (bit repeaters) 23 24 4 LAN From Repeaters to Hubs 10 BASE T Hubs Multiport ß Multiport repeater (n ports), Repeater logically equivalent to: hub ß n simple repeater ß connected to one internal Ethernet segment hub hub ß Multi-port repeaters make it possible to use point-to-point segments (Ethernet in the Ethernet Hub box) S1 ßß efaauslet iosfo lmataionnagement S2 MpuRoletr-it- ß Tßreheu bto (préopléotgeuyr (mstualtri)port) S3 UTP segment peater ß max. 4 hubs to other hub 25 26 10 BASE T 10BaseT and 100BaseT ß 10/100 Mbps rate; latter called “fast ethernet” hub ß T stands for Twisted Pair ß Hub to which nodes are connected by twisted pair, thus “star topology” ß CSMA/CD supported by hubs host ß Two pairs ß Hub - host ß emission ß straight cable ß reception ß Hub - hub ß RJ-45 jack ß inversed cable 27 28 Gigabit Ethernet Gigabit Ethernet ß use standard Ethernet frame format ß 1000 BASE T ß allows for point-to-point links and shared broadcast ß over twisted pair (25 m) channels ß 1000 BASE SX ß in shared mode, CSMA/CD is used; short distances ß short wavelength (850 nm) over multimode (500 m) between nodes to be efficient ß 1000 BASE LX ß Full-Duplex at 1 Gbps for point-to-point links ß long wavelength (1300 nm) over multimode (550 m) and single- mode fiber (10 km) ß 1000 BASE LH (Long Haul) ß greater distance over 10 µm single-mode (500 m) ß 1000 BASE ZX ß extended wavelength (1550 nm) over 10 µm single-mode (70 km) 29 30 5 LAN Bridges Bridges – interconnection at layer 2 ß Link Layer devices: operate on Ethernet frames, port 1 port 3 Forwarding Table examining frame header and selectively forwarding Bridge Dest Port frame based on its destination A C MAC Nb ß Bridge isolates collision domains since it buffers Repeater port 2 addr frames A 1 ß When needs to forward a frame on a segment, B 2 B C 3 bridge uses CSMA/CD to access the segment and D D 2 transmit ß Can connect different type Ethernets, since it is a buffering device ß Bridges are intermediate systems, or switches, that ß Two main types of bridges: transparent bridges and forward MAC frames to destinations based on MAC spanning tree bridges (guarantee no loops) addresses ß Transparent bridges: learn the Forwarding Table 31 32 Collision domains Bridges vs. Routers ß both store-and-forward devices bridge ß routers: network layer devices (examine network layer headers) ß bridges are Link Layer devices (look into MAC headers) ß routers are more complex hub hub ß bridges are plug-and-play ß Bridges separate collision domains ß a bridged LAN maybe much larger than a repeated LAN ß there may be several frames transmitted in parallel in a bridged LAN 33 34 Repeaters and Bridges in OSI Model Ethernet Switches – layer 2 Application Application ß layer 2 (frame) forwarding, 5 to 7 Presentation Presentation 5 to 7 filtering using LAN addresses Session Session ß Switching: A-to-B and A’-to- 4 Transport Transport B’ simultaneously, no 3 Network Network 4 L2 PDU L2 PDU collisions 2 MLLACC (MAC Frame) MAC (MAC Frame) MLLACC 32 ß large number of interfaces 1 Physical Physical Physical Physical 1 ß often: individual hosts, star- End System Repeater Bridge End System connected into switch ß Bridges are layer 2 intermediate systems ß Ethernet, but no collisions! ß Repeaters are in layer 1 intermediate systems ß Routers are layer 3 intermediate systems (IP routers) 35 36 6 LAN Ethernet Switches (more) Switching Dedicated ß Store-and-forward ß receive frame, check if valid, retransmit ß 50 ms delay for a 64 bytes frame Shared ß Cut through ß address read, retransmit ß 20 ms delay for a 64 bytes frame ß transmission of non-valid frames 37 38 Full duplex Ethernet Gigabit Ethernet ß 1000 BASE T ß A shared medium Ethernet cable is half duplex ß over twisted pair (25 m) ß Full duplex Ethernet = a point to point cable, used in ß 1000 BASE SX both directions ß short wavelength (850 nm) over multimode (500 m) ß no access method, no CSMA/CD ß 1000 BASE LX ß 100 Mb/s and Gigabit Ethernet switches use full ß long wavelength (1300 nm) over multimode (550 m) and duplex links to avoid distance limitations and to single-mode fiber (10 km) guarantee bandwidth for stations ß 1000 BASE LH (Long Haul) ß Requires full duplex adapters at stations ß greater distance over 10 µm single-mode (500 m) ß 1000 BASE ZX ß extended wavelength (1550 nm) over 10 µm single-mode (70 km) 39 40 Wireless LAN: 802.11b 802.11 - Physical layer ß 802.11b: wireless LAN ß nominal bit rate of 11 Mb/s, degraded to 5.5, 2, 1 Mb/s ß 802.11b ß 6.5 Mb/s at application layer (file transfer) ß frequency band of 2.4 GHz: [2,4 GHz ; 2,48 GHz] ß shared radio channel, 2.4 GHz band, 13 channels (3 non ß nominal bit rate of 11 Mb/s overlapping of 22 MHz) ß passes through concrete ß DSSS (Direct Sequence Spread Spectrum), 1 bit Æ chipping ß 802.11g sequence ß frequency band of 2.4 GHz ß coverage 50m, open air 100m ß nominal bit rate of > 22 Mb/s ß MAC layer ß 802.11a ß DCF (Distributed Coordination Function) ß frequency band of 5 GHz: [5,15 GHz ; 5,825 GHz] ß CtoS MEtAh/eCrAn e(tC, anrori ecro lSliesinosne dMeuteltciptiloen Access/Collision Avoidance), similar ß nominal bit rate of 54 Mb/s ß PCF (Point Coordination Function) ß 6, 9, 12, 18, 24, 36, 48, 54 Mb/s, (6, 12, 24 Mb/s mandatory) ß polling, optional ß LOS - Line-of-Sight (no obstacles) 41 42 7 LAN 802.11 - Physical layer Channel selection Europe (ETSI) channel 1 channel 7 channel 13 2400 2412 2442 2472 2483.5 22 MHz [MHz] US (FCC)/Canada (IC) channel 1 channel 6 channel 11 2400 2412 2437 2462 2483.5 22 MHz [MHz] 43 44 Infrastructure vs. ad-hoc 802.11 - infrastructure ß Station (STA) infrastructure 802.11 LAN 802.x LAN ß ttoer tmhien awl irweiltehs sa cmceesdsiu mme acnhdan riasdmios network AP: Access Point contact to the access point AP wirAePd network AP STA1 BSS1Access Portal ß ßBagrsaircdo iuSop ef rroevfq icsuteea ntSicoeynts ( uBsSinSg) the same Point ß Access Point Distribution System ß station integrated into the Access wireless LAN and the distribution ESS Point system ad-hoc network BSS2 ß Portal ß bridge to other (wired) networks ß Distribution System STA2 802.11 LAN STA3 ß ionntee rlcoognicnaelc ntieotnw noerktwork to form 45 46 802.11 802.11 DCF - CSMA/CA ß Inter-frame spacing contention window ß SIFS (Short Inter Frame Spacing) DIFS DIFS (mraencdhoamniiszmed) back-off ß 10 ms, for ACK, CTS, polling response ß PIFS (PCF IFS) medium busy next frame ß for time-bounded service using PCF direct access if t ß DIFS (DCF IFS) medium is free ≥ DIFS slot time ß 50 ms, for contention access ß Channel idle during DIFS, transmit frame ß If the medium is busy, wait for a free DIFS and a random back-off time (collision avoidance, multiple of DIFS DIFS slot-time) PIFS medium busy SIFS contention next frame ß If another station uses the medium during the back-off time of the station, the back-off timer stops (fairness) t direct access if medium is free ≥ DIFS 47 48 8 LAN CSMA/CA (Collision Avoidance) 802.11 - CSMA/CA A B ß Sending unicast packets ß Channel idle during ß station has to wait for DIFS before sending data DIFS, transmit frame DIFS ß receivers acknowledge at once (after waiting for SIFS) if the ß Frame received packet was received correctly (CRC) correctly, wait SIFS, and ß automatic retransmission of data packets in case of send ACK transmission errors data DIFS data sender SIFS SIFS receiver ACK ACK other DIFS data stations t waiting time contention 49 50 CSMA/CA (Collision Avoidance) Contention A B ß If channel busy, defer. T(N) DIFS SLOT SIFS Then, if idle during DIFS, DIFS wait random interval data ACK (multiple of the slot) and contention t transmit window backoff time ß If channel busy, wait again ß Backoff time - random interval until medium idle for at slot ß Contention Window: uniform distribution [0, CW] * SLOT least DIFS ß CW: CWmin = 31, CWmax = 1023 ß Contention window doubles data ß SLOT = 20 ms with each collision - ß T(N) should also include time wasted in collisions exponential back-off 51 52 Hidden Terminal effect 802.11 - contention ß Hidden terminals: A and B cannot hear each other DIFS DIFS DIFS DIFS because of obstacles or signal attenuation; so, their station1 busy packets collide at B busy station2 exponential busy backoff station3 busy station4 collision busy station5 t elapsed backoff time busy medium busy residual backoff time packet arrival at MAC shortest backoff time 53 54 9 LAN RTS/CTS Extension Register to Access Point A B ß CTS (Clear To Send) “freezes” stations within DIFS range of receiver (hidden from transmitter); this RTS Mobile Sign-on (Addr) prevents collisions by SIFS hidden station during data OK (NWID) Beacon CTS transfer ß RTS (Request To Send) and SIFS CTS are very short: collisions are very unlikely data Access point Access point (the end result is similar to Ethernet Collision Detection) SIFS addressport ACK Addr Wireless 55 56 Hand-off Bluetooth ß Replaces cables ß short range (10m), low power, cheap ß 2.4 GHz band Hand-off Mobile ß FHSS (Frequency Hopping Spread Spectrum) ß piconet ß all devices share the same hopping sequence OK (NWID) ß one master, seven slaves ß bit rate: around 1 Mb/s ß symmetric connections - 432.6 kb/s ß asymmetric - 721 kb/s, 57.6 Kb/s Access point Hand-off Access point ß access method: polling, reservation Ethernet addressport Addr Wireless 57 58 IEEE 802.4 Physical layer ß Token Bus ß industrial LAN 1 0 ß Physical layer ß modulation (broadband) ß coaxial cable 75 W ß 1, 5, 10 Mb/s bit rate ß Access method code violation ß token on a virtual ring 59 60 10