01_Link_layer_Chapter_6_v8.0.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 Approach Thanks and enjoy! JFK/KWR 8th edition All material copyright 1996-2020 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 and routers: nodes national or global ISP  communication channels that connect adjacent nodes along communication path: links wired wireless LANs  layer-2 packet: frame, datacenter encapsulates datagram network link layer has responsibility of transferring datagram from one node enterprise network to physically adjacent node over a link Link Layer: 6-4 Link layer: context  datagram transferred by transportation analogy: different link protocols over  trip from Princeton to Lausanne different links: limo: Princeton to JFK e.g., WiFi on first link, Ethernet plane: JFK to Geneva on next link train: Geneva to Lausanne  each link protocol provides  tourist = datagram different services  transport segment = e.g., may or may not provide communication link reliable data transfer over link  transportation mode = link-layer protocol  travel agent = routing algorithm Link Layer: 6-5 Link layer: services  framing, link access: … encapsulate datagram into frame, adding … header, trailer channel access if shared medium “MAC” addresses in frame headers identify source, destination (different from IP address!)  reliable delivery between adjacent nodes we already know how to do this! seldom used on low bit-error links wireless links: high error rates Q: why both link-level and end-end reliability? Link Layer: 6-6 Link layer: services (more)  flow control: … pacing between adjacent sending and … receiving nodes  error detection: errors caused by signal attenuation, noise. receiver detects errors, signals retransmission, or drops frame  error correction: receiver identifies and corrects bit error(s) without retransmission  half-duplex and full-duplex: with half duplex, nodes at both ends of link can transmit, but not at same time Link Layer: 6-7 Where is the link layer implemented?  in each-and-every host  link layer implemented in network interface card (NIC) or on a chip application transport cpu memory Ethernet, WiFi card or chip network link implements link, physical layer host bus (e.g., PCI)  attaches into host’s system link physical controller buses physical  combination of hardware, network interface software, firmware Link Layer: 6-8 Interfaces communicating application application transport transport cpu memory memory CPU datagram network network link link linkh datagram controller controller datagram link 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: 6-9  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-10 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: 6-11  Parity checking single bit parity: two-dimensional bit parity:  detect single bit errors  detect and correct single bit errors row parity 0111000110101011 1 d1,1... d1,j d1,j+1 d data bits d2,1... d2,j d2,j+1 parity............ bit di,1... di,j di,j+1 column parity di+1,1... Even parity: set parity di+1,j di+1,j+1 bit so there is an even number of 1’s no errors: 1 0 1 0 1 1 detected 10101 1 11110 0 and 10110 0 parity error correctable 01110 1 single-bit 01110 1 10101 0 error: 10101 0 * Check out the online interactive exercises for more parity error examples: http://gaia.cs.umass.edu/kurose_ross/interactive/ Link Layer: 6-12 Internet checksum (review) 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 Transport Layer: 3-13 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) r CRC bits d data bits D R bit pattern = D *2r XOR R formula for bit pattern goal: choose 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: 6-14  Cyclic Redundancy Check (CRC): example We want: G 1 0 1 0 1 1 D.2r XOR R = nG 1 0 0 1 1 0 1 1 1 00 0 0 or equivalently: 1 0 0 1 D.2r = nG XOR R 1 0 1 D* 2r 0 0 0 or equivalently: 1 0 1 0 1 0 0 1 if we divide D.2r by G, want 1 1 0 remainder R to satisfy: 0 0 0 D.2r 1 1 0 0 R = remainder [ ] 1 0 0 1 G 1 0 1 0 1 0 0 1 0 1 1 R * Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/ Link Layer: 6-15 CRC properties  Standard generators of 8,12,16 and 32 bits were defined  For instance, the CRC32 for several data link protocols is: GCRC-32 =100000100110000010001110110110111  CRC can detect: burst of error less than r+1 bits all odd numbers of bit errors Link Layer: 6-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-fashioned Ethernet upstream HFC in cable-based access network 802.11 wireless LAN, 4G/5G. satellite shared wire (e.g., humans at a cocktail party cabled Ethernet) shared radio: 4G/5G shared radio: WiFi shared radio: satellite (shared air, acoustical) Link Layer: 6-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: 6-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: 6-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: 6-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: 6-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 frequency bands FDM cable Link Layer: 6-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 MAC 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: 6-24 Slotted ALOHA assumptions: operation:  all frames same size  when node obtains fresh  time divided into equal size frame, transmits in next slot slots (time to transmit 1 frame) if no collision: node can send  nodes start to transmit only new frame in next slot slot beginning if collision: node retransmits  nodes are synchronized frame in each subsequent  if 2 or more nodes transmit in slot with probability p until slot, all nodes detect collision success randomization – why? Link Layer: 6-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  simple  clock synchronization Link Layer: 6-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: 6-27 Pure ALOHA  unslotted Aloha: simpler, no synchronization when frame first arrives: transmit immediately If collision, retransmit at the end of the frame, with probability P  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: 6-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: 6-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: 6-30 CSMA/CD (collision detection)  CSMA/CD: carrier sensing, deferral as in CSMA collisions detected within short time colliding transmissions aborted, reducing channel wastage  collision detection: easy in wired LANs: measure signal strengths, compare transmitted, received signals difficult in wireless LANs: received signal strength overwhelmed by local transmission strength  human analogy: the polite conversationalist Link Layer: 6-31 CSMA/CD: spatial layout of nodes  CSMA/CS reduces the amount of time wasted in collisions transmission aborted on collision detection Link Layer: 6-32 Ethernet CSMA/CD algorithm 1. NIC receives datagram from network layer, creates frame 2. NIC senses channel: if idle: start frame transmission. if busy: wait until channel idle, then transmit 3. If NIC transmits entire frame without collision, NIC is done with frame ! 4. If NIC detects another transmission while sending: abort, send jam signal 5. After aborting, NIC enters binary (exponential) backoff: after mth collision, NIC chooses K at random from {0,1,2, …, 2m-1}. NIC waits K·512 bit times, returns to Step 2 more collisions: longer backoff interval Link Layer: 6-33 CSMA/CD efficiency  Tprop = max prop delay between 2 nodes in LAN  ttrans = time to transmit max-size frame 1 efficiency  1  5t prop /ttrans  efficiency goes to 1 as tprop goes to 0 as ttrans goes to infinity  better performance than ALOHA: and simple, cheap, decentralized! Link Layer: 6-34 “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: 6-35 “Taking turns” MAC protocols polling:  master node “invites” other nodes to transmit in turn data poll  typically used with “dumb” devices master  concerns: data polling overhead latency slaves single point of failure (master) Link Layer: 6-36 “Taking turns” MAC protocols T token passing:  control token passed from one node to next sequentially. (nothing  token message to send)  concerns: T token overhead latency single point of failure (token) data Link Layer: 6-37 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-38 Cable access network: MAP frame for Interval [t1, t2] CMTS Downstream channel i 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 specificaiton  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-39 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-40 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-41  Switched network, an example  Switches operate at link layer  They switch link-layer frames and DON’T use IP addresses…  Thus DON’T use routing algorithm (OSPF, RIP…) Link Layer: 6-42 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-43 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-44 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-45 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 137.196.7.23 58-23-D7-FA-20-B0 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-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 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-47 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-48 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-49 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-50 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-51 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-52 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-53 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-54 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-55 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-56 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) Metcalfe’s Ethernet sketch https://www.uspto.gov/learning-and-resources/journeys-innovation/audio-stories/defying-doubters Link Layer: 6-57 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-58 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-59 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-60 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-61 802.3 Ethernet standards: link & physical layers  many different Ethernet standards common MAC protocol and frame format different speeds: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10 Gbps, 40 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-62 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-63 Switched network, an example Link Layer: 6-64 Ethernet switch  Switch is a link-layer device: takes an active role store, forward Ethernet 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-65 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-66 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-67 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 entry: 1 2 6  (MAC address of host, interface to reach 3 5 4 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-68 Switch: self-learning Source: A  switch learns which hosts Dest: A’ A A’ can be reached through A 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-69 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-70 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 A’ 2 on just one link 3 5 4 B’ C A’ A A’ MAC addr interface TTL A 1 60 switch table A’ 4 60 (initially empty) Link Layer: 6-71 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-72 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-73 Small institutional network mail server to external network router web server IP subnet Link Layer: 6-74 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-756-75 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-76 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-77 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-78 Port-based VLANs port-based VLAN: switch ports grouped (by switch management software) so that single physical switch …… Virtual Local Area Network (VLAN) 7 9 15 1 switch(es) supporting 2 8 10 16 … … VLAN capabilities can be configured to define EE (VLAN ports 1-8) CS (VLAN ports 9-15) 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-79 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-80 Port-based VLANs Link Layer: 6-81 Port-based VLANs Link Layer: 6-82 Port-based VLANs Link Layer: 6-83 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-84 802.1Q VLAN frame format type dest. source data (payload) CRC preamble address address 802.1 Ethernet frame type dest. source data (payload) CRC preamble address address 802.1Q frame 2-byte Tag Protocol Identifier Recomputed (value: 81-00) CRC Tag Control Information (12 bit VLAN ID field, 3 bit priority field like IP TOS) Link Layer: 6-85 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-93 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 Inside a 40-ft Microsoft container, Chicago data center bottlenecks Link Layer: 6-94 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  40-100Gbps Ethernet to blades Server racks  20- 40 server blades: hosts Link Layer: 6-95 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-96 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-97 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-98 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-100 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-101 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 simple! Google’s network 64.233.169.105 64.233.160.0/19 Link Layer: 6-102  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 arriving mobile: DHCP Eth Phy DHCP client DNS server: use DHCP DHCP  DHCP request encapsulated in UDP, DHCP DHCP encapsulated in IP, encapsulated in 802.3 DHCP DHCP UDP IP Ethernet DHCP Eth Phy router has  Ethernet frame broadcast (dest: DHCP server FFFFFFFFFFFF) on LAN, received at router running DHCP server  Ethernet demuxed to IP demuxed, UDP demuxed to DHCP Link Layer: 6-103  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 forwarded (switch learning) through LAN, IP 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-104  A day in the life… ARP (before DNS, before HTTP) DNS DNS  before sending HTTP request, need IP address DNS UDP 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-105  A day in the life… using DNS DNS DNS  demuxed to DNS DNS DNS UDP DNS DNS DNS UDP DNS IP DNS IP  DNS replies to client Eth 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-106  A day in the life…TCP connection carrying HTTP HTTP HTTP  to send HTTP request, SYNACK SYN TCP SYNACK SYN IP client first opens TCP SYNACK SYN Eth Phy Comcast network socket to web server 68.80.0.0/13  TCP SYN segment (step 1 in TCP 3-way handshake) inter- domain routed to web server  web server responds with SYNACK SYN SYNACK SYN TCP IP TCP SYNACK (step 2 in TCP 3- SYNACK SYN Eth way handshake) Phy Google web server  TCP connection established! 64.233.169.105 Link Layer: 6-107  A day in the life… HTTP request/reply HTTP HTTP HTTP HTTP HTTP TCP  HTTP request sent into HTTP HTTP IP  web page finally (!!!) TCP socket HTTP HTTP Eth displayed Phy Comcast network  IP datagram containing 68.80.0.0/13 HTTP request routed to www.google.com  web server responds with HTTP HTTP HTTP HTTP reply (containing web TCP 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-108 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-109 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-110