Chapter 5: Network Layer - Control Plane

What is the primary function of the network layer?

To forward packets from the router's input to the appropriate router output.

What are the two approaches to structuring the network control plane?

Per-router control and logically centralized control (software-defined networking).

In per-router control, where do routing algorithm components reside?

In each and every router.

What does a remote controller do in software-defined networking?

Computes and installs forwarding tables in routers.

What is the purpose of routing protocols?

To determine 'good' routes from sending hosts to receiving hosts through a network of routers.

What factors determine a 'good' route in routing protocols?

Least cost, fastest, and least congested routes.

What is represented by the graph G = (N,E) in routing?

N is the set of routers and E is the set of links connecting those routers.

What does the cost of a direct link between routers represent?

It is defined by the network operator and can be based on bandwidth or congestion.

What are the two classifications of routing algorithms?

Global (link state algorithms) and dynamic (distance vector algorithms).

What is Dijkstra's Link-State Routing Algorithm used for?

To compute least cost paths from a source node to all other nodes in the network.

What does the Bellman-Ford equation relate to in routing?

It is used in the Distance Vector Algorithm for determining the least-cost path.

What is the algorithm complexity of Dijkstra's Algorithm?

O(n^2) for n nodes, with more efficient implementations possible.

What can cause route oscillations in Dijkstra's Algorithm?

When link costs depend on traffic volume.

What is the initialization step in Dijkstra's Algorithm?

Setting the cost D(v) to the direct path cost for nodes adjacent to the source node.

What is the iterative process in Dijkstra's Algorithm?

Finding the node with the minimum cost not in the known set and updating costs for adjacent nodes.

What does the term 'N'' represent in Dijkstra's Algorithm?

The set of nodes whose least-cost path is known.

How does the Distance Vector Algorithm communicate routing information?

Through an iterative process of computation and exchange of information with neighbors.

What is the main difference between static and dynamic routing?

Static routing changes slowly over time, while dynamic routing changes more quickly in response to link cost changes.

What is the significance of the predecessor node p(v) in Dijkstra's Algorithm?

It indicates the previous node along the least-cost path from the source to node v.

What happens in the case of ties in Dijkstra's Algorithm?

Ties can be broken arbitrarily.

What is the message complexity in Dijkstra's Algorithm?

Each router must broadcast its link state information, leading to O(n^2) overall message complexity.

What is the role of link costs in routing?

Link costs can be inversely related to bandwidth or congestion, affecting route selection.

What does the term 'least-cost-path tree' refer to?

It is constructed by tracing predecessor nodes to identify the least-cost paths from the source.

What is the output of Dijkstra's Algorithm?

A forwarding table that indicates the best route from the source to each destination.

What is the purpose of periodic updates in dynamic routing?

To adjust routes based on changing link costs.

What is the main advantage of a logically centralized control plane?

It allows for more efficient management and configuration of network resources.

What is the impact of traffic volume on link costs?

Traffic volume can lead to dynamic changes in link costs, affecting routing decisions.

What is the Bellman-Ford equation used for in networking?

To calculate the least-cost path to a destination node.

What does Dx(y) represent in the context of the Distance Vector Algorithm?

The estimated least-cost path cost from node x to node y.

What is the key idea behind the Distance Vector Algorithm?

Each node periodically sends its own distance vector estimate to its neighbors.

What happens when a node receives a new distance vector estimate from a neighbor?

It updates its own distance vector using the Bellman-Ford equation.

What is the convergence condition for the Distance Vector estimates?

Under minor, natural conditions, the estimates converge to the actual least cost.

What triggers a local iteration in the Distance Vector Algorithm?

A change in local link cost or a distance vector update message from a neighbor.

What is the purpose of notifying neighbors in the Distance Vector Algorithm?

To inform them only when the distance vector changes.

What does the notation minv{cx,v + Dv(y)} signify?

It signifies the minimum cost from node x to node y through neighbor v.

How does the Distance Vector Algorithm handle asynchronous updates?

Each node updates its distance vector independently and asynchronously.

What is the initial distance vector for a node in the Distance Vector Algorithm?

The distance to itself is 0, and the distance to all other nodes is infinity.

In the Distance Vector Algorithm, what does Da(a) = 0 mean?

Node a has a distance of 0 to itself.

What does it mean if Da(b) = 8 in the Distance Vector example?

Node a estimates the cost to reach node b as 8.

What is the significance of the iterative communication in the Distance Vector Algorithm?

It allows information to diffuse through the network over time.

What does it mean for a node to recompute its distance vector?

It calculates new distance estimates based on received distance vectors from neighbors.

What happens if a node does not receive any notification?

No actions are taken; the node retains its current distance vector.

What is the role of the minimum function in distance vector calculations?

It selects the least cost path from multiple potential paths to a destination.

What is the effect of a link cost change in the Distance Vector Algorithm?

The node detects the change, updates its distance vector, and notifies neighbors.

What is the distance vector for node c at time t=1?

Dc(a) = ∞, Dc(b) = 1, Dc(c) = 0, Dc(d) = ∞, Dc(e) = ∞, Dc(f) = ∞, Dc(g) = ∞, Dc(h) = ∞, Dc(i) = ∞.

How does node b compute its new distance vector?

By receiving distance vectors from its neighbors and applying the minimum function.

What does it mean if Db(e) = 1?

Node b estimates the cost to reach node e as 1.

What is the significance of the distance vector being ∞ for some nodes?

It indicates that those nodes are currently unreachable from the source node.

What does the iterative nature of the Distance Vector Algorithm imply for network updates?

It allows for gradual convergence of distance estimates across the network.

What is the primary outcome of the Distance Vector Algorithm?

To provide each node with the least-cost path estimates to all other nodes.

What does the term 'self-stopping' refer to in the context of the Distance Vector Algorithm?

Nodes stop notifying neighbors if their distance vector has not changed.

What does the distance vector Da(c) = ∞ indicate?

Node a cannot currently reach node c.

What is the impact of a node's state at time t=0 on its neighbors?

It can influence distance vector computations up to 1 hop away.

What does the process of computing new local distance vectors involve?

Each node calculates its distance vector based on the received vectors from neighbors.

What is the Distance Vector (DV) routing protocol?

A routing protocol where each router shares its distance vector with its neighbors to determine the best path.

How does a node compute its distance vector?

By using the minimum cost from itself to each destination based on received distance vectors from neighbors.

What happens when a node detects a local link cost change?

The node updates its routing information, recalculates its local distance vector, and notifies its neighbors if changes occur.

What is the 'count-to-infinity' problem in Distance Vector routing?

A situation where incorrect routing information circulates, causing nodes to continuously update their distance to a destination, leading to infinite loops.

What is the purpose of inter-AS routing?

To manage routing between different autonomous systems (AS) on the internet.

What is the role of a gateway router?

To connect an autonomous system to other ASes and manage inter-domain routing.

What are the main types of routing protocols used within an AS?

Intra-AS routing protocols, such as RIP, EIGRP, and OSPF.

What is RIP in the context of routing protocols?

Routing Information Protocol, a classic distance vector protocol that exchanges distance vectors every 30 seconds.

What is OSPF?

Open Shortest Path First, a link-state routing protocol that uses Dijkstra's algorithm to compute the shortest path.

What is the significance of link-state advertisements in OSPF?

They allow routers to share their link states with all other routers in the AS to maintain a complete topology.

What is the difference between inter-AS and intra-AS routing?

Inter-AS routing is for routing between different autonomous systems, while intra-AS routing is for routing within the same AS.

What does the term 'autonomous system' (AS) refer to?

A collection of IP networks and routers under the control of a single organization that presents a common routing policy to the internet.

What is the purpose of a forwarding table in routing?

To determine the next hop for packets based on the destination address.

How does distance vector routing handle the propagation of routing information?

Through iterative communication, where each node updates its distance vector based on information received from neighbors.

What is the initial state of a node in distance vector routing?

The node's distance vector reflects only its direct connections at the start.

What happens at time t=1 in distance vector routing?

The state of a node at t=0 influences distance vector computations up to 1 hop away.

What is the impact of link cost changes in distance vector routing?

Nodes must recalculate their distance vectors and inform their neighbors of any changes.

What is the main advantage of using OSPF over distance vector protocols?

OSPF provides faster convergence and more accurate routing information due to its link-state nature.

What does the term 'good news travels fast' imply in routing?

When a node learns of a better route, it quickly updates its neighbors to propagate the new information.

What does 'bad news travels slow' mean in the context of routing?

When a node detects a worse route, it may take longer to propagate this information, leading to potential routing loops.

What is the significance of the Dijkstra algorithm in OSPF?

It is used to compute the shortest path to each destination based on the complete network topology.

What are the characteristics of EIGRP?

Enhanced Interior Gateway Routing Protocol, a distance vector protocol that was Cisco-proprietary but became open in 2013.

How does OSPF ensure security?

All OSPF messages are authenticated to prevent unauthorized access and malicious intrusions.

What is the role of link costs in routing protocols?

Link costs determine the best path for data packets based on metrics such as bandwidth and delay.

What does 'hierarchical OSPF' refer to?

A two-level hierarchy in OSPF that includes local areas and a backbone for efficient routing.

What is the effect of multiple link cost metrics in OSPF?

They allow routers to choose paths based on varying criteria, improving routing efficiency.

What is the primary function of intra-AS routing protocols?

To manage routing within a single autonomous system, ensuring efficient data packet delivery.

What is the purpose of link-state advertisements in OSPF?

To flood information only in the area or backbone, allowing each node to know the direction to reach other destinations.

What does a boundary router do?

Connects to other Autonomous Systems (ASes) and summarizes distances to destinations in its own area.

What is the role of area border routers in OSPF?

To summarize distances to destinations in their area and advertise this information in the backbone.

What is the function of a backbone router in OSPF?

Runs OSPF limited to the backbone.

What does BGP stand for?

Border Gateway Protocol.

Why is BGP referred to as the 'glue that holds the Internet together'?

It allows subnets to advertise their existence and reachable destinations to the rest of the Internet.

What are the two types of BGP connections?

eBGP (external BGP) and iBGP (internal BGP).

What does eBGP do?

Obtains subnet reachability information from neighboring ASes.

What is the purpose of iBGP?

To propagate reachability information to all AS-internal routers.

What is a BGP session?

A semi-permanent TCP connection between two BGP routers (peers) that exchange BGP messages.

What are the four types of BGP messages?

OPEN, UPDATE, KEEPALIVE, and NOTIFICATION.

What does the AS-PATH attribute in BGP indicate?

The list of ASes through which the prefix advertisement has passed.

What is policy-based routing in BGP?

The gateway receiving a route advertisement uses an import policy to accept or decline the path.

What is hot potato routing?

Choosing the local gateway with the least intra-domain cost, regardless of inter-domain costs.

What is the main focus of intra-AS routing?

Performance, as it is managed by a single administrator.

What is the main focus of inter-AS routing?

Policy, as multiple administrators are involved.

What is the role of a managing server in network management?

To manage and configure devices, typically with human network managers involved.

What does SNMP stand for?

Simple Network Management Protocol.

What is the purpose of MIB in SNMP?

To define the structure of the management data of a device.