Network Layer Functions and Protocols

Powerpoint Slide Usage

• The slides are freely available for faculty, students, and readers.
• The slides are in PowerPoint format, allowing for animations and modifications.
• Users are asked to credit the source and copyright when using or posting the slides online.

Network-Layer Functions

• Forwarding: Moving packets from a router's input to an appropriate output router.
• Routing: Determining the route packets take from source to destination. This is handled by the control plane, while forwarding is handled by the data plane.

Routing Protocols

• The goal of a routing protocol is to determine the "good" paths (routes) for packets from the source host to the destination host.
• A path is a sequence of routers packets traverse.
• A "good" path is typically the least cost, fastest, or least congested.

Graph Abstraction of the Network

• Network routers are represented as nodes (N).
• Network links are represented as edges (E) connecting those nodes.

Graph Abstraction: Costs

• The cost of a link (c(x,x')) represents the cost to transmit data across that link.
• The cost of a path (X1, X2, X3...Xp) is the sum of the costs of each individual link in the path.
• A key question in routing is finding the least-cost path between two nodes.

Routing Algorithm Classification

• Routing algorithms can be either global or decentralized, depending on the information available to the routers.
• Global algorithms have complete knowledge of the network topology and link costs.
• Decentralized algorithms, each router knows only about its neighboring routers and links.
• Routing algorithms can be classified as static or dynamic, depending on how the routes change over time.

Dijkstra's Algorithm

• A centralized algorithm that computes the least cost paths from a source node to all other nodes in a graph.
• Works iteratively, finding the minimum-cost node not yet included in the set.
• Updates distances to neighbors based on shortest paths to intermediate nodes.

Dijkstra's Algorithm: Example

• The algorithm provides sequential steps to find paths
• The example shows how to implement Dijkstra’s algorithm.

Distance Vector Algorithm

• Based on Bellman-Ford (BF) equation for dynamic programming.
• Each node maintains a distance vector, which is the estimated cost to every node.

Distance Vector Algorithm: Example

• The example illustrates how nodes exchange their distance vectors
• It also demonstrates how routing information converges towards optimal routes over time (or not).

Distance Vector Algorithm: Link Cost Changes

• If a link cost changes, a node updates its distance vector and informs its neighbors.
• Updates to the distance vector can cause difficulties like count-to-infinity problems.

Making Routing Scalable

• Current networks have many billions of destinations.
• Storing all destinations in routing tables isn't feasible.
• Routing table exchange across nodes will consume a great deal of resources (bandwidth, time).
• Administrative autonomy involves the idea of network management authority.

Internet Approach to Scalable Routing

• Internet routing uses autonomous systems (ASes) to segment the network.
• Intra-AS routing manages routing within an AS (using OSPF).
• Inter-AS routing handles routing between ASes (using BGP)

Hierarchical OSPF

• OSPF (Open Shortest Path First) has a two-level hierarchy: areas and backbone.
• Area border routers summarize distances to destinations within an area.
• Local routers perform routing computations within an area or for outside destinations.
• Boundary routers connect to other ASes.

Internet Inter-AS Routing: BGP

• BGP (Border Gateway Protocol) is the standard for inter-AS routing.
• It enables ASes to advertise their existence, destinations, and paths.
• BGP provides a mechanism to obtain destination network reachability.

BGP, iBGP Connections

• eBGP is used between gateway routers in different ASes.
• iBGP is used between gateway routers within the same AS to exchange local BGP routes.

BGP Basics

• BGP routers exchange messages over semi-permanent TCP connections.
• BGP is a path-vector protocol, meaning routers advertised paths to destinations.
• Network administrators use policy-based routing to control how routing decisions work.

BGP Path Advertisement

• ASes advertise their routes via BGP messages.
• Routers receive and process BGP advertisements via policy and algorithms to choose and propagate routes to other networks.

Path Attributes and BGP Routes

• BGP advertisements include prefixes and attributes, such as AS-PATH, to identify the path taken.
• NEXT-HOP attribute indicates the next hop within the internal-AS router.
• Policy-based routing is for administrative control over the routing decisions.

BGP Achieving Policy via Advertisements

• ISPs only want to advertise traffic to their customer networks to manage local and autonomous system traffic

Different Peering Point Advertisements

• Consistent export is a method to advertise consistent information across peering points, helping avoid inconsistent routing information.

Why Different Intra-, Inter-AS Routing

• Inter-AS routing requires policy to manage who controls routing traffic, whereas intra-AS routing tends to focus on performance.
• BGP routing is hierarchical and summarized, whereas intra-AS uses OSPF to be more efficient

Chapter 5: Summary

• Different types of approaches exist to network control plane.
• Routing protocols (link state, distance vector) are used for routing.
• Implementation of routing in the Internet (OSPF, BGP) is explained.

Next Stop: Link Layer

This quiz explores the core functions of the network layer, including forwarding and routing. It also delves into routing protocols and how paths are determined for data packets. Understanding these concepts is essential for networking students and professionals.