Internet Routing Flashcards
What is Internet routing?
Internet routing is the process of determining the path that data packets take from a source to a destination across networks. It involves selecting optimal routes based on algorithms and maintaining routing tables for forwarding data efficiently.
What is the difference between routing and forwarding?
Routing determines the overall end-to-end path that data packets follow through the network, while forwarding refers to the actual process of moving packets from one node to the next along the chosen path, based on the routing table.
What are the key components that make up the Internet?
The Internet consists of applications like browsers and Skype, computing devices like laptops and smartphones, networking devices such as routers and switches, physical media like fiber optics and copper cables, and protocols like TCP/IP that manage communication.
How are routing algorithms classified based on their scope?
Routing algorithms can be classified as global, where routers have a complete view of the network topology (like Link-State algorithms), or decentralized, where routers only know about their immediate neighbors (like Distance Vector algorithms).
How are routing algorithms classified based on their dynamics?
Routing algorithms can be static, where routes change infrequently, or dynamic, where routes adapt quickly to network changes through periodic updates or in response to link failures.
What are the characteristics of load-sensitive and load-insensitive routing algorithms?
Load-sensitive algorithms adjust routing decisions based on current network traffic conditions, while load-insensitive algorithms do not consider traffic load and make decisions based on fixed metrics.
What is Dijkstra’s Algorithm?
Dijkstra’s Algorithm is a Link-State routing algorithm that computes the shortest paths from a source node to all other nodes in a network. It uses a greedy approach and relies on each router having a complete view of the network.
What are the key steps of Dijkstra’s Algorithm?
First, initialize the source node’s distance to zero and all other nodes to infinity. Then, repeatedly select the node with the smallest tentative distance, update the distances of its neighbors if a shorter path is found, and continue until all nodes are processed.
What is the time complexity of Dijkstra’s Algorithm?
The time complexity of Dijkstra’s Algorithm is O(N²), where N represents the number of nodes in the network.
What is the Distance Vector (DV) Routing Algorithm?
The Distance Vector Routing Algorithm is a distributed algorithm where each router maintains a vector of distances to all other nodes, sharing this information with its neighbors to determine the shortest paths.
What are the key features of the Distance Vector Routing Algorithm?
It is distributed, meaning routers exchange information only with their direct neighbors; iterative, as updates continue until the network converges; and asynchronous, meaning routers update independently without a global clock.
What is the Bellman-Ford equation used in Distance Vector Routing?
The Bellman-Ford equation calculates the shortest distance from one node to another by considering the minimum cost of reaching a destination through all possible neighbors. The formula is D(G, H) = min {c(G, E) + D(E, H)}.
What is the Count-to-Infinity problem in Distance Vector Routing?
The Count-to-Infinity problem occurs when routers take a long time to detect that a route is no longer available, causing incorrect routing information to propagate through the network and leading to routing loops.
How does the Poisoned Reverse technique help mitigate the Count-to-Infinity problem?
In Poisoned Reverse, a router advertises an infinite cost for a route back to the neighbor from which it learned the route, preventing that neighbor from mistakenly routing traffic back through the original router, thereby avoiding loops.
Why is hierarchical routing necessary in large networks like the Internet?
Hierarchical routing is essential because the Internet is too large for flat routing. It reduces the size of routing tables, minimizes the overhead of control messages, and allows for administrative control within different regions called Autonomous Systems.
What is an Autonomous System (AS) in Internet routing?
An Autonomous System is a collection of IP networks under a single administrative domain that operates using a common routing policy. It allows for more efficient routing within and between different organizations.
What is RIP (Routing Information Protocol), and how does it work?
RIP is one of the earliest distance vector protocols. It uses hop count as a metric, with a maximum of 15 hops, and periodically exchanges routing information every 30 seconds between neighboring routers.
What is OSPF (Open Shortest Path First), and how does it function?
OSPF is a Link-State routing protocol where each router maintains a map of the network. Routers use Dijkstra’s algorithm to compute the shortest path tree to all destinations, and updates are triggered by network changes rather than periodic broadcasts.
What is BGP (Border Gateway Protocol), and what is its role in Internet routing?
BGP is the standard protocol for routing between Autonomous Systems on the Internet. It helps routers learn about reachability information for different networks, propagates this information across the Internet, and applies policies to control routing decisions.
What types of messages are exchanged in BGP?
BGP uses several message types: OPEN to establish connections, UPDATE to advertise or withdraw routes, KEEPALIVE to maintain the connection, and NOTIFICATION to report errors and terminate connections if needed.
How do Link-State and Distance Vector algorithms differ in terms of information sharing?
Link-State algorithms require routers to have a complete view of the network, sharing detailed topology information. In contrast, Distance Vector algorithms involve routers sharing only their distance vectors with immediate neighbors, without full knowledge of the entire network.
What are the main advantages of hierarchical routing?
Hierarchical routing reduces the size of routing tables, limits the volume of routing updates, allows for better scalability, and supports policy-based routing between different administrative domains.
How does a router update its Distance Vector in the DV algorithm?
A router updates its Distance Vector by applying the Bellman-Ford equation whenever it receives new distance information from its neighbors or when the cost of one of its direct links changes.
What happens during the convergence process of the Distance Vector algorithm?
During convergence, routers continuously exchange and update distance vectors until all routers in the network agree on the shortest paths to all destinations, resulting in stable routing tables.
What are the challenges of using Link-State algorithms in large, dynamic networks?
Link-State algorithms can face challenges such as slow response to rapid network changes, large memory requirements for maintaining full network topology, and high bandwidth usage for frequent link-state updates.
How does OSPF handle network changes more efficiently than RIP?
OSPF responds to network changes immediately by triggering updates only when changes occur, while RIP relies on periodic updates, which can lead to slower convergence in dynamic environments.
What is the role of gateway routers in hierarchical routing?
Gateway routers connect different Autonomous Systems and are responsible for handling both intra-AS and inter-AS routing, applying local routing policies and propagating routing information between networks.
Why is BGP considered policy-based routing?
BGP allows network administrators to define routing policies that influence how traffic flows between Autonomous Systems. It considers factors beyond just the shortest path, such as business agreements and security preferences.
How do routers in a Link-State protocol like OSPF maintain consistent routing tables?
Routers in OSPF flood the network with Link-State Advertisements (LSAs), ensuring all routers have the same network topology information. Each router independently computes the shortest paths using this consistent data.
