Podcast
Questions and Answers
The two approaches to structuring the network control plane are ______ control and logically centralized control.
The two approaches to structuring the network control plane are ______ control and logically centralized control.
per-router
In Software-Defined Networking, the remote ______ computes and installs forwarding tables in routers.
In Software-Defined Networking, the remote ______ computes and installs forwarding tables in routers.
controller
Routing protocols are designed to determine good ______ from sending hosts to receiving hosts.
Routing protocols are designed to determine good ______ from sending hosts to receiving hosts.
paths
Routing is considered a top-10 networking ______.
Routing is considered a top-10 networking ______.
In link state routing algorithms, the net topology and link costs are known to all ______.
In link state routing algorithms, the net topology and link costs are known to all ______.
The link cost from node x to y is denoted as c______,y.
The link cost from node x to y is denoted as c______,y.
Routing decisions are evaluated in terms of a certain ______, such as least cost or fastest.
Routing decisions are evaluated in terms of a certain ______, such as least cost or fastest.
The ______ state broadcast allows all nodes to acquire information about link states in a network.
The ______ state broadcast allows all nodes to acquire information about link states in a network.
Graph abstraction involves link costs denoted by c______,b, which represent the cost of direct links.
Graph abstraction involves link costs denoted by c______,b, which represent the cost of direct links.
In a routing context, a path is a sequence of routers packets traverse from a given initial ______ host to final destination host.
In a routing context, a path is a sequence of routers packets traverse from a given initial ______ host to final destination host.
Dijkstra's algorithm is used to find the least cost paths to ______ destinations after k iterations.
Dijkstra's algorithm is used to find the least cost paths to ______ destinations after k iterations.
In Dijkstra's algorithm, the notation cx,y represents the link cost from node x to ______; it is ∞ if not direct neighbors.
In Dijkstra's algorithm, the notation cx,y represents the link cost from node x to ______; it is ∞ if not direct neighbors.
D(v) indicates the current value of the cost of path from source to destination ______.
D(v) indicates the current value of the cost of path from source to destination ______.
The set N' consists of nodes whose least cost path is definitively ______.
The set N' consists of nodes whose least cost path is definitively ______.
The complexity of Dijkstra's algorithm with n nodes is O(n^2) due to the need to check all nodes not in ______.
The complexity of Dijkstra's algorithm with n nodes is O(n^2) due to the need to check all nodes not in ______.
A more efficient implementation of Dijkstra's algorithm using a priority queue has a complexity of O(n log ______).
A more efficient implementation of Dijkstra's algorithm using a priority queue has a complexity of O(n log ______).
Each router must broadcast its link state information to ______ other routers.
Each router must broadcast its link state information to ______ other routers.
The overall message complexity in Dijkstra’s algorithm becomes O(n^2) due to each router’s message crossing O(______) links.
The overall message complexity in Dijkstra’s algorithm becomes O(n^2) due to each router’s message crossing O(______) links.
An oscillation issue in Dijkstra’s algorithm can occur when link costs depend on ______ volume.
An oscillation issue in Dijkstra’s algorithm can occur when link costs depend on ______ volume.
Routing to destination a can be affected by traffic rates entering from ______, c, and e.
Routing to destination a can be affected by traffic rates entering from ______, c, and e.
Flashcards are hidden until you start studying
Study Notes
Introduction to Control Plane in Network Layer
- The network layer is responsible for forwarding packets from the source to the destination.
- Forwarding deals with moving packets between input and output ports of the router (data plane).
- Routing determines the route packets will take between source and destination (control plane).
- There are two approaches to structuring the network control plane:
- Per-router control: Each router has its own control plane elements which interact independently to decide routes.
- Logically centralized control (SDN): A remote controller calculates and installs forwarding tables in routers.
Routing Protocols
- Routing protocols are responsible for determining the "best" paths between hosts across a network of routers.
- The "best" path is defined by a specific metric, such as least cost, fastest route, or least congested path.
Graph Abstraction and Link Costs
- Networks can be represented as graphs where nodes are routers and edges are links.
- Link costs are assigned to each link, reflecting the cost of using that link, and determined by network operators.
- This can be defined in different ways, for example:
- A fixed cost of 1 for all links.
- A cost inversely proportional to bandwidth.
- A cost inversely proportional to congestion levels.
Routing Algorithm Classification
- Routing algorithms are classified as either link state or distance vector protocols.
Link State Routing Algorithm
- In link state routing, every node in the network has complete knowledge of the network topology and link costs.
- Each node broadcasts its link state information to all other nodes, resulting in all nodes having the same information.
- The goal is to compute the least cost paths from one node to all other nodes in the network.
- Dijkstra's algorithm is used to calculate these paths, working iteratively by finding the least cost path to progressively larger sets of destination nodes.
Dijkstra's Link State Routing Algorithm - Example
- The algorithm uses a set of variables:
- c(x, y): Cost of the link from node x to node y (infinity if no direct link).
- D(v): Cost of the least cost path from the source to destination node v.
- p(v): Predecessor node on the least cost path from the source to destination node v.
- N': Set of nodes whose least cost path is definitively known.
- The algorithm iteratively builds the least cost path tree by tracing predecessor nodes in the graph.
Dijkstra's Algorithm: Discussion
- Complexity: The complexity of the algorithm is O(n^2) for a network with n nodes.
- Message Complexity: Each router broadcasts its link state information to all other routers, resulting in O(n^2) message complexity overall.
Oscillation Issue in Dijkstra's Algorithm
- Link costs can change due to network traffic.
- This dynamic change in link costs can cause the routing paths to constantly change, a phenomenon called route oscillation.
- This issue can lead to inefficient network performance.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
