CSC358 Week 9 - Cs.toronto.edu
CSC358 Week 9Adapted from slides by J.F. Kurose and K. W. Ross.All material copyright 1996-2016 J.F Kurose and K.W. Ross, All Rights Reserved
Logistics§ A3 outNetwork Layer4-2
Outline5.1 introduction5.2 routing protocols§ link state§ distance vector5.3 intra-AS routing inthe Internet: OSPF5.4 routing among the ISPs:BGP5.5 The SDN control plane5.6 ICMP: The InternetControl MessageProtocolNetwork Layer: Control Plane 5-3
Making routing scalableour routing study thus far - idealized§ all routers identical§ network flat not true in practicescale: with billions ofdestinations:§ can t store alldestinations in routingtables!§ routing table exchangewould swamp links!administrative autonomy§ internet network ofnetworks§ each network admin maywant to control routing inits own networkNetwork Layer: Control Plane 5-4
Internet approach to scalable routingaggregate routers into regions known as autonomoussystems (AS) (a.k.a. “domains”)intra-AS routing§ routing among hosts, routersin same AS (“network”)§ all routers in AS must runsame intra-domain protocol§ routers in different AS can rundifferent intra-domain routingprotocol§ gateway router: at “edge” ofits own AS, has link(s) torouter(s) in other AS’esinter-AS routing§ routing among AS’es§ gateways perform interdomain routing (as wellas intra-domain routing)Network Layer: Control Plane 5-5
Interconnected ASes3c3a3bAS32a1c1a1d2cAS21b mForwardingtable2b§ forwarding tableconfigured by both intraand inter-AS routingalgorithm intra-AS routingdetermine entries fordestinations within AS inter-AS & intra-ASdetermine entries forexternal destinationsNetwork Layer: Control Plane 5-6
Inter-AS tasks§ suppose router in AS1receives datagramdestined outside of AS1: router should forwardpacket to gatewayrouter, but which one?AS1 must:1. learn which dests arereachable through AS2,which through AS32. propagate thisreachability info to allrouters in AS1job of inter-AS ernetworksAS2Network Layer: Control Plane 5-7
Intra-AS Routing§ also known as interior gateway protocols (IGP)§ most common intra-AS routing protocols: RIP: Routing Information Protocol OSPF: Open Shortest Path First (IS-IS protocolessentially same as OSPF) IGRP: Interior Gateway Routing Protocol(Cisco proprietary for decades, until 2016)Network Layer: Control Plane 5-8
OSPF (Open Shortest Path First)§ open : publicly available§ uses link-state algorithm link state packet dissemination topology map at each node route computation using Dijkstra s algorithm§ router floods OSPF link-state advertisements to allother routers in entire AS carried in OSPF messages directly over IP (rather thanTCP or UDP link state: for each attached linkNetwork Layer: Control Plane 5-9
OSPF advanced features§ security: all OSPF messages authenticated (to preventmalicious intrusion)§ multiple same-cost paths allowed (only one path inRIP)§ for each link, multiple cost metrics for different ToS(e.g., satellite link cost set low for best effort ToS;high for real-time ToS)§ integrated uni- and multi-cast support: Multicast OSPF (MOSPF) uses same topology database as OSPF§ hierarchical OSPF in large domains.Network Layer: Control Plane 5-10
Outline5.1 introduction5.2 routing protocols§ link state§ distance vector5.3 intra-AS routing in theInternet: OSPF5.4 routing among theISPs: BGP5.5 The SDN control plane5.6 ICMP: The InternetControl MessageProtocolNetwork Layer: Control Plane 5-11
Internet inter-AS routing: BGP§ BGP (Border Gateway Protocol): the de factointer-domain routing protocol glue that holds the Internet together§ BGP provides each AS a means to: eBGP: obtain subnet reachability information fromneighboring ASes iBGP: propagate reachability information to all ASinternal routers. determine good routes to other networks based onreachability information and policy§ allows subnet to advertise its existence to rest ofInternet: I am hereNetwork Layer: Control Plane 5-12
eBGP, iBGP connections2b2a1b1a1c2dAS 21dAS 11c2c eBGP connectivityiBGP connectivity3b 3a3c3dAS 3gateway routers run both eBGP and iBGP protocolsNetwork Layer: Control Plane 5-13
BGP basics§ BGP session: two BGP routers ( peers ) exchange BGPmessages over semi-permanent TCP connection: advertising paths to different destination network prefixes(BGP is a path vector protocol)§ when AS3 gateway router 3a advertises path AS3,X to AS2gateway router 2c: AS3 promises to AS2 it will forward datagrams towards XAS 1AS 31b1a3b3a1cAS 21d2b2a3d2c2d3cXBGP advertisement:AS3, XNetwork Layer: Control Plane 5-14
Path attributes and BGP routes§ advertised prefix includes BGP attributes prefix attributes route§ two important attributes: AS-PATH: list of ASes through which prefix advertisementhas passed NEXT-HOP: indicates specific internal-AS router to nexthop AS§ Policy-based routing: gateway receiving route advertisement uses import policy toaccept/decline path (e.g., never route through AS Y). AS policy also determines whether to advertise path toother other neighboring ASesNetwork Layer: Control Plane 5-15
BGP path S3,X3dX2c2d§ AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3router 3a§ Based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates(via iBGP) to all AS2 routers§ Based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2,AS3, X to AS1 router 1cNetwork Layer: Control Plane 5-16
BGP path 2a3cAS3,X3dX2c2dgateway router may learn about multiple paths to destination:§ AS1 gateway router 1c learns path AS2,AS3,X from 2a§ AS1 gateway router 1c learns path AS3,X from 3a§ Based on policy, AS1 gateway router 1c chooses path AS3,X, andadvertises path within AS1 via iBGPNetwork Layer: Control Plane 5-17
BGP messages§ BGP messages exchanged between peers over TCPconnection§ BGP messages: OPEN: opens TCP connection to remote BGP peer andauthenticates sending BGP peer UPDATE: advertises new path (or withdraws old) KEEPALIVE: keeps connection alive in absence ofUPDATES; also ACKs OPEN request NOTIFICATION: reports errors in previous msg; alsoused to close connectionNetwork Layer: Control Plane 5-18
BGP, OSPF, forwarding table entriesQ: how does router set forwarding table entry to distant prefix?AS11b11a2AS3,XAS3,X3b3a1clocal linkinterfaces 2 1d 1at 1a, 1dAS2,AS3,XAS3AS22b2a3cAS3,XX3d2cphysical link2ddest interface X1 § recall: 1a, 1b, 1c learn about dest X via iBGPfrom 1c: “path to X goes through 1c”§ 1d: OSPF intra-domain routing: to get to 1c,forward over outgoing local interface 1Network Layer: Control Plane 5-19
BGP, OSPF, forwarding table entriesQ: how does router set forwarding table entry to distant prefix?AS1AS31b11a3a1c23bAS21d2b2a3c3dX2c2ddest interface X2 § recall: 1a, 1b, 1c learn about dest X via iBGPfrom 1c: “path to X goes through 1c”§ 1d: OSPF intra-domain routing: to get to 1c,forward over outgoing local interface 1§ 1a: OSPF intra-domain routing: to get to 1c,forward over outgoing local interface 2Network Layer: Control Plane 5-20
BGP route selection§ router may learn about more than one route todestination AS, selects route based on:1.2.3.4.local preference value attribute: policy decisionshortest AS-PATHclosest NEXT-HOP router: hot potato routingadditional criteriaNetwork Layer: Control Plane 5-21
Hot Potato 2d1123c3dXAS3,X2cOSPF link weights§ 2d learns (via iBGP) it can route to X via 2a or 2c§ hot potato routing: choose local gateway that has least intradomain cost (e.g., 2d chooses 2a, even though more AS hopsto X): don’t worry about inter-domain cost!Network Layer: Control Plane 5-22
BGP: achieving policy via twork:CYSuppose an ISP only wants to route traffic to/from its customernetworks (does not want to carry transit traffic between other ISPs)§ A advertises path Aw to B and to C§ B chooses not to advertise BAw to C:§ B gets no revenue for routing CBAw, since none of C, A, w are B scustomers§ C does not learn about CBAw path§ C will route CAw (not using B) to get to wNetwork Layer: Control Plane 5-23
Why different Intra-, Inter-AS routing ?policy:§ inter-AS: admin wants control over how its trafficrouted, who routes through its net.§ intra-AS: single admin, so no policy decisions neededscale:§ hierarchical routing saves table size, reduced updatetrafficperformance:§ intra-AS: can focus on performance§ inter-AS: policy may dominate over performanceNetwork Layer: Control Plane 5-24
Outline5.1 introduction5.2 routing protocols§ link state§ distance vector5.3 intra-AS routing in theInternet: OSPF5.4 routing among the ISPs:BGP5.5 The SDN controlplane5.6 ICMP: The InternetControl MessageProtocolNetwork Layer: Control Plane 5-25
Software defined networking (SDN)§ Internet network layer: historically has beenimplemented via distributed, per-router approach monolithic router contains switching hardware, runsproprietary implementation of Internet standardprotocols (IP, RIP, IS-IS, OSPF, BGP) in proprietaryrouter OS (e.g., Cisco IOS) different “middleboxes” for different network layerfunctions: firewalls, load balancers, NAT boxes, .§ 2005: renewed interest in rethinking networkcontrol planeNetwork Layer: Control Plane 5-26
Recall: per-router control planeIndividual routing algorithm components in each and everyrouter interact with each other in control plane to computeforwarding tables4.1 OVERVIEW OF NETWORK LAYERRoutingAlgorithmRouting algorithmControl plane309controlplaneData planeLocal aplaneValues in arrivingpacket’s header111013Figure 4.2 2Routing algorithms determine values in forward tablesNetwork Layer: Control Plane 5-27
Recall: logically centralized control planeA distinct (typically remote) controller interacts with localcontrol agents (CAs) in routers to compute forwarding tablesRemote ControllercontrolplanedataplaneCACACACACANetwork Layer: Control Plane 5-28
Software defined networking (SDN)Why a logically centralized control plane?§ easier network management: avoid routermisconfigurations, greater flexibility of traffic flows§ flow-based forwarding, allows “programming”routers centralized “programming” easier: compute tablescentrally and distribute distributed “programming”: more difficult: computetables as result of distributed algorithm (protocol)implemented in each and every router§ open (non-proprietary) implementation of controlplaneNetwork Layer: Control Plane 5-29
Traffic engineering: difficult traditional routing52vu321xw3151yz2Q: what if network operator wants u-to-z traffic to flow alonguvwz, x-to-z traffic to flow xwyz?A: need to define link weights so traffic routing algorithmcomputes routes accordingly (or need a new routing algorithm)!Link weights are only control “knobs”: wrong!Network Layer: Control Plane 5-30
Traffic engineering: difficult52vu321xw3151yz2Q: what if network operator wants to split u-to-ztraffic along uvwz and uxyz (load balancing)?A: can’t do it (or need a new routing algorithm)Network Layer: Control Plane 5-31
Traffic engineering: difficultNetworking 401523vv2u1xxwwzz1315yy2Q: what if w wants to route blue and red trafficdifferently?A: can’t do it (with destination based forwarding, and LS,DV routing)Network Layer: Control Plane 5-32
Read Textbook Chapter 5.5 for more details aboutSDN.
Outline5.1 introduction5.2 routing protocols§ link state§ distance vector5.3 intra-AS routing in theInternet: OSPF5.4 routing among the ISPs:BGP5.5 The SDN control plane5.6 ICMP: The InternetControl MessageProtocolNetwork Layer: Control Plane 5-34
ICMP: internet control message protocol§ used by hosts & routersto communicate networklevel information error reporting:unreachable host, network,port, protocol echo request/reply (used byping)§ network-layer above IP: ICMP msgs carried in IPdatagrams§ ICMP message: type, codeplus first 8 bytes of IPdatagram causing ionecho reply (ping)dest. network unreachabledest host unreachabledest protocol unreachabledest port unreachabledest network unknowndest host unknownsource quench (congestioncontrol - not used)echo request (ping)route advertisementrouter discoveryTTL expiredbad IP headerNetwork Layer: Control Plane 5-35
Traceroute and ICMP§ source sends series ofUDP segments todestination first set has TTL 1 second set has TTL 2, etc. unlikely port number§ when datagram in nth setarrives to nth router: router discards datagram andsends source ICMP message(type 11, code 0, TTL expired) ICMP message include nameof router & IP address3 probes§ when ICMP messagearrives, source recordsRTTsstopping criteria:§ UDP segment eventuallyarrives at destination host§ destination returns ICMPport unreachablemessage (type 3, code 3)§ source stops3 probes3 probesNetwork Layer: Control Plane 5-36
Summary: Network Layer Control Planewe’ve learned a lot!§ approaches to network control plane per-router control (traditional) logically centralized control (software defined networking)§ traditional routing algorithms link state algorithm, distance vector algorithms implementation in Internet: OSPF, BGP§ SDN controllers§ Internet Control Message Protocol§ network managementnext stop: link layer!Network Layer: Control Plane 5-37
Going deeper: Link Layer4-38
Link layer and LANsour goals:§ understand principles behind link layerservices: error detection, correctionsharing a broadcast channel: multiple accesslink layer addressinglocal area networks: Ethernet, VLANs§ instantiation, implementation of various linklayer technologiesLink Layer and LANs 6-39
Link layer: Outline6.1 introduction, services 6.5 link virtualization:MPLS6.2 error detection,correction6.6 data centernetworking6.3 multiple accessprotocols6.7 a day in the life of aweb request6.4 LANs addressing, ARPEthernetswitchesVLANSLink Layer and LANs 6-40
Link layer: introductionterminology:§ hosts and routers: nodes§ communication channels thatconnect adjacent nodes alongcommunication path: links wired links wireless links LANs§ layer-2 packet: frame,encapsulates datagramdata-link layer has responsibility oftransferring datagram from one nodeto physically adjacent node over a linkLink Layer and LANs 6-41
Link layer: context§ datagram transferred bydifferent link protocols overdifferent links: e.g., Ethernet on first link,frame relay onintermediate links, 802.11on last link§ each link protocol providesdifferent services e.g., may or may notprovide rdt over linktransportation analogy:§ trip from Princeton to Lausanne limo: Princeton to JFK plane: JFK to Geneva train: Geneva to Lausanne§ tourist datagram§ transportation mode linklayer protocol§ travel agent routingalgorithmLink Layer and LANs 6-42
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,destination different from IP address!§ reliable delivery between adjacent nodes we learned how to do this already! seldom used on low bit-error link (fiber, some twisted pair) wireless links: high error rates Q: why both link-layer and transport-layer reliability?Link Layer and LANs 6-43
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 toretransmission§ half-duplex and full-duplex with half duplex, nodes at both ends of link can transmit, but notat same timeLink Layer and LANs 6-44
Where is the link layer implemented?§ in each and every host/node§ link layer implemented inadaptor (aka network interfacecard NIC) or on a chip Ethernet card, 802.11 card;Ethernet chipset implements link, physicallayer§ attaches into host’s systembuses§ combination of hardware,software, ntrollerlinkphysicalhostbus(e.g., PCI)physicaltransmissionnetwork adaptercardLink Layer and LANs 6-45
Adaptors ending hostreceiving hostdatagramframe§ sending side:§ receiving side encapsulates datagram in looks for errors, rdt,frameflow control, etc. adds error checking bits, extracts datagram, passesrdt, flow control, etc.to upper layer atreceiving sideLink Layer and LANs 6-46
Link layer, LANs: outline6.1 introduction, services 6.5 link virtualization:MPLS6.2 error detection,correction6.6 data centernetworking6.3 multiple accessprotocols6.7 a day in the life of aweb request6.4 LANs addressing, ARPEthernetswitchesVLANSLink Layer and LANs 6-47
Error detectionEDC 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 correctionotherwiseLink Layer and LANs 6-48
Parity checkingsingle bit parity:two-dimensional bit parity:§ detect single biterrors§detect and correct single bit errors00Link Layer and LANs 6-49
Internet checksum (review)goal: detect errors (e.g., flipped bits) in transmitted packet(note: used at transport layer only)sender:§ treat segment contentsas sequence of 16-bitintegers§ checksum: addition (1 scomplement sum) ofsegment contents§ sender puts checksumvalue into UDPchecksum fieldreceiver:§ compute checksum ofreceived segment§ check if computedchecksum equals checksumfield value: NO - error detected YES - no error detected.But maybe errorsnonetheless?Link Layer and LANs 6-50
Cyclic Redundancy Check (CRC)§§§§more powerful error-detection codingview data bits, D, as a binary numberchoose r 1 bit pattern (generator), Ggoal: choose r CRC bits, R, such that D,R exactly divisible by G (modulo 2) receiver knows G, divides D,R by G. If non-zero remainder:error detected! can detect burst bit errors§ widely used in practice (Ethernet, 802.11 WiFi, ATM)Link Layer and LANs 6-51
CRC exampleA xor B C ó A B xor C ó B A xor Cwant:D.2r xor R nGequivalently:D.2r “ ” R nGD.2r “-” R nG(when binary modulo 2, x y mod 2 x–y mod 2 x xor y)equivalently:if we divide D.2r by G, wantremainder R to satisfy:R remainder[D . 2r]GMore details on the math:https://www.cs.jhu.edu/ scheideler/courses/600.344 S02/CRC.htmlLink Layer and LANs 6-52
systems (AS) (a.k.a. "domains") inter-AS routing § routing among AS'es § gateways perform inter-domain routing (as well as intra-domain routing) Internet approach to scalable routing intra-AS routing § routing among hosts, routers in same AS ("network") § all routers in AS must run sameintra-domain protocol § routers in .
(prorated 13/week) week 1 & 2 156 week 3 130 week 4 117 week 5 104 week 6 91 week 7 78 week 8 65 week 9 52 week 10 39 week 11 26 week 12 13 17-WEEK SERIES* JOIN IN MEMBER PAYS (prorated 10.94/week) week 1 & 2 186.00 week 3 164.10 week 4 153.16 week 5 142.22 week 6 131.28 week 7 120.34
Week 3: Spotlight 21 Week 4 : Worksheet 22 Week 4: Spotlight 23 Week 5 : Worksheet 24 Week 5: Spotlight 25 Week 6 : Worksheet 26 Week 6: Spotlight 27 Week 7 : Worksheet 28 Week 7: Spotlight 29 Week 8 : Worksheet 30 Week 8: Spotlight 31 Week 9 : Worksheet 32 Week 9: Spotlight 33 Week 10 : Worksheet 34 Week 10: Spotlight 35 Week 11 : Worksheet 36 .
28 Solving and Graphing Inequalities 29 Function and Arrow Notation 8th Week 9th Week DECEMBER REVIEW TEST WEEK 7,8 and 9 10th Week OCTOBER 2nd Week 3rd Week REVIEW TEST WEEK 1,2 and 3 4th Week 5th Week NOVEMBER 6th Week REVIEW TEST WEEK 4,5 and 6 7th Week IMP 10TH GRADE MATH SCOPE AND SEQUENCE 1st Week
Year 4 negative numbers. digit numbers by one digit, integer Year Group Y4 Term Autumn Week 1 Week 2 Week 3 Week 4 Week 5 Week 6 Week 7 Week 8 Week 9 Week 10 Week 11 Week 12 Number – place value Count in multiples of 6, 7, 9. 25 and 1000. digits using the formal writt
WRM –Year 6 –Scheme of Learning 2.0s Week 1 Week 2 Week 3 Week 4 Week 5 Week 6 Week 7 Week 8 Week 9 Week 10 Week 11 Week 12 tumn Number: Place Value N
Toronto Music Strategy 2 The Toronto Music Sector in Numbers Invest Toronto ranks Toronto as North America's 3rd-largest music market.Toronto is home to anada's largest community of artists;2 as such, it is also unquestionably the largest music city in Canada and the centre of the country's music industry.
Toronto Downtown 475 Yonge Street, Toronto, ON M4Y 1X7 1 416-924-0611 . Courtyard Marriott Toronto Downtown 2019 Wedding Package . Courtyard Toronto Downtown 475 Yonge Street, Toronto, ON M4Y 1X7 All prices listed are in Canadian Dollars & are subject to a 15.5% taxable service charge, a taxable 1.5% administration &
MMWR Week. Week 10: 3/29-4/4 3/1-3/7 Week 11: 3/8-3/14 Week 12: 3/15-3/21 Week 13: 3/22-3/28 Week 14: Week 15: 4/5-4/11 Week 16: 4/12-4/18 Week 17: 4/19-4/25 Week 18: 4/26-5/2 Week 19: 5/
