Computer Networking: A Top-Down Approach 8th Edition PDF

Chapter 6 The Link Layer and LANs A note on the use of these PowerPoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit...

Chapter 6 The Link Layer and LANs A note on the use of these PowerPoint slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: ▪ If you use these slides (e.g., in a class) that you mention their source (after all, we’d like people to use our book!) ▪ If you post any slides on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Computer Networking: A For a revision history, see the slide note for this page. Top-Down th Approach Thanks and enjoy! JFK/KWR 8 edition All material copyright 1996-2023 Jim Kurose, Keith Ross J.F Kurose and K.W. Ross, All Rights Reserved Pearson, 2020 Link layer and LANs: our goals ▪understand principles ▪ instantiation, implementation behind link layer services: of various link layer error detection, correction technologies sharing a broadcast channel: multiple access link layer addressing local area networks: Ethernet, VLANs ▪datacenter networks Link Layer: 6-2 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-3 Link layer: introduction terminology: mobile network ▪ hosts, routers: nodes national or global ISP ▪ communication channels that connect adjacent nodes along communication path: links wired , wireless LANs ▪ layer-2 packet: frame, encapsulates datagram datacenter network link layer has responsibility of transferring datagram from one node enterprise to physically adjacent node over a link network Link Layer 4 Link layer: context ▪ datagram transferred by different link protocols over different links: e.g., WiFi on first link, Ethernet on next link ▪ each link protocol provides different services e.g., may or may not provide reliable data transfer over link Link Layer 5  Transportation analogy transportation analogy: ▪ trip from Princeton to Lausanne Princeton limo: Princeton to JFK JFK plane: JFK to Geneva train: Geneva to Lausanne ▪ tourist = datagram ▪ transport segment = communication link ▪ transportation mode = link-layer protocol ▪ travel agent = routing algorithm Geneva Lausanne Link Layer 6 Link layer: services ▪ framing, link access: … encapsulate datagram into frame, adding … header, trailer Cable access channel access if shared medium “MAC” addresses in frame headers identify source, destination (different from IP address!) ▪ reliable delivery between adjacent nodes cellular we already know how to do this! seldom used on low bit-error links Ethernet LANs wireless links: high error rates Q: why both link-level and end-end WiFi reliability? Link Layer 7 Link layer: services (more) ▪ flow control: … pacing between adjacent sending and … receiving nodes Cable access ▪ error detection: errors caused by signal attenuation, noise. receiver detects errors, signals retransmission, or drops frame ▪ error correction: cellular receiver identifies and corrects bit error(s) without retransmission Ethernet LANs ▪ half-duplex and full-duplex: with half duplex, nodes at both ends of link WiFi can transmit, but not at same time Link Layer 8 Host link-layer implementation ▪ in each-and-every host ▪ link layer implemented on-chip or in network interface card (NIC) application transport memor cpu implements link, physical layer network link y ▪ attaches into host’s system buses control host bus (e.g., PCI) ▪ combination of hardware, link physical ler physical software, firmware network interface Link Layer 9 Interfaces communicating application application transport memor memor transport datagram network cpu CPU network y y link link control control linkh datagram ler ler link datagram link physical physical physical physical sending side: receiving side: ▪ encapsulates datagram in frame ▪ looks for errors, reliable data ▪ adds error checking bits, reliable data transfer, flow control, etc. transfer, flow control, etc. ▪ extracts datagram, passes to upper layer at receiving side Link Layer 10 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-11 Error detection EDC: error detection and correction bits (e.g., redundancy) D: data protected by error checking, may include header fields datagram datagram Error detection not 100% otherwise reliable! all bits in D’ N ▪ protocol may miss OK detected some errors, but rarely ? error d data bits ▪ larger EDC field yields D EDC D’ EDC’ better detection and correction bit-error prone link Link Layer 12  Parity checking Can detect and correct errors single bit parity: (without retransmission!) ▪ detect single bit errors ▪ two-dimensional parity: detect and correct single bit errors 0111000110101011 1 row parity d data bits d1,1... d1,j d1,j+1 d2,1... d2,j d2,j+1 parity bit............ Even/odd parity: set parity bit so di,1... di,j di,j+1 there is an even/odd number of 1’s column parity di+1,1... di+1,j di+1,j+1 At receiver: ▪ compute parity of d received detected 10101 1 no errors: 1 0 1 0 1 1 bits 11110 0 and 10110 0 parity error ▪ compare with received parity bit 01110 1 correctable single-bit 01110 1 – if different than error detected 10101 0 error: 10101 0 parity error * Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/ Internet checksum (review, see section 3.3) Goal: detect errors (i.e., flipped bits) in transmitted segment sender: receiver: ▪ treat contents of UDP ▪ compute checksum of received segment (including UDP header segment fields and IP addresses) as sequence of 16-bit integers ▪ check if computed checksum equals ▪ checksum: addition (one’s checksum field value: complement sum) of segment not equal - error detected content equal - no error detected. But maybe ▪ checksum value put into errors nonetheless? More later …. UDP checksum field Link Layer 14 Cyclic Redundancy Check (CRC) ▪ more powerful error-detection coding ▪ D: data bits (given, think of these as a binary number) ▪ G: bit pattern (generator), of r+1 bits (given, specified in CRC standard) r CRC bits d data bits D R bits to send = D *2r XOR R formula for these bits sender: compute r CRC bits, R, such that exactly divisible by G (mod 2) receiver knows G, divides by G. If non-zero remainder: error detected! can detect all burst errors less than r+1 bits widely used in practice (Ethernet, 802.11 WiFi) Link Layer 15  Cyclic Redundancy Check (CRC): example Sender wants to compute R G 1 0 1 0 1 1 such that: 1 0 0 1 1 0 1 1 1 00 0 0 D. 2r XOR R = nG 1 0 0 1 1 0 1 D * 2r (here, r=3) 0 0 0... or equivalently (XOR R both sides): 1 0 1 0 D. 2r = nG XOR R 1 0 0 1 1 1 0... which says: 0 0 0 1 1 0 0 if we divide D. 2r by G, we 1 0 0 1 want remainder R to satisfy: 1 0 1 0. r 1 0 0 1 R = remainder [ 2 ] D algorithm for 0 1 1 G computing R R * Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/ Link Layer 16 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-17 Multiple access links, protocols two types of “links”: ▪ point-to-point point-to-point link between Ethernet switch, host PPP for dial-up access ▪ broadcast (shared wire or medium) old-school Ethernet upstream HFC in cable-based access network 802.11 wireless LAN, 4G/4G. satellite shared wire (e.g., shared radio: 4G/5G shared radio: WiFi shared radio: satellite humans at a cocktail party cabled Ethernet) (shared air, acoustical) Link Layer 18 Multiple access protocols ▪ single shared broadcast channel ▪ two or more simultaneous transmissions by nodes: interference collision if node receives two or more signals at the same time multiple access protocol ▪ distributed algorithm that determines how nodes share channel, i.e., determine when node can transmit ▪ communication about channel sharing must use channel itself! no out-of-band channel for coordination Link Layer 19 An ideal multiple access protocol given: multiple access channel (MAC) of rate R bps desiderata: 1. when one node wants to transmit, it can send at rate R. 2. when M nodes want to transmit, each can send at average rate R/M 3. fully decentralized: no special node to coordinate transmissions no synchronization of clocks, slots 4. simple Link Layer 20 MAC protocols: taxonomy three broad classes: ▪ channel partitioning divide channel into smaller “pieces” (time slots, frequency, code) allocate piece to node for exclusive use ▪ random access channel not divided, allow collisions “recover” from collisions ▪ “taking turns” nodes take turns, but nodes with more to send can take longer turns Link Layer 21 Channel partitioning MAC protocols: TDMA TDMA: time division multiple access ▪ access to channel in “rounds” ▪ each station gets fixed length slot (length = packet transmission time) in each round ▪ unused slots go idle ▪ example: 6-station LAN, 1,3,4 have packets to send, slots 2,5,6 idle 6-slot 6-slot frame frame 1 3 4 1 3 4 Link Layer 22 Channel partitioning MAC protocols: FDMA FDMA: frequency division multiple access ▪ channel spectrum divided into frequency bands ▪ each station assigned fixed frequency band ▪ unused transmission time in frequency bands go idle ▪ example: 6-station LAN, 1,3,4 have packet to send, frequency bands 2,5,6 idle time frequency bands FDM cable Link Layer 23 Random access protocols ▪ when node has packet to send transmit at full channel data rate R no a priori coordination among nodes ▪ two or more transmitting nodes: “collision” ▪ random access protocol specifies: how to detect collisions how to recover from collisions (e.g., via delayed retransmissions) ▪ examples of random access MAC protocols: ALOHA, slotted ALOHA CSMA, CSMA/CD, CSMA/CA Link Layer 24 Slotted ALOHA operation: t0 t0+1 ▪ when node obtains fresh assumptions: frame, transmits in next slot ▪ all frames same size if no collision: node can send ▪ time divided into equal size new frame in next slot slots (time to transmit 1 frame) if collision: node retransmits ▪ nodes start to transmit only frame in each subsequent slot beginning slot with probability p until ▪ nodes are synchronized success ▪ if 2 or more nodes transmit in randomization – why? slot, all nodes detect collision Link Layer 25 Slotted ALOHA node 1 1 1 1 1 node 2 2 2 2 C: collision S: success node 3 3 3 3 E: empty C E C S E C E S S Pros: Cons: ▪ single active node can ▪ collisions, wasting slots continuously transmit at full rate ▪ idle slots of channel ▪ nodes may be able to detect collision in ▪ highly decentralized: only slots in less than time to transmit packet nodes need to be in sync ▪ clock synchronization ▪ simple Link Layer 26 Slotted ALOHA: efficiency efficiency: long-run fraction of successful slots (many nodes, all with many frames to send) ▪ suppose: N nodes with many frames to send, each transmits in slot with probability p prob that given node has success in a slot = p(1-p)N-1 prob that any node has a success = Np(1-p)N-1 max efficiency: find p* that maximizes Np(1-p)N-1 for many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives: max efficiency = 1/e =.37 ▪ at best: channel used for useful transmissions 37% of time! Link Layer 27 Pure ALOHA ▪ unslotted Aloha: simpler, no synchronization when frame first arrives: transmit immediately ▪ collision probability increases with no synchronization: frame sent at t0 collides with other frames sent in [t0-1,t0+1] will overlap will overlap with start of with end of i’s frame i’s frame t0 - 1 t0 t0 + 1 ▪ pure Aloha efficiency: 18% ! Link Layer 28 CSMA (carrier sense multiple access) simple CSMA: listen before transmit: if channel sensed idle: transmit entire frame if channel sensed busy: defer transmission ▪ human analogy: don’t interrupt others! CSMA/CD: CSMA with collision detection collisions detected within short time colliding transmissions aborted, reducing channel wastage collision detection easy in wired, difficult with wireless ▪ human analogy: the polite conversationalist Link Layer 29 CSMA: collisions spatial layout of nodes ▪ collisions can still occur with carrier sensing: propagation delay means two nodes may not hear each other’s just-started transmission ▪ collision: entire packet transmission time wasted distance & propagation delay play role in in determining collision probability Link Layer 30 CSMA/CD: spatial layout of nodes ▪ CSMA/CD reduces the amount of time wasted in collisions transmission aborted on collision detection Link Layer 31 Ethernet CSMA/CD algorithm 1. Ethernet receives datagram from network layer, creates frame 2. If Ethernet senses channel: if idle: start frame transmission. if busy: wait until channel idle, then transmit 3. If entire frame transmitted without collision - done! 4. If another transmission detected while sending: abort, send jam signal 5. After aborting, enter binary (exponential) backoff: after mth collision, chooses K at random from {0,1,2, …, 2m-1}. Ethernet waits K·512 bit times, returns to Step 2 more collisions: longer backoff interval Link Layer 32 CSMA/CD efficiency ▪ Tprop = max prop delay between 2 nodes in LAN ▪ ttrans = time to transmit max-size frame ▪ efficiency goes to 1 as tprop goes to 0 as ttrans goes to infinity ▪ better performance than ALOHA: and simple, cheap, decentralized! Link Layer 33 “Taking turns” MAC protocols channel partitioning MAC protocols: ▪ share channel efficiently and fairly at high load ▪ inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node! random access MAC protocols ▪ efficient at low load: single node can fully utilize channel ▪ high load: collision overhead “taking turns” protocols ▪ look for best of both worlds! Link Layer 34 “Taking turns” MAC protocols polling: ▪ centralized controller “invites” other nodes to transmit in turn data poll ▪ typically used with “dumb” devices centralized ▪ concerns: data controller polling overhead latency client devices single point of failure (master) Bluetooth uses polling Link Layer 35 “Taking turns” MAC protocols T token passing: ▪ control token message explicitly passed from one node (nothing to next, sequentially to send) ▪ transmit while holding token T ▪ concerns: token overhead latency single point of failure (token) data Link Layer 36 Cable access network: FDM, TDM and random access! Internet frames, TV channels, control transmitted downstream at different frequencies cable headend CMTS … splitter cable cable modem … modem ISP termination system ▪ multiple downstream (broadcast) FDM channels: up to 1.6 Gbps/channel ▪ single CMTS transmits into channels ▪ multiple upstream channels (up to 1 Gbps/channel) ▪ multiple access: all users contend (random access) for certain upstream channel time slots; others assigned TDM Link Layer: 6-37 Cable access network: MAP frame for Interval [t1, t2] Downstream channel i CMTS Upstream channel j cable headend t1 t2 Residences with cable modems Minislots containing Assigned minislots containing cable modem minislots request frames upstream data frames DOCSIS: data over cable service interface specification ▪ FDM over upstream, downstream frequency channels ▪ TDM upstream: some slots assigned, some have contention downstream MAP frame: assigns upstream slots request for upstream slots (and data) transmitted random access (binary backoff) in selected slots Link Layer: 6-38 Summary of MAC protocols ▪ channel partitioning, by time, frequency or code Time Division, Frequency Division ▪ random access (dynamic), ALOHA, S-ALOHA, CSMA, CSMA/CD carrier sensing: easy in some technologies (wire), hard in others (wireless) CSMA/CD used in Ethernet CSMA/CA used in 802.11 ▪ taking turns polling from central site, token passing Bluetooth, FDDI, token ring Link Layer: 6-39 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-40 MAC addresses ▪ 32-bit IP address: network-layer address for interface used for layer 3 (network layer) forwarding e.g.: 128.119.40.136 ▪ MAC (or LAN or physical or Ethernet) address: function: used “locally” to get frame from one interface to another physically-connected interface (same subnet, in IP-addressing sense) 48-bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable e.g.: 1A-2F-BB-76-09-AD hexadecimal (base 16) notation (each “numeral” represents 4 bits) Link Layer: 6-41 MAC addresses each interface on LAN ▪ has unique 48-bit MAC address ▪ has a locally unique 32-bit IP address (as we’ve seen) 137.196.7.78 1A-2F-BB-76-09-AD LAN (wired or wireless) 137.196.7/24 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 137.196.7.23 137.196.7.14 0C-C4-11-6F-E3-98 137.196.7.88 Link Layer: 6-42 MAC addresses ▪ MAC address allocation administered by IEEE ▪ manufacturer buys portion of MAC address space (to assure uniqueness) ▪ analogy: MAC address: like Social Security Number IP address: like postal address ▪ MAC flat address: portability can move interface from one LAN to another recall IP address not portable: depends on IP subnet to which node is attached Link Layer: 6-43 ARP: address resolution protocol Question: how to determine interface’s MAC address, knowing its IP address? ARP table: each IP node (host, ARP router) on LAN has table 137.196.7.78 ARP 1A-2F-BB-76-09-AD IP/MAC address mappings for ARP some LAN nodes: LAN < IP address; MAC address; TTL> 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 137.196.7.23 137.196.7.14 TTL (Time To Live): time after ARP 0C-C4-11-6F-E3-98 which address mapping will be 137.196.7.88 forgotten (typically 20 min) Link Layer: 6-44 ARP protocol in action example: A wants to send datagram to B B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address A broadcasts ARP query, containing B's IP addr Ethernet frame (sent to FF-FF-FF-FF-FF-FF) 1 destination MAC address = FF-FF-FF-FF-FF-FF all nodes on LAN receive ARP query C Source MAC: 71-65-F7-2B-08-53 Source IP: 137.196.7.23 ARP table in A Target IP address: 137.196.7.14 … IP addr MAC addr TTL TTL A B 1 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 137.196.7.23 137.196.7.14 D Link Layer: 6-45 ARP protocol in action example: A wants to send datagram to B B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address ARP message into Ethernet frame (sent to 71-65-F7-2B-08-53) C Target IP address: 137.196.7.14 Target MAC address: ARP table in A 58-23-D7-FA-20-B0 … IP addr MAC addr TTL TTL A B 2 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 137.196.7.23 137.196.7.14 2 B replies to A with ARP response, giving its MAC address D Link Layer: 6-46 ARP protocol in action example: A wants to send datagram to B B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address C ARP table in A IP addr MAC addr TTL TTL 137.196. 58-23-D7-FA-20-B0 500 A B 7.14 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 137.196.7.23 137.196.7.14 3 A receives B’s reply, adds B entry into its local ARP table D Link Layer: 6-47 Routing to another subnet: addressing walkthrough: sending a datagram from A to B via R ▪ focus on addressing – at IP (datagram) and MAC layer (frame) levels ▪ assume that: A knows B’s IP address A knows IP address of first hop router, R (how?) A knows R’s MAC address (how?) A B R 111.111.111.111 74-29-9C-E8-FF-55 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.220 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221 88-B2-2F-54-1A-0F Link Layer: 6-48 Routing to another subnet: addressing ▪ A creates IP datagram with IP source A, destination B ▪ A creates link-layer frame containing A-to-B IP datagram R's MAC address is frame’s destination MAC src: 74-29-9C-E8-FF-55 MAC dest: E6-E9-00-17-BB-4B IP src: 111.111.111.111 IP dest: 222.222.222.222 IP Eth Phy A B R 111.111.111.111 74-29-9C-E8-FF-55 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.220 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221 88-B2-2F-54-1A-0F Link Layer: 6-49 Routing to another subnet: addressing ▪ frame sent from A to R ▪ frame received at R, datagram removed, passed up to IP MAC src: 74-29-9C-E8-FF-55 IP src: 111.111.111.111 MAC dest: E6-E9-00-17-BB-4B IP dest: 222.222.222.222 IP src: 111.111.111.111 IP dest: 222.222.222.222 IP IP Eth Eth Phy Phy A B R 111.111.111.111 74-29-9C-E8-FF-55 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.220 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221 88-B2-2F-54-1A-0F Link Layer: 6-50 Routing to another subnet: addressing ▪ R determines outgoing interface, passes datagram with IP source A, destination B to link layer ▪ R creates link-layer frame containing A-to-B IP datagram. Frame destination address: B's MAC address MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2A IP src: 111.111.111.111 IP dest: 222.222.222.222 IP Eth Phy A B R 111.111.111.111 74-29-9C-E8-FF-55 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.220 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221 88-B2-2F-54-1A-0F Link Layer: 6-51 Routing to another subnet: addressing ▪ R determines outgoing interface, passes datagram with IP source A, destination B to link layer ▪ R creates link-layer frame containing A-to-B IP datagram. Frame destination address: B's MAC address MAC src: 1A-23-F9-CD-06-9B ▪ transmits link-layer frame MAC dest: 49-BD-D2-C7-56-2A IP src: 111.111.111.111 IP dest: 222.222.222.222 IP IP Eth Eth Phy Phy A B R 111.111.111.111 74-29-9C-E8-FF-55 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.220 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221 88-B2-2F-54-1A-0F Link Layer: 6-52 Routing to another subnet: addressing ▪ B receives frame, extracts IP datagram destination B ▪ B passes datagram up protocol stack to IP IP src: 111.111.111.111 IP dest: 222.222.222.222 IP IP Eth Eth Phy Phy A B R 111.111.111.111 74-29-9C-E8-FF-55 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.220 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221 88-B2-2F-54-1A-0F Link Layer: 6-53 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-54 Ethernet “dominant” wired LAN technology: ▪ first widely used LAN technology ▪ simpler, cheap ▪ kept up with speed race: 10 Mbps – 400 Gbps ▪ single chip, multiple speeds (e.g., Broadcom BCM5761) Bob Metcalfe: Ethernet co-inventor, 2022 ACM Turing Award recipient Metcalfe’s Ethernet sketch https://www.uspto.gov/learning-and-resources/journeys-innovation/audio-stories/defying-doubters Link Layer: 6-55 Ethernet: physical topology ▪ bus: popular through mid 90s all nodes in same collision domain (can collide with each other) ▪ switched: prevails today active link-layer 2 switch in center each “spoke” runs a (separate) Ethernet protocol (nodes do not collide with each other) bus: coaxial cable switched Link Layer: 6-56 Ethernet frame structure sending interface encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame type dest. source data (payload) CRC preamble address address preamble: ▪ used to synchronize receiver, sender clock rates ▪ 7 bytes of 10101010 followed by one byte of 10101011 Link Layer: 6-57 Ethernet frame structure (more) type dest. source data (payload) CRC preamble address address ▪ addresses: 6 byte source, destination MAC addresses if adapter receives frame with matching destination address, or with broadcast address (e.g., ARP packet), it passes data in frame to network layer protocol otherwise, adapter discards frame ▪ type: indicates higher layer protocol mostly IP but others possible, e.g., Novell IPX, AppleTalk used to demultiplex up at receiver ▪ CRC: cyclic redundancy check at receiver error detected: frame is dropped Link Layer: 6-58 Ethernet: unreliable, connectionless ▪connectionless: no handshaking between sending and receiving NICs ▪unreliable: receiving NIC doesn’t send ACKs or NAKs to sending NIC data in dropped frames recovered only if initial sender uses higher layer rdt (e.g., TCP), otherwise dropped data lost ▪Ethernet’s MAC protocol: unslotted CSMA/CD with binary backoff Link Layer: 6-59  802.3 Ethernet standards: link & physical layers ▪ many different Ethernet standards common MAC protocol and frame format different speeds: 2 Mbps,... 100 Mbps, 1Gbps, 10 Gbps, 40 Gbps, 80 Gbps different physical layer media: fiber, cable MAC protocol application and frame format transport network 100BASE-TX 100BASE-T2 100BASE-FX link 100BASE-T4 100BASE-SX 100BASE-BX physical copper (twister pair) physical layer fiber physical layer Link Layer: 6-60 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-61 Ethernet switch ▪ Switch is a link-layer device: takes an active role store, forward Ethernet (or other type of) frames examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses CSMA/CD to access segment ▪ transparent: hosts unaware of presence of switches ▪ plug-and-play, self-learning switches do not need to be configured Link Layer: 6-62 Switch: multiple simultaneous transmissions ▪ hosts have dedicated, direct connection to switch A ▪ switches buffer packets C’ B ▪ Ethernet protocol used on each 1 2 incoming link, so: 6 3 no collisions; full duplex 5 4 each link is its own collision domain B’ C A’ ▪ switching: A-to-A’ and B-to-B’ can transmit simultaneously, without collisions switch with six interfaces (1,2,3,4,5,6) Link Layer: 6-63 Switch: multiple simultaneous transmissions ▪ hosts have dedicated, direct connection to switch A ▪ switches buffer packets C’ B ▪ Ethernet protocol used on each 1 2 incoming link, so: 6 3 no collisions; full duplex 5 4 each link is its own collision domain B’ C A’ ▪ switching: A-to-A’ and B-to-B’ can transmit simultaneously, without collisions switch with six interfaces (1,2,3,4,5,6) but A-to-A’ and C to A’ can not happen simultaneously Link Layer: 6-64 Switch forwarding table Q: how does switch know A’ reachable via interface 4, B’ reachable via interface 5? A C’ B A: each switch has a switch table, each 1 entry: 6 2 ▪ (MAC address of host, interface to reach 5 4 3 host, time stamp) ▪ looks like a routing table! B’ C A’ Q: how are entries created, maintained in switch table? ▪ something like a routing protocol? Link Layer: 6-65 Switch: self-learning Source: A ▪switch learns which hosts Dest: A’ A can be reached through AA’ which interfaces C’ B when frame received, switch 1 2 6 “learns” location of sender: 3 5 incoming LAN segment 4 records sender/location pair B’ C A’ in switch table Switch table MAC addr interface TTL (initially empty) A 1 60 Link Layer: 6-66 Switch: frame filtering/forwarding when frame received at switch: 1. record incoming link, MAC address of sending host 2. index switch table using MAC destination address 3. if entry found for destination then { if destination on segment from which frame arrived then drop frame else forward frame on interface indicated by entry } else flood Link Layer: 6-67 Self-learning, forwarding: example Source: A Dest: A’ ▪ frame destination, A’, A A’ location unknown: flood A C’ B ▪ destination A location 1 known: selectively send 6A 2 3 on just one link A’ 5 4 B’ C A’ A A’ MAC addr interface TTL A 1 60 switch table A’ 4 60 (initially empty) Link Layer: 6-68 Interconnecting switches self-learning switches can be connected together: S4 S1 S3 A S2 F D I B C G H E Q: sending from A to G - how does S1 know to forward frame destined to G via S4 and S3? ▪ A: self learning! (works exactly the same as in single-switch case!) Link Layer: 6-69 Self-learning multi-switch example Suppose C sends frame to I, I responds to C S4 S1 S3 A S2 F D I B C G H E Q: show switch tables and packet forwarding in S1, S2, S3, S4 Link Layer: 6-70  UMass Campus Network - Detail UMass network: ▪ 4 firewalls to off campus ▪ 10 routers border border ▪ 2000+ network switches ▪ 6000 wireless access points ▪ 30000 active wired Core core network jacks ▪ 55000 active end-user wireless devices Agg1 Agg2 Agg3 Agg4 WiFi... firewall data center … all built,............ Wireless Wireless operated, building closets Controller Controller maintained by ~15 people  UMass Campus Network - Detail Protocols Link Speeds to off campus eBGP 10G; 100G pending inter-domain border border routing iBGP 40G & 100G IS-IS Core core intra-domain routing IS-IS 40G Agg1 Agg2 Agg3 Agg4 WiFi... firewall data center............ Wireless Wireless layer-2 Ethernet building Controller Controller 10G & 1G closets switching Switches vs. routers application transport both are store-and-forward: datagram frame network link ▪ routers: network-layer devices (examine physical link frame network-layer headers) physical ▪ switches: link-layer devices (examine switch link-layer headers) network datagram link frame both have forwarding tables: physical ▪ routers: compute tables using routing application algorithms, IP addresses transport ▪ switches: learn forwarding table using network link flooding, learning, MAC addresses physical 6-736-73 Link Layer: Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-74 Virtual LANs (VLANs): motivation Q: what happens as LAN sizes scale, users change point of attachment? single broadcast domain: ▪ scaling: all layer-2 broadcast traffic (ARP, DHCP, unknown MAC) must cross entire LAN Computer ▪ efficiency, security, privacy issues Science EE Link Layer: 6-75 Virtual LANs (VLANs): motivation Q: what happens as LAN sizes scale, users change point of attachment? single broadcast domain: ▪ scaling: all layer-2 broadcast traffic (ARP, DHCP, unknown MAC) must cross entire LAN Computer ▪ efficiency, security, privacy, efficiency Science EE issues administrative issues: ▪ CS user moves office to EE - physically attached to EE switch, but wants to remain logically attached to CS switch Link Layer: 6-76 Port-based VLANs port-based VLAN: switch ports grouped (by switch management software) so that single physical switch …… Virtual Local Area Network (VLAN) 1 7 9 15 2 8 16 switch(es) supporting 10 … … VLAN capabilities can be EE (VLAN ports 1-8) CS (VLAN ports 9-15) configured to define multiple virtual LANS … operates as multiple virtual switches over single physical LAN infrastructure. 1 7 9 15 2 8 10 16 … … EE (VLAN ports 1-8) CS (VLAN ports 9-15) Link Layer: 6-77 Port-based VLANs ▪ traffic isolation: frames to/from ports 1-8 can only reach ports 1-8 can also define VLAN based on MAC addresses of endpoints, rather than switch port ▪ dynamic membership: ports can be dynamically assigned among VLANs 1 7 9 15 2 8 10 16 ▪ forwarding between VLANS: done via … … routing (just as with separate switches) EE (VLAN ports 1-8) CS (VLAN ports 9-15) in practice vendors sell combined switches plus routers Link Layer: 6-78 VLANS spanning multiple switches 1 7 9 15 1 3 5 7 2 8 10 16 2 4 6 8 … … … EE (VLAN ports 1-8) CS (VLAN ports 9-15) Ports 2,3,5 belong to EE VLAN Ports 4,6,7,8 belong to CS VLAN trunk port: carries frames between VLANS defined over multiple physical switches ▪ frames forwarded within VLAN between switches can’t be vanilla 802.1 frames (must carry VLAN ID info) ▪ 802.1q protocol adds/removed additional header fields for frames forwarded between trunk ports Link Layer: 6-79 802.1Q VLAN frame format type dest. source data (payload) CRC preamble address address 802.1 Ethernet frame type dest. source CRC preamble address address data (payload) 802.1Q frame 2-byte Tag Protocol Identifier Recomputed (value: 81-00) Tag Control Information CRC (12 bit VLAN ID field, 3 bit priority field like IP TOS) Link Layer: 6-80 EVPN: Ethernet VPNs (aka VXLANs) 5 1 7 9 15 1 3 7 2 8 10 16 IP Ethernet 2 4 6 8 datagram frame … … … Sunnyvale Bangalore data center Ethernet data center Layer-2 Ethernet switches logically connected to each other (e.g., using IP as an underlay) ▪ Ethernet frames carried within IP datagrams between sites ▪ “tunneling scheme to overlay Layer 2 networks on top of Layer 3 networks... runs over the existing networking infrastructure and provides a means to "stretch" a Layer 2 network.” [RFC 7348] Link Layer: 6-81 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-82 Multiprotocol label switching (MPLS) ▪ goal: high-speed IP forwarding among network of MPLS-capable routers, using fixed length label (instead of shortest prefix matching) faster lookup using fixed length identifier borrowing ideas from Virtual Circuit (VC) approach but IP datagram still keeps IP address! Ethernet remainder of Ethernet remainder frame, including of Ethernet IP frame, including IP MPLS header header header with IP source, destination addresses header with IP source, destination addresses label Exp S TTL 20 3 1 5 Link Layer: 6-83 MPLS capable routers ▪ a.k.a. label-switched router ▪ forward packets to outgoing interface based only on label value (don’t inspect IP address) MPLS forwarding table distinct from IP forwarding tables ▪ flexibility: MPLS forwarding decisions can differ from those of IP use destination and source addresses to route flows to same destination differently (traffic engineering) re-route flows quickly if link fails: pre-computed backup paths Link Layer: 6-84 MPLS versus IP paths R6 D IP router R4 R3 R5 A R2 ▪ IP routing: path to destination determined by destination address alone Link Layer: 6-85 MPLS versus IP paths IP/MPLS entry router (R4) can use different MPLS routes to A based, e.g., on IP source address or other fields R6 D IP router R4 R3 R5 IP/MPLS router A R2 R1 ▪ IP routing: path to destination determined by destination address alone ▪ MPLS routing: path to destination can be based on source and destination address flavor of generalized forwarding (MPLS 10 years earlier) fast reroute: precompute backup routes in case of link failure Link Layer: 6-86 MPLS signaling ▪ modify OSPF, IS-IS link-state flooding protocols to carry info used by MPLS routing: e.g., link bandwidth, amount of “reserved” link bandwidth ▪ entry MPLS router uses RSVP-TE signaling protocol to set up MPLS forwarding at downstream routers R6 RSVP-TE D R4 R3 R5 modified link state A flooding R2 R1 Link Layer: 6-87 MPLS forwarding tables in out out label label dest interface 10 A 0 in out out 12 D 0 label label dest interface 8 A 1 10 6 A 1 12 9 D 0 R6 0 0 D 1 1 R4 R3 R5 0 0 A R2 R1 in out out in out out label label dest interface label label dest interface 8 6 A 0 6 - A 0 Link Layer: 6-88 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-89 Datacenter networks 10’s to 100’s of thousands of hosts, often closely coupled, in close proximity: ▪ e-business (e.g. Amazon) ▪ content-servers (e.g., YouTube, Akamai, Apple, Microsoft) ▪ search engines, data mining (e.g., Google) challenges: ▪ multiple applications, each serving massive numbers of clients ▪ reliability ▪ managing/balancing load, avoiding processing, networking, data bottlenecks Inside a 40-ft Microsoft container, Chicago data center Link Layer: 6-90 Datacenter networks: network elements Border routers ▪ connections outside datacenter Tier-1 switches ▪ connecting to ~16 T-2s below Tier-2 switches ▪ connecting to ~16 TORs below … … … … Top of Rack (TOR) switch … … … … ▪ one per rack ▪ 100G-400G Ethernet to blades Server racks ▪ 20- 40 server blades: hosts Link Layer: 6-91 Datacenter networks: network elements Facebook F16 data center network topology: https://engineering.fb.com/data-center-engineering/f16-minipack/ (posted 3/2019) Link Layer: 6-92 Datacenter networks: multipath ▪ rich interconnection among switches, racks: increased throughput between racks (multiple routing paths possible) increased reliability via redundancy 9 10 11 12 13 14 15 16 two disjoint paths highlighted between racks 1 and 11 Link Layer: 6-93 Datacenter networks: application-layer routing Internet load balancer: application-layer routing ▪ receives external Load client requests balancer ▪ directs workload within data center … … … … ▪ returns results to external client (hiding … … … data center internals … from client) Link Layer: 6-94  Datacenter networks: protocol innovations ▪ link layer: RoCE: remote DMA (RDMA) over Converged Ethernet ▪ transport layer: ECN (explicit congestion notification) used in transport-layer congestion control (DCTCP, DCQCN) experimentation with hop-by-hop (backpressure) congestion control ▪ routing, management: SDN widely used within/among organizations’ datacenters place related services, data as close as possible (e.g., in same rack or nearby rack) to minimize tier-2, tier-1 communication Google Networking: Infrastructure and Selected Challenges (Slides: https://networkingchannel.eu/google-networking-infrastructure-and-selected-challenges/ Link Layer: 6-95 ORION: Google’s new SDN control plane for internal datacenter (Jupiter) + wide area (B4) network ▪ routing (intradomain, iBGP), traffic Orion SDN architecture and core apps engineering: implemented in applications on top of ORION core ▪ edge-edge flow-based controls (e.g., CoFlow scheduling) to meet contract SLAs ▪ management: pub-sub distributed microservices in Orion core, OpenFlow for switch signaling/monitoring Note: ▪ no routing protocols, congestion control (partially) also managed by SDN rather than by protocol ▪ are protocols dying? Network Layer Control Plane: 5-96 Link layer, LANs: roadmap ▪ introduction ▪ error detection, correction ▪ multiple access protocols ▪ LANs addressing, ARP Ethernet switches VLANs ▪ a day in the life of a web ▪ link virtualization: MPLS request ▪ data center networking Link Layer: 6-97 Synthesis: a day in the life of a web request ▪ our journey down the protocol stack is now complete! application, transport, network, link ▪ putting-it-all-together: synthesis! goal: identify, review, understand protocols (at all layers) involved in seemingly simple scenario: requesting www page scenario: student attaches laptop to campus network, requests/receives www.google.com Link Layer: 6-98 A day in the life: scenario scenario: browser DNS server ▪ arriving mobile Comcast network client attaches 68.80.0.0/13 to network … ▪ requests web school network page: 68.80.2.0/24 www.google.com web page Sounds web server Google’s network simple! 64.233.169.105 64.233.160.0/19 Link Layer: 6-99  A day in the life: connecting to the Internet DHCP DHCP DHCP UDP ▪ connecting laptop needs to get its own IP DHCP IP address, addr of first-hop router, addr of Eth arriving mobile: DHCP Phy DHCP client DNS server: use DHCP DHCP ▪ DHCP request encapsulated in UDP, DHCP DHCP encapsulated in IP, encapsulated in 802.3 UDP DHCP DHCP IP Ethernet DHCP Eth Phy router has ▪ Ethernet frame broadcast (dest: DHCP server FFFFFFFFFFFF) on LAN, received at router running DHCP server ▪ Ethernet de-muxed to IP de-muxed, UDP de-muxed to DHCP Link Layer: 6-100  A day in the life: connecting to the Internet DHCP DHCP UDP ▪ DHCP server formulates DHCP ACK DHCP DHCP IP Eth arriving mobile: containing client’s IP address, IP address DHCP Phy DHCP client of first-hop router for client, name & IP address of DNS server DHCP DHCP ▪ encapsulation at DHCP server, frame DHCP DHCP UDP IP forwarded (switch learning) through LAN, DHCP Eth demultiplexing at client DHCP Phy router has DHCP server ▪ DHCP client receives DHCP ACK reply Client now has IP address, knows name & addr of DNS server, IP address of its first-hop router Link Layer: 6-101  A day in the life… ARP (before DNS, before HTTP) DNS DNS DNS UDP ▪ before sending HTTP request, need IP address DNS ARP IP of www.google.com: DNS ARP query Eth arriving mobile: Phy ARP client ▪ DNS query created, encapsulated in UDP, encapsulated in IP, encapsulated in Eth. To send frame to router, need MAC address of router interface: ARP ARP ▪ ARP query broadcast, received by router, which ARP reply Eth Phy replies with ARP reply giving MAC address of router has router interface ARP server ▪ client now knows MAC address of first hop router, so can now send frame containing DNS query Link Layer: 6-102  A day in the life… using DNS DNS DNS ▪ de-muxed to DNS DNS DNS UDP DNS DNS UDP ▪ DNS replies to client DNS DNS IP Eth DNS IP DNS DNS Phy DNS Eth server with IP address of DNS Phy www.google.com Comcast network 68.80.0.0/13 ▪ IP datagram ▪ IP datagram forwarded from campus containing DNS query network into Comcast network, forwarded via LAN routed (tables created by RIP, OSPF, switch from client to IS-IS and/or BGP routing protocols) 1st hop router to DNS server Link Layer: 6-103  A day in the life…TCP connection carrying HTTP HTTP SYNACK SYN HTTP TCP ▪ to send HTTP request, SYNACK SYN IP client first opens TCP Eth SYNACK SYN Phy Comcast network socket to web server ▪ TCP SYN segment (step 1 in TCP 68.80.0.0/13 3-way handshake) inter-domain routed to web server ▪ web server responds with TCP SYNACK SYN SYNACK SYN IP TCP SYNACK (step 2 in TCP SYNACK SYN Eth 3-way handshake) Phy Google web server ▪ TCP connection established! 64.233.169.105 Link Layer: 6-104  A day in the life… HTTP request/reply HTTP HTTP HTTP HTTP TCP ▪ HTTP request sent into ▪ web page finally (!!!) HTTP HTTP HTTP IP TCP socket HTTP HTTP Eth displayed Phy Comcast network 68.80.0.0/13 ▪ IP datagram containing HTTP request routed to www.google.com ▪ web server responds with HTTP HTTP HTTP TCP HTTP reply (containing web HTTP IP page) HTTP Eth Phy ▪ IP datagram containing Google web server HTTP reply routed back to 64.233.169.105 client Link Layer: 6-105 Chapter 6: Summary ▪ principles behind data link layer services: error detection, correction sharing a broadcast channel: multiple access link layer addressing ▪ instantiation, implementation of various link layer technologies Ethernet switched LANS, VLANs virtualized networks as a link layer: MPLS ▪ synthesis: a day in the life of a web request Link Layer: 6-106 Chapter 6: let’s take a breath ▪ journey down protocol stack complete (except PHY) ▪ solid understanding of networking principles, practice! ▪ ….. could stop here …. but more interesting topics! wireless security Link Layer: 6-107 Additional Chapter 6 slides Network Layer: 5-108 Pure ALOHA efficiency P(success by given node) = P(node transmits) * P(no other node transmits in [t0-1,t0] * * P(no other node transmits in [t0-1,t0] = p. (1-p)N-1. (1-p)N-1 = p. (1-p)2(N-1) … choosing optimum p and then letting n = 1/(2e) =.18 even worse than slotted Aloha! Link Layer: 6-109