Network Routing and Data Link Layer Essentials
Routing Fundamentals
Link and Router Failures: Links and routers can fail, disrupting network topology. Network State Changes: Routing algorithms must track and adapt to changes in the set of functioning links and routers. Routing Loops: A packet continuously traverses a cycle of routers without reaching its destination, consuming bandwidth and causing congestion. Black Holes: A router lacks a valid next-hop entry for a destination, causing packets to be dropped and leading to communication failures. Converged/Valid Graph if and only if there are no black holes and no loops.
Routing Algorithms
Shortest Path Routing: Find the shortest (least-cost) paths to destinations to minimize latency and optimize network performance; this reduces transmission time and improves efficiency. Network as a Graph: Represented as G(N,E), where N is the set of nodes (routers) and E is the set of edges (links); each edge has an associated cost (e.g., latency, bandwidth, hop count).
Routing Protocols
Intra-Domain Routing: Routing within a single Autonomous System (AS); aims for shortest path routing to optimize internal performance. Protocols: OSPF (Open Shortest Path First), IS-IS (Intermediate System to Intermediate System). Inter-Domain Routing: Routing between different ASes; based on policies reflecting business agreements, not necessarily shortest paths. Protocol: BGP (Border Gateway Protocol). From Algorithms to Protocols: Challenge—Algorithms like Dijkstra’s require complete network knowledge (not feasible on the Internet). Solution—Routing protocols disseminate network state information, allowing routers to compute routes with partial knowledge. Routing Convergence: Process where all routers update forwarding tables to reflect the current topology. Properties at Convergence: Uniform link-state databases; consistent paths without loops or black holes. Convergence Time: Influenced by detection delays, status propagation, and computation delays. Transient Inconsistencies: Can cause temporary loops or black holes; may lead to packet loss or out-of-order delivery.
Link State Routing – Open Shortest Path First (OSPF)
Performs better in large, diverse networks, with fast convergence speed, but is complex to set up. Link State Advertisements (LSAs): Packets containing the state and cost of all links connected to a router. Contents: Link ID, State (Up/Down), Cost (latency, bandwidth), Sequence Number (version control), Age Field (to discard outdated LSAs). Reliable Dissemination: Flooding Mechanism—Routers send LSAs to all direct neighbors; neighbors forward LSAs to their neighbors (excluding the sender); this continues until all routers receive the LSA. Property: Ensures network-wide dissemination of link states. When to Initiate Flooding: Topology changes (link/node failures), configuration changes, periodic refreshes. Scaling Link State Routing: Problem—Flooding LSAs doesn’t scale in large networks. Solution—Introduce hierarchy (e.g., OSPF areas); Backbone Area connects all other areas; Regular Areas contain LSAs within themselves; Area Border Routers summarize routes to other areas, reducing LSA flooding scope. Dijkstra’s Algorithm: Computes the shortest paths from a single source node. Algorithm Steps: Initialization—Set the source distance to 0, others to infinity; place nodes in a priority queue. Iteration—While the queue is not empty, extract the node with the smallest distance; for each neighbor, calculate the tentative distance through the current node; if less than the known distance, update and reinsert the neighbor.
Distance Vector Routing (RIP) – Routing Information Protocol
Distance Vector Algorithm: Routers maintain a vector of minimum distances to all destinations and share with neighbors. Bellman-Ford Equation: Dx(y)=minv{c(x,v)+Dv(y)}, where Dx(y) is the cost from node x to y; c(x,v) is the cost from x to neighbor v; Dv(y) is v’s estimate to y. Algorithm Steps: Initialization—Each router knows the cost to directly connected neighbors. Update—Upon receiving distance vectors or detecting cost changes, use Bellman-Ford to update distances; inform neighbors if changes occur. Iteration—Repeat until convergence. Distance Vector Protocols: Example—RIP (Routing Information Protocol) used in smaller networks. Convergence and Issues: Problems—Routing loops, count to infinity. Mitigation Techniques: Split Horizon—Don’t advertise a route back to the neighbor from which it was learned. Poisoned Reverse—Advertise failed route to neighbor with infinite metric to prevent loops. RIP: Considers only the number of routers (hops) a packet must pass through to reach its destination, slow convergence speed, simple, and good for small AS’s.
Inter-Domain Routing
Hierarchical Addressing and Route Aggregation: Organizes IP addresses to reduce routing table size. Multi-Homing: Organization connects to multiple ISPs for redundancy and reliability. Challenges: Difficult to aggregate IP prefixes; increases routing table size; requires careful route advertisement to maintain policies.
Border Gateway Protocol (BGP) in Depth
Border Routers: Routers within an AS that connect to routers in other ASes. BGP Sessions: External BGP (eBGP)—Between border routers of different ASes; use TCP connections. Internal BGP (iBGP)—Between border routers within the same AS; disseminate external routes. BGP Routes: Route Structure—Contains prefix (IP address block) and AS Path (sequence of AS numbers traversed). Route Propagation: AS receives routes via eBGP; border router propagates routes via iBGP; uses intra-domain protocols to forward packets. BGP Protocol Mechanics: Uses TCP for reliable transmission. Message Types: Open—Establishes session; Update—Conveys new/withdrawn routes; Keepalive—Keeps connection active; Notification—Reports errors. BGP Attributes: AS Path—Lists ASes traversed; loop avoidance by discarding routes containing own AS. Next Hop—IP address of next-hop router. Local Preference (LocalPref)—Determines route preference within an AS; higher is preferred. Multi-Exit Discriminator (MED)—Suggests preferred entry points when multiple links exist; lower is preferred. Processing BGP Updates: Import Policies—Adjust attributes like LocalPref based on relationships. Best Route Selection: Highest LocalPref, shortest AS Path, lowest MED. Export Policies—Determine which routes to advertise. Forwarding Table Update—Install best routes for packet forwarding. Issues with BGP: Misconfigurations—Can lead to loops, black holes. Route Hijacking—Unauthorized announcement of IP prefixes. Delayed Convergence—BGP can take minutes to hours to converge. Non-Convergence—Conflicting policies may prevent a stable state.
Software Defined Networking (SDN)
SDN Architecture
Data Plane: Part of the router that forwards packets based on the decisions made by the control plane. Control Plane: Responsible for making routing and forwarding decisions, manages calculations. Applications: Implement network services (routing, load balancing, security). Interaction with Controller: Use APIs to communicate intents; don’t manage low-level switch details. Northbound Interface: Connects apps to the controller, allowing apps to read the network state and develop flow tables. Southbound Interface: Allows the controller to communicate with switches to enforce policies and get the network state. Centralized Controller: Maintains global network state; provides an interface for applications; translates high-level policies into forwarding rules. State Management: Collects info from switches; updates switches based on directives. Switches: Forward packets based on flow rules from the controller. Features: Match-Action Tables—Determine handling of packets; Flow Entries—Define processing of matching packets. Communication with Controller: Report events; receive instructions. Reliability and Scalability: Controller Redundancy—Backup controllers for failover. Scalability—Partition the network; assign controllers to segments; controllers communicate for inter-segment traffic.
Generalized Forwarding and OpenFlow
Generalized Forwarding: Allows matching on multiple packet header fields; supports complex policies. OpenFlow Protocol: Enables the controller to interact with switches to modify network behavior. Key Concepts: Flow—Set of packets matching criteria; Flow Specification—Header fields defining a flow; Actions—Operations on matching packets (forward, drop, modify). OpenFlow Switch Operation: Match-Action Table—Contains flow entries. Packet Processing: Match—Check incoming packets against the flow table; Action—Execute corresponding action; Table Miss—Forward packet to the controller if no match is found. Controller-Switch Interaction: Controller Commands—Query features, configure the switch, modify flow entries, send packets. Switch Notifications—Packet-in events, port status changes, flow removal notifications. Advantages of OpenFlow: Flexibility—Custom routing policies; Programmability—Dynamic network behavior; Vendor-Neutral—Works across devices from different manufacturers.
Introduction to the Data Link Layer
Role of the Data Link Layer: Handles different transmission media (wired, wireless); ensures compatibility and reliable data transfer.
Functions of the Data Link Layer
Framing: Encapsulates network layer packets into frames. Frame Structure: Header (control info), Payload (encapsulated packet), Trailer (error detection). Link Access (MAC): Determines when a device can access the shared medium. Scenarios: Point-to-Point Links—Dedicated direct connections; Broadcast Links—Shared wire or medium (e.g., Wi-Fi).
Link Layer Implementation
Hardware and Software Components: Network Interface Card (NIC)—Connects device to medium; implements physical and data link layers. Sender Operations: Encapsulates packets; adds error detection/correction. Receiver Operations: Checks for errors; decapsulates frames.
Error Detection and Correction Methods
Parity Checks: Single Parity Bit: Adds one bit to ensure an even/odd number of 1s; detects single-bit errors. Two-Dimensional Parity: Data bits in a grid; parity bits for rows and columns; can detect and correct single-bit errors. Cyclic Redundancy Check (CRC): Powerful error-detecting code; can detect burst errors up to a certain length. Process: Compute FCS (Frame Check Sequence); the receiver performs the same computation; compare results.
Medium Access Control (MAC) Protocols
Challenges with Shared Medium: Collisions—When multiple nodes transmit simultaneously. MAC Protocol Categories: Channel Partitioning Protocols: TDMA—Time divided into slots; nodes have dedicated slots. FDMA—Channel divided into frequency bands. Random Access Protocols: Slotted ALOHA—Devices synchronize to time slots; nodes transmit at the start of the slot; collisions are handled by retries. ALOHA: Like slotted, but sends data immediately at a random time and waits a random amount of time if a collision occurs. CSMA/CD—Checks the channel to make sure nothing is being transmitted before transmitting; collision detection during transmission; uses binary exponential backoff. CSMA: Like /CD but doesn’t check for collisions during transmission. CSMA/CA: Like /CD but with wireless, so it can’t detect collisions, so it tries to avoid them by waiting until the channel is idle. Turn-Taking Protocols: Token Passing—Token circulates; only the token holder transmits.
Ethernet
Types of Ethernet Networks: Shared Ethernet—Devices share medium; uses CSMA/CD. Switched Ethernet—Devices connect via switches; dedicated links; no collisions. Advantages of Switched Ethernet: Concurrent Communication—Multiple pairs communicate simultaneously. No Collisions—Eliminates the need for CSMA/CD. Higher Utilization—Dedicated bandwidth. Ethernet Frame Structure: Preamble (8 bytes), Destination MAC (6 bytes), Source MAC (6 bytes), Type Field (2 bytes), Payload (46-1500 bytes), FCS (4 bytes for CRC). Framing Techniques: Byte Count—Length field; issue if corrupted. Byte Stuffing—Special start/end bytes; escape characters. Bit Stuffing—Insert ‘0’ after five consecutive ‘1’s; receiver removes stuffed ‘0’s.
MAC Addressing
MAC Addresses: Unique hardware addresses; 48-bit in hexadecimal. Hierarchical Allocation: OUI—First 24 bits assigned to manufacturers; NIC-Specific—Last 24 bits assigned by the manufacturer.
Routing in Broadcast Ethernet
Challenges: Broadcast Storms—Loops cause indefinite forwarding. Solution: Spanning Tree Protocol (STP): Eliminates loops by creating a loop-free topology. Key Concepts: Root Bridge—Central reference point. BPDUs—Bridge Protocol Data Units messages exchanged to build the tree. Algorithm Steps: Root Election—Lowest Bridge ID becomes root. Path Selection—Shortest path to root; tie-breaker is the lowest Bridge ID. Port Roles: Root Port, Designated Port, Blocked Port. Maintaining the Spanning Tree: Dynamic updates; periodic BPDUs.
Forwarding and Self-Learning in Switches
Flooding: If the destination MAC is unknown, flood the frame to all ports except the incoming one. Self-Learning Mechanism: MAC Address Table—Maps MAC addresses to ports once it has received a message from them. Learning Process: Note the source MAC and incoming port; update the table. Forwarding Decision: If the destination is in the table, forward to a specific port; else, flood. Soft State Entries: TTL—Entries expire if no frames are received; adapts to network changes.
Discovery of Network Information
Dynamic Host Configuration Protocol (DHCP)
Purpose: Assigns IP addresses and configuration to hosts. Process Steps: Discovery—Client broadcasts DHCP Discover. Offer—Servers respond with DHCP Offer. Request—Client requests offered IP. Acknowledgment—Server confirms with DHCP ACK. Lease Duration: IP addresses are leased; must be renewed.
Address Resolution Protocol (ARP)
Purpose: Maps IP addresses to MAC addresses. ARP Table: Cache of IP-to-MAC mappings. Process Steps: ARP Request—Broadcast request for MAC. ARP Reply—Host with IP responds with MAC. Updating ARP Cache: Hosts update mappings. Cache Timeout: Entries expire after a set time.
Commonalities Between DHCP and ARP
Broadcast Usage: Both use broadcasts for discovery. Caching: Store information locally. Soft State Management: Information has TTL; refreshed or discarded. Robustness: Designed to handle network changes.