Chapter 6 The Link Layer and LANs 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!) Computer  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. Networking: A Top- For a revision history, see the slide note for this page. Down Approach Thanks and enjoy! JFK/KWR 8th edition Jim Kurose, Keith Ross All material copyright 1996-2023 Pearson, 2020 J.F Kurose and K.W. Ross, All Rights Reserved Link layer and LANs: our goals  understand principles  instantiation, behind link layer implementation of services: error detection, various link layer 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, datacenter network encapsulates datagram 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 Princeto Lausanne n JFK limo: Princeton to JFK plane: JFK to Geneva train: Geneva to Lausanne  tourist = datagram  transport segment = communication link  transportation mode = link- layer protocol  travel agent = routing Geneva Lausann algorithm Link Layer 6 e 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- WiFi end 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 WiFi link 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 application card (NIC) transport network cpu memory implements link, physical link host bus layer controller (e.g., PCI)  attaches into host’s system link physical physical buses  combination of hardware, network interface software, firmware Link Layer 9 Interfaces communicating application application transport transport cpu memory memory CPU datagra network network link link m linkh datagra controller controller datagra link link m physical physical m physical physical sending side: receiving side:  encapsulates datagram in  looks for errors, reliable frame data transfer, flow control,  adds error checking bits, etc. reliable data transfer, flow  extracts datagram, passes control, etc. to upper layer at receivingLink Layer 10 Link layer, LANs: roadmap  introduction  error detection, correction  multiple access protocols  LANs addressing, ARP Ethernet  a day in the life of a switches web request VLANs  link virtualization: MPLS 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 otherwise 100% reliable! all  protocol may miss bits in D’ N OK detected some errors, but ? error d data bits rarely D EDC D’ EDC’  larger EDC field yields better bit-error prone link detection and correction Link Layer 12  Parity checking Can detect and correct single bit parity: errors (without  detect single bit retransmission!) errors  two-dimensional parity: 01110001101010111 row parity detect and correct single d data d1,1... d d1,j+1 bit errors 1,j bits d2,1... d2,j d2,j+ parity bit............ 1 Even/odd parity: set parity di,1... di,j di,j+1 bit so there is an even/odd column parity... number of 1’s di+1,1 di+1,j di+1,j At receiver:  compute parity of d +1 no errors:1 0 1 0 11 detected 10101 1 received bits 1 1 1 1 00 and 10110 parity 0 error  compare with received 0 1 1 1 01 correctabl 01110 1 e parity bit – if different 1 0 1 0 10 single-bit 10101 0 than error detected error: parity error * Check out the online interactive exercises for more examples: h ttp://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 segment (including UDP received segment header fields and IP addresses) as sequence  check if computed checksum of 16-bit integers equals checksum field value:  checksum: addition not equal - error detected (one’s complement sum) equal - no error detected. But of segment content maybe errors nonetheless?  checksum value put More later …. into 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 G Sender wants to compute 1 0 10 1 1 R such that: 1 0 0 11 0 1 1 1 00 0 0 D. 2r XOR R = nG 1 0 0 1 1 0 1 D2 *r (here, r=3)... or equivalently (XOR R both 0 0 0 sides): 1 0 1 0 D. 2r = nG XOR R 1 0 0 1 1 1 0... which says: 0 0 0 if we divide D. 2r by G, we 1 1 0 0 want remainder R to 1 0 0 1 satisfy: 1 0 1 0 D.2r 1 0 0 1 R = remainder [ ] algorithm for 0 1 1 G computing R R * Check out the online interactive exercises for more examples: h ttp://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  a day in the life of a switches web request VLANs  link virtualization: MPLS 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 cabled Ethernet) party (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 multiple time 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  random access protocol specifies: two or more transmitting how to detect collisions nodes: “collision” 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  time divided into equal size send new frame in next slots (time to transmit 1 slot frame) if collision: node  nodes start to transmit only retransmits frame in slot beginning each subsequent slot  nodes are synchronized with probability p until  if 2 or more nodes transmit success randomization – why? in 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  idle slots rate of channel  nodes may be able to detect  highly decentralized: only collision in less than time to slots in nodes need to be in transmit packet sync  simple  clock synchronization 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 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 “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 random access MAC protocols active node!  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 data poll transmit in turn  typically used with “dumb” centralized devices data controller  concerns: 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 (nothing one node to next, to send) sequentially T  transmit while holding token  concerns: token overhead latency single point of failure data (token) 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) 71-65-F7-2B-08-53 137.196.7/24 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 ARP 137.196.7.78 1A-2F-BB-76-09-AD IP/MAC address mappings ARP for some LAN nodes: LAN < IP address; MAC address; TTL> 71-65-F7-2B-08-53 137.196.7.23 58-23-D7-FA-20-B0 137.196.7.14 TTL (Time To Live): time ARP 0C-C4-11-6F-E3-98 after which address 137.196.7.88 mapping will be 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 Ethernet frame (sent to FF-FF-FF-FF- 1 IP addr FF-FF) destination MAC address = FF-FF-FF- C Source MAC: 71-65-F7-2B- FF-FF-FF 08-53 all nodes ARP table Source IP: 137.196.7.23 on in A receive ARP query LAN Target IP address: IP MAC TTL TTL 137.196.7.14 addr addr 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- C 2B-08-53) Target IP address: 137.196.7.14 ARP table in A Target MAC address: 58-23-D7-FA- IP MAC TTL TTL 20-B0 addr addr 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 D address 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 MAC TTL TTL addr 137.196. addr 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 MAC dest: 49-BD-D2-C7-56-2A IP src: 111.111.111.111 frame 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 Bdestination 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. preamble address source data CRC address (payload) 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. preamble address source data CRC address (payload)  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 different Gbps, 80 Gbps 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) fiber physical layer 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 1 2 each incoming link, so: 6 3 no collisions; full duplex 5 4 each link is its own collision B’ C domain A’  switching: A-to-A’ and B-to-B’ can transmit simultaneously, without switch with six collisions 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 1 2 each incoming link, so: 6 3 no collisions; full duplex 5 4 each link is its own collision B’ C domain A’ switching: A-to-A’ and B-to-B’ can transmit simultaneously, without switch with six collisions interfaces but A-to-A’ and C to A’ can not happen (1,2,3,4,5,6) simultaneously Link Layer: 6-64 Switch forwarding table Q: how does switch know A’ reachable via interface 4, B’ A reachable via interface 5? C’ B A: each switch has a switch table, each entry: 1 2 6  (MAC address of host, interface 3 to reach host, time stamp) 5 4  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 Dest: A’ A A’ hosts can be reached A through which C’ B when frame received, interfaces 1 2 switch “learns” location of 6 sender: incoming LAN 3 5 4 segment records sender/location B’ C A’ pair 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 A unknown: flood C’ B  destination A 1 location known: selectively 6A A’ 2 send 3 5 4 on just one link 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  2000+ network border border switches  6000 wireless access points Core core  30000 active wired 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 building 10G & 1G closets Controller Controller switchingEthernet Switches vs. routers applicatio n both are store-and-forward: datagram transport frame network  routers: network-layer devices link link frame (examine network-layer physical physical headers) switch  switches: link-layer devices (examine link-layer headers) network datagram link both have forwarding tables: physical frame  routers: compute tables using routing algorithms, IP addresses applicatio  switches: learn forwarding table n transport using flooding, learning, MAC network addresses link physical 6-73 Link Layer: 6-73 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 : 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 Science EE issues Link Layer: 6-75  Virtual LANs (VLANs): motivation : 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, Science EE efficiency 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 Virtual Local switch …… Area Network 7 15 (VLAN) 1 9 switch(es) 2 8 10 16 … … supporting VLAN EE (VLAN ports 1-8) CS (VLAN ports 9-15) capabilities can be configured to … operates as multiple virtual switches define multiple virtual LANS over 15 single physical LAN 1 7 9 2 8 10 16 infrastructure. … … 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  dynamic switch port ports membership: can be dynamically assigned 1 7 9 15 among VLANs 2 8 10 16  forwarding between VLANS: … … done via routing (just as with EE (VLAN ports 1-8) CS (VLAN ports 9-15) separate switches) 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. preamble address source data CRC address (payload) 802.1 Ethernet frame type dest. source data CRC preamble address address (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 with IP source, destination addresses header 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 R6 address or other fields D IP router R4 R3 R5 IP/MPLS router A R2 R1  IP routing: path to destination determined by destination address  MPLS alone 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 RSVP-TE R6 D R4 R3 R5 modified link state flooding A 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 label label dest interface 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, Inside a 40-ft Microsoft container, Chicago data center networking, data 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 Server racks Ethernet to blades  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 1 1 1 1 1 1 1 0 1 2 3 4 5 6 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 Load external client balancer requests  directs workload … … … …  within returnsdata results center 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- 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: DNS server  arriving browser mobile client Comcast network attaches to 68.80.0.0/13 network …  requests web school network page: 68.80.2.0/24 www.google.co m 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 DHCP IP own IP address, addr of first-hop Eth arriving mobile: DHCP Phy DHCP client router, addr of DNS server: use DHCP DHCP  DHCP request encapsulated in DHCP DHCP UDP, encapsulated in IP, UDP DHCP DHCP IP encapsulated in 802.3 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 DHCP DHCP IP Eth arriving mobile: ACK containing client’s IP DHCP Phy DHCP client address, IP address of first-hop router for client, name & IP address of DNS server DHCP DHCP  encapsulation at DHCP server, DHCP DHCP UDP IP frame forwarded (switch learning) DHCP Eth through LAN, demultiplexing at Phy DHCP router has client 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  before sending HTTP request, need IP DNS UDP DNS ARP IP address 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 ARP reply Eth Phy router, which replies with ARP reply router has giving MAC address of 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 DNS DNS UDP DNS DNS  de-muxed to DNS UDP DNS IP DNS DNS IP  DNS replies to Eth DNS DNS Phy DNS Eth server client with IP Phy DNS address of www.google.com Comcast network 68.80.0.0/13  IP datagram  IP datagram forwarded from containing DNS campus network into query forwarded Comcast network, routed via LAN switch (tables created by RIP, OSPF, from client to 1st IS-IS and/or BGP routing hop router protocols) to DNS server Link Layer: 6-103  A day in the life…TCP connection carrying HTTP HTTP HTTP  to send HTTP SYNACK SYN TCP SYNACK SYN IP request, client first Eth SYNACK SYN Phy Comcast network opens TCP socket to 68.80.0.0/13 web server  TCP SYN segment (step 1 in TCP 3-way handshake) inter-domain routed to  web server responds TCP SYNACK SYN SYNACK SYN IP with TCP SYNACK (step SYNACK SYN Eth 2 in TCP 3-way handshake) Phy  TCP connection Google web server 64.233.169.105 established! Link Layer: 6-104  A day in the life… HTTP request/reply HTTP HTTP HTTP  HTTP request sent HTTP HTTP TCP HTTP HTTP IP  web page finally into TCP socket HTTP HTTP Eth (!!!) displayed Phy Comcast network  IP datagram 68.80.0.0/13 containing HTTP request routed to  www.google.com web server responds HTTP HTTP HTTP TCP with HTTP reply HTTP IP (containing web page) HTTP Eth Phy  IP datagram Google web server containing HTTP 64.233.169.105 reply routed back to 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 even worse than = = 1/(2e) slotted.18 Aloha! Link Layer: 6-109