Question? Leave a message!




Link Layer Services

Link Layer Services
Link Layer EECS 489 Computer Networks http://www.eecs.umich.edu/courses/eecs489/w07 Z. Morley Mao Wednesday Feb 14, 2007 1 Mao W07 Acknowledgement: Some slides taken from KuroseRoss and KatzStoicaƒƒ Adminstrivia Homework 2 is posted Problems from the book You can either use Turnin program or turn in the homework on paper to my office. Due date: next Tuesday 2/20 th Midterm 1 is in class on Wednesday March 7 Please let us know if you prefer to take it early Material: Chapter 14 Including half of today’s lecture You can have one sheet of notes for the midterm. 2 Mao W07ƒƒƒ BGP basics Pairs of routers (BGP peers) exchange routing info over semi permanent TCP conctns: BGP sessions Note that BGP sessions do not correspond to physical links. When AS2 advertises a prefix to AS1, AS2 is promising it will forward any datagrams destined to that prefix towards the prefix. AS2 can aggregate prefixes in its advertisement 3c 2c 3a 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 eBGP session iBGP session 3 Mao W07ƒƒƒƒ Distributing reachability info With eBGP session between 3a and 1c, AS3 sends prefix reachability info to AS1. 1c can then use iBGP do distribute this new prefix reach info to all routers in AS1 1b can then readvertise the new reach info to AS2 over the 1bto2a eBGP session When router learns about a new prefix, it creates an entry for the prefix in its forwarding table. 3c 2c 3a 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 eBGP session iBGP session 4 Mao W07ƒƒƒ Path attributes BGP routes When advertising a prefix, advert includes BGP attributes. prefix + attributes = “route” Two important attributes: ASPATH: contains the ASs through which the advert for the prefix passed: AS 67 AS 17 NEXTHOP: Indicates the specific internalAS router to nexthop AS. (There may be multiple links from current AS to nexthopAS.) When gateway router receives route advert, uses import policy to accept/decline. 5 Mao W07ƒƒ BGP route selection Router may learn about more than 1 route to some prefix. Router must select route. Elimination rules: 1. Local preference value attribute: policy decision 2. Shortest ASPATH 3. Closest NEXTHOP router: hot potato routing 4. Additional criteria 6 Mao W07ƒƒ BGP messages BGP messages exchanged using TCP. BGP messages: OPEN: opens TCP connection to peer and authenticates sender UPDATE: advertises new path (or withdraws old) KEEPALIVE keeps connection alive in absence of UPDATES; also ACKs OPEN request NOTIFICATION: reports errors in previous msg; also used to close connection 7 Mao W07BGP routing policy legend: provider B network X W A customer network: C Y Figure 4.5BGPnew: a simple BGP scenario A,B,C are provider networks X,W,Y are customer (of provider networks) X is dualhomed: attached to two networks X does not want to route from B via X to C .. so X will not advertise to B a route to C 8 Mao W07BGP routing policy (2) legend: provider B network X W A customer network: C Y Figure 4.5BGPnew: a simple BGP scenario A advertises to B the path AW B advertises to X the path BAW Should B advertise to C the path BAW No way B gets no “revenue” for routing CBAW since neither W nor C are B’s customers B wants to force C to route to w via A B wants to route only to/from its customers 9 Mao W07ƒƒƒƒƒ Why different Intra and InterAS routing Policy: InterAS: admin wants control over how its traffic routed, who routes through its net. IntraAS: single admin, so no policy decisions needed, exception: VPN networks. Scale: hierarchical routing saves table size, reduced update traffic Performance: IntraAS: can focus on performance InterAS: policy may dominate over performance 10 Mao W07Broadcast routing duplicate creation/transmission duplicate R1 duplicate R2 R2 R3 R4 R3 R4 (b) (a) Sourceduplication versus innetwork duplication. (a) source duplication, (b) innetwork duplication 11 Mao W07ƒƒ How to get rid of duplicates Sequencenumber A controlled flooding B Broadcast sequence c number Source node address D E F G Only forward if packet arrived on the link on Reverse path forwarding its own shortest unicast path back to source 12 Mao W07ƒ Spanning tree to the rescue Spanningtree broadcast A tree containing every node, no cycles A A B B c c D D F E E F G G (b) Broadcast initiated at D (a) Broadcast initiated at A Broadcast along a spanning tree 13 Mao W07ƒƒ How to construct a spanning tree A A 3 B B c c 4 2 D D F E E F 5 1 G G (a) Stepwise construction (b) Constructed spanning of spanning tree tree Centerbased construction of a spanning tree E is the center of the tree Is this a minimum spanning tree 14 Mao W07How is BGP relevant to the us 15 Mao W07Level 3 depeers with Cogent 16 Mao W07Botnet of 100,000 PCs crushed 17 Mao W07ƒƒ Up Until Now..... Shortterm contention is lossless main resource (link bandwidth) is controlled by router router deals with shortterm contention by queuing packets switch algorithms and router buffers ensure no packets are dropped due to shortterm contention We have focused on longterm contention queuing schemes (FQ, FIFO, RED, etc.) endtoend congestion control (TCP) 18 Mao W07ƒƒƒ What’s New in This Lecture Shortterm contention leads to loss Lecture deals with networking over shared media longrange radio ethernet shortrange radio Also known as “multipleaccess” don’t go through central router to get access to link instead, multiple users can access shared medium 19 Mao W07ƒƒƒ Medium Access Protocols Channel partitioning Divide channel into smaller “pieces” (e.g., time slots, frequency) Allocate a piece to node for exclusive use Random access Allow collisions “recover” from collisions “Takingturns” Tightly coordinate shared access to avoid collisions 20 Mao W07ƒƒƒ Problem in a Nutshell Shared medium If two users send at the same time, collision results in no packet being received (interference) If no users send, channel goes idle Thus, want to have only one user send at a time Want high network utilization TDMA doesn’t give high utilization Want simple distributed algorithm no fancy tokenpassing schemes that avoid collisions 21 Mao W07ƒƒƒƒ What Layer Where should shortterm contention be handled Network layer 7. application layer 6. presentation layer 5. session layer Application layer 4. transport layer 3 .network layer Link layer 2. link layer 1. physical layer 22 Mao W07ƒƒ The Data Link Layer Our goals: understand principles behind data link layer services: error detection, correction sharing a broadcast channel: multiple access link layer addressing reliable data transfer, flow control: done instantiation and implementation of various link layer technologies 23 Mao W07ƒƒƒ Link Layer: Introduction “link” Some terminology: hosts and routers are nodes communication channels that connect adjacent nodes along communication path are links wired links wireless links LANs layer2 packet is a frame, encapsulates datagram datalink layer has responsibility of transferring datagram from one node to adjacent node over a link 24 Mao W07ƒƒƒƒƒ ƒƒ Link layer: context transportation analogy Datagram transferred by trip from Princeton to Lausanne different link protocols over limo: Princeton to JFK different links: plane: JFK to Geneva e.g., Ethernet on first link, train: Geneva to Lausanne frame relay on intermediate links, 802.11 on last link tourist = datagram Each link protocol transport segment = communication link provides different services transportation mode = link layer e.g., may or may not provide protocol rdt over link travel agent = routing algorithm 25 Mao W07ƒƒ Link Layer Services Framing, link access: encapsulate datagram into frame, adding header, trailer channel access if shared 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 linklevel and endend reliability 26 Mao W07ƒƒƒƒ 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 Correction: receiver identifies and corrects bit error(s) without resorting to retransmission Halfduplex and fullduplex with half duplex, nodes at both ends of link can transmit, but not at same time 27 Mao W07ƒƒƒ ƒƒ Adaptors Communicating datagram rcving link layer protocol sending node node frame frame adapter adapter link layer implemented in receiving side “adaptor” (aka NIC) looks for errors, rdt, flow control, etc Ethernet card, PCMCI card, 802.11 card extracts datagram, passes to rcving node sending side: adapter is semiautonomous encapsulates datagram in a frame link physical layers adds error checking bits, rdt, flow control, etc. 28 Mao W07Error 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 better detection and correction 29 Mao W07Parity Checking Two Dimensional Bit Parity: Single Bit Parity: Detect and correct single bit errors Detect single bit errors 0 0 30 Mao W07ƒƒ ƒƒƒ Internet checksum Goal: detect “errors” (e.g., flipped bits) in transmitted segment (note: used at transport layer only) Receiver: Sender: compute checksum of received treat segment contents segment as sequence of 16bit integers check if computed checksum equals checksum field value: checksum: addition (1’s complement sum) of NO error detected segment contents YES no error detected. But sender puts checksum maybe errors nonetheless value into UDP More later …. checksum field 31 Mao W07ƒƒƒƒ 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 D,R exactly divisible by G (modulo 2) receiver knows G, divides D,R by G. If nonzero remainder: error detected can detect all burst errors less than r+1 bits widely used in practice (ATM) 32 Mao W07CRC Example Want: r . D 2 XOR R = nG equivalently: r . D 2 = nG XOR R equivalently: r . if we divide D 2 by G, want remainder R r . D 2 R = remainder G 33 Mao W07ƒƒ Multiple Access Links and Protocols Two types of “links”: pointtopoint PPP for dialup access pointtopoint link between Ethernet switch and host broadcast (shared wire or medium) traditional Ethernet upstream HFC 802.11 wireless LAN 34 Mao W07ƒƒƒƒ 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 outofband channel for coordination 35 Mao W07Ideal Mulitple Access Protocol Broadcast channel of rate R bps 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 36 Mao W07ƒƒƒ MAC Protocols: a 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 37 Mao W07ƒƒƒƒƒƒ 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: 6station LAN, 1,3,4 have pkt, slots 2,5,6 idle TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load. FDM (Frequency Division Multiplexing): frequency subdivided. 38 Mao W07ƒƒƒƒƒƒ ti me 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: 6station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load. FDM (Frequency Division Multiplexing): frequency subdivided. 39 Mao W07 frequency bandsƒƒƒƒ 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: slotted ALOHA ALOHA CSMA, CSMA/CD, CSMA/CA 40 Mao W07ƒƒƒ ƒƒƒƒƒ Slotted ALOHA Assumptions Operation all frames same size when node obtains fresh frame, it transmits in next time is divided into equal slot size slots, time to transmit 1 frame no collision, node can send new frame in next slot nodes start to transmit frames only at beginning if collision, node retransmits of slots frame in each subsequent slot with prob. p until nodes are synchronized success if 2 or more nodes transmit in slot, all nodes detect collision 41 Mao W07ƒƒƒƒ ƒƒƒ Slotted ALOHA Pros Cons single active node can collisions, wasting slots continuously transmit at idle slots full rate of channel nodes may be able to highly decentralized: detect collision in less only slots in nodes need than time to transmit to be in sync packet simple clock synchronization 42 Mao W07ƒƒ ƒƒƒ Slotted Aloha efficiency For max efficiency with Efficiency is the longrun N nodes, find p that fraction of successful slots maximizes when there are many nodes, N1 Np(1p) each with many frames to send For many nodes, take N1 limit of Np(1p) as N Suppose N nodes with goes to infinity, gives 1/e many frames to send, = .37 each transmits in slot with probability p prob that node 1 has At best: channel success in a slot used for useful N1 = p(1p) transmissions 37 prob that any node has of time N1 a success = Np(1p) 43 Mao W07ƒƒƒ Pure (unslotted) ALOHA unslotted Aloha: simpler, no synchronization when frame first arrives transmit immediately collision probability increases: frame sent at t collides with other frames sent in t 1,t +1 0 0 0 44 Mao W07Pure Aloha efficiency . P(success by given node) = P(node transmits) . P(no other node transmits in p 1,p 0 0 P(no other node transmits in p 1,p 0 0 N1 N1 . . = p (1p) (1p) 2(N1) . = p (1p) … choosing optimum p and then letting n infty ... = 1/(2e) = .18 Even worse 45 Mao W07ƒƒƒ Why is this better than TDMA In TDMA, you always have to wait your turn delay proportional to number of sites In Aloha, can send immediately Aloha gives much lower delays, at the price of lower utilization (as we will see) 46 Mao W07ƒƒƒ Slotted Aloha Divide time into slots Only start transmission at beginning of slots Decreases chance of “partial collisions” 47 Mao W07ƒƒ CSMA (Carrier Sense Multiple Access) CSMA: listen before transmit: If channel sensed idle: transmit entire frame If channel sensed busy, defer transmission Human analogy: don’t interrupt others 48 Mao W07CSMA collisions spatial layout of nodes collisions can still occur: propagation delay means two nodes may not hear each other’s transmission collision: entire packet transmission time wasted note: role of distance propagation delay in determining collision probability 49 Mao W07ƒƒ 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: receiver shut off while transmitting human analogy: the polite conversationalist 50 Mao W07CSMA/CD collision detection 51 Mao W07“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 52 Mao W07ƒƒƒ ƒƒ “Taking Turns” MAC protocols Token passing: Polling: control token passed from one node master node “invites” to next sequentially. slave nodes to transmit in token message turn concerns: concerns: token overhead polling overhead latency latency single point of failure (token) single point of failure (master) 53 Mao W07ƒ Summary of MAC protocols What do you do with a shared media Channel Partitioning, by time, frequency or code • Time Division, Frequency Division Random partitioning (dynamic), • ALOHA, SALOHA, 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 a central site, token passing 54 Mao W07
Website URL
Comment