JOURNAL / Coursework/COMP 437 Computer Networks/Unit 5 / NOTE
Section 2 Routing Alogrithms
Computer Networks study notes · Unit 5
- Author
- Michel Deosaran
- Published
- Tags
- #computer-networks
Text-to-Speech Q&A Document for Exam Prep: Routing Algorithms and Network Layer Protocols
Section 1: Routing Principles and Algorithm Fundamentals
Question 1: What are the primary goals of a routing algorithm?
Answer: The primary goals of a routing algorithm are to determine the best path for data packets to travel from a source node to a destination node through a network. A routing algorithm must find a path that is optimal according to some criterion, such as minimum cost, shortest distance, or least congestion. It must also be efficient in terms of computational resources and must adapt to changes in network topology, such as link failures or the addition of new nodes. Additionally, a good routing algorithm should be stable, meaning it should not oscillate between different paths unnecessarily, and it should be scalable to handle large networks with many nodes and links.
Question 2: What is the role of the network layer routing protocol?
Answer: The role of the network layer routing protocol is to establish and maintain the routing tables that are used by routers to forward packets toward their destinations. The routing protocol is responsible for discovering network topology, exchanging routing information between routers, computing the best paths based on a chosen metric, and updating routing tables when the network topology changes. It ensures that every router in the network has a consistent and accurate view of the network so that packets can be delivered efficiently and reliably. The routing protocol operates at the network layer of the OSI model and works in conjunction with the forwarding function, which actually moves packets from an input link to the appropriate output link based on the routing table.
Question 3: What is the least cost path between two hosts in a network, and what condition does such a path have to meet?
Answer: The least cost path between two hosts in a network is the path that has the smallest total cost among all possible paths connecting the two hosts. The cost of a path is typically calculated as the sum of the costs of the individual links that make up the path. The cost of a link can be defined in various ways, such as the monetary cost of transmitting data over that link, the delay experienced on that link, the amount of congestion, or simply a hop count where each link has a cost of one. The condition that such a path must meet is that it must be a valid path in the network graph, meaning it must consist of a sequence of edges that connect the source node to the destination node without any breaks. Among all valid paths, the least cost path is the one that minimizes the sum of the link costs.
Question 4: What is the shortest path between two hosts in a network?
Answer: The shortest path between two hosts in a network is the path that has the fewest number of hops, where a hop is a direct link between two adjacent nodes. In other words, it is the path that traverses the smallest number of intermediate routers or switches. The shortest path is a special case of the least cost path where the cost of each link is equal to one. This means that the shortest path minimizes the number of links that a packet must traverse from source to destination. It is important to note that the shortest path in terms of hop count may not always be the least cost path if link costs are not uniform.
Question 5: When can the shortest path and the least cost path be identical?
Answer: The shortest path and the least cost path can be identical when the cost of every link in the network is the same, typically set to one. In this case, minimizing the number of hops is equivalent to minimizing the total cost, because each hop contributes the same amount to the total cost. For example, if every link in the network has a cost of one, then the path with the fewest hops will also have the lowest total cost. However, if link costs vary, for instance due to differences in bandwidth, delay, or monetary cost, then the shortest path and the least cost path may differ. The shortest path minimizes hop count, while the least cost path minimizes the sum of the actual link costs.
Question 6: What are routing algorithms used for?
Answer: Routing algorithms are used to determine the best path for data packets to travel from a source to a destination through a network. They are used by routers to build and maintain routing tables, which are used to forward packets. Routing algorithms are essential for the efficient operation of both small and large networks, including the Internet. They help in adapting to network changes, such as link failures or congestion, by recalculating paths. Routing algorithms can be classified based on whether they are global or decentralized, static or dynamic, and load-sensitive or load-insensitive. They are used in various types of networks, including circuit-switched networks and packet-switched networks.
Question 7: How is a graph used to formulate routing problems?
Answer: A graph is used to formulate routing problems by representing the network as a set of nodes and edges. In this representation, nodes correspond to routers or switches, and edges correspond to communication links between them. Each edge is associated with a cost, which represents the cost of transmitting data over that link. The routing problem then becomes the problem of finding the least cost path from a source node to a destination node in this graph. This abstraction allows routing algorithms to be designed and analyzed using well-established graph theory concepts and algorithms, such as Dijkstra’s algorithm for finding shortest paths. The graph model also allows for the representation of various network topologies and the study of how routing algorithms behave under different conditions.
Question 8: What is a centralized routing algorithm?
Answer: A centralized routing algorithm is a routing algorithm in which one central node or controller has complete knowledge of the entire network topology and all link costs. This central node computes the least cost paths between all pairs of nodes and then distributes the resulting routing information to all routers in the network. Because the central node has a global view of the network, it can make optimal routing decisions. However, centralized routing algorithms have drawbacks, including a single point of failure and scalability issues, as the central node must gather information from and distribute information to all other nodes. An example of a centralized routing algorithm is the link-state algorithm when it is implemented with a central controller, although in practice link-state algorithms are often distributed.
Question 9: What is a decentralized routing algorithm?
Answer: A decentralized routing algorithm is a routing algorithm in which each router independently computes its own routing table based on information it exchanges with its neighbors. No single node has complete knowledge of the entire network. Instead, each router gradually learns about the network through iterative communication with its directly connected neighbors. The distance-vector algorithm is a classic example of a decentralized routing algorithm. In a decentralized algorithm, routers do not need to know the full topology of the network; they only need to know the costs to their neighbors and the distances reported by those neighbors. This makes decentralized algorithms more scalable and robust to failures, but they may converge more slowly and can suffer from problems such as routing loops and the count-to-infinity problem.
Question 10: What is a static routing algorithm?
Answer: A static routing algorithm is a routing algorithm in which the routes are determined in advance and do not change automatically in response to changes in network topology or traffic conditions. The routing table entries are typically configured manually by a network administrator. Static routing is simple and predictable, and it does not consume network resources for routing updates. However, it is not suitable for large or dynamic networks because it cannot adapt to link failures or congestion. If a link goes down, the static route using that link will fail, and manual intervention is required to update the routing table. Static routing is often used in small networks or in stub networks where there is only one path to the outside world.
Question 11: What is a dynamic routing algorithm?
Answer: A dynamic routing algorithm is a routing algorithm that automatically adapts to changes in network topology and traffic conditions. It updates routing tables periodically or in response to network events, such as link failures or the addition of new links. Dynamic routing algorithms exchange routing information between routers to learn about the current state of the network. They can be classified as either global or decentralized, and as either load-sensitive or load-insensitive. Dynamic routing is essential for large networks like the Internet, where topology changes are frequent and manual configuration is impractical. Examples of dynamic routing protocols include RIP, OSPF, and BGP. While dynamic routing is more flexible and resilient than static routing, it introduces overhead due to the exchange of routing updates and can be more complex to configure and troubleshoot.
Question 12: What is a load-sensitive routing algorithm?
Answer: A load-sensitive routing algorithm is a routing algorithm that takes into account the current level of congestion or load on the links when making routing decisions. The cost associated with a link reflects its current traffic load, so heavily loaded links have higher costs and are less likely to be chosen. The goal is to route traffic away from congested links and toward less utilized links, thereby balancing the load across the network and improving overall performance. However, load-sensitive algorithms can introduce instability because routing decisions can cause traffic to shift rapidly from one link to another, leading to oscillations. In practice, most modern routing algorithms, such as OSPF and RIP, are load-insensitive; they use static link costs that do not depend on the current traffic load.
Question 13: What is a global routing algorithm for a network?
Answer: A global routing algorithm is a routing algorithm that has complete knowledge of the entire network topology and all link costs. It computes the least cost path from a source to a destination using this global information. Because it has a full view of the network, a global routing algorithm can make optimal routing decisions. The link-state algorithm is a classic example of a global routing algorithm. In a link-state algorithm, each router broadcasts information about its directly connected links to all other routers in the network, so that every router can construct a complete map of the network and then run a shortest-path algorithm such as Dijkstra’s algorithm to compute the least cost paths. Global routing algorithms are also sometimes referred to as centralized algorithms when the computation is performed at a central location, but the term “global” emphasizes that the algorithm uses global state information.
Question 14: Why is a global routing algorithm referred to as a link-state algorithm?
Answer: A global routing algorithm is referred to as a link-state algorithm because each router in the network broadcasts the state of its directly connected links to all other routers. The “link state” refers to information about the status and cost of each link. In a link-state algorithm, every router periodically sends link-state advertisements that describe its links and their costs. These advertisements are flooded throughout the network, so that every router receives them and can build a complete map of the network topology. Once a router has the complete map, it can run a shortest-path algorithm to compute the least cost paths to all destinations. The term “link-state” distinguishes this approach from distance-vector algorithms, in which routers exchange information about distances to destinations rather than the state of links.
Question 15: What are the differences between distance-vector algorithms and link-state algorithms?
Answer: Distance-vector algorithms and link-state algorithms differ in several key ways. First, in terms of information exchanged: distance-vector algorithms exchange distance vectors with neighbors, where each vector contains the estimated cost to all destinations; link-state algorithms flood link-state advertisements containing information about directly connected links to all routers in the network. Second, in terms of knowledge: distance-vector algorithms are decentralized, as each router only knows the distances reported by its neighbors and does not have a complete map of the network; link-state algorithms are global, as each router builds a complete map of the network topology. Third, in terms of convergence: link-state algorithms generally converge faster and are less prone to routing loops; distance-vector algorithms can suffer from slow convergence, routing loops, and the count-to-infinity problem. Fourth, in terms of computational complexity: link-state algorithms use Dijkstra’s algorithm, which has a complexity of O(n^2) or O(n log n) with efficient data structures, where n is the number of nodes; distance-vector algorithms use the Bellman-Ford equation, which is simpler but can be slower to converge. Finally, in terms of scalability: link-state algorithms require more memory and processing power because each router must store the entire network topology, while distance-vector algorithms require less memory but may generate more routing traffic.
Question 16: How are link cost changes and link failures handled in the distance-vector algorithm?
Answer: In the distance-vector algorithm, link cost changes and link failures are handled through the exchange of updated distance vectors between neighbors. When a router detects a change in the cost of one of its directly connected links, or when a link fails, it updates its own distance vector to reflect the new cost. If the cost decreases, the router can quickly propagate the good news to its neighbors, and the network converges rapidly. However, if the cost increases or a link fails, the router may need to inform its neighbors, and the neighbors may need to update their distance vectors. This process can lead to problems such as routing loops and the count-to-infinity problem. To mitigate these issues, techniques such as poisoned reverse are used, where a router advertises an infinite distance to a neighbor for a destination that the router reaches through that neighbor. This helps prevent two-node routing loops. Despite these techniques, distance-vector algorithms can still converge slowly in the presence of large cost increases or multiple link failures.
Question 17: What is a routing loop?
Answer: A routing loop is a situation in which a packet is forwarded repeatedly between two or more routers without ever reaching its destination. Routing loops occur when routing tables contain inconsistent or incorrect information, causing routers to forward packets back and forth along a cycle. In distance-vector routing, routing loops can occur during periods of slow convergence, especially after a link failure or a cost increase. For example, if router A believes it can reach a destination through router B, and router B believes it can reach the same destination through router A, then packets destined for that destination will loop between A and B. Routing loops lead to wasted bandwidth, increased delay, and potentially severe congestion. Techniques such as split horizon, poisoned reverse, and triggered updates are used to prevent or mitigate routing loops.
Question 18: What is the count-to-infinity problem in distance-vector routing?
Answer: The count-to-infinity problem is a specific type of routing loop that occurs in distance-vector routing when a link fails or its cost increases. In this problem, routers gradually increase their estimated distance to a destination as they exchange outdated information, and the distance counts up toward infinity. For example, consider three routers A, B, and C in a line, where A is connected to B and B is connected to C. If the link between B and C fails, B may learn from A that A can reach C, even though A’s path to C goes through B. B then updates its distance to C based on A’s information, and A updates its distance based on B’s information, and so on. The distances slowly increase, and it can take many iterations for the routers to realize that C is actually unreachable. The count-to-infinity problem can be mitigated by techniques such as poisoned reverse, where a router advertises an infinite distance to a neighbor for a destination that the router reaches through that neighbor. However, poisoned reverse does not solve all cases, especially those involving more than two routers.
Question 19: What is adding poisoned reverse to the distance-vector algorithm?
Answer: Adding poisoned reverse to the distance-vector algorithm is a technique used to prevent routing loops, particularly two-node loops. In the basic distance-vector algorithm, a router advertises its distance to all destinations to all its neighbors. With poisoned reverse, if router A routes packets to destination X through neighbor B, then A advertises to B that its distance to X is infinity. This tells B that A does not have a valid path to X except through B, so B should not try to reach X through A. In other words, A “poisons” the reverse path to B. This prevents the situation where B might incorrectly believe it can reach X through A, which would create a loop. Poisoned reverse is effective for preventing loops between two nodes, but it does not prevent loops involving three or more nodes. It is typically used in conjunction with other techniques, such as triggered updates and split horizon, to improve the convergence and stability of distance-vector routing.
Question 20: What is the comparison between distance-vector and link-state routing algorithms?
Answer: Distance-vector and link-state routing algorithms can be compared across several dimensions. In terms of information exchanged, distance-vector algorithms exchange distance vectors with neighbors, while link-state algorithms flood link-state advertisements to all routers. In terms of knowledge, distance-vector algorithms are decentralized and each router knows only what its neighbors tell it, while link-state algorithms are global and each router builds a complete map of the network. In terms of convergence, link-state algorithms converge faster and are less prone to loops, while distance-vector algorithms can converge slowly and suffer from count-to-infinity. In terms of complexity, link-state algorithms use Dijkstra’s algorithm and require more memory and processing, while distance-vector algorithms use the Bellman-Ford equation and are simpler but may generate more routing traffic. In terms of scalability, link-state algorithms are generally more scalable for large networks, while distance-vector algorithms are better suited for smaller networks. In terms of robustness, link-state algorithms are more robust to link failures, while distance-vector algorithms may experience temporary loops. Overall, both types of algorithms have their strengths and weaknesses, and the choice between them depends on the specific requirements of the network.
Section 2: Specific Routing Algorithms and Protocols
Question 21: What is hot potato routing?
Answer: Hot potato routing is a routing strategy in which a router forwards a packet to the next hop that is closest to the router, without regard for whether that next hop is on the least cost path to the packet’s final destination. The idea is to get the packet out of the router as quickly as possible, like passing a hot potato. Hot potato routing is often used in the context of inter-domain routing between autonomous systems. When a router in one autonomous system needs to forward a packet to a destination in another autonomous system, it may have multiple gateway routers that can reach the destination. Instead of choosing the gateway that provides the least cost path to the destination, the router chooses the gateway that is closest to itself, based on intra-domain routing costs. This minimizes the use of the local autonomous system’s resources, but it may result in a suboptimal end-to-end path. Hot potato routing is also known as deflection routing.
Question 22: What is shortest path first routing?
Answer: Shortest path first routing is a routing strategy in which each router computes the shortest path to each destination and forwards packets along that path. The “shortest path” is typically defined in terms of a cost metric, such as hop count, delay, or bandwidth. Shortest path first routing is the basis for link-state routing algorithms such as OSPF, which stands for Open Shortest Path First. In OSPF, each router builds a complete map of the network topology and then runs Dijkstra’s algorithm to compute the shortest path tree from itself to all other routers. The routing table is then populated with the next hop for each destination based on this tree. Shortest path first routing ensures that packets follow the least cost path, but it can lead to congestion if many packets are sent along the same path. To mitigate this, some protocols support equal-cost multipath, where traffic can be split across multiple shortest paths.
Question 23: What is least loaded path routing?
Answer: Least loaded path routing is a routing strategy in which a router chooses the path that is currently the least congested or least loaded. The load on a path can be measured in terms of the number of packets being transmitted, the utilization of the links, or the queueing delay. The goal is to balance the traffic across the network and avoid sending packets through congested areas. Least loaded path routing is a type of load-sensitive routing, as it takes into account the current traffic conditions. However, it can suffer from instability and oscillations, because as soon as a path becomes less loaded, more traffic is directed to it, which may cause it to become congested again. In practice, least loaded path routing is not widely used in large networks due to these challenges, but it is sometimes used in specific contexts, such as in data center networks or in adaptive routing for interconnection networks.
Question 24: What is maximum free circuit routing?
Answer: Maximum free circuit routing is a routing strategy used in circuit-switched networks. In a circuit-switched network, a dedicated circuit or path must be established between the source and destination before communication can begin. Maximum free circuit routing selects the path that has the maximum amount of free capacity or the maximum number of free circuits available. The goal is to maximize the probability that the call or connection can be established successfully and to balance the load across the network. This strategy is particularly useful in networks where calls have varying bandwidth requirements and where blocking probability is a concern. By choosing the path with the most free circuits, the network can reduce the likelihood of blocking future calls. Maximum free circuit routing is one of several routing strategies used in circuit-switched networks, along with fixed routing and alternate routing.
Question 25: What are gateway routers?
Answer: Gateway routers are routers that connect one network to another, typically connecting an autonomous system to the rest of the Internet. In the context of inter-domain routing, a gateway router is a router that sits at the edge of an autonomous system and communicates with gateway routers in other autonomous systems. Gateway routers are responsible for exchanging routing information between autonomous systems using an exterior gateway protocol such as BGP. They also forward packets between the internal network and external networks. A gateway router may also perform network address translation, firewall functions, or other security functions. In a home network, the gateway router is the device that connects the home network to the Internet service provider. In an enterprise network, gateway routers connect the enterprise network to the Internet and to other enterprise networks.
Question 26: What is the intra-autonomous routing protocol?
Answer: An intra-autonomous routing protocol is a routing protocol used within a single autonomous system to determine how packets are routed between routers inside that autonomous system. An autonomous system is a group of networks and routers under the control of a single administrative entity, such as an Internet service provider, a large corporation, or a university. Intra-autonomous routing protocols are also known as interior gateway protocols. Examples include RIP, OSPF, and IS-IS. These protocols are used to exchange routing information between routers within the autonomous system and to compute the least cost paths between internal destinations. They are designed to be scalable and efficient for the size and complexity of the autonomous system. Intra-autonomous routing protocols differ from inter-autonomous routing protocols, such as BGP, which are used to exchange routing information between autonomous systems.
Question 27: What is hierarchical routing?
Answer: Hierarchical routing is a routing approach in which the network is divided into multiple levels or regions, and routing is performed at each level. In a hierarchical routing architecture, routers within a region know the detailed topology of their own region but only know summary information about other regions. This reduces the size of routing tables and the amount of routing information that must be exchanged, making the network more scalable. Hierarchical routing is used in large networks such as the Internet, where the network is divided into autonomous systems, and within each autonomous system, it may be further divided into areas. For example, OSPF supports hierarchical routing by dividing an autonomous system into areas, with area border routers summarizing information between areas. Hierarchical routing helps to control the growth of routing tables and to localize the impact of topology changes.
Question 28: What are the problems with link-state and distance-vector routing?
Answer: Link-state and distance-vector routing algorithms each have their own problems. Link-state routing can be computationally intensive because each router must run Dijkstra’s algorithm over the entire network topology, which can be expensive in large networks. It also requires significant memory to store the link-state database, and the flooding of link-state advertisements can consume bandwidth. Distance-vector routing can suffer from slow convergence, routing loops, and the count-to-infinity problem, especially after link failures or cost increases. It can also generate a lot of routing traffic as routers exchange distance vectors periodically. Both types of algorithms can be vulnerable to security attacks, such as the injection of false routing information. Additionally, both can suffer from congestion if many packets are routed along the same least cost path, although this is more of a limitation of the routing metric than the algorithm itself. Techniques such as hierarchical routing, load balancing, and authentication are used to mitigate these problems.
Section 3: Circuit-Switched Routing and Network Layer Addressing
Question 29: What are circuit-switched routing algorithms?
Answer: Circuit-switched routing algorithms are algorithms used in circuit-switched networks to establish a dedicated path or circuit between the source and destination before communication begins. In a circuit-switched network, resources such as bandwidth or time slots are reserved along the path for the duration of the connection. Circuit-switched routing algorithms are responsible for selecting the path that will be used for the circuit. Common strategies include fixed routing, where a single permanent path is used; alternate routing, where a set of precomputed alternate paths is available if the primary path is blocked; and adaptive routing, where the path is chosen dynamically based on current network conditions. Examples of circuit-switched routing strategies include maximum free circuit routing and least loaded path routing. Circuit-switched routing is used in traditional telephone networks and in some optical networks.
Question 30: Based on the IPv4 addressing scheme, what is the maximum number of hosts that can be addressed?
Answer: Based on the IPv4 addressing scheme, the maximum number of hosts that can be addressed is 2 to the power of 32, which is approximately 4.3 billion addresses. This is because IPv4 addresses are 32 bits long, and each bit can be either 0 or 1, giving 2^32 possible combinations. However, not all of these addresses are available for hosts. Some addresses are reserved for special purposes, such as network addresses, broadcast addresses, loopback addresses, and multicast addresses. Additionally, the original classful addressing scheme allocated addresses in blocks, which led to inefficient utilization and premature exhaustion of the address space. Classless Interdomain Routing was introduced to allow more flexible allocation of addresses and to slow down the exhaustion of IPv4 addresses. Despite these measures, the depletion of IPv4 addresses has led to the adoption of IPv6, which uses 128-bit addresses and provides a vastly larger address space.
Question 31: What is a network address?
Answer: A network address is an address that identifies a network rather than a specific host. In IPv4, a network address is formed by setting all host bits to zero in an IP address. For example, if the subnet mask is 255.255.255.0 and the IP address is 192.168.1.100, the network address is 192.168.1.0. The network address is used by routers to forward packets to the correct network. When a router receives a packet, it examines the destination IP address and compares it to the network addresses in its routing table to determine the next hop. The network address is also used in routing protocols to advertise networks. A network address cannot be assigned to a host because it is used to represent the network itself. Similarly, the broadcast address for a network is formed by setting all host bits to one, and it is used to send a packet to all hosts on that network.
Question 32: What is a network mask?
Answer: A network mask, also known as a subnet mask, is a 32-bit number that is used to divide an IP address into the network portion and the host portion. The network mask consists of a sequence of ones followed by a sequence of zeros. The ones indicate the bits that belong to the network portion, and the zeros indicate the bits that belong to the host portion. For example, the subnet mask 255.255.255.0 in binary is 11111111.11111111.11111111.00000000, which means that the first 24 bits are the network portion and the last 8 bits are the host portion. By performing a bitwise AND operation between an IP address and the subnet mask, a router or host can determine the network address. The subnet mask is essential for routing because it allows devices to determine whether a destination IP address is on the same local network or on a remote network. It is also used in Classless Interdomain Routing to specify the prefix length of a network.
Question 33: What is classful addressing?
Answer: Classful addressing is an early method of IP address allocation that divided the IPv4 address space into five classes: A, B, C, D, and E. Class A addresses have the first bit set to 0 and use the first 8 bits for the network portion and the remaining 24 bits for the host portion, allowing for a small number of networks with a large number of hosts. Class B addresses have the first two bits set to 10 and use the first 16 bits for the network portion and the remaining 16 bits for the host portion. Class C addresses have the first three bits set to 110 and use the first 24 bits for the network portion and the remaining 8 bits for the host portion, allowing for many networks with a small number of hosts. Class D addresses are used for multicast, and Class E addresses are reserved for experimental use. Classful addressing was replaced by Classless Interdomain Routing because it was inefficient and led to rapid depletion of the address space.
Question 34: What are the differences between class A, B, C, and D addresses?
Answer: Class A, B, C, and D addresses differ in their structure and purpose. Class A addresses have the first bit set to 0, with 8 bits for the network portion and 24 bits for the host portion. They support up to 126 networks and over 16 million hosts per network. Class B addresses have the first two bits set to 10, with 16 bits for the network portion and 16 bits for the host portion. They support approximately 16,000 networks and about 65,000 hosts per network. Class C addresses have the first three bits set to 110, with 24 bits for the network portion and 8 bits for the host portion. They support over 2 million networks and 254 hosts per network. Class D addresses have the first four bits set to 1110 and are used for multicast groups, not for identifying individual hosts or networks. Class E addresses have the first four bits set to 1111 and are reserved for experimental use. The classful system was replaced by CIDR, which allows for more flexible allocation of addresses.
Question 35: Why are the four address classes no longer formally part of the IP addressing architecture?
Answer: The four address classes are no longer formally part of the IP addressing architecture because they were inefficient and led to rapid depletion of the IPv4 address space. The classful system allocated addresses in fixed-size blocks, which did not match the actual needs of most organizations. For example, a small organization that needed only a few dozen addresses would be assigned a Class C block of 256 addresses, wasting many addresses. A large organization that needed more than 254 addresses would be assigned a Class B block of 65,536 addresses, which was often far more than needed. This inflexibility led to inefficient utilization of the address space and accelerated the exhaustion of IPv4 addresses. Classless Interdomain Routing was introduced to replace the classful system. CIDR allows addresses to be allocated in variable-sized blocks, known as prefixes, which can be sized to match the actual needs of the organization. This has greatly improved the efficiency of address allocation and extended the life of IPv4.
Question 36: What is Classless Interdomain Routing?
Answer: Classless Interdomain Routing, or CIDR, is a method of IP address allocation and routing that replaces the older classful addressing system. CIDR allows IP addresses to be allocated in variable-length prefixes, rather than fixed-size classes. A CIDR prefix is written as an IP address followed by a slash and a number indicating the length of the prefix. For example, 192.168.1.0/24 indicates a prefix of 24 bits, which corresponds to a subnet mask of 255.255.255.0. CIDR enables more efficient use of the IPv4 address space by allowing blocks of addresses to be sized according to need. It also supports route aggregation, where multiple contiguous prefixes can be summarized into a single, shorter prefix, reducing the size of routing tables. CIDR is used in both intra-domain and inter-domain routing, and it is a key component of the modern Internet architecture.
Question 37: What is subnetting?
Answer: Subnetting is the process of dividing a single IP network into multiple smaller networks, called subnets. Subnetting is used to improve network performance, enhance security, and simplify management. When a network is subnetted, the host portion of the IP address is divided into a subnet portion and a host portion. This is done by extending the network mask with additional bits. For example, a network with the address 192.168.1.0/24 can be divided into two subnets by using a 25-bit mask, such as 192.168.1.0/25 and 192.168.1.128/25. Each subnet can then be treated as a separate network, with its own range of host addresses. Subnetting allows a network administrator to create logical groupings of devices, control broadcast traffic, and apply different security policies to different subnets. It also helps to conserve IP addresses by allowing a large network to be divided into smaller, more manageable pieces.
Question 38: What is the Dynamic Host Configuration Protocol?
Answer: The Dynamic Host Configuration Protocol, or DHCP, is a network protocol used to automatically assign IP addresses and other network configuration parameters to devices on a network. When a device connects to a network, it can use DHCP to request an IP address from a DHCP server. The DHCP server then assigns an available IP address from a pool of addresses and provides additional information such as the subnet mask, default gateway, and DNS server addresses. DHCP eliminates the need for manual configuration of IP addresses, which is especially useful in large networks or networks with many mobile devices. DHCP operates at the application layer and uses UDP for transport. It is a client-server protocol, with the device acting as a DHCP client and the server providing the configuration. DHCP supports lease times, so that addresses can be reclaimed and reused when devices leave the network.
Question 39: What is route aggregation or route summarization and how does it work?
Answer: Route aggregation, also known as route summarization, is the process of combining multiple contiguous IP prefixes into a single, shorter prefix that represents them all. This reduces the number of routes that must be advertised and stored in routing tables, which improves scalability and reduces routing traffic. Route aggregation works by finding a common prefix that covers all the individual prefixes. For example, if a router has routes for 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24, and 192.168.3.0/24, it can aggregate them into a single route for 192.168.0.0/22, because the first 22 bits are the same for all four prefixes. When a router advertises the aggregated route, other routers only need to know about the single summary route rather than the four individual routes. This reduces the size of routing tables and the amount of routing information exchanged. Route aggregation is a key benefit of CIDR and is widely used in the Internet to keep routing tables manageable.
Question 40: How does an ISP get a block of addresses?
Answer: An Internet Service Provider, or ISP, gets a block of IP addresses by requesting them from a Regional Internet Registry, or RIR. There are five RIRs in the world: ARIN for North America, RIPE NCC for Europe and the Middle East, APNIC for Asia and the Pacific, LACNIC for Latin America and the Caribbean, and AFRINIC for Africa. The RIRs allocate blocks of IP addresses to ISPs and other organizations based on demonstrated need. The RIRs, in turn, receive their address blocks from the Internet Assigned Numbers Authority, or IANA, which is responsible for the global coordination of IP address allocation. When an ISP requests a block of addresses, it must provide justification for the request, such as the number of customers it serves and its projected growth. The RIR then allocates a block of addresses to the ISP, which can then assign individual addresses or sub-blocks to its customers. The process is governed by policies developed by the Internet community through the RIRs.
Question 41: Which organization is responsible for the management of IP addresses?
Answer: The organization responsible for the global management of IP addresses is the Internet Assigned Numbers Authority, or IANA. IANA is responsible for coordinating the global pool of IP addresses and AS numbers, and for allocating blocks of addresses to the Regional Internet Registries. The RIRs are responsible for allocating addresses within their respective regions. The RIRs are: ARIN, RIPE NCC, APNIC, LACNIC, and AFRINIC. These organizations develop and implement policies for address allocation based on community consensus. At the local level, ISPs and other organizations are responsible for assigning addresses to their customers and devices. The overall system is designed to ensure that IP addresses are allocated efficiently and fairly, and that the Internet continues to function smoothly. With the exhaustion of IPv4 addresses, IANA and the RIRs are also responsible for managing the transition to IPv6.
Section 4: IP Datagram, Transport, and ICMP
Question 42: How is an IP datagram formatted?
Answer: An IP datagram is formatted with a header and a payload. The IPv4 header consists of several fields, including the version, which indicates the IP version; the header length, which specifies the length of the header; the type of service, which is used for quality of service; the total length, which is the total length of the datagram; the identification, flags, and fragment offset, which are used for fragmentation; the time to live, which limits the lifetime of the datagram; the protocol, which indicates the transport layer protocol; the header checksum, which is used for error detection; the source IP address; the destination IP address; and options, which are optional. The payload contains the data from the transport layer, such as a TCP segment or UDP datagram. The IPv6 header is different, with a simplified format and a fixed length of 40 bytes, and it uses extension headers for options.
Question 43: How is an IP datagram transported from source to destination?
Answer: An IP datagram is transported from source to destination through a series of routers. When a host sends an IP datagram, it first determines whether the destination is on the same local network or on a remote network by comparing the destination IP address with its own network mask. If the destination is on the same network, the host sends the datagram directly to the destination using the destination’s MAC address. If the destination is on a remote network, the host sends the datagram to its default gateway, which is a router on the local network. The router then examines the destination IP address and consults its routing table to determine the next hop. The router forwards the datagram to the next hop, and this process repeats until the datagram reaches its destination. At each hop, the datagram’s time to live is decremented, and if it reaches zero, the datagram is discarded and an ICMP message is sent back to the source. The datagram may also be fragmented if it is too large for a particular link.
Question 44: What is the maximum transfer unit?
Answer: The maximum transfer unit, or MTU, is the largest size of a packet that can be transmitted over a network link. The MTU is determined by the link-layer protocol and the physical medium. For example, the MTU for Ethernet is typically 1500 bytes. If an IP datagram is larger than the MTU of a link, it must be fragmented into smaller pieces before it can be transmitted. Fragmentation can occur at the source host or at an intermediate router. When a datagram is fragmented, each fragment is a separate IP datagram with its own header, and the fragments are reassembled at the destination. The MTU is important because it affects the efficiency of data transmission. If the MTU is too small, there is more overhead due to headers. If the MTU is too large, the datagram may need to be fragmented, which also adds overhead and can increase the risk of packet loss. Path MTU discovery is a technique used to determine the smallest MTU along a path so that fragmentation can be avoided.
Question 45: What is the Internet Control Message Protocol used for?
Answer: The Internet Control Message Protocol, or ICMP, is used for error reporting and diagnostic functions in IP networks. ICMP is used by routers and hosts to send error messages and operational information. For example, when a router cannot forward a datagram, it sends an ICMP message back to the source to inform it of the problem. ICMP is also used for network diagnostics, such as the ping command, which uses ICMP echo request and echo reply messages to test connectivity, and the traceroute command, which uses ICMP time exceeded messages to discover the path to a destination. ICMP messages are encapsulated in IP datagrams and are identified by the protocol number 1 in the IP header. ICMP is an integral part of the IP protocol suite and is essential for the reliable operation of IP networks. It is important to note that ICMP is not used for exchanging routing information; that is the role of routing protocols.
Section 5: Router Structure and Operation
Question 46: What is the structure of a router?
Answer: A router consists of four main components: input ports, output ports, a switching fabric, and a routing processor. The input ports receive incoming packets and perform several functions, including physical layer termination, data link layer processing, and lookup and forwarding. The lookup function uses the router’s forwarding table to determine the output port for each packet. The switching fabric connects the input ports to the output ports and moves packets from input to output. It can be implemented using various technologies, such as shared memory, a shared bus, or a crossbar switch. The output ports store packets before they are transmitted on the outgoing link and perform data link and physical layer processing. The routing processor runs the routing protocols, maintains the routing table, and computes the forwarding table. It also handles other control functions, such as network management and error handling. The router may also have a queueing mechanism to handle congestion.
Question 47: How do routers work?
Answer: Routers work by forwarding packets from an input link to an appropriate output link based on the destination IP address. When a packet arrives at an input port, the router extracts the destination IP address from the packet header and looks it up in its forwarding table. The forwarding table maps destination prefixes to output ports. The router then uses the switching fabric to move the packet to the correct output port. At the output port, the packet is queued if necessary and then transmitted on the outgoing link. The forwarding table is computed by the routing processor based on the routing table, which is maintained by routing protocols. The router also performs other functions, such as decrementing the time to live, checking the header checksum, and generating ICMP error messages if necessary. Routers operate at the network layer of the OSI model and are essential for connecting different networks and for routing traffic across the Internet.
Question 48: What is a default router?
Answer: A default router, also known as a default gateway, is a router that is used when no other route matches the destination IP address of a packet. When a host needs to send a packet to a destination that is not on its local network and it does not have a specific route for that destination, it sends the packet to its default router. The default router then forwards the packet based on its own routing table. The default router is typically the router that connects the local network to the rest of the Internet or to a larger corporate network. In a host’s configuration, the default router is specified by its IP address. The default route in a routing table is often represented as 0.0.0.0/0, which matches all destinations. The default router is essential for enabling hosts to communicate with devices on other networks without having to know the full topology of the network.
Question 49: What is a first-hop router?
Answer: A first-hop router is the first router that a packet encounters when it leaves the source host’s local network. It is the router to which the source host sends packets destined for remote networks. The first-hop router is also known as the default gateway if it is the router that the host uses for all off-network traffic. The first-hop router is responsible for forwarding the packet toward its destination based on the destination IP address. It may also perform other functions, such as network address translation, firewall filtering, and quality of service. In a network with multiple routers, the first-hop router is the one that is directly connected to the host’s subnet. The term “first-hop” is often used in the context of routing protocols and network design to refer to the router that is closest to the source host.
Question 50: What is a source router?
Answer: A source router is the router that is closest to the source host in a network. It is the first router that handles the packet after it leaves the source host. The source router is responsible for determining the initial path for the packet and forwarding it toward its destination. In some contexts, the term “source router” may be used to refer to the router that originates routing information for a particular network. For example, in multicast routing, a source router is the router that is directly connected to the source of a multicast stream. The source router is responsible for forwarding multicast packets into the multicast distribution tree. In general, the source router plays a key role in the routing process by making the first routing decision for a packet.
Question 51: What is a destination router?
Answer: A destination router is the router that is closest to the destination host in a network. It is the last router that handles the packet before it is delivered to the destination host. The destination router is responsible for forwarding the packet to the destination host on the local network. It uses the destination IP address to determine which host on the local network should receive the packet, and it may use ARP to find the MAC address of the destination host. In some contexts, the term “destination router” may be used to refer to the router that is responsible for a particular destination network. For example, in multicast routing, a destination router is a router that has receivers for a multicast group on its local network. The destination router is responsible for delivering multicast packets to those receivers.
Question 52: What is a neighbor of a node in a graph?
Answer: A neighbor of a node in a graph is another node that is directly connected to it by an edge. In the context of network routing, a neighbor of a router is another router that is directly connected to it by a communication link. Neighbors exchange routing information with each other, and this information is used to compute paths through the network. In a distance-vector routing algorithm, a router only knows the distances to its neighbors and the distances that its neighbors report to other destinations. In a link-state routing algorithm, a router floods information about its links to all other routers, but it only has direct knowledge of its own links and their costs. The concept of a neighbor is fundamental to many routing algorithms, as routing information typically propagates from one neighbor to another.
Question 53: What is a path in a graph?
Answer: A path in a graph is a sequence of nodes and edges that connects a source node to a destination node. In the context of network routing, a path is the sequence of routers and links that a packet traverses from its source to its destination. The cost of a path is the sum of the costs of the edges along the path. A path is said to be simple if it does not repeat any nodes. A path is said to be a cycle if it starts and ends at the same node. In routing, the goal is often to find the least cost path or the shortest path between two nodes. The concept of a path is central to routing algorithms, as they are designed to find the best path according to some metric.
Question 54: What is a link-state broadcasting algorithm?
Answer: A link-state broadcasting algorithm is an algorithm used in link-state routing to distribute link-state information to all routers in the network. In a link-state routing protocol, each router periodically generates a link-state advertisement that describes the state of its directly connected links, including the cost of each link. The link-state broadcasting algorithm is responsible for flooding these advertisements to all other routers in the network. This is typically done using a reliable flooding mechanism, where each router forwards the advertisement to all its neighbors except the one from which it received the advertisement. To prevent infinite loops, each advertisement is assigned a sequence number, and routers only accept advertisements with newer sequence numbers. The link-state broadcasting algorithm ensures that every router receives a consistent view of the network topology, which is necessary for the link-state routing algorithm to compute correct paths.
Question 55: What is the distance-vector routing algorithm?
Answer: The distance-vector routing algorithm is a decentralized routing algorithm in which each router maintains a vector of estimated distances to all destinations in the network. The distance vector is a set of entries, one for each destination, where each entry contains the cost to reach that destination. Initially, each router knows only the costs to its directly connected neighbors and sets the cost to all other destinations to infinity. Periodically, each router sends its distance vector to its neighbors. When a router receives a distance vector from a neighbor, it uses the Bellman-Ford equation to update its own distance vector. The Bellman-Ford equation states that the cost to a destination through a neighbor is the cost to the neighbor plus the neighbor’s reported cost to the destination. If this sum is less than the router’s current cost to the destination, the router updates its cost and records the neighbor as the next hop. This process iterates until the distance vectors converge and no more updates occur. The distance-vector algorithm is simple and requires little processing power, but it can suffer from slow convergence and routing loops.
Question 56: What is the distance vector?
Answer: A distance vector is a data structure used in distance-vector routing algorithms. It is a vector or array that contains, for each destination in the network, the current estimated cost to reach that destination. Each router maintains its own distance vector. The distance vector is exchanged with neighboring routers so that they can update their own distance vectors. The distance vector typically includes entries for all known destinations, including the router’s directly connected networks and remote networks. The cost metric used in the distance vector can be hop count, delay, or another metric. The distance vector is updated using the Bellman-Ford equation when a router receives a distance vector from a neighbor. The distance-vector algorithm is also known as the Bellman-Ford algorithm or the Ford-Fulkerson algorithm.
Question 57: What is the global state information in routing?
Answer: Global state information in routing refers to complete knowledge of the entire network topology and all link costs. A routing algorithm that uses global state information has a full view of the network and can compute the least cost paths between all pairs of nodes. Link-state routing algorithms are examples of algorithms that use global state information. In a link-state algorithm, each router receives link-state advertisements from all other routers, which contain information about the state and cost of each link. The router then constructs a complete graph of the network and runs a shortest-path algorithm such as Dijkstra’s algorithm to compute the least cost paths. The advantage of using global state information is that the routing decisions can be optimal. The disadvantage is that it requires more memory and processing power, and the flooding of link-state information can consume network bandwidth.
Question 58: What is the link-state algorithm?
Answer: The link-state algorithm is a global routing algorithm that uses link-state information to compute least cost paths. In a link-state algorithm, each router is responsible for discovering the state of its directly connected links, including the cost of each link. The router then creates a link-state advertisement containing this information and floods it to all other routers in the network. As a result, every router receives link-state advertisements from all other routers and can build a complete map of the network topology. Once the map is built, each router runs a shortest-path algorithm, typically Dijkstra’s algorithm, to compute the least cost paths from itself to all other destinations. The results are used to populate the routing table. Link-state algorithms converge quickly and are less prone to routing loops than distance-vector algorithms. Examples of link-state routing protocols include OSPF and IS-IS.
Question 59: What is the link cost?
Answer: Link cost is a metric used in routing algorithms to represent the cost of transmitting data over a communication link. The link cost can be defined in various ways depending on the routing protocol and the network’s requirements. Common metrics include hop count, where each link has a cost of one; delay, where the cost is based on the time it takes for a packet to traverse the link; bandwidth, where the cost is inversely related to the link’s capacity; and monetary cost, where the cost reflects the expense of using the link. The link cost is used by routing algorithms to compute the least cost path between a source and a destination. In link-state routing, the link cost is included in the link-state advertisements that are flooded throughout the network. In distance-vector routing, the link cost is used by a router to update its distance vector when it receives information from a neighbor.
Question 60: What is the least cost path in a graph?
Answer: The least cost path in a graph is the path between two nodes that has the smallest total cost, where the total cost is the sum of the costs of the edges along the path. The least cost path is also known as the shortest path when all edge costs are equal. Finding the least cost path is a fundamental problem in routing, and many routing algorithms are designed to compute least cost paths. For example, Dijkstra’s algorithm is used in link-state routing to find the least cost paths from a source to all destinations. The Bellman-Ford equation is used in distance-vector routing to iteratively compute least cost paths. The least cost path depends on the link costs, which can be static or dynamic. If link costs change, the least cost path may also change, and the routing algorithm must recompute the paths.
Question 61: What is the shortest path in a graph?
Answer: The shortest path in a graph is the path between two nodes that has the fewest number of edges or hops. In a graph where each edge has a cost of one, the shortest path is also the least cost path. The shortest path is often used as a simple routing metric because it is easy to compute and understand. However, in networks where link costs vary, the shortest path may not be the best path in terms of delay, bandwidth, or other metrics. The shortest path can be found using algorithms such as breadth-first search or Dijkstra’s algorithm when all edge costs are equal. In routing, the term “shortest path” is sometimes used interchangeably with “least cost path,” but it specifically refers to minimizing the number of hops.
Question 62: What is the Bellman-Ford equation?
Answer: The Bellman-Ford equation is a fundamental equation used in distance-vector routing algorithms to compute the least cost path from a router to a destination. The equation states that the cost from router A to destination X through neighbor B is equal to the cost from A to B plus the cost from B to X. In mathematical terms, if d(A, X) is the cost from A to X, and c(A, B) is the cost of the link from A to B, then d(A, X) = min over all neighbors B of { c(A, B) + d(B, X) }. The router A uses this equation to update its distance vector when it receives a distance vector from neighbor B. If the computed cost is less than the current cost, A updates its distance vector and records B as the next hop for destination X. The Bellman-Ford equation is the basis for the distance-vector routing algorithm, and it is also used in other contexts, such as in the Bellman-Ford algorithm for finding shortest paths in graphs.
Question 63: What is the Dijkstra algorithm?
Answer: Dijkstra’s algorithm is a graph search algorithm that finds the least cost paths from a single source node to all other nodes in a weighted graph. It is used in link-state routing algorithms, such as OSPF, to compute the shortest path tree from a router to all destinations in the network. The algorithm works by maintaining a set of nodes whose least cost path from the source is known, and a set of tentative nodes. Initially, the source node has a cost of zero, and all other nodes have a cost of infinity. The algorithm repeatedly selects the node with the smallest tentative cost, adds it to the known set, and updates the tentative costs of its neighbors. This process continues until all nodes are in the known set. Dijkstra’s algorithm has a complexity of O(n^2) for a graph with n nodes, or O(n log n) with a priority queue. It is guaranteed to find the least cost paths if all edge costs are non-negative.
Question 64: What is the distance-vector algorithm’s count-to-infinity problem?
Answer: The count-to-infinity problem is a serious issue in distance-vector routing algorithms. It occurs when a link or router fails, and the routers gradually increase their estimated distance to the affected destination, counting up toward infinity. This happens because routers exchange outdated information and may incorrectly believe that a destination is reachable through a neighbor that actually routes through them. For example, if router A loses its direct connection to destination X, it may learn from router B that B can reach X. However, B’s path to X may go through A, creating a loop. As A and B exchange updates, their distances to X increase incrementally, and it may take many iterations for the algorithm to converge and realize that X is unreachable. The count-to-infinity problem can be mitigated by techniques such as poisoned reverse, split horizon, and triggered updates, but it is a fundamental limitation of distance-vector routing.
Question 65: What is the poisoned reverse technique?
Answer: The poisoned reverse technique is a method used in distance-vector routing to prevent two-node routing loops. In the basic distance-vector algorithm, a router advertises its distance to all destinations to all its neighbors. With poisoned reverse, if router A routes packets to destination X through neighbor B, then A advertises to B that its distance to X is infinity. This tells B that A does not have a valid path to X except through B, so B should not try to reach X through A. In other words, A “poisons” the reverse path to B. This prevents the situation where B might incorrectly believe it can reach X through A, which would create a loop. Poisoned reverse is effective for preventing loops between two nodes, but it does not prevent loops involving three or more nodes. It is typically used in conjunction with other techniques, such as triggered updates and split horizon, to improve the convergence and stability of distance-vector routing.
Question 66: What is the split horizon technique?
Answer: The split horizon technique is a method used in distance-vector routing to prevent routing loops. The basic idea is that a router should not advertise a route back to the neighbor from which it learned the route. For example, if router A learns a route to destination X from neighbor B, then A should not advertise that route back to B. This is because B already knows about the route, and advertising it back could create a loop. Split horizon is similar to poisoned reverse, but instead of advertising an infinite distance, the router simply omits the route from the advertisement sent to that neighbor. Split horizon is effective for preventing two-node loops, but like poisoned reverse, it does not prevent loops involving three or more nodes. It is often used together with poisoned reverse and triggered updates to improve the stability of distance-vector routing.
Question 67: What is the triggered update technique?
Answer: The triggered update technique is a method used in distance-vector routing to speed up convergence and reduce the likelihood of routing loops. In the basic distance-vector algorithm, routers send their distance vectors periodically, regardless of whether the network has changed. With triggered updates, a router sends an update immediately when it detects a change in its distance vector, such as a link failure or a cost change, rather than waiting for the next periodic update. This allows the change to propagate through the network more quickly, reducing the time during which routing loops can occur. Triggered updates are often used in conjunction with poisoned reverse and split horizon to improve the convergence and stability of distance-vector routing. However, triggered updates can increase the amount of routing traffic, especially if the network is unstable.
Question 68: What is the link-state advertisement?
Answer: A link-state advertisement, or LSA, is a message used in link-state routing protocols to describe the state of a router’s links. Each router periodically generates an LSA that contains information about its directly connected links, including the link identifiers, the cost of each link, and the state of each link. The LSA also includes a sequence number and the identity of the originating router. The LSA is flooded to all other routers in the network, so that every router can build a complete map of the network topology. The sequence number allows routers to determine whether an LSA is newer than the one they have, preventing old LSAs from being used. LSAs are used by link-state routing protocols such as OSPF and IS-IS. The flooding of LSAs is a key part of the link-state routing algorithm and ensures that all routers have a consistent view of the network.
Question 69: What is the forwarding table?
Answer: A forwarding table, also known as a forwarding information base, is a data structure used by a router to determine the output port for each incoming packet. The forwarding table contains entries that map destination prefixes to output ports. When a packet arrives at a router, the router extracts the destination IP address and looks it up in the forwarding table. The longest prefix match is used to find the most specific route for the destination. The forwarding table is computed by the routing processor based on the routing table, which is maintained by routing protocols. The forwarding table is optimized for fast lookup, often using specialized hardware such as content-addressable memory. The forwarding table is distinct from the routing table, which contains all routes learned by the router, including those that are not currently used. The forwarding table contains only the best routes for each destination.
Question 70: What is the routing table?
Answer: A routing table is a data structure maintained by a router that contains all the routes that the router has learned. Each route in the routing table includes the destination network, the next hop, the cost metric, and other information such as the outgoing interface. The routing table is populated by routing protocols, which exchange information with other routers to learn about the network topology. The router uses the routing table to compute the forwarding table, which is used for actual packet forwarding. The routing table may contain multiple routes to the same destination, learned from different routing protocols or with different metrics. The router selects the best route based on administrative distance and metric. The routing table is essential for the operation of the router and is updated dynamically as the network changes.