EITF45 övning 4 (FL7) Routing uppgifter med lösningar.pdf

# Flooding in network routing Flooding is a routing technique where a packet is sent to all available router ports and is only terminated when its Time To Live (TTL) expires [2](#page=2). ### 1.1 Mechanism of flooding When a packet is transmitted using flooding, it is sent out from a router to all its connected neighbors, except for the neighbor from which the packet was received. This process continues as the packet propagates through the network, with each router forwarding the packet to all its other ports [2](#page=2). ### 1.2 Time To Live (TTL) and packet termination To prevent packets from circulating indefinitely in the network, a hop count or Time To Live (TTL) mechanism is employed [2](#page=2). * As a packet leaves a router, its TTL value is decremented by one. This decrement includes the originating router [2](#page=2). * When a packet's TTL reaches zero, it is discarded and no longer propagated through the network. This ensures that flooding eventually terminates [3](#page=3). ### 1.3 Packet propagation illustration The propagation of flooded packets can be visualized by tracking their spread and the decreasing TTL values. Packets can be distinguished by the "color" of their original source branch, with numbers indicating the current TTL value [2](#page=2) [4](#page=4). #### 1.3.1 Example of flooding with a hop limit Consider a network where a packet is sent from a source node with a hop count (TTL) of 3 [2](#page=2). * **Hop 1:** The initial packet is sent from the source with TTL=3. It is then forwarded to neighboring routers, each decrementing the TTL to 2 [2](#page=2). * **Hop 2:** Routers receive packets with TTL=2 and forward them to their other neighbors, decrementing the TTL to 1 [2](#page=2). * **Hop 3:** Routers receive packets with TTL=1 and forward them, decrementing the TTL to 0. Packets with TTL=0 are discarded [2](#page=2). This sequential spreading illustrates how the hop limit controls the reach of the flooded packets [2](#page=2) [3](#page=3). > **Example:** In a network, to ensure a packet reaches destination E from source A, the minimum TTL required is 3 hops. This is because the shortest path from A to E involves traversing at least three routers (e.g., A -> B -> D -> E) [4](#page=4). #### 1.3.2 Calculating the total number of packets When flooding with a hop limit is used, the total number of packets generated can be significant. This count includes the initial packet and all subsequent copies forwarded by routers until their TTL expires [4](#page=4). > **Example:** In a scenario where a packet needs to reach destination E, and the hop limit is set to 3, the total number of packets generated throughout the network can be 14. This count accounts for the initial packet and all its replicated versions that are transmitted before their TTL reaches zero [4](#page=4). --- # Distance vector routing protocols Distance vector routing protocols are a fundamental class of routing protocols where routers maintain routing tables containing distance (or cost) and vector (or next hop) information to reach various network destinations. Routers using this method share their entire routing tables with their directly connected neighbors periodically. This information is then used by each router to update its own routing table by comparing its current knowledge with that received from neighbors [5](#page=5) [9](#page=9). ### 2.1 Core principles of distance vector routing In distance vector routing, each router knows how to reach a network by identifying which next node to send a packet to, ultimately reaching that network. Routers are aware of the networks they are directly connected to and periodically share this information with their neighbors. When a router receives an update message from a neighbor, it increments the hop count for each destination in the neighbor's table by one, as it takes one hop to reach that neighbor. The router then compares these updated distances with its own current routing table. If a path through the neighbor offers a shorter distance (fewer hops) to a destination, the router updates its table with the new, shorter path, indicating the neighbor as the next hop. If the new path is longer, the existing entry is retained [5](#page=5) [9](#page=9). > **Tip:** The core idea is "routing by rumor." Routers learn about the network topology indirectly from their neighbors rather than having a global view of the entire network [9](#page=9). ### 2.2 Routing table updates and convergence The process of updating routing tables involves receiving information from neighbors, calculating new path costs, and comparing them with existing entries. #### 2.2.1 Example: Updating a routing table Consider router X, which has the following routing table: | Network ID | Hops | Router | | :----------- | :--- | :----- | | Net 2 | 6 | A | | Net 3 | 4 | C | | Net 4 | 3 | A | | Net 6 | 2 | C | | Net 7 | 3 | B | Router X receives an update message from its neighbor, router C, with the following information: | Network ID | Hops | | :--------- | :--- | | Net 2 | 6 | | Net 3 | 4 | | Net 4 | 1 | | Net 6 | 2 | | Net 7 | 3 | To update its table, router X adds one hop to each entry from router C's table, as it takes one hop to reach C: * Net 2: C reports 6 hops. Via C, X would need $6 + 1 = 7$ hops. X's current table shows 6 hops. X keeps the old value [5](#page=5). * Net 3: C reports 4 hops. Via C, X would need $4 + 1 = 5$ hops. X's current table shows 4 hops. X updates its value to 5 hops, with C as the next node [5](#page=5). * Net 4: C reports 1 hop. Via C, X would need $1 + 1 = 2$ hops. X's current table shows 3 hops. X updates its value to 2 hops, with C as the next node [5](#page=5). * Net 6: C reports 2 hops. Via C, X would need $2 + 1 = 3$ hops. X's current table shows 2 hops. X updates its value to 3 hops, with C as the next node [5](#page=5). * Net 7: C reports 3 hops. Via C, X would need $3 + 1 = 4$ hops. X's current table shows 3 hops. X keeps the old value [5](#page=5). The updated routing table for router X would be: | Network ID | Hops | Router | Description | | :--------- | :--- | :----- | :------------------------------------------- | | Net 2 | 6 | A | To Net2 via C requires 7 hops. Keep old value. | | Net 3 | 5 | C | Number of hops increased. Update value. | | Net 4 | 2 | C | To Net4 via C requires 2 hops. Update value. | | Net 6 | 3 | C | Number of hops increased. Update value. | | Net 7 | 3 | B | To Net7 via C requires 4 hops. Keep old value. | #### 2.2.2 Network convergence Convergence in distance vector routing refers to the state where all routers in the network have consistent and accurate routing information, and they have stabilized their routing tables. This process can take time, as information propagates hop by hop through the network. During convergence, routers may exchange multiple updates as they learn about new paths or changes in the network topology [8](#page=8). > **Tip:** Distance vector protocols are susceptible to slow convergence and issues like count-to-infinity problems if not properly managed with mechanisms like split horizon and poison reverse, although these are not detailed in the provided text. ### 2.3 Initial vs. final routing tables At the beginning of network operation, or after a topology change, routers have initial routing tables. These tables typically reflect only directly connected networks or information received from immediate neighbors. For example, router R5 in Figure 1 of the document has an initial routing table that lists directly connected networks without any next hop or hop count information, indicating these are local links: | Network | Next node | Hops | | :------------------ | :-------- | :--- | | 10.0.31.128/24 | - | - | | 10.0.32.128/24 | - | - | | 10.0.33.128/24 | - | - | | 10.0.34.128/24 | - | - | After the network converges, R5's routing table will contain entries for all reachable networks, including those not directly connected. The "Next node" column will indicate the neighbor router to which a packet should be sent to reach that destination, and the "Hops" column will show the shortest path cost in terms of hops [8](#page=8) [9](#page=9). For instance, a converged routing table for R5 might look like this (assuming specific updates and convergence order): | Network | Next node | Hops | | :------------- | :---------- | :--- | | 10.0.31.128/24 | - | - | | 10.0.32.128/24 | - | - | | 10.0.10.128/24 | 10.0.32.1 | 1 | | 10.0.2.128/24 | 10.0.31.1 | 1 | | 10.0.33.128/24 | - | - | | 10.0.34.128/24 | - | - | | 10.0.4.128/24 | 10.0.32.1 | 1 | This final table signifies that to reach network 10.0.10.128/24, R5 should send the packet to the next node 10.0.32.1, and this path requires 1 hop (presumably from R5 to a router with IP 10.0.32.1, which then has direct or short access to the destination network). Networks without a next node and hop count, like 10.0.31.128/24, are likely directly connected and do not require routing to reach [9](#page=9). --- # Link state routing protocols Link state routing protocols operate by having each router construct a complete map of the network topology, enabling them to calculate shortest paths. ## 3 Link state routing protocols Link state routing protocols operate on the principle that each router possesses a complete understanding of the network's topology. This global view allows routers to independently calculate the shortest path to every other node in the network from their own perspective. Unlike distance vector protocols, link state routers do not rely on periodic updates from neighbors about their routing tables; instead, they exchange information about the state of their directly connected links [8](#page=8) [9](#page=9). ### 3.1 Core principles of link state routing In link state routing, a cost is assigned to each available path within the network. Each router maintains an awareness of all accessible paths and uses this information to build an internal map of the entire network. This map is then used to run a shortest path algorithm, such as Dijkstra's algorithm, to determine the optimal route to each destination [8](#page=8) [9](#page=9). ### 3.2 Initial messages and network convergence When a router using a link state protocol starts up or joins the network, it sends an initial message that contains information about its directly connected links and their associated costs. This message, often referred to as a Link State Advertisement (LSA), is flooded throughout the network so that all routers can receive it [9](#page=9). **Example:** For router R5, the initial message it sends out in a link state protocol would detail the cost to its directly connected networks. For instance, if R5 is directly connected to networks with costs of 9, 1, 2, and 3, its initial routing table would reflect these direct connections and costs [10](#page=10) [9](#page=9). > **Tip:** The initial routing table in a link state protocol reflects only the directly known links and their costs. The complete routing table, showing shortest paths to all networks, is only formed after the network converges. After all routers have exchanged their link state information and flooded these LSAs, the network converges. At this point, every router has an identical and complete map of the network topology. Each router then independently executes a shortest path algorithm to calculate the shortest path to every other network and builds its final routing table [8](#page=8). **Example:** Following network convergence, router R5's final routing table would include entries for all networks in the topology, not just those directly connected. For instance, it might show a path to network `10.0.2.128/24` via `10.0.32.1` with a total cost of 6, and a path to network `10.0.4.128/24` also via `10.0.32.1` with a total cost of 5. The table also lists the direct connections with their respective costs, such as network `10.0.32.128/24` with a cost of 1 [10](#page=10). > **Tip:** To fully understand the convergence process for link state routing, it is essential to trace the path and accumulated cost from the source router to each destination network using the network map and shortest path algorithm. --- # Network topology and visualization This topic covers the process of drawing and visualizing network topologies based on routing table information, detailing routers, subnets, and links after configuration changes or protocol convergence [5](#page=5) [6](#page=6) [7](#page=7). ### 4.1 Understanding network topology from routing tables Distance-vector routing protocols involve routers periodically exchanging their routing tables with neighbors. This exchange allows routers to learn about the network's structure and the cost (hops or other metrics) to reach various network IDs. When a router receives an update, it compares the new information with its existing table and updates its entries if a shorter path is found or if new network information is acquired [5](#page=5) [6](#page=6). #### 4.1.1 Router neighbor discovery and path calculation A router's routing table indicates its direct neighbors and the cost to reach different network IDs. If a network ID has no "next node" listed, it typically signifies that the router is directly connected to that network. When an update is received from a neighbor, the cost to reach each network ID in the update is increased by one (representing the hop to the neighbor). The router then compares this new path cost with its current best path cost for that network ID [5](#page=5) [6](#page=6). > **Tip:** When updating a routing table based on a neighbor's information, remember to increment the hop count for each entry received from the neighbor. #### 4.1.2 Updating routing tables with new information The process of updating a routing table involves several steps: 1. **Receive update:** A router receives a routing update message from a neighbor [5](#page=5). 2. **Increment costs:** For each network ID in the received update, add one hop to the cost to account for the link to the neighbor [5](#page=5). 3. **Compare and update:** Compare the newly calculated costs with the existing costs in the router's own routing table [5](#page=5). * If the new path is shorter (lower cost) or if the network ID was not previously in the table, update the table with the new information, including the neighbor as the next hop [5](#page=5). * If the new path is longer or equal in cost, keep the old entry [5](#page=5). * If a network is directly connected (no next hop), its cost remains the same unless a better path is found via a neighbor [6](#page=6). #### 4.1.3 Visualizing network topology After processing routing updates, the network topology can be visualized by drawing the routers and the links between them, representing subnets and their connections [6](#page=6) [7](#page=7). * **Routers:** Represented as nodes in the network diagram [6](#page=6) [7](#page=7). * **Subnets/Networks:** Represented as connections or distinct areas within the diagram, often associated with link IDs [5](#page=5) [6](#page=6). * **Links:** Lines connecting routers, indicating a physical or logical connection, and potentially representing a subnet [5](#page=5) [6](#page=6). * **Neighbor relationships:** Inferred from routing table entries that list a specific router as the "next node" [6](#page=6). * **Directly connected networks:** Identified by entries in the routing table with no "next node" specified [6](#page=6). > **Example:** In the provided exercises, Router A initially knows about its neighbor D and directly connected networks 1 and 6. When it receives an update from a new router E, it incorporates E's routing information, potentially discovering new paths or networks through E. The visualization then reflects these updated adjacencies and paths [6](#page=6) [7](#page=7). ### 4.2 Example: Network configuration update and visualization Consider a scenario where a router receives an update from a new neighbor, Router E. Router A's routing table is updated based on this information [6](#page=6) [7](#page=7). **Initial state (Router A's known information):** * Networks 1 and 6 are directly connected (cost 1, no next node) [6](#page=6). * Network 4 is reachable via Router D with a cost of 3 [6](#page=6). * Network 2 is reachable via Router D with a cost of 4 [6](#page=6). * Network 5 is reachable via Router D with a cost of 2 [6](#page=6). * Network 3 is reachable via Router D with a cost of 2 [6](#page=6). **Update from Router E:** Router E provides information about its reachable networks. For example, it might state it can reach Network 2 with a cost of 1 [7](#page=7). **Router A's updated routing table after processing E's update:** * Net1: Cost 1 (Directly connected) [7](#page=7). * Net2: Cost 2 (Via E, since E's cost to Net2 is 1, plus 1 hop to E) [7](#page=7). * Net3: Cost 2 (Via D, original entry) [7](#page=7). * Net4: Cost 3 (Via D, original entry) [7](#page=7). * Net5: Cost 2 (Via D, original entry) [7](#page=7). * Net6: Cost 1 (Directly connected) [7](#page=7). * Net7: Cost 3 (Via E, assuming E's cost to Net7 is 2, plus 1 hop to E) [7](#page=7). **Visualization of the new network:** The updated routing table allows for a drawing of the network that includes Router E and the paths that now lead through it. This may reveal a more connected or efficient network structure than initially apparent. The diagram would show routers A, D, and E, along with their respective connections and the subnets they can reach, reflecting the latest routing information [7](#page=7). --- ## Common mistakes to avoid - Review all topics thoroughly before exams - Pay attention to formulas and key definitions - Practice with examples provided in each section - Don't memorize without understanding the underlying concepts

| Term | Definition | |------|------------| | Flooding | A routing technique where a packet is sent to all router ports and is only terminated when its Time To Live (TTL) expires. As a packet arrives at a router, it is relayed to all other ports except the one it arrived on. | | Hop count | A metric used in routing to limit the propagation of packets, effectively setting a maximum number of routers a packet can traverse before being discarded. This prevents infinite loops and excessive network traffic. | | Time To Live (TTL) | A mechanism used in network packets to prevent them from circulating indefinitely on a network. Each router that processes the packet decrements the TTL value, and the packet is discarded when the TTL reaches zero. | | Distance Vector Routing | A class of routing protocols where each router advertises its routing table to its directly connected neighbors. Routers then use this information to calculate the shortest path to destinations, updating their tables based on received updates. | | Routing Table | A data table stored in a router that lists the available routes to various network destinations. It typically includes the destination network, the next hop router to forward the packet to, and the cost or number of hops to reach that destination. | | Link State Routing | A routing protocol where each router builds a complete map of the network's topology. Routers exchange information about their directly connected links and their costs, allowing each router to independently calculate the shortest path to all other nodes using algorithms like Dijkstra's. | | Stub Net | A network that connects to only one router, meaning it has a single point of entry or exit to the larger network. | | Convergence | The process by which all routers in a network agree on the same network topology and routing information. This occurs after changes are made to the network or when routing protocols have exchanged sufficient updates to establish consistent routing tables. | | Neighbor | In the context of routing protocols, a neighbor refers to a directly connected router with which routing information is exchanged. | | Cost | A metric used in routing protocols to represent the 'expense' or desirability of a particular path. Lower cost typically indicates a more favorable path, often based on factors like bandwidth, latency, or hop count. |