Quản trị mạng - Chapter 10: Link - State routing protocols

Chapter 10: Link-State Routing Protocols CCNA Exploration version 4.0 Học viện mạng Bach Khoa - Website: www.bkacad.com 2 Objectives • Describe the basic features & concepts of link-state routing protocols. • List the benefits and requirements of link-state routing protocols. Học viện mạng Bach Khoa - Website: www.bkacad.com 3 Link-State Routing Học viện mạng Bach Khoa - Website: www.bkacad.com 4 Link-State Routing Protocols • Link state routing protocols – Also known as shortest path first algorithms – Built around Dijkstra’s SPF Học viện mạng Bach Khoa - Website: www.bkacad.com 5 Introduction to the SPF Algorithm • Dikjstra’s algorithm also known as the shortest path first (SPF) algorithm. This algorithm accumulates costs along each path, from source to destination. • Each router determines its own cost to each destination in the topology. Học viện mạng Bach Khoa - Website: www.bkacad.com 6 Introduction to the SPF Algorithm Học viện mạng Bach Khoa - Website: www.bkacad.com 7 Introduction to the SPF Algorithm • The shortest path to a destination is not necessarily the path with the least number of hops Học viện mạng Bach Khoa - Website: www.bkacad.com 8 Link-State Routing Process • How routers using Link State Routing Protocols reach convergence 1. Each routers learns about its own directly connected networks. 2. Link state routers exchange hello packet to “meet” other directly connected link state routers. 3. Each router builds its own Link State Packet (LSP) which includes information about neighbors such as neighbor ID, link type, & bandwidth. 4. After the LSP is created the router floods it to all neighbors who then store the information and then forward it until all routers have the same information. 5. Once all the routers have received all the LSPs, the routers then construct a topological map of the network which is used to determine the best routes to a destination. Học viện mạng Bach Khoa - Website: www.bkacad.com 9 • Link: this is an interface on a router • Information about the state of those links is known as link- states.This information includes: – The interface's IP address and subnet mask. – The type of network, such as Ethernet (broadcast) or Serial point-to-point link. – The cost of that link. – Any neighbor routers on that link. 1.Learning about Directly Connected Network Học viện mạng Bach Khoa - Website: www.bkacad.com 10 2.Sending Hello Packets to Neighbors • Routers with link-state routing protocols use a Hello protocol to discover any neighbors on its links. A neighbor is any other router that is enabled with the same link-state routing protocol. Học viện mạng Bach Khoa - Website: www.bkacad.com 11 2.Sending Hello Packets to Neighbors Học viện mạng Bach Khoa - Website: www.bkacad.com 12 • When 2 link-state routers learn that they are neighbors, they form an adjacency. • These small Hello packets continue to be exchanged between two adjacent neighbors which serve as a "keepalive" function to monitor the state of the neighbor. • If a router stops receiving Hello packets from a neighbor, that neighbor is considered unreachable and the adjacency is broken. 2.Sending Hello Packets to Neighbors Học viện mạng Bach Khoa - Website: www.bkacad.com 13 • Each router builds its own Link State Packet (LSP). • Contents of LSP: 1. State of each directly connected link 2. Includes information about neighbors such as neighbor ID, link type, & bandwidth. 3.Building the Link-State Packet Học viện mạng Bach Khoa - Website: www.bkacad.com 14 3.Building the Link-State Packet Học viện mạng Bach Khoa - Website: www.bkacad.com 15 4.Flooding Link-State Packets to Neighbors • Each router floods the LSP to all neighbors, who then store all LSPs received in a database. • Each router floods its link-state information to all other link-state routers in the routing area. • Whenever a router receives an LSP from a neighboring router, it immediately sends that LSP out all other interfaces except the interface that received the LSP. Học viện mạng Bach Khoa - Website: www.bkacad.com 16 4.Flooding Link-State Packets to Neighbors • LSPs are sent out under the following conditions 1. During initial startup of the router or of the routing protocol process on that router 2. Whenever there is a change in the topology, including a link going down or coming up, or a neighbor adjacency being established or broken Học viện mạng Bach Khoa - Website: www.bkacad.com 17 4.Flooding Link-State Packets to Neighbors Học viện mạng Bach Khoa - Website: www.bkacad.com 18 4.Flooding Link-State Packets to Neighbors • Unlike distance vector routing protocols that must first run the Bellman-Ford algorithm to process routing updates before sending them to other routers, link-state routing protocols calculate the SPF algorithm after the flooding is complete. • As a result, link-state routing protocols reach convergence much faster than distance vector routing protocols. Học viện mạng Bach Khoa - Website: www.bkacad.com 19 5.Constructing a link state database • Each router uses the database to construct a complete map of the topology and computes the best path to each destination network. Học viện mạng Bach Khoa - Website: www.bkacad.com 20 • Each router in the topology determines the shortest path from its own perspective. 5.Constructing a link state database Học viện mạng Bach Khoa - Website: www.bkacad.com 21 5.Constructing a link state database Học viện mạng Bach Khoa - Website: www.bkacad.com 22 • Building a portion of the SPF tree: Process begins by examining R2’s LSP information R1 ignores 1st LSP: R1 already knows it’s connected to R2 Shortest Path First (SPF) Tree ignore Học viện mạng Bach Khoa - Website: www.bkacad.com 23 Shortest Path First (SPF) Tree • Building a portion of the SPF tree: R1 uses 2nd LSP Reason: R1 can create a link from R2 to R5. This information is added to R1’s SPF tree Học viện mạng Bach Khoa - Website: www.bkacad.com 24 Shortest Path First (SPF) Tree • Building a portion of the SPF tree: R1 uses 3rd LSP
Reason: R1 learns that R2 is connected to 10.5.0.0/16.
This link is added to R1’s SPF tree. Học viện mạng Bach Khoa - Website: www.bkacad.com 25 Shortest Path First (SPF) Tree • Determining the shortest path – The shortest path to a destination determined by adding the costs & finding the lowest cost Học viện mạng Bach Khoa - Website: www.bkacad.com 26 Shortest Path First (SPF) Tree • Once the SPF algorithm has determined the shortest path routes, these routes are placed in the routing table. Học viện mạng Bach Khoa - Website: www.bkacad.com 27 Implementing Link-State Routing Protocols Học viện mạng Bach Khoa - Website: www.bkacad.com 28 Routing protocol Builds Topological map Router can independently determine the shortest path to every network Convergence A periodic/ event driven routing updates Use of LSP Distance vector No No Slow Yes/Yes No Link State Yes Yes Fast No/Yes Yes Advantages of a Link-State Routing Protocol Học viện mạng Bach Khoa - Website: www.bkacad.com 29 Advantages of a Link-State Routing Protocol Học viện mạng Bach Khoa - Website: www.bkacad.com 30 • Memory requirements – Typically link state routing protocols use more memory • Processing Requirements – More CPU processing is required of link state routing protocols • Bandwidth Requirements – Initial startup of link state routing protocols can consume lots of bandwidth Requirements for using a link state routing protocol Học viện mạng Bach Khoa - Website: www.bkacad.com 31 Requirements for using a link state routing protocol • Modern LSR protocols are designed to minimize the effects on memory, CPU, and bandwidth. Multiple areas can reduce the size of the link-state databases. It limits the amount of link-state information flooding in a routing domain and send LSPs only to those routers that need them. Học viện mạng Bach Khoa - Website: www.bkacad.com 32 Requirements for using a link state routing protocol • 2 link state routing protocols used for routing IP – Open Shortest Path First (OSPF) – Intermediate System-Intermediate System (IS-IS) Multi-areas OSPF and IS-IS are discussed in CCNP Học viện mạng Bach Khoa - Website: www.bkacad.com 33 Summary Học viện mạng Bach Khoa - Website: www.bkacad.com 34