CS 31204: Computer Networks – The Routers

INDIAN INSTITUTE OF TECHNOLOGY

KHARAGPUR

Department of Computer Science and Engineering

Sandip Chakraborty

sandipc@cse.iitkgp.ac.in

​

Abhijnan Chakraborty

abhijnan@cse.iitkgp.ac.in

The Life of a Router

• Do
• Find Path
• Forward, forward, forward, forward, forward
• Find Path
• Forward, forward, forward, forward, forward
• Repeat until powered off

​

• Two basic operations –
• Construct the routing table – the control plane
• Do a routing match and forward the packet to a dedicated interface – the data plane

Indian Institute of Technology Kharagpur

Evolution of Router Architecture

• 1^st Generation (Until 1980’s): Standard Computer

​

• 2^nd Generation (Early 1990’s): Delegate to interfaces

​

• 3^rd Generation (Late 1990’s): Distributed Architecture

​

• 4^th Generation (Early 2000’s): Distributed over multiple racks

​

• 5^th Generation (Today): Software Defined Routing

Indian Institute of Technology Kharagpur

Basic Architectural Components of a Router

​

​

Processor

Memory

CPU

Interconnection Network

Interface card

Interface card

Interface card

Interface card

Indian Institute of Technology Kharagpur

Router Hardware

• Processor is responsible for control functions (route processors)
• Construct the routing table based on the routing algorithm

​

• Forwarding is done at the interface card
• Route match needs to be very fast
• Specialized hardware – Ternary Content-Addressable Memory (TCAM)

Control Plane

Data Plane

Routing Table Construction

Forwarding

Indian Institute of Technology Kharagpur

Router Internals

Indian Institute of Technology Kharagpur

Slotted Chassis – The Physical Infrastructure for Routers

• Large routers are built as slotted chassis
• Interface cards are inserted in the slots
• Route processor is also inserted at a slot
• Simplifies repairs and upgrades of components

Indian Institute of Technology Kharagpur

Functional Components

Routing Functions

IP Forwarding

Table

Update

Route Lookup

Control

Datapath

Per Packet Processing

Indian Institute of Technology Kharagpur

Control Plane in a Router

• Note that a router is a special purpose computer

​

• Implemented as a software (router OS) that supports the basic computing functionalities to run a router along with routing functionalities

​

• Routing protocols are implemented in the router OS

​

• Example: Cisco IOS

Indian Institute of Technology Kharagpur

Routing Functions

• Route Calculation
• Maintenance of the routing table
• Execution of the routing protocol

​

• On commercial routers, routing functions are handled by a single general purpose processor, called the route processor

Indian Institute of Technology Kharagpur

Data Plane of a Router

• Implement forwarding functionalities – make a route lookup and forward the packet at the destination interface

​

• Functionality is similar to a L2 switch – use switch fabric (the mapping from input ports to output ports) to forward the packet from one interface to another

​

• Maintains interface buffer – to implement store and forward functionality

Indian Institute of Technology Kharagpur

IP Forwarding

• Per packet processing of the IP packets

​

• IP forwarding is distributed, handled by individual interface controllers

​

• Special hardware devices are used - TCAM

Indian Institute of Technology Kharagpur

Per Packet Processing – Basic Architectural Components

Routing Table

Indian Institute of Technology Kharagpur

Forwarding Information Base (FIB)

• The interfaces maintains a forwarding information base (FIB) – a mapping from input interface to output interface

​

• A replica of the routing table used at the interfaces for making the forwarding decision

FIB Lookup

Route Lookup

Forward Packet

Input Interface

Output

Interface

PACKET_IN

PACKET_OUT

Routing Protocols

FIB HIT

FIB MISS

Indian Institute of Technology Kharagpur

Difference between RIB and FIB

• Routing Information Base (RIB) – The routing table, implemented in software, is maintained at the control plane

​

• Forwarding Information Base (FIB) – The copy of the required routes maintained in interface TCAM hardware

​

• RIB is dynamic and maintains entire routing information, FIB is updated whenever required

Indian Institute of Technology Kharagpur

RIB and FIB

The RIB

FIB at Eth0

FIB at Eth1

Indian Institute of Technology Kharagpur

RIB Feeds FIB

Image source: Cisco

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

1

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

1

1

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

1

1

0

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

1

1

0

1

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

1

1

0

1

0

0

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

1

1

0

1

0

0

1

1

1

0

0

0

Indian Institute of Technology Kharagpur

Basic TCAM Architecture

Image Source: http://thenetworksherpa.com/tcam-in-the-forwarding-engine/

Let us try to match 1010

1

1

1

1

0

1

0

0

1

1

1

0

0

0

Indian Institute of Technology Kharagpur

Software Defined Networking

Software-defined networking (SDN) is a network framework which involves in separating a network's control functions from its data forwarding functions, centralizing its intelligence, and abstracting its underlying architecture from applications and services.

​

Indian Institute of Technology Kharagpur

Control and Data Plane

Indian Institute of Technology Kharagpur

• Control plane
• The module which takes all decisions, basically an instructor
• The routing algorithm

​

• Data plane
• The module which carries out the tasks given by the control plane
• Forwarding of Packets

Control and Data Plane

Indian Institute of Technology Kharagpur

• Traditional networking devices are proprietary
• Vendors decide software (control plane) and hardware (data plane)
• No standardization

These two modules are “baked” in

Unchangeable

What does separating control and data plane mean?

Indian Institute of Technology Kharagpur

• Vendors only provide the hardware (data plane)

​

• We decide the control plane by writing custom logic – the software

But what if they were separate?

What does separating control and data plane mean?

Indian Institute of Technology Kharagpur

• Vendors only provide the hardware (data plane)
• We decide the control plane by writing custom logic

​

Advantages:

• Features are no longer limited to what the vendor provides
• Community development
• Longer life of products

But what if they were separate?

What does separating control and data plane mean?

Indian Institute of Technology Kharagpur

• Vendors only provide the hardware (data plane)
• We decide the control plane by writing custom logic

​

Advantages:

• Features are no longer limited to what the vendor provides
• Community development
• Longer life of products

But what if they were separate?

How Does SDN Work

Indian Institute of Technology Kharagpur

• Compared to traditional networks, a software defined network has 2 types of devices
• Controller
• Switches

​

• The switches in SDN are blind
• No built-in features
• Need to be instructed by the controller

Zodiac FX - A Tiny SDN Switch

SDN Controller

• “Brains” of the network
• All policies, routing logic are placed in the controller
• “Teaches” the switches what to do with an unknown packet

SDN Controller

• “Brains” of the network
• All policies, routing logic are placed in the controller
• “Teaches” the switches what to do with an unknown packet

Let us now see a scenario where a packet wants to go from h1 to h3 in an SDN environment

Forwarding Request from h1 to s1

SRC - h1

DST - h3

?

Table MISS

Table Miss at s1

No rule is there for h1->h3 at the beginning, so a FIB miss at S1

Till then, the packet is buffered at s1

Packet-IN

Packet-OUT

Packet-IN to Controller

?

Table MISS

The controller generates the rule based on a software program (the routing logic)

Flow Rule Set at s1…

Rule 1

The rule is installed at the FIB of S1

All Future Packets from h1->h3

Rule 1

The buffered packet is forwarded based on that rule

Buffered Packet Forwarded to h3…

Rule 1

All the future packets from h1->h3 follow the same rule

The SDN Architecture

Image source: qmonnet.github.io

Indian Institute of Technology Kharagpur

Traditional Network vs SDN

Image source: http://opensourceforu.com/

Indian Institute of Technology Kharagpur