InternetRouting2025.pdf

# Internet and routing fundamentals This section explores the foundational concepts of the Internet as a network of networks, its evolution with the adoption of TCP/IP, and the principles of local and global routing, including the crucial role of routers. ### 1.1 The evolution of the Internet with TCP/IP The Internet's transition to the TCP/IP protocol suite on January 1, 1983, marked a significant milestone. This shift introduced key protocols [4](#page=4): * **IPv4 (Internet Protocol version 4):** Provides host-to-host communication with a "best effort" delivery service, meaning it does not guarantee delivery and is independent of the underlying link-layer protocols [4](#page=4). * **TCP (Transmission Control Protocol):** Enables reliable process-to-process communication by adding features like error checking and flow control [4](#page=4). * **UDP (User Datagram Protocol):** Offers process-to-process communication but, like IPv4, provides "best effort" delivery without reliability guarantees [4](#page=4). ### 1.2 The physical and virtual structure of the Internet The Internet is fundamentally a "network of networks". It comprises interconnected local area networks (LANs) and broader infrastructure [10](#page=10): * **Home Networks:** Typically include devices like firewalls, routers, wireless access points (WLANs), file servers, Network Attached Storage (NAS), and service servers [5](#page=5). * **Global Infrastructure:** Characterized by extensive fiber optic cables forming a backbone, emphasizing redundancy for reliability. For example, Sunet CD's backbone operates at 400Gbps [6](#page=6) [7](#page=7). * **Virtual Networks:** The concept of virtual networks extends to data centers and telecommunication systems, such as LTE networks [8](#page=8) [9](#page=9). ### 1.3 The role of routers Routers are essential devices that connect different LANs, often with varying Layer 1 and Layer 2 protocols. Their primary functions include [10](#page=10): * **Interconnecting Networks:** Routers act as the gateways between disparate networks, enabling communication across them [10](#page=10). * **Breaking Broadcast Domains:** They segment broadcast domains, which is critical because protocols like ARP (Address Resolution Protocol) rely on broadcasts [10](#page=10). ### 1.4 Routing concepts: Intra-domain vs. Inter-domain Routing within the Internet can be categorized into two main types: #### 1.4.1 Intra-domain routing * **Definition:** This refers to routing within a single autonomous system (AS) or administrative domain [10](#page=10). * **Functionality:** Intra-domain routing focuses on efficiently forwarding packets between nodes within a given network. It helps in breaking broadcast domains [10](#page=10). #### 1.4.2 Inter-domain routing * **Definition:** This is routing between different autonomous systems [11](#page=11). * **Policy Routing:** Inter-domain routing is heavily influenced by policy, where agreements and organizational policies often take precedence over simple connectivity. Key considerations include [11](#page=11): * Which networks traffic is exchanged with. * Which networks are permitted to carry one's traffic [11](#page=11). * **Further Study:** More in-depth details on Inter-Domain Routing are covered in ETSF10 Internetprotokoll [11](#page=11). ### 1.5 Core routing problem: Finding the best path The fundamental challenge in routing is to determine the "best path" for a packet to reach its destination network. This involves [3](#page=3): * **Identifying the next hop:** Deciding which neighboring router to send the packet to. * **Optimizing for the destination network:** Ensuring the path is efficient and aligns with network policies [3](#page=3). ### 1.6 Routing algorithms (Introduction) The course agenda introduces two primary routing algorithms that will be discussed: * **Distance Vector:** Algorithms that determine routing paths by having each router communicate its routing table to its neighbors [3](#page=3). * **Link State:** Algorithms where each router builds a complete map of the network and then computes the shortest path to all destinations [3](#page=3). ### 1.7 Mathematical foundations for routing Graph theory provides the mathematical framework for understanding and analyzing routing algorithms. Concepts from graph theory are essential for calculating optimal paths and understanding network topology [3](#page=3). --- # Local routing and address resolution This section details the mechanisms by which devices on the same network communicate, focusing on the Address Resolution Protocol (ARP) for IPv4 and its IPv6 equivalent, the Neighbor Discovery Protocol. ### 2.1 Local routing principles Local routing refers to the process of directing datagrams (packets) between devices that are on the same network. The primary decision point for local routing is whether the destination IP address belongs to a device on the same network segment as the sender [13](#page=13) [14](#page=14). #### 2.1.1 Determining if a destination is on the local network A sender determines if a destination IP address is on the local network by comparing its own network identifier (Netid) with the destination's Netid. If both the sender and the destination share the same Netid, the destination is considered to be on the local network [14](#page=14). #### 2.1.2 Routing to a local destination When the destination IP address is identified as being on the local network, the sender needs to find the destination's MAC address to construct the Layer 2 frame [14](#page=14). 1. **Check ARP cache:** The sender first checks its Address Resolution Protocol (ARP) cache to see if it already has a mapping for the destination IP address to its corresponding MAC address [14](#page=14). 2. **ARP request:** If the destination's MAC address is not found in the ARP cache, the sender initiates an ARP request. This ARP request is typically broadcast to all devices on the local network segment, asking for the MAC address associated with the target IP address [14](#page=14) [17](#page=17). 3. **ARP reply:** The device with the matching IP address responds with an ARP reply containing its MAC address [14](#page=14) [17](#page=17). 4. **Frame construction:** The sender then uses the obtained MAC address to construct the Layer 2 frame and sends the datagram [14](#page=14). > **Tip:** The switch handles only Layer 2 frames and is unaware of IP addresses; the ARP process is crucial for resolving IP addresses to MAC addresses on the local network [19](#page=19). #### 2.1.3 Routing to a remote destination (default gateway) If the destination IP address is *not* on the local network (i.e., it has a different Netid), the sender must send the datagram to its configured default gateway [15](#page=15). 1. **Identify default gateway:** The sender uses its default gateway's IP address as the target for the Layer 2 frame. 2. **Check ARP cache for gateway:** The sender checks its ARP cache for the MAC address of the default gateway [15](#page=15). 3. **ARP for gateway:** If the gateway's MAC address is not in the cache, the sender performs an ARP request specifically for the default gateway's IP address [15](#page=15). 4. **Frame construction:** The sender then constructs the Layer 2 frame using the default gateway's MAC address, even though the ultimate destination IP address is different. The gateway will then handle the routing of the packet to its final destination [15](#page=15). > **Example:** If a laptop needs to send an IP packet to a server `DatorX` that is not on the same local network, the laptop's ARP request will ask for the MAC address of the router (the default gateway) on the local network, not the MAC address of `DatorX` [19](#page=19). ### 2.2 Address Resolution Protocol (ARP) for IPv4 ARP is a crucial protocol used in IPv4 networks to map an IP address to a physical machine address (MAC address) on the same link layer [14](#page=14). #### 2.2.1 ARP operation When a host needs to send an IP datagram to another host on the same logical network, it first determines if the destination host is on the local network by comparing IP addresses and subnet masks. If it is local, the host needs the destination's MAC address. If the MAC address is not in the sender's ARP cache, an ARP request is broadcast. The ARP request contains the IP address of the target and asks for its MAC address. The host with the matching IP address replies with its MAC address [14](#page=14) [17](#page=17). #### 2.2.2 ARP cache The ARP cache stores mappings of IP addresses to MAC addresses that have been recently resolved. This caching mechanism improves efficiency by avoiding the need to send an ARP request for every packet sent to a known destination on the local network [14](#page=14). ### 2.3 Neighbor Discovery Protocol (NDP) for IPv6 For IPv6 networks, the functionality provided by ARP in IPv4 is replaced by the Neighbor Discovery Protocol (NDP), which is part of ICMPv6. NDP handles functions such as address resolution, router discovery, and duplicate address detection. It operates analogously to ARP in IPv4, enabling devices on the same IPv6 link to resolve link-layer addresses from IPv6 addresses [16](#page=16). --- # Global routing principles and graph theory This section explores fundamental principles of global routing in networks, from basic concepts to advanced graph theory applications for finding optimal paths [20](#page=20) [21](#page=21) [22](#page=22) [23](#page=23) [24](#page=24) [25](#page=25) [26](#page=26) [27](#page=27) [28](#page=28) [29](#page=29) [30](#page=30) [31](#page=31) [32](#page=32) [33](#page=33) [34](#page=34) [35](#page=35) [36](#page=36) [37](#page=37) [38](#page=38) [39](#page=39) [40](#page=40) [41](#page=41) [42](#page=42) [43](#page=43) [44](#page=44) [45](#page=45) [46](#page=46) [47](#page=47) [48](#page=48) [49](#page=49) [50](#page=50) [51](#page=51) [52](#page=52) [53](#page=53). ### 3.1 Routing principles overview Routing involves directing data packets across networks. The approach to routing can be categorized into three main principles: "no intelligence" (flooding), centralized routing, and distributed routing. Internet Protocol (IP) operates on packet switching, where packets can take different routes and arrive out of order. The sender's IP layer doesn't need to know the exact path or even if the packet will arrive [21](#page=21) [22](#page=22). #### 3.1.1 "No intelligence" routing: Flooding Flooding is a routing method where a packet is sent out on all ports or links except for the ingress port it arrived on (#page=23, 28). This ensures that the packet is propagated throughout the network [23](#page=23) [28](#page=28). ##### 3.1.1.1 Problems with flooding A significant issue with flooding is the potential for packets to loop indefinitely, creating unnecessary traffic. Two common solutions to mitigate this are [28](#page=28): * **TTL (Time To Live) counter:** A counter decrements with each hop, and the packet is discarded when the counter reaches zero [28](#page=28). * **Remembering handled packets:** Nodes keep track of packets they have already processed to avoid re-sending them [28](#page=28). ##### 3.1.1.2 Flooding example and exercise Consider a network graph. The minimum TTL required to ensure all nodes receive a message in a fully connected network is 3 hops. If two links fail, the worst-case scenario requires 5 hops to reach all nodes (#page=29, 30) [29](#page=29) [30](#page=30). #### 3.1.2 Centralized routing In centralized routing, the control plane and data plane are separated. A central database and routing algorithm manage network intelligence. Nodes in the network update this central function with their information. Packet forwarding, however, remains distributed. This concept is closely related to Software-Defined Networks (SDN) [32](#page=32). #### 3.1.3 Distributed routing With distributed routing, the routing process, encompassing both the control and data planes, is distributed among all routers in the network (#page=33, 34). Two primary methods exist [33](#page=33) [34](#page=34): * **Distance Vector:** Each node shares its information about the best paths to its neighbors. The end-to-end best path is determined by comparing these updates with all possible next hops. This method is simple and has low demands on processing power and memory [34](#page=34). * **Link State:** Information about the local topology is flooded to all nodes. Each node then independently calculates the best end-to-end path to all other nodes, typically using a tree-building algorithm. This approach requires more processing power and memory [34](#page=34). ### 3.2 The router and its role A router is responsible for forwarding packets between networks based on their network layer addresses. Routing decisions are made based on the network identity (net ID), not the host identity (host ID). Routers "learn" the best paths towards a destination's network by exchanging information with other routers within a routing domain. The destination's host ID is only relevant for the final router in the path [35](#page=35). A router's schematic structure includes input queues, output queues, and a "vägväljar-modul" (path selection module) which makes routing decisions [36](#page=36). Routing tables are distinct from the forwarding table. Routing tables are maintained by specific routing protocols like OSPF, RIP, and BGP, and they contain information about reachable networks and their paths. The forwarding table, often managed by a Forwarding Table Manager, is a more optimized structure used for rapid packet lookup and forwarding, and can also include static routes [37](#page=37). #### 3.2.1 Traceroute exercise The `traceroute` (or `tracert`) command helps determine the path IP datagrams take to a destination. By observing the Round Trip Time (RTT), significant increases can indicate hops over long distances, such as across continents. It's important to note that not all nodes respond to traceroute requests for security reasons [38](#page=38) [40](#page=40). ### 3.3 Graph theory in routing Graph theory provides a powerful mathematical framework for understanding and solving routing problems, particularly for finding the shortest paths (#page=41, 42) [41](#page=41) [42](#page=42). #### 3.3.1 Graph fundamentals A graph is composed of: * **Nodes (vertices):** Represent entities in the network, such as routers [42](#page=42). * **Edges (arcs):** Connect nodes, representing links or paths between them [42](#page=42). Graphs can be: * **Weighted:** Edges have associated costs, representing metrics like latency, bandwidth, or hop count [42](#page=42). * **Directed:** Edges have a specific direction, indicating one-way communication or asymmetric costs [42](#page=42). The concept of a "tree" within a graph is crucial: for any arbitrary graph, there exists a tree that contains the shortest paths from a specific node to all other nodes. The "best" path is defined as the one with the lowest total cost [42](#page=42). ##### 3.3.1.1 Historical context: Euler's bridges The foundation of graph theory is often attributed to Leonard Euler's solution to the Seven Bridges of Königsberg problem in 1736, which explored the possibility of traversing all bridges exactly once [43](#page=43). #### 3.3.2 Tree building algorithms Routing's core objective is to find the best path from a source to all destinations, which is essentially a "tree building" problem in graph theory. Two prominent algorithms for this are [44](#page=44): * **Bellman-Ford algorithm:** An iterative method that updates distance estimates for all edges in the graph [45](#page=45). * The algorithm iterates a number of times equal to one less than the number of vertices in the graph [46](#page=46). * In each iteration, it checks every edge $(u, v)$ and updates the distance to $v$ if a shorter path is found through $u$: $d(v) = d(u) + c(u, v)$, where $d(u)$ is the current cost to reach node $u$, and $c(u, v)$ is the cost of the edge $(u, v)$ (#page=45, 46) [45](#page=45) [46](#page=46). * If an iteration results in no changes to the distances, the algorithm can terminate early [47](#page=47). > **Example:** Applying Bellman-Ford from node D in a given graph results in a specific shortest-path tree structure after three iterations [53](#page=53). * **Shortest Path First (SPF) algorithm (Dijkstra's algorithm):** A greedy algorithm that finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights (#page=44, 49) [44](#page=44) [49](#page=49). * It maintains a set of visited nodes and iteratively selects the unvisited node with the smallest known distance from the source [50](#page=50). * The algorithm then updates the distances of the neighbors of the selected node [50](#page=50). > **Example:** Applying Dijkstra's algorithm from node A in a given graph leads to the construction of a shortest-path tree, yielding the same final tree structure as Bellman-Ford in some cases (#page=50, 51) [50](#page=50) [51](#page=51). #### 3.3.3 Exercise on tree building Given a graph and a starting node (e.g., D), one can calculate the shortest-path tree using both the Bellman-Ford and Dijkstra's SPF algorithms. The results of these calculations should be compared (#page=52, 53) [52](#page=52) [53](#page=53). --- # Distance vector and link state routing algorithms This section delves into two fundamental distributed routing algorithms, Distance Vector and Link State, explaining their operational principles, mechanisms for routing table updates, and maintenance processes. [57-66, 68-80 ### 4.1 Distance vector routing Distance Vector (DV) is a distributed routing algorithm where each node periodically exchanges its entire routing table with its directly connected neighbors. The core idea is that each router advertises its knowledge of the best paths to all destinations, including the cost and the next hop. This knowledge is spread "locally" to neighbors, and through these exchanges, global routing information eventually converges across the network [58](#page=58). #### 4.1.1 Principles of distance vector routing * **Information Exchange:** Routers send their current routing tables to their neighbors periodically and also whenever a change occurs in their routing information [58](#page=58). * **Bellman-Ford Algorithm:** The underlying principle for updating routing tables in Distance Vector routing is often based on the Bellman-Ford algorithm [58](#page=58). * **Routing Table Updates:** Tables are updated when information about new destinations is received, or when the cost or path to an existing destination changes [58](#page=58). * **Routing Table Structure:** A typical distance vector routing table contains the destination network ID, the cost (often measured in hop count), and the next hop router. The "Next Hop" is the router that sent the vector containing the information [62](#page=62). #### 4.1.2 Bellman-Ford algorithm for distance vector The Bellman-Ford algorithm, adapted for distance vector routing, updates a node's cost to a destination based on the costs advertised by its neighbors. If a router `x` learns about a path to destination `y` through neighbor `z` with a cost `c(x,z) + D_{zy}`, it compares this with its current best known cost `D_{xy}` [60](#page=60). The update rule can be generalized as: $D_{xy} = \min \{ c_{xz} + D_{zy} \}$ for all neighbors $z$ of $x$ [60](#page=60). This can also be expressed as: $D_{xy} = \min \{ D_{xy}, c_{xz} + D_{zy} \}$ [60](#page=60). It's important to note that $D_{xy}$ can change even if a new node `z` is not directly involved in the path to `y`, but rather a neighbor `z` advertises a better path to `y` [60](#page=60). The algorithm for updating a routing table at node `x` based on an advertised vector from a neighbor can be described as follows [59](#page=59): 1. If the advertised destination is not in the table, add it. 2. If the advertised destination is already in the table: a. If the advertised next-hop is the same as the next-hop in the table, replace the entry (e.g., if the cost is updated). b. If the advertised next-hop is different: i. If the advertised hop count is less than the hop count in the table, replace the entry. ii. Otherwise, do nothing. #### 4.1.3 Distance vector example Consider a network with routers R1, R2, R3, and R4, and networks A, B, C, and D. Each router periodically sends its routing table (containing network ID and cost) to its neighbors [61](#page=61). For instance, R1 might have a table: * Network A: Cost - * Network B: Cost 1 (Directly connected) * Network C: Cost 2 (via R2) * Network D: Cost 3 (via R2) If R1 sends its table to R2, and R2 has a cost of 4 to reach network D, R2 will update its entry for D. If R2 receives an advertisement from R5 indicating a cost of 5 to reach network D, and R5 is the next hop, R2's table for D might be updated. If R2's current entry for D is a direct connection with cost 5, and it receives an advertisement from R5 with cost 5, it might update its entry to next hop R5 with cost 10 (assuming cost from R2 to R5 is 5) [64](#page=64). A more structured example of a distance vector table might look like this: | Destination | Cost | Next Hop | | :---------- | :--- | :------- | | Network A | 8 | --- | | Network B | 4 | --- | | Network C | 2 | Rtr5 | | Network D | 5 | --- | | Network E | 5 | Rtr5 | | Network F | 7 | Rtr5 | | Network G | 3 | Rtr5 | When Rtr3 receives an update from Rtr5, which advertises routes with a cost of 5 from Rtr5: * If Rtr3's table has `D - 5`, and Rtr5 advertises `D - 5`, Rtr3 might update its entry for D to `D - 10` if Rtr5 is the new next hop with a cost of 5. However, if Rtr3 already has a direct connection for D with cost 5, and Rtr5 is not the preferred next hop, it may not update. * If Rtr3's table has no entry for C, and Rtr5 advertises `C - 2` with a cost of 5 (meaning `C` is 5 hops from Rtr3 via Rtr5), Rtr3 will add `C - 7 (via Rtr5)` to its table [64](#page=64). #### 4.1.4 Challenges with distance vector routing * **Neighbor Discovery:** There isn't a natural mechanism for discovering neighbors [65](#page=65). * **Failure Detection:** Detecting the disappearance of a neighbor or link can be slow, leading to routing loops or incorrect routing information for a period [65](#page=65). * **Periodic Updates:** Relying solely on periodic updates can lead to delays in propagating changes [65](#page=65). ### 4.2 Link state routing Link State (LS) routing algorithms work on the principle that each router constructs a complete map of the network topology. This map is built by flooding "Link State Advertisements" (LSAs) globally throughout the network. Each LSA contains information about a router's directly connected links, their costs, and its neighbors [69](#page=69) [71](#page=71). #### 4.2.1 Principles of link state routing * **Global Topology Knowledge:** Each router in the network maintains a database of all known link states [69](#page=69). * **Link State Advertisements (LSAs):** When a local change occurs (e.g., a link goes up or down), a router generates an LSA describing this change and floods it to all other routers. LSAs are also periodically sent, though much less frequently than in DV routing (e.g., every half hour) [69](#page=69). * **Shortest Path First (SPF) Algorithm:** Once a router has a complete link state database, it uses an SPF algorithm (like Dijkstra's algorithm) to calculate the shortest path to every other network destination [69](#page=69). * **Routing Table Updates:** The routing table is updated whenever new information is added to the link state database, triggering an SPF calculation [69](#page=69). * **Information Flow:** The principle is "local knowledge spreads globally" [69](#page=69). #### 4.2.2 Link State Advertisement (LSA) An LSA typically contains: * **Advertiser:** The ID of the router originating the advertisement [71](#page=71). * **Network ID:** The identifier of the network or destination being advertised [71](#page=71). * **Cost:** The cost associated with the link to that network [71](#page=71). * **Neighbor:** The adjacent router or node connected via this link [71](#page=71). For routing between a router and a network, the link cost is specified. For routing between a network and a router, the cost is effectively 0 [73](#page=73). #### 4.2.3 Link State Database example A Link State database in a router might contain entries like: | Advertiser | Network ID | Cost | Neighbour | | :--------- | :--------- | :--- | :-------- | | Rtr 1 | Net A | 8 | --- | | Rtr 1 | Net B | 4 | Rtr 2 | | Rtr 1 | Net B | 4 | Rtr 3 | | Rtr 2 | Net B | 4 | Rtr 1 | | Rtr 2 | Net C | 2 | Rtr 4 | | Rtr 3 | Net B | 4 | Rtr 2 | | Rtr 3 | Net D | 10 | Rtr 5 | | ... | ... | ... | ... | #### 4.2.4 Shortest Path First (SPF) calculation example To calculate the routing table for Rtr3, an SPF algorithm like Dijkstra's is used on the aggregated link state information. **Step 1:** Identify the cheapest links originating from Rtr3. If Rtr3 has direct connections to Networks B (cost 4) and D (cost 5), these are marked as permanent [74](#page=74). **Step 2:** From the set of permanent links, explore outward. For example, if Rtr3 is connected to Rtr2 with cost 4, and Rtr2 is connected to Network C with cost 2, then the path Rtr3 -> Rtr2 -> Net C has a total cost of $4 + 2 = 6$. This path is now considered [75](#page=75). **Step 3:** Continue this process, iteratively adding the cheapest unvisited node to the permanent set and updating path costs. This process builds up the shortest path tree rooted at the current router [74](#page=74) [75](#page=75) [76](#page=76). **Step 4:** The final SPF calculation yields the shortest path and cost to all reachable networks. For Rtr3, the routing table might look like: | Network ID | Next-hop | Cost | | :--------- | :------- | :--- | | Net A | Rtr1 | 12 | | Net B | --- | 4 | | Net C | Rtr2 | 6 | | Net D | --- | 5 | | Net E | Rtr2 | 10 | | Net F | Rtr2 | 13 | | Net G | Rtr2 | 13 | #### 4.2.5 Challenges with link state routing Similar to Distance Vector, Link State routing also faces challenges in [78](#page=78): * **Failure Detection:** Detecting link and node failures and how to handle them requires specific mechanisms [78](#page=78). * **Neighbor Discovery:** Identifying directly connected neighbors is a prerequisite for exchanging LSAs [78](#page=78). * **Disappearance of Neighbors:** Gracefully handling the event when a neighbor disappears is crucial [78](#page=78). * **Periodic Updates:** While less frequent than DV, periodic updates are still part of the protocol [78](#page=78). --- ## 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 | |------|------------| | Internet | A network of networks, rather than a single unified network, where all participating nodes universally utilize IP protocols for communication. | | Router | A network device that connects different Local Area Networks (LANs), often supporting diverse Layer 1 (physical) and Layer 2 (data link) protocols, and facilitates communication between these networks. | | TCP/IP | A suite of communication protocols used for the Internet and similar networks, consisting of the Internet Protocol (IP) for host-to-host communication and the Transmission Control Protocol (TCP) for reliable, process-to-process data transfer. | | IPv4 | A network layer protocol that provides host-to-host connectivity with a "best effort" delivery service, operating independently of the underlying link protocols. | | TCP | A transport layer protocol that ensures reliable, process-to-process communication by managing data flow, error checking, and retransmissions. | | UDP | A transport layer protocol that provides a "best effort", connectionless communication service between processes, prioritizing speed over reliability. | | Intra-Domain Routing | A type of routing that occurs within a single autonomous system or administrative domain, responsible for breaking down broadcast domains and typically involving protocols like ARP, which broadcast requests. | | Inter-Domain Routing | A type of routing that occurs between different autonomous systems or administrative domains, where policies and agreements regarding traffic exchange and routing paths take precedence over simple connectivity. | | Policy Routing | A routing strategy where routing decisions are influenced by administrative policies, agreements on traffic exchange, and who is permitted to carry traffic, rather than solely by network topology or reachability. | | Backbone Network | A high-capacity network infrastructure that forms the core of larger networks, often designed with significant bandwidth (e.g., 400Gbps) and redundancy to handle substantial data traffic. | | Local Routing | The process by which devices on the same network segment communicate with each other directly, without needing to pass through a router. This involves determining if the destination IP address resides within the local network. | | Address Resolution Protocol (ARP) | A network protocol used to discover the link layer address (MAC address) corresponding to a given Internet layer address (IPv4 address) within a local network. It is crucial for devices to be able to resolve an IP address to a MAC address to send data frames. | | MAC Address | A unique hardware identifier assigned to each network interface controller (NIC) for communications at the data link layer of a network segment. It is used to identify devices on a local network. | | ARP Cache | A temporary storage maintained by a network device that maps IP addresses to their corresponding MAC addresses. When a device needs to send data to an IP address, it first checks the ARP cache to see if the MAC address is already known. | | ARP Request | A broadcast message sent by a device on a local network when it needs to find the MAC address of another device on the same network. The request typically asks, "Who has the IP address X? Tell Y (the sender)." | | ARP Reply | A unicast message sent by a device in response to an ARP request. It contains the MAC address of the device that owns the requested IP address. | | Network ID | The portion of an IP address that identifies the network to which a device belongs. Devices with the same Network ID are considered to be on the same local network. | | Datagram | A unit of data transmitted over a packet-switched network. In the context of IP, a datagram refers to an IP packet. | | Neighbour Discovery Protocol (NDP) | A protocol in IPv6 that serves a similar purpose to ARP in IPv4. It is part of the Internet Control Message Protocol version 6 (ICMPv6) and is used for functions such as address resolution, duplicate address detection, and router discovery. | | Default Gateway | A router on a local network that serves as the entry point to other networks, such as the internet. When a device needs to send a packet to an IP address outside its local network, it forwards the packet to the default gateway. | | Global Routing | The process of determining the path for data packets across an entire network, typically involving multiple interconnected networks or autonomous systems. | | IP Packet Switching | A method where data is broken down into packets, and each packet can take a different route through the network to reach its destination, potentially arriving out of order. | | Flooding | A routing principle where a packet is sent out on all network interfaces except the one it arrived on, ensuring delivery but potentially causing loops and excessive traffic. | | TTL (Time To Live) | A mechanism used to prevent packets from endlessly looping in a network; each hop decrements the TTL counter, and a packet is discarded when the TTL reaches zero. | | Centralized Routing | A routing approach where a single central entity or database holds all routing information and makes decisions for the entire network, separating control and data planes. | | Distributed Routing | A routing approach where each router independently participates in the routing process, exchanging information with its neighbors to build routing tables and make forwarding decisions. | | Distance Vector Routing | A distributed routing method where each node shares its current knowledge of the best paths and distances to other nodes with its direct neighbors. | | Link State Routing | A distributed routing method where each node floods information about its local topology to all other nodes in the network, allowing each node to independently construct a complete network map. | | Graph Theory | A branch of mathematics that studies graphs, which are abstract representations of networks consisting of nodes (vertices) and connections between them (edges). | | Graph | A collection of nodes (vertices) and edges (arcs/connections) that link these nodes together. | | Weighted Graph | A graph where each edge has an associated cost or weight, often representing metrics like latency, bandwidth, or hop count. | | Directed Graph | A graph in which the edges have a specific direction, indicating a one-way relationship or flow between nodes. | | Tree Building | A process in graph theory and routing algorithms aimed at finding the shortest path from a source node to all other reachable nodes in a network, forming a shortest-path tree. | | Bellman-Ford Algorithm | An iterative algorithm used for finding the shortest paths from a single source vertex to all other vertices in a weighted digraph, capable of handling negative edge weights. | | Shortest Path First (SPF) / Dijkstra's Algorithm | An algorithm that finds the shortest paths between nodes in a graph, typically used in link-state routing protocols; it efficiently calculates the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights. | | Vertex (Node) | A fundamental element of a graph, representing a point or entity in the network. | | Edge (Arc/Connection) | A link or connection between two vertices in a graph, representing a path or relationship. | | Cost (Weight) | A value assigned to an edge in a weighted graph, representing the expense or difficulty of traversing that connection. | | Network Topology | The arrangement of the various elements (links, nodes, etc.) of a computer network. | | Control Plane | The part of a network that is responsible for routing decisions and network management. | | Data Plane | The part of a network that is responsible for forwarding the actual data traffic based on decisions made by the control plane. | | Distance Vector | A routing algorithm where each router maintains a routing table that represents the distance (e.g., hop count) to known destinations. Routers periodically exchange their entire routing tables with their direct neighbors, allowing for decentralized updates and propagation of network knowledge. | | Link State | A routing algorithm where each router advertises its local link status (connections and their costs) to all other routers in the network. Each router then constructs a complete map of the network topology and uses an algorithm like Shortest Path First (SPF) to calculate the best routes. | | Routing Table | A data structure stored in a router that lists the available routes to various network destinations. It typically includes the destination network, the cost to reach it, and the next hop router or interface to use for forwarding packets towards that destination. | | Next Hop | The next router in the path to a destination network. When a router receives a packet, it consults its routing table to determine the next hop where the packet should be forwarded to continue its journey towards the final destination. | | Link State Advertisement (LSA) | A packet used in Link State routing protocols to broadcast information about a router's directly connected links and their associated costs. These advertisements are flooded throughout the network to ensure all routers have an up-to-date view of the network topology. | | Link State Database | A database maintained by each router in a Link State routing domain. This database stores all received Link State Advertisements (LSAs), effectively building a complete map of the network topology for that router. | | Shortest Path First (SPF) Algorithm | An algorithm, such as Dijkstra's algorithm, used in Link State routing to calculate the shortest path from a source node to all other nodes in a network. It constructs a shortest-path tree based on the network topology information stored in the Link State Database. | | Directly Connected | Refers to a network or interface that is directly attached to a router's interface, requiring no intermediate hops. In routing tables, "directly connected" is often indicated by a specific flag or by having the next hop field empty or set to a special value. | | Hop Count | A metric used in some routing algorithms (like Distance Vector) to measure the distance to a destination. It represents the number of routers a packet must traverse to reach the destination. A lower hop count is generally preferred, indicating a shorter path. | | Periodical Update | A mechanism in routing protocols where routing information is exchanged between routers at regular time intervals. This ensures that routers receive updated network status even if no immediate change has occurred, helping to maintain routing table consistency. | | Global Knowledge (Spread Locally) | A characteristic of Distance Vector routing, where each router shares its entire routing table (global knowledge about destinations and costs) only with its immediate neighbors (locally). This local sharing allows the global view to propagate through the network. | | Local Knowledge (Spread Globally) | A characteristic of Link State routing, where each router shares its local knowledge of its own links and their immediate neighbors. This local information is then flooded globally to all other routers, enabling them to build a complete network map. | | Routing Metric | A value assigned to a link or path that quantifies its "cost" or desirability for routing. Common metrics include hop count, bandwidth, delay, and load. Routing algorithms use these metrics to determine the best path for data transmission. | | Convergence | The state of a routing network where all routers have consistent and accurate routing information. During network changes, routing protocols work to reach convergence, ensuring that all routers agree on the best paths to all destinations. | | Distance Vector Update | The process by which routers running a Distance Vector algorithm exchange and process routing information from their neighbors. This involves comparing received distance vectors with the current routing table and updating entries if a better path is found. | | Link State Update | The process in Link State routing where changes in network topology, such as link failures or additions, trigger the generation and flooding of Link State Advertisements (LSAs). Upon receiving new LSAs, routers update their Link State Databases and recalculate shortest paths. | | Advertised Destination | A destination network advertised by a neighboring router in a Distance Vector protocol. This information is used to update the local routing table. | | Advertised Next-Hop | The next-hop router specified by a neighbor in its advertised routing information. This is crucial for updating the local routing table with the correct forwarding path. | | Advertised Hop Count | The number of hops to a particular destination as advertised by a neighboring router in a Distance Vector protocol. This value is compared against the current hop count in the local routing table to determine if an update is necessary. | | Neighbor | A router that is directly connected to another router via a network link. In Distance Vector routing, neighbors exchange routing tables, and in Link State routing, they exchange Link State Advertisements. | | Cost | A numerical value representing the expense of using a particular link or path. Lower costs are typically preferred in routing algorithms, indicating a more desirable or efficient path. The definition of cost varies depending on the routing protocol and its metrics. | | Link State Advertisement Advertiser | The router that originates and sends a Link State Advertisement (LSA). This identifies the source of the topological information being broadcast. | | Link State Advertisement Neighbour | The adjacent router or network that a router advertises a link to in a Link State Advertisement. This indicates the direct connectivity and the associated cost to that neighbor. | | Routing/Forwarding Table | A table used by routers to make decisions on where to forward incoming IP packets. The routing table informs the forwarding process about the best path to a destination network. In some contexts, the forwarding table is an optimized version of the routing table used for high-speed packet switching. | | Interface | A network connection point on a router or host. Data packets are sent out from and received into specific interfaces. In routing tables, the interface field indicates which physical or logical port the packet should be sent through to reach the next hop. | | \(D_{xy}\) | In the context of the Bellman-Ford algorithm, this represents the estimated minimum cost (or distance) from router $x$ to destination $y$. | | \(c_{xa}\) | In the context of the Bellman-Ford algorithm, this represents the direct cost (or link cost) from router $x$ to an intermediate router $a$. | | \(D_{ay}\) | In the context of the Bellman-Ford algorithm, this represents the estimated minimum cost (or distance) from an intermediate router $a$ to the destination $y$. | | \(\min\) | Mathematical operator representing "minimum". Used in routing algorithms to select the path with the lowest cost among several options. For example, \(\min(a, b)\) returns the smaller of $a$ and $b$. |