Transcript lecture
Link Layer 2 Mozafar Bag-Mohammadi University of Ilam Spanning Tree Algorithm A Problem: loops B B3 C B5 D B2 B7 E K F B1 G H B6 B4 I J Bridges run a distributed spanning tree algorithm select which bridges actively forward developed by Radia Perlman now IEEE 802.1 specification Algorithm Overview Each bridge has unique id (e.g., B1, B2, B3) Select bridge with smallest id as root Select bridge on each LAN closest to root as designated bridge (use id to break ties) Each bridge forwards frames over each LAN for which it is the designated bridge A B B3 C B5 D B2 B7 E K F B1 G H B6 B4 I J Algorithm Details Bridges exchange configuration messages id for bridge sending the message id for what the sending bridge believes to be root bridge distance (hops) from sending bridge to root bridge Each bridge records current best configuration message for each port Initially, each bridge believes it is the root Algorithm Detail (cont) When learn not root, stop generating config messages in steady state, only root generates configuration messages When learn not designated bridge, stop forwarding config messages in steady state, only designated bridges forward config messages Root continues to periodically send config messages If any bridge does not receive config message after a period of time, it starts generating config messages claiming to be the root Broadcast and Multicast Forward all broadcast/multicast frames current practice Learn when no group members downstream Accomplished by having each member of group G send a frame to bridge multicast address with G in source field Token Ring Overview Examples 16Mbps IEEE 802.5 (based on earlier IBM ring) 100Mbps Fiber Distributed Data Interface (FDDI) Token Ring (cont) Idea Frames flow in one direction: upstream to downstream special bit pattern (token) rotates around ring must capture token before transmitting release token after done transmitting • • immediate release delayed release remove your frame when it comes back around stations get round-robin service Frame Format 8 8 48 48 Start of frame Control Dest addr Src addr 32 Body 8 CRC End of frame 24 Status Timed Token Algorithm Token Holding Time (THT) upper limit on how long a station can hold the token Token Rotation Time (TRT) how long it takes the token to traverse the ring. TRT <= ActiveNodes x THT + RingLatency Target Token Rotation Time (TTRT) agreed-upon upper bound on TRT Algorithm (cont) Each node measures TRT between successive tokens if measured-TRT > TTRT: token is late so don’t send if measured-TRT < TTRT: token is early so OK to send Two classes of traffic synchronous: can always send asynchronous: can send only if token is early Worse case: 2xTTRT between seeing token Back-to-back 2xTTRT rotations not possible Token Maintenance Lost Token no token when initializing ring bit error corrupts token pattern node holding token crashes Generating a Token (and agreeing on TTRT) execute when join ring or suspect a failure send a claim frame that includes the node’s TTRT bid when receive claim frame, update the bid and forward if your claim frame makes it all the way around the ring: • your bid was the lowest • everyone knows TTRT • you insert new token Maintenance (cont) Monitoring for a Valid Token should periodically see valid transmission (frame or token) maximum gap = ring latency + max frame < = 2.5ms set timer at 2.5ms and send claim frame if it fires Wireless LANs IEEE 802.11 Bandwidth: 1 or 2 Mbps Physical Media spread spectrum radio (2.4GHz) diffused infrared (10m) Spread Spectrum Idea spread signal over wider frequency band than required originally designed to thwart jamming Frequency Hopping transmit over random sequence of frequencies sender and receiver share… • • pseudorandom number generator seed 802.11 uses 79 x 1MHz-wide frequency bands Spread Spectrum (cont) Direct Sequence for each bit, send XOR of that bit and n random bits random sequence known to both sender and receiver called n-bit chipping code 802.11 defines an 11-bit chipping code 1 0 Data stream: 1010 1 0 Random sequence: 0100101101011001 1 0 XOR of the two: 1011101110101001 MACAW Sender transmits RequestToSend (RTS) frame Receiver replies with ClearToSend (CTS) frame Neighbors… see CTS: keep quiet see RTS but not CTS: ok to transmit Receiver sends ACK when it has frame neighbors silent until see ACK Collisions no collisions detection known when don’t receive CTS exponential backoff Collisions Avoidance Similar to Ethernet Problem: hidden and exposed nodes Hidden node Exposed node Sending node A B C D Glossary of 802.11 Wireless Terms Station (STA): A computer or device with a wireless network interface. Access Point (AP): Device used to bridge the wireless-wired boundary, or to increase distance as a wireless packet repeater. Ad Hoc Network: A temporary one made up of stations in mutual range. Infrastructure Network: One with one or more Access Points. Channel: A radio frequency band, or Infrared, used for shared communication. Basic Service Set (BSS): A set of stations communicating wirelessly on the same channel in the same area, Ad Hoc or Infrastructure. Extended Service Set (ESS): A set BSSs and wired LANs with Access Points that appear as a single logical BSS. Supporting Mobility ad hoc networking Case 2: access points (AP) Case 1: tethered each mobile node associates with an AP Distribution system AP-1 AP-3 F AP-2 A B G H C E D Overview, 802.11 Architecture ESS Existing Wired LAN AP STA BSS AP STA STA BSS STA Infrastructure Network STA Ad Hoc Network STA BSS BSS STA STA Ad Hoc Network Mobility (cont) Scanning (selecting an AP) node sends Probe frame all AP’s w/in reach reply with ProbeResponse frame node selects one AP; sends it AssociateRequest frame AP replies with AssociationResponse frame new AP informs old AP via tethered network When active: when join or move passive: AP periodically sends Beacon frame 6. Point to Point Data Link Control one sender, one receiver, one link: easier than broadcast link: no Media Access Control no need for explicit MAC addressing e.g., dialup link, ISDN line popular point-to-point Data Link Control protocols: PPP (point-to-point protocol) • Protocol choice for dialup link. Point-to-Point (serial) links Many data link connections are point-to-point serial links: Dial-in or DSL access connects hosts to access routers Routers are connected by high-speed point-to-point links Access Router Modems Dial-Up Access IP hosts and routers are connected by a serial cable Data link layer protocols for pointto-point links are simple: • Main role is encapsulation of IP datagrams • No media access control needed Router Router Router Point-to-Point Links Router Data Link Protocols for Point-to-Point links SLIP (Serial Line IP) • First protocol for sending IP datagrams over dial-up links (from 1988) • Encapsulation, not much else PPP (Point-to-Point Protocol): • • Successor to SLIP (1992), with added functionality Used for dial-in and for high-speed routers HDLC (High-Level Data Link) : • • • Widely used and influential standard (1979) Default protocol for serial links on Cisco routers Actually, PPP is based on a variant of HDLC PPP - IP encapsulation The frame format of PPP is similar to HDLC and the 802.2 LLC frame format: flag addr ctrl 7E FF 03 1 1 1 protocol data CRC flag 7E 2 <= 1500 0021 IP datagram C021 link control data 8021 network control data PPP assumes a duplex circuit Note: PPP does not use addresses Usual maximum frame size is 1500 2 1 Additional PPP functionality In addition to encapsulation, PPP supports: multiple network layer protocols (protocol multiplexing) Link configuration Link quality testing Error detection Option negotiation Address notification Authentication The above functions are supported by helper protocols: LCP PAP, CHAP NCP PPP Support protocols Link management: The link control protocol (LCP) is responsible for establishing, configuring, and negotiating a data-link connection. LCP also monitors the link quality and is used to terminate the link. Authentication: Authentication is optional. PPP supports two authentication protocols: Password Authentication Protocol (PAP) and Challenge Handshake Authentication Protocol (CHAP). Network protocol configuration: PPP has network control protocols (NCPs) for numerous network layer protocols. The IP control protocol (IPCP) negotiates IP address assignments and other parameters when IP is used as network layer.