計算機(jī)網(wǎng)絡(luò)理論教學(xué)資料 chapter5_z

1、Data Link Layer5-1 Computer Networking: A Top Down Approach 5th edition. Jim Kurose, Keith Ross Addison-Wesley, April 2009. Computer Networks Dr. Guifeng Zheng (鄭貴鋒) Data Link Layer5-2 Chapter 5: The Data Link Layer Our goals: understand principles behind data link layer services: error detection, c

2、orrection sharing a broadcast channel: multiple access link layer addressing reliable data transfer, flow control: done! instantiation and implementation of various link layer technologies Data Link Layer5-3 Link Layer 5.1 Introduction and services 5.2 Error detection and correction 5.3Multiple acce

3、ss protocols 5.4 Link-layer Addressing 5.5 Ethernet 5.6 Link-layer switches 5.7 PPP 5.8 Link virtualization: MPLS 5.9 A day in the life of a web request Data Link Layer5-4 Link Layer: Introduction Terminology: hosts and routers are nodes communication channels that connect adjacent nodes along commu

4、nication path are links wired links wireless links LANs layer-2 packet is a frame, encapsulates datagram data-link layer has responsibility of transferring datagram from one node to physically adjacent node over a link Data Link Layer5-5 Link layer: context datagram transferred by different link pro

5、tocols over different links: e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link each link protocol provides different services e.g., may or may not provide rdt over link transportation analogy trip from Princeton to Lausanne limo: Princeton to JFK plane: JFK to Gene

6、va train: Geneva to Lausanne tourist = datagram transport segment = communication link transportation mode = link layer protocol travel agent = routing algorithm Data Link Layer5-6 Link Layer Services framing, link access: encapsulate datagram into frame, adding header, trailer channel access if sha

7、red medium “MAC” addresses used in frame headers to identify source, dest different from IP address! reliable delivery between adjacent nodes we learned how to do this already (chapter 3)! seldom used on low bit-error link (fiber, some twisted pair) wireless links: high error rates Q: why both link-

8、level and end-end reliability? Data Link Layer5-7 Link Layer Services (more) flow control: pacing between adjacent sending and receiving nodes error detection: errors caused by signal attenuation, noise. receiver detects presence of errors: signals sender for retransmission or drops frame error corr

9、ection: receiver identifies and corrects bit error(s) without resorting to retransmission half-duplex and full-duplex with half duplex, nodes at both ends of link can transmit, but not at same time Data Link Layer5-8 Where is the link layer implemented? in each and every host link layer implemented

10、in “adaptor” (aka network interface card NIC) Ethernet card, PCMCI card, 802.11 card implements link, physical layer attaches into hosts system buses combination of hardware, software, firmware controller physical transmission cpumemory host bus (e.g., PCI) network adapter card host schematic applic

11、ation transport network link link physical Data Link Layer5-9 Adaptors Communicating sending side: encapsulates datagram in frame adds error checking bits, rdt, flow control, etc. receiving side looks for errors, rdt, flow control, etc extracts datagram, passes to upper layer at receiving side contr

12、oller controller sending hostreceiving host datagram datagram datagram frame Data Link Layer5-10 Link Layer 5.1 Introduction and services 5.2 Error detection and correction 5.3Multiple access protocols 5.4 Link-layer Addressing 5.5 Ethernet 5.6 Link-layer switches 5.7 PPP 5.8 Link virtualization: MP

13、LS 5.9 A day in the life of a web request Data Link Layer5-11 Error Detection EDC= Error Detection and Correction bits (redundancy) D = Data protected by error checking, may include header fields Error detection not 100% reliable! protocol may miss some errors, but rarely larger EDC field yields bet

14、ter detection and correction otherwise Data Link Layer5-12 Parity Checking Single Bit Parity: Detect single bit errors Two Dimensional Bit Parity: Detect and correct single bit errors 00 Data Link Layer5-13 Internet checksum (review) Sender: treat segment contents as sequence of 16-bit integers chec

15、ksum: addition (1s complement sum) of segment contents sender puts checksum value into UDP checksum field Receiver: compute checksum of received segment check if computed checksum equals checksum field value: NO - error detected YES - no error detected. But maybe errors nonetheless? Goal: detect “er

16、rors” (e.g., flipped bits) in transmitted packet (note: used at transport layer only) Data Link Layer5-14 Checksumming: Cyclic Redundancy Check view data bits, D, as a binary number choose r+1 bit pattern (generator), G goal: choose r CRC bits, R, such that exactly divisible by G (modulo 2) receiver

17、 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, ATM) Data Link Layer5-15 CRC Example Want: D.2r XOR R = nG equivalently: D.2r = nG XOR R equivalently: if we divide D.2r by G, want remainder

18、R R = remainder D.2r G Data Link Layer5-16 Link Layer 5.1 Introduction and services 5.2 Error detection and correction 5.3Multiple access protocols 5.4 Link-layer Addressing 5.5 Ethernet 5.6 Link-layer switches 5.7 PPP 5.8 Link virtualization: MPLS 5.9 A day in the life of a web request Data Link La

19、yer5-17 Multiple Access Links and Protocols Two types of “l(fā)inks”: point-to-point PPP for dial-up access point-to-point link between Ethernet switch and host broadcast (shared wire or medium) old-fashioned Ethernet upstream HFC 802.11 wireless LAN shared wire (e.g., cabled Ethernet) shared RF (e.g.,

20、802.11 WiFi) shared RF (satellite) humans at a cocktail party (shared air, acoustical) Data Link Layer5-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

21、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 Data Link Layer5-19 Ideal Multiple Access Protocol Broadcast channel of rate R bp

22、s 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 Data Link Layer5-20 MAC Protocols: a taxonomy Three broad

23、 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

24、Data Link Layer5-21 Channel Partitioning MAC protocols: TDMA TDMA: time division multiple access access to channel in rounds each station gets fixed length slot (length = pkt trans time) in each round unused slots go idle example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle 134134 6-slot frame D

25、ata Link Layer5-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 pkt, frequency bands 2,

26、5,6 idle frequency bands time FDM cable Data Link Layer5-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 t

27、o recover from collisions (e.g., via delayed retransmissions) Examples of random access MAC protocols: slotted ALOHA ALOHA CSMA, CSMA/CD, CSMA/CA Data Link Layer5-24 Slotted ALOHA Assumptions: all frames same size time divided into equal size slots (time to transmit 1 frame) nodes start to transmit

28、only slot beginning nodes are synchronized if 2 or more nodes transmit in slot, all nodes detect collision Operation: when node obtains fresh frame, transmits in next slot if no collision: node can send new frame in next slot if collision: node retransmits frame in each subsequent slot with prob. p

29、until success Data Link Layer5-25 Slotted ALOHA Pros single active node can continuously transmit at full rate of channel highly decentralized: only slots in nodes need to be in sync simple Cons collisions, wasting slots idle slots nodes may be able to detect collision in less than time to transmit

30、packet clock synchronization Data Link Layer5-26 Slotted Aloha efficiency 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 N

31、p(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 Efficiency : long-run fraction of successful slots (many nodes, all with many frames to send) At best: channel used for useful transmissions 37% of time! ! Data Link Layer5-27 Pure (unslotte

32、d) ALOHA unslotted Aloha: simpler, no synchronization when frame first arrives transmit immediately collision probability increases: frame sent at t0 collides with other frames sent in t0-1,t0+1 Data Link Layer5-28 Pure Aloha efficiency P(success by given node) = P(node transmits) . P(no other node

33、transmits in p0-1,p0 . P(no other node transmits in p0-1,p0 = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) choosing optimum p and then letting n - infty . = 1/(2e) = .18 even worse than slotted Aloha! Data Link Layer5-29 CSMA (Carrier Sense Multiple Access) CSMA: listen before transmit: If channel sens

34、ed idle: transmit entire frame If channel sensed busy, defer transmission human analogy: dont interrupt others! Data Link Layer5-30 CSMA collisions collisions can still occur: propagation delay means two nodes may not hear each others transmission collision: entire packet transmission time wasted sp

35、atial layout of nodes note: role of distance 48 bits Bit time: .1 microsec for 10 Mbps Ethernet ; for K=1023, wait time is about 50 msec Exponential Backoff: Goal: adapt retransmission attempts to estimated current load heavy load: random wait will be longer first collision: choose K from 0,1; delay

36、 is K 512 bit transmission times after second collision: choose K from 0,1,2,3 after ten collisions, choose K from 0,1,2,3,4,1023 See/interact with Java applet on AWL Web site: highly recommended ! http:/ Data Link Layer5-57 CSMA/CD efficiency tprop = max prop delay between 2 nodes in LAN ttrans = t

37、ime to transmit max-size frame efficiency goes to 1 as tprop goes to 0 as ttrans goes to infinity better performance than ALOHA: and simple, cheap, decentralized! transprop /tt efficiency 51 1 Data Link Layer5-58 802.3 Ethernet Standards: Link full duplex each link is its own collision domain switch

38、ing: A-to-A and B-to-B simultaneously, without collisions not possible with dumb hub A A B B C C switch with six interfaces (1,2,3,4,5,6) 1 2 3 4 5 6 Data Link Layer5-65 Switch Table Q: how does switch know that A reachable via interface 4, B reachable via interface 5? A: each switch has a switch ta

39、ble, each entry: (MAC address of host, interface to reach host, time stamp) looks like a routing table! Q: how are entries created, maintained in switch table? something like a routing protocol? A A B B C C switch with six interfaces (1,2,3,4,5,6) 1 2 3 4 5 6 Data Link Layer5-66 Switch: self-learnin

40、g switch learns which hosts can be reached through which interfaces when frame received, switch “l(fā)earns” location of sender: incoming LAN segment records sender/location pair in switch table A A B B C C 1 2 3 4 5 6 A A Source: A Dest: A MAC addr interface TTL Switch table (initially empty) A160 Data

41、 Link Layer5-67 Switch: frame filtering/forwarding When frame received: 1. record link associated with sending host 2. index switch table using MAC dest address 3. if entry found for destination then if dest on segment from which frame arrived then drop the frame else forward the frame on interface

42、indicated else flood forward on all but the interface on which the frame arrived Data Link Layer5-68 Self-learning, forwarding: example A A B B C C 1 2 3 4 5 6 A A Source: A Dest: A MAC addr interface TTL Switch table (initially empty) A160 A AA AA AA AA A frame destination unknown: flood A A vdesti

43、nation A location known: A460 selective send Data Link Layer5-69 Interconnecting switches switches can be connected together A B vQ: sending from A to G - how does S1 know to forward frame destined to G via S4 and S3? vA: self learning! (works exactly the same as in single- switch case!) S1 C D E F

44、S2 S4 S3 H I G Data Link Layer5-70 Self-learning multi-switch example Suppose C sends frame to I, I responds to C vQ: show switch tables and packet forwarding in S1, S2, S3, S4 A B S1 C D E F S2 S4 S3 H I G 1 2 Data Link Layer5-71 Institutional network to external network router IP subnet mail serve

45、r web server Data Link Layer5-72 Switches vs. Routers both store-and-forward devices routers: network-layer devices (examine network-layer headers) switches are link-layer devices (examine link- layer headers) routers maintain routing tables, implement routing algorithms switches maintain switch tab

46、les, implement filtering, learning algorithms application transport network link physical network link physical link physical switch datagram application transport network link physical frame frame frame datagram Data Link Layer5-73 VLANs: motivation What happens if: CS user moves office to EE, but

47、wants connect to CS switch? single broadcast domain: all layer-2 broadcast traffic (ARP, DHCP) crosses entire LAN (security/privacy, efficiency issues) each lowest level switch has only few ports in use Computer Science Electrical Engineering Computer Engineering Whats wrong with this picture? Data

48、Link Layer5-74 VLANs Port-based VLAN: switch ports grouped (by switch management software) so that single physical switch Switch(es) supporting VLAN capabilities can be configured to define multiple virtual LANS over single physical LAN infrastructure. Virtual Local Area Network 1 8 9 1610 2 7 Elect

49、rical Engineering (VLAN ports 1-8) Computer Science (VLAN ports 9-15) 15 Electrical Engineering (VLAN ports 1-8) 1 82 7 9 1610 15 Computer Science (VLAN ports 9-16) operates as multiple virtual switches Data Link Layer5-75 Port-based VLAN 1 8 9 16102 7 Electrical Engineering (VLAN ports 1-8) Compute

50、r Science (VLAN ports 9-15) 15 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 vdynamic membership: ports can be dynamically assigned among VLANs router vforwarding between VLANS: done via routing

51、(just as with separate switches) in practice vendors sell combined switches plus routers Data Link Layer5-76 VLANS spanning multiple switches trunk port: carries frames between VLANS defined over multiple physical switches frames forwarded within VLAN between switches cant be vanilla 802.1 frames (m

52、ust carry VLAN ID info) 802.1q protocol adds/removed additional header fields for frames forwarded between trunk ports 1 8 9 10 2 7 Electrical Engineering (VLAN ports 1-8) Computer Science (VLAN ports 9-15) 15 2 73 Ports 2,3,5 belong to EE VLAN Ports 4,6,7,8 belong to CS VLAN 5 46816 1 Data Link Lay

53、er5-77 Type 2-byte Tag Protocol Identifier (value: 81-00) Tag Control Information (12 bit VLAN ID field, 3 bit priority field like IP TOS) Recomputed CRC 802.1Q VLAN frame format 802.1 frame 802.1Q frame Data Link Layer5-78 Link Layer 5.1 Introduction and services 5.2 Error detection and correction

54、5.3Multiple access protocols 5.4 Link-Layer Addressing 5.5 Ethernet 5.6 Link-layer switches 5.7 PPP 5.8 Link virtualization: MPLS 5.9 A day in the life of a web request Data Link Layer5-79 Point to Point Data Link Control one sender, one receiver, one link: easier than broadcast link: no Media Acces

55、s Control no need for explicit MAC addressing e.g., dialup link, ISDN line popular point-to-point DLC protocols: PPP (point-to-point protocol) HDLC: High level data link control (Data link used to be considered “high layer” in protocol stack! Data Link Layer5-80 PPP Design Requirements RFC 1557 pack

56、et framing: encapsulation of network-layer datagram in data link frame carry network layer data of any network layer protocol (not just IP) at same time ability to demultiplex upwards bit transparency: must carry any bit pattern in the data field error detection (no correction) connection liveness:

57、detect, signal link failure to network layer network layer address negotiation: endpoint can learn/configure each others network address Data Link Layer5-81 PPP non-requirements no error correction/recovery no flow control out of order delivery OK no need to support multipoint links (e.g., polling)

58、Error recovery, flow control, data re-ordering all relegated to higher layers! Data Link Layer5-82 PPP Data Frame Flag: delimiter (framing) Address: does nothing (only one option) Control: does nothing; in the future possible multiple control fields Protocol: upper layer protocol to which frame deli

59、vered (e.g., PPP-LCP, IP, IPCP, etc) Data Link Layer5-83 PPP Data Frame info: upper layer data being carried check: cyclic redundancy check for error detection Data Link Layer5-84 Byte Stuffing “data transparency” requirement: data field must be allowed to include flag pattern Q: is received data or flag? Sender: adds (“stuffs”) extra byte after each data byte Receiver: two 01111110 bytes in a row: discard first byte, continue data reception single 01111110: flag byte Data Link Layer5-85 Byte Stuffing flag byte pattern in data to send flag byte pattern plus stuffed byte in transmitted data Da