Network Routing Concepts Quiz

Network Layer Control Plane

• PowerPoint slides freely available to faculty, students, and readers.
• Animations can be added, modified, and deleted.
• If using the slides, mention their source.
• If posting slides online, acknowledge the source and copyright.
• Revision history is available in the slide notes.

Network Layer Control Plane: Goals

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

Network Layer: "Control Plane" Roadmap

• Introduction
• Routing protocols (link state, distance vector)
• 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 a router's input to an appropriate output.
• Routing: determining the route a packet takes from source to destination.
• 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 within each router interact to manage forwarding tables.

Software-Defined Networking (SDN) Control Plane

• A remote controller computes and installs forwarding tables in routers.

Routing Protocols

• Goal: to determine "good" paths (routes) between sending and receiving hosts.
• Path: sequence of routers a packet traverses.
• Criteria for "good" paths: least cost, fastest, least congested.

Graph Abstraction: Link Costs

• Graph G = (N, E)
  • N: set of routers (nodes).
  • E: set of links (edges) connecting pairs of routers.
• C_ab: cost of a direct link connecting nodes a and b.
• Costs can be defined by network operators and may reflect bandwidth or congestion.

Routing Algorithm Classification

• Static routing: routes change slowly over time
• Global information (all routers have complete topology and link cost information)
• Link-state algorithms: used in static routing
• Decentralized routing: iterative process of computation and exchange of information among neighbors
• Distance vector algorithms: routers initially only know link costs to attached neighbors.

Dijkstra's Link-State Routing Algorithm

• Centralized approach
• Network topology and link costs known to all nodes.
• "Link state broadcast" informs all nodes of the network topology.
• Computes least cost paths.
• Iterative process, after each iteration the algorithm knows the least cost path to a certain number of destinations.
• Forwarding table calculation
• Notation:
  • C_xy: cost of the direct links between nodes x and y. Is ∞ if there is no direct connection.
  • D(v): estimated cost of the least cost path from the source to the destination v.
  • p(v): predecessor node along the path from the source to v.
  • N': set of nodes whose least-cost path is definitively known.

Dijkstra's Algorithm: Example

• Illustrative examples showing the steps of Dijkstra's algorithm.
• Includes tables with the algorithm's intermediate results.
• Shows how the algorithm progresses from initialization to determining least cost paths, producing forwarding tables.

Distance Vector Algorithm

• Based on Bellman-Ford equation (dynamic programming)
• Each node periodically sends its distance vector to its neighbors
• When a node receives a new distance vector from a neighbor, it updates its estimated distance vectors using the Bellman-Ford equation.
• Under minor, natural conditions, the estimated distances converge towards the actual least costs

Distance Vector Algorithm: Key Idea

• Nodes exchange distance vectors
• Nodes update their distance vectors based on new information from neighbors.

Distance Vector Algorithm: Example

• Illustrates the algorithm's operation through iterations of receiving, computing, and disseminating distance vectors.

Distance Vector Algorithm: Iteration

• Nodes receive distance vectors (DV) from neighbors.
• Nodes compute their new local DV
• Nodes send their new DV to neighbors.

Distance Vector Example: Computation

• Sample computations using the distance vector algorithm to calculate distances to various destinations.
• Illustrates updates from different neighbors at different times.

Distance Vector State Information Diffusion

• Illustrates how updated information spreads throughout the network using distance vector.

Distance Vector: Link Cost Changes

• Nodes detect local link cost changes and update routing tables.
• Updated routing tables are communicated to neighbors if changes occur.

Distance Vector: Link Cost Changes (Bad News Travels Slow)

• Illustrates the count-to-infinity problem, where bad news (link cost increase) takes a long time to propagate through the network.

Comparison of LS and DV Algorithms

• Message complexity:
  • LS: O(n²)
  • DV: exchange between neighbors, convergence varies
• Speed of convergence:
  • LS: O(n²)
  • DV: convergence varies
• Robustness: what happens if a router malfunctions or is compromised
  • LS: router can advertise incorrect link cost; each router computes only its own table.
  • DV: router can advertise incorrect path cost (e.g., black holing); each router's DV is used by others, errors propagate.

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 and configuration (SNMP, NETCONF/YANG)

Making Routing Scalable

• Need to deal with billions of destinations.

• Large routing tables cannot be stored in each router.

• Need to deal with routing table exchange.

Internet Approach to Scalable Routing

• Aggregate routers into regions (ASes).

• Intra-AS Routing: routing within a single AS (e.g., OSPF)

• Inter-AS Routing: routing between ASes (e.g., BGP)

• Gateways perform inter-domain routing and intra-domain routing.

Interconnected ASes

• Intra-AS routing manages routing within a single AS.
• Inter-AS routing manages routing between ASes.
• Forwarding tables are configured by both intra-AS and inter-AS routing.

Inter-AS Routing: A Role in Intradomain Forwarding

• Addresses the need to decide which gateway router a packet should be forwarded to if destined for outside the AS.

Intra-AS Routing: Routing within an AS

• RIP, EIGRP, and OSPF, are commonly used intra-AS routing protocols

OSPF (Open Shortest Path First) Routing

• Publicly available protocol.
• Classic link-state routing
• Floods link-state advertisements between routers.
• Uses Dijkstra's algorithm and full topology information
• Security: authentication of messages

Hierarchical OSPF

• Two-level hierarchy: local area, backbone.
• Area border routers summarize distances for destinations in their own areas.
• Backbone routers flood link-state information.
• Each router has a detailed topology for its area; general direction to reach other destinations is detailed.

Network Layer: "Control Plane" Roadmap

• Introduction
• Routing protocols
• Intra-ISP routing: OSPF
• Routing among ISPs: BGP
• SDN control plane
• Internet Control Message Protocol
• Network management, configuration (SNMP, NETCONF/YANG)

BGP (Border Gateway Protocol)

• Internet inter-AS routing protocol
• Used for exchanging routing information between ASes
• Allows networks to advertise reachability information and determine routes.
• Propagates reachability information within an AS.
• Advertises reachability information to neighboring networks.

eBGP, iBGP Connections

• Gateway routers use both eBGP and iBGP protocols.

BGP Basics

• BGP uses TCP connections between routers.
• Routers advertise paths to different destination network prefixes.
• AS3 gateway advertises path AS3.X to AS2 gateway.

BGP Protocol Messages

• BGP messages exchanged over TCP connections
• Includes messages such as OPEN, UPDATE, KEEPALIVE, NOTIFICATION
• These messages are used for initializing, maintaining, and ending the connections between BGP routers, which exchange routing information.

Path Attributes and BGP Routes

• BGP routes include attributes such as prefix (destination advertisement) and AS-PATH
• AS-PATH: list of ASes (autonomous systems) that the advertisement has traversed.
• NEXT-HOP: specifies internal AS router used to reach the destination AS.

BGP Path Advertisement

• AS2 receives path advertisement for AS3.X via eBGP.
• AS2 accepts the path and propagates it internally via iBGP.
• AS2 advertises the path to a neighboring AS via eBGP.

BGP Path Advertisement: Multiple Paths

• Router can obtain multiple paths to the same destination.
• Policies are used to choose preferred routes based on shortest AS-PATH, closest NEXT-HOP router, and additional criteria

BGP: Populating Forwarding Tables

• Routers learn about paths to destinations via BGP messages.
• Routers use intra-domain routing (e.g. OSPF) to reach the next hop router on the path.

Hot Potato Routing

• Routers forward traffic to the next hop based on intra-domain routing cost (i.e, local policy).

BGP: Achieving Policy via Advertisements

• ISPs use BGP to control routing among customer networks.
• Policies are used to prevent unwanted traffic transit between ISPs

BGP Route Selection

• Router considers multiple routes to a destination based on local preferences, shortest AS-PATH, closest NEXT-HOP, and additional criteria.

Why Different Intra-, Inter-AS Routing?

• Policy: administrative control over traffic flow.
• Scale: hierarchical routing is more scalable.
• Performance: intra-AS routing is more focused on performance.

Network Layer: "Control Plane" Roadmap

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

Software Defined Networking (SDN)

• Historically, network layers have used distributed (per-router) control approaches.
• Recent advances use a logically centralized control plane in modern SDN designs.
• Data and control planes are separated and use APIs for communication
• Simpler and more manageable for network management.

Software Defined Networking (SDN): Data Plane Switches

• Fast switches using commodity hardware.
• Utilize flow tables installed by the controller.
• Implementing generalized data-plane forwarding in hardware.

Software Defined Networking (SDN): SDN Controller

• Maintains network state information.

• Interacts with network control applications

• Interacts with switches via southbound APIs

• Implemented as a distributed system.

Software Defined Networking (SDN): Network Control Apps

• "Brains" of control.
• Implement control functions using lower-level services.
• Often provided through an API.

OpenFlow Protocol

• Protocol to control SDN layer.
• Operates between controller and switch using TCP connections.
• Conveys messages using a structured format.

OpenFlow: Controller-to-Switch Messages

• Controller queries and manages the switch's features and configurations.
• Allows for adding, deleting, and modifying flow entries in the Openflow hardware tables.

OpenFlow: Switch-to-Controller Messages

• Switches send packet-in messages to the controller.
• Switches inform the controller about port status changes.

SDN: Control/Data Plane Interaction Example

• Illustrates how the SDN controller responds to network changes (e.g., a link failure) by reconfiguring the network's forwarding tables.

Google ORION SDN Control Plane

• Overview of a Google network control plane that aims to unify control planes in various domains.
• Google’s approach to SDN control plane design.
• Handles routing, traffic engineering, and other network tasks.

OpenDaylight (ODL) Controller

• Implementation details of one possible SDN control plane.

ONOS Controller

• Implementation details of another possible SDN control plane.

SDN: Selected Challenges

• Hardening the control plane.
• Robustness to failures.
• Meeting mission-specific requirements for networks and protocols.
• Internet scaling capabilities.

SDN and the Future of Traditional Network Protocols

• The future of network protocols is uncertain due to SDN
• The future uses of SDN and its effect on existing protocols are uncertain.

Network Layer: Summary

• Summary of the different network control plane approaches to manage networks.

ICMP (Internet Control Message Protocol)

• Protocol for error reporting.
• Hosts and routers exchange network-level information.
• ICMP messages carried within IP datagrams.

Traceroute and ICMP

• Tool used to trace the routes taken by packets.
• Uses ICMP messages.
• Uses several tests to determine the path being taken.

Network Layer: "Control Plane" Roadmap

• Introduction
• Routing Protocols
• Intra-ISP Routing: OSPF
• Inter-AS Routing: BGP
• SDN Control Plane
• Internet Control Message Protocol
• Network Management, Configuration (SNMP, NETCONF/YANG)

What is Network Management?

• Complex systems requiring monitoring and configuration (networks, control systems, etc.).
• Coordination and deployment of hardware/software/human elements.
• Meeting real-time operational performance.
• Quality of service requirements at a reasonable cost.

Components of Network Management

• Managing Server (typically containing applications related to network management).
• Managing Controllers (responsible for managing network/device data).
• Managed devices (network equipment).
• Protocols such as SNMP, CLI, NETCONF that convey network management information.

Network Operator Approaches to Management

• Command-line interfaces (CLIs)
• SNMP/MIB
• NETCONF/YANG

SNMP Protocol

• Uses a request/response mode to convey management information between managing servers and managed devices.
• Uses trap mode in cases where immediate notification of events is necessary

SNMP Protocol: message types

• Types of messages such as GetRequest, GetNextRequest, GetBulkRequest, SetRequest, Responses, Traps

SNMP Protocol: message formats

• Different PDUs (Protocol Data Units) for various SNMP messages.

SNMP: Management Information Base (MIB)

• Data definition language for managed network devices and their information.
• Defines different types of information available via SNMP.

NETCONF Overview

• Active management and configuration of network devices.
• Exchange of data with managed devices using XML-encoded messages.

NETCONF Initialization, Exchange, and Closing

• Shows the steps involved in setup, data exchange, and ending the session between the managing server and device.

Selected NETCONF Operations

• Describes different NETCONF based operations.

Sample NETCONF RPC Message

• A sample XML formatted NETCONF message.
• Shows the content for configuration change request.

YANG Data Modeling Language

• Used to define the structure and semantics for network data to ensure that the configuration data being used is unambiguous and well-formed.
• Generates XML descriptions of device capabilities.

Network Layer: Summary

• Summary of concepts related to network layer and control planes.

Test your knowledge of link costs, routing algorithms, and network graph representations with this quiz. Dive into the distinctions between dynamic and static routing, and explore the theoretical aspects of networking. Ideal for students and professionals in networking courses.