CSCI 4550/8556 Computer NetworksIntroductionStatic Vs. Dynamic RoutingStatic RoutingStatic Routing ExampleDynamic Routing and RoutersRouting in the Global InternetAutonomous System ConceptInterior and Exterior ProtocolsIGP/ECP IllustrationOptimal Routes, Routing Metrics, and IGPsRoutes and Data TrafficThe Border Gateway Protocol (BGP-4)The Routing Information Protocol (RIP)RIP Packet FormatOpen Shortest Path First Protocol (OSPF)OSPF ExampleOSPF AreasMulticast RoutingThe IGMP ProtocolForwarding and Discovery TechniquesMulticast Data Forwarding TechniquesMulticast ProtocolsSummaryCSCI 4550/8556Computer NetworksComer, Chapter 25:Internet RoutingIntroductionWhile the transport protocols form the heart of the protocols used by applications, IP datagrams and their routing form the heart of the delivery system.Routing tables are used by routers to make decisions on how to forward or deliver datagrams.Routing tablesmust be built initially when a router is “powered up,” andmust be updated as the network changes.Static Vs. Dynamic RoutingStatic routes do not change.Dynamic routesbegin with an initial set of routesare updated with information from other computers to learn about optimal routesRoute propagation software, or just “routing software,” is started when a router begins execution.Static RoutingStatic routing isinexpensive and easy to use (no updates sent on the network)inflexible (no updates sent on the network!)used by many hosts with one network interface and one router connecting to the Internet.The routing table is usually small, containing only two entries:specific route to hosts on the network to which the host attachesdefault route to the single routerStatic Routing ExampleDynamic Routing and RoutersStatic routing can be used in routers that deal only with a limited set of routes to a set of networks that never change.But even small network topologies need dynamic routing if networks administered by two or more organizations are connected.manual routing table updates is slow and doesn’t scale.static routing can’t accommodate exceptional conditions (network interface or router failures).To handle routing changes, each router runs software thatlearns about destinations other routers can reach (using incoming information), andinforms other routers about destinations it can reach.Routing in the Global InternetThe global internet is too large for each router to maintain complete information:There are too many individual networks involved.The routing information exchange would overwhelm the networks.Instead, a two-level routing hierarchy is used.Routers and networks are divided into autonomous groups.Routers within a group exchange information.At least one router in each group exchanges summary information with other groups.The size of the groups, and the protocols routers use to exchange information, may vary between organizations.Autonomous System ConceptAutonomous System: contiguous set of networks and routers under control of one administrative authority. [For example, UNOmaha]Size and administrative authority definitions are flexible enough to accommodate disparate groups.If an organization grows, it may be convenient to divide its networks into two autonomous systems, each with its own internal routers, and each connected to an ISP, rather than using much larger routers and more network traffic related to routing.Routing traffic grows O (n 2), where n is the number of routers.Interior and Exterior ProtocolsRouters within an autonomous system use an Interior Gateway Protocol (IGP) to exchange information.There are several different IGPs available.Usually easy to install and operate.Each has its own limitations.An Exterior Gateway Protocol (EGP) is used to exchange routing information with a router in another autonomous system.More complex, but more flexible than IGPs.Summarizes routing information before passing it on.Can use policy constraints to restrict information release to the outside.IGP/ECP IllustrationIGP1 and IGP2 (different IGPs) used in the two autonomous systems for communication between routers.EGP used for exchange of routing information between the systems.Optimal Routes, Routing Metrics, and IGPsOptimal routes are selected using routing metrics comprised of two components:administrative cost – assigned manually to reflect organizational routing policieshop count – reflects actual number of routers/networks in a pathIGPs use routing metrics to find optimal routes within an autonomous system, since the routing metrics are (hopefully) consistent within the organization.EGPs do not use routing metrics, since they have no basis for comparing the metrics used by different autonomous systems.Routes and Data TrafficData traffic for a given destination flows in exactly the opposite direction of routing traffic.This is because only as a result of a router advertising a route can data arrive using that route.The Border Gateway Protocol (BGP-4)Border Gateway Protocol version 4 (BGP-4) is the most popular EGP in the Internet.Provides routes only among autonomous systems, not individual routersHas provision for policies that can restrict route disclosureClassifies systems as transit systems (agree to pass traffic) or stub systems (won’t pass traffic)Uses TCP for reliable communicationUsed by all major ISPsUsed by the routing arbiter system to maintain a distributed database of all possible destination in the Internet, with copies running on separate route serversThe Routing Information Protocol (RIP)RIP, one of the first IGP protocols used with IP, is implemented with the UNIX routed program.Is an Interior Gateway ProtocolMeasures distance in hops (1 hop to an adjacent network)Uses UDP for all routing messagesIntended for use on LANs; version 1 uses broadcast, version 2 allows multicastAllows routers to advertise a default routeUses the distance-vector routing algorithm, with route advertisements giving (destination, distance) pairs.Allows hosts to retrieve routing informationRIP’s chief advantage is simplicity.RIP Packet FormatRIP packets containAn address and subnet mask for each networkNext hop address and distance for each netAddress family (2 for IP)A command (1=request, 2=response, others obsolete)Route tags to allow entries to be groupedOpen Shortest Path First Protocol (OSPF)RIP messages contain complete lists of destinations and distances, making them large. It works well with a small number of routers but doesn’t scale well.A newer