4003-541-70/4005-741-70 Data Communications and Networks II Module 2. Network Routing -- Lecture Notes Prof. Alan Kaminsky -- Spring Quarter 2006 Rochester Institute of Technology -- Department of Computer Science Concepts Graph theoretic models of a network Link weights Path distance metrics Hop count Delay Throughput Administratively assigned   An example from Douglas Comer, Computer Networks and Internets With Internet Applications, Fourth Edition (Prentice Hall, 2004), page 212:     Routing algorithms Point-to-point routing algorithms Distance vector routing algorithm Link state routing algorithm Shortest path algorithm, a graph theoretic algorithm Broadcast routing algorithms Multicast routing algorithms   Internet routing protocols Interior gateway protocols Routing Information Protocol (RIP), uses a distance vector algorithm Open Shortest Path First (OSPF), uses a link state algorithm Exterior gateway protocols Border Gateway Protocol (BGP) Network Layer-to-Data Link Layer protocols Address Resolution Protocol (ARP) Distance Vector Routing Algorithm Used by the Internet's Routing Information Protocol (RIP) RFC 1058 (June 1988) -- "Routing Information Protocol" RFC 1388 (January 1993) -- "RIP Version 2 Carrying Additional Information" RFC 1723 (November 1994) -- "RIP Version 2 Carrying Additional Information" RFC 2453 (November 1998) -- "RIP Version 2"   See Comer, Computer Networks and Internets, Chapter 13   Comer's algorithm does not deal with topology changes due to link failures   Here is another description of the distance vector algorithm from Radia Perlman, Interconnections, Second Edition (Addison Wesley, 2000), pages 299-303.   Information maintained by each router Neighbor table Cost of the link to each directly connected neighbor Router's own distance vector Distance to each destination from this router Neighboring routers' distance vectors Distance to each destination reported by each neighboring router Forwarding table First hop for routing packets to each destination   Algorithm (quoted from Perlman):   Each router is configured with its own ID.   Each router is also configured with a number to use as the cost of each link. (Or a fixed value such as 1 is used as the cost of each link, or some sort of measurement is done to calculate a number to use as the cost.)   Each router starts with a distance vector consisting of the value "0" for itself and the value "infinity" for every other destination.   Each router transmits its distance vector to each of its neighbors whenever the information changes (as well as when a link to a neighbor first comes up and probably also periodically).   Each router saves the most recently received distance vector from each of its neighbors.   Each router calculates its own distance vector, based on minimizing the cost to each destination, by examining the cost to that destination reported by each neighbor in turn and then adding the configured cost of the link to that neighbor.   The following events cause recalculation of the distance vector.   Receipt from a neighbor of a distance vector containing different information than before.   Discovery that a link to a neighbor has gone down. In that case, the distance vector from that neighbor is discarded before the distance vector is recalculated.   The distance vector algorithm can be slow to converge to new routes after a link failure The count-to-infinity problem   For this reason, link state algorithms are now preferred over distance vector algorithms However, distance vector is simpler than link state, and there are still a lot of distance vector (RIP) routers out there   http://xkcd.com/c69.html Shortest Path Algorithms Edsger W. Dijkstra (1930-2002) in 2002 Obituaries The Manuscripts of Edsger W. Dijkstra Robert W Floyd (1936-2001) in 1976 Obituary "Robert W Floyd, In Memoriam" by Donald Knuth Dijkstra's Algorithm Finds the shortest path from one node to every other node in a graph See Comer, Computer Networks and Internets, Chapter 13 Running time = O(N2) or better, depending on how it's implemented, where N = number of nodes Storage = O(N)   Floyd's Algorithm Finds the length of the shortest path from every node to every other node in a graph On input, D is a distance matrix An NxN matrix where D[i,j] is the distance from node i to adjacent node j If node j is not adjacent to node i, then D[i,j] = infinity (The distance matrix need not be symmetric) On output, D[i,j] has been replaced by the length of the shortest path from node i to node j If there is no path from node i to node j, then D[i,j] = infinity With a simple modification, the algorithm can also compute a forwarding table for use in routing Algorithm: for i = 0 to N-1 for r = 0 to N-1 for c = 0 to N-1 D[r,c] = min (D[r,c], D[r,i] + D[i,c]) Running time = O(N3) Storage = O(N2)   Example input distance matrix (N = 10) 0 213 ∞ ∞ ∞ ∞ ∞ 248 240 ∞ 213 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ 103 137 ∞ ∞ ∞ 0 212 ∞ ∞ 188 ∞ ∞ ∞ ∞ ∞ 212 0 77 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 77 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 248 ∞ ∞ 188 ∞ ∞ ∞ 0 ∞ ∞ 240 ∞ 103 ∞ ∞ ∞ ∞ ∞ 0 43 ∞ ∞ 137 ∞ ∞ ∞ ∞ ∞ 43 0 Example output distance matrix 0 213 344 436 648 726 ∞ 248 240 284 213 0 557 649 861 939 ∞ 461 453 497 344 557 0 780 992 1069 ∞ 592 103 137 436 649 780 0 212 289 ∞ 188 677 720 648 861 992 212 0 77 ∞ 400 888 932 726 939 1069 289 77 0 ∞ 477 966 1009 ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 248 461 592 188 400 477 ∞ 0 488 532 240 453 103 677 888 966 ∞ 488 0 43 284 497 137 720 932 1009 ∞ 532 43 0 Comparison from the point of view of one router Floyd's Algorithm computes more information than necessary but is a simpler algorithm Dijkstra's Algorithm does not compute unnecessary information but is a more complicated algorithm Floyd's theoretical asymptotic running time is larger than Dijkstra's, but theory doesn't tell us the value of N where the crossover happens Ditto for storage It's not immediately obvious which one is "better" Link State Routing Algorithm Used by the Internet's Open Shortest Path First (OSPF) protocol RFC 1131 PDF (October 1989) -- "OSPF Specification" RFC 1247 (July 1991) -- "OSPF Version 2" RFC 1583 (March 1994) -- "OSPF Version 2" RFC 2178 (July 1997) -- "OSPF Version 2" RFC 2328 (April 1998) -- "OSPF Version 2"   Here is a description of the link state algorithm from Radia Perlman, Interconnections, Second Edition (Addison Wesley, 2000), pages 307-308.   Each router is responsible for meeting its neighbors and learning their names.   Each router constructs a packet known as a link state packet, or LSP, which contains a list of the names of and cost to each of its neighbors.   The LSP is somehow transmitted to all the other routers, and each router stores the most recently generated LSP from each other router.   Each router, armed now with a complete map of the topology (the information in the LSPs yields complete knowledge of the graph), computes routes to each destination.   How each step is done: Periodic "hello" messages Link costs typically configured manually; hello messages detect when neighbors come up and go down LSPs are flooded throughout the network -- the most complicated part of the whole algorithm Shortest path algorithm, typically Dijkstra's Multicast Concepts Multicast and broadcast Multicast = deliver a packet from a source to multiple (more than 1) destinations Broadcast = deliver a packet from a source to all destinations Broadcast is just an extreme case of multicast   Applications for multicasting   IP addresses for multicast groups High order bits = 1110 ("Class D" address) 228 multicast group addresses available 224.0.0.0 through 239.255.255.255   Assigning multicast group addresses 224.0.0.0 = guaranteed not to be assigned to any group 224.0.0.1 = all IP hosts and routers on the local network 224.0.0.2 = all IP routers on the local network 239.0.0.0 through 239.255.255.255 = administratively scoped RFC 2365, "Administratively Scoped IP Multicast" (July 1998) Packets sent to these addresses "do not cross configured administrative boundaries" These addresses are locally assigned and do not need to be unique across administrative boundaries Other well-known, permanent multicast group addresses are assigned by IANA (http://www.iana.org/assignments/multicast-addresses)   Contexts for multicasting Multicasting on a local area network (e.g., Ethernet) Multicasting on a wide area network (e.g., Internet) -- multicast routing Local Area Multicasting Mapping IP multicast group addresses to Ethernet group addresses IP address (binary) = 1110 xxxx xyyy yyyy yyyy yyyy yyyy yyyy MAC address (binary) = 0000 0001 0000 0000 0101 1110 0yyy yyyy yyyy yyyy yyyy yyyy 32 different IP multicast group addresses map to the same Ethernet group address   Internet Group Management Protocol (IGMP) RFC 988, "Host Extensions for IP Multicasting" (July 1986) RFC 1054, "Host Extensions for IP Multicasting" (May 1988) RFC 1112, "Host Extensions for IP Multicasting" (August 1989) RFC 2236, "Internet Group Management Protocol, Version 2" (November 1997) RFC 3376, "Internet Group Management Protocol, Version 3" (October 2002)   IGMP messages are sent from a host to the local network's gateway (router) Join -- host joins group Leave -- host leaves group   Router operation If one or more hosts have joined multicast group X, router forwards packets from the Internet for group X onto the LAN, using X's corresponding MAC address If one or more hosts have joined multicast group X, router receives packets sent to X's corresponding MAC address and forwards them onto the Internet However, most system administrators configure their routers not to do this   Host operation When host joins multicast group X, host programs its network interface to receive packets sent to X's corresponding MAC address (as well as the host's regular unicast MAC address) The network interface passes all such packets up to the IP layer The IP layer must examine the multicast group address and process the packet only if the host has joined that multicast group Even if the router does not forward multicast traffic onto the Internet, IP multicasting still works on the local network Multicast Routing Algorithms Repeated unicasting Source sends a separate copy of a packet to every destination in the multicast group   Flooding Router forwards an incoming multicast packet out every interface except the one it came in on   Reverse path forwarding Router forwards an incoming multicast packet from source S only if the packet arrived on the interface the router uses for forwarding to S Router ignores an incoming multicast packet from source S if the packet arrived on a different interface Router forwards an accepted incoming multicast packet out every interface except the one it came in on   Spanning tree A spanning tree of a graph G is a subgraph of G with all the vertices and some of the edges such that there is exactly one path from every vertex to every other vertex Dijkstra's Algorithm constructs a "minimum depth" spanning tree from the source   Spanning tree routing Construct a spanning tree of routers for the multicast group All gateway routers for hosts that have joined the group Additional intermediate routers needed to hook up the spanning tree Source-based spanning tree Core-based spanning tree Forward packets along the spanning tree If a packet reaches a "split" in the spanning tree, the router forwards multiple copies of the packet along the multiple branches   Many protocols for Internet multicast routing have been proposed, but none has gained acceptance Distance Vector Multicast Routing Protocol (DVMRP) Multicast OSPF Protocol Independent Multicast Dense Mode (PIM-DM) Protocol Independent Multicast Sparse Mode (PIM-SM) Border Gateway Multicast Protocol/Multicast Address Set Advertisement and Claim (BGMP/MASC) Multicast Source Distribution Protocol (MSDP) Most have trouble scaling up to the size of the Internet   Core Based Trees (CBT) RFC 2189, "Core Based Trees (CBT Version 2) Multicast Routing Protocol Specification" (September 1997) RFC 2201, "Core Based Trees (CBT) Multicast Routing Architecture" (September 1997) Designate one node as the core node for the multicast group Core node determined automatically based on the multicast group address (a rather complicated algorithm) A router joining the group sends a join message along the unicast path to the core node The routers that forward the join message also become part of the (core-based) spanning tree for the multicast group   Simple Multicast (SM) / Root Addressed Multicast Architecture (RAMA) T. Ballardie, R. Perlman, C. Lee, and J. Crowcroft. Simple scalable Internet multicast. UCL Research Note RN/99/21, April 1, 1999. ftp://cs.ucl.ac.uk/darpa/simple-multicast.ps.gz Radia Perlman, Interconnections, Second Edition (Addison-Wesley, 2000), pages 468-475. Root Addressed Multicast Architecture (RAMA). http://www.cs.ucl.ac.uk/research/rama/ Similar to CBT, except a multicast group is designated by an 8-byte quantity (IP address of core node + IP multicast group address) Greatly simplifies administration of multicast groups ARP Address Resolution Protocol (ARP) RFC 826, "Ethernet Address Resolution Protocol" (November 1982)   ARP operation Node A knows node B's IP address and needs to find node B's Ethernet MAC address Used in the network protocol stack to encapsulate IP datagrams in Ethernet frames Node A sends an ARP request message to the Ethernet broadcast address (FF-FF-FF-FF-FF-FF) including: Sender's (A's) IP address Sender's (A's) MAC address Target's (B's) IP address All nodes other than B receive the message, process it, and send no response Node B receives the message, processes it, and sends an ARP reply message to A's MAC address including: Sender's (B's) IP address Sender's (B's) MAC address Target's (A's) IP address Target's (A's) MAC address A caches the information about B to avoid sending an ARP request the next time Cache entries time out eventually and must be regenerated   Reverse Address Resolution Protocol (RARP) RFC 903, "A Reverse Address Resolution Protocol" (June 1984)   RARP operation Node A knows node B's Ethernet MAC address and needs to find node B's IP address Originally used for autoconfiguration before BOOTP and then DHCP came along Node A knows its own MAC address and needs to find out its own IP address from someone else Same messages as ARP, with different data filled in   Demonstrations tcpdump -i eth0 -n -x -X ether proto \\arp Transparent Bridges "Transparent Bridges." Radia Perlman, Interconnections, Second Edition (Addison-Wesley, 2000), pages 45-63. (PDF)   The learning bridge   The spanning tree algorithm Needed to handle loops in the bridge topology automatically   Each bridge has a unique ID   A bridge broadcasts configuration messages on each of its ports, containing this information: The transmitting bridge's own ID The ID of the bridge at the root of the spanning tree The cost (hops) from the transmitting bridge to the root bridge   After the algorithm converges, the following spanning tree has been established: There is one root bridge, the one with the lowest ID in the whole LAN For each LAN segment there is one designated bridge The one with the lowest cost to the root If there are ties, the one with the lowest ID Each bridge X transmits and receives only on the following ports, which constitute the spanning tree: The port leading to the root bridge Each port connected to a LAN segment for which X is the designated bridge   The spanning tree algorithm used by bridges resembles the distance vector algorithm used by routers Data Communications and Networks II 4003-541-70/4005-741-70 Spring Quarter 2006 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2006 Alan Kaminsky. All rights reserved. Last updated 15-Sep-2006. Please send comments to ark­@­cs.rit.edu.