CSC 458/2209 Computer Networks Handout # 7: The Internet Protocol, Routing and Forwarding Professor Yashar Ganjali Department of Computer Science University of Toronto [email protected] http://www.cs.toronto.edu/~yganjali Announcements Dont forget the programming assignment. Due: Friday Oct. 11th at 5pm. Take advantage of tutorials, and piazza. Dont leave it to the last minute. Problem set 1 out on Sep. 24th Friday Oct. 4th at 5 pm Submit electronically on MarkUs. File name: ps1.pdf This weeks tutorial Problem set 1 CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 2 Announcements Contd Reading for next week Chapter 4 of the textbook Midterm exam Section L0101: Thu. Oct. 17th, 1-3 PM Section L5101: Tue. Oct. 22nd, 6-8 PM Section L0201: Tue. Oct. 22nd, 1-3 PM Same room and time as the lecture For undergraduate and graduate students CSC 458/CSC 2209 Computer Networks

University of Toronto Fall 2019 3 The Story So far Layers, and protocols Link layer Interconnecting LANs Hubs, switches, and bridges The Internet Protocol IP datagram, fragmentation Naming and addressing CIDR, DNS Application Presentation Session Transport Network Data Link Physical This time Routing and forwarding CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 4 Packet Routing and Forwarding Forwarding IP datagrams Class-based vs. CIDR Routing Techniques Nave: Flooding

Distance vector: Distributed Bellman Ford Algorithm Link state: Dijkstras Shortest Path First-based Algorithm CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 5 Hop-by-Hop Packet Forwarding Each router has a forwarding table Maps destination addresses to outgoing interfaces Upon receiving a packet Inspect the destination IP address in the header Index into the table Determine the outgoing interface Forward the packet out that interface Then, the next router in the path repeats And the packet travels along the path to the destination CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 6 Inside a Router Link 1, ingress Choose Egress Link 1, egress Link 2, ingress Choose

Egress Link 2, egress Link 3, ingress Choose Egress Link 3, egress Link 4, ingress Choose Egress Link 4, egress CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 7 Inside a Router Forwarding Table Link 1, ingress Forwarding Decision Link 1, egress Link 2, ingress Choose Egress Link 2, egress Link 3, ingress

Choose Egress Link 3, egress Link 4, ingress Choose Egress Link 4, egress CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 8 Forwarding in an IP Router Lookup packet DA in forwarding table. If known, forward to correct port. If unknown, drop packet. Decrement TTL, update header Checksum. Forward packet to outgoing interface. Transmit packet onto link. Question: How is the address looked up in a real router? CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 9 Separate Table Entries Per Address If a router had a forwarding entry per IP address Match destination address of incoming packet to the forwarding-table entry to determine the outgoing interface 1.2.3.4 host

5.6.7.8 host ... 2.4.6.8 1.2.3.5 host host 5.6.7.9 host ... 2.4.6.9 host LAN 2 LAN 1 router WAN router WAN router 1.2.3.4 1.2.3.5 CSC 458/CSC 2209 Computer Networks Forwarding Table University of Toronto Fall 2019 10

Separate Entry Class-based Address If the router had an entry per class-based prefix Mixture of Class A, B, and C addresses Depends on the first couple of bits of the destination Identify the mask automatically from the address First bit of 0: class A address (/8) First two bits of 10: class B address (/16) First three bits of 110: class C address (/24) Then, look in the forwarding table for the match E.g., 1.2.3.4 maps to 1.2.3.0/24 Then, look up the entry for 1.2.3.0/24 to identify the outgoing interface CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 11 Example Class-based Addressing IP Address Space Class A Class B Class C Class A 212.17.9.4 Class B Class C D Routing Table: Exact Match 212.17.9.0 212.17.9.0

Port 4 Exact Match: There are many well-known ways to find an exact match in a table. CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 12 CIDR Makes Packet Forwarding Harder Theres no such thing as a free lunch CIDR allows efficient use of the limited address space But, CIDR makes packet forwarding much harder Forwarding table may have many matches E.g., table entries for 201.10.0.0/21 and 201.10.6.0/23 The IP address 201.10.6.17 would match both! 201.10.0.0/21 Provider 1 201.10.0.0/22 201.10.4.0/24 CSC 458/CSC 2209 Computer Networks 201.10.5.0/24 201.10.6.0/23 University of Toronto Fall 2019 Provider 2 13 Longest Prefix Match Forwarding Forwarding tables in IP routers Maps each IP prefix to next-hop link(s)

Destination-based forwarding Packet has a destination address Router identifies longest-matching prefix Cute algorithmic problem: very fast lookups CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 14 How a Router Forwards Datagrams 128.17.20.1 e.g. 128.9.16.14 => Port 2 R2 1 R1 2 3 R3 R4 Prefix Next-hop Port 65/8 128.9/16 128.9.16/20 128.9.19/24 128.9.25/24 128.9.176/20 142.12/19 128.17.16.1 128.17.14.1 128.17.14.1 128.17.10.1

128.17.14.1 128.17.20.1 128.17.16.1 3 2 2 7 2 1 3 128.17.16.1 Forwarding Table CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 15 Simplest Algorithm is Too Slow Scan the forwarding table one entry at a time See if the destination matches the entry If so, check the size of the mask for the prefix Keep track of the entry with longest-matching prefix Overhead is linear in size of the forwarding table Today, that means 400,000-500,000 entries! And, the router may have just a few nanoseconds before the next packet is arriving Need greater efficiency to keep up with line rate Better algorithms Hardware implementations CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 16 Lookup Performance Required Line

Line Rate T1 1.5Mbps 4.68 Kpps 0.78 Kpps OC3 155Mbps 480 Kpps 80 Kpps OC12 622Mbps 1.94 Mpps 323 Kpps OC48 2.5Gbps 7.81 Mpps 1.3 Mpps OC192 10 Gbps 31.25 Mpps 5.21 Mpps

CSC 458/CSC 2209 Computer Networks Pktsize=40B Pktsize=240B University of Toronto Fall 2019 17 Fast Lookups The are algorithms that are faster than linear scan Proportional to number of bits in the address We can use special hardware Content Addressable Memories (CAMs) Allows look-ups on a key rather than flat address Huge innovations in the mid-to-late 1990s After CIDR was introduced (in 1994) and longest-prefix match was a major bottleneck CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 18 Where do Forwarding Tables Come From? Routers have forwarding tables Map prefix to outgoing link(s) Entries can be statically configured E.g., map 12.34.158.0/24 to Serial0/0.1 But, this doesnt adapt To failures To new equipment To the need to balance load That is where other technologies come in Routing protocols, DHCP, and ARP

CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 19 Packet Routing and Forwarding Forwarding IP datagrams Class-based vs. CIDR Routing Techniques Nave: Flooding Distance vector: Distributed Bellman Ford Algorithm Link state: Dijkstras Shortest Path First-based Algorithm Routing is a very complex subject, and has many aspects. CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 Here, we will concentrate on the basics. 20 The Problem B A RR22 RR11 How does R1 choose a next-hop on the path towards host B? CSC 458/CSC 2209 Computer Networks

RR44 RR33 University of Toronto Fall 2019 21 What is Routing? A famous quotation from RFC 791 A name indicates what we seek. An address indicates where it is. A route indicates how we get there. -- Jon Postel CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 22 Forwarding vs. Routing Forwarding: data plane Directing a data packet to an outgoing link Individual router using a forwarding table Routing: control plane Computing paths the packets will follow Routers talking amongst themselves Individual router creating a forwarding table CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 23 Why Does Routing Matter? End-to-end performance Quality of the path affects user performance Propagation delay, throughput, and packet loss Use of network resources

Balance of the traffic over the routers and links Avoiding congestion by directing traffic to lightly- loaded links Transient disruptions during changes Failures, maintenance, and load balancing Limiting packet loss and delay during changes CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 24 Example Network Objective: Determine the route from A to B that minimizes the path cost. Examples of link cost: Distance, data rate, price, congestion/delay, A 1 R1 1 R2 R4 2 2 4 R6 3

2 R5 R3 CSC 458/CSC 2209 Computer Networks 4 2 R7 3 R8 University of Toronto Fall 2019 B 25 Example Network In this simple case, solution is clear from inspection A 1 R1 1 R2 R4 2 2 4

R6 3 2 R5 R3 CSC 458/CSC 2209 Computer Networks 4 2 R7 3 R8 University of Toronto Fall 2019 B 26 What about this Network...!? Learn more at http://www.lumeta.com CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 27 Technique 1: Nave Approach Flood! -- Routers forward packets to all ports except the ingress port. R1 Advantages: Simple

Every destination in the network is reachable. Disadvantages: Some routers receive a packet multiple times. Packets can go round in loops forever. Inefficient. CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 28 Lowest Cost Routes Objective: Find the lowest cost route from each of (R1, , R7) to R8. 1 R1 1 R2 R4 2 2 4 R6 3 2 R5 R3 CSC 458/CSC 2209 Computer Networks

4 2 R7 3 R8 University of Toronto Fall 2019 29 A Spanning Tree 1 R1 1 R2 4 R4 R6 3 2 2 R5 R3 2 R7 2 3

4 R8 The solution is a spanning tree with R8 as the root of the tree. Tree: There are no loops. Spanning: All nodes included. Well see two algorithms that build spanning trees automatically: The distributed Bellman-Ford algorithm Dijkstras shortest path first algorithm CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 30 Technique 2: Distance Vector Distributed Bellman-Ford Algorithm Define distances at each node x dx(y) = cost of least-cost path from x to y Update distances based on neighbors dx(y) = min {c(x,v) + dv(y)} over all neighbors v 2 v 3 u 1 2 1 w y

1 4 x 5 4 s CSC 458/CSC 2209 Computer Networks z t 3 du(z) = min{c(u,v) + dv(z), c(u,w) + dw(z)} University of Toronto Fall 2019 31 Distance Vector Algorithm c(x,v) = cost for direct link from x to v Node x maintains costs of direct links c(x,v) Dx(y) = estimate of least cost from x to y Node x maintains distance vector Dx = [Dx(y): y N ] Node x maintains its neighbors distance vectors For each neighbor v, x maintains Dv = [Dv(y): y N ] Each node v periodically sends Dv to its neighbors And neighbors update their own distance vectors Dx(y) minv{c(x,v) + Dv(y)} for each node y N N Over time, the distance vector Dx converges CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019

32 Distance Vector Algorithm Iterative, asynchronous: each local iteration caused by: Local link cost change Distance vector update message from neighbor Distributed: Each node notifies neighbors only when its DV changes Neighbors then notify their neighbors if necessary CSC 458/CSC 2209 Computer Networks Each node: wait for (change in local link cost or message from neighbor) recompute estimates if DV to any destination has changed, notify neighbors University of Toronto Fall 2019 33 Distance Vector Example: Step 1 Optimum 1-hop paths Table for A Dst Cst Table for B

Hop Dst Cst Hop A 0 A A 4 A B 4 B B 0 B C C

D D 3 D E 2 E E F 6 F F 1 F Table for C E 3

C 1 1 F 2 6 1 A 3 4 D B Table for D Table for E Table for F Dst Cst Hop Dst Cst Hop Dst

Cst Hop Dst Cst Hop A A A 2 A A 6 A B B

3 B B B 1 B C 0 C C 1 C C C 1 C D 1

D D 0 D D D E E E 0 E E 3

E F 1 Computer F F CSC 458/CSC 2209 Networks F 3 F F of Toronto 0 University FFall 2019 34 Distance Vector Example: Step 2 Optimum 2-hop paths Table for A Dst Cst Hop A 0 A B 4 B C 7 F D 7 B E

2 E F 5 E Table for B Dst Cst Hop A 4 A B 0 B C 2 F D 3 D E 4 F F 1 F E 3 C 1 1 F 2 6 1

A 3 4 D B Table for C Dst Cst Hop A 7 F B 2 F C 0 C D 1 D E 4 F F 1 F Table for D Dst Cst Hop A 7 B B 3 B C 1 C D

0 D E F 2 C CSC 458/CSC 2209 Computer Networks Table for E Dst Cst Hop A 2 A B 4 F C 4 F D E 0 E F 3 F Table for F Dst Cst Hop A 5 B B 1 B C 1 C

D 2 C E 3 E F 0 F University of Toronto Fall 2019 35 Distance Vector Example: Step 3 Optimum 3-hop paths Table for A Dst Cst Hop A 0 A B 4 B C 6 E D 7 B E 2 E F 5 E Table for B Dst Cst Hop A 4 A B 0

B C 2 F D 3 D E 4 F F 1 F E 3 C 1 1 F 2 6 1 A 3 4 D B Table for C Dst Cst Hop A

6 F B 2 F C 0 C D 1 D E 4 F F 1 F Table for D Dst Cst Hop A 7 B B 3 B C 1 C D 0 D E 5 C F 2 C CSC 458/CSC 2209 Computer Networks Table for E Dst Cst Hop

A 2 A B 4 F C 4 F D 5 F E 0 E F 3 F Table for F Dst Cst Hop A 5 B B 1 B C 1 C D 2 C E 3 E F 0 F University of Toronto Fall 2019 36

Bellman-Ford Algorithm Questions: How long can the algorithm take to run? How do we know that the algorithm always converges? What happens when link costs change, or when routers/links fail? Topology changes make life hard for the Bellman- Ford algorithm CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 37 A Problem with Bellman-Ford Bad news travels slowly R1 1 R2 1 R3 1 R4 Consider the calculation of distances to R4: Time 0 1 2 3

R1 R2 3,R2 2,R3 3,R2 2,R3 3,R2 4,R3 5,R2 4,R3 Counting to infinity CSC 458/CSC 2209 Computer Networks R3 1, R4 3,R2 3,R2 5,R2 R3 R4 fails University of Toronto Fall 2019 38 Counting to Infinity Problem Solutions Set infinity = some small integer (e.g. 16). Stop when count = 16. Split Horizon: Because R2 received lowest cost path from R3, it does not advertise cost to R3 Split-horizon with poison reverse: R2 advertises infinity to R3 There are many problems with (and fixes for) the Bellman-Ford algorithm.

CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 39 Technique 3: Link State Dijkstras Shortest Path First Algorithm Routers send out update messages whenever the state of an incident link changes. Called Link State Updates Based on all link state updates received each router calculates lowest cost path to all others, starting from itself. Use Dijkstras single-source shortest path algorithm Assume all updates are consistent At each step of the algorithm, router adds the next shortest (i.e. lowest-cost) path to the tree. Finds spanning tree rooted at the router. CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 40 Dijsktras Algorithm 1 Initialization: 2 S = {u} 3 for all nodes v 4 if v adjacent to u { 5 D(v) = c(u,v) 6 else D(v) = 7 8 Loop 9 find w not in S with the smallest D(w) 10 add w to S 11 update D(v) for all v adjacent to w and not in S:

12 D(v) = min{D(v), D(w) + c(w,v)} 13 until all nodes in S CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 41 Dijkstras Algorithm Example Find Routes for the Red (Leftmost) Node 2 3 2 1 1 2 5 4 1 1 1 4 1 CSC 458/CSC 2209 Computer Networks 5 3 2 3 2 3

4 1 1 1 4 5 1 4 3 2 2 3 4 1 3 2 1 4 4 5 3 University of Toronto Fall 2019 42 Dijkstras Algorithm Example

2 3 2 1 1 2 5 4 1 1 1 4 1 CSC 458/CSC 2209 Computer Networks 5 3 2 3 2 3 4 1 1 1 4 5

1 4 3 2 2 3 4 1 3 2 1 4 4 5 3 University of Toronto Fall 2019 43 Shortest-Path Tree Shortest-path tree from u 2 v 3 u 1 2 w

y 4 5 4 s CSC 458/CSC 2209 Computer Networks link 1 x 1 Forwarding table at u z t 3 v w x y z s t University of Toronto Fall 2019 (u,v) (u,w) (u,w) (u,v) (u,v) (u,w) (u,w) 44

Reliable Flooding of LSP The Link State Packet: The ID of the router that created the LSP List of directly connected neighbors, and cost Sequence number TTL Reliable Flooding Resend LSP over all links other than incident link, if the sequence number is newer. Otherwise drop it. Link State Detection: Link layer failure Loss of hello packets CSC 458/CSC 2209 Computer Networks University of Toronto Fall 2019 45 Comparison of LS and DV algorithms Message complexity LS: with n nodes, E links, O(nE) messages sent DV: exchange between neighbors only Convergence time varies Speed of Convergence LS: O(n2) algorithm requires O(nE) messages DV: convergence time varies May be routing loops Count-to-infinity problem CSC 458/CSC 2209 Computer Networks Robustness: what happens if router malfunctions? LS: Node can advertise incorrect link cost

Each node computes only its own table DV: DV node can advertise incorrect path cost Each nodes table used by others (error propagates) University of Toronto Fall 2019 46