ECE 4436A Networking: Control Plane Principles

ECE 4436A NETWORKING: PRINCIPLES, PROTOCOLS, AND ARCHITECTURES

• Course offered by Dr. Fang (Fiona) Fang, Department of Electrical and Computer Engineering, University of Western Ontario
• Some slides adapted from Kurose and Ross notes. Copyright held by authors and publishers.

Network Layer Control Plane: Goals

• Understand principles behind network control plane
• Includes traditional routing algorithms, SDN controllers, network management and configuration
• Internet instantiation and implementation: OSPF, BGP, OpenFlow, ODL, ONOS controllers, ICMP (Internet Control Message Protocol), SNMP, YANG/NETCONF

Network Layer: "Control Plane" Roadmap

• Introduction to routing protocols
• Link state and distance vector protocols
• Intra-ISP routing (OSPF)
• Routing among ISPs (BGP)
• SDN control plane
• Internet Control Message Protocol (ICMP)
• Network management and configuration (SNMP, NETCONF/YANG)

Network-layer Functions

• Forwarding: moving packets from router input to appropriate router output (data plane)
• Routing: determining the route taken by packets from source to destination (control plane)
• Two approaches to structuring network control plane:
  • Per-router control (traditional)
  • Logically centralized control (software-defined networking)

Per-router Control Plane

• Individual routing algorithm components in each router interact in the control plane.
• Local forwarding tables in each router handle packet forwarding.
• Values in arriving packet headers determine next-hop forwarding.

Software-Defined Networking (SDN) Control Plane

• Remote controller computes and installs forwarding tables in routers.
• Centralized control for network forwarding.
• Controller installs forwarding tables in routers based on incoming packet header values.

Routing Protocols

• Determine "good" paths (routes) from sending host to receiving host.
• Path is the sequence of routers packets traverse.
• "good" can be least "cost", "fastest", or "least congestioned"
• Routing is a significant networking challenge.

Graph Abstraction: Link Costs

• Graph model G = (N, E) where:
  • N: set of routers ({u, v, w, x, y, z})
  • E: set of links (e.g., (u, v), (u, x), (v, x), ...)
• C_ab: cost of a direct link connecting a and b. Cost can be defined based on network operator rules, bandwidth, or congestion.

Routing Algorithm Classification

• Static routing: routes change slowly over time.
• Dynamic routing: routes change more quickly.
  • Decentralized: an iterative process of computation and information exchange with neighbors. Routers initially have knowledge of costs to neighbors. Distance vector algorithms.
    • Global or decentralized information (complete knowledge of network topology)

Dijkstra's Link-State Routing Algorithm

• Centralized approach: network topology and link costs known to all nodes. Achieved through "link state broadcast."
• Computes least-cost paths from a source node to all other nodes, creating a forwarding table for that node.
• Iterative: after each iteration, more destinations can be found with least possible cost/path.

Dijkstra's Algorithm: Another Example

• Iterative computations finding minimum costs from a node.

Dijkstra's Algorithm: Discussion

• Algorithm complexity: O(n^2), where n is the number of nodes.
• More efficient implementations possible: O(n log n).
• Message complexity: O(n^2).

Distance Vector Algorithm

• Based on Bellman-Ford (BF) equation.
• Let D_x(y) be the cost of the least-cost path from router x to router y. D_x(y) = min_v{C_(x, v) + D_v(y)}
• Each node sends its distance vector estimates to neighbors periodically.
• When a node receives a new distance vector from a neighbor, it updates its own distance vector using the formula above.

Distance Vector Algorithm: Key Idea

• Each node sends its own distance vector to its neighbors periodically.
• Nodes update their distance vectors when new distance vectors are received from a neighbor.
• Distance estimates converge to the actual least cost under suitable conditions.

Distance Vector Algorithm: Iterative, Asynchronous

• Updates caused by local link cost changes and DV update messages from neighbors.
• Distributed and self-stopping. Nodes notify their neighbors only if their DV changes.

Distance Vector: Example

• Illustrative example of node distance vector updates.

Distance Vector Algorithm: Iteration

• Illustration of iterative distance vector computations over time.

Distance Vector Example: Iteration

• Steps of iteration, highlighting node calculations and message exchanges to neighbors.

Distance Vector: Link Cost Changes

• Node detecting local link-cost change and notifying neighbors when DV changes.
• Count-to-infinity problem in distance-vector algorithms. Illustration, involving potential paths with successively calculated and increased costs from one node to another over iterations.

Comparison of LS and DV Algorithms

• Message complexity: LS (O(n^2)) vs. DV (variable).
• Convergence time: LS (O(n^2)) vs. DV (variable).
• Robustness: LS (less susceptible to errors) vs. DV (more susceptible to errors).

Network Layer: "Control Plane" Roadmap

• Introduction, routing protocols (intra-ISP routing: OSPF; routing among ISPs: BGP), SDN control plane, Internet Control Message Protocol (ICMP), network management, configuration (SNMP, NETCONF/YANG).

Making Routing Scalable

• Idealized routing (all routers identical; network "flat") may not be true in practice.
• Routing tables could be huge (billions of destinations).
• Routing table exchange could swamp links.
• Administrative autonomy: Each network admin wants control over how traffic is routed.

Internet Approach to Scalable Routing

• Aggregate routers into "autonomous systems" (ASs).
• Intra-AS routing happens within an AS.
• All routers in an AS generally run the same intra-domain routing protocol.
• Gateway routers act as the "edge" of an AS and link to other ASes.
• Inter-AS routing: routing between ASes.

Interconnected ASes

• Intra-AS and inter-AS routing: Determine entries in a forwarding table for intra-AS destinations.
• Inter-AS and intra-AS routing: Determine entries in the forwarding table for external destinations.

Inter-AS Routing: A Role in Intradomain Forwarding

• If a router in AS1 receives traffic destined outside of AS1, which gateway router should it use to forward the packet?

Inter-AS Routing: Routing within an AS

• Routing protocols common in intra-AS domains, like RIP, EIGRP, and OSPF.

OSPF (Open Shortest Path First) Routing

• Open standard link-state routing protocol.

Hierarchical OSPF

• Two-level hierarchy (local area, backbone).
• Link-state advertisements (flooded) in the area.
• Nodes in a given area have detailed area topologies and know direction to other destinations.

Internet Inter-AS Routing: BGP

• De facto inter-domain routing protocol. BGP is a "path vector" protocol.
• Allows subnets to advertise their existence and destinations to others.
• BGP provides a means for each AS to:
  • Obtain subnet reachability information from neighbors.
  • Propagate to AS-internal routers.
  • Determine desired routes to other networks.

eBGP, iBGP Connections

• eBGP: BGP connectivity between gateway routers of different ASes.
• iBGP: BGP connectivity between gateway routers within the same AS.

BGP Basics

• Routing among peers via semi-permanent TCP connections.
• Messages (OPEN, UPDATE, KEEPALIVE, NOTIFICATION) used by peers.

Path Attributes and BGP Routes

• Routing prefix + attributes (like AS Path, NEXT-HOP).
• Policy-based routing for gateways, determines appropriate routes through other ASes.

BGP Path Advertisement

• AS router advertises paths to other ASes.
• Based on policy and reachability.

BGP Messages

• Exchange messages between peers over TCP connections.
• Common BGP messages: OPEN, UPDATE, KEEPALIVE, NOTIFICATION

ICMP: Internet Control Message Protocol

• Used by hosts and routers for network-level information and error reporting.
• Supports network-layer functions "above" IP address layer. ICMP messages include a type, code and data of the message, along with 8 bytes from the initial IP datagram with the error.
• Components of an ICMP message, types of errors handled by ICMP.

Traceroute and ICMP

• Traceroute uses ICMP to determine network paths.
• Uses Time-to-Live (TTL) values in IP packets.
• Stopping criteria involve arrival/non-arrival of ICMP messages, providing RTT measurements.

SDN: Selected Challenges

• Hardening the control plane (dependability, reliability, performance, scalability, security).
• Network and protocol requirements (e.g., real-time, ultra-reliable, ultra-secure).
• Internet-scaling (beyond a single AS).
• Applications in 5G cellular networks.

SDN and the Future of Traditional Network Protocols

• SDN-computed vs. router-computed forwarding tables.
• Potential for SDN-computed congestion control.

Software-Defined Networking (SDN)

• Historically, network layers have used a distributed, per-router control approach.
• More recent "softwarization" efforts with SDN offer enhanced control plane that includes centralized control.
• SDN's central control plane uses a network OS which oversees the network.

Explore the fundamental principles of the network control plane in this quiz. Focused on traditional routing algorithms and protocols like OSPF and BGP, the quiz also covers SDN controllers, network management tools, and key internet protocols. Test your understanding of concepts essential for effective network communication.