Concept of Network Layer: Interplay between Routing and Forwarding

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Network Layer

Introduction

  • Virtual circuit and datagram networks
  • Routing algorithms
    • Link state
    • Distance vector
    • Hierarchical routing
  • transport segment from sending to receiving host
  • on sending side encapsulates segments into datagrams
  • on rcving side, delivers segments to transport layer
  • network layer protocols in every host, router
  • Router examines header fields in all IP datagrams passing through it
Network Layer

Key Network-Layer Functions

  • Forwarding: move packets from router՚s input to appropriate router output
  • Routing: determine route taken by packets from source to dest.
    • Routing algorithms

Analogy

  • Routing: process of planning trip from source to dest
  • Forwarding: process of getting through single interchange

Interplay between Routing and Forwarding

Interplay between Routing and Forwarding

Network Layer Connection and Connection-Less Service

  • Datagram network provides network-layer connectionless service
  • VC network provides network-layer connection service
  • Analogous to the transport-layer services, but:
    • Service: host-to-host
    • No Choice: network provides one or the other
    • Implementation: in the core

Virtual Circuits

“source-to-dest path behaves much like telephone circuit.”

  • Performance-wise
  • Network actions along source-to-dest path
  • call setup, teardown for each call before data can flow
  • each packet carries VC identifier (not destination host address)
  • every router on source-dest path maintains “state” for each passing connection
  • link, router resources (bandwidth, buffers) may be allocated to VC

VC Implementation

A VC consists of:

  • Path from source to destination
  • VC numbers, one number for each link along path
  • Entries in forwarding tables in routers along path

Packet belonging to VC carries a VC number.

  • VC number must be changed on each link.
  • New VC number comes from forwarding table

Datagram Networks

  • No call setup at network layer
  • Routers: no state about end-to-end connections
    • no network-level concept of “connection”
  • Packets forwarded using destination host address
    • Packets between same source-dest pair may take different paths
Datagram Networks

Routing Algorithm Classification

Global or decentralized information?

Global

  • All routers have complete topology, link cost info
  • “Link state” algorithms

Decentralized

  • Router knows physically-connected neighbors, link costs to neighbors
  • Iterative process of computation, exchange of info with neighbors
  • “Distance vector” algorithms

Static or Dynamic?

Static

Routes change slowly over time

Dynamic

  • Routes change more quickly
  • Periodic update
  • In response to link cost changes

A Link-State Routing Algorithm

Dijkstra՚s Algorithm

  • Net topology, link costs known to all nodes
    • accomplished via “link state broadcast”
    • all nodes have same info
  • Computes least cost paths from one node ( “source” ) to all other nodes
    • Gives forwarding table for that node
  • Iterative: after k iterations, know least cost path to k dest. ՚s

Notation

  • c (x, y) : link cost from node x to y; = ∞ if not direct neighbors
  • D (v) : current value of cost of path from source to dest. v
  • p (v) : predecessor node along path from source to v
  • N՚: set of nodes whose least cost path definitively known

Dijkstra՚s Algorithm: Example

Dijkstra՚s Algorithm: Example
Dijkstra՚s Algorithm: Example

Developed by: