Data link layer services ppt

Link Layer Services and data link layer services provided to network layer and link layer services in computer networks
Dr.GriffinWood Profile Pic
Dr.GriffinWood,United Kingdom,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
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 Kurose&Ross and Katz&Stoicaƒƒ 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 1-4 - 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 re-advertise the new reach info to AS2 over the 1b-to-2a 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: - AS-PATH: contains the ASs through which the advert for the prefix passed: AS 67 AS 17 - NEXT-HOP: Indicates the specific internal-AS router to next-hop AS. (There may be multiple links from current AS to next-hop-AS.) 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 AS-PATH 3. Closest NEXT-HOP 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.5-BGPnew: a simple BGP scenario A,B,C are provider networks X,W,Y are customer (of provider networks) X is dual-homed: 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.5-BGPnew: 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 Inter-AS routing ? Policy: Inter-AS: admin wants control over how its traffic routed, who routes through its net. Intra-AS: single admin, so no policy decisions needed, exception: VPN networks. Scale: hierarchical routing saves table size, reduced update traffic Performance: Intra-AS: can focus on performance Inter-AS: policy may dominate over performance 10 Mao W07Broadcast routing duplicate creation/transmission duplicate R1 duplicate R2 R2 R3 R4 R3 R4 (b) (a) Source-duplication versus in-network duplication. (a) source duplication, (b) in-network duplication 11 Mao W07ƒƒ How to get rid of duplicates? Sequence-number- 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 Spanning-tree 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 Center-based 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..... Short-term contention is loss-less - main resource (link bandwidth) is controlled by router - router deals with short-term contention by queuing packets - switch algorithms and router buffers ensure no packets are dropped due to short-term contention We have focused on long-term contention - queuing schemes (FQ, FIFO, RED, etc.) - end-to-end congestion control (TCP) 18 Mao W07ƒƒƒ What’s New in This Lecture? Short-term contention leads to loss Lecture deals with networking over shared media - long-range radio - ethernet - short-range radio Also known as “multiple-access” - 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 “Taking-turns” - Tightly coordinate shared access to avoid collisions 20 Mao W07